minsk.c

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