Skip to content
TypeScript
6.6 KB
Raw Blame
// Animated GIF encoder (GIF89a, looping). One global palette for all frames; more than 256
// colors (lit scenes) are reduced by median cut. Fully transparent pixels become the
// transparent index. Identical consecutive frames are merged.
import { TRANSPARENT } from "../core/color.ts";
import type { Img } from "../core/image.ts";

export interface GifFrame {
  img: Img;
  /** Duration in ms (GIF stores centiseconds; minimum 20ms). */
  ms: number;
}

export function encodeGif(frames: GifFrame[]): Buffer {
  if (!frames.length) throw new Error("gif needs at least one frame");
  const w = Math.max(...frames.map((f) => f.img.w)), h = Math.max(...frames.map((f) => f.img.h));
  const merged = mergeRepeats(frames);

  // Palette: every opaque color, reduced if needed; index 0 is transparent when any pixel is.
  const counts = new Map<number, number>();
  let transparent = false;
  for (const { img } of merged) {
    if (img.w < w || img.h < h) transparent = true;
    for (const c of img.data) {
      if (isClear(c)) { transparent = true; continue; }
      const rgb = c >>> 8;
      counts.set(rgb, (counts.get(rgb) ?? 0) + 1);
    }
  }
  const room = transparent ? 255 : 256;
  const pal = counts.size <= room ? [...counts.keys()] : medianCut(counts, room);
  const colors = (transparent ? [0] : []).concat(pal);
  const base = transparent ? 1 : 0;
  let bits = 1;
  while (1 << bits < colors.length) bits++;
  const exact = new Map<number, number>();
  pal.forEach((c, i) => exact.set(c, i + base));
  const indexOf = (rgb: number): number => {
    let i = exact.get(rgb);
    if (i === undefined) {
      i = nearest(pal, rgb) + base;
      exact.set(rgb, i);
    }
    return i;
  };

  const out: number[] = [];
  const u16 = (v: number) => out.push(v & 255, (v >> 8) & 255);
  out.push(...Buffer.from("GIF89a"));
  u16(w); u16(h);
  out.push(0x80 | 0x70 | (bits - 1), 0, 0);
  for (let i = 0; i < 1 << bits; i++) {
    const c = colors[i] ?? 0;
    out.push((c >> 16) & 255, (c >> 8) & 255, c & 255);
  }
  out.push(0x21, 0xff, 11, ...Buffer.from("NETSCAPE2.0"), 3, 1, 0, 0, 0);   // loop forever

  const minSize = Math.max(2, bits);
  for (const { img, ms } of merged) {
    const cs = Math.max(2, Math.round(ms / 10));
    // Restore to background between frames when anything is transparent, so frames don't pile up.
    out.push(0x21, 0xf9, 4, ((transparent ? 2 : 1) << 2) | (transparent ? 1 : 0));
    u16(cs);
    out.push(0, 0);
    out.push(0x2c);
    u16(0); u16(0); u16(w); u16(h);
    out.push(0);
    const idx = new Uint8Array(w * h);
    for (let y = 0; y < img.h; y++)
      for (let x = 0; x < img.w; x++) {
        const c = img.data[y * img.w + x];
        idx[y * w + x] = isClear(c) ? 0 : indexOf(c >>> 8);
      }
    out.push(minSize);
    const data = lzw(idx, minSize);
    for (let i = 0; i < data.length; i += 255) {
      const n = Math.min(255, data.length - i);
      out.push(n);
      for (let j = 0; j < n; j++) out.push(data[i + j]);
    }
    out.push(0);
  }
  out.push(0x3b);
  return Buffer.from(out);
}

function isClear(c: number): boolean {
  return c === TRANSPARENT || (c & 255) === 0;
}

function mergeRepeats(frames: GifFrame[]): GifFrame[] {
  const out: GifFrame[] = [];
  for (const f of frames) {
    const prev = out[out.length - 1];
    if (prev && same(prev.img, f.img)) prev.ms += f.ms;
    else out.push({ img: f.img, ms: f.ms });
  }
  return out;
}

function same(a: Img, b: Img): boolean {
  if (a.w !== b.w || a.h !== b.h) return false;
  for (let i = 0; i < a.data.length; i++) if (a.data[i] !== b.data[i]) return false;
  return true;
}

/** LZW with variable code size, clearing the table when it fills (4096 codes). */
function lzw(index: Uint8Array, minSize: number): number[] {
  const clear = 1 << minSize, eoi = clear + 1;
  let size = minSize + 1, next = eoi + 1;
  let table = new Map<number, number>();
  const out: number[] = [];
  let cur = 0, shift = 0;
  const emit = (code: number) => {
    cur |= code << shift;
    shift += size;
    while (shift >= 8) {
      out.push(cur & 255);
      cur >>>= 8;
      shift -= 8;
    }
  };
  emit(clear);
  let code = index[0];
  for (let i = 1; i < index.length; i++) {
    const k = index[i], key = (code << 8) | k, hit = table.get(key);
    if (hit !== undefined) {
      code = hit;
      continue;
    }
    emit(code);
    if (next === 4096) {
      emit(clear);
      table = new Map();
      size = minSize + 1;
      next = eoi + 1;
    } else {
      if (next >= 1 << size) size++;
      table.set(key, next++);
    }
    code = k;
  }
  emit(code);
  emit(eoi);
  if (shift > 0) out.push(cur & 255);
  return out;
}

/** Median cut over 0xRRGGBB colors weighted by count. */
function medianCut(counts: Map<number, number>, n: number): number[] {
  type Box = { cs: number[] };
  const ch = (c: number, k: number) => (c >> (16 - 8 * k)) & 255;
  const range = (b: Box) => {
    let best = 0, axis = 0;
    for (let k = 0; k < 3; k++) {
      let lo = 255, hi = 0;
      for (const c of b.cs) { const v = ch(c, k); if (v < lo) lo = v; if (v > hi) hi = v; }
      if (hi - lo > best) { best = hi - lo; axis = k; }
    }
    return { best, axis };
  };
  const boxes: Box[] = [{ cs: [...counts.keys()] }];
  while (boxes.length < n) {
    let pick = -1, score = 0, axis = 0;
    boxes.forEach((b, i) => {
      if (b.cs.length < 2) return;
      const r = range(b);
      let wsum = 0;
      for (const c of b.cs) wsum += counts.get(c)!;
      const s = r.best * Math.sqrt(wsum);
      if (s > score) { score = s; pick = i; axis = r.axis; }
    });
    if (pick < 0) break;
    const b = boxes[pick];
    b.cs.sort((p, q) => ch(p, axis) - ch(q, axis));
    let total = 0;
    for (const c of b.cs) total += counts.get(c)!;
    let acc = 0, cut = 1;
    for (let i = 0; i < b.cs.length - 1; i++) {
      acc += counts.get(b.cs[i])!;
      if (acc >= total / 2) { cut = i + 1; break; }
    }
    boxes.splice(pick, 1, { cs: b.cs.slice(0, cut) }, { cs: b.cs.slice(cut) });
  }
  return boxes.map((b) => {
    let r = 0, g = 0, bl = 0, wsum = 0;
    for (const c of b.cs) {
      const wt = counts.get(c)!;
      r += ch(c, 0) * wt; g += ch(c, 1) * wt; bl += ch(c, 2) * wt; wsum += wt;
    }
    return (Math.round(r / wsum) << 16) | (Math.round(g / wsum) << 8) | Math.round(bl / wsum);
  });
}

function nearest(pal: number[], rgb: number): number {
  const r = (rgb >> 16) & 255, g = (rgb >> 8) & 255, b = rgb & 255;
  let best = 0, bd = Infinity;
  for (let i = 0; i < pal.length; i++) {
    const c = pal[i], dr = ((c >> 16) & 255) - r, dg = ((c >> 8) & 255) - g, db = (c & 255) - b;
    const d = 2 * dr * dr + 4 * dg * dg + 3 * db * db;
    if (d < bd) { bd = d; best = i; }
  }
  return best;
}