Tesseract  3.02
 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 }