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