From 9ceb83972adc62aff28618c196f0a473fb85b1a0 Mon Sep 17 00:00:00 2001 From: Paul Gilbert Date: Sun, 14 Apr 2019 21:41:16 -0700 Subject: GLK: GLULXE: Added heap methods --- engines/glk/glulxe/glulxe.cpp | 6 +- engines/glk/glulxe/glulxe.h | 81 +++++++++- engines/glk/glulxe/glulxe_types.h | 8 + engines/glk/glulxe/heap.cpp | 322 ++++++++++++++++++++++++++++++++++++++ engines/glk/module.mk | 1 + 5 files changed, 413 insertions(+), 5 deletions(-) create mode 100644 engines/glk/glulxe/heap.cpp diff --git a/engines/glk/glulxe/glulxe.cpp b/engines/glk/glulxe/glulxe.cpp index 1f05b9432a..d16ecfb8cc 100644 --- a/engines/glk/glulxe/glulxe.cpp +++ b/engines/glk/glulxe/glulxe.cpp @@ -35,10 +35,12 @@ Glulxe::Glulxe(OSystem *syst, const GlkGameDescription &gameDesc) : GlkAPI(syst, startfuncaddr(0), checksum(0), stackptr(0), frameptr(0), pc(0), prevpc(0), origstringtable(0), stringtable(0), valstackbase(0), localsbase(0), endmem(0), protectstart(0), protectend(0), stream_char_handler(nullptr), stream_unichar_handler(nullptr), - // Accel + // accel classes_table(0), indiv_prop_start(0), class_metaclass(0), object_metaclass(0), routine_metaclass(0), string_metaclass(0), self(0), num_attr_bytes(0), cpv__start(0), - accelentries(nullptr) { + accelentries(nullptr), + // heap + heap_start(0), alloc_count(0), heap_head(nullptr), heap_tail(nullptr) { g_vm = this; } diff --git a/engines/glk/glulxe/glulxe.h b/engines/glk/glulxe/glulxe.h index 2eed876ffe..eacc51fd56 100644 --- a/engines/glk/glulxe/glulxe.h +++ b/engines/glk/glulxe/glulxe.h @@ -80,6 +80,34 @@ public: accelentry_t **accelentries; /**@}*/ + + /** + * \defgroup heap fields + * @{ + */ + + uint heap_start = 0; ///< zero for inactive heap + int alloc_count = 0; + + /* The heap_head/heap_tail is a doubly-linked list of blocks, both + free and allocated. It is kept in address order. It should be + complete -- that is, the first block starts at heap_start, and each + block ends at the beginning of the next block, until the last one, + which ends at endmem. + + (Heap_start is never the same as end_mem; if there is no heap space, + then the heap is inactive and heap_start is zero.) + + Adjacent free blocks may be merged at heap_alloc() time. + + ### To make alloc more efficient, we could keep a separate + free-list. To make free more efficient, we could keep a hash + table of allocations. + */ + heapblock_t *heap_head = NULL; + heapblock_t *heap_tail = NULL; + + /**@}*/ protected: /** * \defgroup glkop fields @@ -370,14 +398,61 @@ public: * \defgroup Heap access methods * @{ */ + + /** + * Set the heap state to inactive, and free the block lists. This is called when the game + * starts or restarts. + */ void heap_clear(void); - int heap_is_active(void); - uint heap_get_start(void); + + /** + * Returns whether the heap is active. + */ + int heap_is_active() const; + + /** + * Returns the start address of the heap, or 0 if the heap is not active. + */ + uint heap_get_start() const; + + /** + * Allocate a block. If necessary, activate the heap and/or extend memory. This may not be + * available at all; #define FIXED_MEMSIZE if you want the interpreter to unconditionally refuse. + * Returns the memory address of the block, or 0 if the operation failed. + */ uint heap_alloc(uint len); + + /** + * Free a heap block. If necessary, deactivate the heap. + */ void heap_free(uint addr); + + /** + * Create an array of words, in the VM serialization format: + * + * heap_start + * alloc_count + * addr of first block + * len of first block + * ... + * + * (Note that these are uint values -- native byte ordering. Also, the blocks will be in address order, + * which is a stricter guarantee than the VM specifies; that'll help in heap_apply_summary().) + * + * If the heap is inactive, store NULL. Return 0 for success; otherwise, the operation failed. + * + * The array returned in summary must be freed with glulx_free() after the caller uses it. + */ int heap_get_summary(uint *valcount, uint **summary); + + /** + * Given an array of words in the above format, set up the heap to contain it. As noted above, + * the caller must ensure that the blocks are in address order. When this is called, the heap + * must be inactive. + * + * Return 0 for success. Otherwise the operation failed (and, most likely, caused a fatal error). + */ int heap_apply_summary(uint valcount, uint *summary); - void heap_sanity_check(void); /**@}*/ diff --git a/engines/glk/glulxe/glulxe_types.h b/engines/glk/glulxe/glulxe_types.h index c6ce238460..96943d2f2a 100644 --- a/engines/glk/glulxe/glulxe_types.h +++ b/engines/glk/glulxe/glulxe_types.h @@ -348,6 +348,14 @@ typedef accelentry_struct accelentry_t; #define ACCEL_HASH_SIZE (511) +struct heapblock_struct { + uint addr; + uint len; + int isfree; + struct heapblock_struct *next; + struct heapblock_struct *prev; +}; +typedef heapblock_struct heapblock_t; } // End of namespace Glulxe } // End of namespace Glk diff --git a/engines/glk/glulxe/heap.cpp b/engines/glk/glulxe/heap.cpp new file mode 100644 index 0000000000..29d9405aca --- /dev/null +++ b/engines/glk/glulxe/heap.cpp @@ -0,0 +1,322 @@ +/* ScummVM - Graphic Adventure Engine + * + * ScummVM is the legal property of its developers, whose names + * are too numerous to list here. Please refer to the COPYRIGHT + * file distributed with this source distribution. + * + * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + */ + +#include "engines/glk/glulxe/glulxe.h" + +namespace Glk { +namespace Glulxe { + +void Glulxe::heap_clear() { + while (heap_head) { + heapblock_t *blo = heap_head; + heap_head = blo->next; + blo->next = nullptr; + blo->prev = nullptr; + glulx_free(blo); + } + heap_tail = nullptr; + + if (heap_start) { + uint res = change_memsize(heap_start, true); + if (res) + fatal_error_i("Unable to revert memory size when deactivating heap.", + heap_start); + } + + heap_start = 0; + alloc_count = 0; + /* heap_sanity_check(); */ +} + +int Glulxe::heap_is_active() const { + return (heap_start != 0); +} + +uint Glulxe::heap_get_start() const { + return heap_start; +} + +uint Glulxe::heap_alloc(uint len) { + heapblock_t *blo, *newblo; + +#ifdef FIXED_MEMSIZE + return 0; +#else /* FIXED_MEMSIZE */ + + if (len <= 0) + fatal_error("Heap allocation length must be positive."); + + blo = heap_head; + while (blo) { + if (blo->isfree && blo->len >= len) + break; + + if (!blo->isfree) { + blo = blo->next; + continue; + } + + if (!blo->next || !blo->next->isfree) { + blo = blo->next; + continue; + } + + /* This is a free block, but the next block in the list is also + free, so we "advance" by merging rather than by going to + blo->next. */ + newblo = blo->next; + blo->len += newblo->len; + if (newblo->next) { + blo->next = newblo->next; + newblo->next->prev = blo; + } + else { + blo->next = nullptr; + heap_tail = blo; + } + newblo->next = nullptr; + newblo->prev = nullptr; + glulx_free(newblo); + newblo = nullptr; + continue; + } + + if (!blo) { + /* No free area is visible on the list. Try extending memory. How + much? Double the heap size, or by 256 bytes, or by the memory + length requested -- whichever is greatest. */ + uint res; + uint extension; + uint oldendmem = endmem; + + extension = 0; + if (heap_start) + extension = endmem - heap_start; + if (extension < len) + extension = len; + if (extension < 256) + extension = 256; + /* And it must be rounded up to a multiple of 256. */ + extension = (extension + 0xFF) & (~(uint)0xFF); + + res = change_memsize(endmem+extension, true); + if (res) + return 0; + + /* If we just started the heap, note that. */ + if (heap_start == 0) + heap_start = oldendmem; + + if (heap_tail && heap_tail->isfree) { + /* Append the new space to the last block. */ + blo = heap_tail; + blo->len += extension; + } + else { + /* Append the new space to the block list, as a new block. */ + newblo = (heapblock_t *)glulx_malloc(sizeof(heapblock_t)); + if (!newblo) + fatal_error("Unable to allocate record for heap block."); + newblo->addr = oldendmem; + newblo->len = extension; + newblo->isfree = true; + newblo->next = nullptr; + newblo->prev = nullptr; + + if (!heap_tail) { + heap_head = newblo; + heap_tail = newblo; + } + else { + blo = heap_tail; + heap_tail = newblo; + blo->next = newblo; + newblo->prev = blo; + } + + blo = newblo; + newblo = nullptr; + } + + /* and continue forwards, using this new block (blo). */ + } + + /* Something strange happened. */ + if (!blo || !blo->isfree || blo->len < len) + return 0; + + /* We now have a free block of size len or longer. */ + + if (blo->len == len) { + blo->isfree = false; + } + else { + newblo = (heapblock_t *)glulx_malloc(sizeof(heapblock_t)); + if (!newblo) + fatal_error("Unable to allocate record for heap block."); + newblo->isfree = true; + newblo->addr = blo->addr + len; + newblo->len = blo->len - len; + blo->len = len; + blo->isfree = false; + newblo->next = blo->next; + if (newblo->next) + newblo->next->prev = newblo; + newblo->prev = blo; + blo->next = newblo; + if (heap_tail == blo) + heap_tail = newblo; + } + + alloc_count++; + /* heap_sanity_check(); */ + return blo->addr; + +#endif /* FIXED_MEMSIZE */ +} + +void Glulxe::heap_free(uint addr) { + heapblock_t *blo; + + for (blo = heap_head; blo; blo = blo->next) { + if (blo->addr == addr) + break; + }; + if (!blo || blo->isfree) + fatal_error_i("Attempt to free unallocated address from heap.", addr); + + blo->isfree = true; + alloc_count--; + if (alloc_count <= 0) { + heap_clear(); + } + + /* heap_sanity_check(); */ +} + +int Glulxe::heap_get_summary(uint *valcount, uint **summary) { + uint *arr, len, pos; + heapblock_t *blo; + + *valcount = 0; + *summary = nullptr; + + if (heap_start == 0) + return 0; + + len = 2 + 2*alloc_count; + arr = (uint *)glulx_malloc(len * sizeof(uint)); + if (!arr) + return 1; + + pos = 0; + arr[pos++] = heap_start; + arr[pos++] = alloc_count; + + for (blo = heap_head; blo; blo = blo->next) { + if (blo->isfree) + continue; + arr[pos++] = blo->addr; + arr[pos++] = blo->len; + } + + if (pos != len) + fatal_error("Wrong number of active blocks in heap"); + + *valcount = len; + *summary = arr; + return 0; +} + +int Glulxe::heap_apply_summary(uint valcount, uint *summary) { + uint lx, jx, lastend; + + if (heap_start) + fatal_error("Heap active when heap_apply_summary called"); + + if (valcount == 0 || summary == nullptr) + return 0; + if (valcount == 2 && summary[0] == 0 && summary[1] == 0) + return 0; + +#ifdef FIXED_MEMSIZE + return 1; +#else /* FIXED_MEMSIZE */ + + lx = 0; + heap_start = summary[lx++]; + alloc_count = summary[lx++]; + + for (jx=lx; jx+2= summary[jx+2]) + fatal_error("Heap block summary is out of order."); + } + + lastend = heap_start; + + while (lx < valcount || lastend < endmem) { + heapblock_t *blo; + + blo = (heapblock_t *)glulx_malloc(sizeof(heapblock_t)); + if (!blo) + fatal_error("Unable to allocate record for heap block."); + + if (lx >= valcount) { + blo->addr = lastend; + blo->len = endmem - lastend; + blo->isfree = true; + } else { + if (lastend < summary[lx]) { + blo->addr = lastend; + blo->len = summary[lx] - lastend; + blo->isfree = true; + } else { + blo->addr = summary[lx++]; + blo->len = summary[lx++]; + blo->isfree = false; + } + } + + blo->prev = nullptr; + blo->next = nullptr; + + if (!heap_head) { + heap_head = blo; + heap_tail = blo; + } + else { + heap_tail->next = blo; + blo->prev = heap_tail; + heap_tail = blo; + } + + lastend = blo->addr + blo->len; + } + + /* heap_sanity_check(); */ + + return 0; +#endif /* FIXED_MEMSIZE */ +} + +} // End of namespace Glulxe +} // End of namespace Glk diff --git a/engines/glk/module.mk b/engines/glk/module.mk index f1dcd84d72..669f81168e 100644 --- a/engines/glk/module.mk +++ b/engines/glk/module.mk @@ -65,6 +65,7 @@ MODULE_OBJS := \ glulxe/gestalt.o \ glulxe/glkop.o \ glulxe/glulxe.o \ + glulxe/heap.o \ magnetic/detection.o \ magnetic/magnetic.o \ scott/detection.o \ -- cgit v1.2.3