minsk.c

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