1 /* ScummVM - Graphic Adventure Engine
2 *
3 * ScummVM is the legal property of its developers, whose names
4 * are too numerous to list here. Please refer to the COPYRIGHT
5 * file distributed with this source distribution.
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20 *
21 */
22
23 #include "glk/glulx/glulx.h"
24
25 namespace Glk {
26 namespace Glulx {
27
28 enum serop {
29 serop_KeyIndirect = 0x01,
30 serop_ZeroKeyTerminates = 0x02,
31 serop_ReturnIndex = 0x04
32 };
33
linear_search(uint key,uint keysize,uint start,uint structsize,uint numstructs,uint keyoffset,uint options)34 uint Glulx::linear_search(uint key, uint keysize, uint start, uint structsize, uint numstructs,
35 uint keyoffset, uint options) {
36 unsigned char keybuf[4];
37 uint count;
38 uint ix;
39 int retindex = ((options & serop_ReturnIndex) != 0);
40 int zeroterm = ((options & serop_ZeroKeyTerminates) != 0);
41
42 fetchkey(keybuf, key, keysize, options);
43
44 for (count = 0; count < numstructs; count++, start += structsize) {
45 int match = true;
46 if (keysize <= 4) {
47 for (ix = 0; match && ix < keysize; ix++) {
48 if (Mem1(start + keyoffset + ix) != keybuf[ix])
49 match = false;
50 }
51 } else {
52 for (ix = 0; match && ix < keysize; ix++) {
53 if (Mem1(start + keyoffset + ix) != Mem1(key + ix))
54 match = false;
55 }
56 }
57
58 if (match) {
59 if (retindex)
60 return count;
61 else
62 return start;
63 }
64
65 if (zeroterm) {
66 match = true;
67 for (ix = 0; match && ix < keysize; ix++) {
68 if (Mem1(start + keyoffset + ix) != 0)
69 match = false;
70 }
71 if (match) {
72 break;
73 }
74 }
75 }
76
77 if (retindex)
78 return (uint) - 1;
79 else
80 return 0;
81 }
82
83
binary_search(uint key,uint keysize,uint start,uint structsize,uint numstructs,uint keyoffset,uint options)84 uint Glulx::binary_search(uint key, uint keysize, uint start, uint structsize, uint numstructs,
85 uint keyoffset, uint options) {
86 byte keybuf[4];
87 byte byte1, byte2;
88 uint top, bot, val, addr;
89 uint ix;
90 int retindex = ((options & serop_ReturnIndex) != 0);
91
92 fetchkey(keybuf, key, keysize, options);
93
94 bot = 0;
95 top = numstructs;
96 while (bot < top) {
97 int cmp = 0;
98 val = (top + bot) / 2;
99 addr = start + val * structsize;
100
101 if (keysize <= 4) {
102 for (ix = 0; (!cmp) && ix < keysize; ix++) {
103 byte1 = Mem1(addr + keyoffset + ix);
104 byte2 = keybuf[ix];
105 if (byte1 < byte2)
106 cmp = -1;
107 else if (byte1 > byte2)
108 cmp = 1;
109 }
110 } else {
111 for (ix = 0; (!cmp) && ix < keysize; ix++) {
112 byte1 = Mem1(addr + keyoffset + ix);
113 byte2 = Mem1(key + ix);
114 if (byte1 < byte2)
115 cmp = -1;
116 else if (byte1 > byte2)
117 cmp = 1;
118 }
119 }
120
121 if (!cmp) {
122 if (retindex)
123 return val;
124 else
125 return addr;
126 }
127
128 if (cmp < 0) {
129 bot = val + 1;
130 } else {
131 top = val;
132 }
133 }
134
135 if (retindex)
136 return (uint) - 1;
137 else
138 return 0;
139 }
140
linked_search(uint key,uint keysize,uint start,uint keyoffset,uint nextoffset,uint options)141 uint Glulx::linked_search(uint key, uint keysize, uint start, uint keyoffset, uint nextoffset, uint options) {
142 unsigned char keybuf[4];
143 uint ix;
144 uint val;
145 int zeroterm = ((options & serop_ZeroKeyTerminates) != 0);
146
147 fetchkey(keybuf, key, keysize, options);
148
149 while (start != 0) {
150 int match = true;
151 if (keysize <= 4) {
152 for (ix = 0; match && ix < keysize; ix++) {
153 if (Mem1(start + keyoffset + ix) != keybuf[ix])
154 match = false;
155 }
156 } else {
157 for (ix = 0; match && ix < keysize; ix++) {
158 if (Mem1(start + keyoffset + ix) != Mem1(key + ix))
159 match = false;
160 }
161 }
162
163 if (match) {
164 return start;
165 }
166
167 if (zeroterm) {
168 match = true;
169 for (ix = 0; match && ix < keysize; ix++) {
170 if (Mem1(start + keyoffset + ix) != 0)
171 match = false;
172 }
173 if (match) {
174 break;
175 }
176 }
177
178 val = start + nextoffset;
179 start = Mem4(val);
180 }
181
182 return 0;
183 }
184
fetchkey(unsigned char * keybuf,uint key,uint keysize,uint options)185 void Glulx::fetchkey(unsigned char *keybuf, uint key, uint keysize, uint options) {
186 uint ix;
187
188 if (options & serop_KeyIndirect) {
189 if (keysize <= 4) {
190 for (ix = 0; ix < keysize; ix++)
191 keybuf[ix] = Mem1(key + ix);
192 }
193 } else {
194 switch (keysize) {
195 case 4:
196 Write4(keybuf, key);
197 break;
198 case 2:
199 Write2(keybuf, key);
200 break;
201 case 1:
202 Write1(keybuf, key);
203 break;
204 default:
205 fatal_error("Direct search key must hold one, two, or four bytes.");
206 }
207 }
208 }
209
210 } // End of namespace Glulx
211 } // End of namespace Glk
212