png2gif.mjs

#!/usr/bin/env node
// PNG frames -> animated GIF, using nothing but Node's built-in zlib.
//
// Exists so that recording the demo needs no ffmpeg, no ImageMagick and no
// npm install: `git clone` and run. Handles 8-bit non-interlaced RGB/RGBA PNGs,
// which is what headless Chrome produces.

import { readFileSync, writeFileSync } from 'node:fs';
import { inflateSync } from 'node:zlib';

/* --------------------------------- PNG ---------------------------------- */

function decodePNG(buf) {
  if (buf.readUInt32BE(0) !== 0x89504e47) throw new Error('not a PNG');
  let pos = 8;
  let width = 0;
  let height = 0;
  let channels = 0;
  const idat = [];

  while (pos < buf.length) {
    const len = buf.readUInt32BE(pos);
    const type = buf.toString('ascii', pos + 4, pos + 8);
    const data = buf.subarray(pos + 8, pos + 8 + len);
    pos += 12 + len;

    if (type === 'IHDR') {
      width = data.readUInt32BE(0);
      height = data.readUInt32BE(4);
      const depth = data[8];
      const colorType = data[9];
      if (depth !== 8) throw new Error(`unsupported bit depth ${depth}`);
      if (data[12] !== 0) throw new Error('interlaced PNG unsupported');
      channels = { 2: 3, 6: 4, 0: 1, 4: 2 }[colorType];
      if (!channels) throw new Error(`unsupported color type ${colorType}`);
    } else if (type === 'IDAT') {
      idat.push(data);
    } else if (type === 'IEND') {
      break;
    }
  }

  const raw = inflateSync(Buffer.concat(idat));
  const stride = width * channels;
  const out = Buffer.alloc(height * stride);
  let src = 0;

  for (let y = 0; y < height; y++) {
    const filter = raw[src++];
    const line = raw.subarray(src, src + stride);
    src += stride;
    const cur = out.subarray(y * stride, (y + 1) * stride);
    const prev = y > 0 ? out.subarray((y - 1) * stride, y * stride) : null;

    for (let x = 0; x < stride; x++) {
      const a = x >= channels ? cur[x - channels] : 0;
      const b = prev ? prev[x] : 0;
      const c = prev && x >= channels ? prev[x - channels] : 0;
      let v = line[x];
      switch (filter) {
        case 0: break;
        case 1: v += a; break;
        case 2: v += b; break;
        case 3: v += (a + b) >> 1; break;
        case 4: {
          const p = a + b - c;
          const pa = Math.abs(p - a);
          const pb = Math.abs(p - b);
          const pc = Math.abs(p - c);
          v += pa <= pb && pa <= pc ? a : pb <= pc ? b : c;
          break;
        }
        default: throw new Error(`bad filter ${filter}`);
      }
      cur[x] = v & 0xff;
    }
  }
  return { width, height, pixels: out, channels };
}

/* ------------------------------ Quantising ------------------------------ */

const key15 = (r, g, b) => ((r >> 3) << 10) | ((g >> 3) << 5) | (b >> 3);

/** Median cut over a 15-bit histogram. The UI is a flat, limited palette, so
 *  256 entries is comfortably enough and no dithering is needed. */
function buildPalette(histogram, max = 256) {
  const present = [];
  for (let k = 0; k < histogram.length; k++) if (histogram[k]) present.push(k);
  if (present.length === 0) throw new Error('empty image');

  let boxes = [makeBox(present, histogram)];
  while (boxes.length < max) {
    let target = -1;
    let best = 0;
    boxes.forEach((box, i) => {
      if (box.keys.length < 2) return;
      const score = box.count * Math.max(box.range[0], box.range[1], box.range[2]);
      if (score > best) {
        best = score;
        target = i;
      }
    });
    if (target < 0) break;

    const box = boxes[target];
    const axis = box.range.indexOf(Math.max(...box.range));
    const shift = [10, 5, 0][axis];
    const sorted = box.keys.slice().sort((p, q) => ((p >> shift) & 31) - ((q >> shift) & 31));

    // Split at the median *pixel*, not the median colour: rare colours should
    // not get the same share of the palette as dominant ones.
    let acc = 0;
    let cut = 0;
    for (; cut < sorted.length - 1; cut++) {
      acc += histogram[sorted[cut]];
      if (acc >= box.count / 2) break;
    }
    boxes.splice(target, 1,
      makeBox(sorted.slice(0, cut + 1), histogram),
      makeBox(sorted.slice(cut + 1), histogram));
  }

  return boxes.map((box) => {
    let r = 0;
    let g = 0;
    let b = 0;
    for (const k of box.keys) {
      const w = histogram[k];
      r += (((k >> 10) & 31) << 3) * w;
      g += (((k >> 5) & 31) << 3) * w;
      b += ((k & 31) << 3) * w;
    }
    return [Math.round(r / box.count), Math.round(g / box.count), Math.round(b / box.count)];
  });
}

function makeBox(keys, histogram) {
  let count = 0;
  const lo = [31, 31, 31];
  const hi = [0, 0, 0];
  for (const k of keys) {
    count += histogram[k];
    const c = [(k >> 10) & 31, (k >> 5) & 31, k & 31];
    for (let i = 0; i < 3; i++) {
      if (c[i] < lo[i]) lo[i] = c[i];
      if (c[i] > hi[i]) hi[i] = c[i];
    }
  }
  return { keys, count, range: [hi[0] - lo[0], hi[1] - lo[1], hi[2] - lo[2]] };
}

function buildLookup(palette) {
  const map = new Uint8Array(32768);
  for (let k = 0; k < 32768; k++) {
    const r = ((k >> 10) & 31) << 3;
    const g = ((k >> 5) & 31) << 3;
    const b = (k & 31) << 3;
    let best = 0;
    let bestDist = Infinity;
    for (let i = 0; i < palette.length; i++) {
      const dr = r - palette[i][0];
      const dg = g - palette[i][1];
      const db = b - palette[i][2];
      const d = dr * dr + dg * dg + db * db;
      if (d < bestDist) {
        bestDist = d;
        best = i;
      }
    }
    map[k] = best;
  }
  return map;
}

/* --------------------------------- LZW ---------------------------------- */

function lzwEncode(minCodeSize, indices) {
  const out = [];
  const CLEAR = 1 << minCodeSize;
  const END = CLEAR + 1;
  let codeSize = minCodeSize + 1;
  let next = END + 1;
  let dict = new Map();
  let bitBuf = 0;
  let bitCount = 0;

  const emit = (code) => {
    bitBuf |= code << bitCount;
    bitCount += codeSize;
    while (bitCount >= 8) {
      out.push(bitBuf & 0xff);
      bitBuf >>>= 8;
      bitCount -= 8;
    }
  };

  emit(CLEAR);
  let prefix = indices[0];
  for (let i = 1; i < indices.length; i++) {
    const k = indices[i];
    const combined = prefix * 256 + k;
    const found = dict.get(combined);
    if (found !== undefined) {
      prefix = found;
      continue;
    }
    emit(prefix);
    dict.set(combined, next++);
    if (next > 4095) {
      emit(CLEAR);
      dict = new Map();
      next = END + 1;
      codeSize = minCodeSize + 1;
    } else if (next > 1 << codeSize) {
      codeSize++;
    }
    prefix = k;
  }
  emit(prefix);
  emit(END);
  if (bitCount > 0) out.push(bitBuf & 0xff);
  return out;
}

/** Decode our own output and compare. Getting the code-size growth off by one
 *  produces a file that some viewers render and others do not, so this is
 *  checked rather than assumed. */
function lzwDecode(minCodeSize, bytes) {
  const CLEAR = 1 << minCodeSize;
  const END = CLEAR + 1;
  let codeSize = minCodeSize + 1;
  let dict = [];
  const reset = () => {
    dict = [];
    for (let i = 0; i < CLEAR; i++) dict.push([i]);
    dict.push(null, null);
    codeSize = minCodeSize + 1;
  };
  reset();

  const out = [];
  let bitBuf = 0;
  let bitCount = 0;
  let pos = 0;
  let prev = null;

  for (;;) {
    while (bitCount < codeSize) {
      if (pos >= bytes.length) return out;
      bitBuf |= bytes[pos++] << bitCount;
      bitCount += 8;
    }
    const code = bitBuf & ((1 << codeSize) - 1);
    bitBuf >>>= codeSize;
    bitCount -= codeSize;

    if (code === CLEAR) {
      reset();
      prev = null;
      continue;
    }
    if (code === END) return out;

    let entry;
    if (code < dict.length && dict[code]) entry = dict[code];
    else if (prev) entry = [...prev, prev[0]];
    else throw new Error('corrupt stream');

    out.push(...entry);
    if (prev) {
      dict.push([...prev, entry[0]]);
      // `dict.length` is the next code that would be assigned, so it must grow
      // as soon as that code no longer fits — one step ahead of the encoder,
      // which is exactly the lag between the two dictionaries.
      if (dict.length >= 1 << codeSize && codeSize < 12) codeSize++;
    }
    prev = entry;
  }
}

/* --------------------------------- GIF ---------------------------------- */

function subBlocks(bytes) {
  const out = [];
  for (let i = 0; i < bytes.length; i += 255) {
    const chunk = bytes.slice(i, i + 255);
    out.push(chunk.length, ...chunk);
  }
  out.push(0);
  return out;
}

function encodeGIF(frames, width, height, palette, delays) {
  const bytes = [];
  const push = (...v) => bytes.push(...v);
  const u16 = (v) => push(v & 0xff, (v >> 8) & 0xff);

  push(...Buffer.from('GIF89a'));
  u16(width);
  u16(height);
  push(0x80 | (7 << 4) | 7, 0, 0); // global colour table, 256 entries

  for (let i = 0; i < 256; i++) {
    const c = palette[i] || [0, 0, 0];
    push(c[0], c[1], c[2]);
  }

  push(0x21, 0xff, 0x0b, ...Buffer.from('NETSCAPE2.0'), 0x03, 0x01, 0x00, 0x00, 0x00);

  frames.forEach((indices, i) => {
    push(0x21, 0xf9, 0x04, 0x04); // disposal: do not dispose
    u16(delays[i]);
    push(0x00, 0x00);

    push(0x2c);
    u16(0);
    u16(0);
    u16(width);
    u16(height);
    push(0x00);

    const data = lzwEncode(8, indices);
    const decoded = lzwDecode(8, data);
    if (decoded.length !== indices.length) {
      throw new Error(`LZW round-trip length mismatch on frame ${i}`);
    }
    for (let p = 0; p < indices.length; p++) {
      if (decoded[p] !== indices[p]) throw new Error(`LZW round-trip mismatch at ${p}`);
    }

    push(8, ...subBlocks(data));
  });

  push(0x3b);
  return Buffer.from(bytes);
}

/* --------------------------------- main --------------------------------- */

const [out, ...inputs] = process.argv.slice(2);
if (!out || inputs.length === 0) {
  console.error('usage: png2gif.mjs out.gif frame0.png frame1.png ...');
  process.exit(1);
}

// Hold on the states worth reading; skip through the typing. Centiseconds.
const DEFAULT_DELAYS = (process.env.BUOY_GIF_DELAYS || '130,190,45,190,180,280')
  .split(',')
  .map(Number);

const decoded = inputs.map((f) => decodePNG(readFileSync(f)));
for (const img of decoded) {
  if (img.width !== decoded[0].width || img.height !== decoded[0].height) {
    throw new Error('frame size mismatch');
  }
}

// BUOY_GIF_CROP="x,y,w,h" — capture taller than needed and trim, which is how
// we keep the panel's bottom edge (and its rendering seam) out of the frame.
const crop = (process.env.BUOY_GIF_CROP || '').split(',').map(Number);
const box =
  crop.length === 4 && crop.every((v) => Number.isFinite(v))
    ? { x: crop[0], y: crop[1], w: crop[2], h: crop[3] }
    : { x: 0, y: 0, w: decoded[0].width, h: decoded[0].height };

const width = Math.min(box.w, decoded[0].width - box.x);
const height = Math.min(box.h, decoded[0].height - box.y);

function pixelAt(img, x, y) {
  return ((y + box.y) * img.width + (x + box.x)) * img.channels;
}

const histogram = new Uint32Array(32768);
for (const img of decoded) {
  for (let y = 0; y < height; y++) {
    for (let x = 0; x < width; x++) {
      const p = pixelAt(img, x, y);
      histogram[key15(img.pixels[p], img.pixels[p + 1], img.pixels[p + 2])]++;
    }
  }
}

const palette = buildPalette(histogram);
const lookup = buildLookup(palette);

const frames = decoded.map((img) => {
  const idx = new Uint8Array(width * height);
  for (let y = 0; y < height; y++) {
    for (let x = 0; x < width; x++) {
      const p = pixelAt(img, x, y);
      idx[y * width + x] = lookup[key15(img.pixels[p], img.pixels[p + 1], img.pixels[p + 2])];
    }
  }
  return idx;
});

const delays = frames.map((_, i) => DEFAULT_DELAYS[i] ?? 120);
writeFileSync(out, encodeGIF(frames, width, height, palette, delays));

const kb = (Buffer.byteLength(readFileSync(out)) / 1024).toFixed(0);
console.log(`${out}: ${frames.length} frames, ${width}x${height}, ${palette.length} colours, ${kb} KB`);