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