GIF Frame Extractor — C# source

// GIF Frame Extractor — decode a GIF byte stream into indexed frames.
//
// Language: C# (.NET 8), 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).

using System;
using System.Collections.Generic;
using System.Text;

namespace Gif;

/// <summary>One decoded image: a rect on the canvas plus palette-index data.</summary>
public sealed class GifFrame
{
    public required int X { get; init; }
    public required int Y { get; init; }
    public required int Width { get; init; }
    public required int Height { get; init; }

    /// <summary>RGB triplets; null = use the global color table.</summary>
    public byte[]? Palette { get; init; }

    /// <summary>Pixel indices in natural row order.</summary>
    public required byte[] Indices { get; init; }

    public int DelayMs { get; init; }
    public int TransparentIndex { get; init; } // -1 = opaque.
    public int Disposal { get; init; }
}

/// <summary>Whole-file result: screen size, frames, palettes, loop count.</summary>
public sealed class GifResult
{
    public required int Width { get; init; }
    public required int Height { get; init; }      // Logical screen size.
    public required List<GifFrame> Frames { get; init; }
    public byte[]? GlobalPalette { get; init; }

    /// <summary>NETSCAPE loop; 0 = forever, null when absent.</summary>
    public int? LoopCount { get; init; }
}

public static class GifFrameExtractor
{
    // ── GIF LZW decompression ─────────────────────────────────────────────

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

    /// <summary>Emit a code's chain; returns the chain's FIRST byte (for KwKwK).</summary>
    private static int EmitChain(int code, int[] prefix, int[] suffix, List<byte> output)
    {
        var stack = new byte[4096];
        int n = 0, c = code;
        while (c >= 0) { stack[n++] = (byte)suffix[c]; c = prefix[c]; }
        for (int i = n - 1; i >= 0; i--) output.Add(stack[i]);
        return stack[n - 1];
    }

    /// <summary>minCodeSize 2-8, clear-code resets, growing codes — same contract as TS.</summary>
    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.
        var prefix = new int[4096];
        var suffix = new int[4096];
        var first = new int[4096];
        var output = new List<byte>();
        int bitPos = 0, prev = -1;
        for (;;)
        {
            int code = ReadCode(data, ref 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, output);
                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)
            {
                EmitChain(prev, prefix, suffix, output);
                output.Add((byte)first[prev]);
                emittedFirst = first[prev];
            }
            else
            {
                emittedFirst = EmitChain(code, prefix, suffix, output);
            }
            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;
        }
        return output.ToArray();
    }

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

    /// <summary>Reorder interlaced rows into natural order; identity for short frames.</summary>
    public static byte[] DeInterlace(byte[] indices, int width, int height)
    {
        if (height < 4 || width == 0) return indices;
        var output = new byte[indices.Length];
        int src = 0; // Stored pass-by-pass: four passes, starts/steps below.
        int[][] passes = { new[] { 0, 8 }, new[] { 4, 8 }, new[] { 2, 4 }, new[] { 1, 2 } };
        foreach (var p in passes)
        {
            for (int row = p[0]; row < height; row += p[1])
            {
                Array.Copy(indices, src, output, row * width, width);
                src += width;
            }
        }
        return output;
    }

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

    private static int Le16(byte[] b, int p) => b[p] | (b[p + 1] << 8);

    /// <summary>Concatenate a sub-block chain; null on truncation.</summary>
    private static byte[]? ReadSubBlocks(byte[] b, ref int pos)
    {
        var chunks = new List<byte[]>();
        int total = 0;
        for (;;)
        {
            if (pos >= b.Length) return null;
            int size = b[pos++];
            if (size == 0) break; // Terminator ends the chain.
            if (pos + size > b.Length) return null;
            var chunk = new byte[size];
            Array.Copy(b, pos, chunk, 0, size);
            chunks.Add(chunk);
            total += size;
            pos += size;
        }
        var output = new byte[total];
        int offset = 0;
        foreach (var chunk in chunks)
        {
            Array.Copy(chunk, 0, output, offset, chunk.Length);
            offset += chunk.Length;
        }
        return output;
    }

    /// <summary>Parse signature, screen descriptor, extensions, and all frames.</summary>
    public static GifResult? DecodeGif(byte[] bytes)
    {
        if (bytes.Length < 13) return null;
        var magic = Encoding.ASCII.GetString(bytes, 0, 6);
        if (magic != "GIF87a" && magic != "GIF89a") return null;
        // Logical screen descriptor: canvas size, flags, optional global palette.
        int pos = 6;
        int width = Le16(bytes, pos), height = Le16(bytes, pos + 2);
        int packed = bytes[pos + 4];
        pos += 7; // Skip bg color + aspect ratio.
        byte[]? globalPalette = null;
        if ((packed & 0x80) != 0)
        {
            int n = (2 << (packed & 7)) * 3;
            if (pos + n > bytes.Length) return null;
            globalPalette = new byte[n];
            Array.Copy(bytes, pos, globalPalette, 0, n);
            pos += n;
        }
        var frames = new List<GifFrame>();
        int? loopCount = null; // Absent until a NETSCAPE block says otherwise.
        int delayMs = 0, transparentIndex = -1, disposal = 0;

        for (;;)
        {
            if (pos >= bytes.Length) return null;
            int block = bytes[pos++];
            if (block == 0x3b) break; // trailer
            if (block == 0x21)        // Extension: graphic control / NETSCAPE / skip.
            {
                if (pos >= bytes.Length) return null;
                int label = bytes[pos++];
                if (label == 0xf9)
                {
                    byte[]? gce = ReadSubBlocks(bytes, ref pos);
                    if (gce is null || gce.Length < 4) return null;
                    disposal = (gce[0] >> 2) & 7;
                    delayMs = Le16(gce, 1) * 10;
                    transparentIndex = (gce[0] & 1) != 0 ? gce[3] : -1;
                }
                else if (label == 0xff)
                {
                    byte[]? app = ReadSubBlocks(bytes, ref pos);
                    // Concatenated: 11-byte name, then id 1 + loop lo/hi.
                    if (app is not null && app.Length >= 14 && app[11] == 1
                        && Encoding.ASCII.GetString(app, 0, 11) == "NETSCAPE2.0")
                        loopCount = Le16(app, 12);
                }
                else if (ReadSubBlocks(bytes, ref pos) is null)
                {
                    return null;
                }
                continue;
            }
            if (block == 0x2c) // Image descriptor: rect, local palette, LZW data.
            {
                if (pos + 9 > bytes.Length) return null;
                int x = Le16(bytes, pos), y = Le16(bytes, pos + 2);
                int w = Le16(bytes, pos + 4), h = Le16(bytes, pos + 6);
                int ip = bytes[pos + 8];
                pos += 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 + n > bytes.Length) return null;
                    palette = new byte[n];
                    Array.Copy(bytes, pos, palette, 0, n);
                    pos += n;
                }
                if (pos >= bytes.Length) return null;
                int minCodeSize = bytes[pos++];
                // LZW payload must be a complete sub-block chain.
                byte[]? data = ReadSubBlocks(bytes, ref pos);
                if (data is null) return null;
                byte[] indices = LzwDecode(minCodeSize, data);
                if ((ip & 0x40) != 0) indices = DeInterlace(indices, w, h);
                frames.Add(new GifFrame
                {
                    X = x, Y = y, Width = w, Height = h,
                    Palette = palette, Indices = indices,
                    DelayMs = delayMs, TransparentIndex = transparentIndex,
                    Disposal = disposal,
                });
                delayMs = 0; transparentIndex = -1; disposal = 0;
                continue;
            }
            return null; // Unknown block type — bail.
        }
        return new GifResult
        {
            Width = width, Height = height, Frames = frames,
            GlobalPalette = globalPalette, LoopCount = loopCount,
        };
    }
}

public static class GifFrameExtractorDemo
{
    public static void Main()
    {
        // 2×1 GIF89a: 2-color global palette (red, blue), one frame, pixels [0,1].
        byte[] gif =
        {
            0x47, 0x49, 0x46, 0x38, 0x39, 0x61,          // "GIF89a"
            0x02, 0x00, 0x01, 0x00, 0x80, 0x00, 0x00,    // LSD: 2×1, GCT, 2 entries
            0xff, 0x00, 0x00, 0x00, 0x00, 0xff,          // GCT: red, blue
            0x2c,                                        // image descriptor
            0x00, 0x00, 0x00, 0x00, 0x02, 0x00, 0x01, 0x00, 0x00,
            0x02,                                        // LZW min code size
            0x02, 0x44, 0x0a, 0x00,                      // sub-block + terminator
            0x3b                                         // trailer
        };
        GifResult? res = GifFrameExtractor.DecodeGif(gif);
        if (res is null)
        {
            Console.Error.WriteLine("malformed GIF");
            return;
        }
        Console.WriteLine(
            $"{res.Width}x{res.Height}, {res.Frames.Count} frame(s), loop={res.LoopCount?.ToString() ?? "∞"}");
        for (int i = 0; i < res.Frames.Count; i++)
        {
            GifFrame f = res.Frames[i];
            string idx = string.Join(", ", f.Indices);
            Console.WriteLine(
                $"frame {i}: {f.Width}x{f.Height} at ({f.X},{f.Y}), delay {f.DelayMs}ms, indices [{idx}]");
        }
    }
}