minsk.c

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