Video to GIF Converter — C source

// Video to GIF Converter — C (C11, 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 <stdint.h>
#include <stdlib.h>
#include <string.h>

typedef struct { uint8_t r, g, b; } Pixel;
typedef struct { uint8_t r, g, b; uint32_t population; } Swatch;
typedef struct { int width, height; const uint8_t *rgba; int delay_ms; } GifFrameInput;

/* Growable byte buffer — the TS version pushes to a plain number[]. */
typedef struct { uint8_t *data; size_t len, cap; } Buf;
static void buf_reserve(Buf *b, size_t extra) {
    if (b->len + extra > b->cap) {
        while (b->len + extra > b->cap) b->cap = b->cap ? b->cap * 2 : 256;
        b->data = realloc(b->data, b->cap);
    }
}
static void push(Buf *b, uint8_t v) { buf_reserve(b, 1); b->data[b->len++] = v; }
static void push_n(Buf *b, const uint8_t *src, size_t n) { buf_reserve(b, n); memcpy(b->data + b->len, src, n); b->len += n; }
static void push_ascii(Buf *b, const char *s) { while (*s) push(b, (uint8_t)*s++); }
static void u16le(Buf *b, int n) { push(b, (uint8_t)(n & 0xff)); push(b, (uint8_t)((n >> 8) & 0xff)); }

/* Per-channel spread of a pixel bucket. */
static void bounds(const Pixel *p, size_t n, int spread[3]) {
    int mn[3] = {255, 255, 255}, mx[3] = {0, 0, 0};
    for (size_t i = 0; i < n; i++) {
        const uint8_t v[3] = {p[i].r, p[i].g, p[i].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]; }
    }
    for (int c = 0; c < 3; c++) spread[c] = mx[c] - mn[c];
}

/* qsort's comparator can't take the channel — keep it at file scope (display
 * source, single-threaded). Pixel is three uint8_t, so index it as raw bytes.
 * qsort is not stable, unlike TS sort(); ties don't move the bucket average. */
static int g_channel;
static int cmp_channel(const void *a, const void *b) {
    const uint8_t *x = a, *y = b;
    return (int)x[g_channel] - (int)y[g_channel];
}

/* Split a bucket at the median of its widest channel. */
static void split_bucket(Pixel *p, size_t n, Pixel **halves, size_t *half_n) {
    int spread[3]; bounds(p, n, spread);
    g_channel = spread[1] > spread[0] ? 1 : 0;
    if (spread[2] > spread[g_channel]) g_channel = 2;
    qsort(p, n, sizeof *p, cmp_channel);
    halves[0] = p; half_n[0] = n / 2; halves[1] = p + n / 2; half_n[1] = n - n / 2;
}

/* Median-cut quantization: split the widest-range bucket until maxColors. */
static size_t extract_palette(const uint8_t *rgba, size_t rgba_len, int max_colors, Swatch *out) {
    size_t total = rgba_len / 4;
    Pixel *px = malloc((total ? total : 1) * sizeof *px);
    size_t npx = 0;
    size_t stride = total / 16384; if (stride < 1) stride = 1;
    for (size_t i = 0; i < total; i += stride) {
        const uint8_t *o = rgba + i * 4;
        if (o[3] > 0) px[npx++] = (Pixel){o[0], o[1], o[2]}; /* skip transparent */
    }
    if (npx == 0) { free(px); return 0; }

    Pixel *buckets[256]; size_t bucket_n[256]; int nb = 1;
    buckets[0] = px; bucket_n[0] = npx;
    while (nb < max_colors) {
        int best = -1, best_range = 1; /* range 1 (duplicates only) never splits */
        for (int i = 0; i < nb; i++) {
            int spread[3]; bounds(buckets[i], bucket_n[i], spread);
            int range = spread[0]; for (int c = 1; c < 3; c++) if (spread[c] > range) range = spread[c];
            if (range > best_range) { best_range = range; best = i; }
        }
        if (best < 0) break;
        Pixel *halves[2]; size_t half_n[2];
        split_bucket(buckets[best], bucket_n[best], halves, half_n);
        buckets[best] = halves[0]; bucket_n[best] = half_n[0];
        buckets[nb] = halves[1]; bucket_n[nb] = half_n[1]; nb++;
    }

    size_t n = 0;
    for (int i = 0; i < nb; i++) {
        if (bucket_n[i] == 0) continue;
        uint32_t sum[3] = {0, 0, 0};
        for (size_t j = 0; j < bucket_n[i]; j++) { sum[0] += buckets[i][j].r; sum[1] += buckets[i][j].g; sum[2] += buckets[i][j].b; }
        out[n++] = (Swatch){(uint8_t)((sum[0] + bucket_n[i] / 2) / bucket_n[i]),
                            (uint8_t)((sum[1] + bucket_n[i] / 2) / bucket_n[i]),
                            (uint8_t)((sum[2] + bucket_n[i] / 2) / bucket_n[i]), (uint32_t)bucket_n[i]};
    }
    free(px);
    /* populous colors get low indices — insertion sort by population, descending */
    for (size_t i = 1; i < n; i++) {
        Swatch s = out[i]; size_t j = i;
        while (j > 0 && out[j - 1].population < s.population) { out[j] = out[j - 1]; j--; }
        out[j] = s;
    }
    return n;
}

/* Map RGBA pixels to palette indices: exact-match cache, else nearest RGB.
 * Open addressing over the 24-bit packed RGB key; the `used` flag matters
 * because key 0 is a real color (black), not an empty slot. */
typedef struct { uint32_t key; uint8_t val; uint8_t used; } CacheSlot;

static uint8_t nearest(const Swatch *pal, size_t npal, uint8_t r, uint8_t g, uint8_t b) {
    size_t best = 0; long best_dist = 1L << 30;
    for (size_t p = 0; p < npal; p++) {
        int dr = r - pal[p].r, dg = g - pal[p].g, db = b - pal[p].b;
        long dist = (long)dr * dr + (long)dg * dg + (long)db * db;
        if (dist < best_dist) { best_dist = dist; best = p; }
    }
    return (uint8_t)best;
}

static uint8_t *map_to_palette(const uint8_t *rgba, size_t rgba_len, const Swatch *pal, size_t npal) {
    size_t total = rgba_len / 4;
    uint8_t *indices = malloc(total ? total : 1);
    enum { CACHE_SIZE = 1 << 16, CACHE_MASK = CACHE_SIZE - 1 };
    CacheSlot *cache = calloc(CACHE_SIZE, sizeof *cache);
    for (size_t i = 0; i < total; i++) {
        const uint8_t *o = rgba + i * 4;
        uint32_t key = ((uint32_t)o[0] << 16) | ((uint32_t)o[1] << 8) | o[2];
        size_t h = (key * 2654435761u) & CACHE_MASK; /* Knuth multiplicative hash */
        while (cache[h].used && cache[h].key != key) h = (h + 1) & CACHE_MASK;
        if (cache[h].used) { indices[i] = cache[h].val; continue; }
        uint8_t best = nearest(pal, npal, o[0], o[1], o[2]);
        cache[h] = (CacheSlot){key, best, 1};
        indices[i] = best;
    }
    free(cache);
    return indices;
}

/* LZW compression (GIF variant). Bit writer state kept in a struct — no nested
 * functions (GCC extension) so this stays portable C11. */
typedef struct {
    Buf *out;
    uint32_t bit_buffer;
    int bit_count, code_size;
} BitWriter;

static void emit(BitWriter *bw, int code) {
    /* GIF packs codes LSB-first — the opposite bit order from PNG's deflate. */
    bw->bit_buffer |= (uint32_t)code << bw->bit_count;
    bw->bit_count += bw->code_size;
    while (bw->bit_count >= 8) { push(bw->out, (uint8_t)(bw->bit_buffer & 0xff)); bw->bit_buffer >>= 8; bw->bit_count -= 8; }
}

static uint8_t *lzw_encode(int min_code_size, const uint8_t *indices, size_t n, size_t *out_len) {
    int clear_code = 1 << min_code_size, eoi_code = clear_code + 1;
    enum { DICT_SIZE = 1 << 13, DICT_MASK = DICT_SIZE - 1 };
    static const uint32_t NO_KEY = 0xffffffffu; /* a real key is only 24 bits */
    /* (prefixCode, byte) -> code; 8192 slots for at most ~4094 live entries */
    uint32_t *keys = malloc(DICT_SIZE * sizeof *keys);
    uint16_t *vals = malloc(DICT_SIZE * sizeof *vals);
    Buf out = {0};
    BitWriter bw = {&out, 0, 0, min_code_size + 1};
    int next_code = eoi_code + 1;

    emit(&bw, clear_code);
    if (n == 0) { emit(&bw, eoi_code); goto done; }

    for (int i = 0; i < DICT_SIZE; i++) keys[i] = NO_KEY;
    int w = indices[0];
    for (size_t i = 1; i < n; i++) {
        uint8_t c = indices[i];
        uint32_t key = ((uint32_t)w << 8) | c;
        uint32_t h = (key * 2654435761u) & DICT_MASK;
        while (keys[h] != NO_KEY && keys[h] != key) h = (h + 1) & DICT_MASK;
        if (keys[h] == key) { w = vals[h]; continue; }
        emit(&bw, w);
        keys[h] = key; vals[h] = (uint16_t)next_code; next_code++;
        /* Width lags one entry behind the dictionary: grow after adding 2^codeSize. */
        if (next_code - 1 == (1 << bw.code_size) && bw.code_size < 12) bw.code_size++;
        w = c;
        if (next_code >= 4096) { /* full — reset (trap: emit clear BEFORE continuing) */
            emit(&bw, clear_code);
            for (int k = 0; k < DICT_SIZE; k++) keys[k] = NO_KEY;
            next_code = eoi_code + 1; bw.code_size = min_code_size + 1;
            w = c;
        }
    }
    emit(&bw, w); emit(&bw, eoi_code);
done:
    if (bw.bit_count > 0) push(&out, (uint8_t)(bw.bit_buffer & 0xff));
    free(keys); free(vals);
    *out_len = out.len;
    return out.data;
}

uint8_t *encode_gif(const GifFrameInput *frames, size_t nframes, int max_colors, size_t *out_len) {
    if (nframes == 0) { *out_len = 0; return NULL; }

    /* One shared palette, quantized from a down-sampled mix of all frames. */
    Buf mixed = {0};
    for (size_t f = 0; f < nframes; f++) {
        size_t total = (size_t)frames[f].width * frames[f].height;
        size_t stride = total / 4096; if (stride < 1) stride = 1;
        for (size_t i = 0; i < total; i += stride)
            push_n(&mixed, frames[f].rgba + i * 4, 4);
    }
    Swatch *palette = malloc(256 * sizeof *palette);
    int cap = max_colors > 256 ? 256 : max_colors;
    size_t npal = extract_palette(mixed.data, mixed.len, cap, palette);
    free(mixed.data);
    if (npal == 0) { free(palette); *out_len = 0; return NULL; }

    /* 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 table_bits = 1;
    while ((1 << table_bits) < (int)npal) table_bits++;

    Buf out = {0};
    push_ascii(&out, "GIF89a");
    u16le(&out, frames[0].width); u16le(&out, frames[0].height);
    push(&out, (uint8_t)(0x80 | (table_bits - 1))); push(&out, 0); push(&out, 0); /* GCT flag + size; bg; aspect */
    for (int i = 0; i < (1 << table_bits); i++) {
        push(&out, i < (int)npal ? palette[i].r : 0);
        push(&out, i < (int)npal ? palette[i].g : 0);
        push(&out, i < (int)npal ? palette[i].b : 0);
    }
    push(&out, 0x21); push(&out, 0xff); push(&out, 0x0b); /* NETSCAPE loop-forever extension */
    push_ascii(&out, "NETSCAPE2.0");
    push(&out, 0x03); push(&out, 0x01); push(&out, 0x00); push(&out, 0x00); push(&out, 0x00);

    int min_code_size = table_bits > 2 ? table_bits : 2; /* GIF spec floor: 2 */
    for (size_t f = 0; f < nframes; f++) {
        int cs = frames[f].delay_ms / 10; /* delay, centiseconds */
        if (cs < 0) cs = 0; if (cs > 0xffff) cs = 0xffff;
        push(&out, 0x21); push(&out, 0xf9); push(&out, 0x04); push(&out, 0x00); /* graphic control ext */
        u16le(&out, cs); push(&out, 0x00); push(&out, 0x00);
        push(&out, 0x2c); u16le(&out, 0); u16le(&out, 0);
        u16le(&out, frames[f].width); u16le(&out, frames[f].height);
        push(&out, 0x00); /* no local color table, no interlace */
        size_t npx = (size_t)frames[f].width * frames[f].height;
        uint8_t *indices = map_to_palette(frames[f].rgba, npx * 4, palette, npal);
        size_t data_len; uint8_t *data = lzw_encode(min_code_size, indices, npx, &data_len);
        free(indices);
        push(&out, (uint8_t)min_code_size);
        for (size_t i = 0; i < data_len; i += 255) /* sub-blocked every 255 bytes */
            push_n(&out, data + i, data_len - i < 255 ? data_len - i : 255);
        free(data);
        push(&out, 0x00); /* block terminator */
    }
    push(&out, 0x3b); /* trailer */
    free(palette);
    *out_len = out.len;
    return out.data;
}

/* Usage: encode_gif(frames, n, 128, &len) -> GIF89a bytes — one shared palette,
 * one image block per frame. */