GIF Frame Extractor — C++ source

// GIF Frame Extractor — decode a GIF byte stream into indexed frames.
//
// Language: C++ (C++20), 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 std::nullopt (the TS `null` return analogue).

#include <array>
#include <cstdint>
#include <cstring>
#include <optional>
#include <vector>

#include <cstdio>

namespace gif {

struct GifFrame {
    int x = 0, y = 0, width = 0, height = 0;
    std::vector<uint8_t> palette;  // RGB triplets; empty = use the global one.
    std::vector<uint8_t> indices;  // Pixel indices in natural row order.
    int delayMs = 0, transparentIndex = -1, disposal = 0;
};

struct GifResult {
    int width = 0, height = 0;     // Logical screen size.
    std::vector<GifFrame> frames;
    std::vector<uint8_t> globalPalette;
    int loopCount = -1;            // NETSCAPE loop; 0 = forever, -1 when absent.
};

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

// Read one code LSB-first; returns EOI on truncation, like the TS decoder.
int readCode(const std::vector<uint8_t>& data, size_t& bitPos, int codeSize, int eoiCode) {
    if ((bitPos + codeSize) >> 3 > data.size()) return eoiCode;
    int code = 0;
    for (int i = 0; i < codeSize; i++) {
        size_t byteIdx = (bitPos + i) >> 3;
        if (byteIdx >= data.size()) return eoiCode;
        code |= ((data[byteIdx] >> ((bitPos + i) & 7)) & 1) << i;
    }
    bitPos += codeSize;
    return code;
}

// Emit a code's chain; returns the chain's FIRST byte (needed for KwKwK).
uint8_t emitChain(int code, const std::array<int, 4096>& prefix,
                  const std::array<uint8_t, 4096>& suffix, std::vector<uint8_t>& out) {
    std::array<uint8_t, 4096> stack;
    int n = 0, c = code;
    while (c >= 0) { stack[n++] = suffix[c]; c = prefix[c]; }
    for (int i = n - 1; i >= 0; i--) out.push_back(stack[i]);
    return stack[n - 1];
}

// minCodeSize 2-8, clear-code resets, growing codes — same contract as TS.
std::vector<uint8_t> lzwDecode(int minCodeSize, const std::vector<uint8_t>& 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.
    std::array<int, 4096> prefix{}, first{};
    std::array<uint8_t, 4096> suffix{};
    auto resetDict = [&] {
        for (int i = 0; i < clearCode; i++) { prefix[i] = -1; suffix[i] = i; first[i] = i; }
        nextCode = eoiCode + 1; codeSize = minCodeSize + 1;
    };
    resetDict();
    std::vector<uint8_t> out;
    size_t bitPos = 0;
    int prev = -1;
    for (;;) {
        int code = readCode(data, bitPos, codeSize, eoiCode);
        if (code == eoiCode) break;
        if (code == clearCode) { resetDict(); prev = -1; continue; }
        if (prev == -1) {
            if (code >= clearCode) break; // First code after clear is a literal.
            emitChain(code, prefix, suffix, 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).
        uint8_t emittedFirst = code == nextCode
            ? (emitChain(prev, prefix, suffix, out), out.push_back(first[prev]), first[prev])
            : emitChain(code, prefix, suffix, 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;
    }
    return out;
}

// Reorder interlaced rows into natural order; identity for short frames.
std::vector<uint8_t> deInterlace(std::vector<uint8_t> indices, int width, int height) {
    if (height < 4 || width == 0) return indices;
    std::vector<uint8_t> out(indices.size());
    size_t src = 0; // Stored pass-by-pass: four passes, starts/steps below.
    for (auto [start, step] : { std::pair<int, int>{0, 8}, {4, 8}, {2, 4}, {1, 2} }) {
        for (int row = start; row < height; row += step) {
            std::copy(indices.begin() + src, indices.begin() + src + width,
                      out.begin() + static_cast<size_t>(row) * width);
            src += width;
        }
    }
    return out;
}

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

int le16(const uint8_t* p) { return p[0] | (p[1] << 8); }

// Concatenate a sub-block chain; nullopt on truncation.
std::optional<std::vector<uint8_t>> readSubBlocks(const std::vector<uint8_t>& b, size_t& pos) {
    std::vector<uint8_t> out;
    for (;;) {
        if (pos >= b.size()) return std::nullopt;
        size_t size = b[pos++];
        if (size == 0) break; // Terminator ends the chain.
        if (pos + size > b.size()) return std::nullopt;
        out.insert(out.end(), b.begin() + pos, b.begin() + pos + size);
        pos += size;
    }
    return out;
}

// Parse signature, screen descriptor, extensions, and all frames.
std::optional<GifResult> decodeGif(const std::vector<uint8_t>& bytes) {
    if (bytes.size() < 13) return std::nullopt;
    if (std::memcmp(bytes.data(), "GIF87a", 6) != 0 &&
        std::memcmp(bytes.data(), "GIF89a", 6) != 0) return std::nullopt;
    // Logical screen descriptor: canvas size, flags, optional global palette.
    size_t pos = 6;
    GifResult res;
    res.width = le16(&bytes[pos]); res.height = le16(&bytes[pos + 2]);
    uint8_t packed = bytes[pos + 4]; pos += 7; // Skip bg color + aspect ratio.
    if (packed & 0x80) {
        size_t n = (2 << (packed & 7)) * 3;
        if (pos + n > bytes.size()) return std::nullopt;
        res.globalPalette.assign(bytes.begin() + pos, bytes.begin() + pos + n);
        pos += n;
    }
    int delayMs = 0, transparentIndex = -1, disposal = 0;

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

} // namespace gif

int main() {
    // 2×1 GIF89a: 2-color global palette (red, blue), one frame, pixels [0,1].
    std::vector<uint8_t> gif = {
        'G','I','F','8','9','a', 0x02,0x00, 0x01,0x00, 0x80, 0x00, 0x00,
        0xff,0x00,0x00, 0x00,0x00,0xff,
        0x2c, 0x00,0x00, 0x00,0x00, 0x02,0x00, 0x01,0x00, 0x00,
        0x02, 0x02, 0x44,0x0a, 0x00, 0x3b
    };
    auto res = gif::decodeGif(gif);
    if (!res) { std::fprintf(stderr, "malformed GIF\n"); return 1; }
    std::printf("%dx%d, %zu frame(s), loop=%d\n",
                res->width, res->height, res->frames.size(), res->loopCount);
    for (size_t i = 0; i < res->frames.size(); i++) {
        const auto& f = res->frames[i];
        std::printf("frame %zu: %dx%d at (%d,%d), delay %dms, indices [",
                    i, f.width, f.height, f.x, f.y, f.delayMs);
        for (size_t j = 0; j < f.indices.size(); j++)
            std::printf(j ? ", %d" : "%d", f.indices[j]);
        std::printf("]\n");
    }
    return 0;
}