Capture

import { exportNode, record, encodeFrames, download } from "@/lib/robocn/capture"

// The whole path: record two seconds and save the file.
await exportNode(node, { format: "gif", name: "robot-arm", duration: 2, fps: 15 })

// Or keep the frames: they are canvases, so anything can have them.
const frames = await record(node, { duration: 2, fps: 20, scale: 2 })
download(await encodeFrames(frames, "webp"), "robot-arm.webp")

"use client"

/**
 * Getting a machine out of the DOM and into a file.
 *
 * A robocn component is an `<svg>` whose colours are `var(--robot-shell, …)`,
 * whose text inherits the page's font and whose sparks are CSS keyframes.
 * Serialize it and hand it to an `Image` and you get the *fallback* palette on
 * a transparent field with nothing moving — a different drawing than the one on
 * screen. So this module bakes the cascade into a clone before serializing it,
 * frame by frame, and writes the frame deltas it actually measured.
 *
 * Encoding is elsewhere and dependency-free: `./gif` writes GIF89a, `./webp`
 * re-houses the browser's own WebP frames as an animation. Notes:
 * `docs/export.md`.
 */

import { encodeGif, type GifFrame } from "@/lib/robocn/gif"
import { muxAnimatedWebp } from "@/lib/robocn/webp"

export type ExportFormat = "webp" | "gif" | "png"

export interface CaptureOptions {
  /** Device pixels per CSS pixel. */
  scale?: number
  /** A CSS colour painted under the drawing, or null to keep it transparent. */
  background?: string | null
  /** Inline same-origin `@font-face` files so text keeps its typeface. */
  fonts?: boolean
}

export interface RecordOptions extends CaptureOptions {
  /** Frames a second to aim for. What is written is what was measured. */
  fps?: number
  /** Seconds of motion. Zero — the default — takes a single frame. */
  duration?: number
  signal?: AbortSignal
  onProgress?: (captured: number, total: number) => void
}

/** A captured frame and how long it should stay on screen, in milliseconds. */
export interface Frame {
  canvas: HTMLCanvasElement
  delay: number
}

export type CaptureTarget = HTMLElement | SVGElement

/** Both containers floor a frame at 10 ms, and nothing should hang on one. */
const MIN_DELAY = 10
const MAX_DELAY = 10_000

/**
 * Frame delays from the instants the frames were sampled at.
 *
 * Serializing and decoding a frame costs tens of milliseconds, so a nominal
 * rate is a lie. Recording the real deltas means a recording plays back at the
 * speed the machine moved, and a slow frame reads as a long frame rather than
 * as a speed-up. The last frame has no successor, so it takes the average of
 * the rest — or the nominal interval when it is the only frame.
 */
export function frameDelays(sampledAt: number[], nominal: number): number[] {
  const clamp = (value: number) => Math.min(MAX_DELAY, Math.max(MIN_DELAY, Math.round(value)))
  if (sampledAt.length <= 1) return [clamp(nominal)]
  const deltas = sampledAt.slice(1).map((at, index) => clamp(at - sampledAt[index]))
  const mean = deltas.reduce((total, delta) => total + delta, 0) / deltas.length
  return [...deltas, clamp(mean)]
}

/** `robot-arm` + `gif` → `robot-arm.gif`; an empty name still gets a file. */
export const exportFileName = (name: string, format: ExportFormat) => {
  const stem = name.trim().toLowerCase().replace(/[^a-z0-9]+/g, "-").replace(/^-|-$/g, "")
  return `${stem || "robocn"}.${format}`
}

/** Frames a recording of this length at this rate is made of. */
export const frameCount = (duration: number, fps: number) =>
  duration <= 0 ? 1 : Math.max(1, Math.round(duration * Math.max(1, fps)))

/**
 * Properties SVG children inherit. Emitted only where a child's computed value
 * differs from the one its parent already carries, which is the difference
 * between a few hundred declarations and twenty thousand.
 */
const SVG_INHERITED = [
  "color",
  "fill",
  "fill-opacity",
  "fill-rule",
  "stroke",
  "stroke-opacity",
  "stroke-width",
  "stroke-linecap",
  "stroke-linejoin",
  "stroke-dasharray",
  "stroke-dashoffset",
  "stroke-miterlimit",
  "paint-order",
  "shape-rendering",
  "text-anchor",
  "visibility",
  "font-family",
  "font-size",
  "font-style",
  "font-weight",
  "letter-spacing",
]

/** Properties an SVG element keeps to itself, with the value worth omitting. */
const SVG_OWN: [string, string][] = [
  ["opacity", "1"],
  ["mix-blend-mode", "normal"],
  ["filter", "none"],
  ["clip-path", "none"],
  ["mask", "none"],
  ["mask-type", "luminance"],
  ["vector-effect", "none"],
  ["dominant-baseline", "auto"],
  ["stop-color", "rgb(0, 0, 0)"],
  ["stop-opacity", "1"],
  ["display", "inline"],
]

/** What an HTML element needs for the clone to lay itself out and paint the same. */
const HTML_INHERITED = [
  "color",
  "font-family",
  "font-size",
  "font-style",
  "font-weight",
  "font-variant-numeric",
  "letter-spacing",
  "line-height",
  "text-align",
  "text-transform",
  "visibility",
  "white-space",
  "word-break",
]

const HTML_OWN = [
  "display",
  "position",
  "top",
  "right",
  "bottom",
  "left",
  "width",
  "height",
  "min-width",
  "min-height",
  "max-width",
  "max-height",
  "box-sizing",
  "margin-top",
  "margin-right",
  "margin-bottom",
  "margin-left",
  "padding-top",
  "padding-right",
  "padding-bottom",
  "padding-left",
  "flex-direction",
  "flex-wrap",
  "flex-grow",
  "flex-shrink",
  "flex-basis",
  "align-items",
  "align-self",
  "justify-content",
  "gap",
  "grid-template-columns",
  "grid-template-rows",
  "grid-column",
  "grid-row",
  "order",
  "overflow-x",
  "overflow-y",
  "background-color",
  "background-image",
  "background-size",
  "background-position",
  "background-repeat",
  "border-top-width",
  "border-right-width",
  "border-bottom-width",
  "border-left-width",
  "border-style",
  "border-top-color",
  "border-right-color",
  "border-bottom-color",
  "border-left-color",
  "border-radius",
  "box-shadow",
  "opacity",
  "filter",
  "mix-blend-mode",
  "transform",
  "transform-origin",
  "text-decoration-line",
  "text-shadow",
  "text-overflow",
  "vertical-align",
  "z-index",
]

/** Read a computed value without throwing on an engine that does not know the property. */
const read = (style: CSSStyleDeclaration, property: string) => {
  try {
    return style.getPropertyValue(property)
  } catch {
    return ""
  }
}

/**
 * Copy one element's computed style onto its clone, and hand the children the
 * inherited values they should be compared against.
 *
 * CSS animation is baked here too: an element mid-keyframe has a computed
 * `transform` and `opacity`, and copying them is the only way `robocn-spin`
 * survives into a clone that has no stylesheet.
 */
function bakeElement(
  live: Element,
  clone: Element,
  inherited: Map<string, string>,
  svg: boolean,
): Map<string, string> {
  const style = window.getComputedStyle(live)
  const declarations: string[] = []
  const next = new Map(inherited)

  for (const property of svg ? SVG_INHERITED : HTML_INHERITED) {
    const value = read(style, property)
    if (!value) continue
    if (inherited.get(property) === value) continue
    declarations.push(`${property}:${value}`)
    next.set(property, value)
  }

  if (svg) {
    for (const [property, initial] of SVG_OWN) {
      const value = read(style, property)
      if (!value || value === initial) continue
      declarations.push(`${property}:${value}`)
    }
    // Only an animated element needs its matrix copied; every other transform
    // is already on the clone as the attribute it was written as.
    if (read(style, "animation-name") !== "none") {
      for (const property of ["transform", "transform-origin", "transform-box"]) {
        const value = read(style, property)
        if (value) declarations.push(`${property}:${value}`)
      }
    }
  } else {
    for (const property of HTML_OWN) {
      const value = read(style, property)
      if (value) declarations.push(`${property}:${value}`)
    }
  }

  if (declarations.length > 0) {
    const own = clone.getAttribute("style")
    // The element's own inline style wins: it is the pose the component set.
    clone.setAttribute("style", `${declarations.join(";")};${own ?? ""}`)
  }
  // Classes cannot resolve in the clone and animation declarations would only
  // restart what has just been baked.
  clone.removeAttribute("class")
  return next
}

/** Walk the live tree and its clone together, baking as it goes. */
function bake(live: Element, clone: Element, inherited: Map<string, string>, svg: boolean) {
  const next = bakeElement(live, clone, inherited, svg)
  const inSvg = svg || live.tagName.toLowerCase() === "svg"
  const liveChildren = live.children
  const cloneChildren = clone.children
  for (let index = 0; index < liveChildren.length && index < cloneChildren.length; index += 1) {
    bake(liveChildren[index], cloneChildren[index], next, inSvg)
  }
}

/**
 * Swap every live `<canvas>` into the clone as the picture it is showing.
 *
 * A cloned canvas is blank — the bitmap is not part of the element. WebGL reads
 * back empty unless its context was made with `preserveDrawingBuffer`, which is
 * why `robot-stage` asks for one.
 */
function bakeCanvases(live: Element, clone: Element) {
  const liveCanvases = [live, ...live.querySelectorAll("canvas")].filter(
    (node): node is HTMLCanvasElement => node instanceof HTMLCanvasElement,
  )
  const cloneCanvases = [clone, ...clone.querySelectorAll("canvas")].filter(
    (node) => node.tagName.toLowerCase() === "canvas",
  )
  liveCanvases.forEach((canvas, index) => {
    const target = cloneCanvases[index]
    if (!target?.parentNode) return
    let url: string
    try {
      url = canvas.toDataURL("image/png")
    } catch {
      return // Tainted by a cross-origin draw: leave the gap rather than throw.
    }
    const rect = canvas.getBoundingClientRect()
    const image = document.createElementNS("http://www.w3.org/1999/xhtml", "img")
    image.setAttribute("src", url)
    image.setAttribute("width", String(Math.round(rect.width) || canvas.width))
    image.setAttribute("height", String(Math.round(rect.height) || canvas.height))
    image.setAttribute("style", target.getAttribute("style") ?? "")
    target.parentNode.replaceChild(image, target)
  })
}

let fontFaces: Promise<string> | null = null

/**
 * Every same-origin `@font-face` in the document, with its files inlined.
 *
 * Fetched once per page: a capture re-serializes on every frame, and the
 * typeface does not change between them. A cross-origin sheet throws on
 * `cssRules` and a cross-origin file cannot be read — both are skipped, and the
 * text falls back rather than the capture failing.
 */
async function inlineFonts(): Promise<string> {
  if (fontFaces) return fontFaces
  fontFaces = (async () => {
    // A rule and the sheet it came from: font URLs are relative to the
    // stylesheet, not to the page. Next writes `../media/…`, which resolves to
    // a 404 against the document and to the real file against the sheet.
    const rules: { text: string; base: string }[] = []
    // Recursive on purpose: a `@font-face` can sit inside `@layer`, `@media` or
    // `@supports`, and Tailwind puts the whole sheet in layers.
    const collect = (list: CSSRuleList, base: string) => {
      for (const rule of Array.from(list)) {
        if (/^@font-face/.test(rule.cssText)) {
          rules.push({ text: rule.cssText, base })
          continue
        }
        const nested = (rule as CSSGroupingRule).cssRules
        if (nested) collect(nested, base)
      }
    }
    for (const sheet of Array.from(document.styleSheets)) {
      try {
        collect(sheet.cssRules, sheet.href ?? document.baseURI)
      } catch {
        // A cross-origin sheet throws rather than listing: its faces fall back.
      }
    }
    const urls = new Map<string, string>()
    for (const rule of rules) {
      for (const match of rule.text.matchAll(/url\((['"]?)([^'")]+)\1\)/g)) {
        urls.set(match[2], rule.base)
      }
    }
    const embedded = new Map<string, string>()
    await Promise.all(
      [...urls].map(async ([url, base]) => {
        try {
          const absolute = new URL(url, base)
          if (absolute.origin !== window.location.origin) return
          const response = await fetch(absolute.href)
          if (!response.ok) return
          const buffer = await response.arrayBuffer()
          let binary = ""
          const bytes = new Uint8Array(buffer)
          for (let index = 0; index < bytes.length; index += 1) {
            binary += String.fromCharCode(bytes[index])
          }
          const type = response.headers.get("content-type") ?? "font/woff2"
          embedded.set(url, `data:${type};base64,${window.btoa(binary)}`)
        } catch {
          /* One missing face is a fallback, not a failed export. */
        }
      }),
    )
    return rules
      .map((rule) =>
        rule.text.replace(/url\((['"]?)([^'")]+)\1\)/g, (whole, _quote, url) => {
          const data = embedded.get(url)
          return data ? `url("${data}")` : whole
        }),
      )
      .filter((rule) => rule.includes("data:"))
      .join("\n")
  })()
  return fontFaces
}

const escapeXml = (text: string) =>
  text.replace(/&/g, "&amp;").replace(/</g, "&lt;").replace(/>/g, "&gt;")

export interface Snapshot {
  markup: string
  width: number
  height: number
  /** Whether the document wraps HTML in a `<foreignObject>`. It changes how it can be loaded. */
  foreign: boolean
}

/**
 * One instant of a target as a standalone SVG document.
 *
 * An `<svg>` target is snapshotted as itself. Anything else — a demo panel with
 * its controls, the workbench stage, a whole matrix — is wrapped in a
 * `<foreignObject>`, which is how the browser is persuaded to rasterize HTML.
 */
export async function snapshot(
  target: CaptureTarget,
  options: CaptureOptions = {},
): Promise<Snapshot> {
  const rect = target.getBoundingClientRect()
  const width = Math.max(1, Math.round(rect.width))
  const height = Math.max(1, Math.round(rect.height))
  const isSvg = target.tagName.toLowerCase() === "svg"
  const clone = target.cloneNode(true) as Element

  bake(target, clone, new Map(), isSvg)
  bakeCanvases(target, clone)
  // Last, so neither walk above loses its live-to-clone alignment: the export
  // button itself sits inside the thing it records, and does not belong in it.
  for (const chrome of Array.from(clone.querySelectorAll("[data-robocn-hide]"))) chrome.remove()

  const wantsFonts = options.fonts !== false && (target.textContent ?? "").trim().length > 0
  const faces = wantsFonts ? await inlineFonts() : ""

  if (isSvg) {
    clone.setAttribute("xmlns", "http://www.w3.org/2000/svg")
    clone.setAttribute("xmlns:xlink", "http://www.w3.org/1999/xlink")
    clone.setAttribute("width", String(width))
    clone.setAttribute("height", String(height))
    if (faces) {
      const sheet = document.createElementNS("http://www.w3.org/2000/svg", "style")
      sheet.textContent = faces
      clone.insertBefore(sheet, clone.firstChild)
    }
    return {
      markup: new XMLSerializer().serializeToString(clone),
      width,
      height,
      foreign: false,
    }
  }

  const style = faces ? `<style>${escapeXml(faces)}</style>` : ""

  clone.setAttribute("xmlns", "http://www.w3.org/1999/xhtml")
  const own = clone.getAttribute("style") ?? ""
  // The clone is the whole document now: it lays out at the origin, at the size
  // it had on the page, with nothing outside it to push it around.
  clone.setAttribute(
    "style",
    `${own};margin:0;position:static;inset:auto;width:${width}px;height:${height}px;`,
  )
  const body = new XMLSerializer().serializeToString(clone)
  const markup =
    `<svg xmlns="http://www.w3.org/2000/svg" width="${width}" height="${height}" ` +
    `viewBox="0 0 ${width} ${height}">${style}` +
    `<foreignObject x="0" y="0" width="${width}" height="${height}">${body}</foreignObject></svg>`
  return { markup, width, height, foreign: true }
}

/**
 * The colour showing through a target that paints none of its own — the first
 * opaque background above it, which is what a viewer sees behind the machine.
 */
export function backgroundBehind(node: Element): string {
  let current: Element | null = node
  while (current) {
    const colour = window.getComputedStyle(current).backgroundColor
    if (colour && colour !== "transparent" && !/^rgba\(.*,\s*0\)$/.test(colour)) return colour
    current = current.parentElement
  }
  return "#ffffff"
}

/**
 * A snapshot, painted.
 *
 * A blob URL beats a data URL on both the encode and the decode, and that is
 * what a pure SVG snapshot gets. A document carrying a `<foreignObject>` does
 * not: Chrome taints the canvas when one arrives over `blob:`, and a tainted
 * canvas cannot be read back at all — no `toBlob`, no `getImageData`, no
 * export. The same document over `data:` is clean.
 */
export async function rasterize(
  shot: Snapshot,
  options: CaptureOptions = {},
): Promise<HTMLCanvasElement> {
  const scale = options.scale ?? 2
  const url = shot.foreign
    ? `data:image/svg+xml;charset=utf-8,${encodeURIComponent(shot.markup)}`
    : URL.createObjectURL(new Blob([shot.markup], { type: "image/svg+xml;charset=utf-8" }))
  try {
    const image = new Image()
    image.decoding = "sync"
    image.src = url
    await (image.decode
      ? image.decode()
      : new Promise<void>((resolve, reject) => {
          image.onload = () => resolve()
          image.onerror = () => reject(new Error("the snapshot would not render"))
        }))
    const canvas = document.createElement("canvas")
    canvas.width = Math.max(1, Math.round(shot.width * scale))
    canvas.height = Math.max(1, Math.round(shot.height * scale))
    const context = canvas.getContext("2d")
    if (!context) throw new Error("no 2d context")
    context.imageSmoothingQuality = "high"
    if (options.background) {
      context.fillStyle = options.background
      context.fillRect(0, 0, canvas.width, canvas.height)
    }
    context.drawImage(image, 0, 0, canvas.width, canvas.height)
    return canvas
  } finally {
    if (!shot.foreign) URL.revokeObjectURL(url)
  }
}

/** One frame, start to finish. */
export const captureFrame = async (target: CaptureTarget, options: CaptureOptions = {}) =>
  rasterize(await snapshot(target, options), options)

/**
 * The next paint, or 100 ms, whichever comes first.
 *
 * A hidden tab never paints, so waiting on `requestAnimationFrame` alone is a
 * recording that hangs at two frames out of fifteen with no way out. The timer
 * keeps it moving: the machine is frozen behind the scenes, so the frames come
 * out the same, but the file is written and the button comes back.
 */
const nextFrame = () =>
  new Promise<void>((resolve) => {
    let settled = false
    const done = () => {
      if (settled) return
      settled = true
      resolve()
    }
    if (typeof requestAnimationFrame === "function") requestAnimationFrame(done)
    setTimeout(done, 100)
  })

const now = () =>
  typeof performance === "object" && typeof performance.now === "function"
    ? performance.now()
    : Date.now()

/**
 * Sample a target over time.
 *
 * Real time, on purpose: the machines run on `requestAnimationFrame`, so the
 * only way to record what they do is to watch them do it. A frame that took
 * longer than the interval is not dropped — the delta is written instead.
 */
export async function record(
  target: CaptureTarget,
  options: RecordOptions = {},
): Promise<Frame[]> {
  const fps = Math.max(1, options.fps ?? 15)
  const total = frameCount(options.duration ?? 0, fps)
  const interval = 1000 / fps
  const canvases: HTMLCanvasElement[] = []
  const sampledAt: number[] = []

  // A throwaway first frame, so the font fetch and the first layout are not
  // charged to frame one — otherwise every loop opens on a held still.
  if (total > 1 && !options.signal?.aborted) await captureFrame(target, options)

  for (let index = 0; index < total; index += 1) {
    if (options.signal?.aborted) break
    const start = now()
    sampledAt.push(start)
    canvases.push(await captureFrame(target, options))
    options.onProgress?.(index + 1, total)
    if (index === total - 1) break
    // Only wait for the part of the interval the capture did not already spend.
    while (now() - start < interval) {
      if (options.signal?.aborted) break
      await nextFrame()
    }
  }

  if (canvases.length === 0) throw new Error("nothing was captured")
  const delays = frameDelays(sampledAt.slice(0, canvases.length), interval)
  return canvases.map((canvas, index) => ({ canvas, delay: delays[index] }))
}

const toBlob = (canvas: HTMLCanvasElement, type: string, quality?: number) =>
  new Promise<Blob>((resolve, reject) => {
    canvas.toBlob(
      (blob) => (blob ? resolve(blob) : reject(new Error(`this browser cannot write ${type}`))),
      type,
      quality,
    )
  })

const imageData = (canvas: HTMLCanvasElement) => {
  const context = canvas.getContext("2d")
  if (!context) throw new Error("no 2d context")
  return context.getImageData(0, 0, canvas.width, canvas.height)
}

/** Whether this browser's canvas can write WebP at all. Safari before 14 could not. */
export const supportsWebp = () => {
  try {
    return document.createElement("canvas").toDataURL("image/webp").startsWith("data:image/webp")
  } catch {
    return false
  }
}

export interface EncodeOptions {
  /** Lossy quality for WebP, 0–1. */
  quality?: number
  /** Repeat count for the animated formats; 0 is forever. */
  loop?: number
}

/** Frames to a file. One frame is a still; more than one is an animation. */
export async function encodeFrames(
  frames: Frame[],
  format: ExportFormat,
  options: EncodeOptions = {},
): Promise<Blob> {
  if (frames.length === 0) throw new Error("nothing to encode")
  const { quality = 0.92, loop = 0 } = options
  const { width, height } = frames[0].canvas

  if (format === "png") return toBlob(frames[0].canvas, "image/png")

  if (format === "gif") {
    const gif = encodeGif(
      frames.map((frame): GifFrame => {
        const { data } = imageData(frame.canvas)
        return { data, delay: frame.delay }
      }),
      { width, height, loop },
    )
    return new Blob([gif as unknown as BlobPart], { type: "image/gif" })
  }

  if (frames.length === 1) return toBlob(frames[0].canvas, "image/webp", quality)
  const encoded = await Promise.all(
    frames.map(async (frame) => ({
      delay: frame.delay,
      data: new Uint8Array(await (await toBlob(frame.canvas, "image/webp", quality)).arrayBuffer()),
    })),
  )
  const webp = muxAnimatedWebp(encoded, { width, height, loop })
  return new Blob([webp as unknown as BlobPart], { type: "image/webp" })
}

/** Hand the file to the browser. Nothing leaves the page. */
export function download(blob: Blob, filename: string) {
  const url = URL.createObjectURL(blob)
  const anchor = document.createElement("a")
  anchor.href = url
  anchor.download = filename
  anchor.rel = "noopener"
  document.body.append(anchor)
  anchor.click()
  anchor.remove()
  // Revoking immediately races the download in Safari; a tick is enough.
  setTimeout(() => URL.revokeObjectURL(url), 1000)
}

export interface ExportOptions extends RecordOptions, EncodeOptions {
  format?: ExportFormat
  /** File stem. The extension comes from the format. */
  name?: string
  /**
   * What to do with the finished file. Defaults to {@link download}, which
   * hands it to the browser.
   *
   * The way out of a page is not always the downloads folder: a page holding a
   * directory handle can write the blob into a repository instead, which is
   * where a screenshot was going anyway.
   */
  save?: (blob: Blob, filename: string) => void | Promise<void>
}

export interface ExportResult {
  blob: Blob
  filename: string
  frames: number
  width: number
  height: number
}

/** Record a target and save it. The whole path, for a button to call. */
export async function exportNode(
  target: CaptureTarget,
  options: ExportOptions = {},
): Promise<ExportResult> {
  const format = options.format ?? "webp"
  // A still is a still whatever the duration says, and PNG has no animation.
  const duration = format === "png" ? 0 : options.duration ?? 0
  const frames = await record(target, { ...options, duration })
  const blob = await encodeFrames(frames, format, options)
  const filename = exportFileName(options.name ?? "robocn", format)
  await (options.save ?? download)(blob, filename)
  return {
    blob,
    filename,
    frames: frames.length,
    width: frames[0].canvas.width,
    height: frames[0].canvas.height,
  }
}

/**
 * A GIF89a encoder, in TypeScript, with no dependencies.
 *
 * Written for flat vector art: median-cut quantization on a 5-bit histogram, a
 * nearest-colour cache keyed by that same 15-bit index, LZW with dictionary
 * resets, and a **local** colour table per frame. Drawings here use few colours
 * and hard edges, so a per-frame table is smaller and exact where one global
 * table would be neither, and there is no dithering to make a flat fill crawl
 * between frames.
 *
 * Reasoning and the format choices: `docs/export.md`.
 */

/** One frame: RGBA bytes, and how long it stays on screen. */
export interface GifFrame {
  /** `width * height * 4` bytes, straight from a canvas. */
  data: Uint8ClampedArray | Uint8Array
  /** Milliseconds. GIF stores hundredths, so this is rounded to 10 ms. */
  delay: number
}

export interface GifOptions {
  width: number
  height: number
  /** Repeat count; 0 — the default — is forever. */
  loop?: number
  /** Alpha at or below this is written as the transparent index. */
  alphaThreshold?: number
}

export interface Quantized {
  /** Up to 256 colours, three bytes each, in table order. */
  palette: Uint8Array
  /** One palette index per pixel. */
  indices: Uint8Array
  /** The index reserved for transparency, or null when the frame is opaque. */
  transparent: number | null
}

/** GIF counts time in hundredths of a second, and browsers floor a 1 to 10 ms. */
export const centiseconds = (ms: number) => Math.max(2, Math.round(ms / 10))

/** The 15-bit histogram key: five bits a channel, the precision of the cut. */
const key = (r: number, g: number, b: number) =>
  ((r >> 3) << 10) | ((g >> 3) << 5) | (b >> 3)

interface Bucket {
  count: number
  r: number
  g: number
  b: number
  key: number
}

interface Box {
  buckets: Bucket[]
  count: number
}

/** The channel a box is widest in — the one worth splitting. */
function widest(box: Box): { channel: "r" | "g" | "b"; range: number } {
  let lowR = 255
  let highR = 0
  let lowG = 255
  let highG = 0
  let lowB = 255
  let highB = 0
  for (const bucket of box.buckets) {
    const r = bucket.r / bucket.count
    const g = bucket.g / bucket.count
    const b = bucket.b / bucket.count
    if (r < lowR) lowR = r
    if (r > highR) highR = r
    if (g < lowG) lowG = g
    if (g > highG) highG = g
    if (b < lowB) lowB = b
    if (b > highB) highB = b
  }
  // Weighted the way the eye is, so a green box splits before a blue one of the
  // same numeric width.
  const spread = [
    { channel: "r" as const, range: (highR - lowR) * 1.0 },
    { channel: "g" as const, range: (highG - lowG) * 1.2 },
    { channel: "b" as const, range: (highB - lowB) * 0.8 },
  ]
  return spread.sort((a, b) => b.range - a.range)[0]
}

/**
 * Median cut: split the box holding the most pixels along its widest channel,
 * at the point half its pixels lie either side, until there are as many boxes
 * as the palette has room for.
 */
function cut(buckets: Bucket[], maxColors: number): Box[] {
  let boxes: Box[] = [
    { buckets, count: buckets.reduce((total, bucket) => total + bucket.count, 0) },
  ]
  while (boxes.length < maxColors) {
    // Only a box with something to split is a candidate; a box holding one
    // colour is finished however many pixels it has.
    const candidates = boxes.filter((box) => box.buckets.length > 1)
    if (candidates.length === 0) break
    const target = candidates.reduce((best, box) => (box.count > best.count ? box : best))
    const { channel } = widest(target)
    const sorted = [...target.buckets].sort(
      (a, b) => a[channel] / a.count - b[channel] / b.count,
    )
    const half = target.count / 2
    let running = 0
    let split = 0
    while (split < sorted.length - 1 && running + sorted[split].count <= half) {
      running += sorted[split].count
      split += 1
    }
    if (split === 0) split = 1
    const left = sorted.slice(0, split)
    const right = sorted.slice(split)
    const total = (list: Bucket[]) => list.reduce((sum, bucket) => sum + bucket.count, 0)
    boxes = boxes.filter((box) => box !== target)
    boxes.push({ buckets: left, count: total(left) }, { buckets: right, count: total(right) })
  }
  return boxes
}

/**
 * RGBA pixels to a palette and an index per pixel. `maxColors` is the whole
 * table; a frame with transparency spends one slot of it on the hole.
 */
export function quantize(
  data: Uint8ClampedArray | Uint8Array,
  maxColors = 256,
  alphaThreshold = 127,
): Quantized {
  const pixels = data.length / 4
  const histogram = new Map<number, Bucket>()
  let translucent = false
  for (let index = 0; index < pixels; index += 1) {
    const offset = index * 4
    if (data[offset + 3] <= alphaThreshold) {
      translucent = true
      continue
    }
    const r = data[offset]
    const g = data[offset + 1]
    const b = data[offset + 2]
    const id = key(r, g, b)
    const bucket = histogram.get(id)
    if (bucket) {
      bucket.count += 1
      bucket.r += r
      bucket.g += g
      bucket.b += b
    } else {
      histogram.set(id, { count: 1, r, g, b, key: id })
    }
  }

  const transparent = translucent ? 0 : null
  const room = Math.max(1, maxColors - (translucent ? 1 : 0))
  const boxes = cut([...histogram.values()], room)
  const colours: number[][] = boxes
    .filter((box) => box.count > 0)
    .map((box) => {
      let count = 0
      let r = 0
      let g = 0
      let b = 0
      for (const bucket of box.buckets) {
        count += bucket.count
        r += bucket.r
        g += bucket.g
        b += bucket.b
      }
      return count === 0
        ? [0, 0, 0]
        : [Math.round(r / count), Math.round(g / count), Math.round(b / count)]
    })
  if (colours.length === 0) colours.push([0, 0, 0])

  // The transparent slot goes first so its index is a constant: the writer
  // names index 0 in the graphic control extension.
  const table = translucent ? [[0, 0, 0], ...colours] : colours
  const palette = new Uint8Array(table.length * 3)
  table.forEach((colour, index) => {
    palette[index * 3] = colour[0]
    palette[index * 3 + 1] = colour[1]
    palette[index * 3 + 2] = colour[2]
  })

  const first = translucent ? 1 : 0
  const cache = new Map<number, number>()
  const nearest = (r: number, g: number, b: number) => {
    const id = key(r, g, b)
    const hit = cache.get(id)
    if (hit !== undefined) return hit
    let best = first
    let bestDistance = Infinity
    for (let index = first; index < table.length; index += 1) {
      const dr = r - table[index][0]
      const dg = g - table[index][1]
      const db = b - table[index][2]
      const distance = dr * dr * 1.0 + dg * dg * 1.2 + db * db * 0.8
      if (distance < bestDistance) {
        bestDistance = distance
        best = index
      }
    }
    cache.set(id, best)
    return best
  }

  const indices = new Uint8Array(pixels)
  for (let index = 0; index < pixels; index += 1) {
    const offset = index * 4
    if (data[offset + 3] <= alphaThreshold) {
      indices[index] = 0
      continue
    }
    indices[index] = nearest(data[offset], data[offset + 1], data[offset + 2])
  }

  return { palette, indices, transparent }
}

/** LZW as GIF specifies it: LSB-first codes, a reset when the dictionary fills. */
export function lzwEncode(indices: Uint8Array, minCodeSize: number): Uint8Array {
  const clear = 1 << minCodeSize
  const end = clear + 1
  const out: number[] = []
  let bits = 0
  let held = 0
  let codeSize = minCodeSize + 1
  let next = end + 1
  let dictionary = new Map<number, number>()

  const emit = (code: number) => {
    held |= code << bits
    bits += codeSize
    while (bits >= 8) {
      out.push(held & 0xff)
      held >>= 8
      bits -= 8
    }
  }

  emit(clear)
  let prefix = indices.length > 0 ? indices[0] : -1
  for (let index = 1; index < indices.length; index += 1) {
    const char = indices[index]
    const pair = (prefix << 8) | char
    const known = dictionary.get(pair)
    if (known !== undefined) {
      prefix = known
      continue
    }
    emit(prefix)
    if (next < 4096) {
      dictionary.set(pair, next)
      next += 1
      // Grow the code only once the dictionary genuinely needs the extra bit.
      if (next - 1 === 1 << codeSize && codeSize < 12) codeSize += 1
    } else {
      emit(clear)
      dictionary = new Map()
      codeSize = minCodeSize + 1
      next = end + 1
    }
    prefix = char
  }
  if (prefix !== -1) emit(prefix)
  emit(end)
  if (bits > 0) out.push(held & 0xff)
  return Uint8Array.from(out)
}

/** A growable byte sink, because a GIF's length is not known until it is written. */
class Bytes {
  private data = new Uint8Array(1024)
  private length = 0

  push(...values: number[]) {
    this.reserve(values.length)
    for (const value of values) {
      this.data[this.length] = value
      this.length += 1
    }
  }

  short(value: number) {
    this.push(value & 0xff, (value >> 8) & 0xff)
  }

  bytes(values: Uint8Array) {
    this.reserve(values.length)
    this.data.set(values, this.length)
    this.length += values.length
  }

  ascii(text: string) {
    this.push(...[...text].map((character) => character.charCodeAt(0)))
  }

  /** LZW output rides in blocks of at most 255 bytes, each with its length. */
  blocks(values: Uint8Array) {
    for (let start = 0; start < values.length; start += 255) {
      const chunk = values.subarray(start, Math.min(start + 255, values.length))
      this.push(chunk.length)
      this.bytes(chunk)
    }
    this.push(0)
  }

  private reserve(extra: number) {
    if (this.length + extra <= this.data.length) return
    let size = this.data.length * 2
    while (size < this.length + extra) size *= 2
    const grown = new Uint8Array(size)
    grown.set(this.data.subarray(0, this.length))
    this.data = grown
  }

  done() {
    return this.data.slice(0, this.length)
  }
}

/** The smallest table size the format allows for this many colours: a power of two, at least 4. */
const tableBits = (colours: number) => {
  let bits = 2
  while (1 << bits < colours) bits += 1
  return Math.min(8, bits)
}

/**
 * Frames to a GIF89a file. Every frame is full-size and carries its own colour
 * table; a frame with transparency disposes to the background so the next one
 * does not show through the hole.
 */
export function encodeGif(frames: GifFrame[], options: GifOptions): Uint8Array {
  const { width, height, loop = 0, alphaThreshold = 127 } = options
  if (frames.length === 0) throw new Error("a GIF needs at least one frame")
  const out = new Bytes()

  out.ascii("GIF89a")
  out.short(width)
  out.short(height)
  // No global colour table: 0x70 is "8 bits of colour resolution, no GCT".
  out.push(0x70, 0, 0)

  // NETSCAPE 2.0 — the de facto looping extension.
  out.push(0x21, 0xff, 0x0b)
  out.ascii("NETSCAPE2.0")
  out.push(0x03, 0x01)
  out.short(loop)
  out.push(0)

  for (const frame of frames) {
    const { palette, indices, transparent } = quantize(frame.data, 256, alphaThreshold)
    const colours = palette.length / 3
    const bits = tableBits(colours)
    const slots = 1 << bits

    // Disposal 2 — restore to background — is the only way a transparent frame
    // can replace rather than layer over the one before it.
    const disposal = transparent === null ? 1 : 2
    out.push(0x21, 0xf9, 0x04)
    out.push((disposal << 2) | (transparent === null ? 0 : 1))
    out.short(centiseconds(frame.delay))
    out.push(transparent ?? 0, 0)

    out.push(0x2c)
    out.short(0)
    out.short(0)
    out.short(width)
    out.short(height)
    out.push(0x80 | (bits - 1))

    const table = new Uint8Array(slots * 3)
    table.set(palette.subarray(0, Math.min(palette.length, table.length)))
    out.bytes(table)

    const minCodeSize = Math.max(2, bits)
    out.push(minCodeSize)
    out.blocks(lzwEncode(indices, minCodeSize))
  }

  out.push(0x3b)
  return out.done()
}

/**
 * Animated WebP without an encoder.
 *
 * There is no `VideoEncoder` for WebP and no VP8 encoder worth shipping in
 * TypeScript — but every browser already has one behind
 * `canvas.toBlob("image/webp")`, which returns a complete single-image WebP
 * file. An animated WebP is exactly those files' payload chunks re-housed in
 * frame headers, so this module never touches a pixel: it reads each file's
 * chunk list, drops the container, and re-emits the chunks inside `ANMF`.
 *
 * Container: RIFF, `VP8X` (canvas size + flags), `ANIM` (background, loop),
 * then one `ANMF` a frame. Notes: `docs/export.md`.
 */

/** A RIFF chunk: a four-character code and its payload, unpadded. */
export interface WebpChunk {
  fourcc: string
  data: Uint8Array
}

/** One frame: a whole single-image WebP file, and how long it stays up. */
export interface WebpFrame {
  data: Uint8Array
  /** Milliseconds; WebP stores them directly, to 24 bits. */
  delay: number
}

export interface WebpOptions {
  width: number
  height: number
  /** Repeat count; 0 — the default — is forever. */
  loop?: number
  /** Canvas background as RGBA bytes. Transparent by default. */
  background?: [number, number, number, number]
}

const ascii = (bytes: Uint8Array, at: number) =>
  String.fromCharCode(bytes[at], bytes[at + 1], bytes[at + 2], bytes[at + 3])

const readU32 = (bytes: Uint8Array, at: number) =>
  bytes[at] | (bytes[at + 1] << 8) | (bytes[at + 2] << 16) | (bytes[at + 3] << 24 >>> 0)

/**
 * The chunks of a WebP file, in order, with the 12-byte RIFF header gone.
 * Throws on anything that is not a WebP, because the alternative is muxing
 * rubbish into a file that fails silently in an image viewer.
 */
export function readChunks(file: Uint8Array): WebpChunk[] {
  if (file.length < 12 || ascii(file, 0) !== "RIFF" || ascii(file, 8) !== "WEBP") {
    throw new Error("not a WebP file")
  }
  const chunks: WebpChunk[] = []
  let at = 12
  while (at + 8 <= file.length) {
    const fourcc = ascii(file, at)
    const size = readU32(file, at + 4)
    const start = at + 8
    if (start + size > file.length) break
    chunks.push({ fourcc, data: file.subarray(start, start + size) })
    // Every chunk is padded to an even length; the pad byte is not its data.
    at = start + size + (size % 2)
  }
  return chunks
}

/** A frame's own dimensions, read out of the bitstream header it carries. */
export function frameSize(chunks: WebpChunk[]): { width: number; height: number } | null {
  const lossy = chunks.find((chunk) => chunk.fourcc === "VP8 ")
  if (lossy && lossy.data.length >= 10) {
    const data = lossy.data
    // 3-byte frame tag, then the start code, then 14-bit width and height.
    if (data[3] === 0x9d && data[4] === 0x01 && data[5] === 0x2a) {
      return {
        width: (data[6] | (data[7] << 8)) & 0x3fff,
        height: (data[8] | (data[9] << 8)) & 0x3fff,
      }
    }
  }
  const lossless = chunks.find((chunk) => chunk.fourcc === "VP8L")
  if (lossless && lossless.data.length >= 5 && lossless.data[0] === 0x2f) {
    const bits =
      lossless.data[1] | (lossless.data[2] << 8) | (lossless.data[3] << 16) | (lossless.data[4] << 24)
    return { width: (bits & 0x3fff) + 1, height: ((bits >> 14) & 0x3fff) + 1 }
  }
  return null
}

/** Whether a frame carries alpha: a lossless bitstream, or a lossy one with `ALPH`. */
export const hasAlpha = (chunks: WebpChunk[]) =>
  chunks.some((chunk) => chunk.fourcc === "ALPH" || chunk.fourcc === "VP8L")

/**
 * The chunks that are the picture itself, and may live inside a frame.
 *
 * Everything else a single-image file carries is document-level furniture. A
 * colour profile in particular is a file-level chunk: Chrome writes an `ICCP`
 * into every WebP it encodes, and copying those into the frames produces a file
 * libwebp rejects outright as a corrupt header.
 */
export const imageChunks = (chunks: WebpChunk[]) =>
  chunks.filter(
    (chunk) => chunk.fourcc === "ALPH" || chunk.fourcc === "VP8 " || chunk.fourcc === "VP8L",
  )

class Bytes {
  private data = new Uint8Array(1024)
  private length = 0

  push(...values: number[]) {
    this.reserve(values.length)
    for (const value of values) {
      this.data[this.length] = value
      this.length += 1
    }
  }

  /** 24-bit little-endian: what WebP uses for sizes, offsets and durations. */
  u24(value: number) {
    this.push(value & 0xff, (value >> 8) & 0xff, (value >> 16) & 0xff)
  }

  u32(value: number) {
    this.push(value & 0xff, (value >> 8) & 0xff, (value >> 16) & 0xff, (value >>> 24) & 0xff)
  }

  ascii(text: string) {
    this.push(...[...text].map((character) => character.charCodeAt(0)))
  }

  bytes(values: Uint8Array) {
    this.reserve(values.length)
    this.data.set(values, this.length)
    this.length += values.length
  }

  get size() {
    return this.length
  }

  private reserve(extra: number) {
    if (this.length + extra <= this.data.length) return
    let size = this.data.length * 2
    while (size < this.length + extra) size *= 2
    const grown = new Uint8Array(size)
    grown.set(this.data.subarray(0, this.length))
    this.data = grown
  }

  done() {
    return this.data.slice(0, this.length)
  }
}

const chunk = (out: Bytes, fourcc: string, payload: Uint8Array) => {
  out.ascii(fourcc)
  out.u32(payload.length)
  out.bytes(payload)
  if (payload.length % 2 === 1) out.push(0)
}

/**
 * Single-image WebP files to one animated WebP.
 *
 * Every frame covers the whole canvas and replaces what is under it — blending
 * off, disposal none — which is what a recording of a moving drawing wants: no
 * frame is a delta, so a seek lands on a complete picture.
 */
export function muxAnimatedWebp(frames: WebpFrame[], options: WebpOptions): Uint8Array {
  const { width, height, loop = 0, background = [0, 0, 0, 0] } = options
  if (frames.length === 0) throw new Error("an animation needs at least one frame")
  if (width < 1 || height < 1) throw new Error("an animation needs a canvas")

  const files = frames.map((frame) => ({
    delay: Math.max(0, Math.round(frame.delay)),
    chunks: readChunks(frame.data),
  }))
  const parsed = files.map((frame) => ({ delay: frame.delay, chunks: imageChunks(frame.chunks) }))
  // One colour profile for the animation, taken from the frames — they all came
  // out of the same encoder, so the first one that has it speaks for all.
  const profile = files
    .flatMap((frame) => frame.chunks)
    .find((entry) => entry.fourcc === "ICCP")

  const body = new Bytes()

  const vp8x = new Bytes()
  // Flags, high bit first: reserved, reserved, ICC, alpha, EXIF, XMP, animation.
  vp8x.push(
    0x02 |
      (parsed.some((frame) => hasAlpha(frame.chunks)) ? 0x10 : 0) |
      (profile ? 0x20 : 0),
  )
  vp8x.u24(0)
  vp8x.u24(width - 1)
  vp8x.u24(height - 1)
  chunk(body, "VP8X", vp8x.done())

  // Order is the format's, not a preference: VP8X, then ICCP, then ANIM.
  if (profile) chunk(body, "ICCP", profile.data)

  const anim = new Bytes()
  // The background is BGRA in the file, whatever order it arrived in here.
  anim.push(background[2], background[1], background[0], background[3])
  anim.push(loop & 0xff, (loop >> 8) & 0xff)
  chunk(body, "ANIM", anim.done())

  for (const frame of parsed) {
    const payload = new Bytes()
    payload.u24(0)
    payload.u24(0)
    payload.u24(width - 1)
    payload.u24(height - 1)
    payload.u24(frame.delay)
    // Bit 1 set: do not blend, overwrite. Bit 0 clear: do not dispose.
    payload.push(0x02)
    for (const entry of frame.chunks) chunk(payload, entry.fourcc, entry.data)
    chunk(body, "ANMF", payload.done())
  }

  const file = new Bytes()
  file.ascii("RIFF")
  file.u32(body.size + 4)
  file.ascii("WEBP")
  file.bytes(body.done())
  return file.done()
}