1 /* -*-C-*-
2 ********************************************************************************
3 *
4 * File: states.c (Formerly states.c)
5 * Description: Representations of search states
6 * Author: Mark Seaman, OCR Technology
7 * Created: Wed May 16 15:49:34 1990
8 * Modified: Mon Jun 17 17:54:41 1991 (Mark Seaman) marks@hpgrlt
9 * Language: C
10 * Package: N/A
11 * Status: Experimental (Do Not Distribute)
12 *
13 * (c) Copyright 1990, Hewlett-Packard Company.
14 ** Licensed under the Apache License, Version 2.0 (the "License");
15 ** you may not use this file except in compliance with the License.
16 ** You may obtain a copy of the License at
17 ** http://www.apache.org/licenses/LICENSE-2.0
18 ** Unless required by applicable law or agreed to in writing, software
19 ** distributed under the License is distributed on an "AS IS" BASIS,
20 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
21 ** See the License for the specific language governing permissions and
22 ** limitations under the License.
23 *
24 *********************************************************************************/
25 /*----------------------------------------------------------------------
26 I n c l u d e s
27 ----------------------------------------------------------------------*/
28 #include "states.h"
29 #include "structures.h"
30 #include "tordvars.h"
31 #include "callcpp.h"
32
33 /*-------------------------------------------------------------------------
34 Variables
35 --------------------------------------------------------------------------*/
36 #define STATEBLOCK 100 /* Cells per block */
37 makestructure (newstate, free_state, printstate, STATE,
38 freestate, STATEBLOCK, "STATE", statecount);
39
40 /*----------------------------------------------------------------------
41 F u n c t i o n s
42 ----------------------------------------------------------------------*/
43 /**********************************************************************
44 * bin_to_chunks
45 *
46 * Convert a representation of the search state in "STATE" form to one
47 * in "SEARCH_STATE" form. Create the memory required to hold the
48 * resultant state value.
49 **********************************************************************/
bin_to_chunks(STATE * state,int num_joints)50 SEARCH_STATE bin_to_chunks(STATE *state, int num_joints) {
51 int x;
52 unsigned int mask;
53 int depth;
54 int pieces = 0;
55 SEARCH_STATE s;
56
57 s = memalloc (sizeof (int) * (ones_in_state (state, num_joints) + 1));
58
59 depth = 1;
60 mask = 1 << (num_joints - 1 - 32);
61 for (x = num_joints; x > 32; x--) {
62 if (state->part1 & mask) {
63 s[depth++] = pieces;
64 pieces = 0;
65 }
66 else {
67 pieces++;
68 }
69 mask >>= 1;
70 }
71
72 if (num_joints > 32)
73 mask = 1 << 31;
74 else
75 mask = 1 << (num_joints - 1);
76
77 while (x--) {
78 if (state->part2 & mask) {
79 s[depth++] = pieces;
80 pieces = 0;
81 }
82 else {
83 pieces++;
84 }
85 mask >>= 1;
86 }
87 s[0] = depth - 1;
88
89 return (s);
90 }
91
92
93 /**********************************************************************
94 * bin_to_pieces
95 *
96 * Convert the binary (bit vector) format of a search state to an array
97 * of piece counts. This array has a zero element after the last valid
98 * character.
99 **********************************************************************/
bin_to_pieces(STATE * state,int num_joints,PIECES_STATE pieces)100 void bin_to_pieces(STATE *state, int num_joints, PIECES_STATE pieces) {
101 int x;
102 unsigned int mask; /* Bit mask */
103 inT16 num_pieces = 0;
104 /* Preset mask */
105 if (tord_debug_8)
106 print_state ("bin_to_pieces = ", state, num_joints);
107
108 mask = ((num_joints > 32) ?
109 (1 << (num_joints - 1 - 32)) : (1 << (num_joints - 1)));
110
111 pieces[num_pieces] = 0;
112
113 for (x = num_joints - 1; x >= 0; x--) {
114 /* Iterate all bits */
115 pieces[num_pieces]++;
116
117 if ((x < 32) ? /* Test for 1 bit */
118 ((state->part2 & mask) ? TRUE : FALSE) :
119 ((state->part1 & mask) ? TRUE : FALSE)) {
120 pieces[++num_pieces] = 0;
121 if (tord_debug_8)
122 cprintf ("[%d]=%d ", num_pieces - 1, pieces[num_pieces - 1]);
123 }
124 /* Next mask value */
125 mask = ((mask == 1) ? (1 << 31) : (mask >> 1));
126 }
127 pieces[num_pieces]++;
128 pieces[++num_pieces] = 0;
129 ASSERT_HOST (num_pieces < MAX_NUM_CHUNKS + 2);
130 if (tord_debug_8)
131 new_line();
132 }
133
134
135 /**********************************************************************
136 * insert_new_chunk
137 *
138 * Add a new chunk division into this state vector at the location
139 * requested.
140 **********************************************************************/
insert_new_chunk(register STATE * state,register int index,register int num_joints)141 void insert_new_chunk(register STATE *state,
142 register int index,
143 register int num_joints) {
144 register unsigned int mask;
145 register unsigned int result;
146
147 index = (num_joints - index);
148 if (index < 32) {
149 mask = ~0;
150 mask <<= index;
151 result = (mask & state->part2) << 1;
152 result |= (~mask & state->part2);
153 state->part1 <<= 1;
154 if (state->part2 & 0x80000000)
155 state->part1 |= 1;
156 state->part2 = result;
157 }
158 else {
159 mask = ~0;
160 mask <<= index - 32;
161 result = (mask & state->part1) << 1;
162 result |= (~mask & state->part1);
163 state->part1 = result;
164 }
165 }
166
167
168 /**********************************************************************
169 * new_state
170 *
171 * Create a memory space for a new state variable. Set its initial
172 * value according to the parameters.
173 **********************************************************************/
new_state(STATE * oldstate)174 STATE *new_state(STATE *oldstate) {
175 STATE *this_state;
176
177 this_state = newstate ();
178 this_state->part1 = oldstate->part1;
179 this_state->part2 = oldstate->part2;
180 return (this_state);
181 }
182
183
184 /*********************************************************************
185 * ones_in_state
186 *
187 * Return the number of ones that are in this state.
188 **********************************************************************/
ones_in_state(STATE * state,int num_joints)189 int ones_in_state(STATE *state, int num_joints) {
190 inT8 num_ones = 0;
191 inT8 x;
192 unsigned int mask;
193
194 if (num_joints > 32) /* Preset mask */
195 mask = 1 << (num_joints - 1 - 32);
196 else
197 mask = 1 << (num_joints - 1);
198
199 for (x = num_joints - 1; x >= 0; x--) {
200 /* Iterate all bits */
201
202 if (x < 32)
203 num_ones += ((state->part2 & mask) ? 1 : 0);
204 else
205 num_ones += ((state->part1 & mask) ? 1 : 0);
206
207 if (mask == 1) /* Next mask value */
208 mask = 1 << 31;
209 else
210 mask >>= 1;
211 }
212
213 return (num_ones);
214 }
215
216
217 /**********************************************************************
218 * print_state
219 *
220 * Print out the current state variable on a line with a label.
221 **********************************************************************/
print_state(const char * label,STATE * state,int num_joints)222 void print_state(const char *label, STATE *state, int num_joints) {
223 int x;
224 unsigned int mask; /* Bit mask */
225
226 if (num_joints > 32) /* Preset mask */
227 mask = 1 << (num_joints - 1 - 32);
228 else
229 mask = 1 << (num_joints - 1);
230
231 cprintf ("%s ", label);
232
233 for (x = num_joints - 1; x >= 0; x--) {
234 /* Iterate all bits */
235
236 if (x < 32)
237 cprintf ("%d", ((state->part2 & mask) ? 1 : 0));
238 else
239 cprintf ("%d", ((state->part1 & mask) ? 1 : 0));
240 if (x % 4 == 0)
241 cprintf (" ");
242
243 if (mask == 1) /* Next mask value */
244 mask = 1 << 31;
245 else
246 mask >>= 1;
247 }
248
249 new_line();
250 }
251
252
253 /**********************************************************************
254 * set_n_ones
255 *
256 * Set the first n bits in a state.
257 **********************************************************************/
set_n_ones(STATE * state,int n)258 void set_n_ones(STATE *state, int n) {
259 if (n < 32) {
260 state->part2 = ~0;
261 state->part2 >>= 32 - n;
262 state->part1 = 0;
263 }
264 else {
265 state->part2 = ~0;
266 state->part1 = ~0;
267 state->part1 >>= 64 - n;
268 }
269 }
270
271
272 /**********************************************************************
273 * compare_states
274 *
275 * Compare the 2 states at the given blob index. Return 1 if the given
276 * blob is a fragment compared to reality, 2 if correct, 4 if a join,
277 * and 5 if both a join and a fragment.
278 * On return the blob index is set to the corresponding index in the
279 * correct string.
280 **********************************************************************/
compare_states(STATE * true_state,STATE * this_state,int * blob_index)281 int compare_states(STATE *true_state, STATE *this_state, int *blob_index) {
282 int blob_count; //number found
283 int true_index; //index of true blob
284 int index; //current
285 int result = 0; //return value
286 uinT32 mask;
287
288 if (true_state->part1 == this_state->part1
289 && true_state->part2 == this_state->part2)
290 return 2;
291 if (*blob_index == 0) {
292 if (bits_in_states > 32) {
293 for (mask = 1 << (bits_in_states - 33); mask != 0; mask >>= 1) {
294 if (this_state->part1 & mask) {
295 if (true_state->part1 & mask)
296 return 2;
297 else
298 return 1;
299 }
300 else if (true_state->part1 & mask)
301 return 4;
302 }
303 index = 31;
304 }
305 else
306 index = bits_in_states - 1;
307 for (mask = 1 << index; mask != 0; mask >>= 1) {
308 if (this_state->part2 & mask) {
309 if (true_state->part2 & mask)
310 return 2;
311 else
312 return 1;
313 }
314 else if (true_state->part2 & mask)
315 return 4;
316 }
317 return 2;
318 }
319 else {
320 blob_count = 0;
321 true_index = 0;
322 if (bits_in_states > 32) {
323 for (mask = 1 << (bits_in_states - 33); mask != 0; mask >>= 1) {
324 if (true_state->part1 & mask)
325 true_index++;
326 if (this_state->part1 & mask) {
327 blob_count++;
328 if (blob_count == *blob_index) {
329 if ((true_state->part1 & mask) == 0)
330 result = 1;
331 break;
332 }
333 }
334 }
335 if (blob_count == *blob_index) {
336 for (mask >>= 1; mask != 0; mask >>= 1) {
337 if (this_state->part1 & mask) {
338 if ((true_state->part1 & mask) && result == 0)
339 return 2;
340 else
341 return result | 1;
342 }
343 else if (true_state->part1 & mask)
344 result |= 4;
345 }
346 }
347 index = 31;
348 }
349 else
350 index = bits_in_states - 1;
351 mask = 1 << index;
352 if (blob_count < *blob_index) {
353 for (; mask != 0; mask >>= 1) {
354 if (true_state->part2 & mask)
355 true_index++;
356 if (this_state->part2 & mask) {
357 blob_count++;
358 if (blob_count == *blob_index) {
359 if ((true_state->part2 & mask) == 0)
360 result = 1;
361 break;
362 }
363 }
364 }
365 if (blob_count != *blob_index)
366 return 2;
367 mask >>= 1;
368 }
369 *blob_index = true_index;
370 for (; mask != 0; mask >>= 1) {
371 if (this_state->part2 & mask) {
372 if ((true_state->part2 & mask) && result == 0)
373 return 2;
374 else
375 return result | 1;
376 }
377 else if (true_state->part2 & mask)
378 result |= 4;
379 }
380 return result == 0 ? 2 : result;
381 }
382 }
383