interpreters/git/saveundo.c

   1 // $Id: saveundo.c,v 1.15 2003/10/20 16:05:06 iain Exp $
   2
   3 #include "git.h"
   4 #include <stdlib.h>
   5 #include <string.h>
   6 #include <assert.h>
   7
   8 typedef const git_uint8 * MemoryPage;
   9 typedef MemoryPage * MemoryMap;
  10
  11 typedef struct UndoRecord UndoRecord;
  12
  13 struct UndoRecord
  14 {
  15     git_uint32   endMem;
  16     MemoryMap    memoryMap;
  17     git_sint32   stackSize;
  18     git_sint32 * stack;
  19     glui32       heapSize;
  20     glui32     * heap;
  21     UndoRecord * prev;
  22     UndoRecord * next;
  23 };
  24
  25 static UndoRecord * gUndo = NULL;
  26 static git_uint32 gUndoSize = 0;
  27 static git_uint32 gMaxUndoSize = 256 * 1024;
  28
  29 static void reserveSpace (git_uint32);
  30 static void deleteRecord (UndoRecord * u);
  31
  32 void initUndo (git_uint32 size)
  33 {
  34     gMaxUndoSize = size;
  35     gUndoSize = 0;
  36     gUndo = NULL;
  37 }
  38
  39 int saveUndo (git_sint32 * base, git_sint32 * sp)
  40 {
  41     git_uint32 undoSize = sizeof(UndoRecord);
  42     git_uint32 mapSize = sizeof(MemoryPage*) * (gEndMem - gRamStart) / 256;
  43     git_uint32 stackSize = sizeof(git_sint32*) * (sp - base);
  44     git_uint32 totalSize = undoSize + mapSize + stackSize;
  45
  46     git_uint32 addr = gRamStart; // Address in glulx memory.
  47     git_uint32 slot = 0;         // Slot in our memory map.
  48
  49     UndoRecord * undo = malloc (undoSize);
  50     if (undo == NULL)
  51         fatalError ("Couldn't allocate undo record");
  52
  53     undo->endMem = gEndMem;
  54     undo->memoryMap = malloc (mapSize);
  55     undo->stackSize = stackSize;
  56     undo->stack = malloc (stackSize);
  57     undo->prev = NULL;
  58     undo->next = NULL;
  59
  60     if (undo->memoryMap == NULL || undo->stack == NULL)
  61         fatalError ("Couldn't allocate memory for undo");
  62
  63     // Save the stack.
  64     memcpy (undo->stack, base, undo->stackSize);
  65
  66     // Are we diffing against the previous undo record,
  67     // or against the initial gamefile state?
  68     if (gUndo == NULL)
  69     {
  70         // We're diffing against the gamefile.
  71         for ( ; addr < gExtStart ; addr += 256, ++slot)
  72         {
  73             if (memcmp (gRom + addr, gRam + addr, 256) != 0)
  74             {
  75                 // We need to save this page.
  76                 git_uint8 * page = malloc(256);
  77                 if (page == NULL)
  78                     fatalError ("Couldn't allocate memory for undo");
  79
  80                 memcpy (page, gRam + addr, 256);
  81                 undo->memoryMap[slot] = page;
  82                 totalSize += 256;
  83             }
  84             else
  85             {
  86                 // We don't need to save this page.
  87                 // Just make it point into ROM.
  88                 undo->memoryMap[slot] = gRom + addr;
  89             }
  90         }
  91
  92         // If the memory map has been extended, save the exended area
  93         for (addr = gExtStart ; addr < gEndMem ; addr += 256, ++slot)
  94         {
  95             git_uint8 * page = malloc(256);
  96             if (page == NULL)
  97                 fatalError ("Couldn't allocate memory for undo");
  98
  99             memcpy (page, gRam + addr, 256);
 100             undo->memoryMap[slot] = page;
 101             totalSize += 256;
 102         }
 103     }
 104     else
 105     {
 106         // We're diffing against the most recent undo record.
 107         git_uint32 endMem = (gUndo->endMem < gEndMem) ? gUndo->endMem : gEndMem;
 108         for ( ; addr < endMem ; addr += 256, ++slot)
 109         {
 110             if (memcmp (gUndo->memoryMap [slot], gRam + addr, 256) != 0)
 111             {
 112                 // We need to save this page.
 113                 git_uint8 * page = malloc(256);
 114                 memcpy (page, gRam + addr, 256);
 115                 undo->memoryMap[slot] = page;
 116                 totalSize += 256;
 117             }
 118             else
 119             {
 120                 // We don't need to save this page. Just copy
 121                 // the pointer from the previous undo record.
 122                 undo->memoryMap[slot] = gUndo->memoryMap[slot];
 123             }
 124         }
 125
 126         // If the memory map has been extended, save the exended area
 127         for (addr = endMem ; addr < gEndMem ; addr += 256, ++slot)
 128         {
 129             git_uint8 * page = malloc(256);
 130             if (page == NULL)
 131                 fatalError ("Couldn't allocate memory for undo");
 132
 133             memcpy (page, gRam + addr, 256);
 134             undo->memoryMap[slot] = page;
 135             totalSize += 256;
 136         }
 137     }
 138
 139     // Save the heap.
 140     if (heap_get_summary (&(undo->heapSize), &(undo->heap)))
 141         fatalError ("Couldn't get heap summary");
 142     totalSize += undo->heapSize * 4;
 143
 144     // Link this record into the undo list.
 145
 146     undo->prev = gUndo;
 147     if (gUndo)
 148         gUndo->next = undo;
 149
 150     gUndo = undo;
 151     gUndoSize += totalSize;
 152
 153     // Delete old records until we have enough free space.
 154     reserveSpace (0);
 155
 156     // And we're done.
 157     return 0;
 158 }
 159
 160 int restoreUndo (git_sint32* base, git_uint32 protectPos, git_uint32 protectSize)
 161 {
 162     if (gUndo == NULL)
 163     {
 164         // Nothing to undo!
 165         return 1;
 166     }
 167     else
 168     {
 169         UndoRecord * undo = gUndo;
 170
 171         git_uint32 addr = gRamStart;     // Address in glulx memory.
 172         MemoryMap map = undo->memoryMap; // Glulx memory map.
 173
 174         // Restore the size of the memory map
 175         heap_clear ();
 176         resizeMemory (undo->endMem, 1);
 177
 178         // Restore the stack.
 179         memcpy (base, undo->stack, undo->stackSize);
 180         gStackPointer = base + (undo->stackSize / sizeof(git_sint32));
 181
 182         // Restore the contents of RAM.
 183
 184         if (protectSize > 0 && protectPos < gEndMem)
 185         {
 186             for ( ; addr < (protectPos & ~0xff) ; addr += 256, ++map)
 187                 memcpy (gRam + addr, *map, 256);
 188
 189             memcpy (gRam + addr, *map, protectPos & 0xff);
 190             protectSize += protectPos & 0xff;
 191
 192             while (protectSize > 256)
 193                 addr += 256, ++map, protectSize -= 256;
 194
 195             if (addr < gEndMem)
 196             {
 197                 memcpy (gRam + addr + protectSize,
 198                         *map + protectSize,
 199                         256 - protectSize);
 200             }
 201             addr += 256, ++map;
 202         }
 203
 204         for ( ; addr < gEndMem ; addr += 256, ++map)
 205             memcpy (gRam + addr, *map, 256);
 206
 207         // Restore the heap.
 208         if (heap_apply_summary (undo->heapSize, undo->heap))
 209             fatalError ("Couldn't apply heap summary");
 210
 211         // Delete the undo record.
 212
 213         gUndo = undo->prev;
 214         deleteRecord (undo);
 215
 216         if (gUndo)
 217             gUndo->next = NULL;
 218         else
 219             assert (gUndoSize == 0);
 220
 221         // And we're done.
 222         return 0;
 223     }
 224 }
 225
 226 void resetUndo ()
 227 {
 228     reserveSpace (gMaxUndoSize);
 229     assert (gUndo == NULL);
 230     assert (gUndoSize == 0);
 231 }
 232
 233 void shutdownUndo ()
 234 {
 235     resetUndo();
 236 }
 237
 238 static void reserveSpace (git_uint32 n)
 239 {
 240     UndoRecord * u = gUndo;
 241     if (u == NULL)
 242         return;
 243
 244     // Find the oldest undo record.
 245
 246     while (u->prev)
 247         u = u->prev;
 248
 249     // Delete records until we've freed up the required amount of space.
 250
 251     while (gUndoSize + n > gMaxUndoSize)
 252     {
 253         if (u->next)
 254         {
 255             assert (u->next->prev == u);
 256             u = u->next;
 257
 258             deleteRecord (u->prev);
 259             u->prev = NULL;
 260         }
 261         else
 262         {
 263             assert (u == gUndo);
 264             gUndo = NULL;
 265
 266             deleteRecord (u);
 267             assert (gUndoSize == 0);
 268             break;
 269         }
 270     }
 271 }
 272
 273 static void deleteRecord (UndoRecord * u)
 274 {
 275     git_uint32 addr = gRamStart; // Address in glulx memory.
 276     git_uint32 slot = 0;         // Slot in our memory map.
 277
 278     // Zero out all the slots which are duplicates
 279     // of pages held in older undo records.
 280
 281     if (u->prev)
 282     {
 283         // We're diffing against the previous undo record.
 284         while (addr < u->endMem && addr < u->prev->endMem)
 285         {
 286             if (u->memoryMap [slot] == u->prev->memoryMap [slot])
 287                 u->memoryMap [slot] = NULL;
 288             addr += 256, ++slot;
 289         }
 290     }
 291     else
 292     {
 293         // We're diffing against the gamefile.
 294         while (addr < u->endMem && addr < gExtStart)
 295         {
 296             if (u->memoryMap [slot] == (gRom + addr))
 297                 u->memoryMap [slot] = NULL;
 298             addr += 256, ++slot;
 299         }
 300     }
 301
 302     // Zero out all the slots which are duplicates
 303     // of newer undo records.
 304
 305     if (u->next)
 306     {
 307         addr = gRamStart;
 308         slot = 0;
 309
 310         while (addr < u->endMem && addr < u->next->endMem)
 311         {
 312             if (u->memoryMap [slot] == u->next->memoryMap [slot])
 313                 u->memoryMap [slot] = NULL;
 314             addr += 256, ++slot;
 315         }
 316     }
 317
 318     // Free all the slots which are owned by this record only.
 319
 320     addr = gRamStart;
 321     slot = 0;
 322     while (addr < u->endMem)
 323     {
 324         if (u->memoryMap [slot])
 325         {
 326             free ((void*) u->memoryMap [slot]);
 327             gUndoSize -= 256;
 328         }
 329         addr += 256, ++slot;
 330     }
 331
 332     // Free the memory map itself.
 333     free ((void*) u->memoryMap);
 334     gUndoSize -= sizeof(MemoryPage*) * (u->endMem - gRamStart) / 256;
 335
 336     // Free the stack.
 337     free (u->stack);
 338     gUndoSize -= u->stackSize;
 339
 340     // Free the heap.
 341     free (u->heap);
 342     gUndoSize -= u->heapSize * 4;
 343
 344     // Finally, free the record.
 345     free (u);
 346     gUndoSize -= sizeof(UndoRecord);
 347 }