minsk.c

   1 /*
   2  *      Minsk-2 Emulator
   3  *
   4  *      (c) 2010 Martin Mares <mj@ucw.cz>
   5  */
   6
   7 /*
   8  * TODO:
   9  *      - debugging/play mode
  10  *      - we probably have to disable NOP
  11  */
  12
  13 /*
  14  * Things that are not implemented:
  15  *
  16  *      - rounding modes
  17  *      - exact behavior of accumulator/R1/R2 (the manual lacks details)
  18  *      - exact behavior of negative zero
  19  *      - I/O instructions for devices that are not emulated (paper tape
  20  *        reader and puncher, card reader and puncher, magnetic tape unit)
  21  */
  22
  23 #include <stdio.h>
  24 #include <string.h>
  25 #include <stdlib.h>
  26 #include <inttypes.h>
  27 #include <assert.h>
  28 #include <math.h>
  29
  30 static int trace = 3;
  31 static int cpu_quota = -1;
  32 static int print_quota = -1;
  33
  34 // Minsk-2 has 37-bit words in sign-magnitude representation (bit 36 = sign)
  35 typedef unsigned long long int word;
  36
  37 #define WORD_MASK 01777777777777ULL
  38 #define SIGN_MASK 01000000000000ULL
  39 #define  VAL_MASK 00777777777777ULL
  40
  41 static int wsign(word w)
  42 {
  43   return (w & SIGN_MASK) ? -1 : 1;
  44 }
  45
  46 static word wabs(word w)
  47 {
  48   return w & VAL_MASK;
  49 }
  50
  51 #define WF(w) (wsign(w) < 0 ? '-' : '+'), wabs(w)
  52
  53 static long long wtoll(word w)
  54 {
  55   if (wsign(w) < 0)
  56     return -wabs(w);
  57   else
  58     return wabs(w);
  59 }
  60
  61 static word wfromll(long long x)
  62 {
  63   word w = ((x < 0) ? -x : x) & VAL_MASK;
  64   if (x < 0)
  65     w |= SIGN_MASK;
  66   return w;
  67 }
  68
  69 static double wtofrac(word w)
  70 {
  71   return (double)wtoll(w) / (double)(1ULL << 36);
  72 }
  73
  74 static word wfromfrac(double d)
  75 {
  76   return wfromll((long long)(d * (double)(1ULL << 36)));
  77 }
  78
  79 static int int_in_range(long long x)
  80 {
  81   return (x >= -(long long)VAL_MASK && x <= (long long)VAL_MASK);
  82 }
  83
  84 static int frac_in_range(double d)
  85 {
  86   return (d > -1. && d < 1.);
  87 }
  88
  89 static int wexp(word w)
  90 {
  91   int exp = w & 077;
  92   return (w & 0100 ? -exp : exp);
  93 }
  94
  95 static word wputexp(word w, int exp)
  96 {
  97   return ((w & ~(word)0177) | ((exp < 0) ? 0100 | (-exp) : exp));
  98 }
  99
 100 static int wmanti(word w)
 101 {
 102   return ((w >> 8) & ((1 << 28) - 1));
 103 }
 104
 105 static double wtofloat(word w)
 106 {
 107   double x = wmanti(w);
 108   return ldexp(x, wexp(w) - 28);
 109 }
 110
 111 static int float_in_range(double x)
 112 {
 113   x = fabs(x);
 114   return (x <= ldexp((1 << 28) - 1, 63 - 28));
 115 }
 116
 117 static word wfromfloat(double x, int normalized)
 118 {
 119   word w = 0;
 120   if (x < 0)
 121     {
 122       w |= SIGN_MASK;
 123       x = -x;
 124     }
 125   int exp;
 126   double m = frexp(x, &exp);
 127   word mm = (word) ldexp(m, 28);
 128   if (exp > 63)
 129     assert(0);
 130   else if (exp < -63)
 131     {
 132       if (normalized || exp < -91)
 133         mm=0, exp=0;
 134       else
 135         {
 136           mm >>= -exp - 63;
 137           exp = -63;
 138         }
 139     }
 140   w |= mm << 8;
 141   if (exp < 0)
 142     {
 143       w |= 0100;
 144       exp = -exp;
 145     }
 146   w |= exp;
 147   return w;
 148 }
 149
 150 static word mem[4096];
 151
 152 static word rd(int addr)
 153 {
 154   word val = addr ? mem[addr] : 0;
 155   if (trace > 2)
 156     printf("\tRD %04o = %c%012llo\n", addr, WF(val));
 157   return val;
 158 }
 159
 160 static void wr(int addr, word val)
 161 {
 162   assert(!(val & ~(WORD_MASK)));
 163   if (trace > 2)
 164     printf("\tWR %04o = %c%012llo\n", addr, WF(val));
 165   mem[addr] = val;
 166 }
 167
 168 static int lino;
 169
 170 static void parse_error(char *msg)
 171 {
 172   printf("Ошибка входа (стр. %d): %s\n", lino, msg);
 173   exit(1);
 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         continue;
 192       if (c[0] == '@')
 193         {
 194           c++;
 195           addr = 0;
 196           for (int i=0; i<4; i++)
 197             {
 198               while (*c == ' ')
 199                 c++;
 200               if (*c >= '0' && *c <= '7')
 201                 addr = 8*addr + *c++ - '0';
 202               else
 203                 parse_error("Плохая цифва");
 204             }
 205           while (*c == ' ')
 206             c++;
 207           if (*c)
 208             parse_error("Адрес слишком долгий");
 209           continue;
 210         }
 211
 212       word w = 0;
 213       if (*c == '-')
 214         w = 1;
 215       else if (*c != '+')
 216         parse_error("Плохой знак");
 217       c++;
 218       for (int i=0; i<12; i++)
 219         {
 220           while (*c == ' ')
 221             c++;
 222           if (*c >= '0' && *c <= '7')
 223             w = 8*w + *c++ - '0';
 224           else
 225             parse_error("Плохая цифва");
 226         }
 227       while (*c == ' ')
 228         c++;
 229       if (*c)
 230         parse_error("Номер слишком долгий");
 231       wr(addr++, w);
 232       addr &= 07777;
 233     }
 234 }
 235
 236 static word acc;
 237 static word r1, r2, current_ins;
 238 static int ip = 00050;                  // Standard program start location
 239 static int prev_ip;
 240
 241 static void stop(char *reason)
 242 {
 243   printf("Машина остановлена -- %s\n", reason);
 244   printf("СчАК:%04o См:%c%012llo Р1:%c%012llo Р2:%c%012llo\n", prev_ip, WF(acc), WF(r1), WF(r2));
 245   exit(0);
 246 }
 247
 248 static void over(void)
 249 {
 250   stop("Аварийный останов");
 251 }
 252
 253 static void notimp(void)
 254 {
 255   acc = current_ins;
 256   stop("Устройство разбитое");
 257 }
 258
 259 static void noins(void)
 260 {
 261   acc = current_ins;
 262   stop("Эту команду не знаю");
 263 }
 264
 265 static uint16_t linebuf[128];
 266
 267 static uint16_t russian_chars[64] = {
 268         '0',    '1',    '2',    '3',    '4',    '5',    '6',    '7',    // 0x
 269         '8',    '9',    '+',    '-',    '/',    ',',    '.',    ' ',    // 1x
 270         0x2169, '^',    '(',    ')',    0x00d7, '=',    ';',    '[',    // 2x
 271         ']',    '*',    '`',    '\'',   0x2260, '<',    '>',    ':',    // 3x
 272         0x410,  0x411,  0x412,  0x413,  0x414,  0x415,  0x416,  0x417,  // 4x
 273         0x418,  0x419,  0x41a,  0x41b,  0x41c,  0x41d,  0x41e,  0x41f,  // 5x
 274         0x420,  0x421,  0x422,  0x423,  0x424,  0x425,  0x426,  0x427,  // 6x
 275         0x428,  0x429,  0x42b,  0x42c,  0x42d,  0x42e,  0x42f,  0x2013  // 7x
 276 };
 277
 278 static uint16_t latin_chars[64] = {
 279         '0',    '1',    '2',    '3',    '4',    '5',    '6',    '7',    // 0x
 280         '8',    '9',    '+',    '-',    '/',    ',',    '.',    ' ',    // 1x
 281         0x2169, '^',    '(',    ')',    0x00d7, '=',    ';',    '[',    // 2x
 282         ']',    '*',    '`',    '\'',   0x2260, '<',    '>',    ':',    // 3x
 283         'A',    'B',    'W',    'G',    'D',    'E',    'V',    'Z',    // 4x
 284         'I',    'J',    'K',    'L',    'M',    'N',    'O',    'P',    // 5x
 285         'R',    'S',    'T',    'U',    'F',    'H',    'C',    ' ',    // 6x
 286         ' ',    ' ',    'Y',    'X',    ' ',    ' ',    'Q',    0x2013  // 7x
 287 };
 288
 289 static void print_line(int r)
 290 {
 291   /*
 292    *  Meaning of bits of r:
 293    *    0 = perform line feed
 294    *    1 = clear buffer
 295    *    2 = actually print
 296    */
 297   if (r & 4)
 298     {
 299       if (print_quota > 0 && !--print_quota)
 300         stop("Бумага дошла - нужно ехать в Сивирь про новую");
 301       for (int i=0; i<128; i++)
 302         {
 303           int ch = linebuf[i];
 304           if (!ch)
 305             ch = ' ';
 306           if (ch < 0x80)
 307             putchar(ch);
 308           else if (ch < 0x800)
 309             {
 310               putchar(0xc0 | (ch >> 6));
 311               putchar(0x80 | (ch & 0x3f));
 312             }
 313           else
 314             {
 315               putchar(0xe0 | (ch >> 12));
 316               putchar(0x80 | ((ch >> 6) & 0x3f));
 317               putchar(0x80 | (ch & 0x3f));
 318             }
 319         }
 320     }
 321   if (r & 2)
 322     memset(linebuf, 0, sizeof(linebuf));
 323   if (r & 1)
 324     putchar('\n');
 325   else if (r & 4)
 326     putchar('\r');
 327   fflush(stdout);
 328 }
 329
 330 static void print_ins(int x, int y)
 331 {
 332   word yy = rd(y);
 333   int pos = x & 0177;
 334   int r = (x >> 9) & 7;
 335
 336   if (x & 0400)
 337     {
 338       print_line(r);
 339       return;
 340     }
 341
 342   char *fmt;
 343   int bit = 37;
 344   int eat = 0;
 345   switch (r)
 346     {
 347     case 0:                             // Decimal float
 348       fmt = "+dddddddx+xbd";
 349       break;
 350     case 1:                             // Octal number
 351       fmt = "+oooooooooooo";
 352       break;
 353     case 2:                             // Decimal fixed
 354       fmt = "+ddddddddd";
 355       break;
 356     case 3:                             // Decimal unsigned
 357       fmt = "x ddddddddd";
 358       eat = 1;
 359       break;
 360     case 4:                             // One Russian symbol
 361       bit = 6;
 362       fmt = "r";
 363       break;
 364     case 5:                             // Russian text
 365       fmt = "xrrrrrr";
 366       break;
 367     case 6:                             // One Latin symbol
 368       bit = 6;
 369       fmt = "l";
 370       break;
 371     default:                            // Latin text
 372       fmt = "xllllll";
 373     }
 374
 375   while (*fmt)
 376     {
 377       int ch;
 378       switch (*fmt++)
 379         {
 380         case 'x':
 381           bit--;
 382           continue;
 383         case ' ':
 384           ch = ' ';
 385           break;
 386         case '+':
 387           bit--;
 388           ch = (yy & (1ULL << bit)) ? '-' : '+';
 389           break;
 390         case 'b':
 391           bit--;
 392           ch = '0' + ((yy >> bit) & 1);
 393           break;
 394         case 'o':
 395           bit -= 3;
 396           ch = '0' + ((yy >> bit) & 7);
 397           break;
 398         case 'd':
 399           bit -= 4;
 400           ch = '0' + ((yy >> bit) & 15);
 401           if (ch > '0' + 9)
 402             ch += 7;
 403           break;
 404         case 'r':
 405           bit -= 6;
 406           ch = russian_chars[(yy >> bit) & 077];
 407           break;
 408         case 'l':
 409           bit -= 6;
 410           ch = latin_chars[(yy >> bit) & 077];
 411           break;
 412         default:
 413           assert(0);
 414         }
 415
 416       if (eat && *fmt)
 417         {
 418           if (ch == '0' || ch == ' ')
 419             ch = ' ';
 420           else
 421             eat = 0;
 422         }
 423       linebuf[pos] = ch;
 424       pos = (pos+1) & 0177;
 425     }
 426   assert(!bit);
 427 }
 428
 429 static void run(void)
 430 {
 431   for (;;)
 432     {
 433       r2 = acc;
 434       prev_ip = ip;
 435       word w = mem[ip];
 436       current_ins = w;
 437
 438       int op = (w >> 30) & 0177;        // Operation code
 439       int ax = (w >> 28) & 3;           // Address extensions not supported
 440       int ix = (w >> 24) & 15;          // Indexing
 441       int x = (w >> 12) & 07777;        // Operands (original form)
 442       int y = w & 07777;
 443       int xi=x, yi=y;                   // (indexed form)
 444       if (trace)
 445         printf("@%04o  %c%02o %02o %04o %04o\n",
 446           ip,
 447           (w & SIGN_MASK) ? '-' : '+',
 448           (int)((w >> 30) & 077),
 449           (int)((w >> 24) & 077),
 450           x,
 451           y);
 452       if (ix)
 453         {
 454           if (op != 0120)
 455             {
 456               word i = rd(ix);
 457               xi = (xi + (int)((i >> 12) & 07777)) & 07777;
 458               yi = (yi + (int)(i & 07777)) & 07777;
 459               if (trace > 2)
 460                 printf("\tIndexing -> %04o %04o\n", xi, yi);
 461             }
 462         }
 463       ip = (ip+1) & 07777;
 464
 465       if (cpu_quota > 0 && !--cpu_quota)
 466         stop("Тайм-аут");
 467
 468       /* Arithmetic operations */
 469
 470       word a, b, c;
 471       long long aa, bb, cc;
 472       double ad, bd;
 473       int i;
 474
 475       auto void afetch(void);
 476       void afetch(void)
 477         {
 478           if (op & 2)
 479             a = r2;
 480           else
 481             a = rd(yi);
 482           b = r1 = rd(xi);
 483         }
 484
 485       auto void astore(word result);
 486       void astore(word result)
 487         {
 488           acc = result;
 489           if (op & 1)
 490             wr(yi, acc);
 491         }
 492
 493       auto void astore_int(long long x);
 494       void astore_int(long long x)
 495         {
 496           if (!int_in_range(x))
 497             over();
 498           astore(wfromll(x));
 499         }
 500
 501       auto void astore_frac(double f);
 502       void astore_frac(double f)
 503         {
 504           if (!frac_in_range(f))
 505             over();
 506           astore(wfromfrac(f));
 507         }
 508
 509       auto void astore_float(double f);
 510       void astore_float(double f)
 511         {
 512           if (!float_in_range(f))
 513             over();
 514           astore(wfromfloat(f, 0));
 515         }
 516
 517       if (ax)
 518         op = -1;
 519       switch (op)
 520         {
 521         case 000:               // NOP
 522           break;
 523         case 004 ... 007:       // XOR
 524           afetch();
 525           astore(a^b);
 526           break;
 527         case 010 ... 013:       // FIX addition
 528           afetch();
 529           astore_int(wtoll(a) + wtoll(b));
 530           break;
 531         case 014 ... 017:       // FP addition
 532           afetch();
 533           astore_float(wtofloat(a) + wtofloat(b));
 534           break;
 535         case 020 ... 023:       // FIX subtraction
 536           afetch();
 537           astore_int(wtoll(a) - wtoll(b));
 538           break;
 539         case 024 ... 027:       // FP subtraction
 540           afetch();
 541           astore_float(wtofloat(a) - wtofloat(b));
 542           break;
 543         case 030 ... 033:       // FIX multiplication
 544           afetch();
 545           astore_frac(wtofrac(a) * wtofrac(b));
 546           break;
 547         case 034 ... 037:       // FP multiplication
 548           afetch();
 549           astore_float(wtofloat(a) * wtofloat(b));
 550           break;
 551         case 040 ... 043:       // FIX division
 552           afetch();
 553           ad = wtofrac(a);
 554           bd = wtofrac(b);
 555           if (!wabs(b))
 556             over();
 557           astore_frac(ad / bd);
 558           break;
 559         case 044 ... 047:       // FP division
 560           afetch();
 561           ad = wtofloat(a);
 562           bd = wtofloat(b);
 563           if (!bd || wexp(b) < -63)
 564             over();
 565           astore_float(ad / bd);
 566           break;
 567         case 050 ... 053:       // FIX subtraction of abs values
 568           afetch();
 569           astore_int(wabs(a) - wabs(b));
 570           break;
 571         case 054 ... 057:       // FP subtraction of abs values
 572           afetch();
 573           astore_float(fabs(wtofloat(a)) - fabs(wtofloat(b)));
 574           break;
 575         case 060 ... 063:       // Shift logical
 576           afetch();
 577           i = wexp(b);
 578           if (i <= -37 || i >= 37)
 579             astore(0);
 580           else if (i >= 0)
 581             astore((a << i) & WORD_MASK);
 582           else
 583             astore(a >> (-i));
 584           break;
 585         case 064 ... 067:       // Shift arithmetical
 586           afetch();
 587           i = wexp(b);
 588           aa = wabs(a);
 589           if (i <= -36 || i >= 36)
 590             cc = 0;
 591           else if (i >= 0)
 592             cc = (aa << i) & VAL_MASK;
 593           else
 594             cc = aa >> (-i);
 595           astore((a & SIGN_MASK) | wfromll(cc));
 596           break;
 597         case 070 ... 073:       // And
 598           afetch();
 599           astore(a&b);
 600           break;
 601         case 074 ... 077:       // Or
 602           afetch();
 603           astore(a|b);
 604           break;
 605
 606         case 0100:              // Halt
 607           r1 = rd(x);
 608           acc = rd(y);
 609           stop("Останов машины");
 610         case 0103:              // I/O magtape
 611           notimp();
 612         case 0104:              // Disable rounding
 613           notimp();
 614         case 0105:              // Enable rounding
 615           notimp();
 616         case 0106:              // Interrupt control
 617           notimp();
 618         case 0107:              // Reverse tape
 619           notimp();
 620         case 0110:              // Move
 621           wr(yi, r1 = acc = rd(xi));
 622           break;
 623         case 0111:              // Move negative
 624           wr(yi, acc = (r1 = rd(xi)) ^ SIGN_MASK);
 625           break;
 626         case 0112:              // Move absolute value
 627           wr(yi, acc = (r1 = rd(xi)) & VAL_MASK);
 628           break;
 629         case 0113:              // Read from keyboard
 630           notimp();
 631         case 0114:              // Copy sign
 632           wr(yi, acc = rd(yi) ^ ((r1 = rd(xi)) & SIGN_MASK));
 633           break;
 634         case 0115:              // Read code from R1 (obscure)
 635           notimp();
 636         case 0116:              // Copy exponent
 637           wr(yi, acc = wputexp(rd(yi), wexp(r1 = rd(xi))));
 638           break;
 639         case 0117:              // I/O teletype
 640           notimp();
 641         case 0120:              // Loop
 642           if (!ix)
 643             noins();
 644           a = r1 = rd(ix);
 645           aa = (a >> 24) & 017777;
 646           if (!aa)
 647             break;
 648           b = rd(y);            // (a mountain range near Prague)
 649           acc = ((aa-1) << 24) |
 650                 (((((a >> 12) & 07777) + (b >> 12) & 07777) & 07777) << 12) |
 651                 (((a & 07777) + (b & 07777)) & 07777);
 652           wr(ix, acc);
 653           ip = x;
 654           break;
 655         case 0130:              // Jump
 656           wr(y, r2);
 657           ip = x;
 658           break;
 659         case 0131:              // Jump to subroutine
 660           wr(y, acc = ((030ULL << 30) | ((ip & 07777ULL) << 12)));
 661           ip = x;
 662           break;
 663         case 0132:              // Jump if positive
 664           if (wsign(r2) >= 0)
 665             ip = x;
 666           else
 667             ip = y;
 668           break;
 669         case 0133:              // Jump if overflow
 670           // Since we always trap on overflow, this instruction always jumps to the 1st address
 671           ip = x;
 672           break;
 673         case 0134:              // Jump if zero
 674           if (!wabs(r2))
 675             ip = y;
 676           else
 677             ip = x;
 678           break;
 679         case 0135:              // Jump if key pressed
 680           // No keys are ever pressed, so always jump to 2nd
 681           ip = y;
 682           break;
 683         case 0136:              // Interrupt masking
 684           notimp();
 685         case 0137:              // Used only when reading from tape
 686           notimp();
 687         case 0140 ... 0147:     // I/O
 688           notimp();
 689         case 0150 ... 0154:     // I/O
 690           notimp();
 691         case 0160 ... 0161:     // I/O
 692           notimp();
 693         case 0162:              // Printing
 694           print_ins(x, y);
 695           break;
 696         case 0163:              // I/O
 697           notimp();
 698         case 0170:              // FIX multiplication, bottom part
 699           afetch();
 700           if (wtofrac(a) * wtofrac(b) >= .1/(1ULL << 32))
 701             over();
 702           acc = wfromll(((unsigned long long)wabs(a) * (unsigned long long)wabs(b)) & VAL_MASK);
 703           // XXX: What should be the sign? The book does not define that.
 704           break;
 705         case 0171:              // Modulo
 706           afetch();
 707           aa = wabs(a);
 708           bb = wabs(b);
 709           if (!bb)
 710             over();
 711           cc = aa % bb;
 712           if (wsign(b) < 0)
 713             cc = -cc;
 714           acc = wfromll(cc);
 715           break;
 716         case 0172:              // Add exponents
 717           a = r1 = rd(xi);
 718           b = rd(yi);
 719           i = wexp(a) + wexp(b);
 720           if (i < -63 || i > 63)
 721             over();
 722           acc = wputexp(b, i);
 723           wr(yi, acc);
 724           break;
 725         case 0173:              // Sub exponents
 726           a = r1 = rd(xi);
 727           b = rd(yi);
 728           i = wexp(b) - wexp(a);
 729           if (i < -63 || i > 63)
 730             over();
 731           acc = wputexp(b, i);
 732           wr(yi, acc);
 733           break;
 734         case 0174:              // Addition in one's complement
 735           a = r1 = rd(xi);
 736           b = rd(yi);
 737           c = a + b;
 738           if (c > VAL_MASK)
 739             c = c - VAL_MASK;
 740           wr(yi, c);
 741           // XXX: The effect on the accumulator is undocumented, but likely to be as follows:
 742           acc = c;
 743           break;
 744         case 0175:              // Normalization
 745           a = r1 = rd(xi);
 746           if (!wabs(a))
 747             {
 748               wr(yi, 0);
 749               wr((yi+1) & 07777, 0);
 750               acc = 0;
 751             }
 752           else
 753             {
 754               i = 0;
 755               acc = a & SIGN_MASK;
 756               a &= VAL_MASK;
 757               while (!(a & (SIGN_MASK >> 1)))
 758                 {
 759                   a <<= 1;
 760                   i++;
 761                 }
 762               acc |= a;
 763               wr(yi, acc);
 764               wr((yi+1) & 07777, i);
 765             }
 766           break;
 767         case 0176:              // Population count
 768           a = r1 = rd(xi);
 769           cc = 0;
 770           for (int i=0; i<36; i++)
 771             if (a & (1ULL << i))
 772               cc++;
 773           // XXX: Guessing that acc gets a copy of the result
 774           acc = wfromll(cc);
 775           wr(yi, acc);
 776           break;
 777         default:
 778           noins();
 779         }
 780
 781       if (trace > 1)
 782         printf("\tACC:%c%012llo R1:%c%012llo R2:%c%012llo\n", WF(acc), WF(r1), WF(r2));
 783     }
 784 }
 785
 786 int main(void)
 787 {
 788   parse_in();
 789   run();
 790   return 0;
 791 }