#include <stdio.h>
#include <stdlib.h>
/*

these ones have exact solutions with this template:

x / 8 ==  (((x + 0) * 32) >> 8)
x / 4 ==  (((x + 0) * 64) >> 8)
x / 2 ==  (((x + 0) * 128) >> 8)
x / 255 ==  (((x + 1) * 1) >> 8)
x / 85 ==  (((x + 1) * 3) >> 8)
x / 51 ==  (((x + 1) * 5) >> 8)
x / 17 ==  (((x + 1) * 15) >> 8)
x / 15 ==  (((x + 1) * 17) >> 8)
x / 5 ==  (((x + 1) * 51) >> 8)
x / 3 ==  (((x + 1) * 85) >> 8)
x / 1 ==  (((x + 1) * 255) >> 8)

also some more with >>1 added. and any combos of above, eg /45 = /3 followed by /15

 */
#define abs(x) ((x)<0?-(x):x)
int main(int argc, char **argv) {
  int i, r1, r2, r3, r5, offset, recip, possible_divisor, largest_error, error, correction;
  int off[256], rec[256], err[256], pcor[256], ncor[256];
  for (i = 0; i < 256; i++) { err[i] = 255; off[i] = rec[i] = pcor[i] = ncor[i] = 0;}


  // find exact matches first
  for (possible_divisor = 2; possible_divisor <= 128; possible_divisor++) {
  for (offset = 0; offset < 256; offset++) {
    //for (offset = -128; offset < 126; offset++) {
    for (recip = 1; recip < 256; recip++) {   
      largest_error = 0;
      for (i = 1; i < 256; i++) {
        r1 = i / possible_divisor;
        r2 = ((((i + offset)&65535) * recip) >> 8)&255;
        error = abs(r2-r1); if (error > largest_error) largest_error = error;
        if (abs(r2-r1) >= possible_divisor) break;
      }
      if ((i >= 255) && (largest_error == 0) && (rec[possible_divisor] == 0)) {
        rec[possible_divisor] = recip;
        off[possible_divisor] = offset;
        err[possible_divisor] = largest_error;
      }
    }
  }
  }

  for (possible_divisor = 2; possible_divisor <= 128; possible_divisor++) {
  for (offset = 0; offset < 256; offset++) {
    int pluscor = 0, negcor = 0;
    for (recip = 1; recip < 256; recip++) {   
      largest_error = 0;
        for (i = 1; i < 256; i++) {
          r1 = i / possible_divisor;
          r2 = ((((i + offset)&65535) * recip) >> 8)&255;
          r3 = r2 * possible_divisor;
	  if ((i - r3) >= possible_divisor) {r2 += 1; pluscor = 1;}
	  //else if ((i - r3) <= -possible_divisor) {r2 -= 1; negcor = -1;}
          error = abs(r2-r1); if (error > largest_error) largest_error = error;
          if (abs(r2-r1) >= possible_divisor) break;
        }
        if ((i >= 255) && (largest_error < err[possible_divisor])) {
          rec[possible_divisor] = recip;
          off[possible_divisor] = offset;
	  err[possible_divisor] = largest_error;
	  pcor[possible_divisor] = pluscor;
	  ncor[possible_divisor] = negcor;
        }
    }
  }
  }

  fprintf(stdout, "/* Macros for division of an 8 bit integer by constants 2 through 127 */\n");
  for (i = 0; i < 128; i++) {
    if (i >= 86) {
      fprintf(stdout, "#define div%0d(x) (x < %0d ? 0 : (x < %d ? 1 : 2))\n", i, i, i*2);
    } else if (rec[i]) {
      char add[16], mul[32];
      if (off[i] == 0) sprintf(add, "(x)"); else sprintf(add, "((x) + %d)", off[i]);
      if (rec[i]==1) {
        sprintf(mul, "(%s >> 8)", add);
      } else if (rec[i]==2) {
        sprintf(mul, "(%s >> 7)", add);
      } else if (rec[i]==4) {
        sprintf(mul, "(%s >> 6)", add);
      } else if (rec[i]==8) {
        sprintf(mul, "(%s >> 5)", add);
      } else if (rec[i]==16) {
        sprintf(mul, "(%s >> 4)", add);
      } else if (rec[i]==32) {
        sprintf(mul, "(%s >> 3)", add);
      } else if (rec[i]==64) {
        sprintf(mul, "(%s >> 2)", add);
      } else if (rec[i]==128) {
        sprintf(mul, "(%s >> 1)", add);
      } else {
        sprintf(mul, "((%s * %d) >> 8)", add, rec[i]);
      }
      if ((pcor[i] != 0) && (ncor[i] != 0)) {
        fprintf(stdout, "x / %d ~=  %s, max err = %d, correction applied %d,%d\n", i, mul, err[i], pcor[i],ncor[i]);
        // fprintf(stdout, "x / %d ~=  (((x + %d) * %d) >> 8), max err = %d, correction applied %d,%d\n", i, off[i], rec[i], err[i], pcor[i],ncor[i]);
      } else if (pcor[i] != 0) {
        fprintf(stdout, "#define div%0d(x)  (  temp = %s, rem = (x) - temp*%d, temp+(rem >= %d ? 1 : 0)  )\n", i, mul, i, i);
        // fprintf(stdout, "#define div%0d(x)  (  temp = ((((x) + %d) * %d) >> 8), rem = (x) - temp*%d, temp+(rem >= %d ? 1 : 0)  )\n", i, off[i], rec[i], i, i);
      } else if (ncor[i] != 0) {
        fprintf(stdout, "x / %d ~=  %s, max err = %d, correction applied %d\n", i, mul, err[i], ncor[i]);
      } else {
        fprintf(stdout, "#define div%0d(x)  %s\n", i, mul);
        // fprintf(stdout, "#define div%0d(x)  ((((x) + %d) * %d) >> 8)\n", i, off[i], rec[i]);
      }
    } else if ((i >= 128) && (i < 255)) {
      fprintf(stdout, "#define div%0d(x)  ((x)>=%d?1:0)\n", i,i);
    } else if (i == 255) {
      fprintf(stdout, "#define div255(x)  ((x)==255?1:0)\n");
    }
  }
  fprintf(stdout, "%s\n", "#ifndef int8_t");
  fprintf(stdout, "%s\n", "#define int8_t char");
  fprintf(stdout, "%s\n", "#endif");

  fprintf(stdout, "%s\n", "#ifndef int16_t");
  fprintf(stdout, "%s\n", "#define int16_t short");
  fprintf(stdout, "%s\n", "#endif");

  fprintf(stdout, "%s\n", "/* function to divide arbitray unsigned 8 bit numerator by unsigned 8 bit divisor */");
  fprintf(stdout, "%s\n", "unsigned int8_t _f_div(unsigned int8_t num, unsigned int8_t denom) {");
  fprintf(stdout, "%s\n", "  unsigned int16_t temp;");
  fprintf(stdout, "%s\n", "  unsigned int8_t rem;");
  fprintf(stdout, "%s\n", "  static const void *lab[256] = {");
  for (i = 0; i < 86; i+=1) {
    fprintf(stdout, "    &&d%0d,", i); if ((i&7) == 7) fprintf(stdout, "\n"); else fprintf(stdout, " ");
  }
  fprintf(stdout, "\n");
  for (i = 86; i < 128; i+=1) {
    fprintf(stdout, "    &&dd,"); if ((i-86)%10 == 9) fprintf(stdout, "\n"); else fprintf(stdout, " ");
  }
  for (i = 128; i < 256; i+=16) {
    fprintf(stdout, "    &&d, &&d, &&d, &&d, &&d, &&d, &&d, &&d, &&d, &&d, &&d, &&d, &&d, &&d, &&d, &&d,\n");
  }
  fprintf(stdout, "%s\n", "  };");
  fprintf(stdout, "%s\n", "  goto *lab[denom];");
  fprintf(stdout, "%s\n", "  d: return num >= denom ? 1 : 0;\n");
  // 0/88  num = 0  denom = 88          0 < 88 ?  -> 0
  // 90/88  num = 90  denom = 88          90 < 88 ?          90 < 176?  -> 1
  // 190/88  num = 190  denom = 88          190 < 88?          190 < 176? -> 2
  fprintf(stdout, "%s\n", "  dd: return num < denom ? 0 : (num < (denom<<1) ? 1 : 2);\n");
  fprintf(stdout, "%s\n", "  d0: return 255; // User needs to supply some sort of error handler.");
  fprintf(stdout, "%s\n", "  d1: return num;");
  for (i = 2; i < 86; i++) {
    fprintf(stdout, "  d%0d: return div%0d(num);", i, i);
    if (((i-2)&3) == 3) fprintf(stdout, "\n");
  }
  fprintf(stdout, "%s\n", "}");
  
  fprintf(stdout, "%s\n", "#ifdef DBMAIN");
  fprintf(stdout, "%s\n", "#undef int8_t");
  fprintf(stdout, "%s\n", "#undef int16_t");
  fprintf(stdout, "%s\n", "#include <stdio.h>");
  fprintf(stdout, "%s\n", "#include <stdlib.h>");
  fprintf(stdout, "%s\n", "int main(int argc, char **argv) {");
  fprintf(stdout, "%s\n", "  unsigned char num, den;");
  fprintf(stdout, "%s\n", "  num = 0;");
  fprintf(stdout, "%s\n", "  for (;;) {");
  fprintf(stdout, "%s\n", "    den = 1;");
  fprintf(stdout, "%s\n", "    for (;;) {");
  fprintf(stdout, "%s\n", "      if (num/den != _f_div(num,den)) {");
  fprintf(stdout, "%s\n", "        fprintf(stdout, \"div(%d,%d) = %d but %d/%d = %d ?\\n\", num, den, _f_div(num,den), num, den, num/den);");
  fprintf(stdout, "%s\n", "        exit(1);");
  fprintf(stdout, "%s\n", "      }");
  fprintf(stdout, "%s\n", "      den += 1;");
  fprintf(stdout, "%s\n", "      if (den == 0) break;");
  fprintf(stdout, "%s\n", "    }");
  fprintf(stdout, "%s\n", "    num += 1;");
  fprintf(stdout, "%s\n", "    if (num == 0) break;");
  fprintf(stdout, "%s\n", "  }");
  fprintf(stdout, "%s\n", "  fprintf(stdout, \"All tests passed!\\n\");");
  fprintf(stdout, "%s\n", "  exit(0);");
  fprintf(stdout, "%s\n", "}");
  fprintf(stdout, "%s\n", "#endif");

  exit(0);
  return 0;
}