GIF Frame Extractor — TypeScript source

// Pure GIF87a/89a decoder — no React, no DOM. Parses the byte stream and
// LZW-decodes every frame to indexed pixels. Deterministic and side-effect
// free; truncated or malformed input returns null instead of throwing.

export interface GifFrame {
  x: number;
  y: number;
  width: number;
  height: number;
  /** Palette override for this frame (RGB triplets), null = use global. */
  palette: Uint8Array | null;
  /** Pixel indices in natural row order (de-interlaced). */
  indices: Uint8Array;
  /** Frame delay in milliseconds. */
  delayMs: number;
  /** Transparent palette index, or -1. */
  transparentIndex: number;
  /** Disposal method 0-7 (0/1 = keep, 2 = restore bg, 3 = restore previous). */
  disposal: number;
}

export interface GifResult {
  width: number;
  height: number;
  frames: GifFrame[];
  globalPalette: Uint8Array | null;
  /** NETSCAPE loop count; 0 means loop forever, Infinity when absent (play once semantics differ per consumer). */
  loopCount: number;
}

/** GIF LZW decompression — minCodeSize 2-8, clear-code resets, growing codes. */
export function lzwDecode(minCodeSize: number, data: Uint8Array): Uint8Array {
  const clearCode = 1 << minCodeSize;
  const eoiCode = clearCode + 1;
  let codeSize = minCodeSize + 1;
  let nextCode = eoiCode + 1;

  // Dictionary as (prefix, suffix, first-byte) triples — reset per clear code.
  const prefix = new Int32Array(4096);
  const suffix = new Uint8Array(4096);
  const first = new Uint8Array(4096);
  const resetDict = () => {
    for (let i = 0; i < clearCode; i++) {
      prefix[i] = -1;
      suffix[i] = i;
      first[i] = i;
    }
    nextCode = eoiCode + 1;
    codeSize = minCodeSize + 1;
  };
  resetDict();

  const out: number[] = [];
  /** Emit a code's chain, returning the chain's FIRST byte (for KwKwK). */
  const emit = (code: number): number => {
    const stack: number[] = [];
    let c = code;
    while (c >= 0) {
      stack.push(suffix[c]);
      c = prefix[c];
    }
    for (let i = stack.length - 1; i >= 0; i--) out.push(stack[i]);
    return stack[stack.length - 1];
  };

  let bitPos = 0;
  const readCode = (): number => {
    if ((bitPos + codeSize) >> 3 > data.length) return eoiCode;
    let code = 0;
    for (let i = 0; i < codeSize; i++) {
      const byteIdx = (bitPos + i) >> 3;
      if (byteIdx >= data.length) return eoiCode;
      const bit = (data[byteIdx] >> ((bitPos + i) & 7)) & 1;
      code |= bit << i;
    }
    bitPos += codeSize;
    return code;
  };

  let prev = -1;
  for (;;) {
    const code = readCode();
    if (code === eoiCode) break;
    if (code === clearCode) {
      resetDict();
      prev = -1;
      continue;
    }
    if (prev === -1) {
      if (code >= clearCode) break; // First code after clear must be a literal.
      emit(code);
      prev = code;
      continue;
    }
    if (code > nextCode) break; // Invalid — stop like browsers do.
    // KwKwK: code one ahead of the dictionary decodes to prev + first(prev).
    const emittedFirst = code === nextCode ? (emit(prev), out.push(first[prev]), first[prev]) : emit(code);
    prefix[nextCode] = prev;
    suffix[nextCode] = emittedFirst;
    first[nextCode] = first[prev];
    nextCode++;
    prev = code;
    if (nextCode === 1 << codeSize && codeSize < 12) codeSize++;
  }
  return Uint8Array.from(out);
}

/** Reorder interlaced rows into natural order. Identity for progressive rows. */
export function deInterlace(indices: Uint8Array, width: number, height: number): Uint8Array {
  if (height < 4 || width === 0) return indices;
  const out = new Uint8Array(indices.length);
  const passes = [
    { start: 0, step: 8 },
    { start: 4, step: 8 },
    { start: 2, step: 4 },
    { start: 1, step: 2 },
  ];
  let src = 0;
  for (const pass of passes) {
    for (let row = pass.start; row < height; row += pass.step) {
      out.set(indices.subarray(src, src + width), row * width);
      src += width;
    }
  }
  return out;
}

export function decodeGif(bytes: Uint8Array): GifResult | null {
  if (bytes.length < 13) return null;
  const magic = String.fromCharCode(...bytes.subarray(0, 6));
  if (magic !== 'GIF87a' && magic !== 'GIF89a') return null;

  let pos = 6;
  const width = bytes[pos] | (bytes[pos + 1] << 8);
  const height = bytes[pos + 2] | (bytes[pos + 3] << 8);
  const packed = bytes[pos + 4];
  pos += 7;

  let globalPalette: Uint8Array | null = null;
  if (packed & 0x80) {
    const entries = 2 << (packed & 7);
    globalPalette = bytes.slice(pos, pos + entries * 3);
    if (globalPalette.length < entries * 3) return null;
    pos += entries * 3;
  }

  const frames: GifFrame[] = [];
  let loopCount = Infinity;
  let delayMs = 0;
  let transparentIndex = -1;
  let disposal = 0;

  const readSubBlocks = (): Uint8Array | null => {
    const chunks: Uint8Array[] = [];
    for (;;) {
      if (pos >= bytes.length) return null;
      const size = bytes[pos++];
      if (size === 0) break;
      if (pos + size > bytes.length) return null;
      chunks.push(bytes.subarray(pos, pos + size));
      pos += size;
    }
    const total = chunks.reduce((s, c) => s + c.length, 0);
    const out = new Uint8Array(total);
    let o = 0;
    for (const c of chunks) {
      out.set(c, o);
      o += c.length;
    }
    return out;
  };

  for (;;) {
    if (pos >= bytes.length) return null;
    const block = bytes[pos++];
    if (block === 0x3b) break; // trailer

    if (block === 0x21) {
      // Extension
      if (pos >= bytes.length) return null;
      const label = bytes[pos++];
      if (label === 0xf9) {
        const gce = readSubBlocks();
        if (!gce || gce.length < 4) return null;
        disposal = (gce[0] >> 2) & 7;
        delayMs = (gce[1] | (gce[2] << 8)) * 10;
        transparentIndex = gce[0] & 1 ? gce[3] : -1;
      } else if (label === 0xff) {
        const app = readSubBlocks();
        if (app && app.length >= 14) {
          // Sub-block contents concatenated: the 11-byte name, then id 1 + loop lo/hi.
          const name = String.fromCharCode(...app.subarray(0, 11));
          if (name === 'NETSCAPE2.0' && app[11] === 1) {
            loopCount = app[12] | (app[13] << 8);
          }
        }
      } else {
        if (!readSubBlocks()) return null;
      }
      continue;
    }

    if (block === 0x2c) {
      // Image descriptor
      if (pos + 9 > bytes.length) return null;
      const x = bytes[pos] | (bytes[pos + 1] << 8);
      const y = bytes[pos + 2] | (bytes[pos + 3] << 8);
      const w = bytes[pos + 4] | (bytes[pos + 5] << 8);
      const h = bytes[pos + 6] | (bytes[pos + 7] << 8);
      const ip = bytes[pos + 8];
      pos += 9;
      let palette: Uint8Array | null = null;
      if (ip & 0x80) {
        const entries = 2 << (ip & 7);
        palette = bytes.slice(pos, pos + entries * 3);
        if (palette.length < entries * 3) return null;
        pos += entries * 3;
      }
      if (pos >= bytes.length) return null;
      const minCodeSize = bytes[pos++];
      const data = readSubBlocks();
      if (!data) return null;
      const indices = lzwDecode(minCodeSize, data);
      const final = ip & 0x40 ? deInterlace(indices, w, h) : indices;
      frames.push({
        x,
        y,
        width: w,
        height: h,
        palette,
        indices: final,
        delayMs,
        transparentIndex,
        disposal,
      });
      delayMs = 0;
      transparentIndex = -1;
      disposal = 0;
      continue;
    }

    return null; // Unknown block type — bail.
  }

  return { width, height, frames, globalPalette, loopCount };
}