lib/gif/src/encode/storage.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_phase = @import("alloc_phase");
3 const lzw = @import("gif_lzw");
4 const capacity_mod = @import("capacity.zig");
5 const model = @import("model.zig");
6 const plan_mod = @import("plan.zig");
7
8 pub const Regions = struct {
9 dictionary: lzw.Dictionary,
10 compressed: []u8,
11 output: []u8,
12 };
13
14 pub const Status = struct {
15 phase: alloc_phase.capacity.Phase,
16 in_use: bool,
17 storage_bytes: usize,
18 canvas_pixels: usize,
19 frames: usize,
20 palette_entries: usize,
21 compressed_bytes: usize,
22 output_bytes: usize,
23 };
24
25 pub const Storage = struct {
26 phase: alloc_phase.capacity.Phase,
27 capacity: capacity_mod.Capacity,
28 bytes: []align(capacity_mod.storage_alignment) u8,
29 keys: []u32,
30 codes: []u16,
31 compressed: []u8,
32 output: []u8,
33 in_use: bool = false,
34
35 pub const Limits: type = capacity_mod.Limits;
36 pub const Capacity: type = capacity_mod.Capacity;
37 pub const Exhaustion: type = model.Exhaustion;
38 pub const InitError = std.mem.Allocator.Error || capacity_mod.DeriveError;
39 pub const AcquireError: type = plan_mod.Error;
40
41 pub const claim: alloc_phase.capacity.Declaration = .{
42 .source = .{
43 .id = "gif.encode_storage",
44 .kind = .phase_static,
45 .limit_source = .caller,
46 .storage = .{
47 .covered = &.{
48 .{
49 .id = "global_palette_and_exact_encoding_plan",
50 .lifetime = .steady,
51 .detail = "global palette and exact encoding plan",
52 },
53 .{
54 .id = "lzw_dictionary_and_compressed_frame_scratch",
55 .lifetime = .steady,
56 .detail = "LZW dictionary and compressed-frame scratch",
57 },
58 .{
59 .id = "encoded_gif_output_bytes",
60 .lifetime = .steady,
61 .detail = "encoded GIF output bytes",
62 },
63 },
64 .excluded = &.{
65 "caller-owned animation frame bytes and frame views",
66 "filesystem and downstream decoder storage",
67 },
68 },
69 .capacity = .{
70 .inputs = &.{
71 alloc_phase.capacity.bindInput(Limits, "animation_frames", "animation.frames"),
72 alloc_phase.capacity.bindInput(Limits, "bounds_canvas_pixels", "bounds.canvas_pixels"),
73 alloc_phase.capacity.bindInput(Limits, "bounds_frames", "bounds.frames"),
74 },
75 .type_selectors = &.{},
76 .nodes = &.{
77 .{ .constant = 49152 },
78 .{ .input = 1 },
79 .{ .input = 2 },
80 .{ .add = .{ .left = 0, .right = 1 } },
81 .{ .add = .{ .left = 3, .right = 2 } },
82 },
83 .assertions = &.{.{
84 .scope = .closure_total,
85 .measure = .retained,
86 .relation = .upper_bound,
87 .expression = 4,
88 }},
89 },
90 .overload = .{
91 .kind = .reject_before_mutation,
92 .detail = "Bounds, input mismatch, and concurrent use reject before output mutation.",
93 },
94 .risks = .{
95 .transitive = .{
96 .status = .witnessed,
97 .detail = "Palette lookup, LZW coding, GIF framing, and output writing use fixed regions.",
98 },
99 .foreign = .{
100 .status = .excluded,
101 .detail = "input ownership and output consumption remain caller effects",
102 },
103 },
104 .obligations = &.{
105 .{ .key = "gif_encode_capacity", .role = .capacity_model },
106 .{ .key = "gif_encode_acquisition", .role = .custom },
107 .{ .key = "gif_encode_oom", .role = .custom },
108 .{ .key = "gif_encode_boundaries", .role = .overload },
109 .{ .key = "gif_encode_reuse", .role = .overload },
110 .{ .key = "gif_encode_sealed", .role = .transitive_risk },
111 .{ .key = "gif_encode_root", .role = .custom },
112 .{ .key = "gif_encode_consumer", .role = .foreign_risk },
113 },
114 },
115 .bindings = .{
116 .owner = @This(),
117 .seal = .{
118 .family = alloc_phase.capacity.selector(@This().activate),
119 .premise = .{
120 .class = .checked_semantic_fact,
121 .authority = .checker,
122 },
123 },
124 .teardown = .{
125 .family = alloc_phase.capacity.selector(@This().deinit),
126 .premise = .{
127 .class = .checked_semantic_fact,
128 .authority = .checker,
129 },
130 },
131 },
132 };
133
134 pub fn init(allocator: std.mem.Allocator, limits: Limits) InitError!Storage {
135 const capacity = try Capacity.derive(limits);
136 const bytes = try allocator.alignedAlloc(
137 u8,
138 .fromByteUnits(capacity_mod.storage_alignment),
139 capacity.storage_bytes,
140 );
141 const compressed_bytes = capacity.plan.max_compressed_bytes;
142 const compressed = bytes[capacity.compressed_offset..][0..compressed_bytes];
143 return .{
144 .phase = .initialization,
145 .capacity = capacity,
146 .bytes = bytes,
147 .keys = typedSlice(u32, bytes, capacity.key_offset, lzw.dictionary_slots),
148 .codes = typedSlice(u16, bytes, capacity.code_offset, lzw.dictionary_slots),
149 .compressed = compressed,
150 .output = bytes[capacity.output_offset..][0..capacity.plan.output_bytes],
151 };
152 }
153
154 pub fn activate(self: *Storage) void {
155 std.debug.assert(self.phase == .initialization);
156 std.debug.assert(self.bytes.len == self.capacity.storage_bytes);
157 self.phase = .steady;
158 }
159
160 pub fn acquire(self: *Storage, animation: model.AnimationView) AcquireError!Regions {
161 std.debug.assert(self.phase == .steady);
162 if (self.in_use) return error.EncodeStorageInUse;
163 const dictionary = lzw.Dictionary.init(self.keys, self.codes);
164 const actual = try plan_mod.Plan.inspectDictionary(
165 animation,
166 self.capacity.plan.bounds,
167 dictionary,
168 );
169 if (!std.meta.eql(actual, self.capacity.plan)) return error.EncodeInputMismatch;
170 self.in_use = true;
171 return .{
172 .dictionary = dictionary,
173 .compressed = self.compressed,
174 .output = self.output,
175 };
176 }
177
178 pub fn reset(self: *Storage) void {
179 std.debug.assert(self.phase == .steady);
180 std.debug.assert(self.in_use);
181 self.in_use = false;
182 }
183
184 pub fn status(self: *const Storage) Status {
185 return .{
186 .phase = self.phase,
187 .in_use = self.in_use,
188 .storage_bytes = self.capacity.storage_bytes,
189 .canvas_pixels = self.capacity.plan.canvas_pixels,
190 .frames = self.capacity.plan.frames,
191 .palette_entries = self.capacity.plan.palette_entries,
192 .compressed_bytes = self.capacity.plan.max_compressed_bytes,
193 .output_bytes = self.capacity.plan.output_bytes,
194 };
195 }
196
197 pub fn deinit(self: *Storage, allocator: std.mem.Allocator) void {
198 std.debug.assert(self.phase != .teardown);
199 std.debug.assert(!self.in_use);
200 std.debug.assert(self.bytes.len == self.capacity.storage_bytes);
201 self.phase = .teardown;
202 allocator.free(self.bytes);
203 self.bytes = &.{};
204 self.keys = &.{};
205 self.codes = &.{};
206 self.compressed = &.{};
207 self.output = &.{};
208 }
209 };
210
211 fn typedSlice(
212 comptime T: type,
213 bytes: []align(capacity_mod.storage_alignment) u8,
214 offset: usize,
215 count: usize,
216 ) []T {
217 const byte_count = count * @sizeOf(T);
218 const region: []align(@alignOf(T)) u8 = @alignCast(bytes[offset..][0..byte_count]);
219 return std.mem.bytesAsSlice(T, region);
220 }
221
222 const witness_rgba = [_]u8{
223 255, 0, 0, 255,
224 0, 0, 0, 255,
225 };
226
227 const witness_animation = model.AnimationView{
228 .width = 2,
229 .height = 1,
230 .frames = &.{.{ .rgba8 = &witness_rgba }},
231 };
232
233 fn checkInitFailures(allocator: std.mem.Allocator) !void {
234 var scratch: lzw.Scratch = undefined;
235 var storage = try Storage.init(allocator, .{
236 .animation = witness_animation,
237 .bounds = .{ .canvas_pixels = 2, .frames = 1, .palette_entries = 2 },
238 .scratch = &scratch,
239 });
240 storage.deinit(allocator);
241 }
242
243 test "GIF encode storage acquires one exact aligned region" {
244 comptime {
245 @stardustClaim(
246 @import("alloc_phase").capacity.witness(Storage, "gif_encode_acquisition"),
247 null,
248 null,
249 null,
250 null,
251 null,
252 null,
253 );
254 }
255
256 var counting = std.testing.FailingAllocator.init(std.testing.allocator, .{});
257 var scratch: lzw.Scratch = undefined;
258 const limits = capacity_mod.Limits{
259 .animation = witness_animation,
260 .bounds = .{ .canvas_pixels = 2, .frames = 1, .palette_entries = 2 },
261 .scratch = &scratch,
262 };
263 const capacity = try capacity_mod.Capacity.derive(limits);
264 var storage = try Storage.init(counting.allocator(), limits);
265 defer storage.deinit(counting.allocator());
266
267 try std.testing.expectEqual(@as(usize, 1), counting.alloc_index);
268 try std.testing.expectEqual(capacity.storage_bytes, counting.allocated_bytes);
269 storage.activate();
270 const regions = try storage.acquire(witness_animation);
271 defer storage.reset();
272 const base = @intFromPtr(storage.bytes.ptr);
273 try std.testing.expectEqual(
274 base + capacity.key_offset,
275 @intFromPtr(regions.dictionary.keys.ptr),
276 );
277 try std.testing.expectEqual(
278 base + capacity.code_offset,
279 @intFromPtr(regions.dictionary.codes.ptr),
280 );
281 try std.testing.expectEqual(
282 base + capacity.compressed_offset,
283 @intFromPtr(regions.compressed.ptr),
284 );
285 try std.testing.expectEqual(base + capacity.output_offset, @intFromPtr(regions.output.ptr));
286 }
287
288 test "GIF encode storage retries after every allocation failure" {
289 comptime {
290 @stardustClaim(
291 @import("alloc_phase").capacity.witness(Storage, "gif_encode_oom"),
292 null,
293 null,
294 null,
295 null,
296 null,
297 null,
298 );
299 }
300
301 try std.testing.checkAllAllocationFailures(std.testing.allocator, checkInitFailures, .{});
302 }
303
304 comptime {
305 alloc_phase.capacity.requireAllocatorRejectingOwnerShape(Storage);
306 }