lib/gif/src/encode/capacity.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

  1 const std = @import("std");
  2 const lzw = @import("gif_lzw");
  3 const model = @import("model.zig");
  4 const plan_mod = @import("plan.zig");
  5 
  6 pub const storage_alignment: usize = @alignOf(u32);
  7 
  8 pub const Limits = struct {
  9     animation: model.AnimationView,
 10     bounds: plan_mod.Bounds,
 11     scratch: *lzw.Scratch,
 12 };
 13 
 14 pub const DeriveError = plan_mod.Error;
 15 
 16 pub const Capacity = struct {
 17     plan: plan_mod.Plan,
 18     key_offset: usize,
 19     key_bytes: usize,
 20     code_offset: usize,
 21     code_bytes: usize,
 22     compressed_offset: usize,
 23     output_offset: usize,
 24     storage_bytes: usize,
 25 
 26     pub fn derive(limits: Limits) DeriveError!Capacity {
 27         const plan = try plan_mod.Plan.inspect(limits.animation, limits.bounds, limits.scratch);
 28         const keys = try placed(u32, 0, lzw.dictionary_slots);
 29         const codes = try placed(u16, keys.end, lzw.dictionary_slots);
 30         const compressed_offset = codes.end;
 31         const output_offset = try added(compressed_offset, plan.max_compressed_bytes);
 32         const storage_bytes = try added(output_offset, plan.output_bytes);
 33         return .{
 34             .plan = plan,
 35             .key_offset = keys.start,
 36             .key_bytes = keys.bytes,
 37             .code_offset = codes.start,
 38             .code_bytes = codes.bytes,
 39             .compressed_offset = compressed_offset,
 40             .output_offset = output_offset,
 41             .storage_bytes = storage_bytes,
 42         };
 43     }
 44 };
 45 
 46 const Region = struct {
 47     start: usize,
 48     bytes: usize,
 49     end: usize,
 50 };
 51 
 52 fn added(left: usize, right: usize) DeriveError!usize {
 53     return std.math.add(usize, left, right) catch error.CapacityOverflow;
 54 }
 55 
 56 fn placed(comptime T: type, offset: usize, count: usize) DeriveError!Region {
 57     const mask: usize = @alignOf(T) - 1;
 58     const start = (try added(offset, mask)) & ~mask;
 59     const bytes = std.math.mul(usize, count, @sizeOf(T)) catch return error.CapacityOverflow;
 60     return .{ .start = start, .bytes = bytes, .end = try added(start, bytes) };
 61 }
 62 
 63 fn modelCapacity(limits: Limits) DeriveError!Capacity {
 64     const plan = try plan_mod.Plan.inspect(limits.animation, limits.bounds, limits.scratch);
 65     const key_offset: u128 = 0;
 66     const key_bytes = @as(u128, lzw.dictionary_slots) * @sizeOf(u32);
 67     const code_offset = alignForward(key_offset + key_bytes, @alignOf(u16));
 68     const code_bytes = @as(u128, lzw.dictionary_slots) * @sizeOf(u16);
 69     const compressed_offset = code_offset + code_bytes;
 70     const output_offset = compressed_offset + plan.max_compressed_bytes;
 71     const storage_bytes = output_offset + plan.output_bytes;
 72     const values = [_]u128{
 73         key_bytes,
 74         code_offset,
 75         code_bytes,
 76         compressed_offset,
 77         output_offset,
 78         storage_bytes,
 79     };
 80     for (values) |value| {
 81         if (value > std.math.maxInt(usize)) return error.CapacityOverflow;
 82     }
 83     return .{
 84         .plan = plan,
 85         .key_offset = @intCast(key_offset),
 86         .key_bytes = @intCast(key_bytes),
 87         .code_offset = @intCast(code_offset),
 88         .code_bytes = @intCast(code_bytes),
 89         .compressed_offset = @intCast(compressed_offset),
 90         .output_offset = @intCast(output_offset),
 91         .storage_bytes = @intCast(storage_bytes),
 92     };
 93 }
 94 
 95 fn alignForward(value: u128, alignment: u128) u128 {
 96     return (value + alignment - 1) & ~(alignment - 1);
 97 }
 98 
 99 const witness_rgba = [_]u8{
100     255, 0, 0, 255,
101     0,   0, 0, 255,
102 };
103 
104 const witness_animation = model.AnimationView{
105     .width = 2,
106     .height = 1,
107     .frames = &.{.{ .rgba8 = &witness_rgba }},
108 };
109 
110 test "GIF encode capacity matches an independent aligned byte model" {
111     comptime {
112         @stardustClaim(
113             @import("alloc_phase").capacity.witness(@import("./root.zig").Storage, "gif_encode_capacity"),
114             null,
115             null,
116             null,
117             null,
118             null,
119             null,
120         );
121     }
122 
123     var scratch: lzw.Scratch = undefined;
124     const limits = Limits{
125         .animation = witness_animation,
126         .bounds = .{ .canvas_pixels = 2, .frames = 1, .palette_entries = 2 },
127         .scratch = &scratch,
128     };
129     const capacity = try Capacity.derive(limits);
130     try std.testing.expectEqual(try modelCapacity(limits), capacity);
131     try std.testing.expectEqual(lzw.Scratch.bytes, capacity.compressed_offset);
132     try std.testing.expectEqual(capacity.storage_bytes, capacity.output_offset + 43);
133 }