Tesseract 3.02

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
states.cpp
Go to the documentation of this file.
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 "callcpp.h"
31
32 /*-------------------------------------------------------------------------
33 Variables
34 --------------------------------------------------------------------------*/
35 makestructure(newstate, free_state, STATE);
36
37 /*----------------------------------------------------------------------
38 F u n c t i o n s
39 ----------------------------------------------------------------------*/
49 SEARCH_STATE bin_to_chunks(STATE *state, int num_joints) {
50 int x;
51 unsigned int mask;
52 int depth;
53 int pieces = 0;
54 SEARCH_STATE s;
55
56 s = memalloc (sizeof (int) * (ones_in_state (state, num_joints) + 1));
57
58 depth = 1;
59 mask = 1 << (num_joints - 1 - 32);
60 for (x = num_joints; x > 32; x--) {
61 if (state->part1 & mask) {
62 s[depth++] = pieces;
63 pieces = 0;
64 }
65 else {
66 pieces++;
67 }
68 mask >>= 1;
69 }
70
71 if (num_joints > 32)
72 mask = 1 << 31;
73 else
74 mask = 1 << (num_joints - 1);
75
76 while (x--) {
77 if (state->part2 & mask) {
78 s[depth++] = pieces;
79 pieces = 0;
80 }
81 else {
82 pieces++;
83 }
84 mask >>= 1;
85 }
86 s[0] = depth - 1;
87
88 return (s);
89 }
90
91
99 void bin_to_pieces(STATE *state, int num_joints, PIECES_STATE pieces) {
100 int x;
101 unsigned int mask; /* Bit mask */
102 inT16 num_pieces = 0;
103 /* Preset mask */
104 mask = ((num_joints > 32) ?
105 (1 << (num_joints - 1 - 32)) : (1 << (num_joints - 1)));
106
107 pieces[num_pieces] = 0;
108
109 for (x = num_joints - 1; x >= 0; x--) {
110 /* Iterate all bits */
111 pieces[num_pieces]++;
112
113 if ((x < 32) ? /* Test for 1 bit */
114 ((state->part2 & mask) ? TRUE : FALSE) :
115 ((state->part1 & mask) ? TRUE : FALSE)) {
116 pieces[++num_pieces] = 0;
117 }
118 /* Next mask value */
119 mask = ((mask == 1) ? (1 << 31) : (mask >> 1));
120 }
121 pieces[num_pieces]++;
122 pieces[++num_pieces] = 0;
123 ASSERT_HOST (num_pieces < MAX_NUM_CHUNKS + 2);
124 }
125
126
133 void insert_new_chunk(register STATE *state,
134 register int index,
135 register int num_joints) {
136 register unsigned int mask;
137 register unsigned int result;
138
139 index = (num_joints - index);
140 if (index < 32) {
141 mask = ~0;
142 mask <<= index;
143 result = (mask & state->part2) << 1;
144 result |= (~mask & state->part2);
145 state->part1 <<= 1;
146 if (state->part2 & 0x80000000)
147 state->part1 |= 1;
148 state->part2 = result;
149 }
150 else {
151 mask = ~0;
152 mask <<= index - 32;
153 result = (mask & state->part1) << 1;
154 result |= (~mask & state->part1);
155 state->part1 = result;
156 }
157 }
158
159
166 STATE *new_state(STATE *oldstate) {
167 STATE *this_state;
168
169 this_state = newstate ();
170 this_state->part1 = oldstate->part1;
171 this_state->part2 = oldstate->part2;
172 return (this_state);
173 }
174
175
181 int ones_in_state(STATE *state, int num_joints) {
182 inT8 num_ones = 0;
183 inT8 x;
184 unsigned int mask;
185
186 if (num_joints > 32) /* Preset mask */
187 mask = 1 << (num_joints - 1 - 32);
188 else
189 mask = 1 << (num_joints - 1);
190
191 for (x = num_joints - 1; x >= 0; x--) {
192 /* Iterate all bits */
193
194 if (x < 32)
195 num_ones += ((state->part2 & mask) ? 1 : 0);
196 else
197 num_ones += ((state->part1 & mask) ? 1 : 0);
198
199 if (mask == 1) /* Next mask value */
200 mask = 1 << 31;
201 else
202 mask >>= 1;
203 }
204
205 return (num_ones);
206 }
207
208
214 void print_state(const char *label, STATE *state, int num_joints) {
215 int x;
216 unsigned int mask; /* Bit mask */
217
218 if (num_joints > 32) /* Preset mask */
219 mask = 1 << (num_joints - 1 - 32);
220 else
221 mask = 1 << (num_joints - 1);
222
223 cprintf ("%s ", label);
224
225 for (x = num_joints - 1; x >= 0; x--) {
226 /* Iterate all bits */
227
228 if (x < 32)
229 cprintf ("%d", ((state->part2 & mask) ? 1 : 0));
230 else
231 cprintf ("%d", ((state->part1 & mask) ? 1 : 0));
232 if (x % 4 == 0)
233 cprintf (" ");
234
235 if (mask == 1) /* Next mask value */
236 mask = 1 << 31;
237 else
238 mask >>= 1;
239 }
240
241 new_line();
242 }
243
244 // Prints out the number of fragments in each segment in a state to
245 // toappend.
246 void print_state(STATE *state, int num_joints, STRING *toappend) {
247 PIECES_STATE pieces;
248 bin_to_pieces(state, num_joints, pieces);
249 for (int i = 0; pieces[i] > 0; i++) {
250 if (i > 0) {
251 toappend->add_str_int(" ", pieces[i]);
252 } else {
253 toappend->add_str_int("", pieces[i]);
254 }
255 }
256 }
257
263 void set_n_ones(STATE *state, int n) {
264 if (n < 32) {
265 state->part2 = ~0;
266 state->part2 >>= 32 - n;
267 state->part1 = 0;
268 }
269 else {
270 state->part2 = ~0;
271 state->part1 = ~0;
272 state->part1 >>= 64 - n;
273 }
274 }