/*
 *  libbigint is a big integer arithmetic library
 *  Copyright (C) 2001 Ray Strode
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2.1 of the License, or (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */
#include "bigint.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

/*
 * Floor of log base 2
 */
#define lg(n) ((int) (log10(n) / .30102999566398))

/*
 * FIXME: Not fully implemented.  For now keep it 10.
 */
#define RADIX 10

static unsigned int digit_bundle_capacity(); 
static void digit_bundle_new(bigint *num); 

static unsigned int digit_bundle_digit_bits() {
    static unsigned int digit_bits = 0;

    /*
     * Only find the result once and cache it for next time.
     */
    if (digit_bits == 0) digit_bits = (unsigned int) lg(RADIX) + 1; 

    return digit_bits;
}

static unsigned int digit_bundle_capacity() {

    /*
     * 8 == number of bits in a byte
     */
    return (sizeof(int) * 8)/digit_bundle_digit_bits();
}

static void digit_bundle_new(bigint *num) {
    digit_bundle *new_bundle = NULL, *last_bundle = NULL;

    if (num == NULL) return;

    /*
     * Allocate room for bundle
     */
    new_bundle = (digit_bundle *) calloc(sizeof(digit_bundle), 1);
    last_bundle = num->last_bundle;

    /*
     * If there are other bundles, then connect this one to them.
     * Otherwise, set this bundle to be the first bundle.
     */
    if (last_bundle != NULL) {
        new_bundle->prev = last_bundle;
        last_bundle->next = new_bundle;
    } else {

        num->first_bundle = new_bundle;

        /*
         * Just in case the user of the library forgets.
         */
        big_int_seek_start(num);
    }
    
    num->last_bundle = new_bundle;
}

const char *big_int_version() {
    static const char version[] = "1.0";

    return version;
}

bigint *big_int_new() {

    bigint *num = NULL;
    
    /*
     * Allocate and zero space for the bigint
     */
    num = (bigint *) calloc(sizeof(bigint), 1);

    /*
     * Initial bundle 
     */
    digit_bundle_new(num);

    return num;
}

bigint *big_int_new_from_string(const char *string) {

    bigint *num = NULL;
    const char *ch = NULL;
    
    if (string == NULL) return NULL;

    /*
     * Create the big int
     */
    num = big_int_new();
    
    if (num == NULL) return NULL;

    /*
     * Is it negative?
     */
    if (string[0] == '-') big_int_change_negative_state(num, 1);

    /*
     * Populate the bigint
     */
    for (ch = string + strlen(string); ch >= string; ch--) {
        big_int_append_digit(num, (unsigned int) (*ch - '0'));
    }

    return num;  
}

void big_int_append_digit(bigint *num, unsigned int digit) {
    
    /*
     * Don't allow bogus inputs
     */
    if (num == NULL || digit > 9) return;

    /*
     * Pack the digit into the number
     */
    num->last_bundle->packed_number |= 
       (digit << (digit_bundle_digit_bits() * num->last_offset));

    /*
     * Update the offset to the correct location
     */
    num->last_offset = (num->last_offset + 1) % digit_bundle_capacity();
    
    /*
     * Is it time to add on another bundle?
     */
    if (num->last_offset == 0) digit_bundle_new(num);

}

void big_int_print(bigint *num) {

    int digit = -1;

    if (num == NULL) return;
    
    /*
     * Clone it because we are going to change it
     */
    num = big_int_copy(num);

    /*
     * Removing the leading zeros
     */
    big_int_trim(num);

    /*
     * Print a negative sign if necessary
     */
    if (big_int_is_negative(num)) printf("-");

    /*
     * Go to the most significant digit
     */
    big_int_seek_end(num);

    /*
     * Print each successive digit
     */
    while((digit = big_int_prev_digit(num)) != -1) printf("%d", digit);

    /*
     * Delete the copy
     */
    big_int_delete(num);

}

int big_int_compare(bigint *num1, bigint *num2) {

    int num1_digit, num2_digit;
    
    /*
     * Trivial checks (one of the numbers is NULL)
     */
    if (num1 && num2 == NULL) return 1;
    if (num1 == NULL && num2) return -1;
    if (num1 == NULL && num2 == NULL) return 0;

    /*
     * Save state 
     */
    big_int_push_state(num1);
    big_int_push_state(num2);

    /*
     * This is a very large performance hit, but there is nothing I can
     * think of to do better. It just checks if one has more digits than the 
     * other
     */
    big_int_seek_start(num1); 
    big_int_seek_start(num2); 

    while (1) {

        if (big_int_next_digit(num1) == -1) {
            if (big_int_next_digit(num2) != -1) {

                /*
                 * Restore state 
                 */
                big_int_pop_state(num1);
                big_int_pop_state(num2);

                return -1;
            } else break;
        }

        if (big_int_next_digit(num2) == -1) {

            /*
             * Restore state 
             */
            big_int_pop_state(num1);
            big_int_pop_state(num2);

            return 1;
        }
    }

    /*
     * The harder case: they have same amount of digits.
     */

    /*
     * Go to the most significant digit
     */
    big_int_seek_end(num1); 
    big_int_seek_end(num2); 

    /*
     * Compare against each successive digit
     */
    while ((num1_digit = big_int_prev_digit(num1)) != -1 && 
           (num2_digit = big_int_prev_digit(num2)) != -1)
           if (num1_digit > num2_digit) {

               /*
                * Restore state 
                */
               big_int_pop_state(num1);
               big_int_pop_state(num2);

               return 1;
           } else if (num1_digit < num2_digit) {

               /*
                * Restore state 
                */
               big_int_pop_state(num1);
               big_int_pop_state(num2);

               return -1;
           }
    /*
     * Restore state 
     */
    big_int_pop_state(num1);
    big_int_pop_state(num2);

    /*
     * If it made it this far, the numbers are identical
     */
    return 0;
}

/*
 * FIXME: big_int_copy() does not copy the state stack.
 * Doing so would be very complicated and the most 
 * obvious implementation suffers from very, very 
 * poor performance.  Furthermore, it doesn't save the
 * bigints current state for similar (but not identical) reasons.
 */
bigint *big_int_copy(bigint *num) {

    bigint *copy;
    digit_bundle *bundle = NULL;
    int digit;

    if (num == NULL) return NULL;

    /*
     * Allocate space
     */
    copy = big_int_new();

    /*
     * Copy the flags
     */
    copy->flags = num->flags;
    
    /*
     * Copy all the digits
     */
    big_int_push_state(num);
    big_int_seek_start(num);
    while ((digit = big_int_next_digit(num)) != -1) big_int_append_digit(copy, digit);
    big_int_pop_state(num);

    big_int_seek_start(copy);

    return copy;
}

int big_int_next_digit(bigint *num) {

    unsigned int digit = -1, digit_mask = 0;
    int offset = -1;

    if (num == NULL) return -1; 

    /*
     * Have we ran out of bundles?
     */
    if (num->current_bundle == NULL) {
        if (num->current_offset == 0) return -1; 
    
        big_int_seek_start(num);  // Previously called big_int_prev_digit()
    }

    /*
     * Get offset into the packed number
     */
    offset = num->current_offset * digit_bundle_digit_bits();

    /*
     * Create a bitmask to extract the number
     */
    digit_mask = 0xF << offset;

    /*
     * Now extract the number
     */
    digit = (num->current_bundle->packed_number & digit_mask) >> offset;

    /*
     * If we are at the end set the offset to 0
     */
    if (num->current_bundle == num->last_bundle 
            && num->current_offset == num->last_offset) {

        num->current_offset = 0;
    } else {

        /*
         * Increment the offset
         */
        num->current_offset = 
            (num->current_offset + 1) % digit_bundle_capacity();
    }

    /*
     * If we are at offset 0 after being incremented then we need to go to 
     * the next bundle
     */
    if (num->current_offset == 0) {
        num->current_bundle = num->current_bundle->next;
    }

    return digit;
}

int big_int_prev_digit(bigint *num) {

    unsigned int digit = -1, digit_mask = 0;
    int offset = -1;

    if (num == NULL) return -1; 

    /*
     * Have we run out of bundles?
     */
    if (num->current_bundle == NULL) {
        if (num->current_offset == digit_bundle_capacity() - 1) return -1; 

        big_int_seek_end(num);  // Previously called big_int_next_digit()
    }

    /*
     * Get offset into the packed number
     */
    offset = num->current_offset * digit_bundle_digit_bits();

    /*
     * Create a bitmask to extract the number
     */
    digit_mask = 0xF << offset;

    /*
     * Now extract the number
     */
    digit = (num->current_bundle->packed_number & digit_mask) >> offset;

    /*
     * Decrement the offset
     */
    offset = num->current_offset - 1;
    if (offset < 0) offset = offset + digit_bundle_capacity();
    num->current_offset = offset;

    /*
     * If the offset is at it's highest value after decrementing, then go to 
     * the previous bundle
     */
    if (num->current_offset == digit_bundle_capacity() - 1) {
        num->current_bundle = num->current_bundle->prev;
    }

    return digit;
}

void big_int_seek_start(bigint *num) {

    if (num == NULL) return;

    /*
     * Rewind the cursor thing to the begining
     */
    num->current_bundle = num->first_bundle;
    num->current_offset = 0;
}

void big_int_seek_end(bigint *num) {

    if (num == NULL) return;

    /*
     * Fast forward the cursor thing to the end 
     */
    num->current_bundle = num->last_bundle;
    num->current_offset = num->last_offset;
}

void big_int_trim(bigint *num) {
    
    if (num == NULL) return;

    /*
     * Go to the most significant digit
     */
    big_int_seek_end(num);

    /*
     * Loop through each digit that is a leading zero and trim it off
     */
    while (big_int_prev_digit(num) == 0) {

        if (((num->current_offset + 1) % digit_bundle_capacity() == 0)
                && num->current_bundle != NULL 
                && num->current_bundle->next != NULL) {

            /*
             * Plug potential leaks
             */
            free(num->current_bundle->next);
            num->current_bundle->next = NULL;
        }

        /*
         * Trim 
         */
        num->last_bundle = num->current_bundle;
        num->last_offset = num->current_offset;

        /*
         * Well, we need one zero, if that's all there is
         */
        if (num->current_bundle == num->first_bundle 
                && num->current_offset == 0) break;
    }
}

void big_int_change_negative_state(bigint *num, int negative) {

    if (num == NULL) return;

    /* 
     * If we should make num negative then do so,
     * otherwise make it positive
     */
    if (negative) big_int_set_flag(num, BIG_INT_FLAG_NEGATIVE);
    else big_int_unset_flag(num, BIG_INT_FLAG_NEGATIVE);
}

int big_int_is_negative(bigint *num) {

    if (num == NULL) return 0;

    /*
     * Return whether num is negative or not.
     */
    return big_int_is_flag_set(num, BIG_INT_FLAG_NEGATIVE);
}

void big_int_set_flag(bigint *num, int flag) {

    if (num == NULL) return;

    /*
     * Set the flag in the bigint
     */
    num->flags |= flag;
}

void big_int_unset_flag(bigint *num, int flag) {

    if (num == NULL) return;

    /*
     * Unset the flag in the bigint
     */
    num->flags &= ~flag;
}

int big_int_is_flag_set(bigint *num, int flag) {
    
    if (num == NULL) return 1;

    /*
     * Read the flags state from the bigint
     */
    return num->flags & flag; 
}

void big_int_delete(bigint *num) {

    digit_bundle *bundle = NULL;

    if (num == NULL) return;

    /*
     * Start with the last bundle
     */
    bundle = num->last_bundle;

    /*
     * Loop backward, deallocating all the memory along the way.
     */
    while (bundle->prev != NULL) {
       bundle = bundle->prev; 
       free(bundle->next);
    }

    /*
     * And get the last (well first) one, too.
     */
    free(num->first_bundle);

    /*
     * Pop all the state off the state stack
     */
    while (num->saved_state != NULL) big_int_pop_state(num);

    /*
     * Point num members to NULL. Not needed, but may make squashing 
     * a certain bug easier for application developers.
     */
    num->first_bundle = NULL;
    num->last_bundle = NULL;
    num->current_bundle = NULL;

    /*
     * Finally, deallocate the whole structure.
     */
    free(num);
}

bigint *big_int_add(bigint *op1, bigint *op2) {

    bigint *sum = NULL, *tmp = NULL;

    int carry_digit = 0, sum_digit = 0, op1_digit = 0, op2_digit = 0;

    /*
     * Trivial cases
     */
    if (op1 && op2 == NULL) return big_int_copy(op1);
    if (op1 == NULL && op2) return big_int_copy(op2);
    if (op1 == NULL && op2 == NULL) return NULL;

    big_int_push_state(op1);
    big_int_push_state(op2);

    /*
     * Make the one with the bigger one op1.
     */
    if (big_int_compare(op1, op2) < 0) {

        /*
         * Make the swap
         */
        tmp = op2;
        op2 = op1;
        op1 = tmp;
    }

    /*
     * Create a bigint for the sum
     */
    sum = big_int_new();

    /*
     * Go to the least significant digit
     */
    big_int_seek_start(op1);
    big_int_seek_start(op2);
   
    /*
     * Add the none trivial digits.
     */
    while ((op2_digit = big_int_next_digit(op2)) != -1) {
        
        op1_digit = big_int_next_digit(op1);

        /*
         * Are we subtracting or adding.
         */
        if (!big_int_is_negative(op1) && big_int_is_negative(op2)) {
            sum_digit = op1_digit - op2_digit + carry_digit;

            if (sum_digit < 0) {
                sum_digit += 10;
                carry_digit = 0; 
            }

            big_int_append_digit(sum, sum_digit);

        } else {
            sum_digit = op1_digit + op2_digit + carry_digit;

            big_int_append_digit(sum, sum_digit % 10);
            carry_digit =  sum_digit / 10;
        } 
    } 

    /*
     * Tack on the rest.
     */
    while ((sum_digit = big_int_next_digit(op1)) != -1) {
        sum_digit += carry_digit;

        big_int_append_digit(sum, sum_digit % 10);
        carry_digit = sum_digit / 10;
    }

    /*
     * Is there anything left?
     */
    if (carry_digit != 0) {
       big_int_append_digit(sum, carry_digit);
       carry_digit = 0;
    }

    if (big_int_is_negative(op1)) big_int_change_negative_state(sum, 1);

    /*
     * Restore the offset and bundle
     */
    big_int_pop_state(op1);
    big_int_pop_state(op2);

    return sum;
}

bigint *big_int_multiply(bigint *op1, bigint *op2) {

    bigint *product = NULL, *tmp = NULL, *intermediary = NULL;
    
    int carry_digit = 0, op1_digit = -1, op2_digit = -1, product_digit = -1;
    int num_place_holders = 0, i = 0;

    /*
     * Trivial cases
     */
    if (op1 == NULL || op2 == NULL) return NULL;

    big_int_push_state(op1);
    big_int_push_state(op2);

    /*
     * Make the bigger one op1.
     */
    if (big_int_compare(op1, op2) < 0) {

        /*
         * Make the swap.
         */
        tmp = op2;
        op2 = op1;
        op1 = tmp;
        tmp = NULL;
    }

    /*
     * Go to the least significant digit
     */
    big_int_seek_start(op2);

    /*
     * Do the multication part of multiplication
     */
    while((op2_digit = big_int_next_digit(op2)) != -1) {
        
        /*
         * Make a new intermediary bigint
         */
        intermediary = big_int_new(); 

        /*
         * Optimization, the if statement could be removed.
         */
        if (op2_digit != 0) {

            /*
             * Add the place holders
             */
            for (i = 0; i < num_place_holders; i++) 
                big_int_append_digit(intermediary, 0);

            /*
             * Go to the least significant digit
             */
            big_int_seek_start(op1);

            while ((op1_digit = big_int_next_digit(op1)) != -1) {
                
                /*
                 * Small optimization, really only need the else block.
                 */
                if (op2_digit == 1) {

                    big_int_append_digit(intermediary, op1_digit);
                    carry_digit = 0;

                } else {

                    /*
                     * Do the multiplication for one digit 
                     */
                    product_digit = op1_digit * op2_digit + carry_digit; 
                    carry_digit = product_digit / 10;

                    /*
                     * Add it to the intermediary bigint
                     */
                    big_int_append_digit(intermediary, product_digit % 10);

                }
            }

            /*
             * Is there anything left?
             */
            if (carry_digit != 0) {
                big_int_append_digit(intermediary, carry_digit);
                carry_digit = 0;
            }
        }

        /*
         * If this is the first time then intermediary is all we've got,
         * otherwise add intermediary to what we've got.
         */
        if (product == NULL) {
            product = intermediary;
        } else {
            tmp = product;
            product = big_int_add(product, intermediary);
            big_int_delete(tmp);
            big_int_delete(intermediary);
        }

        num_place_holders++;
    }

    if ((big_int_is_negative(op1) && !big_int_is_negative(op2)) ||
        (!big_int_is_negative(op1) && big_int_is_negative(op2)))
        big_int_change_negative_state(product, 1);

    big_int_pop_state(op1);
    big_int_pop_state(op2);

    return product;
}

void big_int_push_state(bigint *num) {

    state_stack *node = NULL;

    if (num == NULL) return;

    /*
     * Save state in a new node of the state stack
     */
    node = calloc(sizeof(state_stack), 1);

    node->bundle = num->current_bundle;
    node->offset = num->current_offset;
    node->flags = num->flags;
    node->next = num->saved_state;
    num->saved_state = node;

}

void big_int_pop_state(bigint *num) {

    state_stack *node = NULL;

    if (num == NULL) return;

    /*
     * Grab the last node that was saved.
     */
    node = num->saved_state;

    if (node == NULL) {
        fprintf(stderr, "\n** WARNING **"
                        " State stack (%p) popped before being pushed! "
                        "** WARNING **\n", num);
        return;
    }

    /*
     * Set the current state to match it 
     */
    num->current_bundle = node->bundle;
    num->current_offset = node->offset;
    num->flags = node->flags;
    num->saved_state = num->saved_state->next;

    free(node);
}

/*
 * FIXME: Decide if this is really a useful addition to the API.
 *        Note: it is destined to fail for large enough numbers and bigints
 *              can be arbitrarily large.
 *        Note2: requires an implementation of big_int_size()
 */
#if 0
char *big_int_to_string(bigint *num) {

    int digit = -1, i;
    char *string = NULL;
    int neg = 0;

    if (num == NULL) return;
    
    /*
     * Clone it because we are going to change it
     */
    num = big_int_copy(num);

    /*
     * Removing the leading zeros
     */
    big_int_trim(num);

    neg = big_int_is_negative(num)? 1: 0;

    /*
     * Allocate space for the string
     */
    string = (char *) malloc((big_int_size(num) + 1 + neg) * sizeof(char));

    /*
     * Go to the least significant digit
     */
    big_int_seek_end(num);

    /*
     * If number is negative add a negative sign
     */
    if (neg) string[0] = '-';

    /*
     * Add each successive digit to the string
     * It just so happens that neg holds the value of the starting index
     */
    for (i = neg; (digit = big_int_prev_digit(num)) != -1; i++) {
        string[i] = digit + '0';
    }

    /*
     * Terminate the string
     */
    string[i] = 0;

    return string;
}
#endif