Start of image cache implementation... breaks image functionality.
[rodin/chimara.git] / interpreters / glulxe / search.c
1 /* search.c: Glulxe code for built-in search opcodes
2     Designed by Andrew Plotkin <erkyrath@eblong.com>
3     http://eblong.com/zarf/glulx/index.html
4 */
5
6 #include "glk.h"
7 #include "glulxe.h"
8 #include "opcodes.h"
9
10 #define serop_KeyIndirect (0x01)
11 #define serop_ZeroKeyTerminates (0x02)
12 #define serop_ReturnIndex (0x04)
13 /* ### KeyZeroBounded? variants? */
14 /* ### LowerBoundKey? */
15
16 /* In general, these search functions look through a bunch of structures
17    in memory, searching for one whose key (a fixed-size sequence of bytes
18    within the structure) matches a given key. The result can indicate a
19    particular structure within the bunch, or it can be NULL ("not found".)
20
21    Any or all of these options can be applied:
22
23    KeyIndirect: If this is true, the key argument is taken to be the
24    start of an array of bytes in memory (whose length is keysize).
25    If it is false, the key argument contains the key itself. In
26    this case, keysize *must* be 1, 2, or 4. The key is stored in the
27    lower bytes of the key argument, big-endian. (The upper bytes are
28    ignored.)
29
30    ZeroKeyTerminates: If this is true, when the search reaches a struct
31    whose key is all zeroes, the search terminates (and returns NULL).
32    If the searched-for key happens to also be zeroes, the key-match
33    (returning the struct) takes precedence over the zero-match (returning
34    NULL.)
35
36    ReturnIndex: If this is false, the return value is the memory address
37    of the matching struct, or 0 to indicate NULL. If true, the return value
38    is the array index of the matching struct, or -1 to indicate NULL. 
39 */
40
41 static void fetchkey(unsigned char *keybuf, glui32 key, glui32 keysize, 
42   glui32 options);
43
44 /* linear_search():
45    An array of data structures is stored in memory, beginning at start,
46    each structure being structsize bytes. Within each struct, there is
47    a key value keysize bytes long, starting at position keyoffset (from
48    the start of the structure.) Search through these in order. If one
49    is found whose key matches, return it. If numstructs are searched
50    with no result, return NULL.
51    
52    numstructs may be -1 (0xFFFFFFFF) to indicate no upper limit to the
53    number of structures to search. The search will continue until a match
54    is found, or (if ZeroKeyTerminates is set) a zero key.
55
56    The KeyIndirect, ZeroKeyTerminates, and ReturnIndex options may be
57    used.
58 */
59 glui32 linear_search(glui32 key, glui32 keysize, 
60   glui32 start, glui32 structsize, glui32 numstructs, 
61   glui32 keyoffset, glui32 options)
62 {
63   unsigned char keybuf[4];
64   glui32 count;
65   int ix;
66   int retindex = ((options & serop_ReturnIndex) != 0);
67   int zeroterm = ((options & serop_ZeroKeyTerminates) != 0);
68
69   fetchkey(keybuf, key, keysize, options);
70
71   for (count=0; count<numstructs; count++, start+=structsize) {
72     int match = TRUE;
73     if (keysize <= 4) {
74       for (ix=0; match && ix<keysize; ix++) {
75         if (Mem1(start + keyoffset + ix) != keybuf[ix])
76           match = FALSE;
77       }
78     }
79     else {
80       for (ix=0; match && ix<keysize; ix++) {
81         if (Mem1(start + keyoffset + ix) != Mem1(key + ix))
82           match = FALSE;
83       }
84     }
85
86     if (match) {
87       if (retindex)
88         return count;
89       else
90         return start;
91     }
92
93     if (zeroterm) {
94       match = TRUE;
95       for (ix=0; match && ix<keysize; ix++) {
96         if (Mem1(start + keyoffset + ix) != 0)
97           match = FALSE;
98       }
99       if (match) {
100         break;
101       }
102     }
103   }
104   
105   if (retindex)
106     return -1;
107   else
108     return 0;
109 }
110
111 /* binary_search():
112    An array of data structures is in memory, as above. However, the
113    structs must be stored in forward order of their keys (taking each key
114    to be a multibyte unsigned integer.) There can be no duplicate keys. 
115    numstructs must indicate the exact length of the array; it cannot
116    be -1.
117
118    The KeyIndirect and ReturnIndex options may be used.
119 */
120 glui32 binary_search(glui32 key, glui32 keysize, 
121   glui32 start, glui32 structsize, glui32 numstructs, 
122   glui32 keyoffset, glui32 options)
123 {
124   unsigned char keybuf[4];
125   unsigned char byte, byte2;
126   glui32 top, bot, val, addr;
127   int ix;
128   int retindex = ((options & serop_ReturnIndex) != 0);
129
130   fetchkey(keybuf, key, keysize, options);
131   
132   bot = 0;
133   top = numstructs;
134   while (bot < top) {
135     int cmp = 0;
136     val = (top+bot) / 2;
137     addr = start + val * structsize;
138
139     if (keysize <= 4) {
140       for (ix=0; (!cmp) && ix<keysize; ix++) {
141         byte = Mem1(addr + keyoffset + ix);
142         byte2 = keybuf[ix];
143         if (byte < byte2)
144           cmp = -1;
145         else if (byte > byte2)
146           cmp = 1;
147       }
148     }
149     else {
150       for (ix=0; (!cmp) && ix<keysize; ix++) {
151         byte = Mem1(addr + keyoffset + ix);
152         byte2 = Mem1(key + ix);
153         if (byte < byte2)
154           cmp = -1;
155         else if (byte > byte2)
156           cmp = 1;
157       }
158     }
159
160     if (!cmp) {
161       if (retindex)
162         return val;
163       else
164         return addr;
165     }
166
167     if (cmp < 0) {
168       bot = val+1;
169     }
170     else {
171       top = val;
172     }
173   }
174
175   if (retindex)
176     return -1;
177   else
178     return 0;
179 }
180
181 /* linked_search():
182    The structures may be anywhere in memory, in any order. They are
183    linked by a four-byte address field, which is found in each struct
184    at position nextoffset. If this field contains zero, it indicates
185    the end of the linked list.
186
187    The KeyIndirect and ZeroKeyTerminates options may be used.
188 */
189 glui32 linked_search(glui32 key, glui32 keysize, 
190   glui32 start, glui32 keyoffset, glui32 nextoffset, glui32 options)
191 {
192   unsigned char keybuf[4];
193   int ix;
194   glui32 val;
195   int zeroterm = ((options & serop_ZeroKeyTerminates) != 0);
196
197   fetchkey(keybuf, key, keysize, options);
198
199   while (start != 0) {
200     int match = TRUE;
201     if (keysize <= 4) {
202       for (ix=0; match && ix<keysize; ix++) {
203         if (Mem1(start + keyoffset + ix) != keybuf[ix])
204           match = FALSE;
205       }
206     }
207     else {
208       for (ix=0; match && ix<keysize; ix++) {
209         if (Mem1(start + keyoffset + ix) != Mem1(key + ix))
210           match = FALSE;
211       }
212     }
213
214     if (match) {
215       return start;
216     }
217
218     if (zeroterm) {
219       match = TRUE;
220       for (ix=0; match && ix<keysize; ix++) {
221         if (Mem1(start + keyoffset + ix) != 0)
222           match = FALSE;
223       }
224       if (match) {
225         break;
226       }
227     }
228     
229     val = start + nextoffset;
230     start = Mem4(val);
231   }
232
233   return 0;
234 }
235
236 /* fetchkey():
237    This massages the key into a form that's easier to handle. When it
238    returns, the key will be stored in keybuf if keysize <= 4; otherwise,
239    it will be in memory.
240 */
241 static void fetchkey(unsigned char *keybuf, glui32 key, glui32 keysize, 
242   glui32 options)
243 {
244   int ix;
245
246   if (options & serop_KeyIndirect) {
247     if (keysize <= 4) {
248       for (ix=0; ix<keysize; ix++)
249         keybuf[ix] = Mem1(key+ix);
250     }
251   }
252   else {
253     switch (keysize) {
254     case 4:
255       Write4(keybuf, key);
256       break;
257     case 2:
258       Write2(keybuf, key);
259       break;
260     case 1:
261       Write1(keybuf, key);
262       break;
263     default:
264       fatal_error("Direct search key must hold one, two, or four bytes.");
265     }
266   }
267 }