Video to GIF Converter — TypeScript source

// Pure GIF89a encoder — quantize RGBA frames to a shared palette, LZW-compress,
// assemble the byte stream. No React, no DOM. Deterministic.

import { extractPalette, type Swatch } from './palette-extract';

export interface GifFrameInput {
  width: number;
  height: number;
  /** RGBA, 4 bytes per pixel, top-left origin. */
  rgba: Uint8Array;
  /** Frame delay in milliseconds (stored as centiseconds). */
  delayMs: number;
}

export interface GifEncodeOptions {
  /** Palette size ceiling. @default 128 */
  maxColors?: number;
}

// ---------------------------------------------------------------------------
// LZW compression (GIF variant)
// ---------------------------------------------------------------------------

/** Pack codes LSB-first at the current width, sub-blocked every 255 bytes. */
export function lzwEncode(minCodeSize: number, indices: Uint8Array): number[] {
  const clearCode = 1 << minCodeSize;
  const eoiCode = clearCode + 1;
  let codeSize = minCodeSize + 1;
  let nextCode = eoiCode + 1;

  // Dictionary: (prefixCode, byte) -> code, keyed numerically.
  const dict = new Map<number, number>();
  const resetDict = () => {
    dict.clear();
    nextCode = eoiCode + 1;
    codeSize = minCodeSize + 1;
  };
  resetDict();

  const out: number[] = [];
  let bitBuffer = 0;
  let bitCount = 0;
  const emit = (code: number) => {
    bitBuffer |= code << bitCount;
    bitCount += codeSize;
    while (bitCount >= 8) {
      out.push(bitBuffer & 0xff);
      bitBuffer >>= 8;
      bitCount -= 8;
    }
  };
  const 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.length === 0) {
    emit(eoiCode);
    flush();
    return out;
  }

  let w = indices[0];
  for (let i = 1; i < indices.length; i++) {
    const c = indices[i];
    const key = (w << 8) | c;
    const found = dict.get(key);
    if (found !== undefined) {
      w = found;
      continue;
    }
    emit(w);
    dict.set(key, nextCode++);
    growIfDue();
    w = c;
    if (nextCode >= 4096) {
      // Dictionary full — reset like encoders do.
      emit(clearCode);
      resetDict();
      w = c;
    }
  }
  emit(w);
  emit(eoiCode);
  flush();
  return out;

  function flush(): void {
    if (bitCount > 0) out.push(bitBuffer & 0xff);
  }
}

// ---------------------------------------------------------------------------
// Palette mapping
// ---------------------------------------------------------------------------

/** Map RGBA to palette indices via exact cache + nearest RGB distance. */
function mapToPalette(rgba: Uint8Array, palette: Swatch[]): Uint8Array {
  const cache = new Map<number, number>();
  const indices = new Uint8Array(Math.floor(rgba.length / 4));
  for (let i = 0; i < indices.length; i++) {
    const o = i * 4;
    const key = (rgba[o] << 16) | (rgba[o + 1] << 8) | rgba[o + 2];
    let idx = cache.get(key);
    if (idx === undefined) {
      let best = 0;
      let bestDist = Infinity;
      for (let p = 0; p < palette.length; p++) {
        const dr = rgba[o] - palette[p].r;
        const dg = rgba[o + 1] - palette[p].g;
        const db = rgba[o + 2] - palette[p].b;
        const dist = dr * dr + dg * dg + db * db;
        if (dist < bestDist) {
          bestDist = dist;
          best = p;
        }
      }
      idx = best;
      cache.set(key, idx);
    }
    indices[i] = idx;
  }
  return indices;
}

// ---------------------------------------------------------------------------
// Byte assembly
// ---------------------------------------------------------------------------

const pushAscii = (out: number[], text: string) => {
  for (const ch of text) out.push(ch.charCodeAt(0));
};

const u16le = (n: number) => [n & 0xff, (n >> 8) & 0xff];

export function encodeGif(frames: GifFrameInput[], opts: GifEncodeOptions = {}): Uint8Array {
  const maxColors = Math.min(opts.maxColors ?? 128, 256);
  if (frames.length === 0) return new Uint8Array(0);

  // One shared palette, quantized from a down-sampled mix of all frames.
  const sampleTargets = frames.map((f) => {
    const total = Math.floor(f.rgba.length / 4);
    const stride = Math.max(1, Math.floor(total / 4096));
    const out = new Uint8Array(Math.ceil(total / stride) * 4);
    let o = 0;
    for (let i = 0; i < total; i += stride) {
      out[o++] = f.rgba[i * 4];
      out[o++] = f.rgba[i * 4 + 1];
      out[o++] = f.rgba[i * 4 + 2];
      out[o++] = f.rgba[i * 4 + 3];
    }
    return out.subarray(0, o);
  });
  const mixed = new Uint8Array(sampleTargets.reduce((s, a) => s + a.length, 0));
  let mo = 0;
  for (const part of sampleTargets) {
    mixed.set(part, mo);
    mo += part.length;
  }
  const palette = extractPalette(mixed, maxColors);
  if (palette.length === 0) return new Uint8Array(0);

  // Palette table padded to a power of two (min 2 entries).
  let tableBits = 1;
  while (1 << tableBits < palette.length) tableBits++;
  const tableSize = 1 << tableBits;

  const out: number[] = [];
  pushAscii(out, 'GIF89a');
  const width = frames[0].width;
  const height = frames[0].height;
  out.push(...u16le(width), ...u16le(height));
  out.push(0x80 | (tableBits - 1), 0, 0); // GCT flag + size; bg; aspect
  for (let i = 0; i < tableSize; i++) {
    const sw = palette[i];
    out.push(sw ? sw.r : 0, sw ? sw.g : 0, sw ? sw.b : 0);
  }

  // NETSCAPE loop forever.
  out.push(0x21, 0xff, 0x0b);
  pushAscii(out, 'NETSCAPE2.0');
  out.push(0x03, 0x01, 0x00, 0x00, 0x00);

  const minCodeSize = Math.max(2, tableBits);
  for (const frame of frames) {
    // Graphic control extension: delay in centiseconds, no transparency.
    const cs = Math.max(0, Math.min(0xffff, Math.round(frame.delayMs / 10)));
    out.push(0x21, 0xf9, 0x04, 0x00, ...u16le(cs), 0x00, 0x00);

    out.push(0x2c);
    out.push(...u16le(0), ...u16le(0), ...u16le(frame.width), ...u16le(frame.height));
    out.push(0x00); // no LCT, no interlace

    const indices = mapToPalette(frame.rgba, palette);
    const data = lzwEncode(minCodeSize, indices);
    out.push(minCodeSize);
    for (let i = 0; i < data.length; i += 255) {
      const chunk = data.slice(i, i + 255);
      out.push(chunk.length, ...chunk);
    }
    out.push(0x00); // block terminator
  }

  out.push(0x3b); // trailer
  return Uint8Array.from(out);
}