undo.c

/*  Nitfol - z-machine interpreter using Glk for output.
    Copyright (C) 1999  Evin Robertson

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.

    The author can be reached at nitfol@deja.com
*/
#include "nitfol.h"


/* Early versions just used quetzal format for the undo slot, which let
   me just call the same function, but made it impossible to add undo
   capability to games which don't natively support it, and was too expensive
   to provide infinite undo/redo.

   Now I use a linked list containing a memory delta and stack stored in
   quetzal format.  We take the delta between consecutive turns. This makes
   things smaller as there should be fewer differences between turns than
   from beginning to end of a story.

   Since there is very little difference between turns, I use quetzal
   format for the delta with a twist.  If there are runs of more than
   127 unchanged bytes, I store the length in a 15 bit number, ala UTF-8.
   This saves over a hundred bytes each turn (depending on game size and
   arrangement).

   Here is some data for advent (note that the usages are mostly for the
   the previous turn, since the save_undo is called shortly after each input):

Command:                    Overhead Dynamic  Stack  Total
                                     Memory
enter                          28  +   20  +  172  =  220
take all                       28  +  435  +  172  =  635
x stream                       28  +  266  +  172  =  466
exit                           28  +  132  +  172  =  332
s                              28  +  120  +  172  =  320
verbose                        28  +  114  +  172  =  314
d                              28  +   64  +  172  =  264
s                              28  +   90  +  172  =  290
unlock grate with keys         28  +  127  +  172  =  327
open grate. down.              28  +  202  +  172  =  402
help                           28  +  199  +  172  =  399

   Overhead doesn't count alignment and malloc overhead. Assume another 20
   bytes there.

   At approx 380 bytes per turn, I can store over 2500 turns in a meg of
   memory, enough for a longish game.

   Note that stack size (and contents mostly) stay the same between calls
   since save_undo is almost always called from the same place.  I should take
   advantage of this somehow.  (another hundred bytes to save, another 1000
   turns per meg...)

*/


static zbyte *prevstate = NULL;

typedef struct move_difference move_difference;

struct move_difference {
  move_difference *next;

  zbyte *delta;       /* Encoded like quetzal mixed with UTF-8 */
  glui32 deltalength;

  offset PC;
  offset oldPC;
  BOOL PC_in_instruction;

  zbyte *stackchunk;  /* Quetzal encoded */
  glui32 stacklength;
};

static move_difference *movelist = NULL;
static int move_index;


void init_undo(void)
{
  kill_undo();

  prevstate = (zbyte *) n_malloc(dynamic_size);
  n_memcpy(prevstate, z_memory, dynamic_size);
}

/* Frees old undo slots if possible in order to reduce memory consumption.
   Will never free the most recent @save_undo */
BOOL free_undo(void)
{
  move_difference *p, *g = NULL;
  for(p = movelist; p; p=p->next)
    if(p->next)
      g = p;
  if(g == NULL)
    return FALSE;

  n_free(g->next->delta);
  n_free(g->next->stackchunk);
  n_free(g->next);
  g->next = NULL;
  return TRUE;
}


BOOL saveundo(BOOL in_instruction)
{
  move_difference newdiff;
  strid_t stack;
  stream_result_t poo;

  if(!allow_saveundo)
    return TRUE;

  /* In games which provide @save_undo, we will have already issued a faked
     saveundo before the first @save_undo hits, since there hadn't been any
     @save_undo before the first read line.  So when this happens, wipe the
     fake saveundo in favor of the real one */
  if(in_instruction && movelist && !movelist->next
     && !movelist->PC_in_instruction)
    init_undo();

    
  if(!quetzal_diff(z_memory, prevstate, dynamic_size, &newdiff.delta,
		   &newdiff.deltalength, TRUE))
    return FALSE;

#ifdef PARANOID
  {
    char *newmem = (char *) n_malloc(dynamic_size);
    n_memcpy(newmem, prevstate, dynamic_size);
    quetzal_undiff(newmem, dynamic_size, newdiff.delta,
		   newdiff.deltalength, TRUE);
    if(n_memcmp(z_memory, newmem, dynamic_size)) {
      n_show_error(E_SAVE, "save doesn't match itself", 0);
    }
    n_free(newmem);
  }
#endif
  
  newdiff.PC = PC;
  newdiff.oldPC = oldPC;
  
  newdiff.PC_in_instruction = in_instruction;
  newdiff.stacklength = get_quetzal_stack_size();
  newdiff.stackchunk = (zbyte *) n_malloc(newdiff.stacklength);
  stack = glk_stream_open_memory((char *) newdiff.stackchunk,
				 newdiff.stacklength, filemode_Write, 0);
  if(!stack) {
    n_free(newdiff.delta);
    n_free(newdiff.stackchunk);
    return FALSE;
  }
  if(!quetzal_stack_save(stack)) {
    glk_stream_close(stack, NULL);
    n_free(newdiff.delta);
    n_free(newdiff.stackchunk);
    return FALSE;
  }
  glk_stream_close(stack, &poo);
  if(poo.writecount != newdiff.stacklength) {
    n_show_error(E_SAVE, "incorrect stack size assessment", poo.writecount);
    n_free(newdiff.delta);
    n_free(newdiff.stackchunk);
    return FALSE;
  }

  while(move_index-- > 0) {
    n_free(movelist->delta);
    n_free(movelist->stackchunk);
    LEremove(movelist);
  }
  LEadd(movelist, newdiff);
  move_index++;
  n_memcpy(prevstate, z_memory, dynamic_size);

  has_done_save_undo = TRUE;
  return TRUE;
}


BOOL restoreundo(void)
{
  strid_t stack;
  int i;
  glui32 wid, hei;
  move_difference *p = movelist;

  if(!p || move_index < 0)
    return FALSE;
  
  for(i = 0; i < move_index; i++) {
    p=p->next;
    if(!p)
      return FALSE;
  }
  move_index++;

  n_memcpy(z_memory, prevstate, dynamic_size);

  quetzal_undiff(prevstate, dynamic_size, p->delta, p->deltalength, TRUE);
  
  stack = glk_stream_open_memory((char *) p->stackchunk, p->stacklength,
				 filemode_Read, 0);

  quetzal_stack_restore(stack, p->stacklength);
  glk_stream_close(stack, NULL);

  if(p->PC_in_instruction) {
    PC = p->PC;
    mop_store_result(2);
    false_undo = FALSE;
  } else {
    PC = p->oldPC;
    false_undo = TRUE;
  }
  has_done_save_undo = TRUE;

  z_find_size(&wid, &hei);
  set_header(wid, hei);
  return TRUE;
}


/* Just like restoreundo, but the opposite ;) 
   The idea is to go to the @save_undo location, but return 0 instead of 2
   so the game thinks it just successfully saved the game. For games which
   don't contain @save_undo, jumps to right after the @read instruction. */
BOOL restoreredo(void)
{
  strid_t stack;
  int i;
  glui32 wid, hei;
  stream_result_t poo;
  move_difference *p = movelist;

  if(!p || move_index <= 0)
    return FALSE;
  
  move_index--;
  for(i = 0; i < move_index; i++) {
    p=p->next;
    if(!p)
      return FALSE;
  }

  quetzal_undiff(prevstate, dynamic_size, p->delta, p->deltalength, TRUE);
  
  n_memcpy(z_memory, prevstate, dynamic_size);

  stack = glk_stream_open_memory((char *) p->stackchunk, p->stacklength,
				 filemode_Read, 0);

  quetzal_stack_restore(stack, p->stacklength);
  glk_stream_close(stack, &poo);

  if(poo.readcount != p->stacklength) {
    n_show_error(E_SAVE, "incorrect stack size assessment", poo.readcount);
    return FALSE;
  }

  if(p->PC_in_instruction) {
    PC = p->PC;
    mop_store_result(0);
    false_undo = FALSE;
  } else {
    PC = p->PC;
    false_undo = FALSE;
  }
  has_done_save_undo = TRUE;

  z_find_size(&wid, &hei);
  set_header(wid, hei);
  return TRUE;
}


#ifdef DEBUGGING

/* For automapping, we want the saveundo/restoreundo to be as fast as possible
   and we also don't want it clobbering the redo capabilities, so give it
   separate fast_saveundo and fast_restoreundo.  Doesn't need multiple undo
   or redo
*/

struct fast_undoslot {
  zbyte *z_mem;
  glui32 z_memsize;
  offset PC;
  zbyte *stackchunk;  /* Quetzal encoded */
  glui32 stackchunksize;
  glui32 stacklength;
};


static struct fast_undoslot automap_undoslot = { NULL, 0, 0, NULL, 0, 0 };

BOOL fast_saveundo(void)
{
  strid_t stack;
  glui32 stack_size;
  /* Avoids realloc() in hopes that'll make it a teensy bit faster */
  if(automap_undoslot.z_memsize < dynamic_size) {
    n_free(automap_undoslot.z_mem);
    automap_undoslot.z_mem = n_malloc(dynamic_size);
    automap_undoslot.z_memsize = dynamic_size;
  }
  n_memcpy(automap_undoslot.z_mem, z_memory, dynamic_size);

  automap_undoslot.PC = oldPC;

  automap_undoslot.stacklength = stack_size = get_quetzal_stack_size();
  if(automap_undoslot.stackchunksize < stack_size) {
    free(automap_undoslot.stackchunk);
    automap_undoslot.stackchunk = (zbyte *) n_malloc(stack_size);
    automap_undoslot.stackchunksize = stack_size;
  }
  
  stack = glk_stream_open_memory((char *) automap_undoslot.stackchunk,
				 automap_undoslot.stacklength,
				 filemode_Write, 0);
  if(!stack)
    return FALSE;
  if(!quetzal_stack_save(stack)) {
    glk_stream_close(stack, NULL);
    return FALSE;
  }
  glk_stream_close(stack, NULL);
  return TRUE;
}


BOOL fast_restoreundo(void)
{
  strid_t stack;
  n_memcpy(z_memory, automap_undoslot.z_mem, dynamic_size);
  PC = automap_undoslot.PC;

  stack = glk_stream_open_memory((char *) automap_undoslot.stackchunk,
				 automap_undoslot.stacklength,
				 filemode_Read, 0);

  quetzal_stack_restore(stack, automap_undoslot.stacklength);
  glk_stream_close(stack, NULL);
  return TRUE;
}

#endif


void kill_undo(void)
{
  n_free(prevstate);
  prevstate = 0;

  while(movelist) {
    n_free(movelist->delta);
    n_free(movelist->stackchunk);
    LEremove(movelist);
  }
  move_index = 0;

#ifdef DEBUGGING
  n_free(automap_undoslot.z_mem);
  n_free(automap_undoslot.stackchunk);
  automap_undoslot.z_mem = NULL;
  automap_undoslot.z_memsize = 0;
  automap_undoslot.PC = 0;
  automap_undoslot.stackchunk = NULL;
  automap_undoslot.stackchunksize = 0;
  automap_undoslot.stacklength = 0;
#endif
}