/*
 * Copyright (c) 2010 Jiri Svoboda
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/** @file Big integers.
 *
 * Sysel type @c int should accomodate large numbers. This implementation
 * is limited by the available memory and range of the @c size_t type used
 * to index digits.
 */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "debug.h"
#include "mytypes.h"

#include "bigint.h"

static void bigint_sign_comb(bool_t srf_a, bigint_t *a, bool_t srf_b,
    bigint_t *b, bigint_t *dest);
static void bigint_add_abs(bigint_t *a, bigint_t *b, bigint_t *dest);
static void bigint_sub_abs(bigint_t *a, bigint_t *b, bigint_t *dest);
static void bigint_shift_mul_dig(bigint_t *a, bigint_word_t b, size_t shift,
    bigint_t *dest);

static void bigint_alloc(bigint_t *bigint, size_t length);
static void bigint_refine_len(bigint_t *bigint);

/** Initialize bigint with value from small integer.
 *
 * Initializes a bigint structure with the provided small value.
 *
 * @param value		Initial value (small int).
 */
void bigint_init(bigint_t *bigint, int value)
{
	size_t length;
	size_t idx;
	int t;

#ifdef DEBUG_BIGINT_TRACE
	printf("Initialize bigint with int value %d.\n", value);
#endif

	if (value < 0) {
		bigint->negative = b_true;
		value = -value;
	} else {
		bigint->negative = b_false;
	}

	/* Determine length. */
	length = 0;
	t = value;
	while (t > 0) {
		length += 1;
		t = t / BIGINT_BASE;
	}

	/* Allocate digit array. */
	bigint_alloc(bigint, length);

	/* Compute digits. */
	t = value;
	for (idx = 0; idx < length; ++idx) {
		bigint->digit[idx] = t % BIGINT_BASE;
		t = t / BIGINT_BASE;
	}
}

/** Shallow copy of integer.
 *
 * @param src		Source.
 * @param dest		Destination.
 */
void bigint_shallow_copy(bigint_t *src, bigint_t *dest)
{
#ifdef DEBUG_BIGINT_TRACE
	printf("Shallow copy of bigint.\n");
#endif
	dest->negative = src->negative;
	dest->digit = src->digit;
	dest->length = src->length;
}
/** Clone big integer.
 *
 * @param src		Source.
 * @param dest		Destination.
 */
void bigint_clone(bigint_t *src, bigint_t *dest)
{
	size_t idx;

#ifdef DEBUG_BIGINT_TRACE
	printf("Clone bigint.\n");
#endif
	/* Copy sign. */
	dest->negative = src->negative;

	/* Allocate dest digit array. */
	bigint_alloc(dest, src->length);

	/* Copy digits. */
	for (idx = 0; idx < dest->length; ++idx)
		dest->digit[idx] = src->digit[idx];
}

/** Compute big integer with reversed sign.
 *
 * @param src		Source.
 * @param dest		Destination.
 */
void bigint_reverse_sign(bigint_t *src, bigint_t *dest)
{
	size_t idx;

#ifdef DEBUG_BIGINT_TRACE
	printf("Reverse-sign copy of bigint.\n");
#endif
	/* Copy reversed sign. */
	dest->negative = !src->negative;

	/* Allocate dest digit array. */
	bigint_alloc(dest, src->length);

	/* Copy digits. */
	for (idx = 0; idx < dest->length; ++idx)
		dest->digit[idx] = src->digit[idx];
}

/** Destroy big integer.
 *
 * Any bigint that is initialized via bigint_init() or any other bigint
 * function that constructs a new bigint value should be destroyed with
 * this function to free memory associated with the bigint. It should
 * also be used to destroy a bigint before it is reused.
 *
 * @param bigint	The bigint to destroy.
 */
void bigint_destroy(bigint_t *bigint)
{
#ifdef DEBUG_BIGINT_TRACE
	printf("Destroy bigint.\n");
#endif
	bigint->negative = b_false;

	bigint->length = 0;

	free(bigint->digit);
	bigint->digit = NULL;
}

/** Get value of big integer.
 *
 * Allows to obtain the value of big integer, provided that it fits
 * into a small integer.
 *
 * @param bigint	Bigint to obtain value from.
 * @param dval		Place to store value.
 * @return		EOK on success, ELIMIT if bigint is too big to fit
 *			to @a dval.
 */
errno_t bigint_get_value_int(bigint_t *bigint, int *dval)
{
	bigint_t vval, diff;
	size_t idx;
	int val;
	bool_t zf;

#ifdef DEBUG_BIGINT_TRACE
	printf("Get int value of bigint.\n");
#endif
	val = 0;
	for (idx = 0; idx < bigint->length; ++idx) {
		val = val * BIGINT_BASE + bigint->digit[idx];
	}

	if (bigint->negative)
		val = -val;

	/* If the value did not fit @c val now contains garbage. Verify. */
	bigint_init(&vval, val);

	bigint_sub(bigint, &vval, &diff);
	zf = bigint_is_zero(&diff);

	bigint_destroy(&vval);
	bigint_destroy(&diff);

	/* If the difference is not zero, the verification failed. */
	if (zf != b_true)
		return EINVAL;

	*dval = val;
	return EOK;
}

/** Determine if bigint is zero.
 *
 * @param bigint	Big integer.
 * @return		b_true if @a bigint is zero, b_false otherwise.
 */
bool_t bigint_is_zero(bigint_t *bigint)
{
#ifdef DEBUG_BIGINT_TRACE
	printf("Determine if bigint is zero.\n");
#endif
	return (bigint->length == 0);
}

/** Determine if bigint is negative.
 *
 * @param bigint	Big integer.
 * @return		b_true if @a bigint is negative, b_false otherwise.
 */
bool_t bigint_is_negative(bigint_t *bigint)
{
#ifdef DEBUG_BIGINT_TRACE
	printf("Determine if bigint is negative\n");
#endif
	/* Verify that we did not accidentaly introduce a negative zero. */
	assert(bigint->negative == b_false || bigint->length > 0);

	return bigint->negative;
}

/** Divide bigint by (unsigned) digit.
 *
 * @param a		Bigint dividend.
 * @param b		Divisor digit.
 * @param quot		Output bigint quotient.
 * @param rem		Output remainder digit.
 */
void bigint_div_digit(bigint_t *a, bigint_word_t b, bigint_t *quot,
    bigint_word_t *rem)
{
	size_t lbound;
	size_t idx;
	bigint_dword_t da, db;
	bigint_dword_t q, r;

#ifdef DEBUG_BIGINT_TRACE
	printf("Divide bigint by digit.\n");
#endif
	lbound = a->length;
	bigint_alloc(quot, lbound);

	quot->negative = a->negative;

	r = 0;
	idx = lbound;
	while (idx > 0) {
		--idx;

		da = a->digit[idx] + r * BIGINT_BASE;
		db = b;

		q = da / db;
		r = da % db;

		quot->digit[idx] = q;
	}

	bigint_refine_len(quot);
	*rem = r;
}

/** Add two big integers.
 *
 * The big integers @a a and @a b are added and the result is stored in
 * @a dest.
 *
 * @param a		First addend.
 * @param b		Second addend.
 * @param dest		Destination bigint.
 */
void bigint_add(bigint_t *a, bigint_t *b, bigint_t *dest)
{
#ifdef DEBUG_BIGINT_TRACE
	printf("Add bigints.\n");
#endif
	bigint_sign_comb(b_false, a, b_false, b, dest);
}

/** Subtract two big integers.
 *
 * The big integers @a a and @a b are subtracted and the result is stored in
 * @a dest.
 *
 * @param a		Minuend.
 * @param b		Subtrahend.
 * @param dest		Destination bigint.
 */
void bigint_sub(bigint_t *a, bigint_t *b, bigint_t *dest)
{
#ifdef DEBUG_BIGINT_TRACE
	printf("Subtract bigints.\n");
#endif
	bigint_sign_comb(b_false, a, b_true, b, dest);
}

/** Multiply two big integers.
 *
 * The big integers @a a and @a b are multiplied and the result is stored in
 * @a dest.
 *
 * @param a		First factor.
 * @param b		Second factor.
 * @param dest		Destination bigint.
 */
void bigint_mul(bigint_t *a, bigint_t *b, bigint_t *dest)
{
	size_t idx;
	bigint_t dprod;
	bigint_t sum;
	bigint_t tmp;

#ifdef DEBUG_BIGINT_TRACE
	printf("Multiply bigints.\n");
#endif
	bigint_init(&sum, 0);
	for (idx = 0; idx < b->length; ++idx) {
		bigint_shift_mul_dig(a, b->digit[idx], idx, &dprod);
		bigint_add(&dprod, &sum, &tmp);
		bigint_destroy(&dprod);

		bigint_destroy(&sum);
		bigint_shallow_copy(&tmp, &sum);
	}

	if (b->negative)
		sum.negative = !sum.negative;

	bigint_shallow_copy(&sum, dest);
}

/** Convert bigint to string.
 *
 * @param bigint	Bigint to convert.
 * @param dptr		Place to store pointer to new string.
 */
void bigint_get_as_string(bigint_t *bigint, char **dptr)
{
	static const char digits[] = { '0', '1', '2', '3', '4', '5', '6',
		'7', '8', '9' };

	bigint_t val, tmp;
	bigint_word_t rem;
	size_t nchars;
	char *str;
	size_t idx;

#ifdef DEBUG_BIGINT_TRACE
	printf("Convert bigint to string.\n");
#endif
	static_assert(BIGINT_BASE >= 10);

	/* Compute number of characters. */
	nchars = 0;

	if (bigint_is_zero(bigint) || bigint->negative)
		nchars += 1; /* '0' or '-' */

	bigint_clone(bigint, &val);
	while (bigint_is_zero(&val) != b_true) {
		bigint_div_digit(&val, 10, &tmp, &rem);
		bigint_destroy(&val);
		bigint_shallow_copy(&tmp, &val);

		nchars += 1;
	}
	bigint_destroy(&val);

	/* Store characters to array. */

	str = malloc(nchars * sizeof(char) + 1);
	if (str == NULL) {
		printf("Memory allocation failed.\n");
		exit(1);
	}

	if (bigint_is_zero(bigint)) {
		str[0] = '0';
	} else if (bigint->negative) {
		str[0] = '-';
	}

	idx = 1;
	bigint_clone(bigint, &val);
	while (bigint_is_zero(&val) != b_true) {
		bigint_div_digit(&val, 10, &tmp, &rem);
		bigint_destroy(&val);
		bigint_shallow_copy(&tmp, &val);

		str[nchars - idx] = digits[(int) rem];
		++idx;
	}

	bigint_destroy(&val);
	str[nchars] = '\0';
	*dptr = str;
}

/** Print bigint to standard output.
 *
 * @param bigint	Bigint to print.
 */
void bigint_print(bigint_t *bigint)
{
	char *str;

#ifdef DEBUG_BIGINT_TRACE
	printf("Print bigint.\n");
#endif
	bigint_get_as_string(bigint, &str);
	printf("%s", str);
	free(str);
}

/** Compute sign combination of two big integers.
 *
 * Of the big integers @a a and @a b each is optionally sign-reversed and then
 * they are added and the result is stored in @a dest.
 *
 * @param srf_a		First sign reversal flag.
 * @param a		First bigint.
 * @param srf_b		Second sign reversal flag.
 * @param b		Second bigint.
 * @param dest		Destination bigint.
 */
static void bigint_sign_comb(bool_t srf_a, bigint_t *a, bool_t srf_b,
    bigint_t *b, bigint_t *dest)
{
	bool_t neg_a, neg_b;

#ifdef DEBUG_BIGINT_TRACE
	printf("Signed combination of two bigints.\n");
#endif
	/* Compute resulting signs of combination elements. */
	neg_a = (srf_a != a->negative);
	neg_b = (srf_b != b->negative);

	if (neg_a == neg_b) {
		bigint_add_abs(a, b, dest);
		dest->negative = neg_a;
	} else {
		bigint_sub_abs(a, b, dest);
		dest->negative = (neg_a != dest->negative);
	}
}

/** Add absolute values of two big integers.
 *
 * The absolute values of big integers @a a and @a b are added and the result
 * is stored in @a dest.
 *
 * @param a		First addend.
 * @param b		Second addend.
 * @param dest		Destination bigint.
 */
static void bigint_add_abs(bigint_t *a, bigint_t *b, bigint_t *dest)
{
	size_t lbound;
	size_t idx;
	bigint_dword_t da, db;
	bigint_dword_t tmp;
	bigint_word_t res, carry;

#ifdef DEBUG_BIGINT_TRACE
	printf("Add absolute values of bigints.\n");
#endif
	/* max(a->length, b->length) + 1 */
	lbound = (a->length > b->length ? a->length : b->length) + 1;
	dest->negative = b_false;

	bigint_alloc(dest, lbound);
	carry = 0;

	for (idx = 0; idx < lbound; ++idx) {
		da = idx < a->length ? a->digit[idx] : 0;
		db = idx < b->length ? b->digit[idx] : 0;

		tmp = da + db + (bigint_word_t) carry;

		carry = (bigint_word_t) (tmp / BIGINT_BASE);
		res = (bigint_word_t) (tmp % BIGINT_BASE);

		dest->digit[idx] = res;
	}

	/* If our lbound is correct, carry must be zero. */
	assert(carry == 0);

	bigint_refine_len(dest);
}

/** Subtract absolute values of two big integers.
 *
 * The absolute values of big integers @a a and @a b are subtracted and the
 * result is stored in @a dest.
 *
 * @param a		Minuend.
 * @param b		Subtrahend.
 * @param dest		Destination bigint.
 */
static void bigint_sub_abs(bigint_t *a, bigint_t *b, bigint_t *dest)
{
	size_t lbound;
	size_t idx;
	bigint_dword_t da, db;
	bigint_dword_t tmp;
	bigint_word_t res, borrow;

#ifdef DEBUG_BIGINT_TRACE
	printf("Subtract absolute values of bigints.\n");
#endif
	/* max(a->length, b->length) */
	lbound = a->length > b->length ? a->length : b->length;

	bigint_alloc(dest, lbound);
	borrow = 0;

	for (idx = 0; idx < lbound; ++idx) {
		da = idx < a->length ? a->digit[idx] : 0;
		db = idx < b->length ? b->digit[idx] : 0;

		if (da > db + borrow) {
			tmp = da - db - borrow;
			borrow = 0;
		} else {
			tmp = da + BIGINT_BASE - db - borrow;
			borrow = 1;
		}

		res = (bigint_word_t) tmp;
		dest->digit[idx] = res;
	}

	if (borrow != 0) {
		/* We subtracted the greater number from the smaller. */
		dest->negative = b_true;

		/*
		 * Now we must complement the number to get the correct
		 * absolute value. We do this by subtracting from 10..0
		 * (0 repeated lbound-times).
		 */
		borrow = 0;

		for (idx = 0; idx < lbound; ++idx) {
			da = 0;
			db = dest->digit[idx];

			if (da > db + borrow) {
				tmp = da - db - borrow;
				borrow = 0;
			} else {
				tmp = da + BIGINT_BASE - db - borrow;
				borrow = 1;
			}

			res = (bigint_word_t) tmp;
			dest->digit[idx] = res;
		}

		/* The last step is the '1'. */
		assert(borrow == 1);
	} else {
		dest->negative = b_false;
	}

	bigint_refine_len(dest);
}

/** Multiply big integer by digit.
 *
 * @param a		Bigint factor.
 * @param b		Digit factor.
 * @param dest		Destination bigint.
 */
static void bigint_shift_mul_dig(bigint_t *a, bigint_word_t b, size_t shift,
    bigint_t *dest)
{
	size_t lbound;
	size_t idx;

	bigint_dword_t da, db;
	bigint_dword_t tmp;
	bigint_word_t res, carry;

#ifdef DEBUG_BIGINT_TRACE
	printf("Multiply bigint by digit.\n");
#endif
	/* Compute length bound and allocate. */
	lbound = a->length + shift + 1;
	bigint_alloc(dest, lbound);

	/* Copy sign. */
	dest->negative = a->negative;

	for (idx = 0; idx < shift; ++idx)
		dest->digit[idx] = 0;

	carry = 0;
	for (idx = 0; idx < lbound - shift; ++idx) {
		da = idx < a->length ? a->digit[idx] : 0;
		db = b;

		tmp = da * db + (bigint_word_t) carry;

		carry = (bigint_word_t) (tmp / BIGINT_BASE);
		res = (bigint_word_t) (tmp % BIGINT_BASE);

		dest->digit[shift + idx] = res;
	}

	/* If our lbound is correct, carry must be zero. */
	assert(carry == 0);

	bigint_refine_len(dest);
}


/** Allocate bigint of the given length.
 *
 * @param bigint	Bigint whose digit array should be allocated.
 * @param length	Length of array (also set as bigint length).
 */
static void bigint_alloc(bigint_t *bigint, size_t length)
{
	size_t a_length;

#ifdef DEBUG_BIGINT_TRACE
	printf("Allocate bigint digit array.\n");
#endif
	/* malloc() sometimes cannot allocate blocks of zero size. */
	if (length == 0)
		a_length = 1;
	else
		a_length = length;

	bigint->digit = malloc(a_length * sizeof(bigint_word_t));
	if (bigint->digit == NULL) {
		printf("Memory allocation failed.\n");
		exit(1);
	}

	bigint->length = length;
}

/** Adjust length field of bigint to be exact.
 *
 * When bigint is allocated with bigint_alloc() its length can be
 * imprecise (higher than actually number of non-zero digits).
 * Then this function is used to lower @c length to the exact value.
 */
static void bigint_refine_len(bigint_t *bigint)
{
#ifdef DEBUG_BIGINT_TRACE
	printf("Refine bigint length.\n");
#endif
	while (bigint->length > 0 && bigint->digit[bigint->length - 1] == 0)
		bigint->length -= 1;

	if (bigint->length == 0)
		bigint->negative = b_false;
}