From 4c77ce8fe3cfeb80b878e3d098adbc6c6ac12ca0 Mon Sep 17 00:00:00 2001 From: Mikhail Romanko Date: Sun, 16 Jun 2024 12:29:48 +0300 Subject: Add big integer implementation --- CMakeLists.txt | 3 + include/bh/bigint.h | 143 ++++ include/bh/internal/bigint.h | 31 + include/bh/internal/config.in | 1 + src/bigint.c | 1558 +++++++++++++++++++++++++++++++++++++++++ tests/src/bigint.c | 429 ++++++++++++ 6 files changed, 2165 insertions(+) create mode 100644 include/bh/bigint.h create mode 100644 include/bh/internal/bigint.h create mode 100644 src/bigint.c create mode 100644 tests/src/bigint.c diff --git a/CMakeLists.txt b/CMakeLists.txt index 299eda9..5206382 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -12,6 +12,7 @@ include(CheckSymbolExists) # Project settings option(BH_PLATFORM_THREADS "Enable multithreading support" TRUE) +option(BH_BIGINT_LONG "Use bigger internal units for big integer calculations" TRUE) # Check for IPO/LTO check_ipo_supported(RESULT supported) @@ -34,6 +35,7 @@ set(BH_SOURCE src/thread.c src/io.c src/deflate.c + src/bigint.c ) set(BH_HEADER @@ -46,6 +48,7 @@ set(BH_HEADER include/bh/thread.h include/bh/io.h include/bh/deflate.h + include/bh/bigint.h ) set(BH_INCLUDE_DIRS diff --git a/include/bh/bigint.h b/include/bh/bigint.h new file mode 100644 index 0000000..116256f --- /dev/null +++ b/include/bh/bigint.h @@ -0,0 +1,143 @@ +#ifndef BH_BIGINT_H +#define BH_BIGINT_H + +#include "bh.h" + +typedef struct bh_bigint_s bh_bigint_t; + +bh_bigint_t *bh_bigint_new(void); +void bh_bigint_free(bh_bigint_t *bigint); + +int bh_bigint_block(void); + +int bh_bigint_clear(bh_bigint_t *bigint); + +int bh_bigint_set(bh_bigint_t *to, + bh_bigint_t *from); + +int bh_bigint_set_int(bh_bigint_t *to, + int from); + +int bh_bigint_set_uint(bh_bigint_t *to, + unsigned int from); + +int bh_bigint_get_int(bh_bigint_t *bigint); + +unsigned int bh_bigint_get_uint(bh_bigint_t *bigint); + +int bh_bigint_set_int8(bh_bigint_t *to, + bh_int8_t from); + +int bh_bigint_set_uint8(bh_bigint_t *to, + bh_uint8_t from); + +bh_int8_t bh_bigint_get_int8(bh_bigint_t *bigint); + +bh_uint8_t bh_bigint_get_uint8(bh_bigint_t *bigint); + +int bh_bigint_set_int16(bh_bigint_t *to, + bh_int16_t from); + +int bh_bigint_set_uint16(bh_bigint_t *to, + bh_uint16_t from); + +bh_int16_t bh_bigint_get_int16(bh_bigint_t *bigint); + +bh_uint16_t bh_bigint_get_uint16(bh_bigint_t *bigint); + +int bh_bigint_set_int32(bh_bigint_t *to, + bh_int32_t from); + +int bh_bigint_set_uint32(bh_bigint_t *to, + bh_uint32_t from); + +bh_int32_t bh_bigint_get_int32(bh_bigint_t *bigint); + +bh_uint32_t bh_bigint_get_uint32(bh_bigint_t *bigint); + +int bh_bigint_set_int64(bh_bigint_t *to, + bh_int64_t from); + +int bh_bigint_set_uint64(bh_bigint_t *to, + bh_uint64_t from); + +bh_int64_t bh_bigint_get_int64(bh_bigint_t *bigint); + +bh_uint64_t bh_bigint_get_uint64(bh_bigint_t *bigint); + +size_t bh_bigint_capacity(bh_bigint_t *bigint); + +size_t bh_bigint_length(bh_bigint_t *bigint); + +int bh_bigint_reserve(bh_bigint_t *bigint, + size_t size); + +int bh_bigint_add(bh_bigint_t *to, + bh_bigint_t *left, + bh_bigint_t *right); + +int bh_bigint_sub(bh_bigint_t *to, + bh_bigint_t *left, + bh_bigint_t *right); + +int bh_bigint_mul(bh_bigint_t *to, + bh_bigint_t *left, + bh_bigint_t *right); + +int bh_bigint_pow(bh_bigint_t *to, + bh_bigint_t *from, + bh_uint32_t power); + +int bh_bigint_powm(bh_bigint_t *to, + bh_bigint_t *left, + bh_bigint_t *right, + bh_bigint_t *mod); + +int bh_bigint_divmod(bh_bigint_t *quotient, + bh_bigint_t *remainder, + bh_bigint_t *left, + bh_bigint_t *right); + +int bh_bigint_div(bh_bigint_t *to, + bh_bigint_t *left, + bh_bigint_t *right); + +int bh_bigint_mod(bh_bigint_t *to, + bh_bigint_t *left, + bh_bigint_t *right); + +int bh_bigint_lsh(bh_bigint_t *to, + bh_bigint_t *from, + bh_uint32_t shift); + +int bh_bigint_rsh(bh_bigint_t *to, + bh_bigint_t *from, + bh_uint32_t shift); + +int bh_bigint_or(bh_bigint_t *to, + bh_bigint_t *left, + bh_bigint_t *right); + +int bh_bigint_and(bh_bigint_t *to, + bh_bigint_t *left, + bh_bigint_t *right); + +int bh_bigint_xor(bh_bigint_t *to, + bh_bigint_t *left, + bh_bigint_t *right); + +int bh_bigint_negate(bh_bigint_t *to, + bh_bigint_t *from); + +int bh_bigint_equal(bh_bigint_t *left, + bh_bigint_t *right); + +int bh_bigint_equal_mod(bh_bigint_t *left, + bh_bigint_t *right); + +int bh_bigint_is_negative(bh_bigint_t *bigint); +int bh_bigint_is_zero(bh_bigint_t *bigint); +int bh_bigint_is_error(bh_bigint_t *bigint); +size_t bh_bigint_log2(bh_bigint_t *bigint); + +#endif /* BH_BIGINT_H */ diff --git a/include/bh/internal/bigint.h b/include/bh/internal/bigint.h new file mode 100644 index 0000000..96377cf --- /dev/null +++ b/include/bh/internal/bigint.h @@ -0,0 +1,31 @@ +#ifndef BH_INTERNAL_BIGINT_H +#define BH_INTERNAL_BIGINT_H + +#include "bh.h" +#include + +#if defined(BH_BIGINT_LONG) +#define BH_BIGINT_BITS 31 +#define BH_BIGINT_MASK 0x7FFFFFFF +#define BH_BIGINT_TYPE bh_uint32_t +#define BH_BIGINT_TMP bh_uint64_t +#else +#define BH_BIGINT_BITS 15 +#define BH_BIGINT_MASK 0x7FFF +#define BH_BIGINT_TYPE bh_uint16_t +#define BH_BIGINT_TMP bh_uint32_t +#endif + +struct bh_bigint_s +{ + BH_BIGINT_TYPE *data; + size_t size; + size_t capacity; + int type; + int error; +}; + +void bh_bigint_init(bh_bigint_t *bigint); +void bh_bigint_destroy(bh_bigint_t *bigint); + +#endif /* BH_INTERNAL_BIGINT_H */ diff --git a/include/bh/internal/config.in b/include/bh/internal/config.in index 5be792c..be668ac 100644 --- a/include/bh/internal/config.in +++ b/include/bh/internal/config.in @@ -1,6 +1,7 @@ #ifndef BH_INTERNAL_CONFIG_H #define BH_INTERNAL_CONFIG_H +#cmakedefine BH_BIGINT_LONG #cmakedefine BH_THREADS_WINXP #endif /* BH_INTERNAL_CONFIG_H */ \ No newline at end of file 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 +#include +#include +#include + +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 diff --git a/tests/src/bigint.c b/tests/src/bigint.c new file mode 100644 index 0000000..b3ae620 --- /dev/null +++ b/tests/src/bigint.c @@ -0,0 +1,429 @@ +#include +#include +#include + +static int round_trip(void) +{ + bh_bigint_t *data[10]; + size_t i; + + for (i = 0; i < 10; i++) + { + data[i] = bh_bigint_new(); + bh_unit_assert(data[i] != NULL); + } + + bh_unit_assert(bh_bigint_set_int(data[0], -12345) == BH_OK); + bh_unit_assert(bh_bigint_get_int(data[0]) == -12345); + + bh_unit_assert(bh_bigint_set_int8(data[1], -120) == BH_OK); + bh_unit_assert(bh_bigint_get_int8(data[1]) == -120); + + bh_unit_assert(bh_bigint_set_int16(data[2], -12345) == BH_OK); + bh_unit_assert(bh_bigint_get_int16(data[2]) == -12345); + + bh_unit_assert(bh_bigint_set_int32(data[3], -12345678l) == BH_OK); + bh_unit_assert(bh_bigint_get_int32(data[3]) == -12345678l); + + bh_unit_assert(bh_bigint_set_int64(data[4], -123456789012345ll) == BH_OK); + bh_unit_assert(bh_bigint_get_int64(data[4]) == -123456789012345ll); + + bh_unit_assert(bh_bigint_set_uint(data[5], 12345) == BH_OK); + bh_unit_assert(bh_bigint_get_uint(data[5]) == 12345); + + bh_unit_assert(bh_bigint_set_uint8(data[6], 230) == BH_OK); + bh_unit_assert(bh_bigint_get_uint8(data[6]) == 230); + + bh_unit_assert(bh_bigint_set_uint16(data[7], 40000) == BH_OK); + bh_unit_assert(bh_bigint_get_uint16(data[7]) == 40000); + + bh_unit_assert(bh_bigint_set_uint32(data[8], 12345678ul) == BH_OK); + bh_unit_assert(bh_bigint_get_uint32(data[8]) == 12345678ul); + + bh_unit_assert(bh_bigint_set_uint64(data[9], 123456789012345ull) == BH_OK); + bh_unit_assert(bh_bigint_get_uint64(data[9]) == 123456789012345ull); + + for (i = 0; i < 10; i++) + bh_bigint_free(data[i]); + + return 0; +} + +static int addition(void) +{ + bh_bigint_t *a, *b, *c; + bh_uint64_t ta, tb; + + a = bh_bigint_new(); + b = bh_bigint_new(); + c = bh_bigint_new(); + + bh_unit_assert(a != NULL); + bh_unit_assert(b != NULL); + bh_unit_assert(c != NULL); + + ta = 0xA3B1DBC158176B96ull; + tb = 0x2748D1622F3E90A2ull; + + bh_unit_assert(bh_bigint_set_uint64(a, ta) == BH_OK); + bh_unit_assert(bh_bigint_set_uint64(b, tb) == BH_OK); + bh_unit_assert(bh_bigint_add(c, a, b) == BH_OK); + bh_unit_assert(bh_bigint_get_uint64(c) == (ta + tb)); + + bh_bigint_free(a); + bh_bigint_free(b); + bh_bigint_free(c); + + return 0; +} + +static int subtraction(void) +{ + bh_bigint_t *a, *b, *c; + bh_uint64_t ta, tb; + + a = bh_bigint_new(); + b = bh_bigint_new(); + c = bh_bigint_new(); + + bh_unit_assert(a != NULL); + bh_unit_assert(b != NULL); + bh_unit_assert(c != NULL); + + ta = 0xA3B1DBC158176B96ull; + tb = 0x2748D1622F3E90A2ull; + + bh_unit_assert(bh_bigint_set_uint64(a, ta) == BH_OK); + bh_unit_assert(bh_bigint_set_uint64(b, tb) == BH_OK); + bh_unit_assert(bh_bigint_sub(c, a, b) == BH_OK); + bh_unit_assert(bh_bigint_get_uint64(c) == (ta - tb)); + + bh_bigint_free(a); + bh_bigint_free(b); + bh_bigint_free(c); + + return 0; +} + +static int addition_sign(void) +{ + bh_bigint_t *a, *b, *c; + + a = bh_bigint_new(); + b = bh_bigint_new(); + c = bh_bigint_new(); + + bh_unit_assert(a != NULL); + bh_unit_assert(b != NULL); + bh_unit_assert(c != NULL); + + bh_unit_assert(bh_bigint_set_int(a, 5) == BH_OK); + bh_unit_assert(bh_bigint_set_int(b, 3) == BH_OK); + bh_unit_assert(bh_bigint_add(c, a, b) == BH_OK); + bh_unit_assert(bh_bigint_get_int(c) == 8); + bh_unit_assert(bh_bigint_add(c, b, a) == BH_OK); + bh_unit_assert(bh_bigint_get_int(c) == 8); + + bh_unit_assert(bh_bigint_set_int(a, -5) == BH_OK); + bh_unit_assert(bh_bigint_set_int(b, 3) == BH_OK); + bh_unit_assert(bh_bigint_add(c, a, b) == BH_OK); + bh_unit_assert(bh_bigint_get_int(c) == -2); + bh_unit_assert(bh_bigint_add(c, b, a) == BH_OK); + bh_unit_assert(bh_bigint_get_int(c) == -2); + + bh_unit_assert(bh_bigint_set_int(a, 5) == BH_OK); + bh_unit_assert(bh_bigint_set_int(b, -3) == BH_OK); + bh_unit_assert(bh_bigint_add(c, a, b) == BH_OK); + bh_unit_assert(bh_bigint_get_int(c) == 2); + bh_unit_assert(bh_bigint_add(c, b, a) == BH_OK); + bh_unit_assert(bh_bigint_get_int(c) == 2); + + bh_unit_assert(bh_bigint_set_int(a, -5) == BH_OK); + bh_unit_assert(bh_bigint_set_int(b, -3) == BH_OK); + bh_unit_assert(bh_bigint_add(c, a, b) == BH_OK); + bh_unit_assert(bh_bigint_get_int(c) == -8); + bh_unit_assert(bh_bigint_add(c, b, a) == BH_OK); + bh_unit_assert(bh_bigint_get_int(c) == -8); + + bh_bigint_free(a); + bh_bigint_free(b); + bh_bigint_free(c); + + return 0; +} + +static int subtraction_sign(void) +{ + bh_bigint_t *a, *b, *c; + + a = bh_bigint_new(); + b = bh_bigint_new(); + c = bh_bigint_new(); + + bh_unit_assert(a != NULL); + bh_unit_assert(b != NULL); + bh_unit_assert(c != NULL); + + bh_unit_assert(bh_bigint_set_int(a, 5) == BH_OK); + bh_unit_assert(bh_bigint_set_int(b, 3) == BH_OK); + bh_unit_assert(bh_bigint_sub(c, a, b) == BH_OK); + bh_unit_assert(bh_bigint_get_int(c) == 2); + bh_unit_assert(bh_bigint_sub(c, b, a) == BH_OK); + bh_unit_assert(bh_bigint_get_int(c) == -2); + + bh_unit_assert(bh_bigint_set_int(a, -5) == BH_OK); + bh_unit_assert(bh_bigint_set_int(b, 3) == BH_OK); + bh_unit_assert(bh_bigint_sub(c, a, b) == BH_OK); + bh_unit_assert(bh_bigint_get_int(c) == -8); + bh_unit_assert(bh_bigint_sub(c, b, a) == BH_OK); + bh_unit_assert(bh_bigint_get_int(c) == 8); + + bh_unit_assert(bh_bigint_set_int(a, 5) == BH_OK); + bh_unit_assert(bh_bigint_set_int(b, -3) == BH_OK); + bh_unit_assert(bh_bigint_sub(c, a, b) == BH_OK); + bh_unit_assert(bh_bigint_get_int(c) == 8); + bh_unit_assert(bh_bigint_sub(c, b, a) == BH_OK); + bh_unit_assert(bh_bigint_get_int(c) == -8); + + bh_unit_assert(bh_bigint_set_int(a, -5) == BH_OK); + bh_unit_assert(bh_bigint_set_int(b, -3) == BH_OK); + bh_unit_assert(bh_bigint_sub(c, a, b) == BH_OK); + bh_unit_assert(bh_bigint_get_int(c) == -2); + bh_unit_assert(bh_bigint_sub(c, b, a) == BH_OK); + bh_unit_assert(bh_bigint_get_int(c) == 2); + + bh_bigint_free(a); + bh_bigint_free(b); + bh_bigint_free(c); + + return 0; +} + +static int multiplication(void) +{ + int i; + bh_bigint_t *a, *b, *c, *d; + + a = bh_bigint_new(); + b = bh_bigint_new(); + c = bh_bigint_new(); + d = bh_bigint_new(); + + bh_unit_assert(a != NULL); + bh_unit_assert(b != NULL); + bh_unit_assert(c != NULL); + bh_unit_assert(d != NULL); + + bh_unit_assert(bh_bigint_set_int(a, 1234567) == BH_OK); + bh_unit_assert(bh_bigint_set_int(b, 1234567) == BH_OK); + + bh_unit_assert(bh_bigint_mul(c, a, b) == BH_OK); + bh_unit_assert(bh_bigint_set(d, a) == BH_OK); + bh_unit_assert(bh_bigint_reserve(d, d->size + a->size + 1) == BH_OK); + + for (i = 1; i < 1234567; i++) + bh_unit_assert(bh_bigint_add(d, d, a) == BH_OK); + + bh_unit_assert(bh_bigint_equal(c, d) == 0); + bh_unit_assert(memcmp(c->data, d->data, c->size * sizeof(*c->data)) == 0); + + bh_unit_assert(bh_bigint_set_int(c, 6) == BH_OK); + bh_unit_assert(bh_bigint_set_int(b, 2) == BH_OK); + bh_unit_assert(bh_bigint_set_int(d, 6) == BH_OK); + + for (i = 0; i < 250; i++) + { + bh_unit_assert(bh_bigint_mul(c, c, b) == BH_OK); + bh_unit_assert(bh_bigint_add(d, d, d) == BH_OK); + } + + bh_unit_assert(bh_bigint_equal(c, d) == 0); + bh_unit_assert(memcmp(c->data, d->data, c->size * sizeof(*c->data)) == 0); + + bh_bigint_free(a); + bh_bigint_free(b); + bh_bigint_free(c); + bh_bigint_free(d); + + return 0; +} + +static int logic(void) +{ + bh_bigint_t *a, *b, *c; + bh_uint64_t ta, tb; + + ta = 0xA3B1DBC158176B96ull; + tb = 0x2748D1622F3E90A2ull; + + a = bh_bigint_new(); + b = bh_bigint_new(); + c = bh_bigint_new(); + + bh_unit_assert(a != NULL); + bh_unit_assert(b != NULL); + bh_unit_assert(c != NULL); + + bh_unit_assert(bh_bigint_set_uint64(a, ta) == BH_OK); + bh_unit_assert(bh_bigint_set_uint64(b, tb) == BH_OK); + + bh_unit_assert(bh_bigint_or(c, a, b) == BH_OK); + bh_unit_assert(bh_bigint_get_uint64(c) == (ta | tb)); + + bh_unit_assert(bh_bigint_and(c, a, b) == BH_OK); + bh_unit_assert(bh_bigint_get_uint64(c) == (ta & tb)); + + bh_unit_assert(bh_bigint_xor(c, a, b) == BH_OK); + bh_unit_assert(bh_bigint_get_uint64(c) == (ta ^ tb)); + + bh_bigint_free(a); + bh_bigint_free(b); + bh_bigint_free(c); + + return 0; +} + +static int shifts(void) +{ + bh_bigint_t *a, *b; + bh_uint64_t ta, tb; + + ta = 0x73B1DBC158176B96ull; + tb = 0x73B1DBC158176B90ull; + + a = bh_bigint_new(); + b = bh_bigint_new(); + + bh_unit_assert(a != NULL); + bh_unit_assert(b != NULL); + + bh_unit_assert(bh_bigint_set_uint64(a, 0xFFull) == BH_OK); + bh_unit_assert(bh_bigint_lsh(b, a, 4) == BH_OK); + bh_unit_assert(bh_bigint_get_uint64(b) == (0xFFull << 4)); + + bh_unit_assert(bh_bigint_set_uint64(a, 0xFFull) == BH_OK); + bh_unit_assert(bh_bigint_lsh(b, a, 15) == BH_OK); + bh_unit_assert(bh_bigint_get_uint64(b) == (0xFFull << 15)); + + bh_unit_assert(bh_bigint_set_uint64(a, 0xFFull) == BH_OK); + bh_unit_assert(bh_bigint_lsh(b, a, 31) == BH_OK); + bh_unit_assert(bh_bigint_get_uint64(b) == (0xFFull << 31)); + + bh_unit_assert(bh_bigint_set_uint64(a, 0xFFull) == BH_OK); + bh_unit_assert(bh_bigint_lsh(b, a, 35) == BH_OK); + bh_unit_assert(bh_bigint_get_uint64(b) == (0xFFull << 35)); + + bh_unit_assert(bh_bigint_set_uint64(a, ta) == BH_OK); + bh_unit_assert(bh_bigint_lsh(b, a, 1) == BH_OK); + bh_unit_assert(bh_bigint_get_uint64(b) == (ta << 1)); + + bh_unit_assert(bh_bigint_set_uint64(a, ta) == BH_OK); + bh_unit_assert(bh_bigint_rsh(b, a, 31) == BH_OK); + bh_unit_assert(bh_bigint_get_uint64(b) == (ta >> 31)) + + bh_unit_assert(bh_bigint_set_uint64(a, ta) == BH_OK); + bh_unit_assert(bh_bigint_rsh(b, a, 15) == BH_OK); + bh_unit_assert(bh_bigint_get_uint64(b) == (ta >> 15)) + + bh_unit_assert(bh_bigint_set_uint64(a, ta) == BH_OK); + bh_unit_assert(bh_bigint_rsh(b, a, 4) == BH_OK); + bh_unit_assert(bh_bigint_get_uint64(b) == (ta >> 4)); + + bh_unit_assert(bh_bigint_lsh(b, b, 4) == BH_OK); + bh_unit_assert(bh_bigint_get_uint64(b) == tb); + + bh_unit_assert(bh_bigint_rsh(b, a, 60) == BH_OK); + bh_unit_assert(bh_bigint_get_uint64(b) == 0x7); + + bh_bigint_free(a); + bh_bigint_free(b); + + return 0; +} + +static int division(void) +{ + bh_bigint_t *a, *b, *c, *d; + + a = bh_bigint_new(); + b = bh_bigint_new(); + c = bh_bigint_new(); + d = bh_bigint_new(); + + bh_unit_assert(a != NULL); + bh_unit_assert(b != NULL); + bh_unit_assert(c != NULL); + bh_unit_assert(d != NULL); + + bh_unit_assert(bh_bigint_set_uint64(a, 0x41F915031348A134ull) == BH_OK); + bh_unit_assert(bh_bigint_set_uint64(b, 0x434115F6ull) == BH_OK); + bh_unit_assert(bh_bigint_mul(a, a, b) == BH_OK); + bh_unit_assert(bh_bigint_set_uint64(b, 0x153F14ABull) == BH_OK); + + bh_unit_assert(bh_bigint_divmod(c, d, a, b) == BH_OK); + + bh_unit_assert(bh_bigint_get_uint64(c) == 0xD0D561E41F7EA081ull); + bh_unit_assert(bh_bigint_get_uint64(d) == 0x0459E1CDull); + + bh_bigint_free(a); + bh_bigint_free(b); + bh_bigint_free(c); + bh_bigint_free(d); + + return 0; +} + +static int power(void) +{ + bh_bigint_t *a, *b, *c, *d, *e; + + a = bh_bigint_new(); + b = bh_bigint_new(); + c = bh_bigint_new(); + d = bh_bigint_new(); + e = bh_bigint_new(); + + bh_unit_assert(a != NULL); + bh_unit_assert(b != NULL); + bh_unit_assert(c != NULL); + bh_unit_assert(d != NULL); + bh_unit_assert(e != NULL); + + bh_unit_assert(bh_bigint_set_int(a, 137) == BH_OK); + bh_unit_assert(bh_bigint_set_int(b, 2048) == BH_OK); + bh_unit_assert(bh_bigint_set_int(c, 100) == BH_OK); + + bh_unit_assert(bh_bigint_pow(d, a, 2048) == BH_OK); + bh_unit_assert(bh_bigint_mod(d, d, c) == BH_OK); + bh_unit_assert(bh_bigint_powm(e, a, b, c) == BH_OK); + bh_unit_assert(bh_bigint_equal(d, e) == 0); + bh_unit_assert(bh_bigint_get_int(d) == 21); + + bh_bigint_free(a); + bh_bigint_free(b); + bh_bigint_free(c); + bh_bigint_free(d); + bh_bigint_free(e); + + return 0; +} + +int main(int argc, char **argv) +{ + (void)argc; + (void)argv; + + /* Add unit tests */ + bh_unit_add("round_trip", round_trip); + bh_unit_add("addition", addition); + bh_unit_add("subtraction", subtraction); + bh_unit_add("addition_sign", addition_sign); + bh_unit_add("subtraction_sign", subtraction_sign); + bh_unit_add("multiplication", multiplication); + bh_unit_add("logic", logic); + bh_unit_add("shifts", shifts); + bh_unit_add("division", division); + bh_unit_add("power", power); + + return bh_unit_run(); +} \ No newline at end of file -- cgit v1.2.3