/*
   Original software by Ian Goldberg,
   Modified and updated by OOO S.  (ooosawaddee3@hotmail.com)
   Version 2.0 by Hector Peraza (peraza@uia.ua.ac.be)
   Modified by jiang 20110930
*/
#include <stdio.h>
#include <string.h>
#include "pdf417_dham.c"

#define NN      1024
#define GG      929
#define A0      928
#define KK      32
#define MIN(x,y) (((x) < (y)) ? (x) : (y))

void decode_segment(int *cw, int len, int mode);
void convert_byte(int *cw, int len, int mode);
void convert_text(int *cw, int len);
void convert_num(int *cw, int len);

int mask[15];
int dump   = 0;          // 3 output switch
int encfmt = 1;          // 0
int numouts;
int codewords[34*90];  /* array for the extracted codewords */

int len   = 0;
int sorow = 0;
int skip  = 0;

#define modbase(x) ((x)%(A0))
int Alpha_to[1024];
int Index_of[1024];
void powers_init()
{
  int i, power_of_3=1;
  Index_of[1] = A0;
  for(i=0;i<A0;i++){
    Alpha_to[i] = power_of_3;
    if(power_of_3 < GG) if(i != A0) Index_of[power_of_3]=i;
    else  printf("Internal error: powers of 3 calculation\n");
    power_of_3 = (power_of_3 * 3) % GG;
  }
  Index_of[0] = Index_of[GG] = A0;  Alpha_to[A0] = 1;
}
int eras_dec_rs(int data[NN], int eras_pos[NN-KK], int no_eras,
                int data_len, int synd_len)
{
  int deg_lambda, el, deg_omega;
  int i, j, r, k, u, q, tmp, num1, num2, den, discr_r;
  int syn_error, count, ci, error_val, fix_loc;
  int lambda[2048+1], s[2048+1];  /* Err+Eras Locator poly and syndrome poly */
  int b[2048+1], t[2048+1], omega[2048+1], root[2048], reg[2048+1], loc[2048];

  powers_init();
  for(i=0; i<data_len; i++) if (data[i] > GG) return -1;
             /* form the syndromes; i.e. evaluate data(x) at roots of g(x)
                            namely @**(1+i)*PRIM, i = 0, ... , (NN-KK-1) */
  for (i = 1; i <= synd_len; i++) s[i] = 0;
  for (j = 1; j <= data_len; j++) {
    if (data[data_len - j] == 0) continue;
    tmp = Index_of[data[data_len - j]];
                           /*  s[i] ^= Alpha_to[modbase(tmp + (1+i-1)*j)]; */
    for (i = 1; i <= synd_len; i++)
      s[i] = (s[i] + Alpha_to[modbase(tmp + i*j)]) % GG;
  }     /* Convert syndromes to index form, checking for nonzero condition */
  syn_error = 0;
  for (i=1; i <= synd_len; i++) { syn_error |=s[i]; s[i]=Index_of[s[i]]; }
  if (!syn_error) {
      /* if syndrome is zero, data[] is a codeword and there are no
       * errors to correct. So return data[] unmodified       */
    count = 0;
    printf("No errors \n");
    goto finish;
  }
  for (ci=synd_len-1; ci>=0; ci--)lambda[ci+1]=0;
  lambda[0] = 1;
  if (no_eras > 0) {    /* Init lambda to be the erasure locator polynomial */
    lambda[1] = Alpha_to[modbase(eras_pos[0])];
    for(i=1;i<no_eras;i++){ u=modbase(eras_pos[i]);
      for(j=i+1;j>0;j--){   tmp=Index_of[lambda[j-1]];
        if(tmp!=A0)lambda[j]=(lambda[j]+Alpha_to[modbase(u+tmp)]) % GG;
      }            /* Test code that verifies the erasure locator polynomial*/
    }              /* just constructed,Needed only for decoder debugging.   */
                          /* find roots of the erasure location polynomial  */
    for(i=1;i<=no_eras;i++)reg[i]=Index_of[lambda[i]];
    count = 0;
    for(i=1,k=data_len-1;i<=data_len+synd_len;i++,k=modbase(data_len+k-1)){
      q = 1;
      for (j = 1; j <= no_eras; j++) if (reg[j] != A0) {
        reg[j] = modbase(reg[j] + j);
        q = (q + Alpha_to[reg[j]]) % GG;
      }
      if(q)continue;       /* store root and error location number indices */
      root[count] = i;
      loc[count] = k;
      count++;
    }
  }
  for (i = 0; i < synd_len + 1; i++) b[i] = Index_of[lambda[i]];
/*Begin Berlekamp-Massey algorithm to determine error+erasure locator polynomial */
  r = no_eras;
  el = no_eras;
  while (++r <= synd_len) {                        /* r is the step number */
                      /* Compute discrepancy at the r-th step in poly-form */
    discr_r = 0;
    for (i = 0; i < r; i++) {
      if ((lambda[i] != 0) && (s[r - i] != A0)) {
        if (i % 2 == 1)
        discr_r=(discr_r+Alpha_to[modbase((Index_of[lambda[i]]+s[r-i]))])%GG;
        else
        discr_r=(discr_r+GG-Alpha_to[modbase((Index_of[lambda[i]]+s[r-i]))])%GG;
      }
    }
    discr_r = Index_of[discr_r];                          /* Index form */
        /* 2 lines below: B(x) <-- x*B(x)  COPYDOWN(&b[1],b,synd_len);  */
    if (discr_r == A0) {
      for (ci = synd_len - 1; ci >= 0; ci--) b[ci + 1] = b[ci];
      b[0] = A0;
    } else {        /* 7 lines below: T(x) <-- lambda(x) - discr_r*x*b(x) */
                                 /*  the T(x) will become the next lambda */
      t[0] = lambda[0];
      for (i = 0; i < synd_len; i++) {
        if (b[i] != A0) {
          t[i+1]=(lambda[i+1]+Alpha_to[modbase(discr_r+ b[i])]) % GG;
        } else  t[i + 1] = lambda[i + 1];
      }
      el = 0;
                     /* 2 lines below: B(x) <-- inv(discr_r) * lambda(x) */
      if (2 * el <= r + no_eras - 1) {
        el = r + no_eras - el;
        for (i = 0; i <= synd_len; i++) {
          if (lambda[i] == 0) b[i] = A0;
          else b[i]=modbase(Index_of[lambda[i]] - discr_r + A0);
        }
      } else {
        for (ci = synd_len - 1; ci >= 0; ci--) b[ci + 1] = b[ci];
        b[0] = A0;
      }
      for (ci = synd_len + 1 - 1; ci >= 0; ci--) lambda[ci] = t[ci];
    }
  }           /* Convert lambda to index form and compute deg(lambda(x)) */
  deg_lambda = 0;
  for (i = 0; i < synd_len + 1; i++) {
    lambda[i] = Index_of[lambda[i]];
    if (lambda[i] != A0) deg_lambda = i;
  }
  /* Find roots of the error+erasure locator polynomial by Chien Search  */
  for (ci = synd_len - 1; ci >= 0; ci--) reg[ci + 1] = lambda[ci + 1];
  count = 0;                             /* Number of roots of lambda(x) */
  for (i = 1, k = data_len - 1; i <= GG; i++) {
    q = 1;
    for (j = deg_lambda; j > 0; j--) {
      if (reg[j] != A0) {
        reg[j] = modbase(reg[j] + j);
        if (deg_lambda != 1) {
          if (j % 2 == 0)  q = (q + Alpha_to[reg[j]]) % GG;
          else    q = (q + GG - Alpha_to[reg[j]]) % GG;
        } else {  q = Alpha_to[reg[j]] % GG; if (q == 1) q--; }
      }
    }
    if (q == 0) {   /* store root (index-form) and error location number */
      root[count] = i;
      loc[count] = A0 - i;
      if (count < synd_len) count += 1;
      else printf("Error : Error count too big = %d \n", count);
    }
    if (k == 0)  k = data_len - 1; else   k -= 1;
/* If we've already found max possible roots, abort the search to save time*/
    if (count == deg_lambda) break;
  }
  if (deg_lambda != count) {
  /* deg(lambda) unequal to number of roots => uncorrectable error detected*/
    printf("Uncorrectable error: root count = %d deg lambda = %d \n",
             count, deg_lambda);
    count = -1;
    goto finish;
  }
/*   Compute err+eras evaluator poly omega(x) = s(x)*lambda(x) (modulo
                  x**(synd_len)). in index form. Also find deg(omega).     */
  deg_omega = 0;
  for (i = 0; i < synd_len; i++) {
    tmp = 0;
    j = (deg_lambda < i) ? deg_lambda : i;
    for (; j >= 0; j--) {
      if ((s[i + 1 - j] != A0) && (lambda[j] != A0)) {
        if (j % 2 == 1)
              tmp=(tmp+GG-Alpha_to[modbase(s[i+1-j]+lambda[j])]) % GG;
        else  tmp=(tmp+Alpha_to[modbase(s[i+1-j]+lambda[j])]) % GG;
      }
    }
    if (tmp != 0) deg_omega = i;
    omega[i] = Index_of[tmp];
  }
  omega[synd_len] = A0;
/*    Compute error values in poly-form. num1 = omega(inv(X(l))), num2 =
      inv(X(l))**(B0-1) and den = lambda_pr(inv(X(l))) all in poly-form   */
  for (j = count - 1; j >= 0; j--) {
    num1 = 0;
    for (i = deg_omega; i >= 0; i--) if (omega[i] != A0)
            num1=(num1+Alpha_to[modbase(omega[i]+((i+1)*root[j]))]) % GG;
    num2 = 1;
    den = 0;
/* denominator if product of all (1 - Bj Bk) for k!=j,if count=1, then den =1*/
    den = 1;
    for (k = 0; k < count; k += 1) {
      if (k != j) {
        tmp=(1+GG-Alpha_to[modbase(A0-root[k]+root[j])]) % GG;
        den = Alpha_to[modbase(Index_of[den] + Index_of[tmp])];
      }
    }
    if (den == 0) {
      printf("\n ERROR: denominator = 0\n");      /* Convert to dual- basis */
      count = -1;
      goto finish;
    }
    error_val = Alpha_to[modbase(Index_of[num1] + Index_of[num2] +
                                 A0 - Index_of[den])] % GG;
    /* Apply error to data */
    if (num1 != 0) {
      if (loc[j] < data_len + 1) {
        fix_loc = data_len - loc[j];
        if (fix_loc < data_len + 1)
            data[fix_loc] = (data[fix_loc] + GG - error_val) % GG;
      }
    }
  }
finish:
  if(eras_pos!=NULL)for(i=0;i<count;i++)if(eras_pos!=NULL)eras_pos[i]=loc[i];
  return count;
}                                       /* Return -1 if wrong cluster */

/*  This routine does all the decoding. Individual compaction segments
 *  are extracted from the codeword array, then for each segment the
 *  decode_segment() function is called, which in turn invokes one of
 *  the convert_*() functions which finally decode the data into a
 *  human readable format. */
static void decode_codewords()
{
  int   i, cw, len, slen, mode, shift;
  int   segment[34*90];         /* single compaction segment to be decoded */
  if (numouts == 0) return;
  len = codewords[0];
  if (len == 0) return;
  slen = 0;
  shift=mode=900;                    /* default mode is Text Compaction */
  for (i = 1; i < len; ++i) {  cw = codewords[i];
    if (cw >= 900) {
      if (slen > 0) decode_segment(segment, slen, mode);
      slen = 0;
      switch (cw) {
      case 900:                      /* mode latch to Text Compaction mode */
      case 901:                      /* mode latch to Byte Compaction */
      case 902:                      /* mode latch to Numeric Compaction */
          mode = shift = cw;
          break;
      case 913:                      /* mode shift to Byte Compaction */
          shift = cw;
          break;
      case 921:                     /* reader initialization */
          break;
      case 922:          /* terminator codeword for Macro PDF control block */
          break;
      case 923:  /* Begin of optional fields in the Macro PDF control block */
          break;
      case 924:        /* mode latch to Byte Compaction (num of encoded bytes
                                               is an integer multiple of 6) */
          mode = shift = cw;
          break;
      case 925:             /* identifier for a user defined Extended Channel
                                                       Interpretation (ECI) */
      case 926:              /* identifier for a general purpose ECI format */
      case 927:    /* identifier for an ECI of a character set or code page */
          break;
      case 928:                       /* Begin of a Macro PDF Control Block */
          break;
      default:
          printf("Unknown mode %d\n", cw);
          break;
      }
      continue;
    }
    segment[slen++] = cw;
    if (shift != mode) {
      if (slen > 0) decode_segment(segment, slen, shift);
      slen = 0;
      shift = mode;
    }
  }
  if (slen > 0) decode_segment(segment, slen, mode);
}

char name[3][3]={"TC","BC","NC"};
void decode_segment(int *cw, int len, int mode)
{
  int i;
  i=mode-900; if(i>2)i=1;
  if(len>99){ printf("ERROR: too many chars in %s\n",name[i]); return; }
  switch (mode) {
  case 900:
      convert_text(cw, len);
      break;
  case 901:
  case 913:
  case 924:
      convert_byte(cw, len, mode);
      break;
  case 902:
      convert_num(cw, len);
      break;
  }
}

void convert_byte(int *cw, int len, int mode)
{
  __int64 codeval;
  int i, j;
  unsigned char b[6];
  if (encfmt) printf("BC \"");
                          /* 6 bytes are encoded in a group of 5 codewords */
  for ( ; (mode == 901) ? (len > 5) : (len >= 5); len -= 5) {
    codeval = 0;                      /* convert from base 900 to base 256 */
    for (i = 0; i < 5; ++i) { codeval *= 900; codeval += *cw++;    }
    for (j = 0; j < 6; ++j) { b[5-j] = (int)codeval % 256; codeval >>= 8;  }
    if (encfmt) for (j = 0; j < 6; ++j) printf("%02X", b[j]);
    else        for (j = 0; j < 6; ++j) printf("%c", b[j]);
  }         /* remaining codewords, if any, are encoded 1 byte per codeword */
  if (len > 0) {
    for (j = 0; j < len; ++j)  b[j] = *cw++;
    if (encfmt) for (j = 0; j < len; ++j) printf("%02X", b[j]);
    else        for (j = 0; j < len; ++j) printf("%c", b[j]);
    codeval = 0;
    i = 0;
  }
  if (encfmt) printf("\"\n");
}

void convert_text(int *cw, int len)
{
  int mode, shift, enc;
  int i, j, c[2], cout;

  static char txt_upper[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ    ";
  static char txt_lower[] = "abcdefghijklmnopqrstuvwxyz    ";
  static char txt_mixed[] = "0123456789&\r\t,:#-.$/+%*=^     ";
  static char txt_punct[] = ";<>@[\\]_`~!\r\t,:\n-.$/\"|*()?{}' ";

  mode = shift = 0;
  if (encfmt) printf("TC \"");
  for (i = 0; i < len; ++i) {
    c[0] = *cw / 30;    c[1] = *cw % 30;    cw++;
    for (j = 0; j < 2; ++j) {
      enc = mode;
      if (mode != shift) { enc = shift; shift = mode; }
      switch (enc) {
      case 0:                                              /* uppercase */
          if (c[j] == 27) { mode = shift = 1; continue; }  /* lower latch */
          if (c[j] == 28) { mode = shift = 2; continue; }  /* mixed latch */
          if (c[j] == 29) { shift = 3; continue; }         /* punct shift */
          cout = txt_upper[c[j]];
          break;
      case 1:                                              /* lowercase */
          if (c[j] == 27) { shift = 0; continue; }         /* upper shift */
          if (c[j] == 28) { mode = shift = 2; continue; }  /* mixed latch */
          if (c[j] == 29) { shift = 3; continue; }         /* punct shift */
          cout = txt_lower[c[j]];
          break;
      case 2:                                              /* mixed (numeric)*/
          if (c[j] == 25) { mode = shift = 3; continue; }  /* punct latch */
          if (c[j] == 27) { mode = shift = 1; continue; }  /* lower latch */
          if (c[j] == 28) { mode = shift = 0; continue; }  /* upper latch */
          if (c[j] == 29) { shift = 3; continue; }         /* punct shift */
          cout = txt_mixed[c[j]];
          break;
      case 3:                                              /* punctuation */
          if (c[j] == 29) { mode = shift = 0; continue; }  /* upper latch */
          cout = txt_punct[c[j]];
          break;
      }
      printf("%c", cout);
    }
  }
  if (encfmt) printf("\"\n");
}

/*  BCD arithmetic is used in this routine in order to simplify
                               large-precision number manipulations.  */
void convert_num(int *cw, int len)
{
  int n_bcd[45], cw_bcd[3];
  int i, j, n, res, carry, start;

  for ( ; len > 0; len -= 15) {               /* clear the accumulator */
    for (i = 0; i < 45; ++i) n_bcd[i] = 0;
    for (i = 0; i < MIN(len, 15); ++i) {      /* convert codeword to BCD */
      n =*cw++; cw_bcd[0] = n % 10;
      n/= 10;   cw_bcd[1] = n % 10;
      n/= 10;   cw_bcd[2] = n;  /* multiply accumulator by 900 (100 * 9) */
      if (i > 0) {
        carry = 0;                                      /* multiply by 9 */
        for (j = 0; j < 45; ++j) {
          res = n_bcd[j] * 9 + carry;
          n_bcd[j] = res % 10;
          carry = res / 10;
        }                                             /* multiply by 100 */
        for (j = 44; j >= 2; --j)  n_bcd[j] = n_bcd[j-2];
        n_bcd[0] = n_bcd[1] = 0;
      }                                     /* then add the BCD codeword */
      carry = 0;
      for (j = 0; j < 3; ++j) {
        res = n_bcd[j] + cw_bcd[j] + carry;
        n_bcd[j] = res % 10;
        carry = res / 10;
      }
      for ( ; j < 45; ++j) {
        res = n_bcd[j] + carry;
        n_bcd[j] = res % 10;
        carry = res / 10;
      }
    }
    start = 0;
    if (encfmt) printf("NC \"");
    for (j = 0; j < 45; ++j) {
      if (start)   printf("%c", n_bcd[44-j] + '0');
      else if (n_bcd[44-j] == 1)    start = 1;
      else if (n_bcd[44-j] != 0) {  printf("<invalid>");  break; }
    }
    if (encfmt) printf("\"\n");
  }
}

//----------------
static int bestham(int word, int which)
{
  int i, best = which;
  if (dump) printf("%d %.4x 0x%08x (%d)\n",
            which, word, dham[which][word], dham[which][word] & 0xffff);
  for (i = 0; i < 3; ++i)
    if ((dham[i][word] & 0xff000000) < (dham[best][word] & 0xff000000))best=i;
  if (best != which) return -1;
  return dham[which][word];
}

int processrow(int cols, int rownum, int *cumbits)
{
  int scale, nchange, word;
  int j, k, s, e, l;
  int cumchange[2048];
  unsigned  int cw;
  nchange = 0;  cumchange[nchange++] = 0;
  for (j=1; j<cols; j++) if(cumbits[j] != cumbits[j-1] ) {
    if(nchange>1&&(j-cumchange[nchange-1])*15<cumchange[1])nchange--;
    else cumchange[nchange++] = j;
  }  if(nchange<8)return 0;
  for (j=0; j < nchange-8; j += 8) {
    word=0;  scale = cumchange[j+8] - cumchange[j];
    for (k = 0; k < 8; k += 2) {
      s=17*(cumchange[j+k] - cumchange[j])/scale;
      e=17*(cumchange[j+k+1]-cumchange[j])/scale;
      if(s<1)s=1;         /* We know we always start with 1, end with 0 */
      if (e > 16) e = 16;
      for (l = s; l < e; ++l) word |= mask[l-1];
    }
    cw = bestham(word>>1, rownum%3);
    if(skip){  skip--; continue; }
    if(numouts==0) len=cw;  /* not really used, but stored as codewords[0] */
    if ((cw & 0xffffff) == 0x030000) {                   /* start sequence */
      skip = 1;
      sorow = numouts;
      continue;
    }
    if((cw & 0xffffff) == 0x030001) {                    /* stop sequence? */
      numouts--;
      continue;
    }
    if(cw == -3) {                           /* Rewind to beginning of row */
      numouts = sorow;
      continue;
    }
    if ((cw & 0xffff) == 0xffff) cw=0;                 /* store codeword */
    codewords[numouts++] = cw & 0xffff;
  }
  return 1;
}

unsigned char bits[512][2048];             // MAX pix 2048*512
short h[27];
char f1[20];
FILE *fp;
int main(int ac, char **av)
{
  int rows,cols, i,j,d,rownum;
  int cumbits[2048];
  for (i = 0; i < 15; i++) mask[i] = 1 << (15-i);
  if(ac<2){ printf("\n\t a ?[.bmp]\n\n"); return 0; }
  strcpy(f1,av[1]); j=strlen(f1); if(f1[j-4]!='.')strcat(f1,".bmp");
  fp=fopen(f1,"rb"); if(fp==0){printf("\n\tfile not found!\n"); return 0;}
  fread(h,2,27,fp); fseek(fp,1078,0);
  cols=h[9]; rows=h[11];  d=(cols+3)/4*4;
  numouts=rownum=0;
  for(j=0;j<rows;j++)fread(&bits[rows-j-1][0],1,d,fp);  fclose(fp);
  for(j=0;j<rows;j+=2){
    for(i=0;i<cols;i++)cumbits[i]=bits[j][i]?0:1;
    processrow(cols,rownum++,cumbits);
  }

//printf("Total codewords = %d (%d data, %d ECC)\n",
//         numouts, codewords[0], numouts - codewords[0]);
  d = eras_dec_rs(codewords, NULL, 0, numouts, numouts - codewords[0]);
  if(d<0)printf("Errors detected, but data could not be corrected\n");
  else if (d > 0) printf("%d codewords corrected\n\n", d);
//printf("clos,rows: %d %d  rownum: %d\n",cols,rows,rownum);
//for(i=0;i<numouts;i++)printf("%d ",codewords[i]); printf("\n");
  decode_codewords();  return 0;
}