aboutsummaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/std/math/big/int.zig295
-rw-r--r--lib/std/math/big/int_test.zig143
2 files changed, 409 insertions, 29 deletions
diff --git a/lib/std/math/big/int.zig b/lib/std/math/big/int.zig
index e1b9c94fff..b7ea284004 100644
--- a/lib/std/math/big/int.zig
+++ b/lib/std/math/big/int.zig
@@ -552,36 +552,54 @@ 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(if (b.positive) a.limbs.len else b.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(if (a.positive) b.limbs.len else a.limbs.len);
}
- r.positive = a.positive or b.positive;
}
- /// 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.
@@ -1847,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);
@@ -2236,28 +2258,236 @@ fn llshr(r: []Limb, a: []const Limb, shift: usize) void {
}
}
-fn llor(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 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);
- 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) {
+ // Result is negative.
+ // r = (--a) | b
+ // = ~(-a - 1) | b
+ // = ~(-a - 1) | ~~b
+ // = ~((-a - 1) & ~b)
+ // = -(((-a - 1) & ~b) + 1)
+
+ 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]));
+ }
+
+ // 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.
+ // 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]));
+ }
+
+ assert(a_borrow == 0); // a was 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)
+
+ 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
+
+ // 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.
+ // 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)
+
+ 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.
+
+ // 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.
+ // 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;
}
}
@@ -2265,6 +2495,8 @@ fn lland(r: []Limb, a: []const Limb, b: []const Limb) void {
// 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);
@@ -2308,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);
diff --git a/lib/std/math/big/int_test.zig b/lib/std/math/big/int_test.zig
index 993101c674..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();
@@ -1476,6 +1553,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, -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(i128)) == -0xeeeeeeee00000001);
+}
+
+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();
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-28 02:00:51 +0000