X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~yarrgweb/git?p=ypp-sc-tools.db-test.git;a=blobdiff_plain;f=pctb%2Focr.c;h=f174c68117c8d31e29da62fe94f153882eb8d14f;hp=f5826dfe84a01e14b8ba1032aba301595eef367c;hb=c2c039f07de178037bfbf12e4ee23c06f546de32;hpb=80646aad7ee5fdbb1ce28b3fe40c5776241d540d diff --git a/pctb/ocr.c b/pctb/ocr.c index f5826df..f174c68 100644 --- a/pctb/ocr.c +++ b/pctb/ocr.c @@ -1,30 +1,84 @@ /* - */ + * Core OCR algorithm (first exact bitmap match) + */ +/* + * This is part of ypp-sc-tools, a set of third-party tools for assisting + * players of Yohoho Puzzle Pirates. + * + * Copyright (C) 2009 Ian Jackson + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + * + * Yohoho and Puzzle Pirates are probably trademarks of Three Rings and + * are used without permission. This program is not endorsed or + * sponsored by Three Rings. + */ #include "ocr.h" +#include "convert.h" typedef struct { Pixcol col; struct DatabaseNode *then; } DatabaseLink; -#define MAXGLYPHCHRS 3 - typedef struct DatabaseNode { - char s[MAXGLYPHCHRS+1]; /* null-terminated; "" means no match here */ + char *str; int nlinks, alinks; + unsigned match:1, defined:1, endsword:1, local:1; DatabaseLink *links; } DatabaseNode; -static const char *context_names[]= { - "Lower", - "Upper", - "Digit" +typedef struct { + OcrReader *rd; + OcrCellType ct; + int w; + Pixcol *cols; + int x; + unsigned ctxmap; +} FindCharArgs; +typedef struct { + DatabaseNode *match; + int rx; +} FindCharResults; + +#define FOR_EACH_CONTEXT(EACH) \ + EACH(Word) \ + EACH(Upper) \ + EACH(Lower) \ + EACH(Digit) + +#define FEC_ENUM(Context) ct_##Context, +#define FEC_BIT(Context) ctf_##Context = 1 << ct_##Context, +enum { + FOR_EACH_CONTEXT(FEC_ENUM) + FOR_EACH_CONTEXT(FEC_BIT) }; -#define NCONTEXTS (sizeof(context_names)/sizeof(context_names[0])) +#define FEC_STRINGS(Context) #Context, +static const char *context_names[]= { FOR_EACH_CONTEXT(FEC_STRINGS) }; + +struct OcrCellTypeInfo { + /* bitmaps of indices into context_names: */ + unsigned initial, nextword, midword; + int space_spaces; + const char *name; + int (*findchar_select)(const FindCharArgs *fca, + const FindCharResults results[]); +}; -#define SPACE_SPACES 4 +#define NCONTEXTS (sizeof(context_names)/sizeof(context_names[0])) struct OcrReader { int h; @@ -33,94 +87,83 @@ struct OcrReader { int aresults, nresults; }; -static FILE *resolver; -static pid_t resolver_pid; -static int resolver_done; - DEBUG_DEFINE_DEBUGF(ocr) -static void fgetsline(FILE *f, char *lbuf, size_t lbufsz) { - char *s= fgets(lbuf,lbufsz,f); - eassert(s); - int l= strlen(lbuf); - eassert(l>0); eassert(lbuf[--l]='\n'); - lbuf[l]= 0; -} -#define FGETSLINE(f,buf) (fgetsline(f,buf,sizeof(buf))) +#define FGETSLINE (dbfile_getsline(lbuf,sizeof(lbuf),__FILE__,__LINE__)) static void cleardb_node(DatabaseNode *n) { int i; - n->s[0]= 0; + free(n->str); n->str=0; + n->defined=n->match=n->endsword= 0; for (i=0; inlinks; i++) cleardb_node(n->links[i].then); } +static void readdb1(OcrReader *rd, const char *which, int local); + static void readdb(OcrReader *rd) { + int ctxi; + + for (ctxi=0; ctxicontexts[ctxi]); + + readdb1(rd, "master", 0); + readdb1(rd, "local", 1); +} + +static void readdb1(OcrReader *rd, const char *which, int local) { int nchrs; DatabaseNode *current, *additional; - char chrs[MAXGLYPHCHRS+1]; + char chrs[100]; Pixcol cv; - int r,j,ctxi; - int h; + int j,ctxi; + int h, endsword; char lbuf[100]; - FILE *db; - for (ctxi=0; ctxicontexts[ctxi]); - - char *dbfname=0; - asprintf(&dbfname,"%s/charset-%d.txt",get_vardir(),rd->h); - eassert(dbfname); + char *dbfname= masprintf("%s/#%s-char%d#.txt", + get_vardir(), which, rd->h); - db= fopen(dbfname,"r"); - free(dbfname); - if (!db) { - eassert(errno==ENOENT); - return; - } + if (!dbfile_open(dbfname)) + goto x; - FGETSLINE(db,lbuf); - eassert(!strcmp(lbuf,"# ypp-sc-tools pctb font v1")); + FGETSLINE; + dbassert(!strcmp(lbuf,"# ypp-sc-tools pctb font v1")); - r= fscanf(db, "%d", &h); - eassert(r==1); - eassert(h==rd->h); + dbassert( dbfile_scanf("%d", &h) == 1); + dbassert(h==rd->h); for (;;) { - FGETSLINE(db,lbuf); - if (!lbuf || lbuf[0]=='#') continue; + FGETSLINE; + if (!lbuf[0] || lbuf[0]=='#') continue; if (!strcmp(lbuf,".")) break; for (ctxi=0; ctxi0 && cr<=255); - c= cr; - } + int c= fgetc(dbfile); sysassert(!ferror(dbfile)); dbassert(c!=EOF); + if (c=='\n') break; /* forces no match */ + dbassert(nchrs0 && chrs[nchrs-1]==' ') { + endsword= 1; + nchrs--; + } current= &rd->contexts[ctxi]; for (;;) { - FGETSLINE(db,lbuf); - if (!lbuf[0]) { eassert(current != &rd->contexts[ctxi]); break; } + FGETSLINE; + if (!lbuf[0]) { dbassert(current != &rd->contexts[ctxi]); break; } char *ep; - cv= strtoul(lbuf,&ep,16); eassert(!*ep); - eassert(!(cv & ~((1UL << rd->h)-1))); + cv= strtoul(lbuf,&ep,16); dbassert(!*ep); + dbassert(!(cv & ~((1UL << rd->h)-1))); for (j=0; jnlinks; j++) if (current->links[j].col == cv) { @@ -128,16 +171,18 @@ static void readdb(OcrReader *rd) { goto found_link; } - additional= malloc(sizeof(*additional)); eassert(additional); - additional->s[0]= 0; + additional= mmalloc(sizeof(*additional)); + additional->str= 0; + additional->defined= 0; + additional->match= 0; + additional->endsword= 0; additional->nlinks= additional->alinks= 0; additional->links= 0; if (current->nlinks==current->alinks) { current->alinks++; current->alinks<<=1; - current->links= realloc(current->links, - sizeof(*current->links) * current->alinks); - eassert(current->links); + current->links= mrealloc(current->links, + sizeof(*current->links) * current->alinks); } current->links[current->nlinks].col= cv; current->links[current->nlinks].then= additional; @@ -147,14 +192,28 @@ static void readdb(OcrReader *rd) { found_link:; } - eassert(!current->s[0]); - strcpy(current->s, chrs); + if (!current->defined) { + free(current->str); + current->str= 0; + current->defined= 1; + current->match= 0; + current->local= local; + + if (nchrs) { + current->str= mmalloc(nchrs+1); + memcpy(current->str, chrs, nchrs); + current->str[nchrs]= 0; + current->match= 1; + current->endsword= endsword; + } + } } - eassert(!ferror(db)); - eassert(!fclose(db)); + x: + dbfile_close(); + free(dbfname); } -static void cu_pr_ctxmap(unsigned ctxmap) { +static void cu_pr_ctxmap(FILE *resolver, unsigned ctxmap) { fprintf(resolver,"{"); const char *spc=""; int ctxi; @@ -168,41 +227,27 @@ static void cu_pr_ctxmap(unsigned ctxmap) { static void callout_unknown(OcrReader *rd, int w, Pixcol cols[], int unk_l, int unk_r, unsigned unk_ctxmap) { - int jobpipe[2],donepipe[2], c, r,i, x,y; + int c,i, x,y; const OcrResultGlyph *s; const char *p; - char cb; Pixcol pv; + + FILE *resolver= resolve_start(); + if (!resolver || !(o_flags & ff_editcharset)) + fatal("OCR failed - unrecognised characters or ligatures.\n" + "Character set database needs to be updated or augmented.\n" + "See README.charset.\n"); - if (!resolver) { - r= pipe(jobpipe); eassert(!r); - r= pipe(donepipe); eassert(!r); - resolver_pid= fork(); - eassert(resolver_pid!=-1); - if (!resolver_pid) { - r= dup2(jobpipe[0],0); eassert(r==0); - r= close(jobpipe[1]); eassert(!r); - r= close(donepipe[0]); eassert(!r); - /* we know donepipe[1] is >= 4 and we have dealt with all the others - * so we aren't in any danger of overwriting some other fd 4: */ - r= dup2(donepipe[1],4); eassert(r==4); - execlp("./show-thing.tcl", "./show-thing.tcl", - DEBUGP(callout) ? "--debug" : "--noop-arg", - "--automatic-1", - (char*)0); - eassert(!"execlp failed"); - } - r= close(jobpipe[0]); eassert(!r); - r= close(donepipe[1]); eassert(!r); - resolver= fdopen(jobpipe[1],"w"); eassert(resolver); - resolver_done= donepipe[0]; - } - fprintf(resolver,"%d %d ",unk_l,unk_r); - cu_pr_ctxmap(unk_ctxmap); + fprintf(resolver, + "char\n" + "%d %d ",unk_l,unk_r); + cu_pr_ctxmap(resolver,unk_ctxmap); for (i=0, s=rd->results; inresults; i++, s++) { if (!strcmp(s->s," ")) continue; fprintf(resolver," %d %d ",s->l,s->r); - cu_pr_ctxmap(s->ctxmap); + cu_pr_ctxmap(resolver, 1u << s->match); + fprintf(resolver," "); + cu_pr_ctxmap(resolver, s->ctxmap); fprintf(resolver," "); for (p=s->s; (c= *p); p++) { if (c=='\\') fprintf(resolver,"\\%c",c); @@ -227,78 +272,139 @@ static void callout_unknown(OcrReader *rd, int w, Pixcol cols[], fputs("\",\n",resolver); } fputs("};\n",resolver); - eassert(!ferror(resolver)); - eassert(!fflush(resolver)); - - eassert(resolver); - - for (;;) { - r= read(resolver_done,&cb,1); - if (r==-1) { eassert(errno==EINTR); continue; } - break; - } - - if (r==0) { - pid_t pid; - for (;;) { - pid= waitpid(resolver_pid, &r, 0); - if (pid==-1) { eassert(errno==EINTR); continue; } - break; - } - eassert(pid==resolver_pid); - if (WIFEXITED(r)) { - eassert(!WEXITSTATUS(r)); - fclose(resolver); - close(resolver_done); - resolver= 0; - } else if (WIFSIGNALED(r)) { - eassert(!"resolver child died due to signal"); - } else { - eassert(!"weird wait status"); - } - } else { - eassert(r==1); - eassert(cb==0); - } + resolve_finish(); readdb(rd); } static void add_result(OcrReader *rd, const char *s, int l, int r, - unsigned ctxmap) { + int match, unsigned ctxmap) { if (rd->nresults >= rd->aresults) { rd->aresults++; rd->aresults<<=1; - rd->results= realloc(rd->results,sizeof(*rd->results)*rd->aresults); - eassert(rd->results); + rd->results= mrealloc(rd->results, sizeof(*rd->results)*rd->aresults); } rd->results[rd->nresults].s= s; rd->results[rd->nresults].l= l; rd->results[rd->nresults].r= r; + rd->results[rd->nresults].match= match; rd->results[rd->nresults].ctxmap= ctxmap; rd->nresults++; } -struct OcrCellTypeInfo { - unsigned initial, nextword, midword; -}; + +static DatabaseNode *findchar_1ctx(const FindCharArgs *fca, + DatabaseNode *start, int *matchx_r) { + DatabaseNode *current= start; + DatabaseNode *bestmatch= 0; + int i; + int x= fca->x; + + for (;;) { + debug_flush(); + debugf(" | x=%d",x); + if (x > fca->w) break; + Pixcol cv= fca->cols[x]; + debugf(" cv=%"PSPIXCOL(PRIx),cv); + for (i=0; inlinks; i++) + if (current->links[i].col == cv) + goto found; + /* not found */ + debugf(" ?"); + break; + + found: + current= current->links[i].then; + if (current->match) { + debugf(" \"%s\"%s",current->str,current->endsword?"_":""); + bestmatch= current; + *matchx_r= x; + } else { + debugf(" ..."); + } + + x++; + } + return bestmatch; +} + +static DatabaseNode *findchar(const FindCharArgs *fca, + int *match_rx, int *match_rctxi) { + FindCharResults results[NCONTEXTS]; + int ctxi, match=-1, nmatches=0; + + debugf("OCR lx=%d ct_state=%x ", fca->x, fca->ctxmap); + for (ctxi=0; ctxictxmap & (1u << ctxi))) continue; + debugf(" || %s",context_names[ctxi]); + + results[ctxi].match= findchar_1ctx(fca, &fca->rd->contexts[ctxi], + &results[ctxi].rx); + if (!results[ctxi].match) continue; + + match= ctxi; + nmatches++; + } + if (nmatches==1) { + debugf(" unique"); + } else { + debugf(" ambiguous"); + match= !fca->ct->findchar_select ? -1 : + fca->ct->findchar_select(fca,results); + debugf(" resolved %s", match<0 ? "" : context_names[match]); + } + if (match<0) + return 0; + + *match_rx= results[match].rx; + if (match_rctxi) *match_rctxi= match; + return results[match].match; +} + +static int findchar_select_text(const FindCharArgs *fca, + const FindCharResults results[]) { + if (fca->ctxmap != 017) return -1; + + dbassert(! results[ct_Digit].match ); + if (results[ct_Word].match) return ct_Word; + if (results[ct_Lower].rx > results[ct_Upper].rx) return ct_Lower; + if (results[ct_Upper].rx > results[ct_Lower].rx) return ct_Upper; + return -1; +} + const struct OcrCellTypeInfo ocr_celltype_number= { - 4,4,4 + ctf_Digit, ctf_Digit, ctf_Digit, + .space_spaces= 5, + .name= "number", + .findchar_select= 0 }; const struct OcrCellTypeInfo ocr_celltype_text= { - .initial=2 /* Uppercase */, - .nextword=3 /* Either */, - .midword=1 /* Lower only */ + .initial= ctf_Digit | ctf_Upper, + .nextword= ctf_Digit | ctf_Upper | ctf_Lower | ctf_Word, + .midword= ctf_Digit | ctf_Lower, + .space_spaces= 4, + .name= "text", + .findchar_select= findchar_select_text }; + +const char *ocr_celltype_name(OcrCellType ct) { return ct->name; } + OcrResultGlyph *ocr(OcrReader *rd, OcrCellType ct, int w, Pixcol cols[]) { int nspaces; - unsigned ctxmap; - int ctxi, i, x; + int x; + + FindCharArgs fca; + fca.rd= rd; + fca.ct= ct; + fca.w= w; + fca.cols= cols; + fca.x= -1; restart: nspaces=- w; - ctxmap= ct->initial; + fca.ctxmap= ct->initial; rd->nresults=0; debugf("OCR h=%d w=%d",rd->h,w); for (x=0; xspace_spaces) { debugf("OCR x=%x nspaces=%d space\n",x,nspaces); - ctxmap= ct->nextword; + fca.ctxmap= ct->nextword; } continue; } /* something here, so we need to add the spaces */ - if (nspaces>=SPACE_SPACES) - add_result(rd," ",x-nspaces,x+1,0); + if (nspaces >= ct->space_spaces) + add_result(rd," ",x-nspaces,x+1,-1,0); nspaces=0; - /* find character */ - int lx=x; + fca.x= x; - DatabaseNode *uniquematch= 0; - int uniquematch_rx=-1; + int match_rx=-1; + int match_ctxi=-1; + DatabaseNode *match= findchar(&fca, &match_rx, &match_ctxi); - debugf("OCR lx=%d ctxmap=%x ",lx,ctxmap); - - for (ctxi=0; ctxicontexts[ctxi];; - DatabaseNode *bestmatch= 0; - int bestmatch_rx=-1; - - x= lx; - if (!(ctxmap & (1u << ctxi))) continue; - debugf(" || %s",context_names[ctxi]); - - for (;;) { - debug_flush(); - debugf(" | x=%d",x); - if (x>w) break; - Pixcol cv= cols[x]; - debugf(" cv=%"PSPIXCOL(PRIx),cv); - for (i=0; inlinks; i++) - if (current->links[i].col == cv) - goto found; - /* not found */ - debugf(" ?"); - break; - - found: - current= current->links[i].then; - if (current->s[0]) { - debugf(" \"%s\"",current->s); - bestmatch= current; - bestmatch_rx= x; - } else { - debugf(" ..."); - } - - x++; + if (match) { + debugf(" || YES"); + add_result(rd, match->str, x, match_rx, match_ctxi, fca.ctxmap); + x= match_rx+1; + if (match->match) fca.ctxmap= ct->midword; + else debugf(" (empty)"); + if (match->endsword) { + nspaces= ct->space_spaces; + debugf("_"); + fca.ctxmap= ct->nextword; } - - if (bestmatch) { - if (uniquematch && strcmp(bestmatch->s, uniquematch->s)) { - debugf( " ambiguous"); - uniquematch= 0; - break; - } - uniquematch= bestmatch; - uniquematch_rx= bestmatch_rx; - } - } - - if (uniquematch) { - debugf(" || YES\n"); - add_result(rd, uniquematch->s, lx, uniquematch_rx, ctxmap); - x= uniquematch_rx+1; - ctxmap= ct->midword; + debugf("\n"); } else { int rx; debugf(" || UNKNOWN"); - for (rx=lx; rxnresults); debug_flush(); return rd->results; @@ -405,9 +471,132 @@ OcrResultGlyph *ocr(OcrReader *rd, OcrCellType ct, int w, Pixcol cols[]) { OcrReader *ocr_init(int h) { OcrReader *rd; - rd= malloc(sizeof(*rd)); eassert(rd); + if (o_flags & ff_dict_fetch) { + char *fetchfile= masprintf("char%d",h); + progress("Updating %s...",fetchfile); + fetch_with_rsync(fetchfile); + free(fetchfile); + } + + rd= mmalloc(sizeof(*rd)); memset(rd,0,sizeof(*rd)); rd->h= h; readdb(rd); return rd; } + +/*---------- character set dump ----------*/ + +static void show_recurse(const DatabaseNode *t, int *count, + const DatabaseNode **store_ary) { + if (t->defined) { + if (store_ary) store_ary[*count]= t; + (*count)++; + } + int l; + for (l=0; lnlinks; l++) + show_recurse(t->links[l].then, count,store_ary); +} + +static int show_char_compar(const void *av, const void *bv) { + const DatabaseNode *const *ap= av; const DatabaseNode *a= *ap; + const DatabaseNode *const *bp= bv; const DatabaseNode *b= *bp; + return strcmp(a->str, b->str) ?: + ((int)a->match - (int)b->match) ?: + ((int)a->endsword - (int)b->endsword) ?: + ((int)a->local - (int)b->local) ?: + 0; +} + +void ocr_showcharsets(void) { + DIR *d; + struct dirent *de; + char found[32]; + pcre *fnpat; + int matchvec[10]; + char hbuf[10]; + const char *pcre_err; + int pcre_erroffset; + + memset(found,0,sizeof(found)); + + fnpat= pcre_compile("\\#(?:master|local)\\-char([1-9]\\d{0,2})\\#\\.txt$", + PCRE_ANCHORED|PCRE_DOLLAR_ENDONLY, + &pcre_err,&pcre_erroffset, 0); + debugf("pcre_compile %p %s\n",fnpat,pcre_err); + assert(fnpat); + + sysassert( d= opendir(get_vardir()) ); + for (;;) { + errno=0; de= readdir(d); if (!de) break; + + int rer= pcre_exec(fnpat,0, de->d_name,strlen(de->d_name), 0,0, + matchvec,ARRAYSIZE(matchvec)); + debugf("pcre_exec `%s' => %d\n", de->d_name,rer); + + if (rer==PCRE_ERROR_NOMATCH || rer==PCRE_ERROR_BADUTF8) continue; + assert(rer==2); + + rer= pcre_copy_substring(de->d_name,matchvec,rer, 1, hbuf,sizeof(hbuf)); + debugf("pcre_copy_substring => %d\n", rer); + assert(rer>0); + + int h= atoi(hbuf); + if (h >= ARRAYSIZE(found)) continue; + + found[h]= 1; + } + + int h; + for (h=0; hcontexts[ctxi], &nchars, 0); + const DatabaseNode **chars= mmalloc(sizeof(*chars) * nchars); + int chari= 0; + show_recurse(&rd->contexts[ctxi], &chari, chars); + assert(chari==nchars); + qsort(chars, nchars, sizeof(*chars), show_char_compar); + + int local; + for (local=0; local<2; local++) { + printf("%2d %-6s %-6s ", h, context_names[ctxi], + local?"local":"master"); + for (chari=0; chari"; + + if (t->local != local) continue; + + if (!t->match) + printf(" [nomatch]"); + else if (!t->endsword && strspn(t->str, accept) == strlen(t->str)) + printf(" %s",t->str); + else { + printf(" \""); + char *p= t->str; + int c; + while ((c=*p++)) { + if (c=='"' || c=='\\') printf("\\%c",c); + else if (c>=' ' && c<=126) putchar(c); + else printf("\\x%02x", (unsigned char)c); + } + if (t->endsword) putchar(' '); + putchar('"'); + } + } + putchar('\n'); + } + free(chars); + } + } +}