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