#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

typedef struct {
  double x, y;
} point;

typedef struct {
  int startw, endw, startl, endl;
} stem;

typedef struct {
  int width, height;
  unsigned char *pix;
} image;

static int nextchar(FILE* f)
{
  int c;

  do {
    c = fgetc(f);
    if (c == '#') {
      do {
	c = fgetc(f);
      } while (c != '\n' && c != '\r' && c != EOF);
    }
  } while (c <= ' ');

  return c;
}

static int readint(FILE* f, int* dest)
{
  int c;

  c = nextchar(f);
  if (c < '0' || c > '9')
    return 1;

  *dest = c - '0';
  while (1) {
    c = fgetc(f);
    if (c >= '0' && c <= '9')
      *dest = (*dest * 10) + c - '0';
    else {
      ungetc(c, f);
      return 0;
    }
  }
}

static int readbinint(FILE* f, int* dest, int i16)
{
  int c = fgetc(f);
  if (c == EOF)
    return 1;
  *dest = c;

  if (i16) {
    c = fgetc(f);
    if (c == EOF)
      return 1;
    *dest = (*dest * 256) + c;
  }
  return 0;
}

static int parsepnm(image* img, FILE* f)
{
  int type, limit, c, r, t;
  int x, y, i;
  unsigned char v, buf;

  c = nextchar(f);
  if (c != 'P')
    return 1;

  if (readint(f, &type))
    return 1;
  if (type < 1 || type > 6)
    return 1;

  if (readint(f, &img->width))
    return 1;
  if (readint(f, &img->height))
    return 1;

  if (type != 1 && type != 4) {
    if (readint(f, &limit))
      return 1;
    if (type == 3 || type == 6)
      limit *= 3;
  }

  fgetc(f);

  img->pix = malloc(img->width * img->height);
  if (!img->pix)
    return 1;

  for (i = y = 0; y < img->height; y++) {
    for (x = 0; x < img->width; x++) {
      switch (type) {
      case 1:
	if (readint(f, &r))
	  return 1;
	v = (r ? 255 : 0);
	break;

      case 2:
	if (readint(f, &r))
	  return 1;
	if (r >= limit)
	  v = 255;
	else
	  v = (r * 255 + limit/2) / limit;
	break;

      case 3:
	r = 0;
	for (c = 0; c < 3; c++) {
	  if (readint(f, &t))
	    return 1;
	  r += t;
	}
	if (r >= limit)
	  v = 255;
	else
	  v = (r * 255 + limit/2) / limit;
	break;

      case 4:
	if (x % 8 == 0) {
	  c = fgetc(f);
	  if (c == EOF)
	    return 1;
	  buf = c;
	}
	else 
	  buf <<= 1;
	v = ((buf & 0x80) ? 255 : 0);
	break;

      case 5:
	if (readbinint(f, &r, limit >= 256))
	  return 1;
	if (r >= limit)
	  v = 255;
	else
	  v = (r * 255 + limit/2) / limit;
	break;

      case 6:
	r = 0;
	for (c = 0; c < 3; c++) {
	  if (readbinint(f, &t, limit >= 768))
	    return 1;
	  r += t;
	}
	if (r >= limit)
	  v = 255;
	else
	  v = (r * 255 + limit/2) / limit;
	break;
      }

      img->pix[i] = v;
      i++;
    }
  }

  return 0;
}

static int openpnm(image* img, const char* name)
{
  FILE* f;

  f = fopen(name, "rb");
  if (!f) {
    perror(name);
    return 1;
  }

  if (parsepnm(img, f)) {
    fprintf(stderr, "%s: error reading image\n", name);
    fclose(f);
    return 1;
  }

  fclose(f);
  return 0;
}

static int getpix(const image* img, int x, int y)
{
  if (x < 0)
    x = 0;
  if (x >= img->width)
    x = img->width - 1;
  if (y < 0)
    y = 0;
  if (y >= img->height)
    y = img->height - 1;
  return (img->pix[y * img->width + x]);
}

static double getsubpix(const image* img, double x, double y)
{
  int ix, iy;
  double fx, fy;
  double sa, sb, sc, sd;

  ix = x;
  iy = y;
  fx = x - ix;
  fy = y - iy;

  sa = getpix(img, ix, iy);
  sb = getpix(img, ix + 1, iy);
  sc = getpix(img, ix, iy + 1);
  sd = getpix(img, ix + 1, iy + 1);

  return ((sa * (1 - fx) + sb * fx) * (1 - fy)
	  + (sc * (1 - fx) + sd * fx) * fy);
}

static void pointweight(point* dest, const point* a, const point* b,
			double f)
{
  dest->x = (a->x * (1.0 - f)) + (b->x * f);
  dest->y = (a->y * (1.0 - f)) + (b->y * f);
}


#define YSAMPLES 24
#define XSAMPLES 24

#define YSKIP 2
#define XSKIP 2

#define MINHSTEM 10
#define MINVSTEM 7

#define MINHWIDTH 2
#define MINVWIDTH 2
#define MAXHWIDTH 10
#define MAXVWIDTH 10

#define MAXSTEMS 50

static void mergestems(stem* stems, int* nstems)
{
  int i, j, k;

  for (i = 0; i < *nstems; i++) {
    for (j = 0; j < i; j++) {
      if (stems[i].startw <= stems[j].endw
	  && stems[j].startw <= stems[i].endw
	  && stems[i].startl < stems[j].endl
	  && stems[j].startl < stems[i].endl) {

	if (stems[i].startl < stems[j].startl)
	  stems[j].startl = stems[i].startl;
	if (stems[i].endl > stems[j].endl)
	  stems[j].endl = stems[i].endl;
	if (stems[i].startw < stems[j].startw)
	  stems[j].startw = stems[i].startw;
	if (stems[i].endw > stems[j].endw)
	  stems[j].endw = stems[i].endw;

	(*nstems)--;
	for (k = i; k < *nstems; k++)
	  stems[k] = stems[k + 1];

	i = 0;
	break;
      }
    }
  }
}

#define L_LEFT           1
#define L_VCENTER        2
#define L_RIGHT          4
#define L_TOP            8
#define L_HCENTER       16
#define L_BOTTOM        32  
#define M_TOPLEFT       64
#define M_TOPRIGHT     128
#define M_BOTTOMLEFT   256
#define M_BOTTOMRIGHT  512
#define M_LEFTCENTER  1024
#define M_RIGHTCENTER 2048

static const int A_stems[] = { L_LEFT, L_RIGHT,
			       L_TOP, L_HCENTER };

static const int B_stems[] = { L_LEFT,
			       L_RIGHT | M_TOPRIGHT,
			       L_RIGHT | M_BOTTOMRIGHT,
			       L_TOP, L_HCENTER, L_BOTTOM };

static const int C_stems[] = { L_LEFT,
			       L_TOP, L_BOTTOM };

static const int D_stems[] = { L_LEFT, L_RIGHT,
			       L_TOP, L_BOTTOM };

static const int E_stems[] = { L_LEFT,
			       L_TOP, L_HCENTER, L_BOTTOM };

static const int F_stems[] = { L_LEFT,
			       L_TOP, L_HCENTER };

static const int H_stems[] = { L_LEFT, L_RIGHT,
			       L_HCENTER };

static const int I_stems[] = { L_VCENTER,
			       L_TOP, L_BOTTOM };

static const int L_stems[] = { L_LEFT,
			       L_BOTTOM };

static const int S_stems[] = { M_TOPLEFT, M_BOTTOMRIGHT,
			       L_TOP, L_HCENTER, L_BOTTOM };

static const int T_stems[] = { L_VCENTER,
			       L_TOP };

static const int U_stems[] = { L_LEFT, L_RIGHT,
			       L_BOTTOM };

static const int b_stems[] = { L_LEFT, M_BOTTOMRIGHT,
			       L_HCENTER | M_RIGHTCENTER, L_BOTTOM };

static const int d_stems[] = { M_BOTTOMLEFT, L_RIGHT,
			       L_HCENTER | M_LEFTCENTER, L_BOTTOM };

static const int h_stems[] = { L_LEFT, M_BOTTOMRIGHT,
			       L_HCENTER | M_RIGHTCENTER };

static const int n_stems[] = { M_BOTTOMLEFT, M_BOTTOMRIGHT,
			       L_HCENTER | M_RIGHTCENTER };

#define COUNT(x) (sizeof(x) / sizeof(x[0]))

static const char codechars[] = "ABCDEFHILSTUbdhn";

static const struct {
  const int *stemmasks;
  int nstemmasks;
} charinfo[16] = { { A_stems, COUNT(A_stems) },
		   { B_stems, COUNT(B_stems) },
		   { C_stems, COUNT(C_stems) },
		   { D_stems, COUNT(D_stems) },
		   { E_stems, COUNT(E_stems) },
		   { F_stems, COUNT(F_stems) },
		   { H_stems, COUNT(H_stems) },
		   { I_stems, COUNT(I_stems) },
		   { L_stems, COUNT(L_stems) },
		   { S_stems, COUNT(S_stems) },
		   { T_stems, COUNT(T_stems) },
		   { U_stems, COUNT(U_stems) },
		   { b_stems, COUNT(b_stems) },
		   { d_stems, COUNT(d_stems) },
		   { h_stems, COUNT(h_stems) },
		   { n_stems, COUNT(n_stems) } };

static void getstemcat(const stem* s,
		       int w1, int w2, int w3, int w4,
		       int l1, int l2, int l3, int l4,
		       int* wc, int* slc, int* elc)
{
  if (s->startw <= w1)
    *wc = 0;
  else if (s->endw >= w4)
    *wc = 4;
  else if ((s->startw + s->endw) / 2 < w2)
    *wc = 1;
  else if ((s->startw + s->endw) / 2 > w3)
    *wc = 3;
  else
    *wc = 2;

  if (s->startl <= l1)
    *slc = 0;
  else if (s->startl >= l4)
    *slc = 4;
  else if (s->startl < l2)
    *slc = 1;
  else if (s->startl > l3)
    *slc = 3;
  else
    *slc = 2;

  if (s->endl <= l1)
    *elc = 0;
  else if (s->endl >= l4)
    *elc = 4;
  else if (s->endl < l2)
    *elc = 1;
  else if (s->endl > l3)
    *elc = 3;
  else
    *elc = 2;
}

#define Hw1 (YSAMPLES / 8)
#define Hw2 (YSAMPLES / 4)
#define Hw3 ((YSAMPLES * 3) / 4)
#define Hw4 ((YSAMPLES * 7) / 8)
#define Hl1 (XSAMPLES / 5)
#define Hl2 (XSAMPLES / 3)
#define Hl3 ((XSAMPLES * 2) / 3)
#define Hl4 ((XSAMPLES * 4) / 5)

#define Vw1 (XSAMPLES / 8)
#define Vw2 (XSAMPLES / 3)
#define Vw3 ((XSAMPLES * 2) / 3)
#define Vw4 ((XSAMPLES * 7) / 8)
#define Vl1 (YSAMPLES / 6)
#define Vl2 (YSAMPLES / 5)
#define Vl3 ((YSAMPLES * 2) / 3)
#define Vl4 ((YSAMPLES * 3) / 4)

#ifdef DEBUG
# define DBG(x...) fprintf(stderr, x)
#else
# define DBG(x...) /*  */
#endif

static char xchr(const image* img,
		 const point* tl, const point* tr,
		 const point* bl, const point* br)
{
  int i, j, k, c;
  point start, end, p;
  double samp[XSAMPLES * YSAMPLES];
  int dark[XSAMPLES * YSAMPLES], lastdark;
  double s, mean, sd, min, max, threshold, hyst;
  stem vstems[MAXSTEMS], hstems[MAXSTEMS];
  int nvstems, nhstems, stemstart;
  int wc, slc, elc;
  int stem_mask, stem_used_mask, unknown_count;
  int score, bestscore, bestchar, nbest;

  mean = 0.0;

  for (i = 0; i < YSAMPLES; i++) {
    pointweight(&start, tl, bl, ((double) (i + YSKIP)
				 / (YSAMPLES - 1 + 2 * YSKIP)));
    pointweight(&end, tr, br, ((double) (i + YSKIP)
			       / (YSAMPLES - 1 + 2 * YSKIP)));
    for (j = 0; j < XSAMPLES; j++) {
      pointweight(&p, &start, &end, ((double) (j + XSKIP)
				     / (XSAMPLES - 1 + 2 * XSKIP)));
      s = getsubpix(img, p.x, p.y);
      samp[i * XSAMPLES + j] = s;
      mean += s;
    }
  }

  mean /= XSAMPLES * YSAMPLES;
  sd = 0.0;
  for (i = 0; i < YSAMPLES * XSAMPLES; i++)
    sd += (samp[i] - mean) * (samp[i] - mean);
  sd = sqrt(sd / (YSAMPLES * XSAMPLES));

  max = 0.0;
  min = 255.0;
  for (i = 0; i < YSAMPLES * XSAMPLES; i++) {
    if (samp[i] > max && samp[i] < mean + 2 * sd)
      max = samp[i];
    if (samp[i] < min && samp[i] > mean - 2 * sd)
      min = samp[i];
  }

  threshold = (max + min) * 0.5;
  hyst = (max - min) / 32;

  DBG("mean = %g, sd = %g, min = %g, max = %g, thresh = %g, hyst = %g\n",
      mean, sd, min, max, threshold, hyst);

  for (i = 0; i < YSAMPLES; i++) {
    lastdark = 0;
    for (j = 0; j < XSAMPLES; j++) {
      s = samp[i * XSAMPLES + j];
      if (lastdark) {
	if (s >= threshold + hyst)
	  lastdark = 0;
      }
      else {
	if (s <= threshold - hyst)
	  lastdark = 1;
      }
      dark[i * XSAMPLES + j] = lastdark;
    }
  }

  /* find vertical stems */
  nvstems = 0;
  for (j = 0; j < XSAMPLES; j++) {
    stemstart = 0;

    for (i = 0; i <= YSAMPLES; i++) {
      if (i == YSAMPLES
	  || !dark[i * XSAMPLES + j]) {

	if (i - stemstart >= MINVSTEM && nvstems < MAXSTEMS) {
	  nvstems++;
	  vstems[nvstems - 1].startw = j;
	  vstems[nvstems - 1].endw = j + 1;
	  vstems[nvstems - 1].startl = stemstart;
	  vstems[nvstems - 1].endl = i;
	}

	stemstart = i;
      }
    }
  }

  mergestems(vstems, &nvstems);

  /* find horizontal stems */
  nhstems = 0;
  for (i = 0; i < YSAMPLES; i++) {
    stemstart = 0;

    for (j = 0; j <= XSAMPLES; j++) {
      if (j == XSAMPLES
	  || !dark[i * XSAMPLES + j]) {

	if (j - stemstart >= MINHSTEM && nhstems < MAXSTEMS) {
	  nhstems++;
	  hstems[nhstems - 1].startw = i;
	  hstems[nhstems - 1].endw = i + 1;
	  hstems[nhstems - 1].startl = stemstart;
	  hstems[nhstems - 1].endl = j;
	}

	stemstart = j;
      }
    }
  }

  mergestems(hstems, &nhstems);

#ifdef DEBUG
  for (i = 0; i < YSAMPLES; i++) {
    for (j = 0; j < XSAMPLES; j++) {
      c = (dark[i * XSAMPLES + j] ? '#' : ' ');

      for (k = 0; k < nvstems && k < MAXSTEMS; k++) {
	if ((vstems[k].startw == j || vstems[k].endw == j + 1)
	    && vstems[k].startl <= i && vstems[k].endl > i) {
	  c = '|';
	  break;
	}
      }

      for (k = 0; k < nhstems && k < MAXSTEMS; k++) {
	if ((hstems[k].startw == i || hstems[k].endw == i + 1)
	    && hstems[k].startl <= j && hstems[k].endl > j) {
	  if (c == '|')
	    c = '+';
	  else
	    c = '-';
	}
      }

      fputc(c, stderr);
    }
    fputc('\n', stderr);
  }
#endif

  /* classify stems by position */

  stem_mask = 0;
  unknown_count = 0;

  DBG("V:");

  for (k = 0; k < nvstems; k++) {
    if (vstems[k].endw - vstems[k].startw > MAXVWIDTH) {
      DBG(" WIDE");
      unknown_count++;
    }
    else if (vstems[k].endw - vstems[k].startw < MINVWIDTH) {
      DBG(" NARROW");
    }
    else {
      getstemcat(&vstems[k], Vw1, Vw2, Vw3, Vw4,
		 Vl1, Vl2, Vl3, Vl4, &wc, &slc, &elc);
      if ((slc == 0 && elc >= 3)
	  || (slc <= 1 && elc == 4)) {
	if (wc == 0) {
	  DBG(" left");
	  stem_mask |= L_LEFT;
	}
	else if (wc == 2) {
	  DBG(" ctr");
	  stem_mask |= L_VCENTER;
	}
	else if (wc == 4) {
	  DBG(" right");
	  stem_mask |= L_RIGHT;
	}
	else {
	  DBG(" UNKNOWN");
	  unknown_count++;
	}
      }
      else if (wc == 0 && slc == 0 && elc == 2) {
	DBG(" top-left");
	stem_mask |= M_TOPLEFT;
      }
      else if (wc == 0 && slc == 2 && elc == 4) {
	DBG(" btm-left");
	stem_mask |= M_BOTTOMLEFT;
      }
      else if (wc == 4 && slc == 0 && elc == 2) {
	DBG(" top-right");
	stem_mask |= M_TOPRIGHT;
      }
      else if (wc == 4 && slc == 2 && elc == 4) {
	DBG(" btm-right");
	stem_mask |= M_BOTTOMRIGHT;
      }
      else if (slc == elc || slc == elc - 1) {
	DBG(" SHORT");
      }
      else {
	DBG(" UNKNOWN");
	unknown_count++;
      }
    }
  }

  DBG("\nH:");

  for (k = 0; k < nhstems; k++) {
    if (hstems[k].endw - hstems[k].startw > MAXHWIDTH) {
      DBG(" WIDE");
      unknown_count++;
    }
    else if (hstems[k].endw - hstems[k].startw < MINHWIDTH) {
      DBG(" NARROW");
    }
    else {
      getstemcat(&hstems[k], Hw1, Hw2, Hw3, Hw4,
		 Hl1, Hl2, Hl3, Hl4, &wc, &slc, &elc);
      if ((slc == 0 && elc >= 3)
	  || (slc <= 1 && elc == 4)) {
	if (wc == 0) {
	  DBG(" top");
	  stem_mask |= L_TOP;
	}
	else if (wc == 2) {
	  DBG(" ctr");
	  stem_mask |= L_HCENTER;
	}
	else if (wc == 4) {
	  DBG(" btm");
	  stem_mask |= L_BOTTOM;
	}
	else {
	  DBG(" UNKNOWN");
	  unknown_count++;
	}
      }
      else if (wc == 2 && slc == 0 && elc == 2) {
	DBG(" left-ctr");
	stem_mask |= M_LEFTCENTER;
      }
      else if (wc == 2 && slc == 2 && elc == 4) {
	DBG(" right-ctr");
	stem_mask |= M_RIGHTCENTER;
      }
      else if (slc == elc || slc == elc - 1) {
	DBG(" SHORT");
      }
      else {
	DBG(" UNKNOWN");
	unknown_count++;
      }
    }
  }

  DBG("\n");

  bestscore = -100;
  bestchar = -1;
  nbest = 0;

  DBG("mask: %08x\n", stem_mask);

  /* check stems against expected character forms */

  for (i = 0; i < 16; i++) {
    score = -unknown_count;
    stem_used_mask = 0;

    DBG("%X [%c]:", i, codechars[i]);

    for (j = 0; j < charinfo[i].nstemmasks; j++) {
      if (charinfo[i].stemmasks[j] & stem_mask) {
	stem_used_mask |= charinfo[i].stemmasks[j] & stem_mask;
      }
      else {
	DBG(" m%X", charinfo[i].stemmasks[j]);
	score--;	
      }
    }

    for (j = 0; j < 32; j++) {
      if ((stem_mask & ~stem_used_mask) & (1 << j)) {
	DBG(" e%X", (1 << j));
	score--;
      }
    }

    DBG("\n");

    if (score > bestscore) {
      bestscore = score;
      bestchar = i;
      nbest = 1;
    }
    else if (score == bestscore) {
      nbest++;
    }
  }

  if (nbest != 1 || bestscore < -1)
    return '?';
  else if (bestchar < 10)
    return '0' + bestchar;
  else
    return 'A' + bestchar - 10;
}

int main(int argc, char** argv)
{
  point tl, tr, bl, br;
  point rtl, rtr, rbl, rbr;
  point ctl, ctr, cbl, cbr;
  image img;
  int i, j;
  double fhoriz[15], fvert[6];

  if (argc != 2 + 8 + 15 + 6) {
    fprintf(stderr,
	    "usage: %s pgm-file Xtl Ytl Xtr Ytr Xbl Ybl Xbr Ybr\n"
	    "       h1 h2 h3 ... h15 v1 v2 v3 v4 v5 v6\n",
	    argv[0]);
    return 1;
  }

  sscanf(argv[2], "%lf", &tl.x);
  sscanf(argv[3], "%lf", &tl.y);
  sscanf(argv[4], "%lf", &tr.x);
  sscanf(argv[5], "%lf", &tr.y);
  sscanf(argv[6], "%lf", &bl.x);
  sscanf(argv[7], "%lf", &bl.y);
  sscanf(argv[8], "%lf", &br.x);
  sscanf(argv[9], "%lf", &br.y);

  for (i = 0; i < 15; i++)
    sscanf(argv[10 + i], "%lf", &fhoriz[i]);

  for (i = 0; i < 6; i++)
    sscanf(argv[25 + i], "%lf", &fvert[i]);

  memset(&img, 0, sizeof(img));

  if (openpnm(&img, argv[1]))
    return 1;

  rtl = tl;
  rtr = tr;

  for (i = 0; i < 7; i++) {
    if (i < 6) {
      pointweight(&rbl, &tl, &bl, fvert[i]);
      pointweight(&rbr, &tr, &br, fvert[i]);
    }
    else {
      rbl = bl;
      rbr = br;
    }

    ctl = rtl;
    cbl = rbl;

    for (j = 0; j < 15; j++) {
      pointweight(&ctr, &rtl, &rtr, fhoriz[j]);
      pointweight(&cbr, &rbl, &rbr, fhoriz[j]);
      putchar(xchr(&img, &ctl, &ctr, &cbl, &cbr));
      fflush(stdout);
      ctl = ctr;
      cbl = cbr;
    }
    putchar(xchr(&img, &ctl, &rtr, &cbl, &rbr));
    putchar('\n');
    fflush(stdout);

    rtl = rbl;
    rtr = rbr;
  }

  return 0;
}