Tesseract  3.02
tesseract-ocr/dict/states.cpp
Go to the documentation of this file.
00001 /* -*-C-*-
00002  ********************************************************************************
00003  *
00004  * File:        states.c  (Formerly states.c)
00005  * Description:  Representations of search states
00006  * Author:       Mark Seaman, OCR Technology
00007  * Created:      Wed May 16 15:49:34 1990
00008  * Modified:     Mon Jun 17 17:54:41 1991 (Mark Seaman) marks@hpgrlt
00009  * Language:     C
00010  * Package:      N/A
00011  * Status:       Experimental (Do Not Distribute)
00012  *
00013  * (c) Copyright 1990, Hewlett-Packard Company.
00014  ** Licensed under the Apache License, Version 2.0 (the "License");
00015  ** you may not use this file except in compliance with the License.
00016  ** You may obtain a copy of the License at
00017  ** http://www.apache.org/licenses/LICENSE-2.0
00018  ** Unless required by applicable law or agreed to in writing, software
00019  ** distributed under the License is distributed on an "AS IS" BASIS,
00020  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00021  ** See the License for the specific language governing permissions and
00022  ** limitations under the License.
00023  *
00024  *********************************************************************************/
00025 /*----------------------------------------------------------------------
00026               I n c l u d e s
00027 ----------------------------------------------------------------------*/
00028 #include "states.h"
00029 #include "structures.h"
00030 #include "callcpp.h"
00031 
00032 /*-------------------------------------------------------------------------
00033             Variables
00034 --------------------------------------------------------------------------*/
00035 makestructure(newstate, free_state, STATE);
00036 
00037 /*----------------------------------------------------------------------
00038               F u n c t i o n s
00039 ----------------------------------------------------------------------*/
00049 SEARCH_STATE bin_to_chunks(STATE *state, int num_joints) {
00050   int x;
00051   unsigned int mask;
00052   int depth;
00053   int pieces = 0;
00054   SEARCH_STATE s;
00055 
00056   s = memalloc (sizeof (int) * (ones_in_state (state, num_joints) + 1));
00057 
00058   depth = 1;
00059   mask = 1 << (num_joints - 1 - 32);
00060   for (x = num_joints; x > 32; x--) {
00061     if (state->part1 & mask) {
00062       s[depth++] = pieces;
00063       pieces = 0;
00064     }
00065     else {
00066       pieces++;
00067     }
00068     mask >>= 1;
00069   }
00070 
00071   if (num_joints > 32)
00072     mask = 1 << 31;
00073   else
00074     mask = 1 << (num_joints - 1);
00075 
00076   while (x--) {
00077     if (state->part2 & mask) {
00078       s[depth++] = pieces;
00079       pieces = 0;
00080     }
00081     else {
00082       pieces++;
00083     }
00084     mask >>= 1;
00085   }
00086   s[0] = depth - 1;
00087 
00088   return (s);
00089 }
00090 
00091 
00099 void bin_to_pieces(STATE *state, int num_joints, PIECES_STATE pieces) {
00100   int x;
00101   unsigned int mask;             /* Bit mask */
00102   inT16 num_pieces = 0;
00103   /* Preset mask */
00104   mask = ((num_joints > 32) ?
00105     (1 << (num_joints - 1 - 32)) : (1 << (num_joints - 1)));
00106 
00107   pieces[num_pieces] = 0;
00108 
00109   for (x = num_joints - 1; x >= 0; x--) {
00110                                  /* Iterate all bits */
00111     pieces[num_pieces]++;
00112 
00113     if ((x < 32) ?               /* Test for 1 bit */
00114       ((state->part2 & mask) ? TRUE : FALSE) :
00115     ((state->part1 & mask) ? TRUE : FALSE)) {
00116       pieces[++num_pieces] = 0;
00117     }
00118     /* Next mask value */
00119     mask = ((mask == 1) ? (1 << 31) : (mask >> 1));
00120   }
00121   pieces[num_pieces]++;
00122   pieces[++num_pieces] = 0;
00123   ASSERT_HOST (num_pieces < MAX_NUM_CHUNKS + 2);
00124 }
00125 
00126 
00133 void insert_new_chunk(register STATE *state,
00134                       register int index,
00135                       register int num_joints) {
00136   register unsigned int mask;
00137   register unsigned int result;
00138 
00139   index = (num_joints - index);
00140   if (index < 32) {
00141     mask = ~0;
00142     mask <<= index;
00143     result = (mask & state->part2) << 1;
00144     result |= (~mask & state->part2);
00145     state->part1 <<= 1;
00146     if (state->part2 & 0x80000000)
00147       state->part1 |= 1;
00148     state->part2 = result;
00149   }
00150   else {
00151     mask = ~0;
00152     mask <<= index - 32;
00153     result = (mask & state->part1) << 1;
00154     result |= (~mask & state->part1);
00155     state->part1 = result;
00156   }
00157 }
00158 
00159 
00166 STATE *new_state(STATE *oldstate) {
00167   STATE *this_state;
00168 
00169   this_state = newstate ();
00170   this_state->part1 = oldstate->part1;
00171   this_state->part2 = oldstate->part2;
00172   return (this_state);
00173 }
00174 
00175 
00181 int ones_in_state(STATE *state, int num_joints) {
00182   inT8 num_ones = 0;
00183   inT8 x;
00184   unsigned int mask;
00185 
00186   if (num_joints > 32)           /* Preset mask */
00187     mask = 1 << (num_joints - 1 - 32);
00188   else
00189     mask = 1 << (num_joints - 1);
00190 
00191   for (x = num_joints - 1; x >= 0; x--) {
00192                                  /* Iterate all bits */
00193 
00194     if (x < 32)
00195       num_ones += ((state->part2 & mask) ? 1 : 0);
00196     else
00197       num_ones += ((state->part1 & mask) ? 1 : 0);
00198 
00199     if (mask == 1)               /* Next mask value */
00200       mask = 1 << 31;
00201     else
00202       mask >>= 1;
00203   }
00204 
00205   return (num_ones);
00206 }
00207 
00208 
00214 void print_state(const char *label, STATE *state, int num_joints) {
00215   int x;
00216   unsigned int mask;             /* Bit mask */
00217 
00218   if (num_joints > 32)           /* Preset mask */
00219     mask = 1 << (num_joints - 1 - 32);
00220   else
00221     mask = 1 << (num_joints - 1);
00222 
00223   cprintf ("%s ", label);
00224 
00225   for (x = num_joints - 1; x >= 0; x--) {
00226                                  /* Iterate all bits */
00227 
00228     if (x < 32)
00229       cprintf ("%d", ((state->part2 & mask) ? 1 : 0));
00230     else
00231       cprintf ("%d", ((state->part1 & mask) ? 1 : 0));
00232     if (x % 4 == 0)
00233       cprintf (" ");
00234 
00235     if (mask == 1)               /* Next mask value */
00236       mask = 1 << 31;
00237     else
00238       mask >>= 1;
00239   }
00240 
00241   new_line();
00242 }
00243 
00244 // Prints out the number of fragments in each segment in a state to
00245 // toappend.
00246 void print_state(STATE *state, int num_joints, STRING *toappend) {
00247   PIECES_STATE pieces;
00248   bin_to_pieces(state, num_joints, pieces);
00249   for (int i = 0; pieces[i] > 0; i++) {
00250    if (i > 0) {
00251      toappend->add_str_int(" ", pieces[i]);
00252    } else {
00253      toappend->add_str_int("", pieces[i]);
00254    }
00255   }
00256 }
00257 
00263 void set_n_ones(STATE *state, int n) {
00264   if (n < 32) {
00265     state->part2 = ~0;
00266     state->part2 >>= 32 - n;
00267     state->part1 = 0;
00268   }
00269   else {
00270     state->part2 = ~0;
00271     state->part1 = ~0;
00272     state->part1 >>= 64 - n;
00273   }
00274 }