pctb/ocr.c

   1 /*
   2  * Core OCR algorithm (first exact bitmap match)
   3  */
   4 /*
   5  *  This is part of ypp-sc-tools, a set of third-party tools for assisting
   6  *  players of Yohoho Puzzle Pirates.
   7  *
   8  *  Copyright (C) 2009 Ian Jackson <ijackson@chiark.greenend.org.uk>
   9  *
  10  *  This program is free software: you can redistribute it and/or modify
  11  *  it under the terms of the GNU General Public License as published by
  12  *  the Free Software Foundation, either version 3 of the License, or
  13  *  (at your option) any later version.
  14  *
  15  *  This program is distributed in the hope that it will be useful,
  16  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  *  GNU General Public License for more details.
  19  *
  20  *  You should have received a copy of the GNU General Public License
  21  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  22  *
  23  *  Yohoho and Puzzle Pirates are probably trademarks of Three Rings and
  24  *  are used without permission.  This program is not endorsed or
  25  *  sponsored by Three Rings.
  26  */
  27
  28 #include "ocr.h"
  29
  30 typedef struct {
  31   Pixcol col;
  32   struct DatabaseNode *then;
  33 } DatabaseLink;
  34
  35 #define MAXGLYPHCHRS 7
  36
  37 typedef struct DatabaseNode {
  38   char s[MAXGLYPHCHRS+1]; /* null-terminated; "" means no match here */
  39   int nlinks, alinks;
  40   unsigned endsword:1;
  41   DatabaseLink *links;
  42 } DatabaseNode;
  43
  44 static const char *context_names[]= {
  45   "Lower",
  46   "Upper",
  47   "Digit"
  48 };
  49 struct OcrCellTypeInfo {
  50   /* bitmaps of indices into context_names: */
  51   unsigned initial, nextword, midword;
  52   int space_spaces;
  53   const char *name;
  54 };
  55 const struct OcrCellTypeInfo ocr_celltype_number= {
  56   4,4,4,
  57   .space_spaces= 5,
  58   .name= "number"
  59 };
  60 const struct OcrCellTypeInfo ocr_celltype_text= {
  61   .initial=2, /* Uppercase */
  62   .nextword=3, /* Either */
  63   .midword=1, /* Lower only */
  64   .space_spaces= 4,
  65   .name= "text"
  66 };
  67
  68
  69 #define NCONTEXTS (sizeof(context_names)/sizeof(context_names[0]))
  70
  71 struct OcrReader {
  72   int h;
  73   DatabaseNode contexts[NCONTEXTS];
  74   OcrResultGlyph *results;
  75   int aresults, nresults;
  76 };
  77
  78 static FILE *resolver;
  79 static pid_t resolver_pid;
  80 static int resolver_done;
  81
  82 DEBUG_DEFINE_DEBUGF(ocr)
  83
  84 #define FGETSLINE (dbfile_getsline(lbuf,sizeof(lbuf),__FILE__,__LINE__))
  85
  86 static void cleardb_node(DatabaseNode *n) {
  87   int i;
  88   n->s[0]= 0;
  89   for (i=0; i<n->nlinks; i++)
  90     cleardb_node(n->links[i].then);
  91 }
  92
  93 static void readdb(OcrReader *rd) {
  94   int nchrs;
  95   DatabaseNode *current, *additional;
  96   char chrs[MAXGLYPHCHRS+1];
  97   Pixcol cv;
  98   int j,ctxi;
  99   int h, endsword;
 100   char lbuf[100];
 101
 102   for (ctxi=0; ctxi<NCONTEXTS; ctxi++)
 103     cleardb_node(&rd->contexts[ctxi]);
 104
 105   char *dbfname=0;
 106   asprintf(&dbfname,"%s/charset-%d.txt",get_vardir(),rd->h);
 107   sysassert(dbfname);
 108
 109   if (!dbfile_open(dbfname))
 110     goto x;
 111
 112   FGETSLINE;
 113   dbassert(!strcmp(lbuf,"# ypp-sc-tools pctb font v1"));
 114
 115   dbassert( dbfile_scanf("%d", &h) == 1);
 116   dbassert(h==rd->h);
 117
 118   for (;;) {
 119     FGETSLINE;
 120     if (!lbuf[0] || lbuf[0]=='#') continue;
 121     if (!strcmp(lbuf,".")) break;
 122
 123     for (ctxi=0; ctxi<NCONTEXTS; ctxi++)
 124       if (!strcmp(lbuf,context_names[ctxi]))
 125         goto found_ctx;
 126     /* not found, just skip */
 127     for (;;) { FGETSLINE; if (!lbuf[0]) break; }
 128     continue;
 129
 130   found_ctx:
 131     for (nchrs=0;;) {
 132       int c= fgetc(dbfile); sysassert(!ferror(dbfile)); dbassert(c!=EOF);
 133       if (c=='\n') { dbassert(nchrs); break; }
 134       dbassert(nchrs<MAXGLYPHCHRS);
 135       if (c=='\\') {
 136         unsigned cr;
 137         c= fgetc(dbfile); sysassert(!ferror(dbfile)); dbassert(c=='x');
 138         dbassert( dbfile_scanf("%2x", &cr) == 1);
 139         assert(cr>0 && cr<=255);
 140         c= cr;
 141       }
 142       chrs[nchrs++]= c;
 143     }
 144     endsword= 0;
 145     if (nchrs>1 && chrs[nchrs-1]==' ') {
 146       endsword= 1;
 147       nchrs--;
 148     }
 149     chrs[nchrs]= 0;
 150
 151     current= &rd->contexts[ctxi];
 152     for (;;) {
 153       FGETSLINE;
 154       if (!lbuf[0]) { dbassert(current != &rd->contexts[ctxi]); break; }
 155       char *ep;
 156       cv= strtoul(lbuf,&ep,16);  dbassert(!*ep);
 157       dbassert(!(cv & ~((1UL << rd->h)-1)));
 158
 159       for (j=0; j<current->nlinks; j++)
 160         if (current->links[j].col == cv) {
 161           current= current->links[j].then;
 162           goto found_link;
 163         }
 164
 165       additional= mmalloc(sizeof(*additional));
 166       additional->s[0]= 0;
 167       additional->nlinks= additional->alinks= 0;
 168       additional->links= 0;
 169       if (current->nlinks==current->alinks) {
 170         current->alinks++;
 171         current->alinks<<=1;
 172         current->links= mrealloc(current->links,
 173                                  sizeof(*current->links) * current->alinks);
 174       }
 175       current->links[current->nlinks].col= cv;
 176       current->links[current->nlinks].then= additional;
 177       current->nlinks++;
 178       current= additional;
 179
 180     found_link:;
 181     }
 182
 183     dbassert(!current->s[0]);
 184     strcpy(current->s, chrs);
 185     current->endsword= endsword;
 186   }
 187  x:
 188   dbfile_close();
 189   free(dbfname);
 190 }
 191
 192 static void cu_pr_ctxmap(unsigned ctxmap) {
 193   fprintf(resolver,"{");
 194   const char *spc="";
 195   int ctxi;
 196   for (ctxi=0; ctxi<NCONTEXTS; ctxi++) {
 197     if (!(ctxmap & (1u << ctxi))) continue;
 198     fprintf(resolver,"%s%s",spc,context_names[ctxi]);
 199     spc=" ";
 200   }
 201   fprintf(resolver,"}");
 202 }
 203
 204 static void callout_unknown(OcrReader *rd, int w, Pixcol cols[],
 205                             int unk_l, int unk_r, unsigned unk_ctxmap) {
 206   int jobpipe[2],donepipe[2], c,i, x,y;
 207   const OcrResultGlyph *s;
 208   const char *p;
 209   char cb;
 210   Pixcol pv;
 211
 212   if (!o_resolver)
 213     fatal("OCR failed - unrecognised characters or ligatures.\n"
 214           "Character set database needs to be updated or augmented.\n"
 215           "See README.charset.\n");
 216
 217   if (!resolver) {
 218     sysassert(! pipe(jobpipe) );
 219     sysassert(! pipe(donepipe) );
 220     resolver_pid= fork();
 221     sysassert(resolver_pid!=-1);
 222     if (!resolver_pid) {
 223       sysassert( dup2(jobpipe[0],0) ==0 );
 224       sysassert(! close(jobpipe[1]) );
 225       sysassert(! close(donepipe[0]) );
 226       /* we know donepipe[1] is >= 4 and we have dealt with all the others
 227        * so we aren't in any danger of overwriting some other fd 4: */
 228       sysassert( dup2(donepipe[1],4) ==4 );
 229       execlp(o_resolver, o_resolver,
 230              DEBUGP(callout) ? "--debug" : "--noop-arg",
 231              "--automatic-1",
 232              (char*)0);
 233       sysassert(!"execlp ocr-resolver failed");
 234     }
 235     sysassert(! close(jobpipe[0]) );
 236     sysassert(! close(donepipe[1]) );
 237     resolver= fdopen(jobpipe[1],"w"); sysassert(resolver);
 238     resolver_done= donepipe[0];
 239   }
 240   fprintf(resolver,"%d %d ",unk_l,unk_r);
 241   cu_pr_ctxmap(unk_ctxmap);
 242   for (i=0, s=rd->results; i<rd->nresults; i++, s++) {
 243     if (!strcmp(s->s," ")) continue;
 244     fprintf(resolver," %d %d ",s->l,s->r);
 245     cu_pr_ctxmap(s->ctxmap);
 246     fprintf(resolver," ");
 247     for (p=s->s; (c= *p); p++) {
 248       if (c=='\\') fprintf(resolver,"\\%c",c);
 249       else if (c>=33 && c<=126) fputc(c,resolver);
 250       else fprintf(resolver,"\\x%02x",(unsigned char)c);
 251     }
 252   }
 253   fputc('\n',resolver);
 254
 255   fprintf(resolver,
 256           "/* XPM */\n"
 257           "static char *t[] = {\n"
 258           "/* columns rows colors chars-per-pixel */\n"
 259           "\"%d %d 2 1\",\n"
 260           "\"  c black\",\n"
 261           "\"o c white\",\n",
 262           w,rd->h);
 263   for (y=0, pv=1; y<rd->h; y++, pv<<=1) {
 264     fputc('"',resolver);
 265     for (x=0; x<w; x++)
 266       fputc(cols[x] & pv ? 'o' : ' ', resolver);
 267     fputs("\",\n",resolver);
 268   }
 269   fputs("};\n",resolver);
 270   sysassert(!ferror(resolver));
 271   sysassert(!fflush(resolver));
 272
 273   sysassert(resolver);
 274
 275   int r;
 276   for (;;) {
 277     r= read(resolver_done,&cb,1);
 278     if (r==-1) { sysassert(errno==EINTR); continue; }
 279     break;
 280   }
 281
 282   if (r==0) {
 283     waitpid_check_exitstatus(resolver_pid, "character resolver");
 284     fclose(resolver);
 285     close(resolver_done);
 286     resolver= 0;
 287   } else {
 288     assert(r==1);
 289     sysassert(cb==0);
 290   }
 291
 292   readdb(rd);
 293 }
 294
 295 static void add_result(OcrReader *rd, const char *s, int l, int r,
 296                        unsigned ctxmap) {
 297   if (rd->nresults >= rd->aresults) {
 298     rd->aresults++; rd->aresults<<=1;
 299     rd->results= mrealloc(rd->results, sizeof(*rd->results)*rd->aresults);
 300   }
 301   rd->results[rd->nresults].s= s;
 302   rd->results[rd->nresults].l= l;
 303   rd->results[rd->nresults].r= r;
 304   rd->results[rd->nresults].ctxmap= ctxmap;
 305   rd->nresults++;
 306 }
 307
 308
 309 const char *ocr_celltype_name(OcrCellType ct) { return ct->name; }
 310
 311 OcrResultGlyph *ocr(OcrReader *rd, OcrCellType ct, int w, Pixcol cols[]) {
 312   int nspaces;
 313   unsigned ctxmap;
 314   int ctxi, i, x;
 315
 316  restart:
 317
 318   nspaces=- w;
 319   ctxmap= ct->initial;
 320   rd->nresults=0;
 321   debugf("OCR h=%d w=%d",rd->h,w);
 322   for (x=0; x<w; x++) debugf(" %"PSPIXCOL(PRIx),cols[x]);
 323   debugf("\n");
 324   debug_flush();
 325
 326   x=0;
 327   for (;;) {
 328     debug_flush();
 329     /* skip spaces */
 330     if (x>=w)
 331       break;
 332
 333     if (!cols[x]) {
 334       nspaces++;
 335       x++;
 336       if (nspaces == ct->space_spaces) {
 337         debugf("OCR  x=%x nspaces=%d space\n",x,nspaces);
 338         ctxmap= ct->nextword;
 339       }
 340       continue;
 341     }
 342
 343     /* something here, so we need to add the spaces */
 344     if (nspaces >= ct->space_spaces)
 345       add_result(rd," ",x-nspaces,x+1,0);
 346     nspaces=0;
 347
 348     /* find character */
 349     int lx=x;
 350
 351     DatabaseNode *uniquematch= 0;
 352     int uniquematch_rx=-1;
 353
 354     debugf("OCR  lx=%d ctxmap=%x  ",lx,ctxmap);
 355
 356     for (ctxi=0; ctxi<NCONTEXTS; ctxi++) {
 357       DatabaseNode *current= &rd->contexts[ctxi];;
 358       DatabaseNode *bestmatch= 0;
 359       int bestmatch_rx=-1;
 360
 361       x= lx;
 362       if (!(ctxmap & (1u << ctxi))) continue;
 363       debugf(" || %s",context_names[ctxi]);
 364
 365       for (;;) {
 366         debug_flush();
 367         debugf(" | x=%d",x);
 368         if (x>w) break;
 369         Pixcol cv= cols[x];
 370         debugf(" cv=%"PSPIXCOL(PRIx),cv);
 371         for (i=0; i<current->nlinks; i++)
 372           if (current->links[i].col == cv)
 373             goto found;
 374         /* not found */
 375         debugf(" ?");
 376         break;
 377
 378       found:
 379         current= current->links[i].then;
 380         if (current->s[0]) {
 381           debugf(" \"%s\"%s",current->s,current->endsword?"_":"");
 382           bestmatch= current;
 383           bestmatch_rx= x;
 384         } else {
 385           debugf(" ...");
 386         }
 387
 388         x++;
 389       }
 390
 391       if (bestmatch) {
 392         if (uniquematch && strcmp(bestmatch->s, uniquematch->s)) {
 393           debugf( " ambiguous");
 394           uniquematch= 0;
 395           break;
 396         }
 397         uniquematch= bestmatch;
 398         uniquematch_rx= bestmatch_rx;
 399       }
 400     }
 401
 402     if (uniquematch) {
 403       debugf(" || YES");
 404       add_result(rd, uniquematch->s, lx, uniquematch_rx, ctxmap);
 405       x= uniquematch_rx+1;
 406       if (uniquematch->s[0]) ctxmap= ct->midword;
 407       else debugf(" (empty)");
 408       if (uniquematch->endsword) {
 409         nspaces= ct->space_spaces;
 410         debugf("_");
 411         ctxmap= ct->nextword;
 412       }
 413       debugf("\n");
 414     } else {
 415       int rx;
 416       debugf(" || UNKNOWN");
 417       for (rx=lx; rx<w && cols[rx]; rx++);
 418       debugf(" x=%d ctxmap=%x %d..%d\n",x, ctxmap, lx,rx);
 419       debug_flush();
 420       callout_unknown(rd, w,cols, lx,rx-1, ctxmap);
 421       goto restart;
 422     }
 423   }
 424   add_result(rd, 0,-1,-1,0);
 425   debugf("OCR  finished %d glyphs\n",rd->nresults);
 426   debug_flush();
 427   return rd->results;
 428 }
 429
 430 OcrReader *ocr_init(int h) {
 431   OcrReader *rd;
 432
 433   rd= mmalloc(sizeof(*rd));
 434   memset(rd,0,sizeof(*rd));
 435   rd->h= h;
 436   readdb(rd);
 437   return rd;
 438 }