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

static int debug = 0;

typedef struct t1 {
  int digit,log,ordinal;
} t1;

const t1 table1[] = {
  { 0, 50, 9},
  { 1, 0, 0},
  { 2, 1, 1},
  { 3, 7, 4},
  { 4, 2, 2},
  { 5, 23, 7},
  { 6, 8, 5},
  { 7, 33, 8},
  { 8, 3, 3},
  { 9, 14, 6},
};

typedef struct t2 {
  int a,b;
} t2;

const t2 table2[] = {
  { 1, 0},
  { 2, 1},
  { 3, 7},
  { 4, 2},
  { 5, 23},
  { 6, 8},
  { 7, 33},
  { 8, 13},
  { 9, 14},
  { 10, 24},
  { 12, 9},
  { 14, 34},
  { 15, 30},
  { 16, 4},
  { 18, 15},
  { 20, 25},
  { 21, 40},
  { 24, 10},
  { 25, 46},
  { 27, 21},
  { 28, 35},
  { 30, 31},
  { 32, 5},
  { 35, 56},
  { 36, 16},
  { 40, 26},
  { 42, 41},
  { 45, 37},
  { 48, 11},
  { 49, 66},
  { 54, 22},
  { 56, 36},
  { 63, 47},
  { 64, 6},
  { 72, 17},
  { 81, 28},
};

typedef struct t3 {
  int log,antilog;
} t3;

const t3 table3[] = {
  { 0, 1},
  { 1, 2},
  { 2, 4},
  { 3, 8},
  { 4, 16},
  { 5, 32},
  { 6, 64},
  { 7, 3},
  { 8, 6},
  { 9, 12},
  { 10, 24},
  { 11, 48},
  { 12, -1},
  { 13, -1},
  { 14, 9},
  { 15, 18},
  { 16, 36},
  { 17, 72},
  { 18, -1},
  { 19, -1},
  { 20, -1},
  { 21, 27},
  { 22, 54},
  { 23, 5},
  { 24, 10},
  { 25, 20},
  { 26, 40},
  { 27, -1},
  { 28, 81},
  { 29, -1},
  { 30, 15},
  { 31, 30},
  { 32, -1},
  { 33, 7},
  { 34, 14},
  { 35, 28},
  { 36, 56},
  { 37, 45},
  { 38, -1},
  { 39, -1},
  { 40, 21},
  { 41, 42},
  { 42, -1},
  { 43, -1},
  { 44, -1},
  { 45, -1},
  { 46, 25},
  { 47, 63},
  { 48, -1},
  { 49, -1},
  { 50, 0},
  { 51, 0},
  { 52, 0},
  { 53, 0},
  { 54, -1},
  { 55, -1},
  { 56, 35},
  { 57, 0},
  { 58, 0},
  { 59, -1},
  { 60, -1},
  { 61, -1},
  { 62, -1},
  { 63, -1},
  { 64, 0},
  { 65, -1},
  { 66, 49},
  { 67, -2},
  { 68, -2},
  { 69, -2},
  { 70, -2},
  { 71, -2},
  { 72, -2},
  { 73, 0},
  { 74, -2},
  { 75, -2},
  { 76, -2},
  { 77, -2},
  { 78, -2},
  { 79, -2},
  { 80, -2},
  { 81, -2},
  { 82, -2},
  { 83, 0},
  { 84, -2},
  { 85, -2},
  { 86, -2},
  { 87, -2},
  { 88, -2},
  { 89, -2},
  { 90, -2},
  { 91, -2},
  { 92, -2},
  { 93, -2},
  { 94, -2},
  { 95, -2},
  { 96, -2},
  { 97, -2},
  { 98, -2},
  { 99, -2},
  { 100, 0},
};

int Multiply_Ludgate(int a, int b) {
  // Multiply two single-digit decimal numbers to produce a two-digit product.
  int result;
  int log1, log2;
  log1 = table1[a].log;
  log2 = table1[b].log;
  result = table3[log1+log2].antilog;
  if (debug) fprintf(stderr, "%d + %d => %d\n", log1, log2, log1+log2);
  if (debug) fprintf(stderr, "%d * %d = %d\n", a, b, result);
  return result;
}

// In the example below I'm using the normal left-to-right order of digits in a number,
// where the piecewise multiplications are performed from right-to-left, for pedagogical
// purposes only.  In practice it would make far more sense to reverse the digits and
// procede from left to right, i.e. little-endian.  Our numbering system is erroneously
// big-endian due to a poor understanding of Arabic when Arabic numerals were introduced
// into countries that used the Latin alphabet and left-to-right writing systems.

// Everything below here is a decimal multiply-and-accumulate implementation and
// has little to do with the Ludgate algorithm other than being a harness for it.

// This is a one-digit multiply-and-accumulate step.
void mul_add_digit(int multiplicand_digit, char *result, int result_rightmost, int multiplier_digit) {
  int result_index;
  int product;

  product = Multiply_Ludgate(multiplicand_digit, multiplier_digit);

  // We get a 2-digit result when multiplying 2 1-digit decimal numbers.  So two adds and two carries.

  result_index = result_rightmost;
  result[result_index]   += product%10;
  result[result_index-1] += product/10;
  // add digit
  while (result_index > 0) {
    while (result[result_index] >= 10) {
      result[result_index] -= 10;
      result[result_index-1] += 1;
    }
    // ripple carry
    result_index -= 1;
  }
}

// This is a multiply-and-accumulate step where an arbitrary length multiplicand
// is multiplied by a single-digit multiplier.
void multiply_and_accumulate(char *multiplicand, int multiplicand_rightmost, char *result, int result_rightmost, int multiplier_digit) {
  int i;
  int result_index;
  
  if (debug) fprintf(stderr, "(result before: %.*s)\n", result_rightmost+1, result);
  if (debug) fprintf(stderr, "Multiply & accumulate %.*s by %c gives:\n", multiplicand_rightmost+1, multiplicand, multiplier_digit);

  multiplier_digit -= '0';
  for (i = 0; i <= multiplicand_rightmost; i++) multiplicand[i] -= '0'; // Ascii to decimal
  for (i = 0; i <= result_rightmost; i++) result[i] -= '0';

  result_index = result_rightmost;
  for (i = multiplicand_rightmost; i >= 0; i -= 1) {
    mul_add_digit(multiplicand[i], result, result_index, multiplier_digit);
    result_index -= 1;
  }
  
  for (i = 0; i <= multiplicand_rightmost; i++) multiplicand[i] += '0'; // Decimal to ascii  
  for (i = 0; i <= result_rightmost; i++) result[i] += '0'; // Decimal to ascii
  if (debug) fprintf(stderr, "%.*s\n", result_rightmost+1, result);
}

// And finally we perform multiple multiply-and-accumulate steps to produce the product
// of two arbitrary length decimal numbers.  In hardware the 'arbitrary length' would
// be done by extending the hardware units side-by-side, though note that a ripple-carry
// is still required (which I didn't see mentioned in the Ludgate documentation)
char *multiply(char *multiplicand, char *multiplier) {
  int max_result_digits;
  int i;
  int multiplier_rightmost, multiplicand_rightmost, result_rightmost;
  char *result;
  
  multiplicand_rightmost = strlen(multiplicand) - 1;
  multiplier_rightmost   = strlen(multiplier) - 1;
  if (debug) fprintf(stderr, "init: multiplier_rightmost = strlen(\"%s\") = %c\n", multiplier, multiplier_rightmost);

  result_rightmost       = multiplicand_rightmost+1 + multiplier_rightmost+1 - 1;
  max_result_digits      = result_rightmost+1;
  result = malloc(max_result_digits+1);
  for (i = 0; i <= result_rightmost; i++) result[i] = '0'; // initialise result to all zeroes
  result[max_result_digits] = '\0';

  while (multiplier_rightmost >= 0) {
    if (debug) fprintf(stderr, "loop: multiplier_rightmost[%d] = %c\n", multiplier_rightmost, multiplier[multiplier_rightmost]);
    multiply_and_accumulate(multiplicand, multiplicand_rightmost, result, result_rightmost, multiplier[multiplier_rightmost]);
    result_rightmost -= 1;      // Multiply next partial sum by 10
    multiplier_rightmost -= 1;  // Take next more significant digit from multiplier.
  }
  
  return result;
}

int main(int argc, char **argv) {
  if (argc > 1 && !strcmp(argv[1], "-d")) {
    debug = 1;
    argc -= 1; argv += 1;
  }
  if (argc != 3) {
    fprintf(stderr, "syntax: ludgate [-d] nnn nnn\n\n");
    exit(EXIT_FAILURE);
  }
  if (!isdigit(*argv[1]) || !isdigit(*argv[2])) {
    fprintf(stderr, "ludgate: both arguments should be positive decimal integers: %s %s\n\n", argv[1], argv[2]);
    exit(EXIT_FAILURE);
  }
  fprintf(stdout, "%s\n", multiply(strdup(argv[1]), strdup(argv[2])));
  exit(EXIT_SUCCESS);
  return EXIT_FAILURE;
}