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