From 2a673a8cb44fe34e1a0feed7fb40d7fc9e0203cd Mon Sep 17 00:00:00 2001 From: Mitya Selivanov Date: Fri, 9 Dec 2022 20:08:07 +0100 Subject: [bitint] Division --- source/kit/bigint.h | 284 ++++++++++++++++++++++++++++++------ source/test/unittests/bigint.test.c | 2 - 2 files changed, 243 insertions(+), 43 deletions(-) (limited to 'source') diff --git a/source/kit/bigint.h b/source/kit/bigint.h index 2ad7514..26268a6 100644 --- a/source/kit/bigint.h +++ b/source/kit/bigint.h @@ -52,36 +52,6 @@ typedef uint_fast8_t kit_bit_t; # pragma GCC optimize("O3") #endif -static uint8_t kit_hex_digit(char const hex) { - if (hex >= '0' && hex <= '9') - return hex - '0'; - if (hex >= 'a' && hex <= 'f') - return hex - 'a'; - if (hex >= 'A' && hex <= 'F') - return hex - 'A'; - return 0; -} - -static uint8_t kit_base58_digit(char const c) { - static const uint8_t BASE58_DIGITS[] = { - ['1'] = 0, ['2'] = 1, ['3'] = 2, ['4'] = 3, ['5'] = 4, - ['6'] = 5, ['7'] = 6, ['8'] = 7, ['9'] = 8, ['A'] = 9, - ['B'] = 10, ['C'] = 11, ['D'] = 12, ['E'] = 13, ['F'] = 14, - ['G'] = 15, ['H'] = 16, ['J'] = 17, ['K'] = 18, ['L'] = 19, - ['M'] = 20, ['N'] = 21, ['P'] = 22, ['Q'] = 23, ['R'] = 24, - ['S'] = 25, ['T'] = 26, ['U'] = 27, ['V'] = 28, ['W'] = 29, - ['X'] = 30, ['Y'] = 31, ['Z'] = 32, ['a'] = 33, ['b'] = 34, - ['c'] = 35, ['d'] = 36, ['e'] = 37, ['f'] = 38, ['g'] = 39, - ['h'] = 40, ['i'] = 41, ['j'] = 42, ['k'] = 43, ['m'] = 44, - ['n'] = 45, ['o'] = 46, ['p'] = 47, ['q'] = 48, ['r'] = 49, - ['s'] = 50, ['t'] = 51, ['u'] = 52, ['v'] = 53, ['w'] = 54, - ['x'] = 55, ['y'] = 56, ['z'] = 57 - }; - return c >= '\0' && c < (sizeof BASE58_DIGITS) - ? BASE58_DIGITS[(size_t) (unsigned char) c] - : 0; -} - static kit_bigint_t kit_bi_uword(kit_uword_t const x) { kit_bigint_t z; memset(z.v8, 0, KIT_BIGINT_SIZE); @@ -96,22 +66,109 @@ static kit_bigint_t kit_bi_uint64(uint64_t const x) { return z; } -static kit_bigint_t kit_bi_hex(kit_str_t const hex) { +static int kit_bi_equal(kit_bigint_t const x, kit_bigint_t const y) { + return kit_ar_equal_bytes(1, KIT_BIGINT_SIZE, x.v8, 1, + KIT_BIGINT_SIZE, y.v8); +} + +static int kit_bi_compare(kit_bigint_t const x, + kit_bigint_t const y) { + for (ptrdiff_t i = KIT_BIGINT_SIZE / KIT_UWORD_SIZE - 1; i >= 0; + i--) + if (x.v[i] < y.v[i]) + return -1; + else if (x.v[i] > y.v[i]) + return 1; + return 0; +} + +static ptrdiff_t kit_bi_significant_bit_count(kit_bigint_t const x) { + ptrdiff_t bytes = KIT_BIGINT_SIZE - 1; + + while (bytes > 0 && x.v8[bytes] == 0) bytes--; + + uint8_t const byte = x.v8[bytes]; + + if (byte == 0) + return 0; + + ptrdiff_t const bits = (byte & 0x80) != 0 ? 8 + : (byte & 0x40) != 0 ? 7 + : (byte & 0x20) != 0 ? 6 + : (byte & 0x10) != 0 ? 5 + : (byte & 0x08) != 0 ? 4 + : (byte & 0x04) != 0 ? 3 + : (byte & 0x02) != 0 ? 2 + : (byte & 0x01) != 0 ? 1 + : 0; + + return bytes * 8 + bits; +} + +static kit_bigint_t kit_bi_and(kit_bigint_t const x, + kit_bigint_t const y) { + kit_bigint_t z; + + for (ptrdiff_t i = 0; i < KIT_BIGINT_SIZE / KIT_UWORD_SIZE; i++) + z.v[i] = x.v[i] & y.v[i]; + + return z; +} + +static kit_bigint_t kit_bi_or(kit_bigint_t const x, + kit_bigint_t const y) { + kit_bigint_t z; + + for (ptrdiff_t i = 0; i < KIT_BIGINT_SIZE / KIT_UWORD_SIZE; i++) + z.v[i] = x.v[i] | y.v[i]; + + return z; +} + +static kit_bigint_t kit_bi_xor(kit_bigint_t const x, + kit_bigint_t const y) { + kit_bigint_t z; + + for (ptrdiff_t i = 0; i < KIT_BIGINT_SIZE / KIT_UWORD_SIZE; i++) + z.v[i] = x.v[i] ^ y.v[i]; + + return z; +} + +static kit_bigint_t kit_bi_shl_uword(kit_bigint_t const x, + kit_uword_t y) { kit_bigint_t z; memset(z.v8, 0, KIT_BIGINT_SIZE); - for (ptrdiff_t i = 0; i < hex.size && i / 2 < KIT_BIGINT_SIZE; + ptrdiff_t const words = (ptrdiff_t) (y / (8 * KIT_UWORD_SIZE)); + ptrdiff_t const bits = (ptrdiff_t) (y % (8 * KIT_UWORD_SIZE)); + + for (ptrdiff_t i = words; i < KIT_BIGINT_SIZE / KIT_UWORD_SIZE; i++) { - uint8_t const digit = kit_hex_digit(hex.values[hex.size - i - 1]); - z.v8[i / 2] |= ((i % 2) == 0) ? digit : (digit << 4); + z.v[i] |= x.v[i - words] << bits; + if (bits != 0 && i + 1 < KIT_BIGINT_SIZE / KIT_UWORD_SIZE) + z.v[i + 1] = x.v[i - words] >> (8 * KIT_UWORD_SIZE - bits); } return z; } -static int kit_bi_equal(kit_bigint_t const x, kit_bigint_t const y) { - return kit_ar_equal_bytes(1, KIT_BIGINT_SIZE, x.v8, 1, - KIT_BIGINT_SIZE, y.v8); +static kit_bigint_t kit_bi_shr_uword(kit_bigint_t const x, + kit_uword_t y) { + kit_bigint_t z; + memset(z.v8, 0, KIT_BIGINT_SIZE); + + ptrdiff_t const words = (ptrdiff_t) (y / (8 * KIT_UWORD_SIZE)); + ptrdiff_t const bits = (ptrdiff_t) (y % (8 * KIT_UWORD_SIZE)); + + for (ptrdiff_t i = KIT_BIGINT_SIZE / KIT_UWORD_SIZE - words - 1; + i >= 0; i--) { + z.v[i] |= x.v[i + words] >> bits; + if (bits != 0 && i > 0) + z.v[i - 1] = x.v[i + words] << (8 * KIT_UWORD_SIZE - bits); + } + + return z; } static kit_bit_t kit_bi_carry(kit_uword_t const x, @@ -210,6 +267,152 @@ static kit_bigint_t kit_bi_mul(kit_bigint_t const x, return z; } +typedef struct { + kit_bit_t undefined; + kit_bigint_t quotient; + kit_bigint_t remainder; +} kit_bi_division_t; + +static kit_bi_division_t kit_bi_div(kit_bigint_t const x, + kit_bigint_t y) { + kit_bi_division_t result; + memset(&result, 0, sizeof result); + + ptrdiff_t const y_bits = kit_bi_significant_bit_count(y); + + if (y_bits == 0) { + result.undefined = 1; + return result; + } + + ptrdiff_t const x_bits = kit_bi_significant_bit_count(x); + ptrdiff_t shift = x_bits - y_bits; + + result.remainder = x; + result.quotient = kit_bi_uword(0); + + y = kit_bi_shl_uword(y, (kit_uword_t) shift); + + while (shift >= 0) { + if (kit_bi_compare(result.remainder, y) > 0) { + result.remainder = kit_bi_sub(result.remainder, y); + result.quotient.v8[shift / 8] |= (1u << (shift % 8)); + } + + y = kit_bi_shr_uword(y, 1); + shift--; + } + + return result; +} + +static uint8_t kit_bin_digit(char const hex) { + return hex == '1' ? 1 : 0; +} + +static kit_bigint_t kit_bi_bin(kit_str_t const bin) { + kit_bigint_t z; + memset(z.v8, 0, KIT_BIGINT_SIZE); + + for (ptrdiff_t i = 0; i < bin.size && i / 8 < KIT_BIGINT_SIZE; + i++) { + uint8_t const digit = kit_bin_digit(bin.values[bin.size - i - 1]); + z.v8[i / 8] |= digit << (i % 8); + } + + return z; +} + +static uint8_t kit_dec_digit(char const c) { + return c >= '0' && c <= '9' ? (uint8_t) (c - '0') : 0; +} + +static kit_bigint_t kit_bi_dec(kit_str_t const dec) { + kit_bigint_t z = kit_bi_uword(0); + kit_bigint_t factor = kit_bi_uword(1); + + for (ptrdiff_t i = 0; i < dec.size; i++) { + uint32_t const digit = kit_dec_digit( + dec.values[dec.size - i - 1]); + z = kit_bi_add(z, kit_bi_mul_uint32(factor, digit)); + factor = kit_bi_mul_uint32(factor, 10); + } + + return z; +} + +static uint8_t kit_hex_digit(char const hex) { + if (hex >= '0' && hex <= '9') + return hex - '0'; + if (hex >= 'a' && hex <= 'f') + return hex - 'a'; + if (hex >= 'A' && hex <= 'F') + return hex - 'A'; + return 0; +} + +static kit_bigint_t kit_bi_hex(kit_str_t const hex) { + kit_bigint_t z; + memset(z.v8, 0, KIT_BIGINT_SIZE); + + for (ptrdiff_t i = 0; i < hex.size && i / 2 < KIT_BIGINT_SIZE; + i++) { + uint8_t const digit = kit_hex_digit(hex.values[hex.size - i - 1]); + z.v8[i / 2] |= ((i % 2) == 0) ? digit : (digit << 4); + } + + return z; +} + +static const uint8_t KIT_BASE32_DIGITS[] = { + ['1'] = 0, ['2'] = 1, ['3'] = 2, ['4'] = 3, ['5'] = 4, + ['6'] = 5, ['7'] = 6, ['8'] = 7, ['9'] = 8, ['a'] = 9, + ['b'] = 10, ['c'] = 11, ['d'] = 12, ['e'] = 13, ['f'] = 14, + ['g'] = 15, ['h'] = 16, ['j'] = 17, ['k'] = 18, ['m'] = 19, + ['n'] = 20, ['p'] = 21, ['q'] = 22, ['r'] = 23, ['s'] = 24, + ['t'] = 25, ['u'] = 26, ['v'] = 27, ['w'] = 28, ['x'] = 29, + ['y'] = 30, ['z'] = 31 +}; + +static uint8_t kit_base32_digit(char const c) { + return c >= '\0' && c < (sizeof KIT_BASE32_DIGITS) + ? KIT_BASE32_DIGITS[(size_t) (unsigned char) c] + : 0; +} + +static kit_bigint_t kit_bi_base32(kit_str_t const base32) { + kit_bigint_t z; + memset(z.v8, 0, KIT_BIGINT_SIZE); + + for (ptrdiff_t i = 0; i < base32.size; i++) { + z = kit_bi_shl_uword(z, 5 * i); + z.v8[i] |= kit_base32_digit(base32.values[i]); + } + + return z; +} + +static const uint8_t KIT_BASE58_DIGITS[] = { + ['1'] = 0, ['2'] = 1, ['3'] = 2, ['4'] = 3, ['5'] = 4, + ['6'] = 5, ['7'] = 6, ['8'] = 7, ['9'] = 8, ['A'] = 9, + ['B'] = 10, ['C'] = 11, ['D'] = 12, ['E'] = 13, ['F'] = 14, + ['G'] = 15, ['H'] = 16, ['J'] = 17, ['K'] = 18, ['L'] = 19, + ['M'] = 20, ['N'] = 21, ['P'] = 22, ['Q'] = 23, ['R'] = 24, + ['S'] = 25, ['T'] = 26, ['U'] = 27, ['V'] = 28, ['W'] = 29, + ['X'] = 30, ['Y'] = 31, ['Z'] = 32, ['a'] = 33, ['b'] = 34, + ['c'] = 35, ['d'] = 36, ['e'] = 37, ['f'] = 38, ['g'] = 39, + ['h'] = 40, ['i'] = 41, ['j'] = 42, ['k'] = 43, ['m'] = 44, + ['n'] = 45, ['o'] = 46, ['p'] = 47, ['q'] = 48, ['r'] = 49, + ['s'] = 50, ['t'] = 51, ['u'] = 52, ['v'] = 53, ['w'] = 54, + ['x'] = 55, ['y'] = 56, ['z'] = 57 +}; + +static uint8_t kit_base58_digit(char const c) { + return c >= '\0' && c < (sizeof KIT_BASE58_DIGITS) + ? KIT_BASE58_DIGITS[(size_t) (unsigned char) c] + : 0; +} + static kit_bigint_t kit_bi_base58(kit_str_t const base58) { kit_bigint_t z = kit_bi_uword(0); kit_bigint_t factor = kit_bi_uword(1); @@ -231,18 +434,17 @@ static kit_bigint_t kit_bi_base58(kit_str_t const base58) { #ifndef KIT_DISABLE_SHORT_NAMES # define bigint_t kit_bigint_t -# define hex_digit kit_hex_digit -# define base58_digit kit_base58_digit # define bi_uword kit_bi_uword # define bi_uint64 kit_bi_uint64 -# define bi_hex kit_bi_hex -# define bi_base58 kit_bi_base58 # define bi_equal kit_bi_equal # define bi_carry kit_bi_carry # define bi_add kit_bi_add # define bi_neg kit_bi_neg # define bi_sub kit_bi_sub # define bi_mul kit_bi_mul +# define hex_digit kit_hex_digit +# define bi_hex kit_bi_hex +# define bi_base58 kit_bi_base58 #endif #ifdef __cplusplus diff --git a/source/test/unittests/bigint.test.c b/source/test/unittests/bigint.test.c index 7df2fcc..87bbc60 100644 --- a/source/test/unittests/bigint.test.c +++ b/source/test/unittests/bigint.test.c @@ -3,8 +3,6 @@ #define KIT_TEST_FILE bigint #include "../../kit_test/test.h" -#include - TEST("bigint hex add") { SZ(foo, "4242424242424242424242424242424242424242"); SZ(bar, "1111111111111111111111111111111111111111"); -- cgit v1.2.3