lib/gif/src/encode/model.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

  1 const std = @import("std");
  2 
  3 pub const opaque_threshold: u8 = 128;
  4 pub const max_palette_entries: usize = 256;
  5 const palette_slots: usize = max_palette_entries * 2;
  6 const empty_slot = std.math.maxInt(u16);
  7 
  8 pub const EncodeError = error{
  9     InvalidDimensions,
 10     FrameSizeMismatch,
 11     NoFrames,
 12     TooManyColors,
 13 };
 14 
 15 pub const Exhaustion = error{
 16     CanvasPixelCapacityExceeded,
 17     EncodeInputMismatch,
 18     EncodeStorageInUse,
 19     FrameCapacityExceeded,
 20     PaletteCapacityExceeded,
 21 };
 22 
 23 pub const FrameView = struct {
 24     rgba8: []const u8,
 25     delay_cs: u16 = 0,
 26 };
 27 
 28 pub const AnimationView = struct {
 29     width: u32,
 30     height: u32,
 31     frames: []const FrameView,
 32     loop_count: ?u16 = null,
 33 };
 34 
 35 pub const Palette = struct {
 36     table: [max_palette_entries * 3]u8 = @as([(max_palette_entries * 3)]u8, @splat(0)),
 37     keys: [max_palette_entries]u24 = @as([max_palette_entries]u24, @splat(0)),
 38     slots: [palette_slots]u16 = @as([palette_slots]u16, @splat(empty_slot)),
 39     color_count: u16 = 0,
 40     transparent: ?u8 = null,
 41 
 42     pub fn build(frames: []const FrameView) EncodeError!Palette {
 43         var palette = Palette{};
 44         var has_transparent = false;
 45         for (frames) |frame| {
 46             var offset: usize = 0;
 47             while (offset < frame.rgba8.len) : (offset += 4) {
 48                 const pixel = frame.rgba8[offset..][0..4];
 49                 if (pixel[3] < opaque_threshold) {
 50                     has_transparent = true;
 51                 } else {
 52                     try palette.insert(colorKey(pixel[0], pixel[1], pixel[2]), pixel[0..3]);
 53                 }
 54             }
 55         }
 56         if (has_transparent) {
 57             if (palette.color_count == max_palette_entries) return error.TooManyColors;
 58             palette.transparent = @intCast(palette.color_count);
 59         }
 60         return palette;
 61     }
 62 
 63     pub fn entryCount(self: Palette) u16 {
 64         return self.color_count + @intFromBool(self.transparent != null);
 65     }
 66 
 67     pub fn tableEntries(self: Palette) u16 {
 68         std.debug.assert(self.entryCount() > 0);
 69         std.debug.assert(self.entryCount() <= max_palette_entries);
 70         return @max(2, std.math.ceilPowerOfTwoAssert(u16, self.entryCount()));
 71     }
 72 
 73     pub fn minCodeSize(self: Palette) u8 {
 74         return @max(2, std.math.log2_int(u16, self.tableEntries()));
 75     }
 76 
 77     pub fn index(self: *const Palette, rgba8: []const u8) u8 {
 78         std.debug.assert(rgba8.len >= 4);
 79         if (rgba8[3] < opaque_threshold) return self.transparent.?;
 80         return self.find(colorKey(rgba8[0], rgba8[1], rgba8[2])).?;
 81     }
 82 
 83     fn insert(self: *Palette, key: u24, rgb: []const u8) EncodeError!void {
 84         if (self.find(key) != null) return;
 85         if (self.color_count == max_palette_entries) return error.TooManyColors;
 86         const palette_index: u16 = self.color_count;
 87         self.keys[palette_index] = key;
 88         const base = @as(usize, palette_index) * 3;
 89         @memcpy(self.table[base..][0..3], rgb[0..3]);
 90         self.slots[self.emptySlot(key)] = palette_index;
 91         self.color_count += 1;
 92     }
 93 
 94     fn find(self: *const Palette, key: u24) ?u8 {
 95         var slot = paletteSlot(key);
 96         var probes: usize = 0;
 97         while (probes < palette_slots) : (probes += 1) {
 98             const palette_index = self.slots[slot];
 99             if (palette_index == empty_slot) return null;
100             if (self.keys[palette_index] == key) return @intCast(palette_index);
101             slot = (slot + 1) & (palette_slots - 1);
102         }
103         return null;
104     }
105 
106     fn emptySlot(self: *const Palette, key: u24) usize {
107         var slot = paletteSlot(key);
108         var probes: usize = 0;
109         while (probes < palette_slots) : (probes += 1) {
110             if (self.slots[slot] == empty_slot) return slot;
111             slot = (slot + 1) & (palette_slots - 1);
112         }
113         unreachable;
114     }
115 };
116 
117 pub const PixelSource = struct {
118     palette: *const Palette,
119     rgba8: []const u8,
120 
121     pub fn len(self: PixelSource) usize {
122         return self.rgba8.len / 4;
123     }
124 
125     pub fn at(self: PixelSource, index: usize) u8 {
126         std.debug.assert(index < self.len());
127         return self.palette.index(self.rgba8[index * 4 ..][0..4]);
128     }
129 };
130 
131 pub fn colorKey(r: u8, g: u8, b: u8) u24 {
132     return (@as(u24, r) << 16) | (@as(u24, g) << 8) | b;
133 }
134 
135 fn paletteSlot(key: u24) usize {
136     var hash: u32 = key;
137     hash ^= hash >> 16;
138     hash *%= 0x7feb352d;
139     hash ^= hash >> 15;
140     return @as(usize, hash) & (palette_slots - 1);
141 }