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