interpreters/nitfol/undo.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., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
  17
  18     The author can be reached at nitfol@deja.com
  19 */
  20 #include "nitfol.h"
  21
  22
  23 /* Early versions just used quetzal format for the undo slot, which let
  24    me just call the same function, but made it impossible to add undo
  25    capability to games which don't natively support it, and was too expensive
  26    to provide infinite undo/redo.
  27
  28    Now I use a linked list containing a memory delta and stack stored in
  29    quetzal format.  We take the delta between consecutive turns. This makes
  30    things smaller as there should be fewer differences between turns than
  31    from beginning to end of a story.
  32
  33    Since there is very little difference between turns, I use quetzal
  34    format for the delta with a twist.  If there are runs of more than
  35    127 unchanged bytes, I store the length in a 15 bit number, ala UTF-8.
  36    This saves over a hundred bytes each turn (depending on game size and
  37    arrangement).
  38
  39    Here is some data for advent (note that the usages are mostly for the
  40    the previous turn, since the save_undo is called shortly after each input):
  41
  42 Command:                    Overhead Dynamic  Stack  Total
  43                                      Memory
  44 enter                          28  +   20  +  172  =  220
  45 take all                       28  +  435  +  172  =  635
  46 x stream                       28  +  266  +  172  =  466
  47 exit                           28  +  132  +  172  =  332
  48 s                              28  +  120  +  172  =  320
  49 verbose                        28  +  114  +  172  =  314
  50 d                              28  +   64  +  172  =  264
  51 s                              28  +   90  +  172  =  290
  52 unlock grate with keys         28  +  127  +  172  =  327
  53 open grate. down.              28  +  202  +  172  =  402
  54 help                           28  +  199  +  172  =  399
  55
  56    Overhead doesn't count alignment and malloc overhead. Assume another 20
  57    bytes there.
  58
  59    At approx 380 bytes per turn, I can store over 2500 turns in a meg of
  60    memory, enough for a longish game.
  61
  62    Note that stack size (and contents mostly) stay the same between calls
  63    since save_undo is almost always called from the same place.  I should take
  64    advantage of this somehow.  (another hundred bytes to save, another 1000
  65    turns per meg...)
  66
  67 */
  68
  69
  70 static zbyte *prevstate = NULL;
  71
  72 typedef struct move_difference move_difference;
  73
  74 struct move_difference {
  75   move_difference *next;
  76
  77   zbyte *delta;       /* Encoded like quetzal mixed with UTF-8 */
  78   glui32 deltalength;
  79
  80   offset PC;
  81   offset oldPC;
  82   BOOL PC_in_instruction;
  83
  84   zbyte *stackchunk;  /* Quetzal encoded */
  85   glui32 stacklength;
  86 };
  87
  88 static move_difference *movelist = NULL;
  89 static int move_index;
  90
  91
  92 void init_undo(void)
  93 {
  94   kill_undo();
  95
  96   prevstate = (zbyte *) n_malloc(dynamic_size);
  97   n_memcpy(prevstate, z_memory, dynamic_size);
  98 }
  99
 100 /* Frees old undo slots if possible in order to reduce memory consumption.
 101    Will never free the most recent @save_undo */
 102 BOOL free_undo(void)
 103 {
 104   move_difference *p, *g = NULL;
 105   for(p = movelist; p; p=p->next)
 106     if(p->next)
 107       g = p;
 108   if(g == NULL)
 109     return FALSE;
 110
 111   n_free(g->next->delta);
 112   n_free(g->next->stackchunk);
 113   n_free(g->next);
 114   g->next = NULL;
 115   return TRUE;
 116 }
 117
 118
 119 BOOL saveundo(BOOL in_instruction)
 120 {
 121   move_difference newdiff;
 122   strid_t stack;
 123   stream_result_t poo;
 124
 125   if(!allow_saveundo)
 126     return TRUE;
 127
 128   /* In games which provide @save_undo, we will have already issued a faked
 129      saveundo before the first @save_undo hits, since there hadn't been any
 130      @save_undo before the first read line.  So when this happens, wipe the
 131      fake saveundo in favor of the real one */
 132   if(in_instruction && movelist && !movelist->next
 133      && !movelist->PC_in_instruction)
 134     init_undo();
 135
 136
 137   if(!quetzal_diff(z_memory, prevstate, dynamic_size, &newdiff.delta,
 138                    &newdiff.deltalength, TRUE))
 139     return FALSE;
 140
 141 #ifdef PARANOID
 142   {
 143     char *newmem = (char *) n_malloc(dynamic_size);
 144     n_memcpy(newmem, prevstate, dynamic_size);
 145     quetzal_undiff(newmem, dynamic_size, newdiff.delta,
 146                    newdiff.deltalength, TRUE);
 147     if(n_memcmp(z_memory, newmem, dynamic_size)) {
 148       n_show_error(E_SAVE, "save doesn't match itself", 0);
 149     }
 150     n_free(newmem);
 151   }
 152 #endif
 153
 154   newdiff.PC = PC;
 155   newdiff.oldPC = oldPC;
 156
 157   newdiff.PC_in_instruction = in_instruction;
 158   newdiff.stacklength = get_quetzal_stack_size();
 159   newdiff.stackchunk = (zbyte *) n_malloc(newdiff.stacklength);
 160   stack = glk_stream_open_memory((char *) newdiff.stackchunk,
 161                                  newdiff.stacklength, filemode_Write, 0);
 162   if(!stack) {
 163     n_free(newdiff.delta);
 164     n_free(newdiff.stackchunk);
 165     return FALSE;
 166   }
 167   if(!quetzal_stack_save(stack)) {
 168     glk_stream_close(stack, NULL);
 169     n_free(newdiff.delta);
 170     n_free(newdiff.stackchunk);
 171     return FALSE;
 172   }
 173   glk_stream_close(stack, &poo);
 174   if(poo.writecount != newdiff.stacklength) {
 175     n_show_error(E_SAVE, "incorrect stack size assessment", poo.writecount);
 176     n_free(newdiff.delta);
 177     n_free(newdiff.stackchunk);
 178     return FALSE;
 179   }
 180
 181   while(move_index-- > 0) {
 182     n_free(movelist->delta);
 183     n_free(movelist->stackchunk);
 184     LEremove(movelist);
 185   }
 186   LEadd(movelist, newdiff);
 187   move_index++;
 188   n_memcpy(prevstate, z_memory, dynamic_size);
 189
 190   has_done_save_undo = TRUE;
 191   return TRUE;
 192 }
 193
 194
 195 BOOL restoreundo(void)
 196 {
 197   strid_t stack;
 198   int i;
 199   glui32 wid, hei;
 200   move_difference *p = movelist;
 201
 202   if(!p || move_index < 0)
 203     return FALSE;
 204
 205   for(i = 0; i < move_index; i++) {
 206     p=p->next;
 207     if(!p)
 208       return FALSE;
 209   }
 210   move_index++;
 211
 212   n_memcpy(z_memory, prevstate, dynamic_size);
 213
 214   quetzal_undiff(prevstate, dynamic_size, p->delta, p->deltalength, TRUE);
 215
 216   stack = glk_stream_open_memory((char *) p->stackchunk, p->stacklength,
 217                                  filemode_Read, 0);
 218
 219   quetzal_stack_restore(stack, p->stacklength);
 220   glk_stream_close(stack, NULL);
 221
 222   if(p->PC_in_instruction) {
 223     PC = p->PC;
 224     mop_store_result(2);
 225     false_undo = FALSE;
 226   } else {
 227     PC = p->oldPC;
 228     false_undo = TRUE;
 229   }
 230   has_done_save_undo = TRUE;
 231
 232   z_find_size(&wid, &hei);
 233   set_header(wid, hei);
 234   return TRUE;
 235 }
 236
 237
 238 /* Just like restoreundo, but the opposite ;)
 239    The idea is to go to the @save_undo location, but return 0 instead of 2
 240    so the game thinks it just successfully saved the game. For games which
 241    don't contain @save_undo, jumps to right after the @read instruction. */
 242 BOOL restoreredo(void)
 243 {
 244   strid_t stack;
 245   int i;
 246   glui32 wid, hei;
 247   stream_result_t poo;
 248   move_difference *p = movelist;
 249
 250   if(!p || move_index <= 0)
 251     return FALSE;
 252
 253   move_index--;
 254   for(i = 0; i < move_index; i++) {
 255     p=p->next;
 256     if(!p)
 257       return FALSE;
 258   }
 259
 260   quetzal_undiff(prevstate, dynamic_size, p->delta, p->deltalength, TRUE);
 261
 262   n_memcpy(z_memory, prevstate, dynamic_size);
 263
 264   stack = glk_stream_open_memory((char *) p->stackchunk, p->stacklength,
 265                                  filemode_Read, 0);
 266
 267   quetzal_stack_restore(stack, p->stacklength);
 268   glk_stream_close(stack, &poo);
 269
 270   if(poo.readcount != p->stacklength) {
 271     n_show_error(E_SAVE, "incorrect stack size assessment", poo.readcount);
 272     return FALSE;
 273   }
 274
 275   if(p->PC_in_instruction) {
 276     PC = p->PC;
 277     mop_store_result(0);
 278     false_undo = FALSE;
 279   } else {
 280     PC = p->PC;
 281     false_undo = FALSE;
 282   }
 283   has_done_save_undo = TRUE;
 284
 285   z_find_size(&wid, &hei);
 286   set_header(wid, hei);
 287   return TRUE;
 288 }
 289
 290
 291 #ifdef DEBUGGING
 292
 293 /* For automapping, we want the saveundo/restoreundo to be as fast as possible
 294    and we also don't want it clobbering the redo capabilities, so give it
 295    separate fast_saveundo and fast_restoreundo.  Doesn't need multiple undo
 296    or redo
 297 */
 298
 299 struct fast_undoslot {
 300   zbyte *z_mem;
 301   glui32 z_memsize;
 302   offset PC;
 303   zbyte *stackchunk;  /* Quetzal encoded */
 304   glui32 stackchunksize;
 305   glui32 stacklength;
 306 };
 307
 308
 309 static struct fast_undoslot automap_undoslot = { NULL, 0, 0, NULL, 0, 0 };
 310
 311 BOOL fast_saveundo(void)
 312 {
 313   strid_t stack;
 314   glui32 stack_size;
 315   /* Avoids realloc() in hopes that'll make it a teensy bit faster */
 316   if(automap_undoslot.z_memsize < dynamic_size) {
 317     n_free(automap_undoslot.z_mem);
 318     automap_undoslot.z_mem = n_malloc(dynamic_size);
 319     automap_undoslot.z_memsize = dynamic_size;
 320   }
 321   n_memcpy(automap_undoslot.z_mem, z_memory, dynamic_size);
 322
 323   automap_undoslot.PC = oldPC;
 324
 325   automap_undoslot.stacklength = stack_size = get_quetzal_stack_size();
 326   if(automap_undoslot.stackchunksize < stack_size) {
 327     free(automap_undoslot.stackchunk);
 328     automap_undoslot.stackchunk = (zbyte *) n_malloc(stack_size);
 329     automap_undoslot.stackchunksize = stack_size;
 330   }
 331
 332   stack = glk_stream_open_memory((char *) automap_undoslot.stackchunk,
 333                                  automap_undoslot.stacklength,
 334                                  filemode_Write, 0);
 335   if(!stack)
 336     return FALSE;
 337   if(!quetzal_stack_save(stack)) {
 338     glk_stream_close(stack, NULL);
 339     return FALSE;
 340   }
 341   glk_stream_close(stack, NULL);
 342   return TRUE;
 343 }
 344
 345
 346 BOOL fast_restoreundo(void)
 347 {
 348   strid_t stack;
 349   n_memcpy(z_memory, automap_undoslot.z_mem, dynamic_size);
 350   PC = automap_undoslot.PC;
 351
 352   stack = glk_stream_open_memory((char *) automap_undoslot.stackchunk,
 353                                  automap_undoslot.stacklength,
 354                                  filemode_Read, 0);
 355
 356   quetzal_stack_restore(stack, automap_undoslot.stacklength);
 357   glk_stream_close(stack, NULL);
 358   return TRUE;
 359 }
 360
 361 #endif
 362
 363
 364 void kill_undo(void)
 365 {
 366   n_free(prevstate);
 367   prevstate = 0;
 368
 369   while(movelist) {
 370     n_free(movelist->delta);
 371     n_free(movelist->stackchunk);
 372     LEremove(movelist);
 373   }
 374   move_index = 0;
 375
 376 #ifdef DEBUGGING
 377   n_free(automap_undoslot.z_mem);
 378   n_free(automap_undoslot.stackchunk);
 379   automap_undoslot.z_mem = NULL;
 380   automap_undoslot.z_memsize = 0;
 381   automap_undoslot.PC = 0;
 382   automap_undoslot.stackchunk = NULL;
 383   automap_undoslot.stackchunksize = 0;
 384   automap_undoslot.stacklength = 0;
 385 #endif
 386 }