#include #include #include #include #include extern const char *__progname; typedef enum { T_PBM = 'b', T_PGM = 'g', T_PPM = 'p', T_PAM = 'a', T_RPBM = 'B', T_RPGM = 'G', T_RPPM = 'P', T_RPAM = 'A' } FILECLASS; typedef struct fdesc FDESC; typedef struct pixval PIXVAL; typedef struct idesc IDESC; typedef struct box BOX; typedef struct link LINK; struct box { int beg; int end; } ; struct pixval { unsigned char r; unsigned char g; unsigned char b; } ; struct idesc { FILECLASS class; unsigned int maxval; /* zero for PBM */ unsigned int maxval2; /* zero for non-PAM */ } ; struct fdesc { IDESC d; const char *fn; FILE *f; unsigned int w; unsigned int h; unsigned char rpbmbuf; unsigned char rpbmbit; } ; struct link { LINK *link; PIXVAL colour; int x1; int y1; int x2; int y2; } ; static FDESC ifile; static int w; static int h; static PIXVAL *pixels; static double *x_margin; static double *y_margin; static const PIXVAL bar = { .r=125, .g=94, .b=62 }; static const double linecutoff = 10; static const int bgcutoff = 40; static int nboxes_x; static int (*boxes_x)[2]; static int maxbox_x; static int nboxes_y; static int (*boxes_y)[2]; static int maxbox_y; static signed char **cells; static PIXVAL *pixlist; static int maxpixlist; static int *pixcounts; static LINK *links; static void badpnm(FDESC *, const char *, ...) __attribute__((__noreturn__)); static void badpnm(FDESC *d, const char *fmt, ...) { va_list ap; va_start(ap,fmt); fprintf(stderr,"%s: %s: bad pnm file: ",__progname,d->fn); vfprintf(stderr,fmt,ap); fprintf(stderr,"\n"); va_end(ap); exit(1); } static int pnmskipcomments(FDESC *d) { int c; while (1) { c = getc(d->f); if (isspace(c)) continue; if (c == '#') { do { c = getc(d->f); } while ((c != '\n') && (c != EOF)); continue; } return(c); } } #define digitval(c) (((int)(c))-'0') static unsigned int pnmgetnum(FDESC *d, const char *what) { int c; unsigned int v; v = 0; c = pnmskipcomments(d); if (c == EOF) badpnm(d,"EOF while reading %s",what); if (! isdigit(c)) badpnm(d,"non-digit when reading %s",what); v = digitval(c); while (1) { c = getc(d->f); if (! isdigit(c)) break; v = (v * 10) + digitval(c); } ungetc(c,d->f); return(v); } static int class_is_raw(FILECLASS class) { switch (class) { case T_PBM: case T_PGM: case T_PPM: case T_PAM: return(0); break; case T_RPBM: case T_RPGM: case T_RPPM: case T_RPAM: return(1); break; } abort(); } static void skip1white(FDESC *d) { int c; c = getc(d->f); if (! isspace(c)) ungetc(c,d->f); } static void init_input(FDESC *d) { int c; d->fn = "standard input"; d->f = stdin; c = getchar(); if (c != 'P') badpnm(d,"bad magic number"); c = getchar(); switch (c) { case '1': d->d.class = T_PBM; break; case '2': d->d.class = T_PGM; break; case '3': d->d.class = T_PPM; break; case '7': d->d.class = T_PAM; break; case '4': d->d.class = T_RPBM; break; case '5': d->d.class = T_RPGM; break; case '6': d->d.class = T_RPPM; break; case '8': d->d.class = T_RPAM; break; default: badpnm(d,"bad magic number"); break; } d->w = pnmgetnum(d,"width"); d->h = pnmgetnum(d,"height"); d->d.maxval = 0; d->d.maxval2 = 0; d->rpbmbuf = 0; d->rpbmbit = 0; switch (d->d.class) { case T_PGM: case T_PPM: case T_PAM: case T_RPGM: case T_RPPM: case T_RPAM: d->d.maxval = pnmgetnum(d,"maxval"); break; case T_PBM: case T_RPBM: d->d.maxval = 255; break; default: break; } switch (d->d.class) { case T_PAM: case T_RPAM: d->d.maxval2 = pnmgetnum(d,"maxval2"); break; default: break; } if (class_is_raw(d->d.class)) skip1white(d); } static int pnmgetbit(FDESC *d) { int c; unsigned int v; v = 0; c = pnmskipcomments(d); if (c == EOF) badpnm(d,"EOF while reading pixel value"); switch (c) { case '0': return(0); break; case '1': return(1); break; } badpnm(d,"invalid pixel character"); } static void dataeof(FDESC *) __attribute__((__noreturn__)); static void dataeof(FDESC *d) { fprintf(stderr,"%s: %s: EOF while reading pixels\n",__progname,d->fn); exit(1); } static unsigned int getrawval(FDESC *d) { int c; c = getc(d->f); if (c == EOF) dataeof(d); return(c); } static PIXVAL pnmgetpixel(FDESC *d) { int r; int g; int b; switch (d->d.class) { default: abort(); break; case T_PBM: { int v; v = pnmgetbit(d); if (0) { case T_RPBM: if (d->rpbmbit < 2) { v = getc(d->f); if (v == EOF) dataeof(d); d->rpbmbuf = v; d->rpbmbit = 0x80; v &= 0x80; } else { v = d->rpbmbuf & (d->rpbmbit >>= 1); } } r = v ? 255 : 0; } break; case T_PGM: r = pnmgetnum(d,"pixel value"); break; case T_RPGM: r = getrawval(d); break; case T_PPM: r = pnmgetnum(d,"pixel value"); g = pnmgetnum(d,"pixel value"); b = pnmgetnum(d,"pixel value"); break; case T_RPPM: r = getrawval(d); g = getrawval(d); b = getrawval(d); break; case T_PAM: r = pnmgetnum(d,"pixel value"); g = pnmgetnum(d,"pixel value"); b = pnmgetnum(d,"pixel value"); pnmgetnum(d,"pixel value"); break; case T_RPAM: r = getrawval(d); g = getrawval(d); b = getrawval(d); getrawval(d); break; } if (d->d.maxval != 255) { r = (r * 255) / d->d.maxval; g = (g * 255) / d->d.maxval; b = (b * 255) / d->d.maxval; } if (r < 0) r = 0; else if (r > 255) r = 255; if (g < 0) g = 0; else if (g > 255) g = 255; if (b < 0) b = 0; else if (b > 255) b = 255; return((PIXVAL){.r=r,.g=g,.b=b}); } static void read_input(void) { int i; PIXVAL *pp; w = ifile.w; h = ifile.h; pixels = malloc(w*h*sizeof(PIXVAL)); pp = pixels; for (i=w*h;i>0;i--) *pp++ = pnmgetpixel(&ifile); } static void compute_margins(void) { int x; int y; PIXVAL *pp; double d; x_margin = malloc(w*sizeof(double)); y_margin = malloc(h*sizeof(double)); for (x=w-1;x>=0;x--) x_margin[x] = 0; for (y=h-1;y>=0;y--) y_margin[y] = 0; pp = pixels + (w * h); for (y=h-1;y>=0;y--) for (x=w-1;x>=0;x--) { pp --; d = fabs(.299*((int)pp->r-(int)bar.r)) + fabs(.587*((int)pp->g-(int)bar.g)) + fabs(.114*((int)pp->b-(int)bar.b)); x_margin[x] += d; y_margin[y] += d; } for (x=w-1;x>=0;x--) x_margin[x] /= h; for (y=h-1;y>=0;y--) y_margin[y] /= w; } static void find_boxes(double *margin, int mc, int *np, int (**boxp)[2], int *maxp) { int i; int n; int i0; int (*b)[2]; int maxw; n = 0; i0 = -1; for (i=0;i linecutoff) { if (i0 < 0) { i0 = i; } } else { if (i0 >= 0) { n ++; i0 = -1; } } } b = malloc(n*sizeof(int [2])); *np = n; *boxp = b; maxw = 0; n = 0; for (i=0;i linecutoff) { if (i0 < 0) { i0 = i; } } else { if (i0 >= 0) { b[n][0] = i0; b[n][1] = i - 1; if (i-i0 > maxw) maxw = i - i0; n ++; i0 = -1; } } } if (n != *np) abort(); *maxp = maxw; } static void find_lines(void) { find_boxes(&x_margin[0],w,&nboxes_x,&boxes_x,&maxbox_x); find_boxes(&y_margin[0],h,&nboxes_y,&boxes_y,&maxbox_y); } static void extract_data(void) { int cx; int cy; int n; int p0x; int p1x; int p0y; int p1y; int px; int py; int i; int j; int mr; int mg; int mb; LINK *l; maxpixlist = maxbox_x * maxbox_y; pixlist = malloc(maxpixlist*sizeof(PIXVAL)); pixcounts = malloc(maxpixlist*sizeof(int)); cells = malloc(nboxes_x*sizeof(*cells)); cells[0] = malloc(nboxes_x*nboxes_y*sizeof(**cells)); for (i=1;i=0;cx--) for (cy=nboxes_y-1;cy>=0;cy--) { p0x = rint( (boxes_x[cx][0] * .65) + (boxes_x[cx][1] * .35) ); p1x = rint( (boxes_x[cx][0] * .35) + (boxes_x[cx][1] * .65) ); p0y = rint( (boxes_y[cy][0] * .65) + (boxes_y[cy][1] * .35) ); p1y = rint( (boxes_y[cy][0] * .35) + (boxes_y[cy][1] * .65) ); if ((p1x-p0x > maxbox_x) || (p1y-p0y > maxbox_y)) abort(); n = 0; j = 0; for (px=p0x;px (py=p0y;py; } } pixlist[n] = pv; pixcounts[n] = 1; n ++; } do { j = 0; for (i=1;i pixlist[i].r) || ( (pixlist[i-1].r == pixlist[i].r) && ( (pixlist[i-1].g > pixlist[i].g) || ( (pixlist[i-1].g == pixlist[i].g) && (pixlist[i-1].b > pixlist[i].b) ) ) ) ) { PIXVAL pt; int it; pt = pixlist[i-1]; it = pixcounts[i-1]; pixlist[i-1] = pixlist[i]; pixcounts[i-1] = pixcounts[i]; pixlist[i] = pt; pixcounts[i] = it; j = 1; } } } while (j); do <"nextcell"> { do <"realcell"> { for (i=n-1;i>=0;i--) { if ( (pixlist[i].r > bgcutoff) || (pixlist[i].g > bgcutoff) || (pixlist[i].b > bgcutoff) ) break <"realcell">; } break <"nextcell">; } while (0); mr = 0; mg = 0; mb = 0; for (i=n-1;i>=0;i--) { mr += pixlist[i].r; mg += pixlist[i].g; mb += pixlist[i].b; } mr /= n; mg /= n; mb /= n; for (l=links;l;l=l->link) { if ((l->colour.r == mr) && (l->colour.g == mg) && (l->colour.b == mb)) { if (l->x2 < 0) { l->x2 = cx; l->y2 = cy; break <"nextcell">; } else { fprintf(stderr,"colour (%d,%d,%d) extra: (%d,%d), (%d,%d), and (%d,%d)\n", mr,mg,mb,l->x1,l->y1,l->x2,l->y2,cx,cy); exit(1); } } } l = malloc(sizeof(LINK)); l->colour.r = mr; l->colour.g = mg; l->colour.b = mb; l->x1 = cx; l->y1 = cy; l->x2 = -1; l->link = links; links = l; } while (0); } for (l=links;l;l=l->link) { if (l->x2 < 0) { fprintf(stderr,"colour (%d,%d,%d) only one: (%d,%d)\n", l->colour.r,l->colour.g,l->colour.b,l->x1,l->y1); exit(1); } } if (nboxes_x == nboxes_y) printf("%d",nboxes_x); else printf("%dx%d",nboxes_x,nboxes_y); for (l=links;l;l=l->link) { printf(" %d", (((((l->y2 * nboxes_x) + l->x2) * nboxes_y) + l->y1) * nboxes_x) + l->x1); } printf("\n"); } int main(void); int main(void) { init_input(&ifile); read_input(); compute_margins(); find_lines(); extract_data(); return(0); }