From 8f5753ba9f1fd43f14628e143d33d6e8a64847f0 Mon Sep 17 00:00:00 2001 From: LemonBoy Date: Wed, 10 Apr 2019 10:57:43 +0200 Subject: Fix normalization of right-shifted BigInt at CT The pointer value for the `digits` field was being treated as if it were a limb. Fixes #2225 --- src/bigint.cpp | 11 +++++++++-- 1 file changed, 9 insertions(+), 2 deletions(-) (limited to 'src/bigint.cpp') diff --git a/src/bigint.cpp b/src/bigint.cpp index d3178c35c6..dcd9dfc0bd 100644 --- a/src/bigint.cpp +++ b/src/bigint.cpp @@ -1410,12 +1410,19 @@ void bigint_shr(BigInt *dest, const BigInt *op1, const BigInt *op2) { } dest->digit_count = op1->digit_count - digit_shift_count; - dest->data.digits = allocate(dest->digit_count); + uint64_t *digits; + if (dest->digit_count == 1) { + digits = &dest->data.digit; + } else { + digits = allocate(dest->digit_count); + dest->data.digits = digits; + } + uint64_t carry = 0; for (size_t op_digit_index = op1->digit_count - 1;;) { 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); + digits[dest_digit_index] = carry | (digit >> leftover_shift_count); carry = digit << (64 - leftover_shift_count); if (dest_digit_index == 0) { break; } -- cgit v1.2.3 From 9ec4ccc68f6473ce4f02fc5d2b87ad92e2eb555a Mon Sep 17 00:00:00 2001 From: LemonBoy Date: Fri, 26 Apr 2019 15:57:47 +0200 Subject: Do not invoke UB in BigInt shr operations Shifting a value of type T by an amount that's greater or equal to the size of the type itself is UB. Spotted by @tgschultz --- src/bigint.cpp | 2 +- test/stage1/behavior/bit_shifting.zig | 6 ++++-- 2 files changed, 5 insertions(+), 3 deletions(-) (limited to 'src/bigint.cpp') diff --git a/src/bigint.cpp b/src/bigint.cpp index dcd9dfc0bd..da53a2b129 100644 --- a/src/bigint.cpp +++ b/src/bigint.cpp @@ -1395,7 +1395,7 @@ void bigint_shr(BigInt *dest, const BigInt *op1, const BigInt *op2) { uint64_t shift_amt = bigint_as_unsigned(op2); if (op1->digit_count == 1) { - dest->data.digit = op1_digits[0] >> shift_amt; + dest->data.digit = (shift_amt < 64) ? op1_digits[0] >> shift_amt : 0; dest->digit_count = 1; dest->is_negative = op1->is_negative; bigint_normalize(dest); diff --git a/test/stage1/behavior/bit_shifting.zig b/test/stage1/behavior/bit_shifting.zig index c638ec1709..1877c8cdcb 100644 --- a/test/stage1/behavior/bit_shifting.zig +++ b/test/stage1/behavior/bit_shifting.zig @@ -90,7 +90,9 @@ fn testShardedTable(comptime Key: type, comptime mask_bit_count: comptime_int, c // #2225 test "comptime shr of BigInt" { comptime { - var n = 0xdeadbeef0000000000000000; - std.debug.assert(n >> 64 == 0xdeadbeef); + var n0 = 0xdeadbeef0000000000000000; + std.debug.assert(n0 >> 64 == 0xdeadbeef); + var n1 = 17908056155735594659; + std.debug.assert(n1 >> 64 == 0); } } -- cgit v1.2.3