Merge pull request #9885 from Snektron/big-int-wrapping

Big int wrapping/saturating

1 files changed, 133 insertions, 67 deletions

diff --git a/src/value.zig b/src/value.zig
index 72fc46ef4c..f5d7b8b05e 100644
--- a/src/value.zig
+++ b/src/value.zig
@@ -1660,19 +1660,26 @@ pub const Value = extern union {
         if (ty.isAnyFloat()) {
             return floatAdd(lhs, rhs, ty, arena);
         }
-        const result = try intAdd(lhs, rhs, arena);
 
-        const max = try ty.maxInt(arena, target);
-        if (compare(result, .gt, max, ty)) {
-            @panic("TODO comptime wrapping integer addition");
-        }
+        const info = ty.intInfo(target);
 
-        const min = try ty.minInt(arena, target);
-        if (compare(result, .lt, min, ty)) {
-            @panic("TODO comptime wrapping integer addition");
-        }
+        var lhs_space: Value.BigIntSpace = undefined;
+        var rhs_space: Value.BigIntSpace = undefined;
+        const lhs_bigint = lhs.toBigInt(&lhs_space);
+        const rhs_bigint = rhs.toBigInt(&rhs_space);
+        const limbs = try arena.alloc(
+            std.math.big.Limb,
+            std.math.big.int.calcTwosCompLimbCount(info.bits),
+        );
+        var result_bigint = BigIntMutable{ .limbs = limbs, .positive = undefined, .len = undefined };
+        result_bigint.addWrap(lhs_bigint, rhs_bigint, info.signedness, info.bits);
+        const result_limbs = result_bigint.limbs[0..result_bigint.len];
 
-        return result;
+        if (result_bigint.positive) {
+            return Value.Tag.int_big_positive.create(arena, result_limbs);
+        } else {
+            return Value.Tag.int_big_negative.create(arena, result_limbs);
+        }
     }
 
     /// Supports integers only; asserts neither operand is undefined.
@@ -1686,19 +1693,25 @@ pub const Value = extern union {
         assert(!lhs.isUndef());
         assert(!rhs.isUndef());
 
-        const result = try intAdd(lhs, rhs, arena);
+        const info = ty.intInfo(target);
 
-        const max = try ty.maxInt(arena, target);
-        if (compare(result, .gt, max, ty)) {
-            return max;
-        }
+        var lhs_space: Value.BigIntSpace = undefined;
+        var rhs_space: Value.BigIntSpace = undefined;
+        const lhs_bigint = lhs.toBigInt(&lhs_space);
+        const rhs_bigint = rhs.toBigInt(&rhs_space);
+        const limbs = try arena.alloc(
+            std.math.big.Limb,
+            std.math.big.int.calcTwosCompLimbCount(info.bits),
+        );
+        var result_bigint = BigIntMutable{ .limbs = limbs, .positive = undefined, .len = undefined };
+        result_bigint.addSat(lhs_bigint, rhs_bigint, info.signedness, info.bits);
+        const result_limbs = result_bigint.limbs[0..result_bigint.len];
 
-        const min = try ty.minInt(arena, target);
-        if (compare(result, .lt, min, ty)) {
-            return min;
+        if (result_bigint.positive) {
+            return Value.Tag.int_big_positive.create(arena, result_limbs);
+        } else {
+            return Value.Tag.int_big_negative.create(arena, result_limbs);
         }
-
-        return result;
     }
 
     /// Supports both floats and ints; handles undefined.
@@ -1714,19 +1727,26 @@ pub const Value = extern union {
         if (ty.isAnyFloat()) {
             return floatSub(lhs, rhs, ty, arena);
         }
-        const result = try intSub(lhs, rhs, arena);
 
-        const max = try ty.maxInt(arena, target);
-        if (compare(result, .gt, max, ty)) {
-            @panic("TODO comptime wrapping integer subtraction");
-        }
+        const info = ty.intInfo(target);
 
-        const min = try ty.minInt(arena, target);
-        if (compare(result, .lt, min, ty)) {
-            @panic("TODO comptime wrapping integer subtraction");
-        }
+        var lhs_space: Value.BigIntSpace = undefined;
+        var rhs_space: Value.BigIntSpace = undefined;
+        const lhs_bigint = lhs.toBigInt(&lhs_space);
+        const rhs_bigint = rhs.toBigInt(&rhs_space);
+        const limbs = try arena.alloc(
+            std.math.big.Limb,
+            std.math.big.int.calcTwosCompLimbCount(info.bits),
+        );
+        var result_bigint = BigIntMutable{ .limbs = limbs, .positive = undefined, .len = undefined };
+        result_bigint.subWrap(lhs_bigint, rhs_bigint, info.signedness, info.bits);
+        const result_limbs = result_bigint.limbs[0..result_bigint.len];
 
-        return result;
+        if (result_bigint.positive) {
+            return Value.Tag.int_big_positive.create(arena, result_limbs);
+        } else {
+            return Value.Tag.int_big_negative.create(arena, result_limbs);
+        }
     }
 
     /// Supports integers only; asserts neither operand is undefined.
@@ -1740,19 +1760,25 @@ pub const Value = extern union {
         assert(!lhs.isUndef());
         assert(!rhs.isUndef());
 
-        const result = try intSub(lhs, rhs, arena);
+        const info = ty.intInfo(target);
 
-        const max = try ty.maxInt(arena, target);
-        if (compare(result, .gt, max, ty)) {
-            return max;
-        }
+        var lhs_space: Value.BigIntSpace = undefined;
+        var rhs_space: Value.BigIntSpace = undefined;
+        const lhs_bigint = lhs.toBigInt(&lhs_space);
+        const rhs_bigint = rhs.toBigInt(&rhs_space);
+        const limbs = try arena.alloc(
+            std.math.big.Limb,
+            std.math.big.int.calcTwosCompLimbCount(info.bits),
+        );
+        var result_bigint = BigIntMutable{ .limbs = limbs, .positive = undefined, .len = undefined };
+        result_bigint.subSat(lhs_bigint, rhs_bigint, info.signedness, info.bits);
+        const result_limbs = result_bigint.limbs[0..result_bigint.len];
 
-        const min = try ty.minInt(arena, target);
-        if (compare(result, .lt, min, ty)) {
-            return min;
+        if (result_bigint.positive) {
+            return Value.Tag.int_big_positive.create(arena, result_limbs);
+        } else {
+            return Value.Tag.int_big_negative.create(arena, result_limbs);
         }
-
-        return result;
     }
 
     /// Supports both floats and ints; handles undefined.
@@ -1768,19 +1794,31 @@ pub const Value = extern union {
         if (ty.isAnyFloat()) {
             return floatMul(lhs, rhs, ty, arena);
         }
-        const result = try intMul(lhs, rhs, arena);
 
-        const max = try ty.maxInt(arena, target);
-        if (compare(result, .gt, max, ty)) {
-            @panic("TODO comptime wrapping integer multiplication");
-        }
+        const info = ty.intInfo(target);
 
-        const min = try ty.minInt(arena, target);
-        if (compare(result, .lt, min, ty)) {
-            @panic("TODO comptime wrapping integer multiplication");
-        }
+        var lhs_space: Value.BigIntSpace = undefined;
+        var rhs_space: Value.BigIntSpace = undefined;
+        const lhs_bigint = lhs.toBigInt(&lhs_space);
+        const rhs_bigint = rhs.toBigInt(&rhs_space);
+        const limbs = try arena.alloc(
+            std.math.big.Limb,
+            std.math.big.int.calcTwosCompLimbCount(info.bits),
+        );
+        var result_bigint = BigIntMutable{ .limbs = limbs, .positive = undefined, .len = undefined };
+        var limbs_buffer = try arena.alloc(
+            std.math.big.Limb,
+            std.math.big.int.calcMulWrapLimbsBufferLen(info.bits, lhs_bigint.limbs.len, rhs_bigint.limbs.len, 1),
+        );
+        defer arena.free(limbs_buffer);
+        result_bigint.mulWrap(lhs_bigint, rhs_bigint, info.signedness, info.bits, limbs_buffer, arena);
+        const result_limbs = result_bigint.limbs[0..result_bigint.len];
 
-        return result;
+        if (result_bigint.positive) {
+            return Value.Tag.int_big_positive.create(arena, result_limbs);
+        } else {
+            return Value.Tag.int_big_negative.create(arena, result_limbs);
+        }
     }
 
     /// Supports integers only; asserts neither operand is undefined.
@@ -1794,19 +1832,35 @@ pub const Value = extern union {
         assert(!lhs.isUndef());
         assert(!rhs.isUndef());
 
-        const result = try intMul(lhs, rhs, arena);
+        const info = ty.intInfo(target);
 
-        const max = try ty.maxInt(arena, target);
-        if (compare(result, .gt, max, ty)) {
-            return max;
-        }
+        var lhs_space: Value.BigIntSpace = undefined;
+        var rhs_space: Value.BigIntSpace = undefined;
+        const lhs_bigint = lhs.toBigInt(&lhs_space);
+        const rhs_bigint = rhs.toBigInt(&rhs_space);
+        const limbs = try arena.alloc(
+            std.math.big.Limb,
+            std.math.max(
+                // For the saturate
+                std.math.big.int.calcTwosCompLimbCount(info.bits),
+                lhs_bigint.limbs.len + rhs_bigint.limbs.len,
+            ),
+        );
+        var result_bigint = BigIntMutable{ .limbs = limbs, .positive = undefined, .len = undefined };
+        var limbs_buffer = try arena.alloc(
+            std.math.big.Limb,
+            std.math.big.int.calcMulLimbsBufferLen(lhs_bigint.limbs.len, rhs_bigint.limbs.len, 1),
+        );
+        defer arena.free(limbs_buffer);
+        result_bigint.mul(lhs_bigint, rhs_bigint, limbs_buffer, arena);
+        result_bigint.saturate(result_bigint.toConst(), info.signedness, info.bits);
+        const result_limbs = result_bigint.limbs[0..result_bigint.len];
 
-        const min = try ty.minInt(arena, target);
-        if (compare(result, .lt, min, ty)) {
-            return min;
+        if (result_bigint.positive) {
+            return Value.Tag.int_big_positive.create(arena, result_limbs);
+        } else {
+            return Value.Tag.int_big_negative.create(arena, result_limbs);
         }
-
-        return result;
     }
 
     /// Supports both floats and ints; handles undefined.
@@ -2118,7 +2172,7 @@ pub const Value = extern union {
         const rhs_bigint = rhs.toBigInt(&rhs_space);
         const limbs = try allocator.alloc(
             std.math.big.Limb,
-            lhs_bigint.limbs.len + rhs_bigint.limbs.len + 1,
+            lhs_bigint.limbs.len + rhs_bigint.limbs.len,
         );
         var result_bigint = BigIntMutable{ .limbs = limbs, .positive = undefined, .len = undefined };
         var limbs_buffer = try allocator.alloc(
@@ -2136,12 +2190,24 @@ pub const Value = extern union {
         }
     }
 
-    pub fn intTrunc(val: Value, arena: *Allocator, bits: u16) !Value {
-        const x = val.toUnsignedInt(); // TODO: implement comptime truncate on big ints
-        if (bits == 64) return val;
-        const mask = (@as(u64, 1) << @intCast(u6, bits)) - 1;
-        const truncated = x & mask;
-        return Tag.int_u64.create(arena, truncated);
+    pub fn intTrunc(val: Value, allocator: *Allocator, signedness: std.builtin.Signedness, bits: u16) !Value {
+        var val_space: Value.BigIntSpace = undefined;
+        const val_bigint = val.toBigInt(&val_space);
+
+        const limbs = try allocator.alloc(
+            std.math.big.Limb,
+            std.math.big.int.calcTwosCompLimbCount(bits),
+        );
+        var result_bigint = BigIntMutable{ .limbs = limbs, .positive = undefined, .len = undefined };
+
+        result_bigint.truncate(val_bigint, signedness, bits);
+        const result_limbs = result_bigint.limbs[0..result_bigint.len];
+
+        if (result_bigint.positive) {
+            return Value.Tag.int_big_positive.create(allocator, result_limbs);
+        } else {
+            return Value.Tag.int_big_negative.create(allocator, result_limbs);
+        }
     }
 
     pub fn shl(lhs: Value, rhs: Value, allocator: *Allocator) !Value {