Commit 351e4f07ce
Changed files (2)
lib
std
math
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;
}
}
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" {