From a73369244471cf15ed8eda624e86c435a5df295f Mon Sep 17 00:00:00 2001 From: Robin Voetter Date: Sun, 26 Sep 2021 07:40:40 +0200 Subject: Update Value.intTrunc to use new big int truncate --- src/value.zig | 24 ++++++++++++++++++------ 1 file changed, 18 insertions(+), 6 deletions(-) (limited to 'src/value.zig') diff --git a/src/value.zig b/src/value.zig index 72fc46ef4c..fa11bb6ddb 100644 --- a/src/value.zig +++ b/src/value.zig @@ -2136,12 +2136,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 { -- cgit v1.2.3 From 69be6ba8eea8e0b64153a0d0676f1b8749df8195 Mon Sep 17 00:00:00 2001 From: Robin Voetter Date: Mon, 27 Sep 2021 04:58:27 +0200 Subject: Comptime wrapping addition/subtraction --- lib/std/math/big/int.zig | 4 ++-- src/value.zig | 53 +++++++++++++++++++++++++++++++----------------- 2 files changed, 36 insertions(+), 21 deletions(-) (limited to 'src/value.zig') diff --git a/lib/std/math/big/int.zig b/lib/std/math/big/int.zig index 59d59a19d3..86d0e22cb8 100644 --- a/lib/std/math/big/int.zig +++ b/lib/std/math/big/int.zig @@ -444,7 +444,7 @@ pub const Mutable = struct { const b_limbs = b.limbs[0..math.min(req_limbs, b.limbs.len)]; if (a.positive != b.positive) { - if (a.positive) { + if (a.positive) { // (a) - (-b) => a + b r.addWrap(a, b.abs(), signedness, bit_count); } else { @@ -1107,7 +1107,7 @@ pub const Mutable = struct { // Zero-extend the result if (req_limbs > r.len) { - mem.set(Limb, r.limbs[r.len .. req_limbs], 0); + mem.set(Limb, r.limbs[r.len..req_limbs], 0); } // Truncate to required number of limbs. diff --git a/src/value.zig b/src/value.zig index fa11bb6ddb..2894840166 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.max(lhs_bigint.limbs.len, rhs_bigint.limbs.len) + 1, + ); + 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. @@ -1714,19 +1721,27 @@ 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.max(lhs_bigint.limbs.len, rhs_bigint.limbs.len) + 1, + ); + 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]; + + 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 integers only; asserts neither operand is undefined. -- cgit v1.2.3 From 8701d8579dafc73856473ad5db73f3d5b4facc56 Mon Sep 17 00:00:00 2001 From: Robin Voetter Date: Fri, 1 Oct 2021 20:57:10 +0200 Subject: Adapt Value.intAddSat and intSubSat to new big int saturating functions --- src/value.zig | 57 ++++++++++++++++++++++++++++++++++----------------------- 1 file changed, 34 insertions(+), 23 deletions(-) (limited to 'src/value.zig') diff --git a/src/value.zig b/src/value.zig index 2894840166..0815c241e4 100644 --- a/src/value.zig +++ b/src/value.zig @@ -1669,7 +1669,7 @@ pub const Value = extern union { const rhs_bigint = rhs.toBigInt(&rhs_space); const limbs = try arena.alloc( std.math.big.Limb, - std.math.max(lhs_bigint.limbs.len, rhs_bigint.limbs.len) + 1, + std.math.max(lhs_bigint.limbs.len, rhs_bigint.limbs.len), ); var result_bigint = BigIntMutable{ .limbs = limbs, .positive = undefined, .len = undefined }; result_bigint.addWrap(lhs_bigint, rhs_bigint, info.signedness, info.bits); @@ -1693,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.max(lhs_bigint.limbs.len, rhs_bigint.limbs.len), + ); + 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. @@ -1730,7 +1736,7 @@ pub const Value = extern union { const rhs_bigint = rhs.toBigInt(&rhs_space); const limbs = try arena.alloc( std.math.big.Limb, - std.math.max(lhs_bigint.limbs.len, rhs_bigint.limbs.len) + 1, + std.math.max(lhs_bigint.limbs.len, rhs_bigint.limbs.len), ); var result_bigint = BigIntMutable{ .limbs = limbs, .positive = undefined, .len = undefined }; result_bigint.subWrap(lhs_bigint, rhs_bigint, info.signedness, info.bits); @@ -1741,7 +1747,6 @@ pub const Value = extern union { } else { return Value.Tag.int_big_negative.create(arena, result_limbs); } - } /// Supports integers only; asserts neither operand is undefined. @@ -1755,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.max(lhs_bigint.limbs.len, rhs_bigint.limbs.len), + ); + 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. -- cgit v1.2.3 From 3dc47b8161f681baef2be776056fa9cc23a8811d Mon Sep 17 00:00:00 2001 From: Robin Voetter Date: Mon, 4 Oct 2021 00:22:03 +0200 Subject: Apply new big int wrap/saturate to Value.zig --- lib/std/math/big/int.zig | 2 +- src/value.zig | 78 ++++++++++++++++++++++++++++++++---------------- 2 files changed, 54 insertions(+), 26 deletions(-) (limited to 'src/value.zig') diff --git a/lib/std/math/big/int.zig b/lib/std/math/big/int.zig index bc19b652d8..4d778f1d22 100644 --- a/lib/std/math/big/int.zig +++ b/lib/std/math/big/int.zig @@ -2738,7 +2738,7 @@ pub fn llcmp(a: []const Limb, b: []const Limb) i8 { /// The result is computed modulo `r.len`. When `r.len >= a.len + b.len`, no overflow occurs. fn llmulaccLong(comptime op: AccOp, r: []Limb, a: []const Limb, b: []const Limb) void { @setRuntimeSafety(debug_safety); - assert(r.len >= a.len + b.len); + assert(r.len >= a.len); assert(a.len >= b.len); var i: usize = 0; diff --git a/src/value.zig b/src/value.zig index 0815c241e4..f5d7b8b05e 100644 --- a/src/value.zig +++ b/src/value.zig @@ -1669,7 +1669,7 @@ pub const Value = extern union { const rhs_bigint = rhs.toBigInt(&rhs_space); const limbs = try arena.alloc( std.math.big.Limb, - std.math.max(lhs_bigint.limbs.len, rhs_bigint.limbs.len), + 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); @@ -1701,7 +1701,7 @@ pub const Value = extern union { const rhs_bigint = rhs.toBigInt(&rhs_space); const limbs = try arena.alloc( std.math.big.Limb, - std.math.max(lhs_bigint.limbs.len, rhs_bigint.limbs.len), + 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); @@ -1736,7 +1736,7 @@ pub const Value = extern union { const rhs_bigint = rhs.toBigInt(&rhs_space); const limbs = try arena.alloc( std.math.big.Limb, - std.math.max(lhs_bigint.limbs.len, rhs_bigint.limbs.len), + 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); @@ -1768,7 +1768,7 @@ pub const Value = extern union { const rhs_bigint = rhs.toBigInt(&rhs_space); const limbs = try arena.alloc( std.math.big.Limb, - std.math.max(lhs_bigint.limbs.len, rhs_bigint.limbs.len), + 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); @@ -1794,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. @@ -1820,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. @@ -2144,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( -- cgit v1.2.3