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