lib/reducer/src/bytes/capacity.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! The layout and the memory bound of the *workspace* (the one byte allocation
2 //! `Storage` makes up front and reuses for every run) are derived for byte
3 //! reduction.
4 //!
5 //! The caller supplies one sizing number, the longest input it will submit, as
6 //! its *limits*, which the formulas write $N$. Shortening a sequence of length
7 //! $N$ needs two regions of memory at the same time:
8 //! 1. The *witness lane* holds the *current sequence* (the shortest sequence
9 //! the oracle has accepted so far, which the search deletes from next) and
10 //! needs $N$ bytes.
11 //! 2. The *scratch lane* is where each *candidate* (one shorter byte sequence
12 //! built by deleting a run of bytes from the current sequence and handed to
13 //! the oracle) is assembled and needs $N - 1$ bytes.
14 //!
15 //! Every candidate is strictly shorter than the current sequence, so the
16 //! scratch lane needs at most $\max(N - 1, 0)$ bytes. The total is:
17 //!
18 //! $$\text{storage\_bytes} = N + \max(N - 1, 0)$$
19 //!
20 //! At $N = 0$ both lanes need 0 bytes, so the total is 0 bytes. A workspace of
21 //! zero length asks the allocator for a zero-byte slice while initializing, and
22 //! that request need not reach the heap.
23 //!
24 //! `Capacity.derive()` works out this layout in arithmetic and allocates
25 //! nothing. The arithmetic overflows when
26 //! $N + \max(N - 1, 0) > \text{maxInt}(\text{usize})$. For example, on a 64-bit
27 //! target the largest input limit that can be represented is
28 //! $\lfloor \text{maxInt}(\text{usize}) / 2 \rfloor + 1 = 2^{63}$, and the
29 //! storage it derives is $\text{maxInt}(\text{usize}) = 2^{64} - 1$ bytes. A
30 //! limit above that returns `DeriveError.CapacityOverflow`, which reports that
31 //! the bound exceeds what `usize` can hold and stands apart from an allocator
32 //! failure.
33
34 const std = @import("std");
35
36 /// Sizing constraint the caller supplies for the byte reduction workspace.
37 pub const Limits = struct {
38 /// Ceiling on the length in bytes of any initial input handed to
39 /// `reduce()`. An input longer than this is refused at acquisition with
40 /// `Exhaustion.InputCapacityExceeded`.
41 max_input_bytes: usize,
42 };
43
44 /// Errors raised while computing the storage requirement from `Limits`.
45 pub const DeriveError = error{
46 /// The requested `max_input_bytes` cannot be represented in `usize` once
47 /// the scratch lane is added to it, which is the condition
48 /// $N + \max(N - 1, 0) > \text{maxInt}(\text{usize})$. The bound exceeds
49 /// what the arithmetic can represent, so it stands apart from the
50 /// allocator's own `OutOfMemory`.
51 CapacityOverflow,
52 };
53
54 /// Workspace layout derived from the caller's limits, sized so that a run in
55 /// steady state needs no further allocation.
56 pub const Capacity = struct {
57 /// Caller's limits that this capacity was derived from.
58 limits: Limits,
59 /// Byte offset in the backing allocation where the scratch lane starts. It
60 /// equals `limits.max_input_bytes` exactly.
61 candidate_offset: usize,
62 /// Greatest length in bytes any candidate takes, which is $\max(N - 1, 0)$.
63 candidate_bytes: usize,
64 /// Total the combined allocation needs, which is
65 /// $\text{candidate\_offset} + \text{candidate\_bytes}$.
66 storage_bytes: usize,
67
68 /// Works out the memory a workspace needs to reduce inputs up to
69 /// `limits.max_input_bytes`. It computes $N + \max(N - 1, 0)$, taking the
70 /// scratch lane's length with saturating subtraction and the total with
71 /// checked addition. It produces the arithmetic layout alone and calls no
72 /// allocator.
73 ///
74 /// ## Errors
75 /// It returns `DeriveError.CapacityOverflow` when the combined requirement
76 /// exceeds `std.math.maxInt(usize)`.
77 pub fn derive(limits: Limits) DeriveError!Capacity {
78 const candidate_bytes = limits.max_input_bytes -| 1;
79 const capacity = Capacity{
80 .limits = limits,
81 .candidate_offset = limits.max_input_bytes,
82 .candidate_bytes = candidate_bytes,
83 .storage_bytes = std.math.add(
84 usize,
85 limits.max_input_bytes,
86 candidate_bytes,
87 ) catch return error.CapacityOverflow,
88 };
89 std.debug.assert(capacity.candidate_offset == limits.max_input_bytes);
90 std.debug.assert(capacity.candidate_bytes <= limits.max_input_bytes);
91 std.debug.assert(capacity.storage_bytes >= limits.max_input_bytes);
92 std.debug.assert(
93 capacity.candidate_offset + capacity.candidate_bytes == capacity.storage_bytes,
94 );
95 return capacity;
96 }
97 };
98
99 fn modelCapacity(limits: Limits) DeriveError!Capacity {
100 const input_bytes: u128 = limits.max_input_bytes;
101 const candidate_bytes = if (input_bytes == 0) 0 else input_bytes - 1;
102 const storage_bytes = input_bytes + candidate_bytes;
103 if (storage_bytes > std.math.maxInt(usize)) return error.CapacityOverflow;
104 return .{
105 .limits = limits,
106 .candidate_offset = limits.max_input_bytes,
107 .candidate_bytes = @intCast(candidate_bytes),
108 .storage_bytes = @intCast(storage_bytes),
109 };
110 }
111
112 test "byte storage capacity matches an independent byte model" {
113 comptime {
114 @stardustClaim(
115 @import("alloc_phase").capacity.witness(@import("./root.zig").Storage, "reducer_byte_capacity"),
116 null,
117 null,
118 null,
119 null,
120 null,
121 null,
122 );
123 }
124
125 const limits = Limits{ .max_input_bytes = 9 };
126 try std.testing.expectEqual(try modelCapacity(limits), try Capacity.derive(limits));
127 try std.testing.expectEqual(@as(usize, 17), (try Capacity.derive(limits)).storage_bytes);
128 try std.testing.expectEqual(
129 @as(usize, 0),
130 (try Capacity.derive(.{ .max_input_bytes = 0 })).storage_bytes,
131 );
132 }
133
134 test "byte storage capacity accepts its largest representable input limit" {
135 const max_input_bytes = std.math.maxInt(usize) / 2 + 1;
136 const capacity = try Capacity.derive(.{ .max_input_bytes = max_input_bytes });
137 try std.testing.expectEqual(std.math.maxInt(usize), capacity.storage_bytes);
138 try std.testing.expectError(
139 error.CapacityOverflow,
140 Capacity.derive(.{ .max_input_bytes = max_input_bytes + 1 }),
141 );
142 }