Video to GIF Converter — Java source

// Video to GIF Converter — a pure GIF89a encoder core.
//
// Language: Java (17+, standard library only)
// CosmoDev polyglot showcase port of the `video-to-gif` tool.
// Ported from src/lib/gif-encode.ts (with its palette-extract dependency
// inlined) — display source, part of CosmoDev's polyglot tool pages.
//
// No video decode — frames arrive as RGBA buffers. One shared palette is
// quantized from a down-sampled mix of ALL frames (median cut), pixels are
// mapped to palette indices via an exact-match cache plus nearest-RGB
// distance, and the index stream is LZW-compressed GIF-style (LSB-first
// codes, 9..12-bit widths, clear-code dictionary resets) into sub-blocks.
//
// Java trap: bytes are SIGNED — every stored byte is masked with & 0xff on
// read, and palette indices are written as (byte) i. Trap two: the encoder's
// dictionary runs one entry AHEAD of the decoder's, so the code width grows
// one entry later than intuition says — right after adding code 2^codeSize.

import java.io.ByteArrayOutputStream;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public final class VideoToGif {

    /** One frame: RGBA pixels (top-left origin) plus its delay. */
    public record GifFrameInput(int width, int height, byte[] rgba, int delayMs) { }

    /** Palette entry from the median cut. */
    public record Swatch(int r, int g, int b, int population) { }

    private record Pixel(int r, int g, int b) { }

    /** Palette size ceiling; GIF caps a color table at 256 entries. */
    private static final int MAX_COLORS = 128;

    // ── Median-cut palette (inlined from palette-extract.ts) ───────────────

    private static int[] bounds(List<Pixel> bucket) {
        int mnR = 255, mxR = 0, mnG = 255, mxG = 0, mnB = 255, mxB = 0;
        for (Pixel p : bucket) {
            if (p.r < mnR) mnR = p.r; if (p.r > mxR) mxR = p.r;
            if (p.g < mnG) mnG = p.g; if (p.g > mxG) mxG = p.g;
            if (p.b < mnB) mnB = p.b; if (p.b > mxB) mxB = p.b;
        }
        return new int[] { mxR - mnR, mxG - mnG, mxB - mnB };
    }

    /** Split a bucket at the median of its widest channel (stable, deterministic). */
    private static List<Pixel>[] splitBucket(List<Pixel> bucket) {
        int[] b = bounds(bucket);
        int channel = b[1] > b[0] ? 1 : 0;
        if (b[2] > b[channel]) channel = 2;
        final int ch = channel;
        Comparator<Pixel> byChannel = switch (ch) {
            case 0 -> Comparator.comparingInt(Pixel::r);
            case 1 -> Comparator.comparingInt(Pixel::g);
            default -> Comparator.comparingInt(Pixel::b);
        };
        List<Pixel> sorted = new ArrayList<>(bucket);
        sorted.sort(byChannel);
        int mid = sorted.size() / 2;
        @SuppressWarnings("unchecked")
        List<Pixel>[] halves = new List[] {
                new ArrayList<>(sorted.subList(0, mid)),
                new ArrayList<>(sorted.subList(mid, sorted.size())) };
        return halves;
    }

    private static List<Swatch> extractPalette(byte[] rgba, int maxColors) {
        int total = rgba.length / 4;
        List<Pixel> pixels = new ArrayList<>();
        int stride = Math.max(1, total / 16384); // bounded samples
        for (int i = 0; i < total; i += stride) {
            int o = i * 4;
            if ((rgba[o + 3] & 0xff) == 0) continue;
            pixels.add(new Pixel(rgba[o] & 0xff, rgba[o + 1] & 0xff, rgba[o + 2] & 0xff));
        }
        if (pixels.isEmpty()) return List.of();

        List<List<Pixel>> buckets = new ArrayList<>(List.of(pixels));
        while (buckets.size() < maxColors) {
            int bestIdx = -1, bestRange = 1; // range 1 (duplicates only) never splits
            for (int i = 0; i < buckets.size(); i++) {
                int[] b = bounds(buckets.get(i));
                int range = Math.max(b[0], Math.max(b[1], b[2]));
                if (range > bestRange) { bestRange = range; bestIdx = i; }
            }
            if (bestIdx == -1) break;
            buckets.addAll(List.of(splitBucket(buckets.remove(bestIdx))));
        }
        List<Swatch> out = new ArrayList<>();
        for (List<Pixel> bucket : buckets) {
            if (bucket.isEmpty()) continue;
            long sr = 0, sg = 0, sb = 0;
            for (Pixel p : bucket) { sr += p.r; sg += p.g; sb += p.b; }
            out.add(new Swatch((int) Math.round((double) sr / bucket.size()),
                               (int) Math.round((double) sg / bucket.size()),
                               (int) Math.round((double) sb / bucket.size()),
                               bucket.size()));
        }
        out.sort(Comparator.comparingInt(Swatch::population).reversed());
        return out;
    }

    // ── LZW compression (GIF variant) ──────────────────────────────────────

    /** Pack codes LSB-first at the current width; returns the raw byte stream. */
    public static byte[] lzwEncode(int minCodeSize, byte[] indices) {
        int clearCode = 1 << minCodeSize, eoiCode = clearCode + 1;
        int[] codeSize = { minCodeSize + 1 };
        int[] nextCode = { eoiCode + 1 };

        // Dictionary: (prefixCode << 8 | byte) -> code, keyed numerically.
        java.util.HashMap<Integer, Integer> dict = new java.util.HashMap<>();
        Runnable resetDict = () -> {
            dict.clear();
            nextCode[0] = eoiCode + 1;
            codeSize[0] = minCodeSize + 1;
        };
        resetDict.run();

        ByteArrayOutputStream out = new ByteArrayOutputStream();
        long[] bitBuffer = { 0 }; // long: codeSize + 7 leftover bits always fits
        int[] bitCount = { 0 };
        Runnable flush = () -> { if (bitCount[0] > 0) out.write((int) (bitBuffer[0] & 0xff)); };
        java.util.function.IntConsumer emit = code -> {
            bitBuffer[0] |= (long) code << bitCount[0];
            bitCount[0] += codeSize[0];
            while (bitCount[0] >= 8) {
                out.write((int) (bitBuffer[0] & 0xff));
                bitBuffer[0] >>>= 8;
                bitCount[0] -= 8;
            }
        };
        // The encoder's dictionary runs one entry AHEAD of the decoder's, so
        // the width grows one entry later: right after adding code 2^codeSize.
        Runnable growIfDue = () -> {
            if (nextCode[0] - 1 == (1 << codeSize[0]) && codeSize[0] < 12) codeSize[0]++;
        };

        emit.accept(clearCode);
        if (indices.length == 0) {
            emit.accept(eoiCode);
            flush.run();
            return out.toByteArray();
        }

        int w = indices[0] & 0xff;
        for (int i = 1; i < indices.length; i++) {
            int c = indices[i] & 0xff;
            int key = (w << 8) | c;
            Integer found = dict.get(key);
            if (found != null) { w = found; continue; }
            emit.accept(w);
            dict.put(key, nextCode[0]++);
            growIfDue.run();
            w = c;
            if (nextCode[0] >= 4096) { // Dictionary full — reset like encoders do.
                emit.accept(clearCode);
                resetDict.run();
                w = c;
            }
        }
        emit.accept(w);
        emit.accept(eoiCode);
        flush.run();
        return out.toByteArray();
    }

    // ── Palette mapping ────────────────────────────────────────────────────

    /** Map RGBA to palette indices via exact cache + nearest RGB distance. */
    private static byte[] mapToPalette(byte[] rgba, List<Swatch> palette) {
        java.util.HashMap<Integer, Integer> cache = new java.util.HashMap<>();
        byte[] indices = new byte[rgba.length / 4];
        for (int i = 0; i < indices.length; i++) {
            int o = i * 4;
            int key = ((rgba[o] & 0xff) << 16) | ((rgba[o + 1] & 0xff) << 8) | (rgba[o + 2] & 0xff);
            Integer idx = cache.get(key);
            if (idx == null) {
                int best = 0;
                long bestDist = Long.MAX_VALUE;
                for (int p = 0; p < palette.size(); p++) {
                    int dr = (rgba[o] & 0xff) - palette.get(p).r;
                    int dg = (rgba[o + 1] & 0xff) - palette.get(p).g;
                    int db = (rgba[o + 2] & 0xff) - palette.get(p).b;
                    long dist = (long) dr * dr + (long) dg * dg + (long) db * db;
                    if (dist < bestDist) { bestDist = dist; best = p; }
                }
                idx = best;
                cache.put(key, idx);
            }
            indices[i] = (byte) idx.intValue();
        }
        return indices;
    }

    // ── Byte assembly ──────────────────────────────────────────────────────

    private static void u16le(ByteArrayOutputStream out, int n) {
        out.write(n & 0xff);
        out.write((n >> 8) & 0xff);
    }

    public static byte[] encodeGif(List<GifFrameInput> frames) {
        if (frames.isEmpty()) return new byte[0];

        // One shared palette, quantized from a down-sampled mix of all frames.
        ByteArrayOutputStream mixed = new ByteArrayOutputStream();
        for (GifFrameInput f : frames) {
            int total = f.rgba.length / 4;
            int stride = Math.max(1, total / 4096);
            for (int i = 0; i < total; i += stride) {
                int o = i * 4;
                // write(int) keeps only the low 8 bits, so signed bytes are safe.
                mixed.write(f.rgba[o]);
                mixed.write(f.rgba[o + 1]);
                mixed.write(f.rgba[o + 2]);
                mixed.write(f.rgba[o + 3]);
            }
        }
        List<Swatch> palette = extractPalette(mixed.toByteArray(), MAX_COLORS);
        if (palette.isEmpty()) return new byte[0];

        // Palette table padded to a power of two (min 2 entries).
        int tableBits = 1;
        while ((1 << tableBits) < palette.size()) tableBits++;
        int tableSize = 1 << tableBits;

        ByteArrayOutputStream out = new ByteArrayOutputStream();
        out.writeBytes("GIF89a".getBytes(java.nio.charset.StandardCharsets.ISO_8859_1));
        int width = frames.get(0).width(), height = frames.get(0).height();
        u16le(out, width);
        u16le(out, height);
        out.write(0x80 | (tableBits - 1)); // GCT flag + size
        out.write(0);                       // background color index
        out.write(0);                       // pixel aspect ratio
        for (int i = 0; i < tableSize; i++) {
            Swatch sw = i < palette.size() ? palette.get(i) : null;
            out.write(sw != null ? sw.r() : 0);
            out.write(sw != null ? sw.g() : 0);
            out.write(sw != null ? sw.b() : 0);
        }

        // NETSCAPE loop forever.
        out.write(0x21); out.write(0xff); out.write(0x0b);
        out.writeBytes("NETSCAPE2.0".getBytes(java.nio.charset.StandardCharsets.ISO_8859_1));
        out.write(0x03); out.write(0x01); out.write(0x00); out.write(0x00); out.write(0x00);

        int minCodeSize = Math.max(2, tableBits);
        for (GifFrameInput frame : frames) {
            // Graphic control extension: delay in centiseconds, no transparency.
            int cs = (int) Math.max(0, Math.min(0xffff, Math.round(frame.delayMs() / 10.0)));
            out.write(0x21); out.write(0xf9); out.write(0x04); out.write(0x00);
            u16le(out, cs);
            out.write(0x00); out.write(0x00);

            out.write(0x2c); // image descriptor
            u16le(out, 0); u16le(out, 0);
            u16le(out, frame.width()); u16le(out, frame.height());
            out.write(0x00); // no LCT, no interlace

            byte[] data = lzwEncode(minCodeSize, mapToPalette(frame.rgba(), palette));
            out.write(minCodeSize);
            for (int i = 0; i < data.length; i += 255) { // sub-blocks of <= 255
                int chunk = Math.min(255, data.length - i);
                out.write(chunk);
                out.write(data, i, chunk);
            }
            out.write(0x00); // block terminator
        }

        out.write(0x3b); // trailer
        return out.toByteArray();
    }

    public static void main(String[] args) {
        // Two 2×1 frames alternating red/blue and blue/red at 100 ms.
        byte[] f0 = { (byte) 200, 0, 0, (byte) 255, 0, 0, (byte) 200, (byte) 255 };
        byte[] f1 = { 0, 0, (byte) 200, (byte) 255, (byte) 200, 0, 0, (byte) 255 };
        byte[] gif = encodeGif(List.of(
                new GifFrameInput(2, 1, f0, 100),
                new GifFrameInput(2, 1, f1, 100)));
        System.out.println("encoded " + gif.length + " bytes");
        for (int i = 0; i < 6; i++) System.out.print((char) gif[i]);
        System.out.println();
    }
}