From 89a4c373d3756baeac9d2780b1249ada37961d16 Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Mon, 23 Apr 2018 12:06:18 -0400 Subject: fix bigint twos complement implementation closes #948 --- src/bigint.cpp | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'src/bigint.cpp') diff --git a/src/bigint.cpp b/src/bigint.cpp index 85e5dad4ad..2a688debd5 100644 --- a/src/bigint.cpp +++ b/src/bigint.cpp @@ -86,6 +86,11 @@ static void to_twos_complement(BigInt *dest, const BigInt *op, size_t bit_count) size_t digits_to_copy = bit_count / 64; size_t leftover_bits = bit_count % 64; dest->digit_count = digits_to_copy + ((leftover_bits == 0) ? 0 : 1); + if (dest->digit_count == 1 && leftover_bits == 0) { + dest->data.digit = op_digits[0]; + if (dest->data.digit == 0) dest->digit_count = 0; + return; + } dest->data.digits = allocate_nonzero(dest->digit_count); for (size_t i = 0; i < digits_to_copy; i += 1) { uint64_t digit = (i < op->digit_count) ? op_digits[i] : 0; -- cgit v1.2.3 From d7b029995c8ac678598de39aa106076dca232902 Mon Sep 17 00:00:00 2001 From: Marc Tiehuis Date: Sat, 5 May 2018 22:40:29 +1200 Subject: Fix bigint multi-limb shift and masks --- src/bigint.cpp | 10 ++++------ test/cases/math.zig | 17 +++++++++++++++++ 2 files changed, 21 insertions(+), 6 deletions(-) (limited to 'src/bigint.cpp') diff --git a/src/bigint.cpp b/src/bigint.cpp index 2a688debd5..64bc59e5cf 100644 --- a/src/bigint.cpp +++ b/src/bigint.cpp @@ -1259,12 +1259,11 @@ void bigint_and(BigInt *dest, const BigInt *op1, const BigInt *op2) { bigint_normalize(dest); return; } - // TODO this code path is untested - uint64_t first_digit = dest->data.digit; + dest->digit_count = max(op1->digit_count, op2->digit_count); dest->data.digits = allocate_nonzero(dest->digit_count); - dest->data.digits[0] = first_digit; - size_t i = 1; + + size_t i = 0; for (; i < op1->digit_count && i < op2->digit_count; i += 1) { dest->data.digits[i] = op1_digits[i] & op2_digits[i]; } @@ -1412,7 +1411,6 @@ void bigint_shr(BigInt *dest, const BigInt *op1, const BigInt *op2) { return; } - // TODO this code path is untested size_t digit_shift_count = shift_amt / 64; size_t leftover_shift_count = shift_amt % 64; @@ -1427,7 +1425,7 @@ void bigint_shr(BigInt *dest, const BigInt *op1, const BigInt *op2) { uint64_t digit = op1_digits[op_digit_index]; size_t dest_digit_index = op_digit_index - digit_shift_count; dest->data.digits[dest_digit_index] = carry | (digit >> leftover_shift_count); - carry = (0xffffffffffffffffULL << leftover_shift_count) & digit; + carry = digit << leftover_shift_count; if (dest_digit_index == 0) { break; } op_digit_index -= 1; diff --git a/test/cases/math.zig b/test/cases/math.zig index 47d001a590..3c33b14fbf 100644 --- a/test/cases/math.zig +++ b/test/cases/math.zig @@ -349,6 +349,23 @@ test "big number shifting" { } } +test "big number multi-limb shift and mask" { + comptime { + var a = 0xefffffffa0000001eeeeeeefaaaaaaab; + + assert(u32(a & 0xffffffff) == 0xaaaaaaab); + a >>= 32; + assert(u32(a & 0xffffffff) == 0xeeeeeeef); + a >>= 32; + assert(u32(a & 0xffffffff) == 0xa0000001); + a >>= 32; + assert(u32(a & 0xffffffff) == 0xefffffff); + a >>= 32; + + assert(a == 0); + } +} + test "xor" { test_xor(); comptime test_xor(); -- cgit v1.2.3 From efa39c5343e13a13e65210f55da5df23ee3feb3e Mon Sep 17 00:00:00 2001 From: Marc Tiehuis Date: Thu, 10 May 2018 22:26:26 +1200 Subject: Fix bigint shift-right partial shift --- src/bigint.cpp | 2 +- test/cases/math.zig | 8 ++++++++ 2 files changed, 9 insertions(+), 1 deletion(-) (limited to 'src/bigint.cpp') diff --git a/src/bigint.cpp b/src/bigint.cpp index 64bc59e5cf..367ae79b6c 100644 --- a/src/bigint.cpp +++ b/src/bigint.cpp @@ -1425,7 +1425,7 @@ void bigint_shr(BigInt *dest, const BigInt *op1, const BigInt *op2) { uint64_t digit = op1_digits[op_digit_index]; size_t dest_digit_index = op_digit_index - digit_shift_count; dest->data.digits[dest_digit_index] = carry | (digit >> leftover_shift_count); - carry = digit << leftover_shift_count; + carry = digit << (64 - leftover_shift_count); if (dest_digit_index == 0) { break; } op_digit_index -= 1; diff --git a/test/cases/math.zig b/test/cases/math.zig index 3c33b14fbf..13704ecd4b 100644 --- a/test/cases/math.zig +++ b/test/cases/math.zig @@ -366,6 +366,14 @@ test "big number multi-limb shift and mask" { } } +test "big number multi-limb partial shift right" { + comptime { + var a = 0x1ffffffffeeeeeeee; + a >>= 16; + assert(a == 0x1ffffffffeeee); + } +} + test "xor" { test_xor(); comptime test_xor(); -- cgit v1.2.3