Commit `a03f9548d3`

Frank Denis <github@pureftpd.org>

2021-01-31 20:58:11

std/math/big/int: normalize after a right shift

After a right shift, top limbs may be all zero. However, without normalization, the number of limbs is not going to change. In order to check if a big number is zero, we used to assume that the number of limbs is 1. Which may not be the case after right shifts, even if the actual value is zero. - Normalize after a right shift - Add a test for that issue - Check all the limbs in `eqlZero()`. It may not be necessary if callers always remember to normalize before calling the function. But checking all the limbs is very cheap and makes the function less bug-prone.

master

1 parent bf76501

Changed files (2)

lib

std

math

big

int.zig

int_test.zig

@@ -549,8 +549,8 @@ pub const Mutable = struct {
             return;
         }
 
-        const r_len = llshr(r.limbs[0..], a.limbs[0..a.limbs.len], shift);
-        r.len = a.limbs.len - (shift / limb_bits);
+        llshr(r.limbs[0..], a.limbs[0..a.limbs.len], shift);
+        r.normalize(a.limbs.len - (shift / limb_bits));
         r.positive = a.positive;
     }
 
@@ -1348,7 +1348,9 @@ pub const Const = struct {
 
     /// Returns true if `a == 0`.
     pub fn eqZero(a: Const) bool {
-        return a.limbs.len == 1 and a.limbs[0] == 0;
+        var d: Limb = 0;
+        for (a.limbs) |limb| d |= limb;
+        return d == 0;
     }
 
     /// Returns true if `|a| == |b|`.

@@ -1287,6 +1287,12 @@ test "big.int shift-right multi" {
     try a.shiftRight(a, 67);
 
     testing.expect((try a.to(u64)) == 0x1fffe0001dddc222);
+
+    try a.set(0xffff0000eeee1111dddd2222cccc3333);
+    try a.shiftRight(a, 63);
+    try a.shiftRight(a, 63);
+    try a.shiftRight(a, 2);
+    testing.expect(a.eqZero());
 }
 
 test "big.int shift-left single" {

Commit a03f9548d3

Commit `a03f9548d3`