lib/preserves/src/integer.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! Signed integers of any size, as data values carry them. An integer value needs equality, a total
2 //! order, a hash and an exact round trip through the bytes the binary syntax writes. Most integers
3 //! 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 ones
6 //! 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 many
8 //! byte spellings that differ only by extra leading `0x00` or `0xff` bytes, and byte equality needs
9 //! one spelling per number.
10 //!
11 //! The [Preserves](https://preserves.dev/) data language has signed integers of unbounded size, and
12 //! the package's binary syntax writes each as its shortest big-endian two's-complement bytes and
13 //! rejects any longer spelling.
14 //!
15 //! A number takes one of three representations (*tier*): 128 signed bits when it fits, 128 unsigned
16 //! bits when it is larger than that but still fits, and bytes otherwise. A number too large for 128
17 //! bits is stored as its shortest big-endian two's-complement bytes (*canonical bytes*), the same
18 //! bytes the binary syntax writes. Only that third representation allocates, so freeing and copying
19 //! cost nothing for every other integer. Equality, order and hash assume each number has one
20 //! 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 signed
22 //! integer (`SignedInteger`) written directly through its representation field (`repr`) can break
23 //! it with nothing to detect it. Across representations the order is numeric: negative large
24 //! numbers, then 128-bit signed, then 128-bit unsigned, then positive large numbers.
25 const std = @import("std");
26 const Allocator = std.mem.Allocator;
27
28 /// The error `fromCanonicalBytes` returns when its bytes are longer than the shortest spelling of
29 /// their number. Code that reads integers from bytes handles this error, as the binary and text
30 /// readers do.
31 pub const DecodeError = error{NonCanonicalInteger};
32 /// The error the `to` conversions return when the number does not fit the requested type. Code that
33 /// reads an integer as a fixed-width Zig integer handles this error when the number is too large or
34 /// has the wrong sign.
35 pub const RangeError = error{OutOfRange};
36
37 /// Names the three ways a number is stored: `i128` for 128 signed bits, `u128` for 128 unsigned
38 /// bits above the signed maximum, and `big` for heap bytes. Code that switches on how an integer is
39 /// stored reads this, as the text reader's tests do.
40 pub const Tier = enum { i128, u128, big };
41
42 /// 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 integers
44 /// 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 directly
46 /// through `repr` has to keep it.
47 pub const SignedInteger = struct {
48 /// The number in one of its three representations. A value set here directly has to use the
49 /// smallest representation that holds the number, because nothing checks it.
50 repr: Repr,
51
52 /// The number stored as 128 signed bits, 128 unsigned bits or heap bytes, tagged by which. Code
53 /// 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 unsigned
58 /// bits.
59 u128: u128,
60 /// The number's shortest big-endian two's-complement bytes, for a number outside both
61 /// 128-bit ranges. These bytes are at least 17 long.
62 big: []const u8,
63 };
64
65 /// 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 }
69
70 /// Returns `v`, stored in 128 signed bits. Readers and constructors call it for any integer
71 /// that fits in 128 signed bits.
72 pub fn fromI128(v: i128) SignedInteger {
73 return .{ .repr = .{ .i128 = v } };
74 }
75
76 /// Returns `v`, stored in 128 signed bits when it fits there and in 128 unsigned bits
77 /// 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 }
85
86 /// Reads a number from its shortest big-endian two's-complement bytes. The binary and text
87 /// readers call it for integers too large for fixed-width parsing. Empty bytes are zero, up to
88 /// 16 bytes give a 128-bit signed number, and 17 bytes of a number that fits 128 unsigned bits
89 /// give a 128-bit unsigned number. Numbers with more bytes keep a copy of the bytes from
90 /// `allocator`, which `deinit` frees. The call returns `error.NonCanonicalInteger` for any
91 /// 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 }
101
102 /// Frees the heap bytes of a number too large for 128 bits, and does nothing for any other
103 /// number. `Value.deinit` and `freeValueDeep` call it for every integer they free. The value is
104 /// 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 }
112
113 /// Returns a copy that owns its storage, copying the heap bytes of a large number with
114 /// `allocator`. `cloneValueDeep` calls it for every integer it copies. A number that fits in
115 /// 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 }
123
124 /// Returns a new allocation from `allocator` holding the number's shortest big-endian
125 /// two's-complement bytes, which the caller frees. The binary writer calls it for the bytes of
126 /// 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 }
134
135 /// 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 }
143
144 /// Returns the number when it is zero or positive and fits in 128 unsigned bits, and
145 /// `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 }
153
154 /// Returns the number when it fits in 64 signed bits, and `error.OutOfRange` otherwise. Code
155 /// 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 }
161
162 /// Returns the number clamped to the 64-bit signed range: the largest `i64` for any number
163 /// above it and the smallest for any number below. The JSON writer calls it to print an integer
164 /// 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 }
176
177 /// Returns the number when it is zero or positive and fits in 64 unsigned bits, and
178 /// `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 }
184
185 /// Returns whether the number is zero. Code that tests for zero calls it. Only a zero stored in
186 /// 128 signed bits counts, so a zero written directly into another representation reads as
187 /// nonzero.
188 pub fn isZero(self: SignedInteger) bool {
189 return switch (self.repr) {
190 .i128 => |v| v == 0,
191 .u128, .big => false,
192 };
193 }
194
195 /// 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 }
203
204 /// Returns whether two integers are equal. `Value.eql` calls it for two integers. Integers in
205 /// different representations are never equal, so the call is exact only when both use the
206 /// 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 }
223
224 /// Returns the numeric order of two integers. `Value.compare` calls it for two integers. Large
225 /// numbers compare by sign, then by byte length, then byte by byte. The order across
226 /// representations is exact only when both integers use the smallest representation that holds
227 /// 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 }
246
247 /// Returns whether `bytes` are the shortest big-endian two's-complement spelling of their
248 /// number. The binary reader calls it before reading an integer, so a longer spelling is
249 /// rejected. Empty bytes spell zero. A lone `0x00` byte, a leading `0x00` before a byte whose
250 /// top bit is clear, and a leading `0xff` before a byte whose top bit is set are all longer
251 /// 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 };
262
263 fn bigIsNegative(bytes: []const u8) bool {
264 return bytes.len > 0 and (bytes[0] & 0x80) != 0;
265 }
266
267 fn 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 }
276
277 fn 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 }
286
287 fn 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 }
295
296 fn 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 }
322
323 fn 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 }
336
337 test "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 }
351
352 test "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 }
367
368 test "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 }
379
380 test "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 }
387
388 test "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 }
396
397 test "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 }