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

typedef struct {
  unsigned char * bytes;
  unsigned length;
} longNumber;

void convert(const char *, unsigned char, unsigned char);
void convertBases(const char *, const char *, const char *);

char * convertedNumber(const char *, const char *, const char *);
char * baseString(unsigned char);
char * toUppercase(const char *);
unsigned char valueOf(char, const char *);
unsigned char checkBase(const char *);
longNumber convertFrom(const char *, const char *, unsigned char);
char * convertTo(longNumber, const char *, unsigned char);

void destroyNumber(longNumber);
longNumber createNumber(unsigned long long);
longNumber copyNumber(longNumber);
unsigned char isZero(longNumber);
longNumber add(longNumber, longNumber);
longNumber addMultiple(longNumber *, unsigned);
longNumber multiplyDigit(longNumber, unsigned char);
longNumber divideDigit(longNumber, unsigned char, unsigned char *);

void convert (const char * number, unsigned char baseFrom, unsigned char baseTo) {
  if (!number) return;
  if ((baseFrom < 2) || (baseFrom > 36) || (baseTo < 2) || (baseTo > 36)) return;
  if (baseFrom == baseTo) {
    printf("%s\n", number);
    return;
  }
  unsigned char negative = 0;
  for (; !isalnum(*number); number ++)
    switch (*number) {
      case '-':
        negative = !negative;
        break;
      case '+': case ' ':
        break;
      default:
        return; // error character
    }
  if (!(*number)) return;
  char * from = baseString(baseFrom);
  char * to = baseString(baseTo);
  char * uppercaseNumber = toUppercase(number);
  char * conversionResult = convertedNumber(uppercaseNumber, from, to);
  if (conversionResult) {
    if (negative) putchar('-');
    printf("%s\n", conversionResult);
    free(conversionResult);
  }
  free(uppercaseNumber);
  free(from);
  free(to);
}

void convertBases (const char * number, const char * baseFrom, const char * baseTo) {
  if (!number) return;
  char * conversionResult = convertedNumber(number, baseFrom, baseTo);
  if (conversionResult) {
    printf("%s\n", conversionResult);
    free(conversionResult);
  }
}


char * convertedNumber (const char * number, const char * baseFrom, const char * baseTo) {
  unsigned char from, to;
  from = checkBase(baseFrom);
  if (!from) return NULL;
  to = checkBase(baseTo);
  if (!to) return NULL;
  longNumber converted = convertFrom(number, baseFrom, from);
  if (!converted.length) return NULL;
  char * result = convertTo(converted, baseTo, to);
  destroyNumber(converted);
  return result;
}

char * baseString (unsigned char base) {
  if (base < 2) return NULL;
  if (base > 36) return NULL;
  char * result = malloc(base + 1);
  result[base] = 0;
  unsigned char pos;
  for (pos = 0; (pos < base) && (pos < 10); pos ++)
    result[pos] = 48 + pos; // ASCII for the digit
  if (base <= 10) return result;
  for (; pos < base; pos ++)
    result[pos] = 55 + pos; // ASCII for the letter
  return result;
}

char * toUppercase (const char * string) {
  // I think there's a strtoupper() somewhere, but that's for pussies
  char * result = malloc(strlen(string) + 1);
  unsigned pos;
  for (pos = 0; string[pos]; pos ++)
    if ((string[pos] >= 97) && (string[pos] <= 122))
      result[pos] = string[pos] - 32;
    else
      result[pos] = string[pos];
  result[pos] = 0;
  return result;
}

unsigned char valueOf (char digit, const char * base) {
  unsigned char pos;
  for (pos = 0; base[pos]; pos ++)
    if (digit == base[pos])
      return pos;
  return (unsigned char) -1;
}

unsigned char checkBase (const char * base) {
  char checked[256]; // yeah, I'm assuming chars are really 8 bits, kill me
  unsigned pos;
  for (pos = 0; pos < 256; pos ++) checked[pos] = 0;
  for (pos = 0; base[pos]; pos ++)
    if (checked[base[pos]])
      return 0;
    else
      checked[base[pos]] = 1;
  if (pos == 1) return 0; // base 1 is not valid!
  return pos; // return the actual size of the base, because why not
}

longNumber convertFrom (const char * number, const char * base, unsigned char baseSize) {
  if (!number) return (longNumber) {NULL, 0};
  if (!(*number)) return (longNumber) {NULL, 0};
  longNumber total = createNumber(0);
  longNumber positionValue = createNumber(1);
  longNumber temp, temp2;
  const char * current = number + (strlen(number) - 1);
  unsigned char digitValue;
  for (; current >= number; current --) {
    digitValue = valueOf(*current, base);
    if (digitValue == (unsigned char) -1) {
      destroyNumber(total);
      destroyNumber(positionValue);
      return (longNumber) {NULL, 0};
    }
    temp = multiplyDigit(positionValue, digitValue);
    temp2 = add(total, temp);
    destroyNumber(total);
    destroyNumber(temp);
    total = temp2;
    temp = multiplyDigit(positionValue, baseSize);
    destroyNumber(positionValue);
    positionValue = temp;
  }
  destroyNumber(positionValue);
  return total;
}

char * convertTo (longNumber number, const char * base, unsigned char baseSize) {
  if (isZero(number)) {
    char * result = malloc(2);
    *result = *base;
    result[1] = 0;
    return result;
  }
  unsigned char nextDigit;
  char * result = NULL;
  unsigned resultLength = 0;
  longNumber temp;
  number = copyNumber(number);
  while (!isZero(number)) {
    temp = divideDigit(number, baseSize, &nextDigit);
    destroyNumber(number);
    number = temp;
    result = realloc(result, resultLength + 1);
    result[resultLength ++] = base[nextDigit];
  }
  destroyNumber(number);
  char * reversed = result;
  result = malloc(resultLength + 1);
  unsigned pos;
  for (pos = 0; pos < resultLength; pos ++)
    result[pos] = reversed[resultLength - pos - 1];
  free(reversed);
  result[resultLength] = 0;
  return result;
}

// this reminds me of a class definition, but oh well

void destroyNumber (longNumber number) {
  if (number.length) free(number.bytes);
}

longNumber createNumber (unsigned long long number) {
  if (!number) {
    longNumber result;
    result.length = 1;
    result.bytes = malloc(1);
    *(result.bytes) = 0;
    return result;
  }
  unsigned char * newNumber = malloc(sizeof(unsigned long long));
  unsigned char length;
  for (length = 0; number; length ++, number >>= 8)
    newNumber[length] = number & 255;
  newNumber = realloc(newNumber, length);
  return (longNumber) {newNumber, length};
}

longNumber copyNumber (longNumber number) {
  unsigned char * newNumber = malloc(number.length);
  memcpy(newNumber, number.bytes, number.length);
  return (longNumber) {newNumber, number.length};
}

unsigned char isZero (longNumber number) {
  unsigned pos;
  for (pos = number.length - 1; pos < number.length; pos --)
    if (number.bytes[pos])
      return 0;
  return 1;
}

longNumber add (longNumber number1, longNumber number2) {
  longNumber numbers[2] = {number1, number2};
  return addMultiple(numbers, 2);
}

longNumber addMultiple (longNumber * numbers, unsigned amount) {
  unsigned long long total;
  unsigned pos;
  unsigned current;
  unsigned resultLength;
  unsigned char * result;
  if (!amount) return createNumber(0);
  if (amount == 1) return copyNumber(*numbers);
  resultLength = (*numbers).length;
  for (current = 1; current < amount; current ++)
    if ((numbers[current]).length > resultLength)
      resultLength = (numbers[current]).length;
  resultLength += sizeof(unsigned);
  total = 0;
  result = malloc(resultLength);
  for (pos = 0; pos < resultLength; pos ++) {
    for (current = 0; current < amount; current ++)
      total += (pos < (numbers[current]).length) ? ((numbers[current]).bytes[pos]) : 0;
    result[pos] = total & 255;
    total >>= 8; // keeps the carry
  }
  for (; (resultLength > 1) && (!(result[resultLength - 1])); resultLength --);
  result = realloc(result, resultLength);
  return (longNumber) {result, resultLength};
}

longNumber multiplyDigit (longNumber number, unsigned char digit) {
  if (!digit) return createNumber(0);
  if (digit == 1) return copyNumber(number);
  unsigned resultLength = number.length + 1;
  unsigned char * result = malloc(resultLength);
  unsigned short total = 0;
  unsigned pos;
  for (pos = 0; pos < number.length; pos ++) {
    total += number.bytes[pos] * digit;
    result[pos] = total & 255;
    total >>= 8;
  }
  result[number.length] = total;
  for (; (resultLength > 1) && (!(result[resultLength - 1])); resultLength --);
  result = realloc(result, resultLength);
  return (longNumber) {result, resultLength};
}

longNumber divideDigit (longNumber number, unsigned char divisor, unsigned char * remainder) {
  if (!divisor) return (longNumber) {NULL, 0}; // BLACKHOLE!!!
  if (divisor == 1) {
    if (remainder) *remainder = 0;
    return copyNumber(number);
  }
  unsigned resultLength = number.length;
  unsigned char * result = malloc(resultLength);
  unsigned pos;
  unsigned short total = 0;
  for (pos = resultLength - 1; pos < resultLength /* -1 = 4294967295 or so */; pos --) {
    total <<= 8;
    total += number.bytes[pos];
    result[pos] = total / divisor;
    total %= divisor;
  }
  if (remainder) *remainder = total;
  for (; (resultLength > 1) && (!(result[resultLength - 1])); resultLength --);
  result = realloc(result, resultLength);
  return (longNumber) {result, resultLength};
}