minsk.c

   1 /*
   2  *      Minsk-2 Emulator
   3  *
   4  *      (c) 2010 Martin Mares <mj@ucw.cz>
   5  */
   6
   7 /*
   8  * Things that are not implemented:
   9  *
  10  *      - rounding modes
  11  *      - exact behavior of accumulator/R1/R2 (the manual lacks details)
  12  *      - exact behavior of negative zero
  13  *      - I/O instructions for devices that are not emulated (paper tape
  14  *        reader and puncher, card reader and puncher, magnetic tape unit)
  15  */
  16
  17 #define _GNU_SOURCE
  18
  19 #include <stdio.h>
  20 #include <string.h>
  21 #include <stdlib.h>
  22 #include <stdarg.h>
  23 #include <inttypes.h>
  24 #include <assert.h>
  25 #include <math.h>
  26
  27 static int trace;
  28 static int cpu_quota = -1;
  29 static int print_quota = -1;
  30 static void (*error_hook)(char *msg);
  31
  32 // Minsk-2 has 37-bit words in sign-magnitude representation (bit 36 = sign)
  33 typedef unsigned long long int word;
  34
  35 #define WORD_MASK 01777777777777ULL
  36 #define SIGN_MASK 01000000000000ULL
  37 #define  VAL_MASK 00777777777777ULL
  38
  39 static int wsign(word w)
  40 {
  41   return (w & SIGN_MASK) ? -1 : 1;
  42 }
  43
  44 static word wabs(word w)
  45 {
  46   return w & VAL_MASK;
  47 }
  48
  49 #define WF(w) (wsign(w) < 0 ? '-' : '+'), wabs(w)
  50
  51 static long long wtoll(word w)
  52 {
  53   if (wsign(w) < 0)
  54     return -wabs(w);
  55   else
  56     return wabs(w);
  57 }
  58
  59 static word wfromll(long long x)
  60 {
  61   word w = ((x < 0) ? -x : x) & VAL_MASK;
  62   if (x < 0)
  63     w |= SIGN_MASK;
  64   return w;
  65 }
  66
  67 static double wtofrac(word w)
  68 {
  69   return (double)wtoll(w) / (double)(1ULL << 36);
  70 }
  71
  72 static word wfromfrac(double d)
  73 {
  74   return wfromll((long long)(d * (double)(1ULL << 36)));
  75 }
  76
  77 static int int_in_range(long long x)
  78 {
  79   return (x >= -(long long)VAL_MASK && x <= (long long)VAL_MASK);
  80 }
  81
  82 static int frac_in_range(double d)
  83 {
  84   return (d > -1. && d < 1.);
  85 }
  86
  87 static int wexp(word w)
  88 {
  89   int exp = w & 077;
  90   return (w & 0100 ? -exp : exp);
  91 }
  92
  93 static word wputexp(word w, int exp)
  94 {
  95   return ((w & ~(word)0177) | ((exp < 0) ? 0100 | (-exp) : exp));
  96 }
  97
  98 static int wmanti(word w)
  99 {
 100   return ((w >> 8) & ((1 << 28) - 1));
 101 }
 102
 103 static double wtofloat(word w)
 104 {
 105   double x = wmanti(w);
 106   return ldexp(x, wexp(w) - 28);
 107 }
 108
 109 static int float_in_range(double x)
 110 {
 111   x = fabs(x);
 112   return (x <= ldexp((1 << 28) - 1, 63 - 28));
 113 }
 114
 115 static word wfromfloat(double x, int normalized)
 116 {
 117   word w = 0;
 118   if (x < 0)
 119     {
 120       w |= SIGN_MASK;
 121       x = -x;
 122     }
 123   int exp;
 124   double m = frexp(x, &exp);
 125   word mm = (word) ldexp(m, 28);
 126   if (exp > 63)
 127     assert(0);
 128   else if (exp < -63)
 129     {
 130       if (normalized || exp < -91)
 131         mm=0, exp=0;
 132       else
 133         {
 134           mm >>= -exp - 63;
 135           exp = -63;
 136         }
 137     }
 138   w |= mm << 8;
 139   if (exp < 0)
 140     {
 141       w |= 0100;
 142       exp = -exp;
 143     }
 144   w |= exp;
 145   return w;
 146 }
 147
 148 static word mem[4096];
 149
 150 static word rd(int addr)
 151 {
 152   word val = addr ? mem[addr] : 0;
 153   if (trace > 2)
 154     printf("\tRD %04o = %c%012llo\n", addr, WF(val));
 155   return val;
 156 }
 157
 158 static void wr(int addr, word val)
 159 {
 160   assert(!(val & ~(WORD_MASK)));
 161   if (trace > 2)
 162     printf("\tWR %04o = %c%012llo\n", addr, WF(val));
 163   mem[addr] = val;
 164 }
 165
 166 static int lino;
 167
 168 static void parse_error(char *msg)
 169 {
 170   if (error_hook)
 171     error_hook("Parse error");
 172   printf("Ошибка входа (стр. %d): %s\n", lino, msg);
 173   exit(0);
 174 }
 175
 176 static void parse_in(void)
 177 {
 178   char line[80];
 179   int addr = 0;
 180
 181   while (fgets(line, sizeof(line), stdin))
 182     {
 183       lino++;
 184       char *eol = strchr(line, '\n');
 185       if (!eol)
 186         parse_error("Строка слишком долгая");
 187       *eol = 0;
 188       if (eol > line && eol[-1] == '\r')
 189         *--eol = 0;
 190
 191       char *c = line;
 192       if (!c[0] || c[0] == ';')
 193         {
 194           if (!strncmp(c, ";daji_zor_i_litva=", 18))
 195             {
 196               trace = atoi(c+18);
 197               if (error_hook)
 198                 error_hook("Secret tracing switch flipped");
 199             }
 200           continue;
 201         }
 202
 203       if (c[0] == '.')
 204         return;
 205
 206       if (c[0] == '@')
 207         {
 208           c++;
 209           addr = 0;
 210           for (int i=0; i<4; i++)
 211             {
 212               while (*c == ' ')
 213                 c++;
 214               if (*c >= '0' && *c <= '7')
 215                 addr = 8*addr + *c++ - '0';
 216               else
 217                 parse_error("Плохая цифра");
 218             }
 219           while (*c == ' ')
 220             c++;
 221           if (*c)
 222             parse_error("Адрес слишком долгий");
 223           continue;
 224         }
 225
 226       word w = 0;
 227       if (*c == '-')
 228         w = 1;
 229       else if (*c != '+')
 230         parse_error("Плохой знак");
 231       c++;
 232       for (int i=0; i<12; i++)
 233         {
 234           while (*c == ' ')
 235             c++;
 236           if (*c >= '0' && *c <= '7')
 237             w = 8*w + *c++ - '0';
 238           else
 239             parse_error("Плохая цифра");
 240         }
 241       while (*c == ' ')
 242         c++;
 243       if (*c)
 244         parse_error("Номер слишком долгий");
 245       wr(addr++, w);
 246       addr &= 07777;
 247     }
 248 }
 249
 250 static word acc;
 251 static word r1, r2, current_ins;
 252 static int ip = 00050;                  // Standard program start location
 253 static int prev_ip;
 254
 255 static void stop(char *reason, char *notice)
 256 {
 257   if (error_hook)
 258     error_hook(notice);
 259   printf("Машина остановлена -- %s\n", reason);
 260   printf("СчАК:%04o См:%c%012llo Р1:%c%012llo Р2:%c%012llo\n", prev_ip, WF(acc), WF(r1), WF(r2));
 261   exit(0);
 262 }
 263
 264 static void over(void)
 265 {
 266   stop("Аварийный останов", "Overflow");
 267 }
 268
 269 static void notimp(void)
 270 {
 271   acc = current_ins;
 272   stop("Устройство разбитое", "Not implemented");
 273 }
 274
 275 static void noins(void)
 276 {
 277   acc = current_ins;
 278   stop("Эту команду не знаю", "Illegal instruction");
 279 }
 280
 281 static uint16_t linebuf[128];
 282
 283 static uint16_t russian_chars[64] = {
 284         '0',    '1',    '2',    '3',    '4',    '5',    '6',    '7',    // 0x
 285         '8',    '9',    '+',    '-',    '/',    ',',    '.',    ' ',    // 1x
 286         0x2169, '^',    '(',    ')',    0x00d7, '=',    ';',    '[',    // 2x
 287         ']',    '*',    '`',    '\'',   0x2260, '<',    '>',    ':',    // 3x
 288         0x410,  0x411,  0x412,  0x413,  0x414,  0x415,  0x416,  0x417,  // 4x
 289         0x418,  0x419,  0x41a,  0x41b,  0x41c,  0x41d,  0x41e,  0x41f,  // 5x
 290         0x420,  0x421,  0x422,  0x423,  0x424,  0x425,  0x426,  0x427,  // 6x
 291         0x428,  0x429,  0x42b,  0x42c,  0x42d,  0x42e,  0x42f,  0x2013  // 7x
 292 };
 293
 294 static uint16_t latin_chars[64] = {
 295         '0',    '1',    '2',    '3',    '4',    '5',    '6',    '7',    // 0x
 296         '8',    '9',    '+',    '-',    '/',    ',',    '.',    ' ',    // 1x
 297         0x2169, '^',    '(',    ')',    0x00d7, '=',    ';',    '[',    // 2x
 298         ']',    '*',    '`',    '\'',   0x2260, '<',    '>',    ':',    // 3x
 299         'A',    'B',    'W',    'G',    'D',    'E',    'V',    'Z',    // 4x
 300         'I',    'J',    'K',    'L',    'M',    'N',    'O',    'P',    // 5x
 301         'R',    'S',    'T',    'U',    'F',    'H',    'C',    ' ',    // 6x
 302         ' ',    ' ',    'Y',    'X',    ' ',    ' ',    'Q',    0x2013  // 7x
 303 };
 304
 305 static void print_line(int r)
 306 {
 307   /*
 308    *  Meaning of bits of r:
 309    *    0 = perform line feed
 310    *    1 = clear buffer
 311    *    2 = actually print
 312    */
 313   if (r & 4)
 314     {
 315       if (print_quota > 0 && !--print_quota)
 316         stop("Бумага дошла - нужно ехать в Сибирь про новую", "Out of paper");
 317       for (int i=0; i<128; i++)
 318         {
 319           int ch = linebuf[i];
 320           if (!ch)
 321             ch = ' ';
 322           if (ch < 0x80)
 323             putchar(ch);
 324           else if (ch < 0x800)
 325             {
 326               putchar(0xc0 | (ch >> 6));
 327               putchar(0x80 | (ch & 0x3f));
 328             }
 329           else
 330             {
 331               putchar(0xe0 | (ch >> 12));
 332               putchar(0x80 | ((ch >> 6) & 0x3f));
 333               putchar(0x80 | (ch & 0x3f));
 334             }
 335         }
 336     }
 337   if (r & 2)
 338     memset(linebuf, 0, sizeof(linebuf));
 339   if (r & 1)
 340     putchar('\n');
 341   else if (r & 4)
 342     putchar('\r');
 343   fflush(stdout);
 344 }
 345
 346 static void print_ins(int x, int y)
 347 {
 348   word yy = rd(y);
 349   int pos = x & 0177;
 350   int r = (x >> 9) & 7;
 351
 352   if (x & 0400)
 353     {
 354       print_line(r);
 355       return;
 356     }
 357
 358   char *fmt;
 359   int bit = 37;
 360   int eat = 0;
 361   switch (r)
 362     {
 363     case 0:                             // Decimal float
 364       fmt = "+dddddddx+xbd";
 365       break;
 366     case 1:                             // Octal number
 367       fmt = "+oooooooooooo";
 368       break;
 369     case 2:                             // Decimal fixed
 370       fmt = "+ddddddddd";
 371       break;
 372     case 3:                             // Decimal unsigned
 373       fmt = "x ddddddddd";
 374       eat = 1;
 375       break;
 376     case 4:                             // One Russian symbol
 377       fmt = "xr";
 378       break;
 379     case 5:                             // Russian text
 380       fmt = "xrrrrrr";
 381       break;
 382     case 6:                             // One Latin symbol
 383       fmt = "xl";
 384       break;
 385     default:                            // Latin text
 386       fmt = "xllllll";
 387     }
 388
 389   while (*fmt)
 390     {
 391       int ch;
 392       switch (*fmt++)
 393         {
 394         case 'x':
 395           bit--;
 396           continue;
 397         case ' ':
 398           ch = ' ';
 399           break;
 400         case '+':
 401           bit--;
 402           ch = (yy & (1ULL << bit)) ? '-' : '+';
 403           break;
 404         case 'b':
 405           bit--;
 406           ch = '0' + ((yy >> bit) & 1);
 407           break;
 408         case 'o':
 409           bit -= 3;
 410           ch = '0' + ((yy >> bit) & 7);
 411           break;
 412         case 'd':
 413           bit -= 4;
 414           ch = '0' + ((yy >> bit) & 15);
 415           if (ch > '0' + 9)
 416             ch += 7;
 417           break;
 418         case 'r':
 419           bit -= 6;
 420           ch = russian_chars[(yy >> bit) & 077];
 421           break;
 422         case 'l':
 423           bit -= 6;
 424           ch = latin_chars[(yy >> bit) & 077];
 425           break;
 426         default:
 427           assert(0);
 428         }
 429
 430       if (eat && *fmt)
 431         {
 432           if (ch == '0' || ch == ' ')
 433             ch = ' ';
 434           else
 435             eat = 0;
 436         }
 437       linebuf[pos] = ch;
 438       pos = (pos+1) & 0177;
 439     }
 440   assert(bit >= 0);
 441 }
 442
 443 static void run(void)
 444 {
 445   for (;;)
 446     {
 447       r2 = acc;
 448       prev_ip = ip;
 449       word w = mem[ip];
 450       current_ins = w;
 451
 452       int op = (w >> 30) & 0177;        // Operation code
 453       int ax = (w >> 28) & 3;           // Address extensions not supported
 454       int ix = (w >> 24) & 15;          // Indexing
 455       int x = (w >> 12) & 07777;        // Operands (original form)
 456       int y = w & 07777;
 457       int xi=x, yi=y;                   // (indexed form)
 458       if (trace)
 459         printf("@%04o  %c%02o %02o %04o %04o\n",
 460           ip,
 461           (w & SIGN_MASK) ? '-' : '+',
 462           (int)((w >> 30) & 077),
 463           (int)((w >> 24) & 077),
 464           x,
 465           y);
 466       if (ix)
 467         {
 468           if (op != 0120)
 469             {
 470               word i = rd(ix);
 471               xi = (xi + (int)((i >> 12) & 07777)) & 07777;
 472               yi = (yi + (int)(i & 07777)) & 07777;
 473               if (trace > 2)
 474                 printf("\tIndexing -> %04o %04o\n", xi, yi);
 475             }
 476         }
 477       ip = (ip+1) & 07777;
 478
 479       if (cpu_quota > 0 && !--cpu_quota)
 480         stop("Тайм-аут", "CPU quota exceeded");
 481
 482       /* Arithmetic operations */
 483
 484       word a, b, c;
 485       long long aa, bb, cc;
 486       double ad, bd;
 487       int i;
 488
 489       auto void afetch(void);
 490       void afetch(void)
 491         {
 492           if (op & 2)
 493             a = r2;
 494           else
 495             a = rd(yi);
 496           b = r1 = rd(xi);
 497         }
 498
 499       auto void astore(word result);
 500       void astore(word result)
 501         {
 502           acc = result;
 503           if (op & 1)
 504             wr(yi, acc);
 505         }
 506
 507       auto void astore_int(long long x);
 508       void astore_int(long long x)
 509         {
 510           if (!int_in_range(x))
 511             over();
 512           astore(wfromll(x));
 513         }
 514
 515       auto void astore_frac(double f);
 516       void astore_frac(double f)
 517         {
 518           if (!frac_in_range(f))
 519             over();
 520           astore(wfromfrac(f));
 521         }
 522
 523       auto void astore_float(double f);
 524       void astore_float(double f)
 525         {
 526           if (!float_in_range(f))
 527             over();
 528           astore(wfromfloat(f, 0));
 529         }
 530
 531       if (ax)
 532         op = -1;
 533       switch (op)
 534         {
 535         case 000:               // NOP
 536           break;
 537         case 004 ... 007:       // XOR
 538           afetch();
 539           astore(a^b);
 540           break;
 541         case 010 ... 013:       // FIX addition
 542           afetch();
 543           astore_int(wtoll(a) + wtoll(b));
 544           break;
 545         case 014 ... 017:       // FP addition
 546           afetch();
 547           astore_float(wtofloat(a) + wtofloat(b));
 548           break;
 549         case 020 ... 023:       // FIX subtraction
 550           afetch();
 551           astore_int(wtoll(a) - wtoll(b));
 552           break;
 553         case 024 ... 027:       // FP subtraction
 554           afetch();
 555           astore_float(wtofloat(a) - wtofloat(b));
 556           break;
 557         case 030 ... 033:       // FIX multiplication
 558           afetch();
 559           astore_frac(wtofrac(a) * wtofrac(b));
 560           break;
 561         case 034 ... 037:       // FP multiplication
 562           afetch();
 563           astore_float(wtofloat(a) * wtofloat(b));
 564           break;
 565         case 040 ... 043:       // FIX division
 566           afetch();
 567           ad = wtofrac(a);
 568           bd = wtofrac(b);
 569           if (!wabs(b))
 570             over();
 571           astore_frac(ad / bd);
 572           break;
 573         case 044 ... 047:       // FP division
 574           afetch();
 575           ad = wtofloat(a);
 576           bd = wtofloat(b);
 577           if (!bd || wexp(b) < -63)
 578             over();
 579           astore_float(ad / bd);
 580           break;
 581         case 050 ... 053:       // FIX subtraction of abs values
 582           afetch();
 583           astore_int(wabs(a) - wabs(b));
 584           break;
 585         case 054 ... 057:       // FP subtraction of abs values
 586           afetch();
 587           astore_float(fabs(wtofloat(a)) - fabs(wtofloat(b)));
 588           break;
 589         case 060 ... 063:       // Shift logical
 590           afetch();
 591           i = wexp(b);
 592           if (i <= -37 || i >= 37)
 593             astore(0);
 594           else if (i >= 0)
 595             astore((a << i) & WORD_MASK);
 596           else
 597             astore(a >> (-i));
 598           break;
 599         case 064 ... 067:       // Shift arithmetical
 600           afetch();
 601           i = wexp(b);
 602           aa = wabs(a);
 603           if (i <= -36 || i >= 36)
 604             cc = 0;
 605           else if (i >= 0)
 606             cc = (aa << i) & VAL_MASK;
 607           else
 608             cc = aa >> (-i);
 609           astore((a & SIGN_MASK) | wfromll(cc));
 610           break;
 611         case 070 ... 073:       // And
 612           afetch();
 613           astore(a&b);
 614           break;
 615         case 074 ... 077:       // Or
 616           afetch();
 617           astore(a|b);
 618           break;
 619
 620         case 0100:              // Halt
 621           r1 = rd(x);
 622           acc = rd(y);
 623           stop("Останов машины", "Halted");
 624         case 0103:              // I/O magtape
 625           notimp();
 626         case 0104:              // Disable rounding
 627           notimp();
 628         case 0105:              // Enable rounding
 629           notimp();
 630         case 0106:              // Interrupt control
 631           notimp();
 632         case 0107:              // Reverse tape
 633           notimp();
 634         case 0110:              // Move
 635           wr(yi, r1 = acc = rd(xi));
 636           break;
 637         case 0111:              // Move negative
 638           wr(yi, acc = (r1 = rd(xi)) ^ SIGN_MASK);
 639           break;
 640         case 0112:              // Move absolute value
 641           wr(yi, acc = (r1 = rd(xi)) & VAL_MASK);
 642           break;
 643         case 0113:              // Read from keyboard
 644           notimp();
 645         case 0114:              // Copy sign
 646           wr(yi, acc = rd(yi) ^ ((r1 = rd(xi)) & SIGN_MASK));
 647           break;
 648         case 0115:              // Read code from R1 (obscure)
 649           notimp();
 650         case 0116:              // Copy exponent
 651           wr(yi, acc = wputexp(rd(yi), wexp(r1 = rd(xi))));
 652           break;
 653         case 0117:              // I/O teletype
 654           notimp();
 655         case 0120:              // Loop
 656           if (!ix)
 657             noins();
 658           a = r1 = rd(ix);
 659           aa = (a >> 24) & 017777;
 660           if (!aa)
 661             break;
 662           b = rd(y);            // (a mountain range near Prague)
 663           acc = ((aa-1) << 24) |
 664                 (((((a >> 12) & 07777) + (b >> 12) & 07777) & 07777) << 12) |
 665                 (((a & 07777) + (b & 07777)) & 07777);
 666           wr(ix, acc);
 667           ip = x;
 668           break;
 669         case 0130:              // Jump
 670           wr(y, r2);
 671           ip = x;
 672           break;
 673         case 0131:              // Jump to subroutine
 674           wr(y, acc = ((030ULL << 30) | ((ip & 07777ULL) << 12)));
 675           ip = x;
 676           break;
 677         case 0132:              // Jump if positive
 678           if (wsign(r2) >= 0)
 679             ip = x;
 680           else
 681             ip = y;
 682           break;
 683         case 0133:              // Jump if overflow
 684           // Since we always trap on overflow, this instruction always jumps to the 1st address
 685           ip = x;
 686           break;
 687         case 0134:              // Jump if zero
 688           if (!wabs(r2))
 689             ip = y;
 690           else
 691             ip = x;
 692           break;
 693         case 0135:              // Jump if key pressed
 694           // No keys are ever pressed, so always jump to 2nd
 695           ip = y;
 696           break;
 697         case 0136:              // Interrupt masking
 698           notimp();
 699         case 0137:              // Used only when reading from tape
 700           notimp();
 701         case 0140 ... 0147:     // I/O
 702           notimp();
 703         case 0150 ... 0154:     // I/O
 704           notimp();
 705         case 0160 ... 0161:     // I/O
 706           notimp();
 707         case 0162:              // Printing
 708           print_ins(x, y);
 709           break;
 710         case 0163:              // I/O
 711           notimp();
 712         case 0170:              // FIX multiplication, bottom part
 713           afetch();
 714           if (wtofrac(a) * wtofrac(b) >= .1/(1ULL << 32))
 715             over();
 716           acc = wfromll(((unsigned long long)wabs(a) * (unsigned long long)wabs(b)) & VAL_MASK);
 717           // XXX: What should be the sign? The book does not define that.
 718           break;
 719         case 0171:              // Modulo
 720           afetch();
 721           aa = wabs(a);
 722           bb = wabs(b);
 723           if (!bb)
 724             over();
 725           cc = aa % bb;
 726           if (wsign(b) < 0)
 727             cc = -cc;
 728           acc = wfromll(cc);
 729           break;
 730         case 0172:              // Add exponents
 731           a = r1 = rd(xi);
 732           b = rd(yi);
 733           i = wexp(a) + wexp(b);
 734           if (i < -63 || i > 63)
 735             over();
 736           acc = wputexp(b, i);
 737           wr(yi, acc);
 738           break;
 739         case 0173:              // Sub exponents
 740           a = r1 = rd(xi);
 741           b = rd(yi);
 742           i = wexp(b) - wexp(a);
 743           if (i < -63 || i > 63)
 744             over();
 745           acc = wputexp(b, i);
 746           wr(yi, acc);
 747           break;
 748         case 0174:              // Addition in one's complement
 749           a = r1 = rd(xi);
 750           b = rd(yi);
 751           c = a + b;
 752           if (c > VAL_MASK)
 753             c = c - VAL_MASK;
 754           wr(yi, c);
 755           // XXX: The effect on the accumulator is undocumented, but likely to be as follows:
 756           acc = c;
 757           break;
 758         case 0175:              // Normalization
 759           a = r1 = rd(xi);
 760           if (!wabs(a))
 761             {
 762               wr(yi, 0);
 763               wr((yi+1) & 07777, 0);
 764               acc = 0;
 765             }
 766           else
 767             {
 768               i = 0;
 769               acc = a & SIGN_MASK;
 770               a &= VAL_MASK;
 771               while (!(a & (SIGN_MASK >> 1)))
 772                 {
 773                   a <<= 1;
 774                   i++;
 775                 }
 776               acc |= a;
 777               wr(yi, acc);
 778               wr((yi+1) & 07777, i);
 779             }
 780           break;
 781         case 0176:              // Population count
 782           a = r1 = rd(xi);
 783           cc = 0;
 784           for (int i=0; i<36; i++)
 785             if (a & (1ULL << i))
 786               cc++;
 787           // XXX: Guessing that acc gets a copy of the result
 788           acc = wfromll(cc);
 789           wr(yi, acc);
 790           break;
 791         default:
 792           noins();
 793         }
 794
 795       if (trace > 1)
 796         printf("\tACC:%c%012llo R1:%c%012llo R2:%c%012llo\n", WF(acc), WF(r1), WF(r2));
 797     }
 798 }
 799
 800 /*** Daemon interface ***/
 801
 802 #include <unistd.h>
 803 #include <errno.h>
 804 #include <time.h>
 805 #include <syslog.h>
 806 #include <sys/signal.h>
 807 #include <sys/wait.h>
 808 #include <sys/poll.h>
 809 #include <sys/socket.h>
 810 #include <netinet/in.h>
 811 #include <arpa/inet.h>
 812
 813 #if 0
 814 #define DTRACE(msg, args...) fprintf(stderr, msg "\n", ##args)
 815 #define DLOG(msg, args...) fprintf(stderr, msg "\n", ##args)
 816 #else
 817 #define DTRACE(msg, args...) do { } while(0)
 818 #define DLOG(msg, args...) syslog(LOG_INFO, msg, ##args)
 819 #endif
 820
 821 #define MAX_CONNECTIONS 50              // Per daemon
 822 #define MAX_CONNS_PER_IP 1              // Per IP
 823 #define MAX_TRACKERS 200                // IP address trackers
 824 #define TBF_MAX 5                       // Max number of tokens in the bucket
 825 #define TBF_REFILL_PER_SEC 0.2          // Bucket refill rate (buckets/sec)
 826
 827 #define PID_FILE "/var/run/pd-minsk.pid"
 828 #define UID 124
 829 #define GID 125
 830
 831 static void die(char *msg)
 832 {
 833   fprintf(stderr, "minsk: ");
 834   fprintf(stderr, msg);
 835   fputc('\n', stderr);
 836   exit(1);
 837 }
 838
 839 static char **spt_argv;
 840 static char *spt_start, *spt_end;
 841
 842 static void setproctitle_init(int argc, char **argv)
 843 {
 844   int i, len;
 845   char **env, **oldenv, *t;
 846
 847   spt_argv = argv;
 848
 849   /* Create a backup copy of environment */
 850   oldenv = __environ;
 851   len = 0;
 852   for (i=0; oldenv[i]; i++)
 853     len += strlen(oldenv[i]) + 1;
 854   __environ = env = malloc(sizeof(char *)*(i+1));
 855   t = malloc(len);
 856   if (!__environ || !t)
 857     die("malloc failed");
 858   for (i=0; oldenv[i]; i++)
 859     {
 860       env[i] = t;
 861       len = strlen(oldenv[i]) + 1;
 862       memcpy(t, oldenv[i], len);
 863       t += len;
 864     }
 865   env[i] = NULL;
 866
 867   /* Scan for consecutive free space */
 868   spt_start = spt_end = argv[0];
 869   for (i=0; i<argc; i++)
 870     if (!i || spt_end+1 == argv[i])
 871       spt_end = argv[i] + strlen(argv[i]);
 872   for (i=0; oldenv[i]; i++)
 873     if (spt_end+1 == oldenv[i])
 874       spt_end = oldenv[i] + strlen(oldenv[i]);
 875 }
 876
 877 static void
 878 setproctitle(const char *msg, ...)
 879 {
 880   va_list args;
 881   char buf[256];
 882   int n;
 883
 884   va_start(args, msg);
 885   if (spt_end > spt_start)
 886     {
 887       n = vsnprintf(buf, sizeof(buf), msg, args);
 888       if (n >= (int) sizeof(buf) || n < 0)
 889         sprintf(buf, "<too-long>");
 890       n = spt_end - spt_start;
 891       strncpy(spt_start, buf, n);
 892       spt_start[n] = 0;
 893       spt_argv[0] = spt_start;
 894       spt_argv[1] = NULL;
 895     }
 896   va_end(args);
 897 }
 898
 899 static void sigchld_handler(int sig __attribute__((unused)))
 900 {
 901 }
 902
 903 static void sigalrm_handler(int sig __attribute__((unused)))
 904 {
 905   const char err[] = "--- Timed out. Time machine disconnected. ---\n";
 906   write(1, err, sizeof(err));
 907   DLOG("Connection timed out");
 908   exit(0);
 909 }
 910
 911 static void child_error_hook(char *err)
 912 {
 913   DLOG("Stopped: %s", err);
 914 }
 915
 916 static void child(int sk2)
 917 {
 918   dup2(sk2, 0);
 919   dup2(sk2, 1);
 920   close(sk2);
 921
 922   struct sigaction sact = {
 923     .sa_handler = sigalrm_handler,
 924   };
 925   if (sigaction(SIGALRM, &sact, NULL) < 0)
 926     die("sigaction: %m");
 927
 928   // Set up limits
 929   alarm(60);
 930   cpu_quota = 100000;
 931   print_quota = 100;
 932
 933   const char welcome[] = "+++ Welcome to our computer museum. +++\n+++ Our time machine will connect you to one of our exhibits. +++\n\n";
 934   write(1, welcome, sizeof(welcome));
 935
 936   error_hook = child_error_hook;
 937   parse_in();
 938   run();
 939   fflush(stdout);
 940   DTRACE("Finished");
 941 }
 942
 943 struct conn {
 944   pid_t pid;
 945   struct in_addr addr;
 946   struct tracker *tracker;
 947 };
 948
 949 static struct conn connections[MAX_CONNECTIONS];
 950
 951 static struct conn *get_conn(struct in_addr *a)
 952 {
 953   for (int i=0; i<MAX_CONNECTIONS; i++)
 954     {
 955       struct conn *c = &connections[i];
 956       if (!c->pid)
 957         {
 958           memcpy(&c->addr, a, sizeof(struct in_addr));
 959           return c;
 960         }
 961     }
 962   return NULL;
 963 }
 964
 965 static struct conn *pid_to_conn(pid_t pid)
 966 {
 967   for (int i=0; i<MAX_CONNECTIONS; i++)
 968     {
 969       struct conn *c = &connections[i];
 970       if (c->pid == pid)
 971         return c;
 972     }
 973   return NULL;
 974 }
 975
 976 static void put_conn(struct conn *c)
 977 {
 978   c->pid = 0;
 979   c->tracker = NULL;
 980 }
 981
 982 struct tracker {
 983   struct in_addr addr;
 984   int active_conns;
 985   time_t last_access;
 986   double tokens;
 987 };
 988
 989 static struct tracker trackers[MAX_TRACKERS];
 990
 991 static int get_tracker(struct conn *c)
 992 {
 993   struct tracker *t;
 994   time_t now = time(NULL);
 995   int i;
 996
 997   for (i=0; i<MAX_TRACKERS; i++)
 998     {
 999       t = &trackers[i];
1000       if (!memcmp(&t->addr, &c->addr, sizeof(struct in_addr)))
1001         break;
1002     }
1003   if (i < MAX_TRACKERS)
1004     {
1005       if (now > t->last_access)
1006         {
1007           t->tokens += (now - t->last_access) * (double) TBF_REFILL_PER_SEC;
1008           t->last_access = now;
1009           if (t->tokens > TBF_MAX)
1010             t->tokens = TBF_MAX;
1011         }
1012       DTRACE("TBF: Using tracker %d (%.3f tokens)", i, t->tokens);
1013     }
1014   else
1015     {
1016       int min_i = -1;
1017       for (int i=0; i<MAX_TRACKERS; i++)
1018         {
1019           t = &trackers[i];
1020           if (!t->active_conns && (min_i < 0 || t->last_access < trackers[min_i].last_access))
1021             min_i = i;
1022         }
1023       if (min_i < 0)
1024         {
1025           DLOG("TBF: Out of trackers!");
1026           return 0;
1027         }
1028       t = &trackers[min_i];
1029       if (t->last_access)
1030         DTRACE("TBF: Recycling tracker %d", min_i);
1031       else
1032         DTRACE("TBF: Creating tracker %d", min_i);
1033       memset(t, 0, sizeof(*t));
1034       t->addr = c->addr;
1035       t->last_access = now;
1036       t->tokens = TBF_MAX;
1037     }
1038
1039   if (t->active_conns >= MAX_CONNS_PER_IP)
1040     {
1041       DTRACE("TBF: Too many conns per IP");
1042       return 0;
1043     }
1044
1045   if (t->tokens >= 0.999)
1046     {
1047       t->tokens -= 1;
1048       t->active_conns++;
1049       c->tracker = t;
1050       DTRACE("TBF: Passed (%d conns)", t->active_conns);
1051       return 1;
1052     }
1053   else
1054     {
1055       DTRACE("TBF: Failed");
1056       t->tokens = 0;
1057       return 0;
1058     }
1059 }
1060
1061 static void put_tracker(struct conn *c)
1062 {
1063   struct tracker *t = c->tracker;
1064   if (!t)
1065     {
1066       DLOG("put_tracker: no tracker?");
1067       sleep(5);
1068       return;
1069     }
1070   if (t->active_conns <= 0)
1071     {
1072       DLOG("put_tracker: no counter?");
1073       sleep(5);
1074       return;
1075     }
1076   t->active_conns--;
1077   DTRACE("TBF: Put tracker (%d conns remain)", t->active_conns);
1078 }
1079
1080 static void run_as_daemon(int do_fork)
1081 {
1082   int sk = socket(PF_INET, SOCK_STREAM, IPPROTO_TCP);
1083   if (sk < 0)
1084     die("socket: %m");
1085
1086   int one = 1;
1087   if (setsockopt(sk, SOL_SOCKET, SO_REUSEADDR, &one, sizeof(one)) < 0)
1088     die("setsockopt: %m");
1089
1090   struct sockaddr_in sa = {
1091     .sin_family = AF_INET,
1092     .sin_port = ntohs(1969),
1093     .sin_addr.s_addr = INADDR_ANY,
1094   };
1095   if (bind(sk, (struct sockaddr *) &sa, sizeof(sa)) < 0)
1096     die("bind: %m");
1097   if (listen(sk, 128) < 0)
1098     die("listen: %m");
1099   // if (fcntl(sk, F_SETFL, O_NONBLOCK) < 0)
1100   //  die("fcntl: %m");
1101
1102   if (do_fork)
1103     {
1104       pid_t pid = fork();
1105       if (pid < 0)
1106         die("fork: %m");
1107       if (pid)
1108         {
1109           FILE *f = fopen(PID_FILE, "w");
1110           if (f)
1111             {
1112               fprintf(f, "%d\n", pid);
1113               fclose(f);
1114             }
1115           exit(0);
1116         }
1117
1118       chdir("/");
1119       setresgid(GID, GID, GID);
1120       setresuid(UID, UID, UID);
1121       setsid();
1122     }
1123
1124   struct sigaction sact = {
1125     .sa_handler = sigchld_handler,
1126     .sa_flags = SA_RESTART,
1127   };
1128   if (sigaction(SIGCHLD, &sact, NULL) < 0)
1129     die("sigaction: %m");
1130
1131   DLOG("Daemon ready");
1132   setproctitle("minsk: Listening");
1133   openlog("minsk", LOG_PID, LOG_LOCAL7);
1134
1135   for (;;)
1136     {
1137       struct pollfd pfd[1] = {
1138         { .fd = sk, .events = POLLIN },
1139       };
1140
1141       int nfds = poll(pfd, 1, 60000);
1142       if (nfds < 0 && errno != EINTR)
1143         {
1144           DLOG("poll: %m");
1145           sleep(5);
1146           continue;
1147         }
1148
1149       int status;
1150       pid_t pid;
1151       while ((pid = waitpid(-1, &status, WNOHANG)) > 0)
1152         {
1153           if (!WIFEXITED(status) || WEXITSTATUS(status))
1154             DLOG("Process %d exited with strange status %x", pid, status);
1155
1156           struct conn *conn = pid_to_conn(pid);
1157           if (conn)
1158             {
1159               DTRACE("Connection with PID %d exited", pid);
1160               put_tracker(conn);
1161               put_conn(conn);
1162             }
1163           else
1164             DTRACE("PID %d exited, matching no connection", pid);
1165         }
1166
1167       if (!(pfd[0].revents & POLLIN))
1168         continue;
1169
1170       socklen_t salen = sizeof(sa);
1171       int sk2 = accept(sk, (struct sockaddr *) &sa, &salen);
1172       if (sk2 < 0)
1173         {
1174           if (errno != EINTR)
1175             {
1176               DLOG("accept: %m");
1177               sleep(5);
1178             }
1179           continue;
1180         }
1181       DTRACE("Got connection: fd=%d", sk2);
1182
1183       struct conn *conn = get_conn(&sa.sin_addr);
1184       const char *reason = NULL;
1185       if (conn)
1186         {
1187           if (!get_tracker(conn))
1188             {
1189               DLOG("Connection from %s dropped: Throttling", inet_ntoa(sa.sin_addr));
1190               put_conn(conn);
1191               conn = NULL;
1192               reason = "--- Sorry, but you are sending too many requests. Please slow down. ---\n";
1193             }
1194         }
1195       else
1196         {
1197           DLOG("Connection from %s dropped: Too many connections", inet_ntoa(sa.sin_addr));
1198           reason = "--- Sorry, maximum number of connections exceeded. Please come later. ---\n";
1199         }
1200
1201       pid = fork();
1202       if (pid < 0)
1203         {
1204           DLOG("fork failed: %m");
1205           close(sk2);
1206           continue;
1207         }
1208       if (!pid)
1209         {
1210           close(sk);
1211           if (conn)
1212             {
1213               DLOG("Accepted connection from %s", inet_ntoa(sa.sin_addr));
1214               setproctitle("minsk: %s", inet_ntoa(sa.sin_addr));
1215               child(sk2);
1216             }
1217           else
1218             {
1219               DLOG("Sending error message to %s", inet_ntoa(sa.sin_addr));
1220               setproctitle("minsk: %s ERR", inet_ntoa(sa.sin_addr));
1221               write(sk2, reason, strlen(reason));
1222             }
1223           exit(0);
1224         }
1225
1226       DTRACE("Created process %d", pid);
1227       if (conn)
1228         conn->pid = pid;
1229       close(sk2);
1230     }
1231 }
1232
1233 static void init_memory(void)
1234 {
1235   // For the contest, we fill the whole memory with -00 00 0000 0000 (HALT),
1236   // not +00 00 0000 0000 (NOP). Otherwise, an empty program would reveal
1237   // the location of the password :)
1238   for (int i=0; i<4096; i++)
1239     mem[i] = 01000000000000ULL;
1240
1241   // Store the password
1242   int pos = 02655;
1243   mem[pos++] = 0574060565373;
1244   mem[pos++] = 0371741405340;
1245   mem[pos++] = 0534051524017;
1246 }
1247
1248 int main(int argc, char **argv)
1249 {
1250   init_memory();
1251
1252   if (argc > 1)
1253     {
1254       setproctitle_init(argc, argv);
1255       if (!strcmp(argv[1], "--daemon"))
1256         run_as_daemon(1);
1257       else if (!strcmp(argv[1], "--net"))
1258         run_as_daemon(0);
1259       else if (!strncmp(argv[1], "--trace=", 8))
1260         trace = atoi(argv[1] + 8);
1261       else
1262         die("Usage: minsk [--daemon | --net]");
1263     }
1264
1265   parse_in();
1266   run();
1267   return 0;
1268 }