GIF Frame Extractor — Java source

// GIF Frame Extractor — decode a GIF byte stream into indexed frames.
//
// Language: Java (17+, 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.
//
// A from-scratch GIF87a/89a parser: signature + logical screen descriptor
// (canvas size, global color table), extension blocks (frame delay,
// transparency, NETSCAPE loop count), and LZW image data decompressed to
// palette indices — interlaced frames reordered to natural row order.
// Malformed input returns null (same contract as the TS reference).

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public final class GifFrameExtractor {

    /** One decoded image: a rect on the canvas plus its palette-index data. */
    public record GifFrame(int x, int y, int width, int height,
                           byte[] palette,       // RGB triplets; null = global.
                           byte[] indices,       // Pixel indices, natural row order.
                           int delayMs, int transparentIndex, int disposal) { }

    /** Whole-file result: screen size, frames, palettes, loop count. */
    public record GifResult(int width, int height, List<GifFrame> frames,
                            byte[] globalPalette,
                            int loopCount) { } // 0 = forever, -1 when absent.

    // ── GIF LZW decompression ─────────────────────────────────────────────

    /** Read one code LSB-first; returns EOI on truncation, like the TS decoder. */
    private static int readCode(byte[] data, int[] bitPos, int codeSize, int eoiCode) {
        if ((bitPos[0] + codeSize) >>> 3 > data.length) return eoiCode;
        int code = 0;
        for (int i = 0; i < codeSize; i++) {
            int byteIdx = (bitPos[0] + i) >>> 3;
            if (byteIdx >= data.length) return eoiCode;
            code |= ((data[byteIdx] >>> ((bitPos[0] + i) & 7)) & 1) << i;
        }
        bitPos[0] += codeSize;
        return code;
    }

    /** Emit a code's chain; returns the chain's FIRST byte (needed for KwKwK). */
    private static int emitChain(int code, int[] prefix, int[] suffix,
                                 int[] first, List<Integer> out) {
        int[] stack = new int[4096];
        int n = 0, c = code;
        while (c >= 0) { stack[n++] = suffix[c]; c = prefix[c]; }
        for (int i = n - 1; i >= 0; i--) out.add(stack[i]);
        return stack[n - 1];
    }

    /** minCodeSize 2-8, clear-code resets, growing codes — same contract as TS. */
    public static byte[] lzwDecode(int minCodeSize, byte[] data) {
        int clearCode = 1 << minCodeSize, eoiCode = clearCode + 1;
        int codeSize = minCodeSize + 1, nextCode = eoiCode + 1;
        // Dictionary as (prefix, suffix, first-byte) triples, reset per clear.
        int[] prefix = new int[4096], suffix = new int[4096], first = new int[4096];
        List<Integer> out = new ArrayList<>();
        int[] bitPos = {0};
        int prev = -1;
        for (;;) {
            int code = readCode(data, bitPos, codeSize, eoiCode);
            if (code == eoiCode) break;
            if (code == clearCode) {
                for (int i = 0; i < clearCode; i++) { prefix[i] = -1; suffix[i] = i; first[i] = i; }
                nextCode = eoiCode + 1; codeSize = minCodeSize + 1;
                prev = -1; continue;
            }
            if (prev == -1) {
                if (code >= clearCode) break; // First code after clear is a literal.
                emitChain(code, prefix, suffix, first, out); prev = code; continue;
            }
            if (code > nextCode) break;       // Invalid — stop like browsers do.
            // KwKwK: a code one ahead of the dictionary is prev + first(prev).
            int emittedFirst;
            if (code == nextCode) {
                emittedFirst = emitChain(prev, prefix, suffix, first, out);
                out.add(first[prev]);
                emittedFirst = first[prev];
            } else {
                emittedFirst = emitChain(code, prefix, suffix, first, out);
            }
            if (nextCode < 4096) { // Table full: TS silently no-ops this write.
                prefix[nextCode] = prev; suffix[nextCode] = emittedFirst;
                first[nextCode] = first[prev];
                nextCode++;
                if (nextCode == (1 << codeSize) && codeSize < 12) codeSize++;
            }
            prev = code;
        }
        byte[] bytes = new byte[out.size()];
        for (int i = 0; i < bytes.length; i++) bytes[i] = (byte) out.get(i).intValue();
        return bytes;
    }

    // ── Interlace ──────────────────────────────────────────────────────────

    /** Reorder interlaced rows into natural order; identity for short frames. */
    public static byte[] deInterlace(byte[] indices, int width, int height) {
        if (height < 4 || width == 0) return indices;
        byte[] out = new byte[indices.length];
        int src = 0; // Stored pass-by-pass: four passes, starts/steps below.
        int[][] passes = { {0, 8}, {4, 8}, {2, 4}, {1, 2} };
        for (int[] p : passes) {
            for (int row = p[0]; row < height; row += p[1]) {
                System.arraycopy(indices, src, out, row * width, width);
                src += width;
            }
        }
        return out;
    }

    // ── Whole-GIF parse ────────────────────────────────────────────────────

    private static int le16(byte[] b, int p) { return (b[p] & 0xff) | ((b[p + 1] & 0xff) << 8); }

    /** Concatenate a sub-block chain; null on truncation. */
    private static byte[] readSubBlocks(byte[] b, int[] pos) {
        List<byte[]> chunks = new ArrayList<>();
        int total = 0;
        for (;;) {
            if (pos[0] >= b.length) return null;
            int size = b[pos[0]++] & 0xff;
            if (size == 0) break; // Terminator ends the chain.
            if (pos[0] + size > b.length) return null;
            chunks.add(Arrays.copyOfRange(b, pos[0], pos[0] + size));
            total += size;
            pos[0] += size;
        }
        byte[] out = new byte[total];
        int o = 0;
        for (byte[] c : chunks) { System.arraycopy(c, 0, out, o, c.length); o += c.length; }
        return out;
    }

    /** Parse signature, screen descriptor, extensions, and all frames. */
    public static GifResult decodeGif(byte[] bytes) {
        if (bytes.length < 13) return null;
        String magic = new String(bytes, 0, 6, java.nio.charset.StandardCharsets.US_ASCII);
        if (!magic.equals("GIF87a") && !magic.equals("GIF89a")) return null;
        // Logical screen descriptor: canvas size, flags, optional global palette.
        int[] pos = {6};
        int width = le16(bytes, pos[0]), height = le16(bytes, pos[0] + 2);
        int packed = bytes[pos[0] + 4] & 0xff;
        pos[0] += 7; // Skip bg color + aspect ratio.
        byte[] globalPalette = null;
        if ((packed & 0x80) != 0) {
            int n = (2 << (packed & 7)) * 3;
            if (pos[0] + n > bytes.length) return null;
            globalPalette = Arrays.copyOfRange(bytes, pos[0], pos[0] + n);
            pos[0] += n;
        }
        List<GifFrame> frames = new ArrayList<>();
        int loopCount = -1; // Absent until a NETSCAPE block says otherwise.
        int delayMs = 0, transparentIndex = -1, disposal = 0;

        for (;;) {
            if (pos[0] >= bytes.length) return null;
            int block = bytes[pos[0]++] & 0xff;
            if (block == 0x3b) break; // trailer
            if (block == 0x21) {      // Extension: graphic control / NETSCAPE / skip.
                if (pos[0] >= bytes.length) return null;
                int label = bytes[pos[0]++] & 0xff;
                if (label == 0xf9) {
                    byte[] gce = readSubBlocks(bytes, pos);
                    if (gce == null || gce.length < 4) return null;
                    disposal = (gce[0] >> 2) & 7;
                    delayMs = le16(gce, 1) * 10;
                    transparentIndex = (gce[0] & 1) != 0 ? gce[3] & 0xff : -1;
                } else if (label == 0xff) {
                    byte[] app = readSubBlocks(bytes, pos);
                    // Concatenated: 11-byte name, then id 1 + loop lo/hi.
                    if (app != null && app.length >= 14 && app[11] == 1
                            && new String(app, 0, 11,
                                          java.nio.charset.StandardCharsets.US_ASCII)
                                   .equals("NETSCAPE2.0"))
                        loopCount = le16(app, 12);
                } else if (readSubBlocks(bytes, pos) == null) {
                    return null;
                }
                continue;
            }
            if (block == 0x2c) { // Image descriptor: rect, local palette, LZW data.
                if (pos[0] + 9 > bytes.length) return null;
                int x = le16(bytes, pos[0]), y = le16(bytes, pos[0] + 2);
                int w = le16(bytes, pos[0] + 4), h = le16(bytes, pos[0] + 6);
                int ip = bytes[pos[0] + 8] & 0xff;
                pos[0] += 9; // Descriptor is 9 bytes: x, y, w, h, packed flags.
                byte[] palette = null;
                if ((ip & 0x80) != 0) {
                    int n = (2 << (ip & 7)) * 3;
                    if (pos[0] + n > bytes.length) return null;
                    palette = Arrays.copyOfRange(bytes, pos[0], pos[0] + n);
                    pos[0] += n;
                }
                if (pos[0] >= bytes.length) return null;
                int minCodeSize = bytes[pos[0]++] & 0xff;
                // LZW payload must be a complete sub-block chain.
                byte[] data = readSubBlocks(bytes, pos);
                if (data == null) return null;
                byte[] indices = lzwDecode(minCodeSize, data);
                if ((ip & 0x40) != 0) indices = deInterlace(indices, w, h);
                frames.add(new GifFrame(x, y, w, h, palette, indices,
                                        delayMs, transparentIndex, disposal));
                delayMs = 0; transparentIndex = -1; disposal = 0;
                continue;
            }
            return null; // Unknown block type — bail.
        }
        return new GifResult(width, height, frames, globalPalette, loopCount);
    }

    public static void main(String[] args) {
        // 2×1 GIF89a: 2-color global palette (red, blue), one frame, pixels [0,1].
        byte[] gif = {
            'G','I','F','8','9','a', 0x02,0x00, 0x01,0x00, (byte)0x80, 0x00, 0x00,
            (byte)0xff,0x00,0x00, 0x00,0x00,(byte)0xff,
            0x2c, 0x00,0x00, 0x00,0x00, 0x02,0x00, 0x01,0x00, 0x00,
            0x02, 0x02, 0x44,0x0a, 0x00, 0x3b
        };
        GifResult res = decodeGif(gif);
        if (res == null) { System.err.println("malformed GIF"); return; }
        System.out.printf("%dx%d, %d frame(s), loop=%d%n",
            res.width(), res.height(), res.frames().size(), res.loopCount());
        for (int i = 0; i < res.frames().size(); i++) {
            GifFrame f = res.frames().get(i);
            StringBuilder idx = new StringBuilder();
            for (int j = 0; j < f.indices().length; j++)
                idx.append(j > 0 ? ", " : "").append(f.indices()[j] & 0xff);
            System.out.printf("frame %d: %dx%d at (%d,%d), delay %dms, indices [%s]%n",
                i, f.width(), f.height(), f.x(), f.y(), f.delayMs(), idx);
        }
    }

    private GifFrameExtractor() { }
}