bigint.c

/*
 * 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.
 */

#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);

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;
        }
}

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;
}
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];
}

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];
}

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;
}

int 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;
}

bool_t bigint_is_zero(bigint_t *bigint)
{
#ifdef DEBUG_BIGINT_TRACE
        printf("Determine if bigint is zero.\n");
#endif
        return (bigint->length == 0);
}

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;
}

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;
}

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);
}

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);
}

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);
}

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
        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;
}

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);
}

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);
        }
}

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);
}

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);
}

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);
}


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;
}

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;
}

---