GIF Frame Extractor — C source

/* GIF Frame Extractor — decode a GIF byte stream into indexed frames.
 *
 * Language: C (C11), 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 yields NULL (the TS `null` return analogue); the caller
 * frees results with gif_free(). */

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* ── Growable byte buffer (poor man's TS number[] / Uint8Array) ──────────── */

typedef struct { unsigned char *data; size_t len, cap; } Buf;

static int buf_push(Buf *b, unsigned char c) {
    if (b->len == b->cap) {
        size_t cap = b->cap ? b->cap * 2 : 256;
        unsigned char *p = realloc(b->data, cap);
        if (p == NULL) return 0;
        b->data = p; b->cap = cap;
    }
    b->data[b->len++] = c;
    return 1;
}

/* ── Result types ────────────────────────────────────────────────────────── */

typedef struct {
    int x, y, width, height;
    unsigned char *palette;      /* RGB triplets; NULL = use the global table. */
    size_t palette_len;
    unsigned char *indices;      /* Pixel indices in natural row order. */
    size_t indices_len;
    int delay_ms, transparent_index, disposal;
} GifFrame;

typedef struct {
    int width, height;           /* Logical screen size. */
    GifFrame *frames; size_t nframes;
    unsigned char *global_palette; size_t global_palette_len; /* NULL if absent. */
    int loop_count;              /* NETSCAPE loop; 0 = forever, -1 when absent. */
} GifResult;

void gif_free(GifResult *g) {
    if (g == NULL) return;
    for (size_t i = 0; i < g->nframes; i++) {
        free(g->frames[i].palette); free(g->frames[i].indices);
    }
    free(g->frames); free(g->global_palette);
    free(g);
}

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

/* Read one code LSB-first; returns EOI on truncation, like the TS decoder. */
static int read_code(const unsigned char *data, size_t data_len,
                     size_t *bit_pos, int code_size, int eoi_code) {
    if ((*bit_pos + (size_t)code_size) >> 3 > data_len) return eoi_code;
    int code = 0;
    for (int i = 0; i < code_size; i++) {
        size_t byte_idx = (*bit_pos + (size_t)i) >> 3;
        if (byte_idx >= data_len) return eoi_code;
        code |= ((data[byte_idx] >> ((*bit_pos + (size_t)i) & 7)) & 1) << i;
    }
    *bit_pos += (size_t)code_size;
    return code;
}

/* Emit a code's chain; returns the chain's FIRST byte (needed for KwKwK). */
static int emit_chain(int code, const int *prefix, const unsigned char *suffix,
                      Buf *out) {
    unsigned char stack[4096];
    int n = 0, c = code;
    while (c >= 0) { stack[n++] = suffix[c]; c = prefix[c]; }
    for (int i = n - 1; i >= 0; i--) if (!buf_push(out, stack[i])) return -1;
    return stack[n - 1];
}

/* minCodeSize 2-8, clear-code resets, growing codes — same contract as TS. */
static unsigned char *lzw_decode(int min_code_size, const unsigned char *data,
                                 size_t data_len, size_t *out_len) {
    int clear_code = 1 << min_code_size, eoi_code = clear_code + 1;
    int code_size = min_code_size + 1, next_code = eoi_code + 1;
    /* Dictionary as (prefix, suffix, first-byte) triples, reset per clear. */
    static int prefix[4096];
    static unsigned char suffix[4096], first[4096];
    Buf out = {0};
    size_t bit_pos = 0;
    int prev = -1;

    memset(prefix, 0xff, sizeof prefix); /* -1 everywhere, then literals. */
    for (int i = 0; i < clear_code; i++) { prefix[i] = -1; suffix[i] = (unsigned char)i; first[i] = (unsigned char)i; }

    for (;;) {
        int code = read_code(data, data_len, &bit_pos, code_size, eoi_code);
        if (code == eoi_code) break;
        if (code == clear_code) {
            next_code = eoi_code + 1; code_size = min_code_size + 1;
            for (int i = 0; i < clear_code; i++) { prefix[i] = -1; suffix[i] = (unsigned char)i; first[i] = (unsigned char)i; }
            prev = -1; continue;
        }
        if (prev == -1) {
            if (code >= clear_code) break; /* First code after clear is a literal. */
            emit_chain(code, prefix, suffix, &out); prev = code; continue;
        }
        if (code > next_code) break;      /* Invalid — stop like browsers do. */
        /* KwKwK: a code one ahead of the dictionary is prev + first(prev). */
        int emitted_first;
        if (code == next_code) {
            emitted_first = emit_chain(prev, prefix, suffix, &out);
            if (emitted_first >= 0) buf_push(&out, first[prev]);
            emitted_first = first[prev];
        } else {
            emitted_first = emit_chain(code, prefix, suffix, &out);
        }
        if (next_code < 4096) { /* Table full: TS silently no-ops this write. */
            prefix[next_code] = prev; suffix[next_code] = (unsigned char)emitted_first;
            first[next_code] = first[prev];
            next_code++;
            if (next_code == (1 << code_size) && code_size < 12) code_size++;
        }
        prev = code;
    }
    *out_len = out.len;
    return out.data;
}

/* Reorder interlaced rows into natural order; identity for short frames. */
static unsigned char *de_interlace(const unsigned char *idx, size_t idx_len,
                                   int width, int height) {
    if (height < 4 || width == 0) { /* Just copy — the caller owns one buffer. */
        unsigned char *out = malloc(idx_len ? idx_len : 1);
        if (out) memcpy(out, idx, idx_len);
        return out;
    }
    unsigned char *out = malloc(idx_len);
    if (out == NULL) return NULL;
    size_t src = 0; /* Stored pass-by-pass: four passes, starts/steps below. */
    static const int passes[4][2] = { {0, 8}, {4, 8}, {2, 4}, {1, 2} };
    for (int p = 0; p < 4; p++) {
        for (int row = passes[p][0]; row < height; row += passes[p][1]) {
            memcpy(out + (size_t)row * width, idx + src, (size_t)width);
            src += (size_t)width;
        }
    }
    return out;
}

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

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

/* Concatenate a sub-block chain into *out (caller frees); 0 on truncation. */
static int read_sub_blocks(const unsigned char *b, size_t len, size_t *pos,
                           unsigned char **out, size_t *out_len) {
    Buf acc = {0};
    for (;;) {
        if (*pos >= len) { free(acc.data); return 0; }
        unsigned size = b[(*pos)++];
        if (size == 0) break; /* Terminator ends the chain. */
        if (*pos + size > len) { free(acc.data); return 0; }
        for (unsigned i = 0; i < size; i++) if (!buf_push(&acc, b[(*pos) + i])) { free(acc.data); return 0; }
        *pos += size;
    }
    *out = acc.data ? acc.data : malloc(1); /* Non-NULL even for empty chains. */
    *out_len = acc.len;
    return *out != NULL;
}

GifResult *decode_gif(const unsigned char *b, size_t len) {
    if (len < 13) return NULL;
    if (memcmp(b, "GIF87a", 6) != 0 && memcmp(b, "GIF89a", 6) != 0) return NULL;
    /* Logical screen descriptor: canvas size, flags, optional global palette. */
    size_t pos = 6;
    int width = le16(b + pos), height = le16(b + pos + 2);
    unsigned packed = b[pos + 4]; pos += 7; /* Skip bg color + aspect ratio. */
    unsigned char *global_palette = NULL; size_t global_len = 0;
    if (packed & 0x80) {
        size_t bytes = (size_t)(2 << (packed & 7)) * 3;
        if (pos + bytes > len) return NULL;
        global_palette = malloc(bytes);
        if (global_palette == NULL) return NULL;
        memcpy(global_palette, b + pos, bytes);
        global_len = bytes;
        pos += bytes;
    }

    GifResult *res = calloc(1, sizeof *res);
    if (res == NULL) { free(global_palette); return NULL; }
    res->width = width; res->height = height;
    res->global_palette = global_palette; res->global_palette_len = global_len;
    res->loop_count = -1; /* Absent until a NETSCAPE block says otherwise. */
    int delay_ms = 0, transparent_index = -1, disposal = 0;

    for (;;) {
        if (pos >= len) goto fail;
        unsigned char block = b[pos++];
        if (block == 0x3b) break; /* trailer */
        if (block == 0x21) {      /* Extension: graphic control / NETSCAPE / skip. */
            if (pos >= len) goto fail;
            unsigned char label = b[pos++];
            unsigned char *sub; size_t sub_len;
            if (label == 0xf9) {
                if (!read_sub_blocks(b, len, &pos, &sub, &sub_len)) goto fail;
                if (sub_len < 4) { free(sub); goto fail; }
                disposal = (sub[0] >> 2) & 7;
                delay_ms = le16(sub + 1) * 10;
                transparent_index = (sub[0] & 1) ? sub[3] : -1;
                free(sub);
            } else if (label == 0xff) {
                if (!read_sub_blocks(b, len, &pos, &sub, &sub_len)) goto fail;
                /* Concatenated: 11-byte name, then id 1 + loop lo/hi. */
                if (sub_len >= 14 && memcmp(sub, "NETSCAPE2.0", 11) == 0 && sub[11] == 1)
                    res->loop_count = le16(sub + 12);
                free(sub);
            } else if (!read_sub_blocks(b, len, &pos, &sub, &sub_len)) {
                goto fail;
            } else {
                free(sub);
            }
            continue;
        }
        if (block == 0x2c) { /* Image descriptor: rect, local palette, LZW data. */
            if (pos + 9 > len) goto fail;
            GifFrame *f = calloc(1, sizeof *f);
            GifFrame *grown = res->nframes
                ? realloc(res->frames, (res->nframes + 1) * sizeof *res->frames)
                : malloc(sizeof *res->frames);
            if (f == NULL || grown == NULL) { free(f); goto fail; }
            res->frames = grown;
            res->frames[res->nframes++] = *f;
            f = &res->frames[res->nframes - 1];

            f->x = le16(b + pos); f->y = le16(b + pos + 2);
            f->width = le16(b + pos + 4); f->height = le16(b + pos + 6);
            unsigned ip = b[pos + 8];
            pos += 9; /* Descriptor is 9 bytes: x, y, w, h, packed flags. */
            if (ip & 0x80) {
                size_t bytes = (size_t)(2 << (ip & 7)) * 3;
                if (pos + bytes > len) goto fail;
                f->palette = malloc(bytes);
                if (f->palette == NULL) goto fail;
                memcpy(f->palette, b + pos, bytes);
                f->palette_len = bytes;
                pos += bytes;
            }
            if (pos >= len) goto fail;
            int min_code_size = b[pos++];
            unsigned char *data; size_t data_len;
            /* LZW payload must be a complete sub-block chain. */
            if (!read_sub_blocks(b, len, &pos, &data, &data_len)) goto fail;
            f->indices = lzw_decode(min_code_size, data, data_len, &f->indices_len);
            free(data);
            if (f->indices == NULL) goto fail;
            if (ip & 0x40) { /* Interlaced — reorder to natural row order. */
                unsigned char *nat = de_interlace(f->indices, f->indices_len, f->width, f->height);
                free(f->indices);
                f->indices = nat;
                if (nat == NULL) goto fail;
            }
            f->delay_ms = delay_ms; f->transparent_index = transparent_index;
            f->disposal = disposal;
            delay_ms = 0; transparent_index = -1; disposal = 0;
            continue;
        }
        goto fail; /* Unknown block type — bail. */
    }
    return res;
fail:
    gif_free(res);
    return NULL;
}

int main(void) {
    /* 2×1 GIF89a: 2-color global palette (red, blue), one frame, pixels [0,1]. */
    static const unsigned char 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
    };
    GifResult *res = decode_gif(gif, sizeof gif);
    if (res == NULL) { fprintf(stderr, "malformed GIF\n"); return 1; }
    printf("%dx%d, %zu frame(s), loop=%d\n", res->width, res->height,
           res->nframes, res->loop_count);
    for (size_t i = 0; i < res->nframes; i++) {
        GifFrame *f = &res->frames[i];
        printf("frame %zu: %dx%d at (%d,%d), delay %dms, indices [", i,
               f->width, f->height, f->x, f->y, f->delay_ms);
        for (size_t j = 0; j < f->indices_len; j++)
            printf(j ? ", %d" : "%d", f->indices[j]);
        printf("]\n");
    }
    gif_free(res);
    return 0;
}