Edited documentation of ChimaraIF::command signal
[projects/chimara/chimara.git] / 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 }