Video to GIF Converter — C++ source

// Video to GIF Converter — C++20 (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.

#include <algorithm>
#include <cstdint>
#include <span>
#include <unordered_map>
#include <vector>

namespace gif_encode {

struct Pixel { std::uint8_t r, g, b; };
struct Swatch { std::uint8_t r, g, b; std::uint32_t population; };

struct GifFrameInput {
    int width = 0;
    int height = 0;
    std::span<const std::uint8_t> rgba; // RGBA, 4 bytes/pixel, top-left origin
    int delayMs = 0;                    // frame delay in ms (stored as centiseconds)
};

// ------------------------------------------------------ palette (median cut) --

// Per-channel spread of a pixel bucket.
struct Spread { int r, g, b; };

Spread bounds(const std::vector<Pixel>& bucket) {
    int mn[3] = {255, 255, 255}, mx[3] = {0, 0, 0};
    for (const Pixel& p : bucket) {
        const int v[3] = {p.r, p.g, p.b};
        for (int c = 0; c < 3; c++) {
            if (v[c] < mn[c]) mn[c] = v[c];
            if (v[c] > mx[c]) mx[c] = v[c];
        }
    }
    return Spread{mx[0] - mn[0], mx[1] - mn[1], mx[2] - mn[2]};
}

// Split a bucket at the median of its widest channel (ties prefer r, then g —
// mirroring the TS reduce). std::stable_sort keeps equal pixels in sampling
// order, matching TS sort(), so the split stays deterministic.
std::vector<std::vector<Pixel>> splitBucket(std::vector<Pixel> bucket) {
    Spread s = bounds(bucket);
    int channel = s.g > s.r ? 1 : 0;
    if (s.b > (channel == 0 ? s.r : s.g)) channel = 2;
    std::stable_sort(bucket.begin(), bucket.end(), [channel](const Pixel& a, const Pixel& b) {
        const int x[3] = {a.r, a.g, a.b}, y[3] = {b.r, b.g, b.b};
        return x[channel] < y[channel];
    });
    size_t mid = bucket.size() / 2;
    return {{bucket.begin(), bucket.begin() + mid}, {bucket.begin() + mid, bucket.end()}};
}

// Median-cut quantization: split the widest-range bucket until maxColors.
// Populous colors get low indices — sort by population, descending.
std::vector<Swatch> extractPalette(std::span<const std::uint8_t> rgba, int maxColors) {
    size_t total = rgba.size() / 4;
    std::vector<Pixel> pixels;
    size_t stride = total / 16384; // bounded samples
    if (stride < 1) stride = 1;
    for (size_t i = 0; i < total; i += stride) {
        const std::uint8_t* o = rgba.data() + i * 4;
        if (o[3] > 0) pixels.push_back(Pixel{o[0], o[1], o[2]}); // skip transparent
    }
    if (pixels.empty()) return {};

    std::vector<std::vector<Pixel>> buckets{std::move(pixels)};
    while ((int)buckets.size() < maxColors) {
        int best = -1, bestRange = 1; // range 1 (duplicates only) never splits
        for (size_t i = 0; i < buckets.size(); i++) {
            Spread s = bounds(buckets[i]);
            int range = std::max({s.r, s.g, s.b});
            if (range > bestRange) { bestRange = range; best = (int)i; }
        }
        if (best < 0) break;
        std::vector<std::vector<Pixel>> halves = splitBucket(std::move(buckets[best]));
        buckets.erase(buckets.begin() + best);
        for (auto& h : halves) {
            if (!h.empty()) buckets.push_back(std::move(h));
        }
    }

    std::vector<Swatch> out;
    for (const std::vector<Pixel>& b : buckets) {
        if (b.empty()) continue;
        std::uint64_t sum[3] = {0, 0, 0};
        for (const Pixel& p : b) { sum[0] += p.r; sum[1] += p.g; sum[2] += p.b; }
        // Rounded channel average, exactly like Math.round(sum / n).
        out.push_back(Swatch{
            std::uint8_t((sum[0] + b.size() / 2) / b.size()),
            std::uint8_t((sum[1] + b.size() / 2) / b.size()),
            std::uint8_t((sum[2] + b.size() / 2) / b.size()),
            std::uint32_t(b.size())});
    }
    std::stable_sort(out.begin(), out.end(), [](const Swatch& a, const Swatch& b) {
        return a.population > b.population;
    });
    return out;
}

// ---------------------------------------------------------- palette mapping --

// Map RGBA pixels to palette indices: exact-match cache, else nearest RGB.
// unordered_map is safe here — only lookups, never iteration, so the
// hash-order nondeterminism that usually bites C++ ports cannot.
std::vector<std::uint8_t> mapToPalette(std::span<const std::uint8_t> rgba,
                                       const std::vector<Swatch>& palette) {
    size_t total = rgba.size() / 4;
    std::unordered_map<std::uint32_t, std::uint8_t> cache;
    std::vector<std::uint8_t> indices(total);
    for (size_t i = 0; i < total; i++) {
        const std::uint8_t* o = rgba.data() + i * 4;
        std::uint32_t key = (std::uint32_t(o[0]) << 16) | (std::uint32_t(o[1]) << 8) | o[2];
        auto found = cache.find(key);
        if (found != cache.end()) { indices[i] = found->second; continue; }
        size_t best = 0;
        long bestDist = 1L << 30;
        for (size_t p = 0; p < palette.size(); p++) {
            long dr = o[0] - palette[p].r, dg = o[1] - palette[p].g, db = o[2] - palette[p].b;
            long dist = dr * dr + dg * dg + db * db;
            if (dist < bestDist) { bestDist = dist; best = p; }
        }
        cache.emplace(key, std::uint8_t(best));
        indices[i] = std::uint8_t(best);
    }
    return indices;
}

// ------------------------------------------------------------------- LZW --

// LZW compression (GIF variant): pack codes LSB-first at the current width.
// Dictionary is (prefixCode, byte) -> code, keyed numerically in a flat u32.
std::vector<std::uint8_t> lzwEncode(int minCodeSize, std::span<const std::uint8_t> indices) {
    int clearCode = 1 << minCodeSize;
    int eoiCode = clearCode + 1;
    int codeSize = minCodeSize + 1;
    int nextCode = eoiCode + 1;

    std::unordered_map<std::uint32_t, int> dict;
    auto resetDict = [&] {
        dict.clear();
        nextCode = eoiCode + 1;
        codeSize = minCodeSize + 1;
    };

    std::vector<std::uint8_t> out;
    std::uint32_t bitBuffer = 0;
    int bitCount = 0;
    // GIF packs codes LSB-first — the opposite bit order from PNG's deflate.
    auto emit = [&](int code) {
        bitBuffer |= std::uint32_t(code) << bitCount;
        bitCount += codeSize;
        while (bitCount >= 8) {
            out.push_back(std::uint8_t(bitBuffer & 0xff));
            bitBuffer >>= 8;
            bitCount -= 8;
        }
    };
    auto growIfDue = [&] {
        // The encoder's dictionary runs one entry AHEAD of the decoder's (its
        // add for (w,c) is only constructible on the decoder's NEXT read), so
        // the width grows one entry later: right after adding code 2^codeSize.
        if (nextCode - 1 == (1 << codeSize) && codeSize < 12) codeSize++;
    };

    emit(clearCode);
    if (indices.empty()) {
        emit(eoiCode);
        if (bitCount > 0) out.push_back(std::uint8_t(bitBuffer & 0xff));
        return out;
    }

    int w = indices[0];
    for (size_t i = 1; i < indices.size(); i++) {
        std::uint8_t c = indices[i];
        std::uint32_t key = (std::uint32_t(w) << 8) | c;
        auto found = dict.find(key);
        if (found != dict.end()) { w = found->second; continue; }
        emit(w);
        dict.emplace(key, nextCode++);
        growIfDue();
        w = c;
        if (nextCode >= 4096) {
            // Dictionary full — reset like encoders do (trap: the clear code
            // must be emitted at the OLD width, before resetting).
            emit(clearCode);
            resetDict();
            w = c;
        }
    }
    emit(w);
    emit(eoiCode);
    if (bitCount > 0) out.push_back(std::uint8_t(bitBuffer & 0xff));
    return out;
}

// -------------------------------------------------------- byte assembly --

std::vector<std::uint8_t> encodeGif(std::span<const GifFrameInput> frames, int maxColors = 128) {
    if (maxColors > 256) maxColors = 256;
    if (frames.empty()) return {};

    // One shared palette, quantized from a down-sampled mix of all frames.
    std::vector<std::uint8_t> mixed;
    for (const GifFrameInput& f : frames) {
        size_t total = f.rgba.size() / 4;
        size_t stride = total / 4096;
        if (stride < 1) stride = 1;
        for (size_t i = 0; i < total; i += stride) {
            const std::uint8_t* o = f.rgba.data() + i * 4;
            mixed.insert(mixed.end(), o, o + 4);
        }
    }
    std::vector<Swatch> palette = extractPalette(mixed, maxColors);
    if (palette.empty()) return {};

    // Palette table padded to a power of two (min 2 entries); the GCT size
    // field stores bits-1, so a 2-color table is written as 0.
    int tableBits = 1;
    while ((1 << tableBits) < (int)palette.size()) tableBits++;
    size_t tableSize = size_t(1) << tableBits;

    std::vector<std::uint8_t> out;
    auto pushAscii = [&](std::string_view s) {
        for (char ch : s) out.push_back(std::uint8_t(ch));
    };
    auto u16le = [&](int n) {
        out.push_back(std::uint8_t(n & 0xff));
        out.push_back(std::uint8_t((n >> 8) & 0xff));
    };

    pushAscii("GIF89a");
    u16le(frames[0].width);
    u16le(frames[0].height);
    out.push_back(std::uint8_t(0x80 | (tableBits - 1))); // GCT flag + size
    out.push_back(0); // background color index
    out.push_back(0); // pixel aspect ratio
    for (size_t i = 0; i < tableSize; i++) {
        const Swatch& sw = i < palette.size() ? palette[i] : Swatch{0, 0, 0, 0};
        out.push_back(sw.r);
        out.push_back(sw.g);
        out.push_back(sw.b);
    }

    // NETSCAPE loop forever.
    out.push_back(0x21); out.push_back(0xff); out.push_back(0x0b);
    pushAscii("NETSCAPE2.0");
    out.push_back(0x03); out.push_back(0x01); out.push_back(0x00); out.push_back(0x00); out.push_back(0x00);

    int minCodeSize = std::max(2, tableBits); // GIF spec floor: 2
    for (const GifFrameInput& frame : frames) {
        // Graphic control extension: delay in centiseconds, no transparency.
        int cs = std::clamp((frame.delayMs + 5) / 10, 0, 0xffff); // rounded ms/10
        out.push_back(0x21); out.push_back(0xf9); out.push_back(0x04); out.push_back(0x00);
        u16le(cs);
        out.push_back(0x00); out.push_back(0x00);

        out.push_back(0x2c); // image separator
        u16le(0); u16le(0);
        u16le(frame.width);
        u16le(frame.height);
        out.push_back(0x00); // no local color table, no interlace

        std::vector<std::uint8_t> indices = mapToPalette(frame.rgba, palette);
        std::vector<std::uint8_t> data = lzwEncode(minCodeSize, indices);
        out.push_back(std::uint8_t(minCodeSize));
        for (size_t i = 0; i < data.size(); i += 255) { // sub-blocked every 255 bytes
            size_t n = std::min<size_t>(255, data.size() - i);
            out.push_back(std::uint8_t(n));
            out.insert(out.end(), data.begin() + i, data.begin() + i + n);
        }
        out.push_back(0x00); // block terminator
    }

    out.push_back(0x3b); // trailer
    return out;
}

} // namespace gif_encode

// Usage: encodeGif(frames, 128) -> GIF89a bytes — one shared palette,
// one image block per frame.