Video to GIF Converter — Zig source

// Video to GIF Converter — Zig (0.13+, standard library only) port of the
// video-to-gif tool: a pure GIF89a encoder core.
// Ported from src/lib/gif-encode.ts (the canonical TypeScript implementation).
// Display source — part of CosmoDev's polyglot tool pages.
//
// Same contract as the TS reference: one palette quantized from a
// down-sampled mix of ALL frames (median cut), nearest-color mapping with an
// exact-match cache, and GIF-variant LZW. No video decode — frames arrive as
// RGBA buffers. Caller owns the returned slice.

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

const Pixel = struct { r: u8, g: u8, b: u8 };
const Swatch = struct { r: u8, g: u8, b: u8, population: u32 };
const GifFrameInput = struct { width: u16, height: u16, rgba: []const u8, delay_ms: u16 };

/// Encode RGBA frames into an animated GIF89a byte stream.
pub fn encode(gpa: Allocator, frames: []const GifFrameInput, max_colors: usize, loop_count: u16) ![]u8 {
    if (frames.len == 0) return error.NoFrames;

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

    // Header + logical screen descriptor sized from the first frame.
    try out.appendSlice("GIF89a");
    try u16le(&out, frames[0].width);
    try u16le(&out, frames[0].height);
    try out.append(0xF0 | 0x07); // GCT flag, 8-bit color resolution, 256 entries
    try out.append(0); // background color index
    try out.append(0); // pixel aspect ratio — unspecified

    // One palette from a down-sampled mix of ALL frames (like the TS lib).
    var palette = try quantizeMixed(gpa, frames, @min(max_colors, 256));
    defer palette.deinit(gpa);
    for (palette.items) |s| {
        try out.appendSlice(&.{ s.r, s.g, s.b });
    }
    var fill: usize = palette.items.len;
    while (fill < 256) : (fill += 3) try out.appendSlice(&.{ 0, 0, 0 });

    // NETSCAPE2.0 application extension — the loop-count block every
    // animated GIF carries.
    try out.appendSlice(&.{ 0x21, 0xFF, 11 });
    try out.appendSlice("NETSCAPE2.0");
    try out.appendSlice(&.{ 3, 1 });
    try u16le(&out, loop_count);
    try out.append(0);

    for (frames) |f| try writeFrame(gpa, &out, f, palette.items);

    try out.append(0x3B); // trailer
    return out.toOwnedSlice();
}

fn writeFrame(gpa: Allocator, o: *std.ArrayList(u8), f: GifFrameInput, palette: []const Swatch) !void {
    // Graphic control extension: disposal 1 (keep), delay in 1/100 s.
    try o.appendSlice(&.{ 0x21, 0xF9, 4, 0x04 });
    try u16le(o, f.delay_ms / 10);
    try o.appendSlice(&.{ 0, 0 }); // no transparent index, block terminator

    // Image descriptor.
    try o.append(0x2C);
    try u16le(o, 0);
    try u16le(o, 0);
    try u16le(o, f.width);
    try u16le(o, f.height);
    try o.append(0); // no local color table, not interlaced

    try o.append(8); // LZW minimum code size
    const indices = try mapToIndices(gpa, f, palette);
    defer gpa.free(indices);
    const lzw = try lzwCompress(gpa, indices, 8);
    defer gpa.free(lzw);
    try writeSubBlocks(o, lzw);
}

/// Nearest-color mapping with an exact-match cache — the TS lib's trick for
/// skipping the O(palette) scan on repeated colors.
fn mapToIndices(gpa: Allocator, f: GifFrameInput, palette: []const Swatch) ![]u8 {
    const n = @as(usize, f.width) * f.height;
    const indices = try gpa.alloc(u8, n);
    var cache = std.AutoHashMap(u32, u8).init(gpa);
    defer cache.deinit();
    for (0..n) |i| {
        const o = i * 4;
        const key = (@as(u32, f.rgba[o]) << 16) | (@as(u32, f.rgba[o + 1]) << 8) | f.rgba[o + 2];
        const hit = cache.get(key);
        if (hit) |idx| {
            indices[i] = idx;
        } else {
            const idx = nearest(palette, f.rgba[o], f.rgba[o + 1], f.rgba[o + 2]);
            try cache.put(key, idx);
            indices[i] = idx;
        }
    }
    return indices;
}

fn nearest(palette: []const Swatch, r: u8, g: u8, b: u8) u8 {
    var best: u8 = 0;
    var best_d: i32 = std.math.maxInt(i32);
    for (palette, 0..) |s, i| {
        const dr = @as(i32, r) - s.r;
        const dg = @as(i32, g) - s.g;
        const db = @as(i32, b) - s.b;
        const d = dr * dr + dg * dg + db * db;
        if (d < best_d) {
            best_d = d;
            best = @intCast(i);
        }
    }
    return best;
}

/// GIF-variant LZW: variable-width codes, little-endian bit packing, clear
/// code emitted on dictionary overflow (the classic 12-bit wall).
fn lzwCompress(gpa: Allocator, pixels: []const u8, min_code_size: u5) ![]u8 {
    const clear: u32 = @as(u32, 1) << min_code_size;
    const eoi: u32 = clear + 1;

    var out = std.ArrayList(u8).init(gpa);
    errdefer out.deinit();
    var dict = std.AutoHashMap(u64, u32).init(gpa);
    defer dict.deinit();

    var code_size: u5 = min_code_size + 1;
    var next: u32 = eoi + 1;
    var cur: i32 = -1;
    var bits: u32 = 0;
    var n_bits: u5 = 0;

    const Emit = struct {
        fn f(o: *std.ArrayList(u8), b: *u32, nb: *u5, code: u32, cs: u5) !void {
            b.* |= code << nb.*;
            nb.* += cs;
            while (nb.* >= 8) {
                try o.append(@truncate(b.* & 0xFF));
                b.* >>= 8;
                nb.* -= 8;
            }
        }
    }.f;

    try Emit(&out, &bits, &n_bits, clear, code_size);
    for (pixels) |p| {
        if (cur < 0) {
            cur = p;
            continue;
        }
        const key = (@as(u64, @intCast(cur)) << 8) | p;
        if (dict.get(key)) |code| {
            cur = @intCast(code);
            continue;
        }
        try Emit(&out, &bits, &n_bits, @intCast(cur), code_size);
        try dict.put(key, next);
        next += 1;
        if (next > (@as(u32, 1) << code_size) and code_size < 12) code_size += 1;
        if (next == 4096) {
            try Emit(&out, &bits, &n_bits, clear, code_size);
            dict.clearRetainingCapacity();
            next = eoi + 1;
            code_size = min_code_size + 1;
        }
        cur = p;
    }
    if (cur >= 0) try Emit(&out, &bits, &n_bits, @intCast(cur), code_size);
    try Emit(&out, &bits, &n_bits, eoi, code_size);
    if (n_bits > 0) try out.append(@truncate(bits & 0xFF));
    return out.toOwnedSlice();
}

fn writeSubBlocks(o: *std.ArrayList(u8), data: []const u8) !void {
    var pos: usize = 0;
    while (pos < data.len) : (pos += 255) {
        const n: u8 = @intCast(@min(255, data.len - pos));
        try o.append(n);
        try o.appendSlice(data[pos .. pos + n]);
    }
    try o.append(0); // block terminator
}

const Palette = struct {
    items: []Swatch,
    fn deinit(self: *Palette, gpa: Allocator) void {
        gpa.free(self.items);
    }
};

/// Median-cut over a 16K-sample mix of every frame's pixels.
fn quantizeMixed(gpa: Allocator, frames: []const GifFrameInput, max_colors: usize) !Palette {
    var pixels = std.ArrayList(Pixel).init(gpa);
    defer pixels.deinit();
    for (frames) |f| {
        const total = f.rgba.len / 4;
        const stride = @max(1, total / (16384 / frames.len));
        var i: usize = 0;
        while (i < total) : (i += stride) {
            const o = i * 4;
            if (f.rgba[o + 3] > 0)
                try pixels.append(.{ .r = f.rgba[o], .g = f.rgba[o + 1], .b = f.rgba[o + 2] });
        }
    }
    if (pixels.items.len == 0) try pixels.append(.{ .r = 0, .g = 0, .b = 0 });

    var buckets = std.ArrayList([]Pixel).init(gpa);
    defer buckets.deinit();
    try buckets.append(pixels.items);

    while (buckets.items.len < max_colors) {
        var best: ?usize = null;
        var best_range: u8 = 0;
        var best_ch: u2 = 0;
        for (buckets.items, 0..) |b, i| {
            const s = spread(b);
            if (s.range > best_range) {
                best_range = s.range;
                best = i;
                best_ch = s.ch;
            }
        }
        if (best == null or best_range == 0) break;
        const b = buckets.orderedRemove(best.?);
        const sorted = try gpa.dupe(Pixel, b);
        // Zig sort is unstable; indexed tiebreak mirrors the TS stable sort.
        const Idx = struct { px: Pixel, i: usize };
        var idx = try gpa.alloc(Idx, sorted.len);
        defer gpa.free(idx);
        for (sorted, 0..) |p, k| idx[k] = .{ .px = p, .i = k };
        const ch = best_ch;
        std.sort.pdq(Idx, idx, ch, struct {
            fn lessThan(channel: u2, a: Idx, b: Idx) bool {
                const av = switch (channel) { 0 => a.px.r, 1 => a.px.g, else => a.px.b };
                const bv = switch (channel) { 0 => b.px.r, 1 => b.px.g, else => b.px.b };
                return if (av == bv) a.i < b.i else av < bv;
            }
        }.lessThan);
        for (idx, 0..) |e, k| sorted[k] = e.px;
        try buckets.append(sorted[0 .. sorted.len / 2]);
        try buckets.append(sorted[sorted.len / 2 ..]);
    }

    const items = try gpa.alloc(Swatch, buckets.items.len);
    for (buckets.items, 0..) |b, i| {
        var rs: u64 = 0;
        var gs: u64 = 0;
        var bs: u64 = 0;
        for (b) |p| {
            rs += p.r;
            gs += p.g;
            bs += p.b;
        }
        items[i] = .{
            .r = @intCast(@divTrunc(rs + b.len / 2, b.len)),
            .g = @intCast(@divTrunc(gs + b.len / 2, b.len)),
            .b = @intCast(@divTrunc(bs + b.len / 2, b.len)),
            .population = @intCast(b.len),
        };
    }
    return .{ .items = items };
}

const SpreadRC = struct { range: u8, ch: u2 };

fn spread(b: []const Pixel) SpreadRC {
    var mn = [3]u8{ 255, 255, 255 };
    var mx = [3]u8{ 0, 0, 0 };
    for (b) |p| {
        const v = [3]u8{ p.r, p.g, p.b };
        for (0..3) |c| {
            mn[c] = @min(mn[c], v[c]);
            mx[c] = @max(mx[c], v[c]);
        }
    }
    const r = mx[0] - mn[0];
    const g = mx[1] - mn[1];
    const bb = mx[2] - mn[2];
    if (r >= g and r >= bb) return .{ .range = r, .ch = 0 };
    if (g >= bb) return .{ .range = g, .ch = 1 };
    return .{ .range = bb, .ch = 2 };
}

fn u16le(o: *std.ArrayList(u8), n: u16) !void {
    try o.append(@truncate(n & 0xFF));
    try o.append(@truncate(n >> 8));
}

pub fn main() !void {
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();
    const gpa = arena.allocator();

    // Smoke: a 1×1 red frame encodes to a tiny valid GIF89a.
    const frame = GifFrameInput{
        .width = 1,
        .height = 1,
        .rgba = &[_]u8{ 255, 0, 0, 255 },
        .delay_ms = 100,
    };
    const gif = try encode(gpa, &.{frame}, 256, 0);
    std.debug.print("{d} bytes, header {s}\n", .{ gif.len, gif[0..6] }); // GIF89a
}