/*
 * bignum.c
 *
 *  Created on: Jan 7, 2010
 *      Author: petergoodman
 *     Version: $Id$
 *
 * Arbitrary precision integer arithmetic library. This library is tuned to be
 * good at printing such integers as opposed to performing actual arithmetic on
 * them. Also, this library assumes that memory is not a premium.
 */

#include "bignum.h"

#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define BASE 10

/* -------------------------------------------------------------------------- */

/* type representing a bignum. deals exclusively with chars as that is both
 * simple and fairly dependable. */
struct bignum_s {
    size_t num_bytes;
    size_t num_used_bytes;
    unsigned char *bytes;
};

/* -------------------------------------------------------------------------- */

/**
 * Grow the size of a bignum and clear out the new space.
 */
static bignum_t update_bignum(const bignum_t num, const size_t num_bytes) {

    const size_t new_mem_size = sizeof(struct bignum_s) + num_bytes;
    const bignum_t new_num = (bignum_t) realloc(num, new_mem_size);

    if(NULL == new_num) {
        fprintf(stderr, "Unable to re-allocate bignum.\n");
        exit(EXIT_FAILURE);
    }

    new_num->bytes = &(((unsigned char *) new_num)[sizeof(struct bignum_s)]);
    memset( /* clear out the new area */
        &(new_num->bytes[new_num->num_bytes]),
        0,
        num_bytes - new_num->num_bytes
    );
    new_num->num_bytes = num_bytes;

    return new_num;
}

/**
 * Add 3 numbers together, limiting their values from 0 to 9 and returning the
 * carry from the operation.
 */
static unsigned char add3(const unsigned int first,
                          const unsigned int second,
                          unsigned int *carry) {
    const unsigned int total = first + second + *carry;
    const unsigned int res = total % BASE;
    *carry = (total - res) / BASE;
    return (unsigned char) (res & 0xFF);
}

/**
 * Given two character arrays, sum the values in each character and then
 * propagate the carry to the next character in the array. This assumes that
 * there is enough space in the first array to hold the result of summing
 * the two arrays in this manner. Returns the number of bytes filled by the
 * addition operation.
 */
static size_t sum_chars(unsigned char *first,
                        unsigned char *second,
                        const size_t num_first,
                        const size_t num_second) {

    const size_t num_common_bytes = MIN(num_first, num_second);
    size_t i = 0;
    unsigned int carry = 0;

    for(; i < num_common_bytes; ++i) {
        first[i] = add3(first[i], second[i], &carry);
    }
    for(; i < num_first; ++i) {
        first[i] = add3(first[i], 0, &carry);
    }

    for(i = num_first; i-- && !first[i]; )
        /* count number of unused tailing bytes */;

    return i + 1;
}

/**
 * Resize a bignum if necessary for an addition operation with another number
 * that uses num_bytes of space.
 */
bignum_t resize_addition(bignum_t num, size_t num_bytes) {
    num_bytes = MAX(num_bytes, num->num_bytes);
    if(num->num_bytes < num_bytes
    || num->bytes[MIN(num->num_bytes - 1, num->num_used_bytes + 1)]) {
        return update_bignum(num, num_bytes + 2);
    }
    return num;
}

/* -------------------------------------------------------------------------- */

/**
 * Allocate a new big integer object with enough space to fill num_digits.
 */
bignum_t bignum_alloc(const size_t num_digits) {
    bignum_t big;
    const size_t mem_size = sizeof(struct bignum_s) + num_digits;

    unsigned char *mem = (unsigned char *) malloc(mem_size);
    if(NULL == mem) {
        fprintf(stderr, "Unable to allocate new bignum.\n");
        exit(EXIT_FAILURE);
    }

    memset(mem, 0, mem_size);
    big = (bignum_t) mem;
    big->num_bytes = num_digits;
    big->num_used_bytes = 0;
    big->bytes = &(mem[sizeof(struct bignum_s)]);

    return big;
}

/**
 * Free the memory associated with a bignum.
 */
bignum_t bignum_free(const bignum_t num) {
    free(num);
    return NULL;
}

/**
 * Change the bignum to have a zero value. Returns the zeroed-out bignum.
 */
bignum_t bignum_zero(const bignum_t num) {
    memset(num->bytes, 0, num->num_bytes);
    num->num_used_bytes = 0;
    return num;
}

/**
 * Take the second bignum parameter and add it into the first, returning the
 * updated version of the first.
 */
bignum_t bignum_add(bignum_t num1, const const_bignum_t num2) {
    num1 = resize_addition(num1, num2->num_used_bytes);
    num1->num_used_bytes = sum_chars(
        num1->bytes,
        num2->bytes,
        num1->num_bytes,
        num2->num_used_bytes
    );
    return num1;
}

/**
 * Take an unsigned integer and add it into a bignum, returning the updated
 * bignum.
 */
bignum_t bignum_add_uint(bignum_t num1, unsigned int num) {
    unsigned char digits[64];
    size_t i = 0;

    for(; num; digits[i++] = (num % BASE), num /= BASE)
        /* convert to the desired base */;

    num1 = resize_addition(num1, i);
    num1->num_used_bytes = sum_chars(
        num1->bytes,
        &(digits[0]),
        num1->num_bytes,
        i
    );
    return num1;
}

/**
 * Print a bignum to a file stream.
 */
void bignum_fprint(const const_bignum_t num, FILE * const stream) {
    size_t i = num->num_bytes;

    for(; i-- && !num->bytes[i]; )
        /* ignore leading zeros */;

    for(i += 1; i--; ) {
        fprintf(stream, "%c", num->bytes[i] + '0');
    }

    fprintf(stream, "\n");
}

int main(void) {

    unsigned int i = 3;
    bignum_t num1 = bignum_alloc(56);
    bignum_t num2 = bignum_alloc(56);
    bignum_t temp = bignum_alloc(56);
    bignum_t swap = NULL;

    num1 = bignum_add_uint(num1, 1);
    num2 = bignum_add_uint(num2, 1);

    printf("%5u: 0 \n", 0);
    printf("%5u: ", 1); bignum_fprint(num1, stdout);
    printf("%5u: ", 2); bignum_fprint(num2, stdout);

    for(; i <= 300; ++i) {
        temp = bignum_add(bignum_add(bignum_zero(temp), num1), num2);

        printf("%5u: ", i);
        bignum_fprint(temp, stdout);

        swap = num1; /* ~ left-rotate a 3-tuple using swap variable */
        num1 = num2;
        num2 = temp;
        temp = swap;
    }

    num1 = bignum_free(num1);
    num2 = bignum_free(num2);
    temp = bignum_free(temp);

    return 0;
}