GLK: GLULXE: Add search methods

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 \