aboutsummaryrefslogtreecommitdiff
path: root/src/bigint.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/bigint.c')
-rw-r--r--src/bigint.c1558
1 files changed, 1558 insertions, 0 deletions
diff --git a/src/bigint.c b/src/bigint.c
new file mode 100644
index 0000000..240dbb2
--- /dev/null
+++ b/src/bigint.c
@@ -0,0 +1,1558 @@
+#include <bh/internal/bigint.h>
+#include <limits.h>
+#include <stdlib.h>
+#include <string.h>
+
+static size_t bh_bigint_type_clz(BH_BIGINT_TYPE x)
+{
+ static const bh_uint8_t lookup[256] = {
+ 8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
+ 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
+ };
+
+ size_t i, tmp;
+
+ for (i = 0; i < BH_BIGINT_BITS / 8 + 1; i++)
+ {
+ tmp = (x >> (BH_BIGINT_BITS - 7)) & 0xFF;
+
+ if (tmp)
+ return lookup[tmp] + 8 * i - 1;
+
+ x <<= 8;
+ }
+
+ return BH_BIGINT_BITS;
+}
+
+static size_t bh_bigint_type_log2(BH_BIGINT_TYPE x)
+{
+ static const bh_uint8_t lookup[256] = {
+ 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
+ 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
+ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
+ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
+ 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
+ 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
+ 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
+ 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
+ };
+
+ size_t i, tmp;
+
+ for (i = 0; i < BH_BIGINT_BITS / 8 + 1; i++)
+ {
+ tmp = (x >> (BH_BIGINT_BITS - 7)) & 0xFF;
+ if (tmp)
+ return ((BH_BIGINT_BITS + 1) - 8 * (i + 1)) + lookup[tmp];
+
+ x <<= 8;
+ }
+
+ return 0;
+}
+
+bh_bigint_t *bh_bigint_new(void)
+{
+ bh_bigint_t *result;
+
+ result = malloc(sizeof(*result));
+ if (result)
+ bh_bigint_init(result);
+
+ return result;
+}
+
+void bh_bigint_free(bh_bigint_t *bigint)
+{
+ bh_bigint_destroy(bigint);
+ free(bigint);
+}
+
+void bh_bigint_init(bh_bigint_t *bigint)
+{
+ bigint->data = NULL;
+ bigint->capacity = 0;
+ bh_bigint_clear(bigint);
+}
+
+void bh_bigint_destroy(bh_bigint_t *bigint)
+{
+ if (bigint->data)
+ free(bigint->data);
+}
+
+int bh_bigint_block(void)
+{
+ return BH_BIGINT_BITS;
+}
+
+int bh_bigint_clear(bh_bigint_t *bigint)
+{
+ bigint->error = 0;
+ bigint->size = 0;
+ bigint->type = 0;
+
+ return BH_OK;
+}
+
+int bh_bigint_set(bh_bigint_t* to,
+ bh_bigint_t* from)
+{
+ /* Shortcut - one of the arguments has error flag set */
+ if (from->error)
+ {
+ to->error = 1;
+ return BH_ERROR;
+ }
+
+ /* Clear up result error flag */
+ to->error = 0;
+
+ /* Reserve space for big integer data */
+ if (to->capacity < from->size)
+ {
+ if (bh_bigint_reserve(to, from->size))
+ {
+ to->error = 1;
+ return BH_OOM;
+ }
+ }
+
+ /* Copy data */
+ memmove(to->data, from->data, sizeof(*from->data) * from->size);
+
+ /* Set fields */
+ to->size = from->size;
+ to->type = from->type;
+
+ return BH_OK;
+}
+
+/*
+ * Universal implementation of set.
+ *
+ * This function:
+ * - determines sign of the input integer
+ * - reserves space in target big integer
+ * - copies data in little-endian like format
+ */
+#define BH_BIGINT_SET_BODY(to, from) \
+ size_t size; \
+ bh_bigint_clear((to)); \
+ if ((from) < 0) { (to)->type = -1; (from) = -(from); } \
+ else if ((from) == 0) { (to)->type = 0; return BH_OK; } \
+ else (to)->type = 1; \
+ if ((to)->capacity < (64 / BH_BIGINT_BITS + 1)) \
+ { \
+ if (bh_bigint_reserve((to), (64 / BH_BIGINT_BITS + 1))) \
+ { \
+ (to)->error = 1; \
+ return BH_OOM; \
+ } \
+ } \
+ for (size = 0; (from); size++) \
+ { \
+ (to)->data[size] = (from) & BH_BIGINT_MASK; \
+ (from) >>= BH_BIGINT_BITS; \
+ } \
+ (to)->size = size; \
+ return BH_OK;
+
+/*
+ * Universal implementation of get.
+ *
+ * This function:
+ * - copies blocks from the most to less significant units
+ * - left shifts result by unit bit width - 1
+ */
+#define BH_BIGINT_GET_BODY(from, rtype) \
+ size_t i; \
+ rtype result = 0; \
+ if ((from)->error) return 0; \
+ for (i = (from)->size; i > 0; i--) \
+ { \
+ result <<= BH_BIGINT_BITS; \
+ result += (from)->data[i - 1]; \
+ } \
+ result *= (from)->type; \
+ return result; \
+
+int bh_bigint_set_int(bh_bigint_t *to,
+ int from)
+{
+ BH_BIGINT_SET_BODY(to, from);
+}
+
+int bh_bigint_set_uint(bh_bigint_t *to,
+ unsigned int from)
+{
+ BH_BIGINT_SET_BODY(to, from);
+}
+
+int bh_bigint_get_int(bh_bigint_t *bigint)
+{
+ BH_BIGINT_GET_BODY(bigint, int);
+}
+
+unsigned int bh_bigint_get_uint(bh_bigint_t *bigint)
+{
+ BH_BIGINT_GET_BODY(bigint, unsigned int);
+}
+
+int bh_bigint_set_int8(bh_bigint_t *to,
+ bh_int8_t from)
+{
+ BH_BIGINT_SET_BODY(to, from);
+}
+
+int bh_bigint_set_uint8(bh_bigint_t *to,
+ bh_uint8_t from)
+{
+ BH_BIGINT_SET_BODY(to, from);
+}
+
+bh_int8_t bh_bigint_get_int8(bh_bigint_t *bigint)
+{
+ BH_BIGINT_GET_BODY(bigint, bh_int8_t);
+}
+
+bh_uint8_t bh_bigint_get_uint8(bh_bigint_t *bigint)
+{
+ BH_BIGINT_GET_BODY(bigint, bh_uint8_t);
+}
+
+int bh_bigint_set_int16(bh_bigint_t *to,
+ bh_int16_t from)
+{
+ BH_BIGINT_SET_BODY(to, from);
+}
+
+int bh_bigint_set_uint16(bh_bigint_t *to,
+ bh_uint16_t from)
+{
+ BH_BIGINT_SET_BODY(to, from);
+}
+
+bh_int16_t bh_bigint_get_int16(bh_bigint_t *bigint)
+{
+ BH_BIGINT_GET_BODY(bigint, bh_int16_t);
+}
+
+bh_uint16_t bh_bigint_get_uint16(bh_bigint_t *bigint)
+{
+ BH_BIGINT_GET_BODY(bigint, bh_uint16_t);
+}
+
+int bh_bigint_set_int32(bh_bigint_t *to,
+ bh_int32_t from)
+{
+ BH_BIGINT_SET_BODY(to, from);
+}
+
+int bh_bigint_set_uint32(bh_bigint_t *to,
+ bh_uint32_t from)
+{
+ BH_BIGINT_SET_BODY(to, from);
+}
+
+bh_int32_t bh_bigint_get_int32(bh_bigint_t *bigint)
+{
+ BH_BIGINT_GET_BODY(bigint, bh_int32_t);
+}
+
+bh_uint32_t bh_bigint_get_uint32(bh_bigint_t *bigint)
+{
+ BH_BIGINT_GET_BODY(bigint, bh_uint32_t);
+}
+
+int bh_bigint_set_int64(bh_bigint_t *to,
+ bh_int64_t from)
+{
+ BH_BIGINT_SET_BODY(to, from);
+}
+
+int bh_bigint_set_uint64(bh_bigint_t *to,
+ bh_uint64_t from)
+{
+ BH_BIGINT_SET_BODY(to, from);
+}
+
+bh_int64_t bh_bigint_get_int64(bh_bigint_t *bigint)
+{
+ BH_BIGINT_GET_BODY(bigint, bh_int64_t);
+}
+
+bh_uint64_t bh_bigint_get_uint64(bh_bigint_t *bigint)
+{
+ BH_BIGINT_GET_BODY(bigint, bh_uint64_t);
+}
+
+size_t bh_bigint_capacity(bh_bigint_t *bigint)
+{
+ return bigint->capacity;
+}
+
+size_t bh_bigint_length(bh_bigint_t *bigint)
+{
+ return bigint->size;
+}
+
+int bh_bigint_reserve(bh_bigint_t *bigint,
+ size_t size)
+{
+ void *data;
+
+ /* Initialize variables */
+ data = NULL;
+
+ /* New capacity can't be lower than current big integer size */
+ if (size < bigint->size)
+ size = bigint->size;
+
+ /* Prevent same size reallocation */
+ if (size == bigint->size)
+ return BH_OK;
+
+ if (size)
+ {
+ /* Allocate memory for the new digit storage */
+ data = malloc(sizeof(*bigint->data) * size);
+ if (!data)
+ return BH_OOM;
+
+ /* Copy existing data */
+ if (bigint->size)
+ memmove(data, bigint->data, sizeof(*bigint->data) * bigint->size);
+ }
+
+ /* If big integer had existing data - free it */
+ if (bigint->data)
+ free(bigint->data);
+
+ /* Update fields */
+ bigint->data = data;
+ bigint->capacity = size;
+
+ return BH_OK;
+}
+
+static int bh_bigint_add_base(bh_bigint_t *to,
+ bh_bigint_t *most,
+ bh_bigint_t *least)
+{
+ BH_BIGINT_TYPE carry, tmp;
+ size_t i;
+
+ /* Clear up result error flag */
+ to->error = 0;
+
+ /* Reserve space for output */
+ if (to->capacity < most->size + 1)
+ {
+ if (bh_bigint_reserve(to, most->size + 1))
+ {
+ to->error = 1;
+ return BH_OOM;
+ }
+ }
+
+ /* Reset carry value */
+ carry = 0;
+
+ /* Main addition loop */
+ for (i = 0; i < least->size; i++)
+ {
+ tmp = most->data[i] + least->data[i] + carry;
+ carry = tmp >> BH_BIGINT_BITS;
+ to->data[i] = tmp & BH_BIGINT_MASK;
+ }
+
+ /* Carry propogation loop */
+ for (; i < most->size; i++)
+ {
+ tmp = most->data[i] + carry;
+ carry = tmp >> BH_BIGINT_BITS;
+ to->data[i] = tmp & BH_BIGINT_MASK;
+ }
+
+ /* Write carry value and update result size */
+ to->data[i] = carry;
+
+ if (carry)
+ to->size = most->size + 1;
+ else
+ to->size = most->size;
+
+ return BH_OK;
+}
+
+static int bh_bigint_sub_base(bh_bigint_t *to,
+ bh_bigint_t *most,
+ bh_bigint_t *least)
+{
+ BH_BIGINT_TYPE carry, tmp;
+ size_t size, i;
+
+ /* Clear up result error flag */
+ to->error = 0;
+
+ /* Reserve space for output */
+ if (to->capacity < most->size)
+ {
+ if (bh_bigint_reserve(to, most->size))
+ {
+ to->error = 1;
+ return BH_OOM;
+ }
+ }
+
+ /* Reset carry and size value */
+ carry = 0;
+ size = 0;
+
+ /* Main subtraction loop */
+ for (i = 0; i < least->size; i++)
+ {
+ tmp = most->data[i] - least->data[i] - carry;
+ carry = tmp >> BH_BIGINT_BITS;
+ to->data[i] = tmp & BH_BIGINT_MASK;
+
+ if (to->data[i])
+ size = i + 1;
+ }
+
+ /* Carry propogation loop */
+ for (; i < most->size; i++)
+ {
+ tmp = most->data[i] - carry;
+ carry = tmp >> BH_BIGINT_BITS;
+ to->data[i] = tmp & BH_BIGINT_MASK;
+
+ if (to->data[i])
+ size = i + 1;
+ }
+
+ /* Update result size */
+ to->size = size;
+ to->error = 0;
+
+ return BH_OK;
+}
+
+int bh_bigint_add(bh_bigint_t *to,
+ bh_bigint_t *left,
+ bh_bigint_t *right)
+{
+ bh_bigint_t *least, *most;
+ int type, code;
+
+ /* Shortcut - one of the arguments has error flag set */
+ if (left->error || right->error)
+ {
+ to->error = 1;
+ return BH_ERROR;
+ }
+
+ /* Determine most and least numbers */
+ if (bh_bigint_equal_mod(left, right) >= 0)
+ {
+ most = left;
+ least = right;
+ type = left->type;
+ }
+ else
+ {
+ most = right;
+ least = left;
+ type = right->type;
+ }
+
+ /* Perform addition or subtraction */
+ if (most->type == least->type)
+ code = bh_bigint_add_base(to, most, least);
+ else
+ code = bh_bigint_sub_base(to, most, least);
+
+ /* Set result sign */
+ if (!code)
+ to->type = type;
+
+ /* Return result code */
+ return code;
+}
+
+int bh_bigint_sub(bh_bigint_t *to,
+ bh_bigint_t *left,
+ bh_bigint_t *right)
+{
+ bh_bigint_t *least, *most;
+ int type, code;
+
+ /* Shortcut - one of the arguments has error flag set */
+ if (left->error || right->error)
+ {
+ to->error = 1;
+ return BH_ERROR;
+ }
+
+ /* Determine most and least numbers */
+ if (bh_bigint_equal_mod(left, right) >= 0)
+ {
+ most = left;
+ least = right;
+ type = left->type;
+ }
+ else
+ {
+ most = right;
+ least = left;
+ type = right->type * -1;
+ }
+
+ /* Perform addition or subtraction */
+ if (most->type == least->type)
+ code = bh_bigint_sub_base(to, most, least);
+ else
+ code = bh_bigint_add_base(to, most, least);
+
+ /* Set result sign */
+ if (!code)
+ to->type = type;
+
+ /* Return result code */
+ return code;
+}
+
+int bh_bigint_mul(bh_bigint_t *to,
+ bh_bigint_t *left,
+ bh_bigint_t *right)
+{
+ bh_bigint_t *result;
+ BH_BIGINT_TYPE carry;
+ BH_BIGINT_TMP tmp;
+ size_t i, j, size;
+
+ /* Shortcut - one of the arguments has error flag set */
+ if (left->error || right->error)
+ {
+ to->error = 1;
+ return BH_ERROR;
+ }
+
+ /* Clear up result error flag */
+ to->error = 0;
+
+ /* Shortcut - multiplication by zero */
+ if (left->type == 0 || right->type == 0)
+ {
+ to->type = 0;
+ to->size = 0;
+ return BH_OK;
+ }
+
+ /* If to is left or right argument - allocate temporary storage */
+ result = to;
+ if (to == left || to == right)
+ {
+ result = bh_bigint_new();
+ if (!result)
+ {
+ to->error = 1;
+ return BH_OOM;
+ }
+ }
+
+ /* Reserve space for result */
+ if (result->capacity < (left->size + right->size + 1))
+ {
+ if (bh_bigint_reserve(result, left->size + right->size + 1))
+ {
+ to->error = 1;
+ return BH_OOM;
+ }
+ }
+
+ /* Clear the result array */
+ memset(result->data, 0, sizeof(*result->data) * (left->size + right->size));
+
+ /* Prepare variables */
+ size = 0;
+
+ /* Multiplication loop */
+ for (i = 0; i < left->size; i++)
+ {
+ carry = 0;
+ for (j = 0; j < right->size; j++)
+ {
+ tmp = (BH_BIGINT_TMP)left->data[i] * (BH_BIGINT_TMP)right->data[j];
+ tmp += carry + result->data[j + i];
+ carry = tmp >> BH_BIGINT_BITS;
+ result->data[j + i] = tmp & BH_BIGINT_MASK;
+ }
+
+ result->data[j + i] = carry;
+ }
+
+ /* Truncate multiplication result size */
+ size = left->size + right->size;
+ while (size && !result->data[size - 1]) size--;
+
+ /* Determine sign */
+ if (left->type != right->type)
+ result->type = -1;
+ else
+ result->type = 1;
+
+ /* Update size */
+ result->size = size;
+
+ /* If tmp is temporary storage - copy data back and deallocate */
+ if (result != to)
+ {
+ bh_bigint_set(to, result);
+ bh_bigint_free(result);
+ }
+
+ return BH_OK;
+}
+
+int bh_bigint_pow(bh_bigint_t *to,
+ bh_bigint_t *from,
+ bh_uint32_t power)
+{
+ bh_bigint_t *base;
+ int code, type;
+
+ /* Initialize variables */
+ base = NULL;
+ code = BH_OK;
+
+ /* Shortcut - one of the arguments has error flag set */
+ if (from->error)
+ {
+ to->error = 1;
+ return BH_ERROR;
+ }
+
+ /* Clear up result error flag */
+ to->error = 0;
+
+ /* Shortcut - power is equal to 0 */
+ if (!power)
+ return bh_bigint_set_int(to, 1);
+
+ /* Shortcut - value is 0 */
+ if (bh_bigint_is_zero(from))
+ return bh_bigint_clear(to);
+
+ /* Determine sign */
+ if (from->type < 0 && power & 0x1)
+ type = -1;
+ else
+ type = 1;
+
+ /* Setup base variable */
+ base = bh_bigint_new();
+ if (!base || bh_bigint_set(base, from))
+ {
+ to->error = 1;
+ code = BH_OOM;
+ goto finish;
+ }
+
+ if (bh_bigint_set_int(to, 1))
+ {
+ to->error = 1;
+ code = BH_OOM;
+ goto finish;
+ }
+
+ /* Perform exponentiation by squaring */
+ while (power)
+ {
+ if (power & 0x1)
+ bh_bigint_mul(to, to, base);
+
+ bh_bigint_mul(base, base, base);
+ power >>= 1;
+
+ /* Stop if error occured */
+ if (base->error || to->error)
+ {
+ to->error = 1;
+ code = BH_ERROR;
+ break;
+ }
+ }
+
+ /* Fix the sign */
+ to->type = type;
+
+finish:
+ /* Free internal variables */
+ if (base)
+ bh_bigint_free(base);
+
+ return code;
+}
+
+int bh_bigint_powm(bh_bigint_t *to,
+ bh_bigint_t *left,
+ bh_bigint_t *right,
+ bh_bigint_t *mod)
+{
+ bh_bigint_t *result, *base, *exponent;
+ int code, type;
+
+ /* Initialize variables */
+ result = NULL; base = NULL; exponent = NULL;
+ code = BH_OK;
+
+ /* Shortcut - one of the arguments has error flag set */
+ if (left->error || right->error)
+ {
+ to->error = 1;
+ return BH_ERROR;
+ }
+
+ /* Clear up result error flag */
+ to->error = 0;
+
+ /* Shortcut - power is equal to 0 */
+ if (bh_bigint_is_zero(right))
+ return bh_bigint_set_int(to, 1);
+
+ /* Shortcut - value is 0 */
+ if (bh_bigint_is_zero(left))
+ return bh_bigint_clear(to);
+
+ /* Shortcut - power is negative */
+ if (bh_bigint_is_negative(right))
+ return bh_bigint_clear(to);
+
+ /* Figure out result sign */
+ if (left->type < 0 && right->data[0] & 0x1)
+ type = -1;
+ else
+ type = 1;
+
+ /* Setup result variable */
+ result = to;
+ if (to == mod)
+ {
+ result = bh_bigint_new();
+ if (!result)
+ {
+ to->error = 1;
+ code = BH_OOM;
+ goto finish;
+ }
+ }
+
+ /* Reserve space for result */
+ if (bh_bigint_reserve(result, mod->size * 2 + 1) || bh_bigint_set_int(result, 1))
+ {
+ to->error = 1;
+ code = BH_OOM;
+ goto finish;
+ }
+
+ /* Setup base variable */
+ base = bh_bigint_new();
+ if (!base || bh_bigint_reserve(base, mod->size * 2 + 1))
+ {
+ to->error = 1;
+ code = BH_OOM;
+ goto finish;
+ }
+
+ if (bh_bigint_mod(base, left, mod))
+ {
+ to->error = 1;
+ code = BH_OOM;
+ goto finish;
+ }
+
+ /* Setup exponent variable */
+ exponent = bh_bigint_new();
+ if (!exponent || bh_bigint_set(exponent, right))
+ {
+ to->error = 1;
+ code = BH_OOM;
+ goto finish;
+ }
+
+ /* Perform exponentiation by squaring */
+ while (!bh_bigint_is_zero(exponent))
+ {
+ if (exponent->data[0] & 0x1)
+ {
+ bh_bigint_mul(result, result, base);
+ bh_bigint_mod(result, result, mod);
+ }
+ bh_bigint_mul(base, base, base);
+ bh_bigint_mod(base, base, mod);
+ bh_bigint_rsh(exponent, exponent, 1);
+
+ /* Stop if error occured */
+ if (base->error || result->error)
+ {
+ to->error = 1;
+ code = BH_ERROR;
+ break;
+ }
+ }
+
+ /* Fix the sign */
+ result->type = type;
+
+finish:
+ /* Free internal variables */
+ if (base)
+ bh_bigint_free(base);
+ if (exponent)
+ bh_bigint_free(exponent);
+ if (result && result != to)
+ {
+ bh_bigint_set(to, result);
+ bh_bigint_free(result);
+ }
+
+ return code;
+}
+
+static BH_BIGINT_TYPE bh_bigint_div_guess(bh_bigint_t *left,
+ bh_bigint_t *right)
+{
+ BH_BIGINT_TMP tmp;
+
+ /* Left is bigger then right */
+ if (bh_bigint_equal_mod(left, right) < 0)
+ return 0;
+
+ /* Make a guess */
+ tmp = left->data[left->size - 1];
+
+ if (left->size != right->size)
+ tmp = (tmp << BH_BIGINT_BITS) + left->data[left->size - 2];
+
+ return tmp / right->data[right->size - 1];
+}
+
+static int bh_bigint_div_base(bh_bigint_t *quotient,
+ bh_bigint_t *remainder,
+ bh_bigint_t *left,
+ bh_bigint_t *right,
+ int *shift)
+{
+ bh_bigint_t *nleft, *nright, *tmp;
+ BH_BIGINT_TYPE q;
+ int code;
+
+ /* Initialize variables */
+ nleft = NULL; nright = NULL; tmp = NULL;
+ code = BH_OK;
+
+ /* Clear up result error flags */
+ if (quotient)
+ quotient->error = 0;
+ remainder->error = 0;
+
+ /* Allocate space for normilized versions of integers and temporary */
+ nleft = bh_bigint_new();
+ if (!nleft || bh_bigint_reserve(nleft, left->size + 1))
+ {
+ if (quotient)
+ quotient->error = 1;
+ remainder->error = 1;
+ code = BH_OOM;
+ goto finish;
+ }
+
+ nright = bh_bigint_new();
+ if (!nright || bh_bigint_reserve(nright, right->size + 1))
+ {
+ if (quotient)
+ quotient->error = 1;
+ remainder->error = 1;
+ code = BH_OOM;
+ goto finish;
+ }
+
+ tmp = bh_bigint_new();
+ if (!tmp || bh_bigint_reserve(tmp, left->size))
+ {
+ if (quotient)
+ quotient->error = 1;
+ remainder->error = 1;
+ code = BH_OOM;
+ goto finish;
+ }
+
+ /* Allocate space for remainder and quotient */
+ if (quotient && (quotient->capacity < left->size + 1))
+ {
+ if (bh_bigint_reserve(quotient, left->size + 1))
+ {
+ if (quotient)
+ quotient->error = 1;
+ remainder->error = 1;
+ code = BH_OOM;
+ goto finish;
+ }
+ }
+
+ if (remainder->capacity < left->size + 1)
+ {
+ if (bh_bigint_reserve(remainder, left->size + 1))
+ {
+ if (quotient)
+ quotient->error = 1;
+ remainder->error = 1;
+ code = BH_OOM;
+ goto finish;
+ }
+ }
+
+ /* Normilize integers */
+ *shift = bh_bigint_type_clz(right->data[right->size - 1]);
+ bh_bigint_lsh(nleft, left, *shift);
+ bh_bigint_lsh(nright, right, *shift);
+
+ /* Reset quotient and remainder. */
+ if (quotient)
+ bh_bigint_set_int(quotient, 0);
+ bh_bigint_set_int(remainder, 0);
+
+ /* Get as many digits from nleft so that remainder >= right */
+ while (bh_bigint_equal_mod(remainder, nright) < 0)
+ {
+ bh_bigint_lsh(remainder, remainder, BH_BIGINT_BITS);
+ remainder->data[0] = nleft->data[nleft->size - 1];
+ if (!remainder->size)
+ {
+ remainder->size = 1;
+ remainder->type = 1;
+ }
+ nleft->size--;
+ }
+
+ while (1)
+ {
+ /* Make a guess at what first digit of quotient should be */
+ q = bh_bigint_div_guess(remainder, nright);
+
+ tmp->size = 1;
+ tmp->type = 1;
+ tmp->data[0] = q;
+ bh_bigint_mul(tmp, nright, tmp);
+
+ /* Decriment quotient digit if our guess was wrong */
+ while (bh_bigint_equal_mod(remainder, tmp) < 0)
+ {
+ q--;
+ tmp->size = 1;
+ tmp->type = 1;
+ tmp->data[0] = q;
+ bh_bigint_mul(tmp, nright, tmp);
+ }
+
+ /* Append guessed digit to quotient (if needed) */
+ if (quotient)
+ {
+ bh_bigint_lsh(quotient, quotient, BH_BIGINT_BITS);
+ quotient->data[0] = q;
+ if (!quotient->size)
+ {
+ quotient->size = 1;
+ quotient->type = 1;
+ }
+ }
+
+ /* Calculate remainder */
+ bh_bigint_sub(remainder, remainder, tmp);
+
+ if (!nleft->size)
+ break;
+
+ /* Fetch remaining digit from nleft */
+ bh_bigint_lsh(remainder, remainder, BH_BIGINT_BITS);
+ remainder->data[0] = nleft->data[nleft->size - 1];
+ if (!remainder->size)
+ {
+ remainder->size = 1;
+ remainder->type = 1;
+ }
+ nleft->size--;
+ }
+
+finish:
+ if (nleft)
+ bh_bigint_free(nleft);
+ if (nright)
+ bh_bigint_free(nright);
+ if (tmp)
+ bh_bigint_free(tmp);
+
+ return code;
+}
+
+int bh_bigint_divmod(bh_bigint_t *quotient,
+ bh_bigint_t *remainder,
+ bh_bigint_t *left,
+ bh_bigint_t *right)
+{
+ int shift, code, type;
+ bh_bigint_t *tmp;
+
+ /* Shortcut - one of the arguments has error flag set */
+ if (left->error || right->error)
+ {
+ if (quotient)
+ quotient->error = 1;
+ if (remainder)
+ remainder->error = 1;
+ return BH_ERROR;
+ }
+
+ /* Clear up result error flags */
+ if (quotient)
+ quotient->error = 0;
+ if (remainder)
+ remainder->error = 0;
+
+ /* Shortcut - left is zero - result is zero */
+ if (left->type == 0)
+ {
+ if (quotient)
+ bh_bigint_clear(quotient);
+ if (remainder)
+ bh_bigint_clear(remainder);
+
+ return BH_OK;
+ }
+
+ /* Shortcut - division by zero */
+ if (right->type == 0)
+ {
+ if (quotient)
+ quotient->error = 1;
+ if (remainder)
+ remainder->error = 1;
+ return BH_ERROR;
+ }
+
+ /* Shortcut - left is less then right - quotient is zero, remainder is left */
+ if (bh_bigint_equal_mod(left, right) < 0)
+ {
+ if (remainder && bh_bigint_set(remainder, left))
+ {
+ if (quotient)
+ quotient->error = 1;
+ remainder->error = 1;
+ return BH_OOM;
+ }
+
+ if (quotient && bh_bigint_clear(quotient))
+ {
+ quotient->error = 1;
+ if (remainder)
+ remainder->error = 1;
+ return BH_OOM;
+ }
+
+ return BH_OK;
+ }
+
+ /* Figure out result sign */
+ if (left->type != right->type)
+ type = -1;
+ else
+ type = 1;
+
+ /* Make sure we have remainder as our working buffer */
+ tmp = remainder;
+ if (!remainder)
+ {
+ tmp = bh_bigint_new();
+ if (!tmp)
+ {
+ if (quotient)
+ quotient->error = 1;
+ if (remainder)
+ remainder->error = 1;
+ return BH_OOM;
+ }
+ }
+
+ code = bh_bigint_div_base(quotient, tmp, left, right, &shift);
+ if (!code)
+ {
+ /* If remainder required - normilize it */
+ if (tmp == remainder)
+ bh_bigint_rsh(remainder, remainder, shift);
+
+ /* Fix the sign */
+ if (quotient)
+ quotient->type = type;
+ }
+
+ if (tmp != remainder)
+ bh_bigint_free(tmp);
+
+ return code;
+}
+
+int bh_bigint_div(bh_bigint_t *to,
+ bh_bigint_t *left,
+ bh_bigint_t *right)
+{
+ return bh_bigint_divmod(to, NULL, left, right);
+}
+
+int bh_bigint_mod(bh_bigint_t *to,
+ bh_bigint_t *left,
+ bh_bigint_t *right)
+{
+ return bh_bigint_divmod(NULL, to, left, right);
+}
+
+int bh_bigint_lsh(bh_bigint_t *to,
+ bh_bigint_t *left,
+ bh_uint32_t shift)
+{
+ size_t i, bits, blocks;
+ BH_BIGINT_TYPE tmp;
+
+ /* Shortcut - one of the arguments has error flag set */
+ if (left->error)
+ {
+ to->error = 1;
+ return BH_ERROR;
+ }
+
+ /* Clear up result error flag */
+ to->error = 0;
+
+ /* Calculate distance in blocks and bits */
+ blocks = shift / BH_BIGINT_BITS;
+ bits = shift % BH_BIGINT_BITS;
+
+ /* Shortcut - initial value is zero */
+ if (left->type == 0)
+ {
+ to->type = 0;
+ to->size = 0;
+ return BH_OK;
+ }
+
+ /* Check if shift is block aligned */
+ if (bits)
+ {
+ /* Shift is not block aligned - reserve space for 1 additional block */
+ if (to->capacity < left->size + blocks + 1)
+ {
+ if (bh_bigint_reserve(to, left->size + blocks + 1))
+ {
+ to->error = 1;
+ return BH_OOM;
+ }
+ }
+
+ /* Main shift loop for unaligned shift */
+ for (i = left->size + blocks + 1; i > blocks; i--)
+ {
+ tmp = 0;
+
+ if (i - blocks - 1 < left->size)
+ tmp |= left->data[i - blocks - 1] << bits;
+ if (i - blocks - 2 < left->size)
+ tmp |= left->data[i - blocks - 2] >> (BH_BIGINT_BITS - bits);
+
+ to->data[i - 1] = tmp & BH_BIGINT_MASK;
+ }
+
+ /* Zero out shifted in blocks */
+ for (; i > 0; i--)
+ to->data[i - 1] = 0;
+
+ /* Trim size to nearest block */
+ i = left->size + blocks + 1;
+ while (i && !to->data[i - 1]) i--;
+ }
+ else
+ {
+ /* Shift is block aligned */
+ if (to->capacity < left->size + blocks)
+ {
+ if (bh_bigint_reserve(to, left->size + blocks))
+ {
+ to->error = 1;
+ return BH_OOM;
+ }
+ }
+
+ /* Main loop for aligned shift */
+ for (i = left->size + blocks; i > blocks; i--)
+ to->data[i - 1] = left->data[i - blocks - 1];
+
+ /* Zero out shifted in blocks */
+ for (; i > 0; i--)
+ to->data[i - 1] = 0;
+
+ /* Trim size to nearest block */
+ i = left->size + blocks;
+ while (i && !to->data[i - 1]) i--;
+ }
+
+ /* Update fields */
+ to->size = i;
+ to->type = left->type;
+
+ return BH_OK;
+}
+
+int bh_bigint_rsh(bh_bigint_t *to,
+ bh_bigint_t *left,
+ bh_uint32_t shift)
+{
+ size_t i, bits, blocks;
+ BH_BIGINT_TYPE tmp;
+
+ /* Shortcut - one of the arguments has error flag set */
+ if (left->error)
+ {
+ to->error = 1;
+ return BH_ERROR;
+ }
+
+ /* Clear up result error flag */
+ to->error = 0;
+
+ /* Calculate distance in blocks and bits */
+ blocks = shift / BH_BIGINT_BITS;
+ bits = shift % BH_BIGINT_BITS;
+
+ /* Shortcut - shift is bigger than value or value is 0 */
+ if (left->type == 0 || left->size < blocks)
+ {
+ to->type = 0;
+ to->size = 0;
+ return BH_OK;
+ }
+
+ /* Check if shift is block aligned */
+ if (bits)
+ {
+ /* Shift is not block aligned */
+ if (to->capacity < left->size - blocks)
+ {
+ if (bh_bigint_reserve(to, left->size - blocks))
+ {
+ to->error = 1;
+ return BH_OOM;
+ }
+ }
+
+ /* Main loop for unaligned shift */
+ for (i = 0; i < left->size - blocks; i++)
+ {
+ tmp = 0;
+
+ if (i + blocks < left->size)
+ tmp |= left->data[i + blocks] >> bits;
+ if (i + blocks + 1 < left->size)
+ tmp |= left->data[i + blocks + 1] << (BH_BIGINT_BITS - bits);
+
+ tmp &= BH_BIGINT_MASK;
+ to->data[i] = tmp;
+ }
+ }
+ else
+ {
+ /* Shift is block aligned */
+ if (to->capacity < left->size - blocks)
+ {
+ if (bh_bigint_reserve(to, left->size - blocks))
+ {
+ to->error = 1;
+ return BH_OOM;
+ }
+ }
+
+ /* Main loop for aligned shift */
+ for (i = 0; i < left->size - blocks; i++)
+ to->data[i] = left->data[i + blocks];
+ }
+
+ /* Trim remaining blocks */
+ i = left->size - blocks;
+ while (i && !to->data[i - 1]) i--;
+
+ /* Update fields */
+ to->size = i;
+ to->type = left->type;
+
+ if (!to->size)
+ to->type = 0;
+
+ return BH_OK;
+}
+
+int bh_bigint_or(bh_bigint_t *to,
+ bh_bigint_t *left,
+ bh_bigint_t *right)
+{
+ size_t i, size;
+ BH_BIGINT_TYPE tmp;
+
+ /* Shortcut - one of the arguments has error flag set */
+ if (left->error || right->error)
+ {
+ to->error = 1;
+ return BH_ERROR;
+ }
+
+ /* Clear up result error flag */
+ to->error = 0;
+
+ /* Calculate resulting size and reserve space */
+ size = (left->size > right->size) ? (left->size) : (right->size);
+ if (to->capacity < size)
+ {
+ if (bh_bigint_reserve(to, size))
+ {
+ to->error = 1;
+ return BH_OOM;
+ }
+ }
+
+ /* Apply OR for each block */
+ for (i = 0; i < size; i++)
+ {
+ tmp = (i < left->size) ? (left->data[i]) : (0);
+ tmp |= (i < right->size) ? (right->data[i]) : (0);
+ to->data[i] = tmp;
+ }
+
+ /* Update fields */
+ to->type = 1;
+ to->size = size;
+
+ return BH_OK;
+}
+
+int bh_bigint_and(bh_bigint_t *to,
+ bh_bigint_t *left,
+ bh_bigint_t *right)
+{
+ size_t i, size;
+ BH_BIGINT_TYPE tmp;
+
+ /* Shortcut - one of the arguments has error flag set */
+ if (left->error || right->error)
+ {
+ to->error = 1;
+ return BH_ERROR;
+ }
+
+ /* Clear up result error flag */
+ to->error = 0;
+
+ /* Calculate resulting size and reserve space */
+ size = (left->size > right->size) ? (left->size) : (right->size);
+ if (to->capacity < size)
+ {
+ if (bh_bigint_reserve(to, size))
+ {
+ to->error = 1;
+ return BH_OOM;
+ }
+ }
+
+ /* Apply AND for each block */
+ for (i = 0; i < size; i++)
+ {
+ tmp = (i < left->size) ? (left->data[i]) : (0);
+ tmp &= (i < right->size) ? (right->data[i]) : (0);
+ to->data[i] = tmp;
+ }
+
+ /* Update fields */
+ to->type = 1;
+ to->size = size;
+
+ return BH_OK;
+}
+
+int bh_bigint_xor(bh_bigint_t *to,
+ bh_bigint_t *left,
+ bh_bigint_t *right)
+{
+ size_t i, size;
+ BH_BIGINT_TYPE tmp;
+
+ /* Shortcut - one of the arguments has error flag set */
+ if (left->error || right->error)
+ {
+ to->error = 1;
+ return BH_ERROR;
+ }
+
+ /* Clear up result error flag */
+ to->error = 0;
+
+ /* Calculate resulting size and reserve space */
+ size = (left->size > right->size) ? (left->size) : (right->size);
+ if (to->capacity < size)
+ {
+ if (bh_bigint_reserve(to, size))
+ {
+ to->error = 1;
+ return BH_OOM;
+ }
+ }
+
+ /* Apply XOR for each block */
+ for (i = 0; i < size; i++)
+ {
+ tmp = (i < left->size) ? (left->data[i]) : (0);
+ tmp ^= (i < right->size) ? (right->data[i]) : (0);
+ to->data[i] = tmp;
+ }
+
+ /* Update fields */
+ to->type = 1;
+ to->size = size;
+
+ return BH_OK;
+}
+
+int bh_bigint_negate(bh_bigint_t *to,
+ bh_bigint_t *from)
+{
+ /* Shortcut - one of the arguments has error flag set */
+ if (from->error)
+ {
+ to->error = 1;
+ return BH_ERROR;
+ }
+
+ /* Clear up result error flag */
+ to->error = 0;
+
+ /* If to and from are not the same - copy data */
+ if (to != from && bh_bigint_set(to, from))
+ {
+ to->error = 1;
+ return BH_OOM;
+ }
+
+ /* Change the sign */
+ if (to->type < 0)
+ to->type = 1;
+ else if (to->type > 0)
+ to->type = -1;
+
+ return BH_OK;
+}
+
+int bh_bigint_equal(bh_bigint_t *left,
+ bh_bigint_t *right)
+{
+ /* Shortcut - one of the arguments have error flag set */
+ if (left->error || right->error)
+ return 0;
+
+ /* Shortcut - check for sign */
+ if (left->type - right->type)
+ return left->type - right->type;
+
+ /* Same sign - check contents */
+ return bh_bigint_equal_mod(left, right);
+}
+
+int bh_bigint_equal_mod(bh_bigint_t *left,
+ bh_bigint_t *right)
+{
+ size_t i;
+
+ /* Shortcut - one of the arguments have error flag set */
+ if (left->error || right->error)
+ return 0;
+
+ /* Shortcut - check for length */
+ if (left->size < right->size)
+ return -1;
+ else if (left->size > right->size)
+ return 1;
+
+ /* Equal length - compare unit by unit from the most significant */
+ for (i = 0; i < left->size; i++)
+ {
+ size_t index = left->size - i - 1;
+
+ if (left->data[index] < right->data[index])
+ return -1;
+ else if (left->data[index] > right->data[index])
+ return 1;
+ }
+
+ /* Units are equal */
+ return 0;
+}
+
+int bh_bigint_is_negative(bh_bigint_t *bigint)
+{
+ if (bigint->error)
+ return 1;
+
+ return bigint->type < 0;
+}
+
+int bh_bigint_is_zero(bh_bigint_t *bigint)
+{
+ if (bigint->error)
+ return 1;
+
+ return bigint->type == 0;
+}
+
+int bh_bigint_is_error(bh_bigint_t *bigint)
+{
+ return bigint->error;
+}
+
+size_t bh_bigint_log2(bh_bigint_t *bigint)
+{
+ size_t result;
+
+ if (bigint->size == 0 || bigint->type == 0)
+ return 0;
+
+ result = bh_bigint_type_log2(bigint->data[bigint->size - 1]);
+ return result + (bigint->size - 1) * BH_BIGINT_BITS;
+} \ No newline at end of file
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-01 01:41:32 +0000