diff options
| -rw-r--r-- | engines/glk/glulxe/glulxe.h | 55 | ||||
| -rw-r--r-- | engines/glk/glulxe/glulxe_types.h | 97 | ||||
| -rw-r--r-- | engines/glk/glulxe/search.cpp | 216 | ||||
| -rw-r--r-- | engines/glk/module.mk | 1 |
4 files changed, 312 insertions, 57 deletions
diff --git a/engines/glk/glulxe/glulxe.h b/engines/glk/glulxe/glulxe.h index 97a7c09179..5dac1444de 100644 --- a/engines/glk/glulxe/glulxe.h +++ b/engines/glk/glulxe/glulxe.h @@ -40,8 +40,8 @@ public: uint gamefile_start, gamefile_len; char *init_err, *init_err2; - unsigned char *memmap; - unsigned char *stack; + byte *memmap; + byte *stack; uint ramstart; uint endgamefile; @@ -247,6 +247,19 @@ protected: char *get_game_id(); /**@}*/ + + /** + * \defgroup search support methods + * @{ + */ + + /** + * This massages the key into a form that's easier to handle. When it returns, the key will + * be stored in keybuf if keysize <= 4; otherwise, it will be in memory. + */ + void fetchkey(unsigned char *keybuf, uint key, uint keysize, uint options); + + /**@}*/ public: /** * Constructor @@ -511,15 +524,39 @@ public: * @{ */ - uint linear_search(uint key, uint keysize, - uint start, uint structsize, uint numstructs, + + /** + * An array of data structures is stored in memory, beginning at start, each structure being structsize bytes. + * Within each struct, there is a key value keysize bytes long, starting at position keyoffset (from + * the start of the structure.) Search through these in order. If one is found whose key matches, return it. + * If numstructs are searched with no result, return NULL. + * + * numstructs may be -1 (0xFFFFFFFF) to indicate no upper limit to the number of structures to search. + * The search will continue until a match is found, or (if ZeroKeyTerminates is set) a zero key. + * + * The KeyIndirect, ZeroKeyTerminates, and ReturnIndex options may be used. + */ + uint linear_search(uint key, uint keysize, uint start, uint structsize, uint numstructs, uint keyoffset, uint options); - uint binary_search(uint key, uint keysize, - uint start, uint structsize, uint numstructs, + + /** + * An array of data structures is in memory, as above. However, the structs must be stored in forward + * order of their keys (taking each key to be a multibyte unsigned integer.) There can be no duplicate keys. + * numstructs must indicate the exact length of the array; it cannot be -1. + * + * The KeyIndirect and ReturnIndex options may be used. + */ + uint binary_search(uint key, uint keysize, uint start, uint structsize, uint numstructs, uint keyoffset, uint options); - uint linked_search(uint key, uint keysize, - uint start, uint keyoffset, uint nextoffset, - uint options); + + /** + * The structures may be anywhere in memory, in any order. They are linked by a four-byte address field, + * which is found in each struct at position nextoffset. If this field contains zero, it indicates + * the end of the linked list. + * + * The KeyIndirect and ZeroKeyTerminates options may be used. + */ + uint linked_search(uint key, uint keysize, uint start, uint keyoffset, uint nextoffset, uint options); /**@}*/ diff --git a/engines/glk/glulxe/glulxe_types.h b/engines/glk/glulxe/glulxe_types.h index 8c99d9047d..50b62a0f15 100644 --- a/engines/glk/glulxe/glulxe_types.h +++ b/engines/glk/glulxe/glulxe_types.h @@ -26,53 +26,54 @@ #include "common/scummsys.h" namespace Glk { - namespace Glulxe { +namespace Glulxe { - class Glulxe; +class Glulxe; - /** - * Comment this definition to turn off memory-address checking. With verification on, - * all reads and writes to main memory will be checked to ensure they're in range. - * This is slower, but prevents malformed game files from crashing the interpreter. - */ +/** + * Comment this definition to turn off memory-address checking. With verification on, + * all reads and writes to main memory will be checked to ensure they're in range. + * This is slower, but prevents malformed game files from crashing the interpreter. + */ #define VERIFY_MEMORY_ACCESS (1) - /** - * Uncomment this definition to permit an exception for memory-address checking for @glk and @copy - * opcodes that try to write to memory address 0. This was a bug in old Superglus-built game files. - */ - /* #define TOLERATE_SUPERGLUS_BUG (1) */ - - /** - * Uncomment this definition to turn on Glulx VM profiling. In this mode, all function calls are timed, - * and the timing information is written to a data file called "profile-raw". - * (Build note: on Linux, glibc may require you to also define _BSD_SOURCE or _DEFAULT_SOURCE or both - * for the timeradd() macro.) - */ - /* #define VM_PROFILING (1) */ - - /** - * Uncomment this definition to turn on the Glulx debugger. You should only do this when debugging - * facilities are desired; it slows down the interpreter. If you do, you will need to build with libxml2; - * see the Makefile. - */ - /* #define VM_DEBUGGER (1) */ - - /** - * Comment this definition to turn off floating-point support. You might need to do this if you are building - * on a very limited platform with no math library. */ +/** + * Uncomment this definition to permit an exception for memory-address checking for @glk and @copy + * opcodes that try to write to memory address 0. This was a bug in old Superglus-built game files. + */ +/* #define TOLERATE_SUPERGLUS_BUG (1) */ + +/** + * Uncomment this definition to turn on Glulx VM profiling. In this mode, all function calls are timed, + * and the timing information is written to a data file called "profile-raw". + * (Build note: on Linux, glibc may require you to also define _BSD_SOURCE or _DEFAULT_SOURCE or both + * for the timeradd() macro.) + */ +/* #define VM_PROFILING (1) */ + +/** + * Uncomment this definition to turn on the Glulx debugger. You should only do this when debugging + * facilities are desired; it slows down the interpreter. If you do, you will need to build with libxml2; + * see the Makefile. + */ +/* #define VM_DEBUGGER (1) */ + +/** + * Comment this definition to turn off floating-point support. You might need to do this if you are building + * on a very limited platform with no math library. + */ #define FLOAT_SUPPORT (1) - /** - * Comment this definition to not cache the original state of RAM in (real) memory. This saves some memory, - * but slows down save/restore/undo operations, which will have to read the original state off disk - * every time. - */ +/** + * Comment this definition to not cache the original state of RAM in (real) memory. This saves some memory, + * but slows down save/restore/undo operations, which will have to read the original state off disk + * every time. + */ #define SERIALIZE_CACHE_RAM (1) - /** - * Some macros to read and write integers to memory, always in big-endian format. - */ +/** + * Some macros to read and write integers to memory, always in big-endian format. + */ #define Read4(ptr) READ_BE_UINT32(ptr) #define Read2(ptr) READ_BE_UINT16(ptr) #define Read1(ptr) ((byte)(((byte *)(ptr))[0])) @@ -88,19 +89,19 @@ namespace Glk { #define VerifyW(adr, ln) (0) #endif /* VERIFY_MEMORY_ACCESS */ -#define Mem1(adr) (Verify(adr, 1), Read1(memmap+(adr))) -#define Mem2(adr) (Verify(adr, 2), Read2(memmap+(adr))) -#define Mem4(adr) (Verify(adr, 4), Read4(memmap+(adr))) +#define Mem1(adr) (Read1(memmap+(adr))) +#define Mem2(adr) (Read2(memmap+(adr))) +#define Mem4(adr) (Read4(memmap+(adr))) #define MemW1(adr, vl) (VerifyW(adr, 1), Write1(memmap+(adr), (vl))) #define MemW2(adr, vl) (VerifyW(adr, 2), Write2(memmap+(adr), (vl))) #define MemW4(adr, vl) (VerifyW(adr, 4), Write4(memmap+(adr), (vl))) - /** - * Macros to access values on the stack. These *must* be used with proper alignment! - * (That is, Stk4 and StkW4 must take addresses which are multiples of four, etc.) - * If the alignment rules are not followed, the program will see performance - * degradation or even crashes, depending on the machine CPU. - */ +/** + * Macros to access values on the stack. These *must* be used with proper alignment! + * (That is, Stk4 and StkW4 must take addresses which are multiples of four, etc.) + * If the alignment rules are not followed, the program will see performance + * degradation or even crashes, depending on the machine CPU. + */ #define Stk1(adr) \ (*((unsigned char *)(stack+(adr)))) #define Stk2(adr) \ diff --git a/engines/glk/glulxe/search.cpp b/engines/glk/glulxe/search.cpp new file mode 100644 index 0000000000..d2f1c85d68 --- /dev/null +++ b/engines/glk/glulxe/search.cpp @@ -0,0 +1,216 @@ +/* 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 { + +enum serop { + serop_KeyIndirect = 0x01, + serop_ZeroKeyTerminates = 0x02, + serop_ReturnIndex = 0x04 +}; + +uint Glulxe::linear_search(uint key, uint keysize, uint start, uint structsize, uint numstructs, + uint keyoffset, uint options) { + unsigned char keybuf[4]; + uint count; + uint ix; + int retindex = ((options & serop_ReturnIndex) != 0); + int zeroterm = ((options & serop_ZeroKeyTerminates) != 0); + + fetchkey(keybuf, key, keysize, options); + + for (count=0; count<numstructs; count++, start+=structsize) { + int match = true; + if (keysize <= 4) { + for (ix=0; match && ix<keysize; ix++) { + if (Mem1(start + keyoffset + ix) != keybuf[ix]) + match = false; + } + } + else { + for (ix=0; match && ix<keysize; ix++) { + if (Mem1(start + keyoffset + ix) != Mem1(key + ix)) + match = false; + } + } + + if (match) { + if (retindex) + return count; + else + return start; + } + + if (zeroterm) { + match = true; + for (ix=0; match && ix<keysize; ix++) { + if (Mem1(start + keyoffset + ix) != 0) + match = false; + } + if (match) { + break; + } + } + } + + if (retindex) + return (uint)-1; + else + return 0; +} + + +uint Glulxe::binary_search(uint key, uint keysize, uint start, uint structsize, uint numstructs, + uint keyoffset, uint options) { + byte keybuf[4]; + byte byte1, byte2; + uint top, bot, val, addr; + uint ix; + int retindex = ((options & serop_ReturnIndex) != 0); + + fetchkey(keybuf, key, keysize, options); + + bot = 0; + top = numstructs; + while (bot < top) { + int cmp = 0; + val = (top+bot) / 2; + addr = start + val * structsize; + + if (keysize <= 4) { + for (ix=0; (!cmp) && ix<keysize; ix++) { + byte1 = Mem1(addr + keyoffset + ix); + byte2 = keybuf[ix]; + if (byte1 < byte2) + cmp = -1; + else if (byte1 > byte2) + cmp = 1; + } + } + else { + for (ix=0; (!cmp) && ix<keysize; ix++) { + byte1 = Mem1(addr + keyoffset + ix); + byte2 = Mem1(key + ix); + if (byte1 < byte2) + cmp = -1; + else if (byte1 > byte2) + cmp = 1; + } + } + + if (!cmp) { + if (retindex) + return val; + else + return addr; + } + + if (cmp < 0) { + bot = val+1; + } + else { + top = val; + } + } + + if (retindex) + return (uint)-1; + else + return 0; +} + +uint Glulxe::linked_search(uint key, uint keysize, uint start, uint keyoffset, uint nextoffset, uint options) { + unsigned char keybuf[4]; + uint ix; + uint val; + int zeroterm = ((options & serop_ZeroKeyTerminates) != 0); + + fetchkey(keybuf, key, keysize, options); + + while (start != 0) { + int match = true; + if (keysize <= 4) { + for (ix=0; match && ix<keysize; ix++) { + if (Mem1(start + keyoffset + ix) != keybuf[ix]) + match = false; + } + } + else { + for (ix=0; match && ix<keysize; ix++) { + if (Mem1(start + keyoffset + ix) != Mem1(key + ix)) + match = false; + } + } + + if (match) { + return start; + } + + if (zeroterm) { + match = true; + for (ix=0; match && ix<keysize; ix++) { + if (Mem1(start + keyoffset + ix) != 0) + match = false; + } + if (match) { + break; + } + } + + val = start + nextoffset; + start = Mem4(val); + } + + return 0; +} + +void Glulxe::fetchkey(unsigned char *keybuf, uint key, uint keysize, uint options) { + uint ix; + + if (options & serop_KeyIndirect) { + if (keysize <= 4) { + for (ix=0; ix<keysize; ix++) + keybuf[ix] = Mem1(key+ix); + } + } + else { + switch (keysize) { + case 4: + Write4(keybuf, key); + break; + case 2: + Write2(keybuf, key); + break; + case 1: + Write1(keybuf, key); + break; + default: + fatal_error("Direct search key must hold one, two, or four bytes."); + } + } +} + +} // End of namespace Glulxe +} // End of namespace Glk diff --git a/engines/glk/module.mk b/engines/glk/module.mk index 6addf7efa2..e09a63ec0a 100644 --- a/engines/glk/module.mk +++ b/engines/glk/module.mk @@ -67,6 +67,7 @@ MODULE_OBJS := \ glulxe/glulxe.o \ glulxe/heap.o \ glulxe/operand.o \ + glulxe/search.o \ magnetic/detection.o \ magnetic/magnetic.o \ scott/detection.o \ |