summaryrefslogtreecommitdiff
path: root/source
diff options
context:
space:
mode:
authorMitya Selivanov <automainint@guattari.tech>2022-12-23 10:58:15 +0100
committerMitya Selivanov <automainint@guattari.tech>2022-12-23 10:58:15 +0100
commit4a16c9bf49bd81ef1d29e8bb7ff013827a73fc8e (patch)
treeca294489b7dceb7e9098525c39ff0881e56ef4d0 /source
parentae1f2013c158e48ae773e74bf00348655e3565ba (diff)
downloadkit-4a16c9bf49bd81ef1d29e8bb7ff013827a73fc8e.zip
[bigint] Signed division
Diffstat (limited to 'source')
-rw-r--r--source/kit/bigint.h126
-rw-r--r--source/test/unittests/bigint.test.c22
2 files changed, 133 insertions, 15 deletions
diff --git a/source/kit/bigint.h b/source/kit/bigint.h
index b2fa49f..e6222c5 100644
--- a/source/kit/bigint.h
+++ b/source/kit/bigint.h
@@ -50,6 +50,32 @@ static kit_bigint_t kit_bi_uint64(uint64_t const x) {
return z;
}
+static kit_bigint_t kit_bi_int32(int32_t const x) {
+ kit_bigint_t z;
+ memset(&z, x < 0 ? -1 : 0, sizeof z);
+ z.v[0] = x;
+ return z;
+}
+
+static kit_bigint_t kit_bi_int64(int64_t const x) {
+ kit_bigint_t z;
+ memset(&z, x < 0 ? -1 : 0, sizeof z);
+ z.v[0] = (uint32_t) (((uint64_t) x) & 0xffffffff);
+ z.v[1] = (uint32_t) (((uint64_t) x) >> 32);
+ return z;
+}
+
+static int kit_bi_is_zero(kit_bigint_t const x) {
+ for (ptrdiff_t i = 0; i < KIT_BIGINT_SIZE / 4; i++)
+ if (x.v[i] != 0)
+ return 0;
+ return 1;
+}
+
+static int kit_bi_is_neg(kit_bigint_t const x) {
+ return (x.v[KIT_BIGINT_SIZE / 4 - 1] & 0x80000000) != 0;
+}
+
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.v, 1,
KIT_BIGINT_SIZE, y.v);
@@ -181,6 +207,36 @@ static kit_bit_t kit_bi_carry(uint32_t const x, uint32_t const y,
return 0xffffffffu - x < y || 0xffffffffu - x - y < carry ? 1 : 0;
}
+/* Increment.
+ */
+static kit_bigint_t kit_bi_inc(kit_bigint_t const x) {
+ kit_bigint_t z;
+ kit_bit_t carry = 1;
+
+ for (ptrdiff_t i = 0; i < KIT_BIGINT_SIZE / 4; i++) {
+ z.v[i] = x.v[i] + carry;
+ carry = kit_bi_carry(x.v[i], 0, carry);
+ }
+
+ return z;
+}
+
+/* Decrement
+ */
+static kit_bigint_t kit_bi_dec(kit_bigint_t const x) {
+ kit_bigint_t z;
+ kit_bit_t carry = 0;
+
+ for (ptrdiff_t i = 0; i < KIT_BIGINT_SIZE / 4; i++) {
+ z.v[i] = x.v[i] + 0xffffffff + carry;
+ carry = kit_bi_carry(x.v[i], 0xffffffff, carry);
+ }
+
+ return z;
+}
+
+/* Addition.
+ */
static kit_bigint_t kit_bi_add(kit_bigint_t const x,
kit_bigint_t const y) {
kit_bigint_t z;
@@ -194,6 +250,8 @@ static kit_bigint_t kit_bi_add(kit_bigint_t const x,
return z;
}
+/* Negation.
+ */
static kit_bigint_t kit_bi_neg(kit_bigint_t const x) {
kit_bigint_t y;
kit_bit_t carry = 1;
@@ -206,6 +264,8 @@ static kit_bigint_t kit_bi_neg(kit_bigint_t const x) {
return y;
}
+/* Subtraction.
+ */
static kit_bigint_t kit_bi_sub(kit_bigint_t const x,
kit_bigint_t const y) {
kit_bigint_t z;
@@ -242,6 +302,8 @@ static kit_bigint_t kit_bi_mul_uint32(kit_bigint_t const x,
return z;
}
+/* Multiplication.
+ */
static kit_bigint_t kit_bi_mul(kit_bigint_t const x,
kit_bigint_t const y) {
kit_bigint_t z;
@@ -275,8 +337,10 @@ typedef struct {
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) {
+/* Unsigned division.
+ */
+static kit_bi_division_t kit_bi_udiv(kit_bigint_t const x,
+ kit_bigint_t y) {
kit_bi_division_t result;
memset(&result, 0, sizeof result);
@@ -308,6 +372,34 @@ static kit_bi_division_t kit_bi_div(kit_bigint_t const x,
return result;
}
+/* Signed division.
+ *
+ * Remainder is always a non-negative value less than absolute value
+ * of y.
+ */
+static kit_bi_division_t kit_bi_div(kit_bigint_t const x,
+ kit_bigint_t const y) {
+ int const x_neg = kit_bi_is_neg(x);
+ int const y_neg = kit_bi_is_neg(y);
+
+ if (!x_neg && !y_neg)
+ return kit_bi_udiv(x, y);
+ if (x_neg && y_neg)
+ return kit_bi_udiv(kit_bi_neg(x), kit_bi_neg(y));
+
+ kit_bigint_t const x_abs = x_neg ? kit_bi_neg(x) : x;
+ kit_bigint_t const y_abs = y_neg ? kit_bi_neg(y) : y;
+
+ kit_bi_division_t z = kit_bi_udiv(x_abs, y_abs);
+
+ if (!kit_bi_is_zero(z.remainder) && !y_neg)
+ z.quotient = kit_bi_dec(kit_bi_neg(z.quotient));
+ else
+ z.quotient = kit_bi_neg(z.quotient);
+
+ return z;
+}
+
static void kit_bi_serialize(kit_bigint_t const in,
uint8_t *const out) {
for (ptrdiff_t i = 0; i < KIT_BIGINT_SIZE / 4; i++) {
@@ -332,7 +424,7 @@ 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) {
+static kit_bigint_t kit_bi_from_bin(kit_str_t const bin) {
kit_bigint_t z;
memset(&z, 0, sizeof z);
@@ -349,7 +441,7 @@ 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) {
+static kit_bigint_t kit_bi_from_dec(kit_str_t const dec) {
kit_bigint_t z = kit_bi_uint32(0);
kit_bigint_t factor = kit_bi_uint32(1);
@@ -373,7 +465,7 @@ static uint8_t kit_hex_digit(char const hex) {
return 0;
}
-static kit_bigint_t kit_bi_hex(kit_str_t const hex) {
+static kit_bigint_t kit_bi_from_hex(kit_str_t const hex) {
kit_bigint_t z;
memset(&z, 0, sizeof z);
@@ -402,7 +494,7 @@ static uint8_t kit_base32_digit(char const c) {
: 0;
}
-static kit_bigint_t kit_bi_base32(kit_str_t const base32) {
+static kit_bigint_t kit_bi_from_base32(kit_str_t const base32) {
kit_bigint_t z;
memset(&z, 0, sizeof z);
@@ -435,7 +527,7 @@ static uint8_t kit_base58_digit(char const c) {
: 0;
}
-static kit_bigint_t kit_bi_base58(kit_str_t const base58) {
+static kit_bigint_t kit_bi_from_base58(kit_str_t const base58) {
kit_bigint_t z = kit_bi_uint32(0);
kit_bigint_t factor = kit_bi_uint32(1);
@@ -455,26 +547,33 @@ static kit_bigint_t kit_bi_base58(kit_str_t const base58) {
#endif
#define KIT_BIN(static_str_) \
- kit_bi_bin(kit_str(sizeof(static_str_) - 1, (static_str_)))
+ kit_bi_from_bin(kit_str(sizeof(static_str_) - 1, (static_str_)))
#define KIT_DEC(static_str_) \
- kit_bi_dec(kit_str(sizeof(static_str_) - 1, (static_str_)))
+ kit_bi_from_dec(kit_str(sizeof(static_str_) - 1, (static_str_)))
#define KIT_HEX(static_str_) \
- kit_bi_hex(kit_str(sizeof(static_str_) - 1, (static_str_)))
+ kit_bi_from_hex(kit_str(sizeof(static_str_) - 1, (static_str_)))
#define KIT_BASE32(static_str_) \
- kit_bi_base32(kit_str(sizeof(static_str_) - 1, (static_str_)))
+ kit_bi_from_base32(kit_str(sizeof(static_str_) - 1, (static_str_)))
#define KIT_BASE58(static_str_) \
- kit_bi_base58(kit_str(sizeof(static_str_) - 1, (static_str_)))
+ kit_bi_from_base58(kit_str(sizeof(static_str_) - 1, (static_str_)))
#ifndef KIT_DISABLE_SHORT_NAMES
# define bigint_t kit_bigint_t
# define bi_uint32 kit_bi_uint32
# define bi_uint64 kit_bi_uint64
+# define bi_int32 kit_bi_int32
+# define bi_int64 kit_bi_int64
+# define bi_is_zero kit_bi_is_zero
+# define bi_is_neg kit_bi_is_neg
# define bi_equal kit_bi_equal
+# define bi_compare kit_bi_compare
# define bi_carry kit_bi_carry
+# define bi_inc kit_bi_inc
+# define bi_dec kit_bi_dec
# define bi_add kit_bi_add
# define bi_neg kit_bi_neg
# define bi_sub kit_bi_sub
@@ -482,9 +581,6 @@ static kit_bigint_t kit_bi_base58(kit_str_t const base58) {
# define bi_div kit_bi_div
# define bi_serialize kit_bi_serialize
# define bi_deserialize kit_bi_deserialize
-# define hex_digit kit_hex_digit
-# define bi_hex kit_bi_hex
-# define bi_base58 kit_bi_base58
# define BIN KIT_BIN
# define DEC KIT_DEC
# define HEX KIT_HEX
diff --git a/source/test/unittests/bigint.test.c b/source/test/unittests/bigint.test.c
index 0b45d7b..048bcca 100644
--- a/source/test/unittests/bigint.test.c
+++ b/source/test/unittests/bigint.test.c
@@ -56,6 +56,28 @@ TEST("bigint base58 mul") {
}
TEST("bigint div") {
+ REQUIRE(bi_equal(bi_div(bi_int32(-1), bi_int32(-1)).quotient,
+ bi_int32(1)));
+ REQUIRE(bi_equal(bi_div(bi_int32(-1), bi_int32(-1)).remainder,
+ bi_int32(0)));
+ REQUIRE(bi_equal(bi_div(bi_int32(-3), bi_int32(2)).quotient,
+ bi_int32(-2)));
+ REQUIRE(bi_equal(bi_div(bi_int32(-3), bi_int32(2)).remainder,
+ bi_int32(1)));
+ REQUIRE(bi_equal(bi_div(bi_int32(3), bi_int32(-2)).quotient,
+ bi_int32(-1)));
+ REQUIRE(bi_equal(bi_div(bi_int32(3), bi_int32(-2)).remainder,
+ bi_int32(1)));
+ REQUIRE(bi_equal(bi_div(bi_int32(-3), bi_int32(4)).quotient,
+ bi_int32(-1)));
+ REQUIRE(bi_equal(bi_div(bi_int32(-3), bi_int32(4)).remainder,
+ bi_int32(3)));
+ REQUIRE(bi_equal(bi_div(bi_int32(3), bi_int32(-4)).quotient,
+ bi_int32(0)));
+ REQUIRE(bi_equal(bi_div(bi_int32(3), bi_int32(-4)).remainder,
+ bi_int32(3)));
+
+
REQUIRE(
bi_equal(bi_div(HEX("100"), HEX("10")).quotient, HEX("10")));