chiark / gitweb /
Merge branch 'origin'
[ypp-sc-tools.web-live.git] / 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 #include "convert.h"
30
31 typedef struct {
32   Pixcol col;
33   struct DatabaseNode *then;
34 } DatabaseLink;
35
36 typedef struct DatabaseNode {
37   char *str;
38   int nlinks, alinks;
39   unsigned match:1, defined:1, endsword:1;
40   DatabaseLink *links;
41 } DatabaseNode;
42
43 typedef struct {
44   OcrReader *rd;
45   OcrCellType ct;
46   int w;
47   Pixcol *cols;
48   int x;
49   unsigned ctxmap;
50 } FindCharArgs;
51 typedef struct {
52   DatabaseNode *match;
53   int rx;
54 } FindCharResults;
55
56 enum { ct_Lower, ct_Upper, ct_Word, ct_Digit };
57 static const char *context_names[]= {
58   "Lower",  /*  bit 0, value 001 */
59   "Upper",  /*  bit 1, value 002 */
60   "Word",   /*  bit 2, value 004 */
61   "Digit",  /*  bit 3, value 010 */
62 };
63 struct OcrCellTypeInfo {
64   /* bitmaps of indices into context_names: */
65   unsigned initial, nextword, midword;
66   int space_spaces;
67   const char *name;
68   int (*findchar_select)(const FindCharArgs *fca,
69                          const FindCharResults results[]);
70 };
71
72 #define NCONTEXTS (sizeof(context_names)/sizeof(context_names[0]))
73
74 struct OcrReader {
75   int h;
76   DatabaseNode contexts[NCONTEXTS];
77   OcrResultGlyph *results;
78   int aresults, nresults;
79 };
80
81 DEBUG_DEFINE_DEBUGF(ocr)
82
83 #define FGETSLINE (dbfile_getsline(lbuf,sizeof(lbuf),__FILE__,__LINE__))
84
85 static void cleardb_node(DatabaseNode *n) {
86   int i;
87   free(n->str); n->str=0;
88   n->defined=n->match=n->endsword= 0;
89   for (i=0; i<n->nlinks; i++)
90     cleardb_node(n->links[i].then);
91 }
92
93 static void readdb1(OcrReader *rd, const char *which);
94
95 static void readdb(OcrReader *rd) {
96   int ctxi;
97   
98   for (ctxi=0; ctxi<NCONTEXTS; ctxi++)
99     cleardb_node(&rd->contexts[ctxi]);
100
101   readdb1(rd, "master");
102   readdb1(rd, "local");
103 }
104
105 static void readdb1(OcrReader *rd, const char *which) {
106   int nchrs;
107   DatabaseNode *current, *additional;
108   char chrs[100];
109   Pixcol cv;
110   int j,ctxi;
111   int h, endsword;
112   char lbuf[100];
113
114   char *dbfname= masprintf("%s/#%s-char%d#.txt",
115                            get_vardir(), which, rd->h);
116   
117   if (!dbfile_open(dbfname))
118     goto x;
119
120   FGETSLINE;
121   dbassert(!strcmp(lbuf,"# ypp-sc-tools pctb font v1"));
122
123   dbassert( dbfile_scanf("%d", &h) == 1);
124   dbassert(h==rd->h);
125
126   for (;;) {
127     FGETSLINE;
128     if (!lbuf[0] || lbuf[0]=='#') continue;
129     if (!strcmp(lbuf,".")) break;
130
131     for (ctxi=0; ctxi<NCONTEXTS; ctxi++)
132       if (!strcmp(lbuf,context_names[ctxi]))
133         goto found_ctx;
134     /* not found, just skip */
135     for (;;) { FGETSLINE; if (!lbuf[0]) break; }
136     continue;
137
138   found_ctx:
139     for (nchrs=0;;) {
140       int c= fgetc(dbfile); sysassert(!ferror(dbfile)); dbassert(c!=EOF);
141       if (c=='\n') break; /* forces no match */
142       dbassert(nchrs<sizeof(chrs));
143       chrs[nchrs++]= c;
144     }
145     endsword= 0;
146     if (nchrs>0 && chrs[nchrs-1]==' ') {
147       endsword= 1;
148       nchrs--;
149     }
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->str= 0;
167       additional->defined= 0;
168       additional->match= 0;
169       additional->endsword= 0;
170       additional->nlinks= additional->alinks= 0;
171       additional->links= 0;
172       if (current->nlinks==current->alinks) {
173         current->alinks++;
174         current->alinks<<=1;
175         current->links= mrealloc(current->links,
176                                  sizeof(*current->links) * current->alinks);
177       }
178       current->links[current->nlinks].col= cv;
179       current->links[current->nlinks].then= additional;
180       current->nlinks++;
181       current= additional;
182
183     found_link:;
184     }
185
186     if (!current->defined) {
187       free(current->str);
188       current->str= 0;
189       current->defined= 1;
190       current->match= 0;
191
192       if (nchrs) {
193         current->str= mmalloc(nchrs+1);
194         memcpy(current->str, chrs, nchrs);
195         current->str[nchrs]= 0;
196         current->match= 1;
197         current->endsword= endsword;
198       }
199     }
200   }
201  x:
202   dbfile_close();
203   free(dbfname);
204 }
205
206 static void cu_pr_ctxmap(FILE *resolver, unsigned ctxmap) {
207   fprintf(resolver,"{");
208   const char *spc="";
209   int ctxi;
210   for (ctxi=0; ctxi<NCONTEXTS; ctxi++) {
211     if (!(ctxmap & (1u << ctxi))) continue;
212     fprintf(resolver,"%s%s",spc,context_names[ctxi]);
213     spc=" ";
214   }
215   fprintf(resolver,"}");
216 }
217
218 static void callout_unknown(OcrReader *rd, int w, Pixcol cols[],
219                             int unk_l, int unk_r, unsigned unk_ctxmap) {
220   int c,i, x,y;
221   const OcrResultGlyph *s;
222   const char *p;
223   Pixcol pv;
224
225   FILE *resolver= resolve_start();
226   if (!resolver)
227     fatal("OCR failed - unrecognised characters or ligatures.\n"
228           "Character set database needs to be updated or augmented.\n"
229           "See README.charset.\n");
230   
231   fprintf(resolver,
232           "char\n"
233           "%d %d ",unk_l,unk_r);
234   cu_pr_ctxmap(resolver,unk_ctxmap);
235   for (i=0, s=rd->results; i<rd->nresults; i++, s++) {
236     if (!strcmp(s->s," ")) continue;
237     fprintf(resolver," %d %d ",s->l,s->r);
238     cu_pr_ctxmap(resolver,s->ctxmap);
239     fprintf(resolver," ");
240     for (p=s->s; (c= *p); p++) {
241       if (c=='\\') fprintf(resolver,"\\%c",c);
242       else if (c>=33 && c<=126) fputc(c,resolver);
243       else fprintf(resolver,"\\x%02x",(unsigned char)c);
244     }
245   }
246   fputc('\n',resolver);
247
248   fprintf(resolver,
249           "/* XPM */\n"
250           "static char *t[] = {\n"
251           "/* columns rows colors chars-per-pixel */\n"
252           "\"%d %d 2 1\",\n"
253           "\"  c black\",\n"
254           "\"o c white\",\n",
255           w,rd->h);
256   for (y=0, pv=1; y<rd->h; y++, pv<<=1) {
257     fputc('"',resolver);
258     for (x=0; x<w; x++)
259       fputc(cols[x] & pv ? 'o' : ' ', resolver);
260     fputs("\",\n",resolver);
261   }
262   fputs("};\n",resolver);
263
264   resolve_finish();
265   readdb(rd);
266 }
267
268 static void add_result(OcrReader *rd, const char *s, int l, int r,
269                        unsigned ctxmap) {
270   if (rd->nresults >= rd->aresults) {
271     rd->aresults++; rd->aresults<<=1;
272     rd->results= mrealloc(rd->results, sizeof(*rd->results)*rd->aresults);
273   }
274   rd->results[rd->nresults].s= s;
275   rd->results[rd->nresults].l= l;
276   rd->results[rd->nresults].r= r;
277   rd->results[rd->nresults].ctxmap= ctxmap;
278   rd->nresults++;
279 }
280
281
282 static DatabaseNode *findchar_1ctx(const FindCharArgs *fca,
283                                    DatabaseNode *start, int *matchx_r) {
284   DatabaseNode *current= start;
285   DatabaseNode *bestmatch= 0;
286   int i;
287   int x= fca->x;
288
289   for (;;) {
290     debug_flush();
291     debugf(" | x=%d",x);
292     if (x > fca->w) break;
293     Pixcol cv= fca->cols[x];
294     debugf(" cv=%"PSPIXCOL(PRIx),cv);
295     for (i=0; i<current->nlinks; i++)
296       if (current->links[i].col == cv)
297         goto found;
298     /* not found */
299     debugf(" ?");
300     break;
301
302   found:
303     current= current->links[i].then;
304     if (current->match) {
305       debugf(" \"%s\"%s",current->str,current->endsword?"_":"");
306       bestmatch= current;
307       *matchx_r= x;
308     } else {
309       debugf(" ...");
310     }
311
312     x++;
313   }
314   return bestmatch;
315 }  
316
317 static DatabaseNode *findchar(const FindCharArgs *fca, int *match_rx) {
318   FindCharResults results[NCONTEXTS];
319   int ctxi, match=-1, nmatches=0;
320
321   debugf("OCR  lx=%d ct_state=%x  ", fca->x, fca->ctxmap);
322   for (ctxi=0; ctxi<NCONTEXTS; ctxi++) {
323     results[ctxi].match= 0;
324     if (!(fca->ctxmap & (1u << ctxi))) continue;
325     debugf(" || %s",context_names[ctxi]);
326
327     results[ctxi].match= findchar_1ctx(fca, &fca->rd->contexts[ctxi],
328                                        &results[ctxi].rx);
329     if (!results[ctxi].match) continue;
330
331     match= ctxi;
332     nmatches++;
333   }
334   if (nmatches==1) {
335     debugf(" unique");
336   } else {
337     debugf(" ambiguous");
338     match= !fca->ct->findchar_select ? -1 :
339       fca->ct->findchar_select(fca,results);
340     debugf(" resolved %s", match<0 ? "<none>" : context_names[match]);
341   }
342   if (match<0)
343     return 0;
344   
345   *match_rx= results[ctxi].rx;
346   return results[ctxi].match;
347 }
348
349 static int findchar_select_text(const FindCharArgs *fca,
350                                 const FindCharResults results[]) {
351   if (fca->ctxmap != 017) return -1;
352
353   dbassert(! results[ct_Digit].match );
354   if (results[ct_Word].match) return ct_Word;
355   if (results[ct_Lower].rx > results[ct_Upper].rx) return ct_Lower;
356   if (results[ct_Upper].rx > results[ct_Lower].rx) return ct_Upper;
357   return -1;
358 }
359
360 const struct OcrCellTypeInfo ocr_celltype_number= {
361   010,010,010,
362   .space_spaces= 5,
363   .name= "number",
364   .findchar_select= 0
365 };
366 const struct OcrCellTypeInfo ocr_celltype_text= {
367   .initial=  012, /* Digit|Upper */
368   .nextword= 017, /* Digit|Upper|Lower|Word */
369   .midword=  014, /* Digit|Lower */
370   .space_spaces= 4,
371   .name= "text",
372   .findchar_select= findchar_select_text
373 };
374
375
376 const char *ocr_celltype_name(OcrCellType ct) { return ct->name; }
377
378 OcrResultGlyph *ocr(OcrReader *rd, OcrCellType ct, int w, Pixcol cols[]) {
379   int nspaces;
380   int x;
381
382   FindCharArgs fca;
383   fca.rd= rd;
384   fca.ct= ct;
385   fca.w= w;
386   fca.cols= cols;
387   fca.x= -1;
388
389  restart:
390
391   nspaces=- w;
392   fca.ctxmap= ct->initial;
393   rd->nresults=0;
394   debugf("OCR h=%d w=%d",rd->h,w);
395   for (x=0; x<w; x++) debugf(" %"PSPIXCOL(PRIx),cols[x]);
396   debugf("\n");
397   debug_flush();
398
399   x=0;
400   for (;;) {
401     debug_flush();
402     /* skip spaces */
403     if (x>=w)
404       break;
405
406     if (!cols[x]) {
407       nspaces++;
408       x++;
409       if (nspaces == ct->space_spaces) {
410         debugf("OCR  x=%x nspaces=%d space\n",x,nspaces);
411         fca.ctxmap= ct->nextword;
412       }
413       continue;
414     }
415
416     /* something here, so we need to add the spaces */
417     if (nspaces >= ct->space_spaces)
418       add_result(rd," ",x-nspaces,x+1,0);
419     nspaces=0;
420
421     fca.x= x;
422
423     int match_rx=-1;
424     DatabaseNode *match= findchar(&fca, &match_rx);
425     
426     if (match) {
427       debugf(" || YES");
428       add_result(rd, match->str, x, match_rx, fca.ctxmap);
429       x= match_rx+1;
430       if (match->match) fca.ctxmap= ct->midword;
431       else debugf(" (empty)");
432       if (match->endsword) {
433         nspaces= ct->space_spaces;
434         debugf("_");
435         fca.ctxmap= ct->nextword;
436       }
437       debugf("\n");
438     } else {
439       int rx;
440       debugf(" || UNKNOWN");
441       for (rx=x; rx<w && cols[rx]; rx++);
442       debugf(" x=%d ctxmap=%x %d..%d\n",x, fca.ctxmap, x,rx);
443       debug_flush();
444       callout_unknown(rd, w,cols, x,rx-1, fca.ctxmap);
445       goto restart;
446     }
447
448   }
449   add_result(rd, 0,-1,-1,0);
450   debugf("OCR  finished %d glyphs\n",rd->nresults);
451   debug_flush();
452   return rd->results;
453 }
454
455 OcrReader *ocr_init(int h) {
456   OcrReader *rd;
457
458   if (o_flags & ff_dict_fetch) {
459     char *fetchfile= masprintf("char%d",h);
460     progress("Updating %s...",fetchfile);
461     fetch_with_rsync(fetchfile);
462     free(fetchfile);
463   }
464
465   rd= mmalloc(sizeof(*rd));
466   memset(rd,0,sizeof(*rd));
467   rd->h= h;
468   readdb(rd);
469   return rd;
470 }