Commit ed284c1f98
Changed files (3)
lib
std
math
src
codegen
lib/std/math/big/int.zig
@@ -1755,119 +1755,60 @@ pub const Mutable = struct {
y.shiftRight(y.toConst(), norm_shift);
}
- /// If a is positive, this passes through to truncate.
- /// If a is negative, then r is set to positive with the bit pattern ~(a - 1).
- /// r may alias a.
- ///
- /// Asserts `r` has enough storage to store the result.
- /// The upper bound is `calcTwosCompLimbCount(a.len)`.
- pub fn convertToTwosComplement(r: *Mutable, a: Const, signedness: Signedness, bit_count: usize) void {
- if (a.positive) {
- r.truncate(a, signedness, bit_count);
- return;
- }
-
- const req_limbs = calcTwosCompLimbCount(bit_count);
- if (req_limbs == 0 or a.eqlZero()) {
- r.set(0);
- return;
- }
-
- const bit = @as(Log2Limb, @truncate(bit_count - 1));
- const signmask = @as(Limb, 1) << bit;
- const mask = (signmask << 1) -% 1;
-
- r.addScalar(a.abs(), -1);
- if (req_limbs > r.len) {
- @memset(r.limbs[r.len..req_limbs], 0);
- }
-
- assert(r.limbs.len >= req_limbs);
- r.len = req_limbs;
-
- llnot(r.limbs[0..r.len]);
- r.limbs[r.len - 1] &= mask;
- r.normalize(r.len);
- }
-
/// Truncate an integer to a number of bits, following 2s-complement semantics.
- /// r may alias a.
+ /// `r` may alias `a`.
///
- /// Asserts `r` has enough storage to store the result.
+ /// Asserts `r` has enough storage to compute the result.
/// The upper bound is `calcTwosCompLimbCount(a.len)`.
pub fn truncate(r: *Mutable, a: Const, signedness: Signedness, bit_count: usize) void {
- const req_limbs = calcTwosCompLimbCount(bit_count);
- const abs_trunc_a: Const = .{
- .positive = true,
- .limbs = a.limbs[0..@min(a.limbs.len, req_limbs)],
- };
-
// Handle 0-bit integers.
- if (req_limbs == 0 or abs_trunc_a.eqlZero()) {
+ if (bit_count == 0) {
+ @branchHint(.unlikely);
r.set(0);
return;
}
- const bit = @as(Log2Limb, @truncate(bit_count - 1));
- const signmask = @as(Limb, 1) << bit; // 0b0..010...0 where 1 is the sign bit.
- const mask = (signmask << 1) -% 1; // 0b0..01..1 where the leftmost 1 is the sign bit.
-
- if (!a.positive) {
- // Convert the integer from sign-magnitude into twos-complement.
- // -x = ~(x - 1)
- // Note, we simply take req_limbs * @bitSizeOf(Limb) as the
- // target bit count.
-
- r.addScalar(abs_trunc_a, -1);
+ const max_limbs = calcTwosCompLimbCount(bit_count);
+ const sign_bit = @as(Limb, 1) << @truncate(bit_count - 1);
+ const mask = @as(Limb, maxInt(Limb)) >> @truncate(-%bit_count);
+
+ // Guess whether the result will have the same sign as `a`.
+ // * If the result will be signed zero, the guess is `true`.
+ // * If the result will be the minimum signed integer, the guess is `false`.
+ // * If the result will be unsigned zero, the guess is `a.positive`.
+ // * Otherwise the guess is correct.
+ const same_sign_guess = switch (signedness) {
+ .signed => max_limbs > a.limbs.len or a.limbs[max_limbs - 1] & sign_bit == 0,
+ .unsigned => a.positive,
+ };
- // Zero-extend the result
- @memset(r.limbs[r.len..req_limbs], 0);
- r.len = req_limbs;
-
- // Without truncating, we can already peek at the sign bit of the result here.
- // Note that it will be 0 if the result is negative, as we did not apply the flip here.
- // If the result is negative, we have
- // -(-x & mask)
- // = ~(~(x - 1) & mask) + 1
- // = ~(~((x - 1) | ~mask)) + 1
- // = ((x - 1) | ~mask)) + 1
- // Note, this is only valid for the target bits and not the upper bits
- // of the most significant limb. Those still need to be cleared.
- // Also note that `mask` is zero for all other bits, reducing to the identity.
- // This means that we still need to use & mask to clear off the upper bits.
-
- if (signedness == .signed and r.limbs[r.len - 1] & signmask == 0) {
- // Re-add the one and negate to get the result.
- r.limbs[r.len - 1] &= mask;
- // Note, addition cannot require extra limbs here as we did a subtraction before.
- r.addScalar(r.toConst(), 1);
- r.normalize(r.len);
- r.positive = false;
- } else {
- llnot(r.limbs[0..r.len]);
- r.limbs[r.len - 1] &= mask;
- r.normalize(r.len);
- }
- } else {
+ const abs_trunc_a: Const = .{
+ .positive = true,
+ .limbs = a.limbs[0..llnormalize(a.limbs[0..@min(a.limbs.len, max_limbs)])],
+ };
+ if (same_sign_guess or abs_trunc_a.eqlZero()) {
+ // One of the following is true:
+ // * The result is zero.
+ // * The result is non-zero and has the same sign as `a`.
r.copy(abs_trunc_a);
- // If the integer fits within target bits, no wrapping is required.
- if (r.len < req_limbs) return;
-
- r.limbs[r.len - 1] &= mask;
+ if (max_limbs <= r.len) r.limbs[max_limbs - 1] &= mask;
r.normalize(r.len);
-
- if (signedness == .signed and r.limbs[r.len - 1] & signmask != 0) {
- // Convert 2s-complement back to sign-magnitude.
- // Sign-extend the upper bits so that they are inverted correctly.
- r.limbs[r.len - 1] |= ~mask;
- llnot(r.limbs[0..r.len]);
-
- // Note, can only overflow if r holds 0xFFF...F which can only happen if
- // a holds 0.
- r.addScalar(r.toConst(), 1);
-
- r.positive = false;
- }
+ r.positive = a.positive or r.eqlZero();
+ } else {
+ // One of the following is true:
+ // * The result is the minimum signed integer.
+ // * The result is unsigned zero.
+ // * The result is non-zero and has the opposite sign as `a`.
+ r.addScalar(abs_trunc_a, -1);
+ llnot(r.limbs[0..r.len]);
+ @memset(r.limbs[r.len..max_limbs], maxInt(Limb));
+ r.limbs[max_limbs - 1] &= mask;
+ r.normalize(max_limbs);
+ r.positive = switch (signedness) {
+ // The only value with the sign bit still set is the minimum signed integer.
+ .signed => !a.positive and r.limbs[max_limbs - 1] & sign_bit == 0,
+ .unsigned => !a.positive or r.eqlZero(),
+ };
}
}
lib/std/math/big/int_test.zig
@@ -1020,7 +1020,7 @@ test "mul large" {
// Generate a number that's large enough to cross the thresholds for the use
// of subquadratic algorithms
for (a.limbs) |*p| {
- p.* = std.math.maxInt(Limb);
+ p.* = maxInt(Limb);
}
a.setMetadata(true, 50);
@@ -1104,7 +1104,7 @@ test "mulWrap large" {
// Generate a number that's large enough to cross the thresholds for the use
// of subquadratic algorithms
for (a.limbs) |*p| {
- p.* = std.math.maxInt(Limb);
+ p.* = maxInt(Limb);
}
a.setMetadata(true, 50);
@@ -1961,23 +1961,78 @@ test "truncate to mutable with fewer limbs" {
.positive = undefined,
};
res.truncate(.{ .positive = true, .limbs = &.{ 0, 1 } }, .unsigned, @bitSizeOf(Limb));
- try testing.expect(res.eqlZero());
+ try testing.expect(res.positive and res.len == 1 and res.limbs[0] == 0);
res.truncate(.{ .positive = true, .limbs = &.{ 0, 1 } }, .signed, @bitSizeOf(Limb));
- try testing.expect(res.eqlZero());
+ try testing.expect(res.positive and res.len == 1 and res.limbs[0] == 0);
res.truncate(.{ .positive = false, .limbs = &.{ 0, 1 } }, .unsigned, @bitSizeOf(Limb));
- try testing.expect(res.eqlZero());
+ try testing.expect(res.positive and res.len == 1 and res.limbs[0] == 0);
res.truncate(.{ .positive = false, .limbs = &.{ 0, 1 } }, .signed, @bitSizeOf(Limb));
- try testing.expect(res.eqlZero());
- res.truncate(.{ .positive = true, .limbs = &.{ std.math.maxInt(Limb), 1 } }, .unsigned, @bitSizeOf(Limb));
- try testing.expect(res.toConst().orderAgainstScalar(std.math.maxInt(Limb)).compare(.eq));
- res.truncate(.{ .positive = true, .limbs = &.{ std.math.maxInt(Limb), 1 } }, .signed, @bitSizeOf(Limb));
+ try testing.expect(res.positive and res.len == 1 and res.limbs[0] == 0);
+ res.truncate(.{ .positive = true, .limbs = &.{ maxInt(Limb), 1 } }, .unsigned, @bitSizeOf(Limb));
+ try testing.expect(res.toConst().orderAgainstScalar(maxInt(Limb)).compare(.eq));
+ res.truncate(.{ .positive = true, .limbs = &.{ maxInt(Limb), 1 } }, .signed, @bitSizeOf(Limb));
try testing.expect(res.toConst().orderAgainstScalar(-1).compare(.eq));
- res.truncate(.{ .positive = false, .limbs = &.{ std.math.maxInt(Limb), 1 } }, .unsigned, @bitSizeOf(Limb));
+ res.truncate(.{ .positive = false, .limbs = &.{ maxInt(Limb), 1 } }, .unsigned, @bitSizeOf(Limb));
try testing.expect(res.toConst().orderAgainstScalar(1).compare(.eq));
- res.truncate(.{ .positive = false, .limbs = &.{ std.math.maxInt(Limb), 1 } }, .signed, @bitSizeOf(Limb));
+ res.truncate(.{ .positive = false, .limbs = &.{ maxInt(Limb), 1 } }, .signed, @bitSizeOf(Limb));
try testing.expect(res.toConst().orderAgainstScalar(1).compare(.eq));
}
+test "truncate value that normalizes after being masked" {
+ var res_limbs: [2]Limb = undefined;
+ var res: Mutable = .{
+ .limbs = &res_limbs,
+ .len = undefined,
+ .positive = undefined,
+ };
+ res.truncate(.{ .positive = true, .limbs = &.{ 0, 2 } }, .signed, 1 + @bitSizeOf(Limb));
+ try testing.expect(res.positive and res.len == 1 and res.limbs[0] == 0);
+ res.truncate(.{ .positive = true, .limbs = &.{ 1, 2 } }, .signed, 1 + @bitSizeOf(Limb));
+ try testing.expect(res.toConst().orderAgainstScalar(1).compare(.eq));
+}
+
+test "truncate to zero" {
+ var res_limbs: [1]Limb = undefined;
+ var res: Mutable = .{
+ .limbs = &res_limbs,
+ .len = undefined,
+ .positive = undefined,
+ };
+ res.truncate(.{ .positive = true, .limbs = &.{0} }, .signed, @bitSizeOf(Limb));
+ try testing.expect(res.positive and res.len == 1 and res.limbs[0] == 0);
+ res.truncate(.{ .positive = false, .limbs = &.{0} }, .signed, @bitSizeOf(Limb));
+ try testing.expect(res.positive and res.len == 1 and res.limbs[0] == 0);
+ res.truncate(.{ .positive = true, .limbs = &.{0} }, .unsigned, @bitSizeOf(Limb));
+ try testing.expect(res.positive and res.len == 1 and res.limbs[0] == 0);
+ res.truncate(.{ .positive = false, .limbs = &.{0} }, .unsigned, @bitSizeOf(Limb));
+ try testing.expect(res.positive and res.len == 1 and res.limbs[0] == 0);
+ res.truncate(.{ .positive = true, .limbs = &.{ 0, 1 } }, .signed, @bitSizeOf(Limb));
+ try testing.expect(res.positive and res.len == 1 and res.limbs[0] == 0);
+ res.truncate(.{ .positive = false, .limbs = &.{ 0, 1 } }, .signed, @bitSizeOf(Limb));
+ try testing.expect(res.positive and res.len == 1 and res.limbs[0] == 0);
+ res.truncate(.{ .positive = true, .limbs = &.{ 0, 1 } }, .unsigned, @bitSizeOf(Limb));
+ try testing.expect(res.positive and res.len == 1 and res.limbs[0] == 0);
+ res.truncate(.{ .positive = false, .limbs = &.{ 0, 1 } }, .unsigned, @bitSizeOf(Limb));
+ try testing.expect(res.positive and res.len == 1 and res.limbs[0] == 0);
+}
+
+test "truncate to minimum signed integer" {
+ var res_limbs: [1]Limb = undefined;
+ var res: Mutable = .{
+ .limbs = &res_limbs,
+ .len = undefined,
+ .positive = undefined,
+ };
+ res.truncate(.{ .positive = true, .limbs = &.{1 << @bitSizeOf(Limb) - 1} }, .signed, @bitSizeOf(Limb));
+ try testing.expect(res.toConst().orderAgainstScalar(-1 << @bitSizeOf(Limb) - 1).compare(.eq));
+ res.truncate(.{ .positive = false, .limbs = &.{1 << @bitSizeOf(Limb) - 1} }, .signed, @bitSizeOf(Limb));
+ try testing.expect(res.toConst().orderAgainstScalar(-1 << @bitSizeOf(Limb) - 1).compare(.eq));
+ res.truncate(.{ .positive = true, .limbs = &.{1 << @bitSizeOf(Limb) - 1} }, .unsigned, @bitSizeOf(Limb));
+ try testing.expect(res.toConst().orderAgainstScalar(1 << @bitSizeOf(Limb) - 1).compare(.eq));
+ res.truncate(.{ .positive = false, .limbs = &.{1 << @bitSizeOf(Limb) - 1} }, .unsigned, @bitSizeOf(Limb));
+ try testing.expect(res.toConst().orderAgainstScalar(1 << @bitSizeOf(Limb) - 1).compare(.eq));
+}
+
test "saturate single signed positive" {
var a = try Managed.initSet(testing.allocator, 0xBBBB_BBBB);
defer a.deinit();
src/codegen/c.zig
@@ -8175,7 +8175,7 @@ fn formatIntLiteral(
try writer.writeAll(string);
} else {
try data.ctype.renderLiteralPrefix(writer, data.kind, ctype_pool);
- wrap.convertToTwosComplement(int, data.int_info.signedness, c_bits);
+ wrap.truncate(int, .unsigned, c_bits);
@memset(wrap.limbs[wrap.len..], 0);
wrap.len = wrap.limbs.len;
const limbs_per_c_limb = @divExact(wrap.len, c_limb_info.count);
@@ -8207,7 +8207,6 @@ fn formatIntLiteral(
c_limb_int_info.signedness = .signed;
c_limb_ctype = c_limb_info.ctype.toSigned();
- c_limb_mut.positive = wrap.positive;
c_limb_mut.truncate(
c_limb_mut.toConst(),
.signed,