GIF Frame Extractor — Zig source

// GIF Frame Extractor — decode a GIF byte stream into indexed frames.
//
// Language: Zig (0.13+), standard library only
// CosmoDev polyglot showcase port of the `gif-frame-extractor` tool.
// Ported from src/lib/gif-decode.ts — display source, part of CosmoDev's
// polyglot tool pages.
//
// Parses GIF87a/89a, LZW-decodes every frame to indexed pixels, and
// de-interlaces interlaced rows. Caller owns every slice: pass an allocator
// in, free the result with deinit. Truncated or malformed input returns an
// error instead of panicking — like the TS lib's null returns.

const std = @import("std");
const Allocator = std.mem.Allocator;

pub const Frame = struct {
    x: u16,
    y: u16,
    width: u16,
    height: u16,
    /// Palette override for this frame (RGB triplets); null = use global.
    palette: ?[]u8 = null,
    /// Pixel indices in natural row order (de-interlaced).
    indices: []u8,
    delay_ms: u16,
    /// Transparent palette index; -1 when the frame has none.
    transparent_index: i32,
    /// Disposal method 0-7 (0/1 keep, 2 restore bg, 3 restore previous).
    disposal: u3,
};

pub const Gif = struct {
    width: u16,
    height: u16,
    frames: []Frame,
    global_palette: ?[]u8,
    /// NETSCAPE loop count; 0 loops forever. Absent extension → play once
    /// (consumers differ on semantics — the TS lib surfaces Infinity there).
    loop_count: ?u16,

    pub fn deinit(self: *Gif, gpa: Allocator) void {
        for (self.frames) |f| {
            if (f.palette) |p| gpa.free(p);
            gpa.free(f.indices);
        }
        gpa.free(self.frames);
        if (self.global_palette) |p| gpa.free(p);
    }
};

const Reader = struct {
    data: []const u8,
    pos: usize = 0,

    fn u8At(self: *Reader) !u8 {
        if (self.pos >= self.data.len) return error.Truncated;
        const b = self.data[self.pos];
        self.pos += 1;
        return b;
    }
    fn u16le(self: *Reader) !u16 {
        const lo = try self.u8At();
        const hi = try self.u8At();
        return @as(u16, lo) | (@as(u16, hi) << 8);
    }
    fn bytes(self: *Reader, n: usize) ![]const u8 {
        if (self.pos + n > self.data.len) return error.Truncated;
        const s = self.data[self.pos .. self.pos + n];
        self.pos += n;
        return s;
    }
};

/// GIF LZW decompression — minCodeSize 2-8, clear-code resets, growing codes.
/// Dictionary as (prefix, suffix) pairs, reset on clear code; the KwKwK case
/// re-emits the previous chain's first byte, exactly like the TS emit().
pub fn lzwDecode(gpa: Allocator, min_code_size: u5, data: []const u8) ![]u8 {
    if (min_code_size < 2 or min_code_size > 8) return error.BadCodeSize;
    const clear_code: u16 = @as(u16, 1) << min_code_size;
    const eoi_code: u16 = clear_code + 1;

    var code_size: u5 = min_code_size + 1;
    var next_code: u16 = eoi_code + 1;

    var prefix = [_]i32{0} ** 4096;
    var suffix = [_]u8{0} ** 4096;
    var resetDict = struct {
        fn f(p: *[4096]i32, s: *[4096]u8, cc: u16, cs: u5, nc: *u16) struct { u5, u16 } {
            for (0..cc) |i| {
                p[i] = -1;
                s[i] = @intCast(i);
            }
            nc.* = cc + 2;
            return .{ cs, nc.* };
        }
    }.f;

    _ = resetDict(&prefix, &suffix, clear_code, min_code_size + 1, &next_code);
    code_size = min_code_size + 1;

    var out = std.ArrayList(u8).init(gpa);
    errdefer out.deinit();

    var stack: [4096]u8 = undefined;

    var bit_pos: usize = 0;
    var prev: i32 = -1;

    while (true) {
        // Read one codeSize-bit little-endian code; past the data = EOI.
        if ((bit_pos + code_size) > data.len * 8) break;
        var code: u16 = 0;
        {
            var i: u5 = 0;
            while (i < code_size) : (i += 1) {
                const idx = (bit_pos + i) >> 3;
                if (idx >= data.len) break;
                const bit = (data[idx] >> @intCast((bit_pos + i) & 7)) & 1;
                code |= @as(u16, bit) << @intCast(i);
            }
        }
        bit_pos += code_size;

        if (code == eoi_code) break;
        if (code == clear_code) {
            code_size = min_code_size + 1;
            next_code = eoi_code + 1;
            prev = -1;
            continue;
        }

        // Emit the code's chain via a stack unwind; remember the first byte
        // (KwKwK: when the code is not yet in the dictionary, emit prev's
        // chain + prev's first byte).
        var chain_first: u8 = undefined;
        var sp: usize = 0;
        var c: i32 = @intCast(code);
        if (code >= next_code) {
            // KwKwK — code not yet defined: chain is prev + first(prev).
            if (prev < 0) return error.BadCode;
            c = prev;
            chain_first = firstOf(&prefix, &suffix, prev);
        } else {
            chain_first = firstOf(&prefix, &suffix, c);
        }
        while (c >= 0) {
            stack[sp] = suffix[@intCast(c)];
            sp += 1;
            c = prefix[@intCast(c)];
        }
        // Unwind in reverse = natural order.
        while (sp > 0) {
            sp -= 1;
            try out.append(stack[sp]);
        }

        // Add prev+first to the dictionary (the entry the KwKwK case used).
        if (prev >= 0 and next_code < 4096) {
            prefix[next_code] = prev;
            suffix[next_code] = chain_first;
            next_code += 1;
        }
        prev = @intCast(code);

        if (next_code == (@as(u16, 1) << code_size) and code_size < 12) code_size += 1;
    }
    return out.toOwnedSlice();
}

fn firstOf(prefix: *const [4096]i32, suffix: *const [4096]u8, c: i32) u8 {
    var cur = c;
    while (prefix[@intCast(cur)] >= 0) cur = prefix[@intCast(cur)];
    return suffix[@intCast(cur)];
}

/// Decode a full GIF byte stream. Errors on bad signature or truncation.
pub fn decode(gpa: Allocator, data: []const u8) !Gif {
    var r = Reader{ .data = data };

    const sig = try r.bytes(6);
    if (!std.mem.eql(u8, sig[0..3], "GIF")) return error.NotGif;

    const width = try r.u16le();
    const height = try r.u16le();
    const flags = try r.u8At();
    const bg = try r.u8At(); // background color index (unused, like TS)
    _ = bg;
    const gct_size = @as(usize, 2) << @intCast(flags & 0x07);

    var global_palette: ?[]u8 = null;
    if (flags & 0x80 != 0) {
        const raw = try r.bytes(gct_size * 3);
        global_palette = try gpa.dupe(u8, raw);
    }
    errdefer if (global_palette) |p| gpa.free(p);

    var frames = std.ArrayList(Frame).init(gpa);
    errdefer frames.deinit();

    var loop_count: ?u16 = null;
    // Per-frame graphic-control state, applied to the NEXT image descriptor.
    var delay_ms: u16 = 0;
    var transparent_index: i32 = -1;
    var disposal: u3 = 0;

    while (true) {
        const b = r.u8At() catch break;
        switch (b) {
            0x3B => break, // trailer
            0x21 => { // extension
                const label = try r.u8At();
                if (label == 0xF9) { // graphic control
                    const block_len = try r.u8At();
                    const blk = try r.bytes(block_len);
                    if (blk.len >= 4) {
                        disposal = @intCast((blk[0] >> 2) & 0x07);
                        delay_ms = @as(u16, blk[1]) | (@as(u16, blk[2]) << 8);
                        transparent_index = if (blk[0] & 1 != 0) blk[3] else -1;
                    }
                } else if (label == 0xFF) { // application — NETSCAPE2.0 loop
                    const block_len = try r.u8At();
                    const ident = try r.bytes(block_len);
                    if (std.mem.eql(u8, ident, "NETSCAPE2.0")) {
                        // Sub-blocks: 03 01 <loop u16le>
                        if (try r.u8At() == 3) {
                            _ = try r.u8At(); // 01 sub-id
                            loop_count = try r.u16le();
                        }
                    }
                }
                // Skip any remaining sub-blocks of this extension.
                while (true) {
                    const n = try r.u8At();
                    if (n == 0) break;
                    _ = try r.bytes(n);
                }
            },
            0x2C => { // image descriptor
                const ix = try r.u16le();
                const iy = try r.u16le();
                const iw = try r.u16le();
                const ih = try r.u16le();
                const iflags = try r.u8At();
                const lct_size = @as(usize, 2) << @intCast(iflags & 0x07);

                var palette: ?[]u8 = null;
                if (iflags & 0x80 != 0) {
                    const raw = try r.bytes(lct_size * 3);
                    palette = try gpa.dupe(u8, raw);
                }
                errdefer if (palette) |p| gpa.free(p);

                const min_code_size = try r.u8At();
                // Concatenate the data sub-blocks, then LZW-decode.
                var lzw = std.ArrayList(u8).init(gpa);
                defer lzw.deinit();
                while (true) {
                    const n = try r.u8At();
                    if (n == 0) break;
                    try lzw.appendSlice(try r.bytes(n));
                }

                var indices = try lzwDecode(gpa, @intCast(min_code_size), lzw.items);
                errdefer gpa.free(indices);

                // De-interlace: rows arrive as passes 0,8 / 4,8 / 2,4 / 1,2.
                if (iflags & 0x40 != 0 and iw > 0 and ih > 0) {
                    const deint = try gpa.alloc(u8, @as(usize, iw) * ih);
                    defer gpa.free(deint);
                    const strides = [4][2]usize{ .{ 0, 8 }, .{ 4, 8 }, .{ 2, 4 }, .{ 1, 2 } };
                    var src_row: usize = 0;
                    for (strides) |pass| {
                        var y = pass[0];
                        while (y < ih) : (y += pass[1]) {
                            if (src_row < ih) {
                                const dst = @as(usize, y) * iw;
                                const src = src_row * iw;
                                const n = @min(iw, indices.len -| src);
                                @memcpy(deint[dst .. dst + n], indices[src .. src + n]);
                            }
                            src_row += 1;
                        }
                    }
                    @memcpy(indices[0..deint.len], deint);
                }

                try frames.append(.{
                    .x = ix,
                    .y = iy,
                    .width = iw,
                    .height = ih,
                    .palette = palette,
                    .indices = indices,
                    .delay_ms = delay_ms,
                    .transparent_index = transparent_index,
                    .disposal = disposal,
                });
                // Reset per-frame state (the TS lib applies it per descriptor).
                delay_ms = 0;
                transparent_index = -1;
                disposal = 0;
            },
            else => return error.BadBlock,
        }
    }

    return .{
        .width = width,
        .height = height,
        .frames = try frames.toOwnedSlice(),
        .global_palette = global_palette,
        .loop_count = loop_count,
    };
}

// Smoke: decode a 1×1 transparent GIF built by hand. Real vectors live in
// the TS test suite — this display port mirrors its structure.
pub fn main() !void {
    var gpa_state = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa_state.deinit();
    const gpa = gpa_state.allocator();

    // 1x1, global 2-color table, single LZW-min-3 image of one index-0 pixel.
    const one_pixel_gif = [_]u8{
        'G', 'I', 'F', '8', '9', 'a', 0x01, 0x00, 0x01, 0x00, 0x80, 0x00, 0x00,
        0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00,
        0x2C, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00,
        0x02, 0x02, 0x44, 0x01, 0x00,
        0x3B,
    };

    var gif = try decode(gpa, &one_pixel_gif);
    defer gif.deinit(gpa);
    std.debug.print("{}x{}, {} frame(s), first pixel index {d}\n", .{
        gif.width, gif.height, gif.frames.len, gif.frames[0].indices[0],
    });
}