From f5c27dd11aeac3bb4647396a0e420c649b30f468 Mon Sep 17 00:00:00 2001 From: Robin Voetter Date: Thu, 23 Sep 2021 04:08:27 +0200 Subject: big ints: 2s complement signed or --- lib/std/math/big/int.zig | 138 +++++++++++++++++++++++++++++++++++++----- lib/std/math/big/int_test.zig | 66 ++++++++++++++++++++ 2 files changed, 190 insertions(+), 14 deletions(-) (limited to 'lib') diff --git a/lib/std/math/big/int.zig b/lib/std/math/big/int.zig index e1b9c94fff..8b9cc7168a 100644 --- a/lib/std/math/big/int.zig +++ b/lib/std/math/big/int.zig @@ -552,21 +552,29 @@ pub const Mutable = struct { r.positive = a.positive; } - /// r = a | b + /// r = a | b under 2s complement semantics. /// r may alias with a or b. /// /// a and b are zero-extended to the longer of a or b. /// /// Asserts that r has enough limbs to store the result. Upper bound is `math.max(a.limbs.len, b.limbs.len)`. pub fn bitOr(r: *Mutable, a: Const, b: Const) void { - if (a.limbs.len > b.limbs.len) { - llor(r.limbs[0..], a.limbs[0..a.limbs.len], b.limbs[0..b.limbs.len]); - r.len = a.limbs.len; + // Trivial cases, llsignedor does not support zero. + if (a.eqZero()) { + r.copy(b); + return; + } else if (b.eqZero()) { + r.copy(a); + return; + } + + if (a.limbs.len >= b.limbs.len) { + r.positive = llsignedor(r.limbs, a.limbs, a.positive, b.limbs, b.positive); + r.normalize(a.limbs.len); } else { - llor(r.limbs[0..], b.limbs[0..b.limbs.len], a.limbs[0..a.limbs.len]); - r.len = b.limbs.len; + r.positive = llsignedor(r.limbs, b.limbs, b.positive, a.limbs, a.positive); + r.normalize(b.limbs.len); } - r.positive = a.positive or b.positive; } /// r = a & b @@ -2236,17 +2244,119 @@ fn llshr(r: []Limb, a: []const Limb, shift: usize) void { } } -fn llor(r: []Limb, a: []const Limb, b: []const Limb) void { +fn llsignedor(r: []Limb, a: []const Limb, a_positive: bool, b: []const Limb, b_positive: bool) bool { @setRuntimeSafety(debug_safety); assert(r.len >= a.len); assert(a.len >= b.len); - var i: usize = 0; - while (i < b.len) : (i += 1) { - r[i] = a[i] | b[i]; - } - while (i < a.len) : (i += 1) { - r[i] = a[i]; + if (a_positive and b_positive) { + // Trivial case, result is positive., + var i: usize = 0; + while (i < b.len) : (i += 1) { + r[i] = a[i] | b[i]; + } + while (i < a.len) : (i += 1) { + r[i] = a[i]; + } + + return true; + } else if (!a_positive and b_positive) { + // r = (--a) | b + // = ~(-a - 1) | b + // = ~(-a - 1) | ~~b + // = ~((-a - 1) & ~b) + // = -(((-a - 1) & ~b) + 1) + // result is negative. + + var i: usize = 0; + var a_borrow: u1 = 1; + var r_carry: u1 = 1; + + while (i < b.len) : (i += 1) { + var a_limb: Limb = undefined; + a_borrow = @boolToInt(@subWithOverflow(Limb, a[i], a_borrow, &a_limb)); + + r[i] = a_limb & ~b[i]; + r_carry = @boolToInt(@addWithOverflow(Limb, r[i], r_carry, &r[i])); + } + + // With b = 0, we get (-a - 1) & ~0 = -a - 1. + while (i < a.len) : (i += 1) { + a_borrow = @boolToInt(@subWithOverflow(Limb, a[i], a_borrow, &r[i])); + r_carry = @boolToInt(@addWithOverflow(Limb, r[i], r_carry, &r[i])); + } + + assert(a_borrow == 0); // a was 0. + + // Can never overflow because a_borrow would need to equal 1. + assert(r_carry == 0); + + return false; + } else if (a_positive and !b_positive) { + // r = a | (--b) + // = a | ~(-b - 1) + // = ~~a | ~(-b - 1) + // = ~(~a & (-b - 1)) + // = -((~a & (-b - 1)) + 1) + // result is negative. + + var i: usize = 0; + var b_borrow: u1 = 1; + var r_carry: u1 = 1; + + while (i < b.len) : (i += 1) { + var b_limb: Limb = undefined; + b_borrow = @boolToInt(@subWithOverflow(Limb, b[i], b_borrow, &b_limb)); + + r[i] = ~a[i] & b_limb; + r_carry = @boolToInt(@addWithOverflow(Limb, r[i], r_carry, &r[i])); + } + + // b is at least 1, so this should never underflow. + assert(b_borrow == 0); // b was 0 + + // Can never overflow because in order for b_limb to be maxInt(Limb), + // b_borrow would need to equal 1. + assert(r_carry == 0); + + // With b = 0 and b_borrow = 0, we get ~a & (-0 - 0) = ~a & 0 = 0. + mem.set(Limb, r[i..a.len], 0); + + return false; + } else { + // r = (--a) | (--b) + // = ~(-a - 1) | ~(-b - 1) + // = ~((-a - 1) & (-b - 1)) + // = -(~(~((-a - 1) & (-b - 1))) + 1) + // = -((-a - 1) & (-b - 1) + 1) + // result is negative. + + var i: usize = 0; + var a_borrow: u1 = 1; + var b_borrow: u1 = 1; + var r_carry: u1 = 1; + + while (i < b.len) : (i += 1) { + var a_limb: Limb = undefined; + a_borrow = @boolToInt(@subWithOverflow(Limb, a[i], a_borrow, &a_limb)); + + var b_limb: Limb = undefined; + b_borrow = @boolToInt(@subWithOverflow(Limb, b[i], b_borrow, &b_limb)); + + r[i] = a_limb & b_limb; + r_carry = @boolToInt(@addWithOverflow(Limb, r[i], r_carry, &r[i])); + } + + // b is at least 1, so this should never underflow. + assert(b_borrow == 0); // b was 0 + + // Can never overflow because in order for b_limb to be maxInt(Limb), + // b_borrow would need to equal 1. + assert(r_carry == 0); + + // With b = 0 and b_borrow = 0 we get (-a - 1) & (-0 - 0) = (-a - 1) & 0 = 0. + mem.set(Limb, r[i..a.len], 0); + return false; } } diff --git a/lib/std/math/big/int_test.zig b/lib/std/math/big/int_test.zig index 993101c674..b9f7c5c116 100644 --- a/lib/std/math/big/int_test.zig +++ b/lib/std/math/big/int_test.zig @@ -1476,6 +1476,72 @@ test "big.int bitwise or multi-limb" { try testing.expect((try a.to(DoubleLimb)) == (maxInt(Limb) + 1) + maxInt(Limb)); } +test "big.int bitwise or negative-positive simple" { + var a = try Managed.initSet(testing.allocator, -0xffffffff11111111); + defer a.deinit(); + var b = try Managed.initSet(testing.allocator, 0xeeeeeeee22222222); + defer b.deinit(); + + try a.bitOr(a, b); + + try testing.expect((try a.to(i64)) == -0x1111111111111111); +} + +test "big.int bitwise or negative-positive multi-limb" { + var a = try Managed.initSet(testing.allocator, -maxInt(Limb) - 1); + defer a.deinit(); + var b = try Managed.initSet(testing.allocator, 1); + defer b.deinit(); + + try a.bitOr(a, b); + + try testing.expect((try a.to(SignedDoubleLimb)) == -maxInt(Limb)); +} + +test "big.int bitwise or positive-negative simple" { + var a = try Managed.initSet(testing.allocator, 0xffffffff11111111); + defer a.deinit(); + var b = try Managed.initSet(testing.allocator, -0xeeeeeeee22222222); + defer b.deinit(); + + try a.bitOr(a, b); + + try testing.expect((try a.to(i64)) == -0x22222221); +} + +test "big.int bitwise or positive-negative multi-limb" { + var a = try Managed.initSet(testing.allocator, maxInt(Limb) + 1); + defer a.deinit(); + var b = try Managed.initSet(testing.allocator, -1); + defer b.deinit(); + + try a.bitOr(a, b); + + try testing.expect((try a.to(SignedDoubleLimb)) == -1); +} + +test "big.int bitwise or negative-negative simple" { + var a = try Managed.initSet(testing.allocator, -0x0fffffff11111111); + defer a.deinit(); + var b = try Managed.initSet(testing.allocator, -0x0eeeeeee22222222); + defer b.deinit(); + + try a.bitOr(a, b); + + try testing.expect((try a.to(i64)) == -0xeeeeeee00000001); +} + +test "big.int bitwise or negative-negative multi-limb" { + var a = try Managed.initSet(testing.allocator, -maxInt(Limb) - 1); + defer a.deinit(); + var b = try Managed.initSet(testing.allocator, -maxInt(Limb)); + defer b.deinit(); + + try a.bitOr(a, b); + + try testing.expect((try a.to(SignedDoubleLimb)) == -maxInt(Limb)); +} + test "big.int var args" { var a = try Managed.initSet(testing.allocator, 5); defer a.deinit(); -- cgit v1.2.3 From 351e4f07cebc8299c107bd3de760efe17d184af7 Mon Sep 17 00:00:00 2001 From: Robin Voetter Date: Thu, 23 Sep 2021 06:19:08 +0200 Subject: big ints: 2s complement signed and + or fixes --- lib/std/math/big/int.zig | 178 +++++++++++++++++++++++++++++++++++------- lib/std/math/big/int_test.zig | 83 +++++++++++++++++++- 2 files changed, 229 insertions(+), 32 deletions(-) (limited to 'lib') diff --git a/lib/std/math/big/int.zig b/lib/std/math/big/int.zig index 8b9cc7168a..fa8a63b67d 100644 --- a/lib/std/math/big/int.zig +++ b/lib/std/math/big/int.zig @@ -570,26 +570,36 @@ pub const Mutable = struct { if (a.limbs.len >= b.limbs.len) { r.positive = llsignedor(r.limbs, a.limbs, a.positive, b.limbs, b.positive); - r.normalize(a.limbs.len); + r.normalize(if (b.positive) a.limbs.len else b.limbs.len); } else { r.positive = llsignedor(r.limbs, b.limbs, b.positive, a.limbs, a.positive); - r.normalize(b.limbs.len); + r.normalize(if (a.positive) b.limbs.len else a.limbs.len); } } - /// r = a & b + /// r = a & b under 2s complement semantics. /// r may alias with a or b. /// - /// Asserts that r has enough limbs to store the result. Upper bound is `math.min(a.limbs.len, b.limbs.len)`. + /// Asserts that r has enough limbs to store the result. + /// If a or b is positive, the upper bound is `math.min(a.limbs.len, b.limbs.len)`. + /// If a and b are negative, the upper bound is `math.max(a.limbs.len, b.limbs.len) + 1`. pub fn bitAnd(r: *Mutable, a: Const, b: Const) void { - if (a.limbs.len > b.limbs.len) { - lland(r.limbs[0..], a.limbs[0..a.limbs.len], b.limbs[0..b.limbs.len]); - r.normalize(b.limbs.len); + // Trivial cases, llsignedand does not support zero. + if (a.eqZero()) { + r.copy(a); + return; + } else if (b.eqZero()) { + r.copy(b); + return; + } + + if (a.limbs.len >= b.limbs.len) { + r.positive = llsignedand(r.limbs, a.limbs, a.positive, b.limbs, b.positive); + r.normalize(if (a.positive or b.positive) b.limbs.len else a.limbs.len + 1); } else { - lland(r.limbs[0..], b.limbs[0..b.limbs.len], a.limbs[0..a.limbs.len]); - r.normalize(a.limbs.len); + r.positive = llsignedand(r.limbs, b.limbs, b.positive, a.limbs, a.positive); + r.normalize(if (a.positive or b.positive) a.limbs.len else b.limbs.len + 1); } - r.positive = a.positive and b.positive; } /// r = a ^ b under 2s complement semantics. @@ -1855,7 +1865,11 @@ pub const Managed = struct { /// r = a & b pub fn bitAnd(r: *Managed, a: Managed, b: Managed) !void { - try r.ensureCapacity(math.min(a.len(), b.len())); + const cap = if (a.isPositive() or b.isPositive()) + math.min(a.len(), b.len()) + else + math.max(a.len(), b.len()) + 1; + try r.ensureCapacity(cap); var m = r.toMutable(); m.bitAnd(a.toConst(), b.toConst()); r.setMetadata(m.positive, m.len); @@ -2244,13 +2258,19 @@ fn llshr(r: []Limb, a: []const Limb, shift: usize) void { } } +// r = a | b with 2s complement semantics. +// r may alias. +// a and b must not be 0. +// Returns `true` when the result is positive. +// When b is positive, r requires at least `a.len` limbs of storage. +// When b is negative, r requires at least `b.len` limbs of storage. fn llsignedor(r: []Limb, a: []const Limb, a_positive: bool, b: []const Limb, b_positive: bool) bool { @setRuntimeSafety(debug_safety); assert(r.len >= a.len); assert(a.len >= b.len); if (a_positive and b_positive) { - // Trivial case, result is positive., + // Trivial case, result is positive. var i: usize = 0; while (i < b.len) : (i += 1) { r[i] = a[i] | b[i]; @@ -2261,12 +2281,12 @@ fn llsignedor(r: []Limb, a: []const Limb, a_positive: bool, b: []const Limb, b_p return true; } else if (!a_positive and b_positive) { + // Result is negative. // r = (--a) | b // = ~(-a - 1) | b // = ~(-a - 1) | ~~b // = ~((-a - 1) & ~b) // = -(((-a - 1) & ~b) + 1) - // result is negative. var i: usize = 0; var a_borrow: u1 = 1; @@ -2280,25 +2300,29 @@ fn llsignedor(r: []Limb, a: []const Limb, a_positive: bool, b: []const Limb, b_p r_carry = @boolToInt(@addWithOverflow(Limb, r[i], r_carry, &r[i])); } + // In order for r_carry to be nonzero at this point, ~b[i] would need to be + // all ones, which would require b[i] to be zero. This cannot be when + // b is normalized, so there cannot be a carry here. + // Also, x & ~b can only clear bits, so (x & ~b) <= x, meaning (-a - 1) + 1 never overflows. + assert(r_carry == 0); + // With b = 0, we get (-a - 1) & ~0 = -a - 1. - while (i < a.len) : (i += 1) { + // Note, if a_borrow is zero we do not need to compute anything for + // the higher limbs so we can early return here. + while (i < a.len and a_borrow == 1) : (i += 1) { a_borrow = @boolToInt(@subWithOverflow(Limb, a[i], a_borrow, &r[i])); - r_carry = @boolToInt(@addWithOverflow(Limb, r[i], r_carry, &r[i])); } assert(a_borrow == 0); // a was 0. - // Can never overflow because a_borrow would need to equal 1. - assert(r_carry == 0); - return false; } else if (a_positive and !b_positive) { + // Result is negative. // r = a | (--b) // = a | ~(-b - 1) // = ~~a | ~(-b - 1) // = ~(~a & (-b - 1)) // = -((~a & (-b - 1)) + 1) - // result is negative. var i: usize = 0; var b_borrow: u1 = 1; @@ -2315,21 +2339,20 @@ fn llsignedor(r: []Limb, a: []const Limb, a_positive: bool, b: []const Limb, b_p // b is at least 1, so this should never underflow. assert(b_borrow == 0); // b was 0 - // Can never overflow because in order for b_limb to be maxInt(Limb), - // b_borrow would need to equal 1. + // x & ~a can only clear bits, so (x & ~a) <= x, meaning (-b - 1) + 1 never overflows. assert(r_carry == 0); // With b = 0 and b_borrow = 0, we get ~a & (-0 - 0) = ~a & 0 = 0. - mem.set(Limb, r[i..a.len], 0); + // Omit setting the upper bytes, just deal with those when calling llsignedor. return false; } else { + // Result is negative. // r = (--a) | (--b) // = ~(-a - 1) | ~(-b - 1) // = ~((-a - 1) & (-b - 1)) // = -(~(~((-a - 1) & (-b - 1))) + 1) // = -((-a - 1) & (-b - 1) + 1) - // result is negative. var i: usize = 0; var a_borrow: u1 = 1; @@ -2352,22 +2375,119 @@ fn llsignedor(r: []Limb, a: []const Limb, a_positive: bool, b: []const Limb, b_p // Can never overflow because in order for b_limb to be maxInt(Limb), // b_borrow would need to equal 1. + + // x & y can only clear bits, meaning x & y <= x and x & y <= y. This implies that + // for x = a - 1 and y = b - 1, the +1 term would never cause an overflow. assert(r_carry == 0); // With b = 0 and b_borrow = 0 we get (-a - 1) & (-0 - 0) = (-a - 1) & 0 = 0. - mem.set(Limb, r[i..a.len], 0); + // Omit setting the upper bytes, just deal with those when calling llsignedor. return false; } } -fn lland(r: []Limb, a: []const Limb, b: []const Limb) void { +// r = a & b with 2s complement semantics. +// r may alias. +// a and b must not be 0. +// Returns `true` when the result is positive. +// When either or both of a and b are positive, r requires at least `b.len` limbs of storage. +// When both a and b are negative, r requires at least `a.limbs.len + 1` limbs of storage. +fn llsignedand(r: []Limb, a: []const Limb, a_positive: bool, b: []const Limb, b_positive: bool) bool { @setRuntimeSafety(debug_safety); - assert(r.len >= b.len); + assert(a.len != 0 and b.len != 0); + assert(r.len >= a.len); assert(a.len >= b.len); - var i: usize = 0; - while (i < b.len) : (i += 1) { - r[i] = a[i] & b[i]; + if (a_positive and b_positive) { + // Trivial case, result is positive. + var i: usize = 0; + while (i < b.len) : (i += 1) { + r[i] = a[i] & b[i]; + } + + // With b = 0 we have a & 0 = 0, so the upper bytes are zero. + // Omit setting them here and simply discard them whenever + // llsignedand is called. + + return true; + } else if (!a_positive and b_positive) { + // Result is positive. + // r = (--a) & b + // = ~(-a - 1) & b + + var i: usize = 0; + var a_borrow: u1 = 1; + + while (i < b.len) : (i += 1) { + var a_limb: Limb = undefined; + a_borrow = @boolToInt(@subWithOverflow(Limb, a[i], a_borrow, &a_limb)); + r[i] = ~a_limb & b[i]; + } + + // With b = 0 we have ~(a - 1) & 0 = 0, so the upper bytes are zero. + // Omit setting them here and simply discard them whenever + // llsignedand is called. + + return true; + } else if (a_positive and !b_positive) { + // Result is positive. + // r = a & (--b) + // = a & ~(-b - 1) + + var i: usize = 0; + var b_borrow: u1 = 1; + + while (i < b.len) : (i += 1) { + var a_limb: Limb = undefined; + b_borrow = @boolToInt(@subWithOverflow(Limb, b[i], b_borrow, &a_limb)); + r[i] = a[i] & ~a_limb; + } + + assert(b_borrow == 0); // b was 0 + + // With b = 0 and b_borrow = 0 we have a & ~(-0 - 0) = a & 0 = 0, so + // the upper bytes are zero. Omit setting them here and simply discard + // them whenever llsignedand is called. + + return true; + } else { + // Result is negative. + // r = (--a) & (--b) + // = ~(-a - 1) & ~(-b - 1) + // = ~((-a - 1) | (-b - 1)) + // = -(((-a - 1) | (-b - 1)) + 1) + + var i: usize = 0; + var a_borrow: u1 = 1; + var b_borrow: u1 = 1; + var r_carry: u1 = 1; + + while (i < b.len) : (i += 1) { + var a_limb: Limb = undefined; + a_borrow = @boolToInt(@subWithOverflow(Limb, a[i], a_borrow, &a_limb)); + + var b_limb: Limb = undefined; + b_borrow = @boolToInt(@subWithOverflow(Limb, b[i], b_borrow, &b_limb)); + + r[i] = a_limb | b_limb; + r_carry = @boolToInt(@addWithOverflow(Limb, r[i], r_carry, &r[i])); + } + + // b is at least 1, so this should never underflow. + assert(b_borrow == 0); // b was 0 + + // With b = 0 and b_borrow = 0 we get (-a - 1) | (-0 - 0) = (-a - 1) | 0 = -a - 1. + while (i < a.len) : (i += 1) { + a_borrow = @boolToInt(@subWithOverflow(Limb, a[i], a_borrow, &r[i])); + r_carry = @boolToInt(@addWithOverflow(Limb, r[i], r_carry, &r[i])); + } + + assert(a_borrow == 0); // a was 0. + + // The final addition can overflow here, so we need to keep that in mind. + r[i] = r_carry; + + return false; } } diff --git a/lib/std/math/big/int_test.zig b/lib/std/math/big/int_test.zig index b9f7c5c116..7b5e14b808 100644 --- a/lib/std/math/big/int_test.zig +++ b/lib/std/math/big/int_test.zig @@ -1365,6 +1365,83 @@ test "big.int bitwise and multi-limb" { try testing.expect((try a.to(u128)) == 0); } +test "big.int bitwise and negative-positive simple" { + var a = try Managed.initSet(testing.allocator, -0xffffffff11111111); + defer a.deinit(); + var b = try Managed.initSet(testing.allocator, 0xeeeeeeee22222222); + defer b.deinit(); + + try a.bitAnd(a, b); + + try testing.expect((try a.to(u64)) == 0x22222222); +} + +test "big.int bitwise and negative-positive multi-limb" { + var a = try Managed.initSet(testing.allocator, -maxInt(Limb) - 1); + defer a.deinit(); + var b = try Managed.initSet(testing.allocator, maxInt(Limb)); + defer b.deinit(); + + try a.bitAnd(a, b); + + try testing.expect(a.eqZero()); +} + +test "big.int bitwise and positive-negative simple" { + var a = try Managed.initSet(testing.allocator, 0xffffffff11111111); + defer a.deinit(); + var b = try Managed.initSet(testing.allocator, -0xeeeeeeee22222222); + defer b.deinit(); + + try a.bitAnd(a, b); + + try testing.expect((try a.to(u64)) == 0x1111111111111110); +} + +test "big.int bitwise and positive-negative multi-limb" { + var a = try Managed.initSet(testing.allocator, maxInt(Limb)); + defer a.deinit(); + var b = try Managed.initSet(testing.allocator, -maxInt(Limb) - 1); + defer b.deinit(); + + try a.bitAnd(a, b); + + try testing.expect(a.eqZero()); +} + +test "big.int bitwise and negative-negative simple" { + var a = try Managed.initSet(testing.allocator, -0xffffffff11111111); + defer a.deinit(); + var b = try Managed.initSet(testing.allocator, -0xeeeeeeee22222222); + defer b.deinit(); + + try a.bitAnd(a, b); + + try testing.expect((try a.to(i128)) == -0xffffffff33333332); +} + +test "big.int bitwise and negative-negative multi-limb" { + var a = try Managed.initSet(testing.allocator, -maxInt(Limb) - 1); + defer a.deinit(); + var b = try Managed.initSet(testing.allocator, -maxInt(Limb) - 2); + defer b.deinit(); + + try a.bitAnd(a, b); + + try testing.expect((try a.to(i128)) == -maxInt(Limb) * 2 - 2); +} + +test "big.int bitwise and negative overflow" { + var a = try Managed.initSet(testing.allocator, -maxInt(Limb)); + defer a.deinit(); + var b = try Managed.initSet(testing.allocator, -2); + defer b.deinit(); + + try a.bitAnd(a, b); + + try testing.expect((try a.to(SignedDoubleLimb)) == -maxInt(Limb) - 1); +} + test "big.int bitwise xor simple" { var a = try Managed.initSet(testing.allocator, 0xffffffff11111111); defer a.deinit(); @@ -1521,14 +1598,14 @@ test "big.int bitwise or positive-negative multi-limb" { } test "big.int bitwise or negative-negative simple" { - var a = try Managed.initSet(testing.allocator, -0x0fffffff11111111); + var a = try Managed.initSet(testing.allocator, -0xffffffff11111111); defer a.deinit(); - var b = try Managed.initSet(testing.allocator, -0x0eeeeeee22222222); + var b = try Managed.initSet(testing.allocator, -0xeeeeeeee22222222); defer b.deinit(); try a.bitOr(a, b); - try testing.expect((try a.to(i64)) == -0xeeeeeee00000001); + try testing.expect((try a.to(i128)) == -0xeeeeeeee00000001); } test "big.int bitwise or negative-negative multi-limb" { -- cgit v1.2.3 From cd3dcc225b52be981b52b71dcdb34ba176f4081b Mon Sep 17 00:00:00 2001 From: Robin Voetter Date: Thu, 23 Sep 2021 06:22:18 +0200 Subject: big ints: only write xor overflow if required --- lib/std/math/big/int.zig | 9 ++++++++- 1 file changed, 8 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/std/math/big/int.zig b/lib/std/math/big/int.zig index fa8a63b67d..b7ea284004 100644 --- a/lib/std/math/big/int.zig +++ b/lib/std/math/big/int.zig @@ -2495,6 +2495,8 @@ fn llsignedand(r: []Limb, a: []const Limb, a_positive: bool, b: []const Limb, b_ // r may alias. // a and b must not be -0. // Returns `true` when the result is positive. +// If the sign of a and b is equal, then r requires at least `max(a.len, b.len)` limbs are required. +// Otherwise, r requires at least `max(a.len, b.len) + 1` limbs. fn llsignedxor(r: []Limb, a: []const Limb, a_positive: bool, b: []const Limb, b_positive: bool) bool { @setRuntimeSafety(debug_safety); assert(a.len != 0 and b.len != 0); @@ -2538,7 +2540,12 @@ fn llsignedxor(r: []Limb, a: []const Limb, a_positive: bool, b: []const Limb, b_ r_carry = @boolToInt(@addWithOverflow(Limb, r[i], r_carry, &r[i])); } - r[i] = r_carry; + // If both inputs don't share the same sign, an extra limb is required. + if (a_positive != b_positive) { + r[i] = r_carry; + } else { + assert(r_carry == 0); + } assert(a_borrow == 0); assert(b_borrow == 0); -- cgit v1.2.3