tiny.preserves.integer_mod

1//! Signed integers of any size, as data values carry them. An integer value needs equality, a total2//! order, a hash and an exact round trip through the bytes the binary syntax writes. Most integers3//! fit in a machine word, so a program should pay for heap storage only when a number needs it.4//!5//! Data can carry integers of any size, and every fixed-width Zig integer, the 128-bit ones6//! included, has a largest value. The unsigned 128-bit range reaches one bit past the signed one,7//! so a number in that gap fits the unsigned type and exceeds the signed one. One number has many8//! byte spellings that differ only by extra leading `0x00` or `0xff` bytes, and byte equality needs9//! one spelling per number.10//!11//! The [Preserves](https://preserves.dev/) data language has signed integers of unbounded size, and12//! the package's binary syntax writes each as its shortest big-endian two's-complement bytes and13//! rejects any longer spelling.14//!15//! A number takes one of three representations (*tier*): 128 signed bits when it fits, 128 unsigned16//! bits when it is larger than that but still fits, and bytes otherwise. A number too large for 12817//! bits is stored as its shortest big-endian two's-complement bytes (*canonical bytes*), the same18//! bytes the binary syntax writes. Only that third representation allocates, so freeing and copying19//! cost nothing for every other integer. Equality, order and hash assume each number has one20//! representation, the smallest that holds it: two values in different representations are unequal.21//! The constructors `fromI128`, `fromU128` and `fromCanonicalBytes` keep that rule, and a signed22//! integer (`SignedInteger`) written directly through its representation field (`repr`) can break23//! it with nothing to detect it. Across representations the order is numeric: negative large24//! numbers, then 128-bit signed, then 128-bit unsigned, then positive large numbers.25const std = @import("std");26const Allocator = std.mem.Allocator;2728/// The error `fromCanonicalBytes` returns when its bytes are longer than the shortest spelling of29/// their number. Code that reads integers from bytes handles this error, as the binary and text30/// readers do.31pub const DecodeError = error{NonCanonicalInteger};32/// The error the `to` conversions return when the number does not fit the requested type. Code that33/// reads an integer as a fixed-width Zig integer handles this error when the number is too large or34/// has the wrong sign.35pub const RangeError = error{OutOfRange};3637/// Names the three ways a number is stored: `i128` for 128 signed bits, `u128` for 128 unsigned38/// bits above the signed maximum, and `big` for heap bytes. Code that switches on how an integer is39/// stored reads this, as the text reader's tests do.40pub const Tier = enum { i128, u128, big };4142/// A signed integer of any size, stored in the smallest of three representations that holds it.43/// Every integer in a value is one of these, so every reader, writer and comparison of integers44/// uses it. A value built by `fromCanonicalBytes` or `clone` owns its heap bytes, and `deinit`45/// frees them. Equality and order assume the smallest representation, so a value written directly46/// through `repr` has to keep it.47pub const SignedInteger = struct {48    /// The number in one of its three representations. A value set here directly has to use the49    /// smallest representation that holds the number, because nothing checks it.50    repr: Repr,5152    /// The number stored as 128 signed bits, 128 unsigned bits or heap bytes, tagged by which. Code53    /// that switches on how an integer is stored reads this.54    pub const Repr = union(Tier) {55        /// The number when it fits in 128 signed bits.56        i128: i128,57        /// The number when it is above the largest 128-bit signed integer and fits in 128 unsigned58        /// bits.59        u128: u128,60        /// The number's shortest big-endian two's-complement bytes, for a number outside both61        /// 128-bit ranges. These bytes are at least 17 long.62        big: []const u8,63    };6465    /// Returns zero, stored in 128 signed bits. Code that needs a zero integer calls it.66    pub fn zero() SignedInteger {67        return .{ .repr = .{ .i128 = 0 } };68    }6970    /// Returns `v`, stored in 128 signed bits. Readers and constructors call it for any integer71    /// that fits in 128 signed bits.72    pub fn fromI128(v: i128) SignedInteger {73        return .{ .repr = .{ .i128 = v } };74    }7576    /// Returns `v`, stored in 128 signed bits when it fits there and in 128 unsigned bits77    /// otherwise. Readers call it for a non-negative integer read as 128 unsigned bits.78    pub fn fromU128(v: u128) SignedInteger {79        const limit: u128 = @intCast(std.math.maxInt(i128));80        if (v <= limit) {81            return .{ .repr = .{ .i128 = @intCast(v) } };82        }83        return .{ .repr = .{ .u128 = v } };84    }8586    /// Reads a number from its shortest big-endian two's-complement bytes. The binary and text87    /// readers call it for integers too large for fixed-width parsing. Empty bytes are zero, up to88    /// 16 bytes give a 128-bit signed number, and 17 bytes of a number that fits 128 unsigned bits89    /// give a 128-bit unsigned number. Numbers with more bytes keep a copy of the bytes from90    /// `allocator`, which `deinit` frees. The call returns `error.NonCanonicalInteger` for any91    /// spelling longer than the shortest.92    pub fn fromCanonicalBytes(allocator: Allocator, bytes: []const u8) !SignedInteger {93        if (!isCanonicalBytes(bytes)) return DecodeError.NonCanonicalInteger;94        if (bytes.len == 0) return zero();95        if (bytes.len <= 16) return fromI128(decodeI128Bytes(bytes));96        if (bytes.len == 17 and bytes[0] == 0x00 and (bytes[1] & 0x80) != 0) {97            return .{ .repr = .{ .u128 = decode16BytesAsU128(bytes[1..]) } };98        }99        return .{ .repr = .{ .big = try allocator.dupe(u8, bytes) } };100    }101102    /// Frees the heap bytes of a number too large for 128 bits, and does nothing for any other103    /// number. `Value.deinit` and `freeValueDeep` call it for every integer they free. The value is104    /// undefined afterward.105    pub fn deinit(self: *SignedInteger, allocator: Allocator) void {106        switch (self.repr) {107            .big => |b| if (b.len != 0) allocator.free(b),108            else => {},109        }110        self.* = undefined;111    }112113    /// Returns a copy that owns its storage, copying the heap bytes of a large number with114    /// `allocator`. `cloneValueDeep` calls it for every integer it copies. A number that fits in115    /// 128 bits is copied without allocating.116    pub fn clone(self: SignedInteger, allocator: Allocator) !SignedInteger {117        return switch (self.repr) {118            .i128 => |v| fromI128(v),119            .u128 => |v| .{ .repr = .{ .u128 = v } },120            .big => |b| .{ .repr = .{ .big = try allocator.dupe(u8, b) } },121        };122    }123124    /// Returns a new allocation from `allocator` holding the number's shortest big-endian125    /// two's-complement bytes, which the caller frees. The binary writer calls it for the bytes of126    /// each integer it writes. Zero gives an empty slice.127    pub fn toCanonicalBytes(self: SignedInteger, allocator: Allocator) ![]u8 {128        return switch (self.repr) {129            .i128 => |v| try encodeI128(allocator, v),130            .u128 => |v| try encodeU128(allocator, v),131            .big => |b| try allocator.dupe(u8, b),132        };133    }134135    /// Returns the number when it is stored in 128 signed bits, and `error.OutOfRange` otherwise.136    /// Code that needs the number as a Zig `i128` calls it, as the package's tests do.137    pub fn toI128(self: SignedInteger) RangeError!i128 {138        return switch (self.repr) {139            .i128 => |v| v,140            .u128, .big => RangeError.OutOfRange,141        };142    }143144    /// Returns the number when it is zero or positive and fits in 128 unsigned bits, and145    /// `error.OutOfRange` otherwise. Code that needs a 128-bit unsigned integer calls it.146    pub fn toU128(self: SignedInteger) RangeError!u128 {147        return switch (self.repr) {148            .i128 => |v| if (v < 0) RangeError.OutOfRange else @intCast(v),149            .u128 => |v| v,150            .big => RangeError.OutOfRange,151        };152    }153154    /// Returns the number when it fits in 64 signed bits, and `error.OutOfRange` otherwise. Code155    /// that reads a field it expects to fit in 64 bits calls it for an `i64`.156    pub fn toI64(self: SignedInteger) RangeError!i64 {157        const v = try self.toI128();158        if (v < std.math.minInt(i64) or v > std.math.maxInt(i64)) return RangeError.OutOfRange;159        return @intCast(v);160    }161162    /// Returns the number clamped to the 64-bit signed range: the largest `i64` for any number163    /// above it and the smallest for any number below. The JSON writer calls it to print an integer164    /// too large for 128 bits. The call never fails.165    pub fn toI64Lossy(self: SignedInteger) i64 {166        return switch (self.repr) {167            .i128 => |v| blk: {168                if (v > std.math.maxInt(i64)) break :blk std.math.maxInt(i64);169                if (v < std.math.minInt(i64)) break :blk std.math.minInt(i64);170                break :blk @intCast(v);171            },172            .u128 => std.math.maxInt(i64),173            .big => |b| if (b.len > 0 and (b[0] & 0x80) != 0) std.math.minInt(i64) else std.math.maxInt(i64),174        };175    }176177    /// Returns the number when it is zero or positive and fits in 64 unsigned bits, and178    /// `error.OutOfRange` otherwise. Code that reads a count or a size calls it for a `u64`.179    pub fn toU64(self: SignedInteger) RangeError!u64 {180        const v = try self.toU128();181        if (v > std.math.maxInt(u64)) return RangeError.OutOfRange;182        return @intCast(v);183    }184185    /// Returns whether the number is zero. Code that tests for zero calls it. Only a zero stored in186    /// 128 signed bits counts, so a zero written directly into another representation reads as187    /// nonzero.188    pub fn isZero(self: SignedInteger) bool {189        return switch (self.repr) {190            .i128 => |v| v == 0,191            .u128, .big => false,192        };193    }194195    /// Returns whether the number is below zero. Code that needs the sign calls it.196    pub fn isNegative(self: SignedInteger) bool {197        return switch (self.repr) {198            .i128 => |v| v < 0,199            .u128 => false,200            .big => |b| b.len > 0 and (b[0] & 0x80) != 0,201        };202    }203204    /// Returns whether two integers are equal. `Value.eql` calls it for two integers. Integers in205    /// different representations are never equal, so the call is exact only when both use the206    /// smallest representation that holds their number.207    pub fn eql(a: SignedInteger, b: SignedInteger) bool {208        return switch (a.repr) {209            .i128 => |av| switch (b.repr) {210                .i128 => |bv| av == bv,211                else => false,212            },213            .u128 => |av| switch (b.repr) {214                .u128 => |bv| av == bv,215                else => false,216            },217            .big => |av| switch (b.repr) {218                .big => |bv| std.mem.eql(u8, av, bv),219                else => false,220            },221        };222    }223224    /// Returns the numeric order of two integers. `Value.compare` calls it for two integers. Large225    /// numbers compare by sign, then by byte length, then byte by byte. The order across226    /// representations is exact only when both integers use the smallest representation that holds227    /// their number.228    pub fn order(a: SignedInteger, b: SignedInteger) std.math.Order {229        return switch (a.repr) {230            .i128 => |av| switch (b.repr) {231                .i128 => |bv| std.math.order(av, bv),232                .u128 => .lt,233                .big => |bv| if (bigIsNegative(bv)) .gt else .lt,234            },235            .u128 => |av| switch (b.repr) {236                .i128 => .gt,237                .u128 => |bv| std.math.order(av, bv),238                .big => |bv| if (bigIsNegative(bv)) .gt else .lt,239            },240            .big => |av| switch (b.repr) {241                .i128, .u128 => if (bigIsNegative(av)) .lt else .gt,242                .big => |bv| compareBig(av, bv),243            },244        };245    }246247    /// Returns whether `bytes` are the shortest big-endian two's-complement spelling of their248    /// number. The binary reader calls it before reading an integer, so a longer spelling is249    /// rejected. Empty bytes spell zero. A lone `0x00` byte, a leading `0x00` before a byte whose250    /// top bit is clear, and a leading `0xff` before a byte whose top bit is set are all longer251    /// than needed.252    pub fn isCanonicalBytes(bytes: []const u8) bool {253        if (bytes.len == 0) return true;254        if (bytes.len == 1) return bytes[0] != 0x00;255        const first = bytes[0];256        const second = bytes[1];257        if (first == 0x00 and (second & 0x80) == 0) return false;258        if (first == 0xff and (second & 0x80) != 0) return false;259        return true;260    }261};262263fn bigIsNegative(bytes: []const u8) bool {264    return bytes.len > 0 and (bytes[0] & 0x80) != 0;265}266267fn compareBig(a: []const u8, b: []const u8) std.math.Order {268    const a_neg = bigIsNegative(a);269    const b_neg = bigIsNegative(b);270    if (a_neg != b_neg) return if (a_neg) .lt else .gt;271    if (a.len != b.len) {272        return if (a_neg) std.math.order(b.len, a.len) else std.math.order(a.len, b.len);273    }274    return std.mem.order(u8, a, b);275}276277fn decodeI128Bytes(bytes: []const u8) i128 {278    std.debug.assert(bytes.len > 0);279    std.debug.assert(bytes.len <= 16);280    var result: u128 = if ((bytes[0] & 0x80) != 0) ~@as(u128, 0) else 0;281    for (bytes) |b| {282        result = (result << 8) | b;283    }284    return @bitCast(result);285}286287fn decode16BytesAsU128(bytes: []const u8) u128 {288    std.debug.assert(bytes.len == 16);289    var result: u128 = 0;290    for (bytes) |b| {291        result = (result << 8) | b;292    }293    return result;294}295296fn encodeI128(allocator: Allocator, value: i128) ![]u8 {297    if (value == 0) return allocator.alloc(u8, 0);298    var raw: [16]u8 = undefined;299    var bits: u128 = @bitCast(value);300    var i: usize = 16;301    while (i > 0) {302        i -= 1;303        raw[i] = @truncate(bits);304        bits >>= 8;305    }306    var start: usize = 0;307    while (start + 1 < 16) {308        const first = raw[start];309        const second = raw[start + 1];310        if (first == 0x00 and (second & 0x80) == 0) {311            start += 1;312            continue;313        }314        if (first == 0xff and (second & 0x80) != 0) {315            start += 1;316            continue;317        }318        break;319    }320    return allocator.dupe(u8, raw[start..]);321}322323fn encodeU128(allocator: Allocator, value: u128) ![]u8 {324    std.debug.assert(value > @as(u128, @intCast(std.math.maxInt(i128))));325    var raw: [17]u8 = undefined;326    raw[0] = 0x00;327    var bits = value;328    var i: usize = 17;329    while (i > 1) {330        i -= 1;331        raw[i] = @truncate(bits);332        bits >>= 8;333    }334    return allocator.dupe(u8, &raw);335}336337test "SignedInteger round-trip I128 fast path" {338    const allocator = std.testing.allocator;339    const cases = [_]i128{ 0, 1, -1, 127, -128, 128, -129, 12345, -12345, std.math.maxInt(i128), std.math.minInt(i128) };340    for (cases) |v| {341        const si = SignedInteger.fromI128(v);342        try std.testing.expectEqual(Tier.i128, @as(Tier, si.repr));343        const bytes = try si.toCanonicalBytes(allocator);344        defer allocator.free(bytes);345        var roundtrip = try SignedInteger.fromCanonicalBytes(allocator, bytes);346        defer roundtrip.deinit(allocator);347        try std.testing.expect(si.eql(roundtrip));348        try std.testing.expectEqual(v, try roundtrip.toI128());349    }350}351352test "SignedInteger U128 tier above i128 max" {353    const allocator = std.testing.allocator;354    const above: u128 = @as(u128, @intCast(std.math.maxInt(i128))) + 1;355    const si = SignedInteger.fromU128(above);356    try std.testing.expectEqual(Tier.u128, @as(Tier, si.repr));357    const bytes = try si.toCanonicalBytes(allocator);358    defer allocator.free(bytes);359    try std.testing.expectEqual(@as(usize, 17), bytes.len);360    try std.testing.expectEqual(@as(u8, 0x00), bytes[0]);361    try std.testing.expect((bytes[1] & 0x80) != 0);362    var roundtrip = try SignedInteger.fromCanonicalBytes(allocator, bytes);363    defer roundtrip.deinit(allocator);364    try std.testing.expectEqual(Tier.u128, @as(Tier, roundtrip.repr));365    try std.testing.expectEqual(above, try roundtrip.toU128());366}367368test "SignedInteger big tier holds bytes above u128" {369    const allocator = std.testing.allocator;370    var bytes_buf: [24]u8 = undefined;371    bytes_buf[0] = 0x01;372    @memset(bytes_buf[1..], 0x00);373    var si = try SignedInteger.fromCanonicalBytes(allocator, &bytes_buf);374    defer si.deinit(allocator);375    try std.testing.expectEqual(Tier.big, @as(Tier, si.repr));376    try std.testing.expect(!si.isNegative());377    try std.testing.expectError(RangeError.OutOfRange, si.toU128());378}379380test "SignedInteger rejects non-canonical bytes" {381    const allocator = std.testing.allocator;382    const non_canonical = [_]u8{ 0x00, 0x00 };383    try std.testing.expectError(DecodeError.NonCanonicalInteger, SignedInteger.fromCanonicalBytes(allocator, &non_canonical));384    const sign_ext = [_]u8{ 0xff, 0xff };385    try std.testing.expectError(DecodeError.NonCanonicalInteger, SignedInteger.fromCanonicalBytes(allocator, &sign_ext));386}387388test "SignedInteger cross-tier ordering" {389    const neg_i128 = SignedInteger.fromI128(-5);390    const pos_i128 = SignedInteger.fromI128(5);391    const u128_val = SignedInteger.fromU128(@as(u128, @intCast(std.math.maxInt(i128))) + 1);392    try std.testing.expectEqual(std.math.Order.lt, SignedInteger.order(neg_i128, pos_i128));393    try std.testing.expectEqual(std.math.Order.lt, SignedInteger.order(pos_i128, u128_val));394    try std.testing.expectEqual(std.math.Order.gt, SignedInteger.order(u128_val, neg_i128));395}396397test "SignedInteger.toI64Lossy saturates out-of-range tiers" {398    try std.testing.expectEqual(@as(i64, 42), SignedInteger.fromI128(42).toI64Lossy());399    try std.testing.expectEqual(@as(i64, -42), SignedInteger.fromI128(-42).toI64Lossy());400    const huge_pos: i128 = std.math.maxInt(i64) + @as(i128, 1);401    try std.testing.expectEqual(std.math.maxInt(i64), SignedInteger.fromI128(huge_pos).toI64Lossy());402    const huge_neg: i128 = std.math.minInt(i64) - @as(i128, 1);403    try std.testing.expectEqual(std.math.minInt(i64), SignedInteger.fromI128(huge_neg).toI64Lossy());404    const u128_val = SignedInteger.fromU128(@as(u128, @intCast(std.math.maxInt(i128))) + 1);405    try std.testing.expectEqual(std.math.maxInt(i64), u128_val.toI64Lossy());406}

1pub const integer_mod = @import("integer.zig");