interpreters/nitfol/stack.c

   1 /*  Nitfol - z-machine interpreter using Glk for output.
   2     Copyright (C) 1999  Evin Robertson
   3
   4     This program is free software; you can redistribute it and/or modify
   5     it under the terms of the GNU General Public License as published by
   6     the Free Software Foundation; either version 2 of the License, or
   7     (at your option) any later version.
   8
   9     This program is distributed in the hope that it will be useful,
  10     but WITHOUT ANY WARRANTY; without even the implied warranty of
  11     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12     GNU General Public License for more details.
  13
  14     You should have received a copy of the GNU General Public License
  15     along with this program; if not, write to the Free Software
  16     Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  17
  18     The author can be reached at nitfol@deja.com
  19 */
  20 #include "nitfol.h"
  21
  22 /* Contains everything which references the stack directly. */
  23
  24 /* Uses two stacks because I don't want to worry about alignment issues */
  25
  26 typedef struct Stack_frame Stack_frame;
  27
  28 struct Stack_frame {
  29   offset stack_stack_start;  /* points into stack_stack to local variables
  30                                 for this frame, which are followed by
  31                                 stack for pushing/popping */
  32   offset return_PC;
  33   int num_locals;
  34   zword arguments;           /* Number of arguments used for check_count */
  35   int result_variable;       /* Where to place the result upon returning */
  36 };
  37
  38 static zword *stack_stack = NULL; /* Holds local variables and pushed values */
  39 static offset stack_pointer;      /* Current offset into stack_stack */
  40 static offset stack_min;  /* Minimum for stack_pointer (how much we can pop) */
  41 static offset stack_max;  /* Maximum for stack_pointer (size of stack) */
  42 static zword *local_vars; /* Pointer to local variables for current frame */
  43
  44 static Stack_frame *stack_frames = NULL;
  45 static zword frame_count;    /* number of frames on the stack */
  46 static zword frame_max;
  47
  48
  49 void init_stack(offset initialstack_stack_size, zword initialframe_size)
  50 {
  51   n_free(stack_stack);
  52   stack_stack = (zword *) n_malloc(sizeof(*stack_stack) *
  53                                    initialstack_stack_size);
  54   stack_pointer = 0;
  55   stack_min = 0;
  56   stack_max = initialstack_stack_size;
  57
  58   n_free(stack_frames);
  59   stack_frames = (Stack_frame *) n_malloc(sizeof(*stack_frames) *
  60                                           initialframe_size);
  61   frame_count = 0;
  62   if(stacklimit && initialframe_size > stacklimit)
  63     frame_max = stacklimit;
  64   else
  65     frame_max = initialframe_size;
  66
  67   stack_frames[frame_count].stack_stack_start = 0;
  68   stack_frames[frame_count].return_PC = 0;
  69   stack_frames[frame_count].num_locals = 0;
  70   stack_frames[frame_count].arguments = 0;
  71   stack_frames[frame_count].result_variable = -2;
  72   local_vars = stack_stack + stack_frames[frame_count].stack_stack_start;
  73 }
  74
  75 void kill_stack(void)
  76 {
  77   n_free(stack_stack);
  78   n_free(stack_frames);
  79   stack_stack = 0;
  80   stack_frames = 0;
  81 }
  82
  83 /* Perform various sanity checks on the stack to make sure all is well in
  84    Denmark. */
  85 BOOL verify_stack(void)
  86 {
  87   zword f;
  88   if(frame_count > frame_max) {
  89     n_show_error(E_STACK, "more frames than max", frame_count);
  90     return FALSE;
  91   }
  92   if(!stack_frames) {
  93     n_show_error(E_STACK, "no frames", 0);
  94     return FALSE;
  95   }
  96   for(f = 0; f < frame_count; f++) {
  97     if(stack_frames[f].stack_stack_start > stack_pointer) {
  98       n_show_error(E_STACK, "stack start after end", f);
  99       return FALSE;
 100     }
 101     if(stack_frames[f].return_PC > total_size) {
 102       n_show_error(E_STACK, "PC after end of game", f);
 103       return FALSE;
 104     }
 105     if(stack_frames[f].num_locals > 15) {
 106       n_show_error(E_STACK, "too many locals", f);
 107       return FALSE;
 108     }
 109     if(stack_frames[f].arguments > 7) {
 110       n_show_error(E_STACK, "too many arguments", f);
 111       return FALSE;
 112     }
 113     if(stack_frames[f].result_variable > 255) {
 114       n_show_error(E_STACK, "result variable too big", f);
 115       return FALSE;
 116     }
 117     if(stack_frames[f].result_variable < -2) {
 118       n_show_error(E_STACK, "unknown magic result variable", f);
 119       return FALSE;
 120     }
 121   }
 122   return TRUE;
 123 }
 124
 125
 126 /* Insure we have at least addsize more zwords available on the stack, and
 127  * if not, allocate more space
 128  */
 129 static void check_stack_stack(offset addsize)
 130 {
 131   if(stack_pointer + addsize >= stack_max) {
 132     stack_max *= 2;
 133     stack_stack = (zword *) n_realloc(stack_stack,
 134                                       sizeof(*stack_stack) * stack_max);
 135
 136     n_show_port(E_STACK, "stack larger than available on some interps", stack_max);
 137
 138     local_vars = stack_stack + stack_frames[frame_count].stack_stack_start;
 139   }
 140 }
 141
 142
 143 void add_stack_frame(offset return_PC, unsigned num_locals, zword *locals,
 144                      unsigned num_args, int result_var)
 145 {
 146   unsigned n;
 147   /* Don't increment the frame yet because we have error messages yet to
 148      show which need to receive a valid frame to output local variables */
 149   if(frame_count+1 >= frame_max) {
 150     frame_max *= 2;
 151     if(stacklimit && frame_max > stacklimit) {
 152       frame_max = stacklimit;
 153       if(frame_count+1 >= frame_max) {
 154         n_show_fatal(E_STACK, "recursed deeper than allowed", frame_count+1);
 155       }
 156     }
 157     stack_frames = (Stack_frame *)
 158                    n_realloc(stack_frames, sizeof(*stack_frames) * frame_max);
 159     n_show_port(E_STACK, "deep recursion not available on some 'terps", frame_max);
 160   }
 161   frame_count++;
 162   stack_frames[frame_count].stack_stack_start = stack_pointer;
 163   stack_frames[frame_count].return_PC = return_PC;
 164   stack_frames[frame_count].num_locals = num_locals;
 165   stack_frames[frame_count].arguments = num_args;
 166   stack_frames[frame_count].result_variable = result_var;
 167
 168
 169   check_stack_stack(num_locals);
 170   for(n = 0; n < num_locals; n++)
 171     stack_stack[stack_pointer++] = locals[n];
 172
 173   stack_min = stack_pointer;
 174
 175   local_vars = stack_stack + stack_frames[frame_count].stack_stack_start;
 176 }
 177
 178
 179 void remove_stack_frame(void)
 180 {
 181 #ifndef FAST
 182   if(frame_count == 0) {
 183     n_show_error(E_STACK, "attempt to remove initial stack frame", 0);
 184     return;
 185   }
 186 #endif
 187   stack_pointer = stack_frames[frame_count].stack_stack_start;
 188   frame_count--;
 189   stack_min = stack_frames[frame_count].stack_stack_start +
 190               stack_frames[frame_count].num_locals;
 191   local_vars = stack_stack + stack_frames[frame_count].stack_stack_start;
 192 }
 193
 194
 195 void check_set_var(int var, zword val)
 196 {
 197   switch(var) {
 198   default: set_var(var, val); break;
 199   case -2: exit_decoder = TRUE; time_ret = val;     /* timer junk */
 200   case -1: ;
 201   }
 202 }
 203
 204
 205 void mop_func_return(zword ret_val)
 206 {
 207   int var;
 208   PC = stack_frames[frame_count].return_PC;
 209   var = stack_frames[frame_count].result_variable;
 210   remove_stack_frame();
 211   check_set_var(var, ret_val);
 212   /*  printf("retn %x\n", PC); */
 213 }
 214
 215
 216 void op_catch(void)
 217 {
 218   mop_store_result(frame_count);
 219 }
 220
 221
 222 unsigned stack_get_numlocals(int frame)
 223 {
 224   if(stack_frames)
 225     return stack_frames[frame].num_locals;
 226   return 0;
 227 }
 228
 229
 230 void op_throw(void)
 231 {
 232 #ifndef FAST
 233   if(operand[1] > frame_count) {
 234     n_show_error(E_STACK, "attempting to throw away non-existent frames", operand[1]);
 235     return;
 236   }
 237 #endif
 238   if(operand[1] != 0) {
 239     frame_count = operand[1];
 240     mop_func_return(operand[0]);
 241   } else {
 242     n_show_error(E_STACK, "attempting to throw away initial frame", operand[0]);
 243   }
 244 }
 245
 246 void op_check_arg_count(void)
 247 {
 248   if(stack_frames[frame_count].arguments >= operand[0])
 249     mop_take_branch();
 250   else
 251     mop_skip_branch();
 252 }
 253
 254
 255 static zword stack_pop(void)
 256 {
 257 #ifndef FAST
 258   if(stack_pointer <= stack_min) {
 259     n_show_error(E_STACK, "underflow - excessive popping", stack_pointer);
 260     return 0;
 261   }
 262 #endif
 263   return stack_stack[--stack_pointer];
 264 }
 265
 266
 267 static void stack_push(zword n)
 268 {
 269   check_stack_stack(1);
 270   stack_stack[stack_pointer++] = n;
 271 }
 272
 273
 274 void op_push(void)
 275 {
 276   stack_push(operand[0]);
 277 }
 278
 279
 280 void op_pop(void)
 281 {
 282   stack_pop();
 283 }
 284
 285
 286 void op_pull(void)
 287 {
 288   if(zversion == 6) {  /* v6 uses user stacks */
 289     if(numoperands == 0 || operand[0] == 0)
 290       mop_store_result(stack_pop());
 291     else {
 292       zword space = LOWORD(operand[0]) + 1; /* One more slot is free */
 293       LOWORDwrite(operand[0], space);
 294       mop_store_result(LOWORD(operand[0] + space * ZWORD_SIZE));
 295     }
 296   } else {
 297     zword val = stack_pop();
 298     set_var(operand[0], val);
 299   }
 300 }
 301
 302
 303 void op_pop_stack(void)
 304 {
 305   zword i;
 306   if(numoperands < 2 || operand[1] == 0) {
 307     for(i = 0; i < operand[0]; i++)
 308       stack_pop();
 309   } else {
 310     zword space = LOWORD(operand[1]) + operand[0];
 311     LOWORDwrite(operand[1], space);
 312   }
 313 }
 314
 315
 316 void op_push_stack(void)
 317 {
 318   zword space = LOWORD(operand[1]);
 319   if(space) {
 320     LOWORDwrite(operand[1] + space * ZWORD_SIZE, operand[0]);
 321     LOWORDwrite(operand[1], space - 1);
 322     mop_take_branch();
 323   } else {
 324     mop_skip_branch();
 325   }
 326 }
 327
 328
 329 void mop_store_result(zword val)
 330 {
 331   set_var(HIBYTE(PC), val);
 332   PC++;
 333 }
 334
 335
 336 void op_ret_popped(void)
 337 {
 338   mop_func_return(stack_pop());
 339 }
 340
 341 unsigned stack_get_depth(void)
 342 {
 343   return frame_count;
 344 }
 345
 346 BOOL frame_is_valid(unsigned frame)
 347 {
 348   return frame <= frame_count;
 349 }
 350
 351 offset frame_get_PC(unsigned frame)
 352 {
 353   if(frame == frame_count) {
 354     return PC;
 355   }
 356   return stack_frames[frame+1].return_PC;
 357 }
 358
 359 zword frame_get_var(unsigned frame, int var)
 360 {
 361   if(var == 0 || var > 0x10) {
 362     n_show_error(E_STACK, "variable not readable from arbitrary frame", var);
 363     return 0;
 364   }
 365
 366   if(var > stack_frames[frame].num_locals)
 367     n_show_error(E_STACK, "reading nonexistant local", var);
 368
 369   return stack_stack[stack_frames[frame].stack_stack_start + (var - 1)];
 370 }
 371
 372
 373 void frame_set_var(unsigned frame, int var, zword val)
 374 {
 375   if(var == 0 || var > 0x10) {
 376     n_show_error(E_STACK, "variable not writable from arbitrary frame", var);
 377     return;
 378   }
 379
 380   if(var > stack_frames[frame].num_locals)
 381     n_show_error(E_STACK, "writing nonexistant local", var);
 382
 383   stack_stack[stack_frames[frame].stack_stack_start + (var - 1)] = val;;
 384 }
 385
 386 N_INLINE zword get_var(int var)
 387 {
 388   if(var < 0x10) {
 389     if(var != 0) {
 390 #ifndef FAST
 391       if(var > stack_frames[frame_count].num_locals)
 392         n_show_error(E_INSTR, "reading nonexistant local", var);
 393 #endif
 394       return local_vars[var - 1];
 395     }
 396     return stack_pop();
 397   }
 398   return LOWORD(z_globaltable + (var - 0x10) * ZWORD_SIZE);
 399 }
 400
 401 N_INLINE void set_var(int var, zword val)
 402 {
 403   if(var < 0x10) {
 404     if(var != 0) {
 405 #ifndef FAST
 406       if(var > stack_frames[frame_count].num_locals)
 407         n_show_error(E_INSTR, "setting nonexistant local", var);
 408 #endif
 409       local_vars[var - 1] = val;
 410     } else {
 411       stack_push(val);
 412     }
 413   } else {
 414     LOWORDwrite(z_globaltable + (var - 0x10) * ZWORD_SIZE, val);
 415   }
 416 }
 417
 418
 419 const unsigned qstackframe[] = { 3, 1, 1, 1, 2, 0 };
 420 enum qstacknames { qreturnPC, qflags, qvar, qargs, qeval };
 421
 422 BOOL quetzal_stack_restore(strid_t stream, glui32 qsize)
 423 {
 424   glui32 i = 0;
 425   int num_frames = 0;
 426
 427   kill_stack();
 428   init_stack(1024, 128);
 429
 430   while(i < qsize) {
 431     unsigned n;
 432     unsigned num_locals;
 433     zword locals[16];
 434     int num_args;
 435     int var;
 436
 437     glui32 qframe[5];
 438     i += fillstruct(stream, qstackframe, qframe, NULL);
 439
 440     if(qframe[qreturnPC] > total_size) {
 441       n_show_error(E_SAVE, "function return PC past end of memory",
 442                  qframe[qreturnPC]);
 443       return FALSE;
 444     }
 445
 446     if((qframe[qflags] & b11100000) != 0) {
 447       n_show_error(E_SAVE, "expected top bits of flag to be zero", qframe[qflags]);
 448       return FALSE;
 449     }
 450
 451     var = qframe[qvar];
 452     if(qframe[qflags] & b00010000)  /* from a call_n */
 453       var = -1;
 454
 455     num_locals = qframe[qflags] & b00001111;
 456
 457     if(num_locals > 15) {
 458       n_show_error(E_SAVE, "too many locals", num_locals);
 459       return FALSE;
 460     }
 461
 462     num_args = 0;
 463     switch(qframe[qargs]) {
 464     default:
 465       n_show_error(E_SAVE, "invalid argument count", qframe[qargs]);
 466       return FALSE;
 467     case b01111111: num_args++;
 468     case b00111111: num_args++;
 469     case b00011111: num_args++;
 470     case b00001111: num_args++;
 471     case b00000111: num_args++;
 472     case b00000011: num_args++;
 473     case b00000001: num_args++;
 474     case b00000000: ;
 475     }
 476
 477     for(n = 0; n < num_locals; n++) {
 478       unsigned char v[ZWORD_SIZE];
 479       glk_get_buffer_stream(stream, (char *) v, ZWORD_SIZE);
 480       locals[n] = MSBdecodeZ(v);
 481       i+=ZWORD_SIZE;
 482     }
 483
 484     if(zversion != 6 && num_frames == 0)
 485       ;               /* dummy stack frame; don't really use it */
 486     else
 487       add_stack_frame(qframe[qreturnPC],
 488                       num_locals, locals,
 489                       num_args, var);
 490
 491     for(n = 0; n < qframe[qeval]; n++) {
 492       unsigned char v[ZWORD_SIZE];
 493       glk_get_buffer_stream(stream, (char *) v, ZWORD_SIZE);
 494       stack_push(MSBdecodeZ(v));
 495       i += ZWORD_SIZE;
 496     }
 497
 498     num_frames++;
 499   }
 500   if(!verify_stack()) {
 501     n_show_error(E_SAVE, "restored stack fails verification", 0);
 502     return FALSE;
 503   }
 504   return TRUE;
 505 }
 506
 507
 508 glui32 get_quetzal_stack_size(void)
 509 {
 510   glui32 framespace;
 511   glui32 stackspace;
 512   framespace = frame_count * 8;
 513   stackspace = stack_pointer * ZWORD_SIZE;
 514   if(zversion != 6)
 515     framespace += 8;  /* for the dummy frame */
 516   return framespace + stackspace;
 517 }
 518
 519
 520 BOOL quetzal_stack_save(strid_t stream)
 521 {
 522   unsigned frame_num = 0;
 523
 524   if(zversion == 6)
 525     frame_num++;
 526
 527   if(!verify_stack()) {
 528     n_show_error(E_SAVE, "stack did not pass verification before saving", 0);
 529     return FALSE;
 530   }
 531
 532   /* We have to look one ahead to see how much stack space a frame uses; when
 533      we get to the last frame, there will be no next frame, so this won't work
 534      if there wasn't a frame there earlier with the correct info.  Add and
 535      remove a frame to make things happy */
 536   add_stack_frame(0, 0, NULL, 0, 0);
 537   remove_stack_frame();
 538
 539   for(; frame_num <= frame_count; frame_num++) {
 540     unsigned n;
 541     int num_locals;
 542     unsigned stack_size;
 543
 544     glui32 qframe[5];
 545
 546     const unsigned char argarray[8] = {
 547       b00000000, b00000001, b00000011, b00000111,
 548       b00001111, b00011111, b00111111, b01111111
 549     };
 550
 551     qframe[qreturnPC] = stack_frames[frame_num].return_PC;
 552
 553     qframe[qvar]      = stack_frames[frame_num].result_variable;
 554
 555     num_locals        = stack_frames[frame_num].num_locals;
 556
 557     if(num_locals > 15) {
 558       n_show_error(E_SAVE, "num_locals too big", num_locals);
 559       return FALSE;
 560     }
 561
 562     qframe[qflags] = num_locals;
 563
 564     if(stack_frames[frame_num].result_variable == -1) {
 565       qframe[qflags] |= b00010000;
 566       qframe[qvar] = 0;
 567     }
 568
 569     if(stack_frames[frame_num].arguments > 7) {
 570       n_show_error(E_SAVE, "too many function arguments", stack_frames[frame_num].arguments);
 571       return FALSE;
 572     }
 573
 574     qframe[qargs] = argarray[stack_frames[frame_num].arguments];
 575
 576     stack_size = (stack_frames[frame_num+1].stack_stack_start -
 577                   stack_frames[frame_num].stack_stack_start -
 578                   num_locals);
 579
 580     qframe[qeval] = stack_size;
 581
 582     if(frame_num == 0) {
 583       qframe[qreturnPC] = 0;
 584       qframe[qflags] = 0;
 585       qframe[qvar] = 0;
 586       qframe[qargs] = 0;
 587     }
 588
 589     emptystruct(stream, qstackframe, qframe);
 590
 591     for(n = 0; n < num_locals + stack_size; n++) {
 592       unsigned char v[ZWORD_SIZE];
 593       zword z = stack_stack[stack_frames[frame_num].stack_stack_start + n];
 594       MSBencodeZ(v, z);
 595       w_glk_put_buffer_stream(stream, (char *) v, ZWORD_SIZE);
 596     }
 597   }
 598   return TRUE;
 599 }