interpreters/git/terp.c

   1 // $Id: terp.c,v 1.42 2004/12/22 14:33:40 iain Exp $
   2 // Interpreter engine.
   3
   4 #include "git.h"
   5 #include <assert.h>
   6 #include <stdlib.h>
   7 #include <stdio.h>
   8 #include <string.h>
   9 #include <time.h>
  10
  11 // -------------------------------------------------------------
  12 // Global variables
  13
  14 git_sint32* gStackPointer;
  15
  16 #ifdef USE_DIRECT_THREADING
  17 Opcode* gOpcodeTable;
  18 #endif
  19
  20 // -------------------------------------------------------------
  21 // Useful macros for manipulating the stack
  22
  23 #define LOCAL(n)   (locals[(n)])
  24
  25 #define PUSH(n)    *sp++ = (n)
  26 #define POP        (*--sp)
  27 #define READ_PC    ((git_uint32)(*pc++))
  28
  29 #define CHECK_FREE(n) if ((top - sp) < (n)) goto stack_overflow
  30 #define CHECK_USED(n) if ((sp - values) < (n)) goto stack_underflow
  31
  32 // -------------------------------------------------------------
  33 // Functions
  34
  35 void startProgram (size_t cacheSize, enum IOMode ioMode)
  36 {
  37     Block pc; // Program counter (pointer into dynamically generated code)
  38
  39     git_sint32 L1=0, L2=0, L3=0, L4=0, L5=0, L6=0, L7=0;
  40 #define S1 L1
  41 #define S2 L2
  42
  43     git_sint32* base;   // Bottom of the stack.
  44     git_sint32* frame;  // Bottom of the current stack frame.
  45     git_sint32* locals; // Start of the locals section of the current frame.
  46     git_sint32* values; // Start of the values section of the current frame.
  47     git_sint32* sp;     // Next free stack slot.
  48     git_sint32* top;    // The top of the stack -- that is, the first unusable slot.
  49
  50     git_sint32 args [64]; // Array of arguments. Count is stored in L2.
  51     git_uint32 runCounter = 0;
  52
  53     git_uint32 ioRock = 0;
  54
  55     git_uint32 stringTable = memRead32(28);
  56     git_uint32 startPos    = memRead32(24);
  57     git_uint32 stackSize   = memRead32(20);
  58
  59     git_uint32 protectPos = 0;
  60     git_uint32 protectSize = 0;
  61
  62     git_uint32 glulxPC = 0;
  63     git_uint32 glulxOpcode = 0;
  64
  65     acceleration_func accelfunc;
  66
  67     // Initialise the code cache.
  68
  69 #ifdef USE_DIRECT_THREADING
  70     static Opcode opcodeTable [] = {
  71 #define LABEL(label) &&do_ ## label,
  72 #include "labels.inc"
  73     NULL};
  74     gOpcodeTable = opcodeTable;
  75 #endif
  76
  77     initCompiler (cacheSize);
  78
  79     // Initialise the random number generator.
  80     srand (time(NULL));
  81
  82     // Set up the stack.
  83
  84     base = malloc (stackSize);
  85     if (base == NULL)
  86         fatalError ("Couldn't allocate stack");
  87
  88     top = base + (stackSize / 4);
  89     frame = locals = values = sp = base;
  90
  91     // Call the first function.
  92
  93     L1 = startPos; // Initial PC.
  94     L2 = 0; // No arguments.
  95     goto do_enter_function_L1;
  96
  97 #ifdef USE_DIRECT_THREADING
  98 #define NEXT do { ++runCounter; goto **(pc++); } while(0)
  99 #else
 100 #define NEXT goto next
 101 //#define NEXT do { CHECK_USED(0); CHECK_FREE(0); goto next; } while (0)
 102 next:
 103     ++runCounter;
 104     switch (*pc++)
 105     {
 106 #define LABEL(foo) case label_ ## foo: goto do_ ## foo;
 107 #include "labels.inc"
 108     default: fatalError("exec: bad opcode");
 109     }
 110 #endif
 111
 112 do_debug_step:
 113     // This opcode lets us keep track of how the compiled
 114     // code relates to the original glulx code.
 115     glulxPC = READ_PC;     // Glulx program counter.
 116     glulxOpcode = READ_PC; // Glulx opcode number.
 117 //    fprintf (stdout, "\nPC: 0x%08x\nOpcode: 0x%04x\n", glulxPC, glulxOpcode);
 118 //    fprintf (stdout, "Stack:");
 119 //    for (L7 = 0 ; L7 < (sp - base) ; ++L7)
 120 //        fprintf (stdout," 0x%x", base[L7]);
 121 //    fprintf (stdout, "\n");
 122     NEXT;
 123
 124 #define LOAD_INSTRUCTIONS(reg)                                  \
 125     do_ ## reg ## _const:   reg = READ_PC; NEXT;                \
 126     do_ ## reg ## _stack:   CHECK_USED(1); reg = POP; NEXT;     \
 127     do_ ## reg ## _addr:    reg = memRead32 (READ_PC); NEXT;    \
 128     do_ ## reg ## _local:   reg = LOCAL (READ_PC); NEXT
 129
 130     LOAD_INSTRUCTIONS(L1);
 131     LOAD_INSTRUCTIONS(L2);
 132     LOAD_INSTRUCTIONS(L3);
 133     LOAD_INSTRUCTIONS(L4);
 134     LOAD_INSTRUCTIONS(L5);
 135     LOAD_INSTRUCTIONS(L6);
 136     LOAD_INSTRUCTIONS(L7);
 137
 138 #define STORE_INSTRUCTIONS(reg)                                 \
 139     do_ ## reg ## _stack:   CHECK_FREE(1); PUSH(reg); NEXT;     \
 140     do_ ## reg ## _addr:    memWrite32 (READ_PC, reg); NEXT;    \
 141     do_ ## reg ## _local:   LOCAL (READ_PC) = reg; NEXT
 142
 143     STORE_INSTRUCTIONS(S1);
 144     STORE_INSTRUCTIONS(S2);
 145
 146 #define DOUBLE_LOAD(mode2) \
 147     do_L1_const_L2_ ## mode2: L1 = READ_PC;             goto do_L2_ ## mode2; \
 148     do_L1_stack_L2_ ## mode2: CHECK_USED(1); L1 = POP;  goto do_L2_ ## mode2; \
 149     do_L1_local_L2_ ## mode2: L1 = LOCAL (READ_PC);     goto do_L2_ ## mode2; \
 150     do_L1_addr_L2_ ## mode2:  L1 = memRead32 (READ_PC); goto do_L2_ ## mode2
 151
 152     DOUBLE_LOAD(const);
 153     DOUBLE_LOAD(stack);
 154     DOUBLE_LOAD(local);
 155     DOUBLE_LOAD(addr);
 156
 157 #undef LOAD_INSTRUCTIONS
 158 #undef STORE_INSTRUCTIONS
 159 #undef DOUBLE_LOAD
 160
 161 do_L1_addr16: L1 = memRead16 (READ_PC); NEXT;
 162 do_L1_addr8:  L1 = memRead8 (READ_PC); NEXT;
 163 do_S1_addr16: memWrite16 (READ_PC, S1); NEXT;
 164 do_S1_addr8:  memWrite8 (READ_PC, S1); NEXT;
 165
 166 #define UL7 ((git_uint32)L7)
 167
 168 do_recompile:
 169     gBlockHeader->runCounter = runCounter;
 170     pc = compile (READ_PC);
 171     runCounter = 0;
 172         NEXT;
 173
 174 do_jump_abs_L7:
 175     gBlockHeader->runCounter = runCounter;
 176     pc = getCode (UL7);
 177     runCounter = gBlockHeader->runCounter;
 178     NEXT;
 179
 180 do_enter_function_L1: // Arg count is in L2.
 181
 182     // Check for an accelerated function
 183     accelfunc = accel_get_func(L1);
 184     if (accelfunc) {
 185         S1 = accelfunc(L2, (glui32 *) args);
 186         goto do_pop_call_stub;
 187     }
 188
 189     frame = sp;
 190     // Read the function type.
 191     L7 = memRead8(L1++);
 192     // Parse the local variables descriptor.
 193     L6 = L5 = L4 = 0;
 194     do
 195     {
 196         L6 = memRead8(L1++); // LocalType
 197         L5 = memRead8(L1++); // LocalCount
 198         if (L6 != 4 && L6 != 0) // We only support 4-byte locals.
 199             fatalError("Local variable wasn't 4 bytes wide");
 200         L4 += L5; // Cumulative local count.
 201     }
 202     while (L5 != 0);
 203
 204     // Write out the stack frame.
 205     // Recall that the number of locals is stored in L4.
 206
 207     CHECK_FREE(3 + L4);
 208
 209     PUSH (L4*4 + 12); // FrameLen
 210     PUSH (12);        // LocalsPos
 211     if (L4 == 0)
 212         L6 = 0;
 213     else
 214         L6 = (4 << 24) | (L4 << 16);
 215     PUSH (L6);         // format of locals
 216
 217     // This is where the local variables start, so:
 218     locals = sp;
 219
 220     // Read the arguments, based on the function type.
 221     switch (L7)
 222     {
 223         case 0xC0: // arguments should be placed on the stack.
 224             // argc is in L2; we'll randomly use L5 as scratch.
 225             CHECK_FREE(L5 + 1);
 226             // Initialise the local variables.
 227             for ( ; L4 > 0 ; --L4)
 228                 PUSH (0);
 229             // This is where the temporary values start, so:
 230             values = sp;
 231             // Push the args onto the stack.
 232             for (L5 = 0 ; L5 < L2 ; ++L5)
 233                 PUSH (args [L5]);
 234             // Push the arg count.
 235             PUSH (L2);
 236             break;
 237
 238         case 0xC1: // arguments should be written into locals.
 239             // argc is in L2, num locals is in L4.
 240             // Stuff as many locals as possible with arguments.
 241             for (L5 = 1 ; L5 <= L2 && L4 > 0 ; ++L5, --L4)
 242                 PUSH (args [L2 - L5]);
 243             // Initialise any remaining locals.
 244             for ( ; L4 > 0 ; --L4)
 245                 PUSH (0);
 246             // This is where the temporary values start, so:
 247             values = sp;
 248             break;
 249
 250         default:
 251             // This isn't a function!
 252             fatalError("Not a function");
 253             break;
 254     }
 255
 256     // Start executing the function.
 257     L7 = L1;
 258     goto do_jump_abs_L7;
 259
 260     do_nop:     NEXT;
 261
 262 #define PEEPHOLE_STORE(tag, code)                     \
 263     do_ ## tag ## _discard:  code; NEXT;              \
 264     do_ ## tag ## _S1_stack: code; goto do_S1_stack;  \
 265     do_ ## tag ## _S1_local: code; goto do_S1_local;  \
 266     do_ ## tag ## _S1_addr:  code; goto do_S1_addr
 267
 268     PEEPHOLE_STORE(add,     S1 = L1 + L2);
 269     PEEPHOLE_STORE(sub,     S1 = L1 - L2);
 270     PEEPHOLE_STORE(mul,     S1 = L1 * L2);
 271     PEEPHOLE_STORE(div,     if (L2 == 0) fatalError ("Divide by zero"); S1 = L1 / L2);
 272     PEEPHOLE_STORE(mod,     if (L2 == 0) fatalError ("Divide by zero"); S1 = L1 % L2);
 273
 274     PEEPHOLE_STORE(neg,     S1 = -L1);
 275     PEEPHOLE_STORE(bitnot,  S1 = ~L1);
 276
 277     PEEPHOLE_STORE(bitand,  S1 = L1 & L2);
 278     PEEPHOLE_STORE(bitor,   S1 = L1 | L2);
 279     PEEPHOLE_STORE(bitxor,  S1 = L1 ^ L2);
 280
 281     PEEPHOLE_STORE(shiftl,  if (L2 > 31) S1 = 0; else S1 = L1 << ((git_uint32) L2));
 282     PEEPHOLE_STORE(sshiftr, if (L2 > 31) L2 = 31; S1 = ((git_sint32) L1) >> ((git_uint32) L2));
 283     PEEPHOLE_STORE(ushiftr, if (L2 > 31) S1 = 0; else S1 = ((git_uint32) L1) >> ((git_uint32) L2));
 284
 285     PEEPHOLE_STORE(aload,   S1 = memRead32 (L1 + (L2<<2)));
 286     PEEPHOLE_STORE(aloads,  S1 = memRead16 (L1 + (L2<<1)));
 287     PEEPHOLE_STORE(aloadb,  S1 = memRead8  (L1 + L2));
 288     PEEPHOLE_STORE(aloadbit,S1 = (memRead8 (L1 + (L2>>3)) >> (L2 & 7)) & 1);
 289
 290     PEEPHOLE_STORE(copys,   S1 = L1 & 0xFFFF);
 291     PEEPHOLE_STORE(copyb,   S1 = L1 & 0x00FF);
 292     PEEPHOLE_STORE(sexs,    S1 = (git_sint32)((signed short)(L1 & 0xFFFF)));
 293     PEEPHOLE_STORE(sexb,    S1 = (git_sint32)((signed char)(L1 & 0x00FF)));
 294
 295 #define PEEPHOLE_LOAD(tag,reg) \
 296     do_ ## tag ## _ ## reg ## _const: reg = READ_PC; goto do_ ## tag; \
 297     do_ ## tag ## _ ## reg ## _stack: CHECK_USED(1); reg = POP; goto do_ ## tag; \
 298     do_ ## tag ## _ ## reg ## _local: reg = LOCAL(READ_PC); goto do_ ## tag; \
 299     do_ ## tag ## _ ## reg ## _addr:  reg = memRead32(READ_PC); goto do_ ## tag
 300
 301     PEEPHOLE_LOAD (return, L1);
 302     PEEPHOLE_LOAD (astore, L3);
 303     PEEPHOLE_LOAD (astores, L3);
 304     PEEPHOLE_LOAD (astoreb, L3);
 305     PEEPHOLE_LOAD (astorebit, L3);
 306
 307 #undef PEEPHOLE_STORE
 308
 309     do_astore:    memWrite32 (L1 + (L2<<2), L3); NEXT;
 310     do_astores:   memWrite16 (L1 + (L2<<1), L3); NEXT;
 311     do_astoreb:   memWrite8  (L1 + L2, L3); NEXT;
 312     do_astorebit:
 313         L4 = memRead8(L1 + (L2>>3));
 314         if (L3 == 0)
 315             L4 &= ~(1 << (L2 & 7));
 316         else
 317             L4 |= (1 << (L2 & 7));
 318         memWrite8(L1 + (L2>>3), L4);
 319         NEXT;
 320
 321 #define DO_JUMP(tag, reg, cond) \
 322     do_ ## tag ## _var:     L7 = READ_PC; if (cond) goto do_goto_ ## reg ## _from_L7; NEXT; \
 323     do_ ## tag ## _const:   L7 = READ_PC; if (cond) goto do_jump_abs_L7; NEXT;              \
 324     do_ ## tag ## _by:      L7 = READ_PC; if (cond) pc += L7; NEXT;                         \
 325     do_ ## tag ## _return0: if (cond) { L1 = 0; goto do_return; } NEXT;                     \
 326     do_ ## tag ## _return1: if (cond) { L1 = 1; goto do_return; } NEXT
 327
 328     DO_JUMP(jump, L1, 1 == 1);
 329     DO_JUMP(jz,   L2, L1 == 0);
 330     DO_JUMP(jnz,  L2, L1 != 0);
 331     DO_JUMP(jeq,  L3, L1 == L2);
 332     DO_JUMP(jne,  L3, L1 != L2);
 333     DO_JUMP(jlt,  L3, L1 < L2);
 334     DO_JUMP(jge,  L3, L1 >= L2);
 335     DO_JUMP(jgt,  L3, L1 > L2);
 336     DO_JUMP(jle,  L3, L1 <= L2);
 337     DO_JUMP(jltu, L3, ((git_uint32)L1 < (git_uint32)L2));
 338     DO_JUMP(jgeu, L3, ((git_uint32)L1 >= (git_uint32)L2));
 339     DO_JUMP(jgtu, L3, ((git_uint32)L1 > (git_uint32)L2));
 340     DO_JUMP(jleu, L3, ((git_uint32)L1 <= (git_uint32)L2));
 341
 342 #undef DO_JUMP
 343
 344     do_jumpabs: L7 = L1; goto do_jump_abs_L7; NEXT;
 345
 346     do_goto_L3_from_L7: L1 = L3; goto do_goto_L1_from_L7;
 347     do_goto_L2_from_L7: L1 = L2; goto do_goto_L1_from_L7;
 348     do_goto_L1_from_L7:
 349         if (L1 == 0 || L1 == 1) goto do_return;
 350         L7 = L7 + L1 - 2; goto do_jump_abs_L7;
 351
 352     do_args_stack:
 353         // The first argument is topmost in the stack; the count is in L2.
 354         CHECK_USED(L2);
 355         // We want to store the arguments in 'args' in the same order.
 356         for (L3 = L2 - 1 ; L3 >= 0 ; --L3)
 357             args [L3] = POP;
 358         NEXT;
 359
 360     // Specialised versions of above:
 361     do_args_stack_call_stub_discard:
 362         CHECK_USED(L2);
 363         for (L3 = L2 - 1 ; L3 >= 0 ; --L3)
 364             args [L3] = POP;
 365         goto do_call_stub_discard;
 366
 367     do_args_stack_call_stub_addr:
 368         CHECK_USED(L2);
 369         for (L3 = L2 - 1 ; L3 >= 0 ; --L3)
 370             args [L3] = POP;
 371         goto do_call_stub_addr;
 372
 373     do_args_stack_call_stub_local:
 374         CHECK_USED(L2);
 375         for (L3 = L2 - 1 ; L3 >= 0 ; --L3)
 376             args [L3] = POP;
 377         goto do_call_stub_local;
 378
 379     do_args_stack_call_stub_stack:
 380         CHECK_USED(L2);
 381         for (L3 = L2 - 1 ; L3 >= 0 ; --L3)
 382             args [L3] = POP;
 383         goto do_call_stub_stack;
 384
 385     do_args_3:
 386         args [0] = L4;
 387         args [1] = L3;
 388         args [2] = L2;
 389         L2 = 3;
 390         NEXT;
 391
 392     do_args_2:
 393         args [0] = L3;
 394         args [1] = L2;
 395         L2 = 2;
 396         NEXT;
 397
 398     do_args_1:
 399         args [0] = L2;
 400         L2 = 1;
 401         NEXT;
 402
 403     do_args_0:
 404         L2 = 0;
 405         NEXT;
 406
 407     do_undo_stub_discard:
 408         CHECK_FREE(4);
 409         PUSH (0); // DestType
 410         PUSH (0); // DestAddr
 411         goto finish_undo_stub;
 412
 413     do_undo_stub_addr:
 414         CHECK_FREE(4);
 415         PUSH (1);       // DestType
 416         PUSH (READ_PC); // DestAddr
 417         goto finish_undo_stub;
 418
 419     do_undo_stub_local:
 420         CHECK_FREE(4);
 421         PUSH (2);       // DestType
 422         PUSH (READ_PC); // DestAddr
 423         goto finish_undo_stub;
 424
 425     do_undo_stub_stack:
 426         CHECK_FREE(4);
 427         PUSH (3); // DestType
 428         PUSH (0); // DestAddr
 429         goto finish_undo_stub;
 430
 431 finish_undo_stub:
 432         PUSH (READ_PC);             // PC
 433         PUSH ((frame - base) * 4);  // FramePtr
 434         saveUndo (base, sp);
 435         S1 = 0;
 436         goto do_pop_call_stub;
 437
 438     do_restoreundo:
 439         if (restoreUndo (base, protectPos, protectSize) == 0)
 440         {
 441             sp = gStackPointer;
 442             S1 = -1;
 443             goto do_pop_call_stub;
 444         }
 445         S1 = 1;
 446         NEXT;
 447
 448     do_save_stub_discard:
 449         CHECK_FREE(4);
 450         PUSH (0); // DestType
 451         PUSH (0); // DestAddr
 452         goto finish_save_stub;
 453
 454     do_save_stub_addr:
 455         CHECK_FREE(4);
 456         PUSH (1);       // DestType
 457         PUSH (READ_PC); // DestAddr
 458         goto finish_save_stub;
 459
 460     do_save_stub_local:
 461         CHECK_FREE(4);
 462         PUSH (2);       // DestType
 463         PUSH (READ_PC); // DestAddr
 464         goto finish_save_stub;
 465
 466     do_save_stub_stack:
 467         CHECK_FREE(4);
 468         PUSH (3); // DestType
 469         PUSH (0); // DestAddr
 470         goto finish_save_stub;
 471
 472 finish_save_stub:
 473         PUSH (READ_PC);                        // PC
 474         PUSH ((frame - base) * 4);  // FramePtr
 475         if (ioMode == IO_GLK)
 476             S1 = saveToFile (base, sp, L1);
 477         else
 478             S1 = 1;
 479         goto do_pop_call_stub;
 480
 481     do_restore:
 482         if (ioMode == IO_GLK
 483          && restoreFromFile (base, L1, protectPos, protectSize) == 0)
 484         {
 485             sp = gStackPointer;
 486             S1 = -1;
 487             goto do_pop_call_stub;
 488         }
 489         S1 = 1;
 490         NEXT;
 491
 492     do_catch_stub_discard:
 493         CHECK_FREE(4);
 494         L7 = 0;
 495         PUSH (0); // DestType
 496         goto finish_catch_stub_addr_L7;
 497
 498     do_catch_stub_addr:
 499         CHECK_FREE(4);
 500         L7 = READ_PC;
 501         memWrite32(L7, (sp-base+4)*4);
 502         PUSH (1);       // DestType
 503         goto finish_catch_stub_addr_L7;
 504
 505     do_catch_stub_local:
 506         CHECK_FREE(4);
 507         L7 = READ_PC;
 508         memWrite32(L7, (sp-base+4)*4);
 509         PUSH (2);       // DestType
 510         goto finish_catch_stub_addr_L7;
 511
 512     do_catch_stub_stack:
 513         CHECK_FREE(5);
 514         PUSH (3);                  // DestType
 515         PUSH (0);                  // DestAddr
 516         PUSH (READ_PC);            // PC
 517         PUSH ((frame - base) * 4); // FramePtr
 518         L7 = (sp - base)*4;        // Catch token.
 519             PUSH (L7);
 520         NEXT;
 521
 522 finish_catch_stub_addr_L7:
 523         PUSH (L7);                 // DestAddr
 524         PUSH (READ_PC);            // PC
 525         PUSH ((frame - base) * 4); // FramePtr
 526         NEXT;
 527
 528     do_throw:
 529         if (L2 < 16 || L2 > ((sp-base)*4))
 530             fatalError ("Invalid catch token in throw");
 531         sp = base + L2 / 4;
 532         goto do_pop_call_stub;
 533
 534 do_call_stub_discard:
 535         CHECK_FREE(4);
 536         PUSH (0); // DestType
 537         PUSH (0); // DestAddr
 538         goto finish_call_stub;
 539
 540     do_call_stub_addr:
 541         CHECK_FREE(4);
 542         PUSH (1);       // DestType
 543         PUSH (READ_PC); // DestAddr
 544         goto finish_call_stub;
 545
 546     do_call_stub_local:
 547         CHECK_FREE(4);
 548         PUSH (2);       // DestType
 549         PUSH (READ_PC); // DestAddr
 550         goto finish_call_stub;
 551
 552     do_call_stub_stack:
 553         CHECK_FREE(4);
 554         PUSH (3); // DestType
 555         PUSH (0); // DestAddr
 556         goto finish_call_stub;
 557
 558 finish_call_stub:
 559         PUSH (READ_PC);             // PC
 560         PUSH ((frame - base) * 4);  // FramePtr
 561         goto do_enter_function_L1;
 562
 563 do_tailcall:
 564         // Zap the current stack frame, down to its call stub.
 565         sp = frame;
 566         // Call the function!
 567         goto do_enter_function_L1;
 568
 569     do_return:
 570         sp = frame;
 571         // ...
 572         // fall through
 573         // ...
 574     do_pop_call_stub:// L1 holds the return value.
 575         if (sp - base < 4)
 576         {
 577             if (sp == base)
 578                 // We just exited the top-level function.
 579                 goto finished;
 580             else
 581                 // Something nasty happened.
 582                 goto stack_underflow;
 583         }
 584         L2 = POP;    // FramePtr
 585         L7 = POP;    // PC
 586         L6 = POP;    // DestAddr
 587         switch (POP) // DestType
 588         {
 589             case 0: // Do not store.
 590                 frame = base + L2 / 4;
 591                 locals = frame + frame[1]/4;
 592                 values = frame + frame[0]/4;
 593                 break;
 594
 595             case 1: // Store in main memory.
 596                 frame = base + L2 / 4;
 597                 locals = frame + frame[1]/4;
 598                 values = frame + frame[0]/4;
 599                 memWrite32 (L6, L1);
 600                 break;
 601
 602             case 2: // Store in local variable.
 603                 frame = base + L2 / 4;
 604                 locals = frame + frame[1]/4;
 605                 values = frame + frame[0]/4;
 606                 LOCAL(L6/4) = L1;
 607                 break;
 608
 609             case 3: // Push on stack.
 610                 frame = base + L2 / 4;
 611                 locals = frame + frame[1]/4;
 612                 values = frame + frame[0]/4;
 613                 PUSH (L1);
 614                 break;
 615
 616             case 10: // Resume printing a compressed (E1) string.
 617                 frame = base + L2 / 4;
 618                 locals = frame + frame[1]/4;
 619                 values = frame + frame[0]/4;
 620                 goto resume_compressed_string_L7_bit_L6;
 621
 622             case 11: // Resume executing function code after a string completes.
 623                 // Don't restore the frame pointer.
 624                 break;
 625
 626             case 12: // Resume printing a signed decimal integer.
 627                 frame = base + L2 / 4;
 628                 locals = frame + frame[1]/4;
 629                 values = frame + frame[0]/4;
 630                 goto resume_number_L7_digit_L6;
 631
 632             case 13: // Resume printing a C-style (E0) string.
 633                 frame = base + L2 / 4;
 634                 locals = frame + frame[1]/4;
 635                 values = frame + frame[0]/4;
 636                 goto resume_c_string_L7;
 637
 638             case 14: // Resume printing a Unicode (E2) string.
 639                 frame = base + L2 / 4;
 640                 locals = frame + frame[1]/4;
 641                 values = frame + frame[0]/4;
 642                 goto resume_uni_string_L7;
 643
 644             default:
 645                 fatalError("Bad call stub");
 646         }
 647         // Restore the PC.
 648         goto do_jump_abs_L7;
 649
 650     do_stkcount:
 651         S1 = sp - values; NEXT;
 652
 653     do_stkpeek:
 654         if (L1 < 0 || L1 > (sp - values))
 655             fatalError("Out of bounds in stkpeek");
 656         S1 = sp[-1 - L1]; NEXT;
 657
 658     do_stkswap:
 659         CHECK_USED(2);
 660         L1 = POP; L2 = POP; PUSH(L1); PUSH(L2); NEXT;
 661
 662     do_stkcopy:
 663         CHECK_USED(L1);
 664         for (L2 = L1 ; L2 > 0 ; --L2)
 665         {
 666             L3 = sp[-L1];
 667             PUSH (L3);
 668         }
 669         NEXT;
 670
 671     resume_number_L7_digit_L6:
 672     {
 673         char buffer [16];
 674
 675         // If the IO mode is 'null', do nothing.
 676         if (ioMode == IO_NULL)
 677             goto do_pop_call_stub;
 678
 679         // Write the number into the buffer.
 680         L1 = (L7 < 0) ? -L7 : L7; // Absolute value of number.
 681         L2 = 0;                   // Current buffer position.
 682         do
 683         {
 684             buffer [L2++] = '0' + (L1 % 10);
 685             L1 /= 10;
 686         }
 687         while (L1 > 0);
 688
 689         if (L7 < 0)
 690             buffer [L2++] = '-';
 691
 692         if (L6 >= L2)
 693             goto do_pop_call_stub; // We printed the whole number already.
 694
 695         // If we're in filter mode, push a call stub
 696         // and filter the next character.
 697         if (ioMode == IO_FILTER)
 698         {
 699             // Store the next character in the args array.
 700             args[0] = buffer [L2 - L6 - 1];
 701             ++L6;
 702
 703             // Push a call stub to print the next character.
 704             CHECK_FREE(4);
 705             PUSH(12); // DestType
 706             PUSH(L6); // DestAddr (next digit)
 707             PUSH(L7); // PC       (number to print)
 708             PUSH ((frame - base) * 4); // FramePtr
 709
 710             // Call the filter function.
 711             L1 = ioRock;
 712             L2 = 1;
 713             goto do_enter_function_L1;
 714         }
 715         else
 716         {
 717             // We're in Glk mode. Just print all the characters.
 718             for ( ; L6 < L2 ; ++L6)
 719                 glk_put_char (buffer [L2 - L6 - 1]);
 720         }
 721     }
 722         goto do_pop_call_stub;
 723
 724     resume_c_string_L7:
 725         // If the IO mode is 'null', or if we've reached the
 726         // end of the string, do nothing.
 727         L2 = memRead8(L7++);
 728         if (L2 == 0 || ioMode == IO_NULL)
 729             goto do_pop_call_stub;
 730         // Otherwise we're going to have to print something,
 731         // If the IO mode is 'filter', filter the next char.
 732         if (ioMode == IO_FILTER)
 733         {
 734             // Store this character in the args array.
 735             args [0] = L2;
 736             // Push a call stub.
 737             CHECK_FREE(4);
 738             PUSH(13); // DestType (resume C string)
 739             PUSH(L6); // DestAddr (ignored)
 740             PUSH(L7); // PC       (next char to print)
 741             PUSH ((frame - base) * 4); // FramePtr
 742             // Call the filter function.
 743             L1 = ioRock;
 744             L2 = 1;
 745             goto do_enter_function_L1;
 746         }
 747         // We're in Glk mode. Just print all the characters.
 748         while (L2 != 0)
 749         {
 750             glk_put_char ((unsigned char) L2);
 751             L2 = memRead8(L7++);
 752         }
 753         goto do_pop_call_stub;
 754
 755     resume_uni_string_L7:
 756         // If the IO mode is 'null', or if we've reached the
 757         // end of the string, do nothing.
 758         L2 = memRead32(L7);
 759         L7 += 4;
 760         if (L2 == 0 || ioMode == IO_NULL)
 761             goto do_pop_call_stub;
 762         // Otherwise we're going to have to print something,
 763         // If the IO mode is 'filter', filter the next char.
 764         if (ioMode == IO_FILTER)
 765         {
 766             // Store this character in the args array.
 767             args [0] = L2;
 768             // Push a call stub.
 769             CHECK_FREE(4);
 770             PUSH(14); // DestType (resume Unicode string)
 771             PUSH(L6); // DestAddr (ignored)
 772             PUSH(L7); // PC       (next char to print)
 773             PUSH ((frame - base) * 4); // FramePtr
 774             // Call the filter function.
 775             L1 = ioRock;
 776             L2 = 1;
 777             goto do_enter_function_L1;
 778         }
 779         // We're in Glk mode. Just print all the characters.
 780         while (L2 != 0)
 781         {
 782 #ifdef GLK_MODULE_UNICODE
 783             glk_put_char_uni ((glui32) L2);
 784 #else
 785             unsigned char c = (L2 > 0 && L2 < 256) ? L2 : '?';
 786             glk_put_char (c);
 787 #endif // GLK_MODULE_UNICODE
 788             L2 = memRead32(L7);
 789             L7 += 4;
 790         }
 791         goto do_pop_call_stub;
 792
 793     resume_compressed_string_L7_bit_L6:
 794         // Load the first string table node into L1.
 795         // Its address is stored at stringTable + 8.
 796         L1 = memRead32 (stringTable + 8);
 797         // Load the node's type byte.
 798         L2 = memRead8 (L1++);
 799         // Is the root node a branch?
 800         if (L2 == 0)
 801         {
 802             // We'll keep a reservoir of input bits in L5.
 803             L5 = memRead8(L7);
 804             // Keep following branch nodes until we hit a leaf node.
 805             while (L2 == 0)
 806             {
 807                 // Read the next bit.
 808                 L4 = (L5 >> L6) & 1;
 809                 // If we're finished reading this byte,
 810                 // move on to the next one.
 811                 if (++L6 > 7)
 812                 {
 813                     L6 -= 8;
 814                     L5 = memRead8(++L7);
 815                 }
 816                 // Follow the branch.
 817                 L1 = memRead32(L1 + 4 * L4);
 818                 L2 = memRead8 (L1++);
 819             }
 820         }
 821         else if (L2 == 2 || L2 == 3)
 822         {
 823             // The root node prints a single character or a string.
 824             // This will produce infinite output in the Null or Glk
 825             // I/O modes, so we'll catch that here.
 826
 827             if (ioMode != IO_FILTER)
 828                 fatalError ("String table prints infinite strings!");
 829
 830             // In Filter mode, the output will be sent to the current
 831             // filter function, which can change the string table
 832             // before returning, so we'll continue and see what happens.
 833         }
 834         // We're at a leaf node.
 835         switch (L2)
 836         {
 837             case 1: // Terminator.
 838                 goto do_pop_call_stub;
 839
 840             case 2: // Single char.
 841                 if (ioMode == IO_NULL)
 842                     { /* Do nothing */ }
 843                 else if (ioMode == IO_GLK)
 844                     glk_put_char ((unsigned char) memRead8(L1));
 845                 else
 846                 {
 847                     // Store this character in the args array.
 848                     args [0] = memRead8(L1);
 849                     // Push a call stub.
 850                     CHECK_FREE(4);
 851                     PUSH(10); // DestType
 852                     PUSH(L6); // DestAddr (bit number in string)
 853                     PUSH(L7); // PC       (byte address in string)
 854                     PUSH ((frame - base) * 4); // FramePtr
 855                     // Call the filter function.
 856                     L1 = ioRock;
 857                     L2 = 1;
 858                     goto do_enter_function_L1;
 859                 }
 860                 break;
 861
 862             case 3: // C string.
 863                 // Push a 'resume compressed string' call stub.
 864                 CHECK_FREE(4);
 865                 PUSH (10); // DestType
 866                 PUSH (L6); // DestAddr (bit number in string)
 867                 PUSH (L7); // PC       (byte address in string)
 868                 PUSH ((frame - base) * 4); // FramePtr
 869                 // Print the C string.
 870                 L7 = L1;
 871                 goto resume_c_string_L7;
 872
 873             case 4: // Unicode char
 874                 if (ioMode == IO_NULL)
 875                     { /* Do nothing */ }
 876                 else if (ioMode == IO_GLK)
 877                 {
 878 #ifdef GLK_MODULE_UNICODE
 879                     glk_put_char_uni (memRead32(L1));
 880 #else
 881                     git_uint32 c = memRead32(L1);
 882                     if (c > 255) c = '?';
 883                     glk_put_char ((unsigned char) c);
 884 #endif // GLK_MODULE_UNICODE
 885                 }
 886                 else
 887                 {
 888                     // Store this character in the args array.
 889                     args [0] = memRead32(L1);
 890                     // Push a call stub.
 891                     CHECK_FREE(4);
 892                     PUSH(10); // DestType
 893                     PUSH(L6); // DestAddr (bit number in string)
 894                     PUSH(L7); // PC       (byte address in string)
 895                     PUSH ((frame - base) * 4); // FramePtr
 896                     // Call the filter function.
 897                     L1 = ioRock;
 898                     L2 = 1;
 899                     goto do_enter_function_L1;
 900                 }
 901                 break;
 902
 903             case 5: // Unicode string.
 904                 // Push a 'resume compressed string' call stub.
 905                 CHECK_FREE(4);
 906                 PUSH (10); // DestType
 907                 PUSH (L6); // DestAddr (bit number in string)
 908                 PUSH (L7); // PC       (byte address in string)
 909                 PUSH ((frame - base) * 4); // FramePtr
 910                 // Print the Unicode string.
 911                 L7 = L1;
 912                 goto resume_uni_string_L7;
 913
 914             case 8:  // Indirect reference.
 915                 L3 = memRead32(L1);
 916                 L2 = 0; goto indirect_L3_args_L2;
 917
 918             case 9:  // Double-indirect reference.
 919                 L3 = memRead32(L1); L3 = memRead32(L3);
 920                 L2 = 0; goto indirect_L3_args_L2;
 921
 922             case 10: // Indirect reference with args.
 923                 L3 = memRead32(L1);
 924                 L2 = memRead32(L1 + 4); goto indirect_L3_args_L2;
 925
 926             case 11: // Double-indirect reference with args.
 927                 L3 = memRead32(L1); L3 = memRead32(L3);
 928                 L2 = memRead32(L1 + 4); goto indirect_L3_args_L2;
 929
 930             indirect_L3_args_L2:
 931                 // Push a 'resume compressed string' call stub.
 932                 CHECK_FREE(4);
 933                 PUSH (10); // DestType
 934                 PUSH (L6); // DestAddr (bit number in string)
 935                 PUSH (L7); // PC       (byte address in string)
 936                 PUSH ((frame - base) * 4); // FramePtr
 937                 // Check the type of the embedded object.
 938                 switch (memRead8(L3))
 939                 {
 940                     case 0xE0: // C string.
 941                         L7 = L3 + 1;
 942                         goto resume_c_string_L7;
 943
 944                     case 0xE1: // Compressed string.
 945                         L7 = L3 + 1;
 946                         L6 = 0;
 947                         goto resume_compressed_string_L7_bit_L6;
 948
 949                     case 0xE2: // Unicode string.
 950                         L7 = L3 + 4; // Skip extra three padding bytes.
 951                         goto resume_uni_string_L7;
 952
 953                     case 0xC0: case 0xC1: // Function.
 954                         // Retrieve arguments.
 955                         for (L1 += 8, L4 = 0; L4 < L2 ; ++L4, L1+=4)
 956                             args[L4] = memRead32(L1);
 957                         // Enter function.
 958                         L1 = L3;
 959                         goto do_enter_function_L1;
 960
 961                     default: fatalError ("Embedded object in string has unknown type");
 962                 }
 963                 break;
 964
 965             default: fatalError ("Unknown string table node type");
 966         }
 967         // Start back at the root node again.
 968         goto resume_compressed_string_L7_bit_L6;
 969
 970     do_streamstr:
 971         // Push a 'resume function' call stub.
 972         CHECK_FREE(4);
 973         PUSH (11);                            // DestType
 974         PUSH (0);                             // Addr
 975         PUSH (READ_PC);                       // PC
 976         PUSH ((frame - base) * 4); // FramePtr
 977
 978         // Load the string's type byte.
 979         L2 = memRead8(L1++);
 980         if (L2 == 0xE0)
 981         {
 982             // Uncompressed string.
 983             L7 = L1;
 984             goto resume_c_string_L7;
 985         }
 986         else if (L2 == 0xE1)
 987         {
 988             // Compressed string.
 989             L7 = L1;
 990             L6 = 0;
 991             goto resume_compressed_string_L7_bit_L6;
 992         }
 993         else if (L2 == 0xE2)
 994         {
 995             // Uncompressed Unicode string.
 996             L7 = L1 + 3; // Skip three padding bytes.
 997             goto resume_uni_string_L7;
 998         }
 999         else
1000         {
1001             fatalError ("Value used in streamstr was not a string");
1002             goto finished;
1003         }
1004
1005     do_streamchar:
1006         L7 = READ_PC;
1007         if (ioMode == IO_NULL)
1008             { /* Do nothing */ }
1009         else if (ioMode == IO_GLK)
1010         {
1011             unsigned char c = (L1 & 0xff);
1012             glk_put_char (c);
1013         }
1014         else
1015         {
1016             // Store this character in the args array.
1017             args [0] = (L1 & 0xff);
1018             // Push a 'resume function' call stub.
1019             CHECK_FREE(4);
1020             PUSH (0);                  // DestType
1021             PUSH (0);                  // Addr
1022             PUSH (L7);                 // PC
1023             PUSH ((frame - base) * 4); // FramePtr
1024             // Call the filter function.
1025             L1 = ioRock;
1026             L2 = 1;
1027             goto do_enter_function_L1;
1028         }
1029         NEXT;
1030
1031     do_streamunichar:
1032         L7 = READ_PC;
1033         if (ioMode == IO_NULL)
1034             { /* Do nothing */ }
1035         else if (ioMode == IO_GLK)
1036         {
1037 #ifdef GLK_MODULE_UNICODE
1038             glk_put_char_uni ((glui32) L1);
1039 #else
1040             unsigned char c = (L1 > 0 && L1 < 256) ? L1 : '?';
1041             glk_put_char (c);
1042 #endif // GLK_MODULE_UNICODE
1043         }
1044         else
1045         {
1046             // Store this character in the args array.
1047             args [0] = L1;
1048             // Push a 'resume function' call stub.
1049             CHECK_FREE(4);
1050             PUSH (0);                  // DestType
1051             PUSH (0);                  // Addr
1052             PUSH (L7);                 // PC
1053             PUSH ((frame - base) * 4); // FramePtr
1054             // Call the filter function.
1055             L1 = ioRock;
1056             L2 = 1;
1057             goto do_enter_function_L1;
1058         }
1059         NEXT;
1060
1061     do_streamnum:
1062         // Push a 'resume function' call stub.
1063         CHECK_FREE(4);
1064         PUSH (11);                            // DestType
1065         PUSH (0);                             // Addr
1066         PUSH (READ_PC);                       // PC
1067         PUSH ((frame - base) * 4); // FramePtr
1068
1069         // Print the number.
1070         L7 = L1;
1071         L6 = 0;
1072         goto resume_number_L7_digit_L6;
1073
1074     // Stub opcodes:
1075
1076     do_getmemsize:
1077         S1 = gEndMem;
1078         NEXT;
1079
1080     do_getiosys:
1081         S1 = ioMode;
1082         S2 = ioRock;
1083         NEXT;
1084
1085     do_setiosys:
1086         switch (L1)
1087         {
1088             case IO_NULL:
1089             case IO_FILTER:
1090             case IO_GLK:
1091                 ioMode = (enum IOMode) L1;
1092                 ioRock = L2;
1093                 break;
1094
1095             default:
1096                 fatalError ("Illegal I/O mode");
1097                 break;
1098         }
1099         NEXT;
1100
1101     do_quit:
1102         goto finished;
1103
1104     do_restart:
1105         // Reset game memory to its initial state.
1106         resetMemory(protectPos, protectSize);
1107         resetUndo();
1108
1109         // Reset all the stack pointers.
1110         frame = locals = values = sp = base;
1111
1112         // Call the first function.
1113         L1 = startPos; // Initial PC.
1114         L2 = 0; // No arguments.
1115         goto do_enter_function_L1;
1116
1117     do_verify:
1118         S1 = verifyMemory();
1119         NEXT;
1120
1121     do_random:
1122         if (L1 > 0)
1123             S1 = rand() % L1;
1124         else if (L1 < 0)
1125             S1 = -(rand() % -L1);
1126         else
1127         {
1128             // The parameter is zero, so we should generate a
1129             // random number in "the full 32-bit range". The rand()
1130             // function might not cover the entire range, so we'll
1131             // generate the high 16 bits and low 16 bits separately.
1132             S1 = (rand() & 0xffff) | (rand() << 16);
1133         }
1134         NEXT;
1135
1136     do_setrandom:
1137         srand (L1 ? L1 : time(NULL));
1138         NEXT;
1139
1140     do_glk:
1141         // The first argument is topmost in the stack; count is in L2.
1142         CHECK_USED(L2);
1143         // We want to store the arguments in 'args' in the same order.
1144         for (L3 = 0 ; L3 < L2 ; ++L3)
1145             args [L3] = POP;
1146         gStackPointer = sp;
1147         S1 = git_perform_glk (L1, L2, (glui32*) args);
1148         sp = gStackPointer;
1149         NEXT;
1150
1151     do_binarysearch:
1152         S1 = git_binary_search (L1, L2, L3, L4, L5, L6, L7);
1153         NEXT;
1154
1155     do_linearsearch:
1156         S1 = git_linear_search (L1, L2, L3, L4, L5, L6, L7);
1157         NEXT;
1158
1159     do_linkedsearch:
1160         S1 = git_linked_search (L1, L2, L3, L4, L5, L6);
1161         NEXT;
1162
1163     do_gestalt:
1164         S1 = gestalt (L1, L2);
1165         NEXT;
1166
1167     do_getstringtbl: S1 = stringTable; NEXT;
1168     do_setstringtbl: stringTable = L1; NEXT;
1169
1170     do_debugtrap:
1171         // TODO: do something useful here.
1172         NEXT;
1173
1174     do_stkroll:
1175         // We need to rotate the top L1 elements by L2 places.
1176         if (L1 < 0)
1177             fatalError ("Negative number of elements to rotate in stkroll");
1178         if (L1 > (sp - values))
1179             fatalError ("Tried to rotate too many elements in stkroll");
1180         // Now, let's normalise L2 into the range [0..L1).
1181         if (L2 >= 0)
1182             L2 = L2 % L1;
1183         else
1184             L2 = L1 - (-L2 % L1);
1185         // Avoid trivial cases.
1186         if (L1 == 0 || L2 == 0 || L2 == L1)
1187             NEXT;
1188         L2 = L1 - L2;
1189         // The problem is reduced to swapping elements [0..L2) with
1190         // elements [L2..L1). Let's call these two sequences A and B,
1191         // so we need to transform AB into BA. We do this sneakily
1192         // with reversals, as follows: AB -> A'B -> A'B' -> (A'B')',
1193         // where X' is the reverse of the sequence X.
1194 #define SWAP(x,y) \
1195         do { L4 = sp[(x)-L1];sp[(x)-L1]=sp[(y)-L1];sp[(y)-L1]=L4; } while (0)
1196
1197         // Reverse [0..L2).
1198         for (L3 = 0 ; L3 < L2/2 ; ++L3)
1199             SWAP (L3, L2-1-L3);
1200         // Reverse [L2..L1).
1201         for (L3 = L2 ; L3 < (L2 + (L1-L2)/2) ; ++L3)
1202             SWAP (L3, L1-1-(L3-L2));
1203         // Reverse [0..L1).
1204         for (L3 = 0 ; L3 < L1/2 ; ++L3)
1205             SWAP (L3, L1-1-L3);
1206
1207 #undef SWAP
1208         // And we're done!
1209         NEXT;
1210
1211     do_setmemsize:
1212         S1 = resizeMemory (L1, 0);
1213         NEXT;
1214
1215     do_protect:
1216         protectPos = L1;
1217         protectSize = L2;
1218         NEXT;
1219
1220     // Memory management (new with glulx spec 3.1)
1221
1222     do_mzero:
1223         if (L1 > 0) {
1224                         if (L2 < gRamStart || (L2 + L1) > gEndMem)
1225                                 memWriteError(L2);
1226                         memset(gRam + L2, 0, L1);
1227                 }
1228         NEXT;
1229
1230     do_mcopy:
1231         if (L1 > 0) {
1232             if (L2 < 0 || (L2 + L1) > gEndMem)
1233                 memReadError(L2);
1234             if (L3 < gRamStart || (L3 + L1) > gEndMem)
1235                 memWriteError(L3);
1236             // ROM and ROM are stored separately, so this is a bit fiddly...
1237             if (L2 > gRamStart) {
1238                 // Only need to copy from RAM. Might be overlapping, so use memmove.
1239                 memmove(gRam + L3, gRam + L2, L1);
1240             } else if ((L2 + L1) <= gRamStart) {
1241                 // Only need to copy from ROM. Can't overlap, so memcpy is safe.
1242                 memcpy(gRam + L3, gRom + L2, L1);
1243             } else {
1244                 // Need to copy from both ROM and RAM.
1245                 L4 = (L2 + L1) - gRamStart; // Amount of ROM to copy.
1246                 memcpy(gRam + L3, gRom + L2, L4);
1247                 memmove(gRam + L3 + L4, gRam + L2 + L4, L1 - L4);
1248             }
1249         }
1250         NEXT;
1251
1252     do_malloc:
1253         S1 = heap_alloc(L1);
1254         NEXT;
1255
1256     do_mfree:
1257         heap_free(L1);
1258         NEXT;
1259
1260     // Function acceleration (new with glulx spec 3.1.1)
1261
1262     do_accelfunc:
1263         accel_set_func(L1, L2);
1264         NEXT;
1265
1266     do_accelparam:
1267         accel_set_param(L1, L2);
1268         NEXT;
1269
1270     // Special Git opcodes
1271
1272     do_git_setcacheram:
1273         gCacheRAM = (L1 == 0) ? 0 : 1;
1274         NEXT;
1275
1276     do_git_prunecache:
1277         pruneCodeCache (L1, L2);
1278         NEXT;
1279
1280     // Error conditions:
1281
1282     do_error_bad_opcode:
1283         fatalError ("Illegal instruction");
1284         goto finished;
1285
1286     stack_overflow:
1287         fatalError ("Stack overflow");
1288         goto finished;
1289
1290     stack_underflow:
1291         fatalError ("Stack underflow");
1292         goto finished;
1293
1294 // ---------------------------------
1295
1296 finished:
1297
1298     free (base);
1299     shutdownCompiler();
1300 }