image-peek

1import type {
2  EngineInterface,
3  Register,
4  RenderViewport,
5  ResolveInput,
6} from "claude-code";
7
8import { decode, shrink } from "./decode";
9import { readLook } from "./options";
10import type { Look } from "./options";
11import { caption, cells, findImages, fit } from "./pixels";
12import type { Found, Pixmap } from "./pixels";
13import { render, strips } from "./render";
14import type { Backdrop } from "./render";
15
16// Image Reads fold into a ToolGroup line ("read 2 files"), which hides them.
17// A group holding an image is unfolded, so each call becomes a ToolUse row,
18// and an image call's row is drawn here: the engine's header and result line,
19// then the picture. A standalone call's result (ToolResult) gets the same
20// picture under its line.
21//
22// PNG, JPEG, GIF and WebP are decoded in the module (decode.ts): it runs no
23// program and needs nothing installed. Pictures are kept at most 768 px a
24// side and drawn per box size by render.ts, ~25 ms, kept, so a scroll redraw
25// costs nothing.
26
27const INDENT = 5; // "  ⎿  "
28const MARGIN = 6; // kept free right of a picture
29const DECODE_PX = 768;
30/** Decoded pictures kept (each up to 768² RGBA, 2.4 MB). */
31const KEEP_DECODED = 24;
32/** Drawn boxes kept (a few KB each). */
33const KEEP_DRAWN = 48;
34
35/** A decoded picture, or why there is none. */
36type Decoded = Pixmap | string;
37
38// Caches, not state: a reload decodes and draws again on the next draw.
39const decoded = new Map<string, Decoded>();
40const drawn = new Map<string, Uint32Array>();
41// Calls whose group this mod unfolded: their ToolUse rows carry the picture.
42const unfolded = new Set<string>();
43
44function keep<V>(cache: Map<string, V>, name: string, value: V, size: number) {
45  cache.set(name, value);
46  for (const [oldest] of cache) {
47    if (cache.size <= size) break;
48    cache.delete(oldest);
49  }
50}
51
52const message = (error: unknown) => (error instanceof Error ? error.message : String(error));
53
54function runDecode(found: Found): Decoded {
55  let bytes: Uint8Array;
56  try {
57    bytes = Uint8Array.fromBase64(found.base64);
58  } catch {
59    return "unreadable base64";
60  }
61  try {
62    return shrink(decode(bytes), DECODE_PX);
63  } catch (error) {
64    return message(error);
65  }
66}
67
68function decodeOnce(slot: string, found: Found): Decoded {
69  let known = decoded.get(slot);
70  if (known === undefined) {
71    known = runDecode(found);
72    keep(decoded, slot, known, KEEP_DECODED);
73  }
74
75  return known;
76}
77
78/** The picture's cells for a box, drawn once per picture, size and look. */
79function cellWords(
80  slot: string,
81  pic: Pixmap,
82  columns: number,
83  rows: number,
84  look: Look,
85  background: Backdrop,
86) {
87  const at = [slot, columns, rows, look.glyphs, look.aspect, background.color, background.exact].join(":");
88  let known = drawn.get(at);
89  if (known === undefined) {
90    known = render(pic, columns, rows, { glyphs: look.glyphs, aspect: look.aspect, background });
91    keep(drawn, at, known, KEEP_DRAWN);
92  }
93
94  return known;
95}
96
97/**
98 * The terminal's background: the person's colour when given, exact; else a
99 * dark grey (the default theme is dark), used only to blend see-through
100 * edges. Claude Code's theme setting is not read: reading settings puts the
101 * mod on a directory review hold.
102 */
103function backdrop(look: Look): Backdrop {
104  return look.background !== undefined
105    ? { color: look.background, exact: true }
106    : { color: 0x1e1e1e, exact: false };
107}
108
109function shortPath(path: string, cwd: string): string {
110  return path.startsWith(`${cwd}/`) ? path.slice(cwd.length + 1) : path;
111}
112
113/** One `⎿ caption` line and its picture per image. */
114async function pictures(
115  $: EngineInterface,
116  e: ResolveInput<"ToolUse" | "ToolResult", "terminal"> & { viewport?: RenderViewport },
117  id: string,
118  found: Found[],
119  look: Look,
120) {
121  const { Box, Text, Raster, Image } = $.ui.resolve(e);
122  const width = (e.viewport?.columns ?? 80) - INDENT - MARGIN;
123  const background = backdrop(look);
124  const results = found.map((one, i) => decodeOnce(`${id}:${i}`, one));
125
126  return found.map((one, i) => {
127    const pic = results[i] ?? "not decoded";
128    const lead = i === 0 ? "  ⎿  " : "     ";
129    const slot = `${id}:${i}`;
130    const maxColumns = Math.min(look.maxColumns, width);
131    let body;
132    if (typeof pic === "string") {
133      body = <Text dimColor>(no preview: {pic})</Text>;
134    } else if (look.renderer === "image") {
135      const box = fit(pic, maxColumns, look.maxRows, look.aspect);
136      body = (
137        <Image
138          source={{ rgba: pic.rgba.toBase64(), width: pic.width, height: pic.height }}
139          columns={box.columns}
140          rows={box.rows}
141          alt={caption(one)}
142        />
143      );
144    } else if (look.renderer === "half") {
145      const box = fit(pic, maxColumns, look.maxRows);
146      body = (
147        <Raster key={slot} columns={box.columns} rows={box.rows} cells={cells(pic, box.columns, box.rows)} />
148      );
149    } else {
150      const box = fit(pic, maxColumns, look.maxRows, look.aspect);
151      const words = cellWords(slot, pic, box.columns, box.rows, look, background);
152      // Stacked strips: a Raster paints at most 1024 colour pairs.
153      body = (
154        <Box flexDirection="column">
155          {strips(words, box.columns, box.rows).map((strip, s) => (
156            <Raster
157              key={`${slot}:${s}`}
158              columns={box.columns}
159              rows={strip.rows}
160              cells={strip.cells}
161            />
162          ))}
163        </Box>
164      );
165    }
166
167    return (
168      <Box key={`${id}:${i}`} flexDirection="column">
169        <Box>
170          <Text dimColor>{lead}</Text>
171          <Text>{caption(one)}</Text>
172        </Box>
173        <Box marginLeft={INDENT}>{body}</Box>
174      </Box>
175    );
176  });
177}
178
179export const register: Register = (on, options) => {
180  const look = readLook(options);
181
182  on("ui.render", { component: "ToolGroup" }, async ($, e, next) => {
183    if (e.surface !== "terminal") return next(e);
184
185    const withImages = e.props.calls.filter(
186      (call) =>
187        !call.isRunning &&
188        call.tool_use_id !== undefined &&
189        findImages(call.output).length > 0,
190    );
191    if (withImages.length === 0) return next(e);
192
193    for (const call of withImages) unfolded.add(call.tool_use_id as string);
194
195    return next({ ...e, props: { ...e.props, isExpanded: true } });
196  }).catch(($, e, next) => next(e));
197
198  on("ui.render", { component: "ToolUse" }, async ($, e, next) => {
199    if (e.surface !== "terminal" || !unfolded.has(e.props.tool_use_id)) {
200      return next(e);
201    }
202    const found = findImages(e.props.output);
203    if (found.length === 0) return next(e);
204
205    const { Box, Text } = $.ui.resolve(e);
206    const input = (e.props.input ?? {}) as Record<string, unknown>;
207    const path = typeof input.file_path === "string" ? input.file_path : undefined;
208    const arg = path === undefined ? "" : `(${shortPath(path, await $.session.cwd())})`;
209    const drawn = await pictures($, e, e.props.tool_use_id, found, look);
210
211    return (
212      <Box flexDirection="column">
213        <Box>
214          <Text color={e.props.isErrored ? "error" : "success"}>● </Text>
215          <Text bold>{e.props.tool}</Text>
216          <Text wrap="truncate-middle">{arg}</Text>
217        </Box>
218        {drawn}
219      </Box>
220    );
221  }).catch(($, e, next) => next(e));
222
223  on("ui.render", { component: "ToolResult" }, async ($, e, next) => {
224    if (e.surface !== "terminal" || e.props.isErrored) return next(e);
225    const found = findImages(e.props.output);
226    if (found.length === 0) return next(e);
227
228    const { Box } = $.ui.resolve(e);
229    const drawn = await pictures($, e, e.props.tool_use_id, found, look);
230
231    return <Box flexDirection="column">{drawn}</Box>;
232  }).catch(($, e, next) => next(e));
233};
234

1// Picture bytes to pixels: PNG, JPEG, GIF and WebP, decoded here in plain
2// code, so nothing has to be installed and no program is run. A JPEG kind the
3// decoder refuses (arithmetic-coded, 12-bit, lossless) gets no preview.
4
5import { decodeGif, isGif } from "./gif";
6import { decodeJpeg, isJpeg } from "./jpeg";
7import { resample } from "./pixels";
8import type { Pixmap } from "./pixels";
9import { decodePng, isPng } from "./png";
10import { decodeWebp, isWebp } from "./webp";
11
12/** The largest picture decoded here: 16.8 megapixels (a 12 MP photo, a 4K screen). */
13export const MAX_PIXELS = 1 << 24;
14
15export type Format = "png" | "jpeg" | "gif" | "webp" | "other";
16
17/** The format by the file's first bytes, whatever it was called. */
18export function format(bytes: Uint8Array): Format {
19  if (isPng(bytes)) return "png";
20  if (isJpeg(bytes)) return "jpeg";
21  if (isGif(bytes)) return "gif";
22  if (isWebp(bytes)) return "webp";
23
24  return "other";
25}
26
27/** Decodes a PNG, JPEG, GIF or WebP (the first frame); throws for anything else. */
28export function decode(bytes: Uint8Array): Pixmap {
29  switch (format(bytes)) {
30    case "png":
31      return decodePng(bytes, MAX_PIXELS);
32    case "jpeg":
33      return decodeJpeg(bytes, MAX_PIXELS);
34    case "gif":
35      return decodeGif(bytes, MAX_PIXELS);
36    case "webp":
37      return decodeWebp(bytes, MAX_PIXELS);
38    default:
39      throw new Error("not a PNG, JPEG, GIF or WebP");
40  }
41}
42
43/** The picture with its longer side at most `side` pixels, box-filtered. */
44export function shrink(img: Pixmap, side: number): Pixmap {
45  const scale = side / Math.max(img.width, img.height);
46  if (scale >= 1) return img;
47
48  return resample(
49    img,
50    Math.max(1, Math.round(img.width * scale)),
51    Math.max(1, Math.round(img.height * scale)),
52  );
53}
54

1// The plugin's options (`userConfig` in plugin.json) as the module uses them,
2// each falling back to its default when unset or out of range.
3
4import { DEFAULT_ASPECT } from "./render";
5import type { Glyphs } from "./render";
6
7export type Look = {
8  maxColumns: number;
9  maxRows: number;
10  renderer: "cells" | "half" | "image";
11  glyphs: Glyphs;
12  /** A cell's height over its width. */
13  aspect: number;
14  /** The terminal's background as the person gave it; unset, unknown. */
15  background: number | undefined;
16};
17
18/** `#rrggbb` (or `rrggbb`) as a colour; anything else is unset. */
19export function parseColor(text: unknown): number | undefined {
20  const m = typeof text === "string" ? /^#?([0-9a-f]{6})$/i.exec(text.trim()) : null;
21
22  return m ? parseInt(m[1]!, 16) : undefined;
23}
24
25export function readLook(options: Readonly<Record<string, unknown>>): Look {
26  const aspect = Number(options.cellAspect);
27
28  return {
29    maxColumns: Number(options.maxColumns) || 64,
30    maxRows: Number(options.maxRows) || 18,
31    renderer: options.renderer === "image" || options.renderer === "half" ? options.renderer : "cells",
32    glyphs: options.glyphs === "wedges" ? "wedges" : "blocks",
33    aspect: aspect >= 1 && aspect <= 4 ? aspect : DEFAULT_ASPECT,
34    background: parseColor(options.background),
35  };
36}
37

1// Pure picture logic: finding images in a tool's output, fitting and
2// resampling a picture, and packing it into half-block Raster cells.
3
4// The runtime has these (ES2026); TypeScript 5's lib does not declare them yet.
5declare global {
6  interface Uint8Array {
7    toBase64(): string;
8  }
9  interface Uint8ArrayConstructor {
10    fromBase64(text: string): Uint8Array;
11  }
12}
13
14export type Found = {
15  base64: string;
16  mediaType?: string;
17  /** Size of the file the tool read, in bytes (Read only). */
18  bytes?: number;
19  /** The picture's own size before any resize for the model (Read only). */
20  width?: number;
21  height?: number;
22};
23
24export type Pixmap = { width: number; height: number; rgba: Uint8Array };
25
26const MAX_DEPTH = 6;
27
28type Obj = Record<string, unknown>;
29
30const isObj = (v: unknown): v is Obj =>
31  typeof v === "object" && v !== null && !Array.isArray(v);
32
33const str = (v: unknown): string | undefined =>
34  typeof v === "string" && v !== "" ? v : undefined;
35
36const num = (v: unknown): number | undefined =>
37  typeof v === "number" && Number.isFinite(v) ? v : undefined;
38
39function one(o: Obj): Found | undefined {
40  // Read: { type: "image", file: { base64, type, originalSize, dimensions } }
41  if (o.type === "image" && isObj(o.file)) {
42    const base64 = str(o.file.base64);
43    if (base64 === undefined) return undefined;
44    const dims = isObj(o.file.dimensions) ? o.file.dimensions : {};
45
46    return {
47      base64,
48      mediaType: str(o.file.type),
49      bytes: num(o.file.originalSize),
50      width: num(dims.originalWidth) ?? num(dims.displayWidth),
51      height: num(dims.originalHeight) ?? num(dims.displayHeight),
52    };
53  }
54  // Messages API block: { type: "image", source: { type: "base64", data, media_type } }
55  if (o.type === "image" && isObj(o.source)) {
56    const base64 = str(o.source.data);
57
58    return base64 === undefined
59      ? undefined
60      : { base64, mediaType: str(o.source.media_type) };
61  }
62  // MCP content block: { type: "image", data, mimeType }
63  if (o.type === "image") {
64    const base64 = str(o.data);
65
66    return base64 === undefined
67      ? undefined
68      : { base64, mediaType: str(o.mimeType) };
69  }
70  // Read's PDF page images: { base64, mediaType }
71  const mediaType = str(o.mediaType);
72  const base64 = str(o.base64);
73  if (base64 !== undefined && mediaType?.startsWith("image/")) {
74    return { base64, mediaType };
75  }
76
77  return undefined;
78}
79
80/** Every base64 image in a tool's output, in order. */
81export function findImages(output: unknown, depth = 0): Found[] {
82  if (depth > MAX_DEPTH) return [];
83  if (Array.isArray(output)) {
84    return output.flatMap((item) => findImages(item, depth + 1));
85  }
86  if (!isObj(output)) return [];
87
88  const found = one(output);
89  if (found !== undefined) return [found];
90
91  return Object.values(output).flatMap((v) => findImages(v, depth + 1));
92}
93
94/**
95 * The cell box a picture is drawn in: as wide as allowed, never wider than
96 * its pixels, aspect kept with a cell `aspect` times as tall as wide.
97 */
98export function fit(
99  img: { width: number; height: number },
100  maxColumns: number,
101  maxRows: number,
102  aspect = 2,
103): { columns: number; rows: number } {
104  const maxC = Math.max(1, Math.floor(maxColumns));
105  const maxR = Math.max(1, Math.floor(maxRows));
106  let columns = Math.min(maxC, img.width);
107  let rows = Math.ceil((columns * img.height) / img.width / aspect);
108  if (rows > maxR) {
109    rows = maxR;
110    columns = Math.min(maxC, Math.max(1, Math.ceil((rows * aspect * img.width) / img.height)));
111  }
112
113  return { columns, rows: Math.max(1, rows) };
114}
115
116/** Box-filter downscale (area average, alpha-weighted colour). */
117export function resample(img: Pixmap, width: number, height: number): Pixmap {
118  const out = new Uint8Array(width * height * 4);
119  for (let y = 0; y < height; y++) {
120    const y0 = Math.floor((y * img.height) / height);
121    const y1 = Math.max(y0 + 1, Math.floor(((y + 1) * img.height) / height));
122    for (let x = 0; x < width; x++) {
123      const x0 = Math.floor((x * img.width) / width);
124      const x1 = Math.max(x0 + 1, Math.floor(((x + 1) * img.width) / width));
125      let r = 0, g = 0, b = 0, a = 0, n = 0;
126      for (let sy = y0; sy < y1 && sy < img.height; sy++) {
127        for (let sx = x0; sx < x1 && sx < img.width; sx++) {
128          const i = (sy * img.width + sx) * 4;
129          const alpha = img.rgba[i + 3]!;
130          r += img.rgba[i]! * alpha;
131          g += img.rgba[i + 1]! * alpha;
132          b += img.rgba[i + 2]! * alpha;
133          a += alpha;
134          n++;
135        }
136      }
137      const o = (y * width + x) * 4;
138      if (a > 0) {
139        out[o] = Math.round(r / a);
140        out[o + 1] = Math.round(g / a);
141        out[o + 2] = Math.round(b / a);
142      }
143      out[o + 3] = n > 0 ? Math.round(a / n) : 0;
144    }
145  }
146
147  return { width, height, rgba: out };
148}
149
150const UPPER = 0x2580; // ▀
151const LOWER = 0x2584; // ▄
152const SPACE = 0x20;
153const DEFAULT = 0x01000000; // the terminal's own colour
154const OPAQUE = 128;
155
156/**
157 * Raster cells for a picture: one half block per cell, the top pixel as its
158 * foreground and the bottom as its background; transparent pixels show the
159 * terminal's own background.
160 */
161export function cells(img: Pixmap, columns: number, rows: number): string {
162  const px = resample(img, columns, rows * 2);
163  const words = new Uint32Array(columns * rows * 3);
164  const colour = (i: number) =>
165    (px.rgba[i]! << 16) | (px.rgba[i + 1]! << 8) | px.rgba[i + 2]!;
166
167  for (let row = 0; row < rows; row++) {
168    for (let col = 0; col < columns; col++) {
169      const top = ((row * 2) * columns + col) * 4;
170      const bottom = ((row * 2 + 1) * columns + col) * 4;
171      const hasTop = px.rgba[top + 3]! >= OPAQUE;
172      const hasBottom = px.rgba[bottom + 3]! >= OPAQUE;
173      const w = (row * columns + col) * 3;
174      if (hasTop) {
175        words[w] = UPPER;
176        words[w + 1] = colour(top);
177        words[w + 2] = hasBottom ? colour(bottom) : DEFAULT;
178      } else if (hasBottom) {
179        words[w] = LOWER;
180        words[w + 1] = colour(bottom);
181        words[w + 2] = DEFAULT;
182      } else {
183        words[w] = SPACE;
184        words[w + 1] = DEFAULT;
185        words[w + 2] = DEFAULT;
186      }
187    }
188  }
189
190  return new Uint8Array(words.buffer).toBase64();
191}
192
193/** `Read image (28.2KB) · 640×360`, as much of it as is known. */
194export function caption(found: Found): string {
195  const parts: string[] = [];
196  parts.push(
197    found.bytes === undefined
198      ? "Image"
199      : `Read image (${(found.bytes / 1024).toFixed(1)}KB)`,
200  );
201  if (found.width !== undefined && found.height !== undefined) {
202    parts.push(`${found.width}×${found.height}`);
203  }
204
205  return parts.join(" · ");
206}
207

1// The cell renderer: every terminal cell becomes the glyph and the two colours
2// that best reproduce the picture under it.
3//
4// A cell is sampled 8 × 16 in linear light (so texture finer than a sample
5// keeps its brightness), each sample then taken to OKLab (perceptual). Each
6// shape the terminal font can draw splits those samples in two, a sample on
7// an edge partly each side; the shape kept is the one whose two colours, each
8// side's OKLab mean, leave the least error.
9//
10// Means, not a least-squares fit: that overshoots on edge samples, to black.
11// OKLab means, not linear ones: an edge rarely lands on an eighth, and the
12// sliver left over brightens a dark side visibly in linear light (a band
13// along every edge of a screenshot).
14//
15// A Raster paints every colour on a 4-bit lattice (16 steps a channel,
16// rounded: measured 2026-10-07, every colour of a picture a multiple of 17
17// while the theme's colours around it were exact). Rounded as it comes, a
18// smooth gradient breaks into blotches, so colours are put on the lattice
19// here. A cell on a gradient gets its exact mean by mixing two lattice
20// colours inside it (quadrants as a fine dither) and hands what is left on
21// to its neighbours (Floyd–Steinberg); a flat cell is its nearest lattice
22// colour, plain; a cell with a real edge rounds each side; and, when the
23// terminal's background colour is known exactly, a colour within a hair of
24// it is the terminal's own colour, which is drawn exactly.
25//
26// Shapes are the ones Unicode defines: Block Elements tile the cell in
27// eighths, halves and quadrants, and the Powerline wedges (U+E0B8–E0BE, Nerd
28// Fonts only) fill it corner to corner. Terminals that draw these themselves
29// (most do) draw them so; a font's own glyphs can be a hair off.
30
31import type { Pixmap } from "./pixels";
32
33/**
34 * A cell's height over its width when nothing says otherwise: about 2 for
35 * most monospace fonts (Menlo, SF Mono, Cascadia, DejaVu), 2.2 for JetBrains
36 * Mono.
37 */
38export const DEFAULT_ASPECT = 2;
39
40/** The terminal's own colour, in a Raster's colour words. */
41export const DEFAULT = 0x01000000;
42
43/**
44 * The terminal's background: what see-through pixels are blended over and,
45 * when `exact` (the person gave the colour), what a colour within a hair of
46 * it is drawn as: the terminal's own colour, so a screenshot of the same
47 * theme has no visible frame. Not exact, it is a guess from the theme.
48 */
49export type Backdrop = { color: number; exact: boolean };
50
51const DARK: Backdrop = { color: 0x1e1e1e, exact: false };
52
53/**
54 * Distinct colour pairs one Raster paints; past that it snaps cells to the
55 * nearest it has. Per Raster (measured 2026-10-07: one 100×40 noise picture
56 * came out with exactly 1024, two 60×15 ones side by side with 900 each).
57 */
58const PAIRS = 1024;
59
60const SX = 8;
61const SY = 16;
62const N = SX * SY;
63/** Supersampling of each sample when measuring a shape's coverage. */
64const SS = 12;
65/**
66 * Error a split must save per sample (OKLab, squared) to beat a plain cell:
67 * keeps flat areas flat instead of tiling them with near-invisible shapes.
68 */
69const FLAT = 0.0001;
70/** A region less opaque than this shows the terminal's background. */
71const CLEAR = 1 / 16;
72/**
73 * Coverage's weight against OKLab in a fit (L spans 0 to 1): high, so where a
74 * picture ends inside a cell the split follows its edge, not a colour edge.
75 */
76const EDGE = 3;
77/** OKLab distance within which a colour is drawn as the terminal's own. */
78const NEAR_BACKGROUND = 0.01;
79/**
80 * OKLab distance within which the nearest lattice colour is drawn plain (its
81 * error kept, not handed on): about half a step. Lower, a lone cell off a
82 * flat fill dithers and shows as a speck.
83 */
84const QUIET = 0.012;
85/** Beside a flat fill, how far (OKLab) its plain colour is carried on. */
86const SEAM = 0.025;
87/**
88 * Two sides closer than this (OKLab) are drawn as one exact mixed colour:
89 * rounded apart they would show the lattice, not the picture.
90 */
91const FAINT = 0.025;
92/**
93 * A cell this even inside (OKLab RMS) is flat unless it sits on a gradient:
94 * both cells 1, 2 or 3 away along a row or a column differ from it by more
95 * than EVEN and less than STEEP (one differing is the side of an edge). Flat is one
96 * plain lattice colour, no dither, no error taken or handed on. A flat fill
97 * shifted by under half a step reads as the same fill; dithered, a
98 * screenshot's panels and backgrounds turn to noise.
99 */
100const EVEN = 0.004;
101const STEEP = 0.05;
102
103type Shape = {
104  /** Draws the inside in the foreground colour. */
105  glyph: number;
106  /** Draws the outside in the foreground colour, where the font has one. */
107  inverse?: number;
108  /** Coverage of each sample by the inside, 0 to 1. */
109  mask: Float32Array;
110  /** Σm, the inside's weight; the outside's is N − n. */
111  n: number;
112  // For the error of a blend m·c1 + (1−m)·c2: Σm², Σm(1−m), Σ(1−m)².
113  a: number;
114  b: number;
115  c: number;
116};
117
118function shape(
119  glyph: number,
120  inverse: number | undefined,
121  inside: (x: number, y: number) => boolean,
122): Shape {
123  const mask = new Float32Array(N);
124  for (let sy = 0; sy < SY; sy++) {
125    for (let sx = 0; sx < SX; sx++) {
126      let hits = 0;
127      for (let j = 0; j < SS; j++) {
128        for (let i = 0; i < SS; i++) {
129          if (inside((sx + (i + 0.5) / SS) / SX, (sy + (j + 0.5) / SS) / SY)) hits++;
130        }
131      }
132      mask[sy * SX + sx] = hits / (SS * SS);
133    }
134  }
135  let n = 0, a = 0, b = 0, c = 0;
136  for (const m of mask) {
137    n += m;
138    a += m * m;
139    b += m * (1 - m);
140    c += (1 - m) * (1 - m);
141  }
142
143  return { glyph, inverse, mask, n, a, b, c };
144}
145
146/** Block Elements: any font has these. */
147const BLOCKS: Shape[] = [
148  // Lower eighths: ink below k/8 from the top.
149  ...[1, 2, 3, 4, 5, 6, 7].map((k) =>
150    shape(0x2588 - k, k === 4 ? 0x2580 : k === 1 ? 0x2594 : undefined, (_x, y) => y >= k / 8),
151  ),
152  // Left blocks, in eighths.
153  shape(0x258f, undefined, (x) => x < 1 / 8),
154  shape(0x258e, undefined, (x) => x < 1 / 4),
155  shape(0x258d, undefined, (x) => x < 3 / 8),
156  shape(0x258c, 0x2590, (x) => x < 1 / 2),
157  shape(0x258b, undefined, (x) => x < 5 / 8),
158  shape(0x258a, undefined, (x) => x < 3 / 4),
159  shape(0x2589, 0x2595, (x) => x < 7 / 8),
160  // Quadrants, each with its three-quadrant complement.
161  shape(0x2598, 0x259f, (x, y) => x < 0.5 && y < 0.5),
162  shape(0x259d, 0x2599, (x, y) => x >= 0.5 && y < 0.5),
163  shape(0x2596, 0x259c, (x, y) => x < 0.5 && y >= 0.5),
164  shape(0x2597, 0x259b, (x, y) => x >= 0.5 && y >= 0.5),
165  shape(0x259a, 0x259e, (x, y) => x < 0.5 === y < 0.5),
166];
167
168/**
169 * Powerline wedges (Private Use Area, Nerd Fonts only): diagonal edges. The
170 * font's arrows and half-ellipses (U+E0B0–E0B6) were tried and left out: they
171 * fit thin diagonal lines as chains of bubbles.
172 */
173const WEDGES: Shape[] = [
174  shape(0xe0b8, 0xe0be, (x, y) => x < y), // lower-left / upper-right
175  shape(0xe0ba, 0xe0bc, (x, y) => x >= 1 - y), // lower-right / upper-left
176];
177
178const SETS = {
179  blocks: BLOCKS,
180  wedges: [...BLOCKS, ...WEDGES],
181};
182
183export type Glyphs = keyof typeof SETS;
184
185const LINEAR = Float32Array.from({ length: 256 }, (_, i) => {
186  const c = i / 255;
187  return c <= 0.04045 ? c / 12.92 : ((c + 0.055) / 1.055) ** 2.4;
188});
189
190/** Linear light to sRGB, 0 to 1, clamped. */
191function srgb(v: number): number {
192  const c = v <= 0 ? 0 : v >= 1 ? 1 : v;
193  return c <= 0.0031308 ? 12.92 * c : 1.055 * c ** (1 / 2.4) - 0.055;
194}
195
196/** Linear sRGB to OKLab, written into `out` at `o`. */
197function oklab(r: number, g: number, b: number, out: Float32Array | Float64Array, o: number) {
198  const l = Math.cbrt(0.4122214708 * r + 0.5363325363 * g + 0.0514459929 * b);
199  const m = Math.cbrt(0.2119034982 * r + 0.6806995451 * g + 0.1073969566 * b);
200  const s = Math.cbrt(0.0883024619 * r + 0.2817188376 * g + 0.6299787005 * b);
201  out[o] = 0.2104542553 * l + 0.793617785 * m - 0.0040720468 * s;
202  out[o + 1] = 1.9779984951 * l - 2.428592205 * m + 0.4505937099 * s;
203  out[o + 2] = 0.0259040371 * l + 0.7827717662 * m - 0.808675766 * s;
204}
205
206/** OKLab to linear sRGB (unclamped), written into `out`. */
207function linear(L: number, A: number, B: number, out: Float64Array) {
208  const l = (L + 0.3963377774 * A + 0.2158037573 * B) ** 3;
209  const m = (L - 0.1055613458 * A - 0.0638541728 * B) ** 3;
210  const s = (L - 0.0894841775 * A - 1.291485548 * B) ** 3;
211  out[0] = 4.0767416621 * l - 3.3077115913 * m + 0.2309699292 * s;
212  out[1] = -1.2684380046 * l + 2.6097574011 * m - 0.3413193965 * s;
213  out[2] = -0.0041960863 * l - 0.7034186147 * m + 1.707614701 * s;
214}
215
216const scratch = new Float64Array(3);
217
218/** OKLab to a 0xRRGGBB colour, clamped to sRGB. */
219function packLab(L: number, A: number, B: number): number {
220  linear(L, A, B, scratch);
221  const byte = (v: number) => Math.round(srgb(v) * 255);
222
223  return (byte(scratch[0]!) << 16) | (byte(scratch[1]!) << 8) | byte(scratch[2]!);
224}
225
226/** A backdrop colour in linear light and in OKLab. */
227function backdrop(color: number) {
228  const lin = [LINEAR[(color >> 16) & 255]!, LINEAR[(color >> 8) & 255]!, LINEAR[color & 255]!] as const;
229  const lab = new Float64Array(3);
230  oklab(lin[0], lin[1], lin[2], lab, 0);
231
232  return { lin, lab };
233}
234
235// The lattice: 16 steps a channel, colour i = (r << 8) | (g << 4) | b.
236const STEPS = 16;
237const LATTICE_LIN = new Float64Array(STEPS ** 3 * 3);
238const LATTICE_LAB = new Float64Array(STEPS ** 3 * 3);
239for (let i = 0; i < STEPS ** 3; i++) {
240  const r = LINEAR[((i >> 8) & 15) * 17]!;
241  const g = LINEAR[((i >> 4) & 15) * 17]!;
242  const b = LINEAR[(i & 15) * 17]!;
243  LATTICE_LIN[i * 3] = r;
244  LATTICE_LIN[i * 3 + 1] = g;
245  LATTICE_LIN[i * 3 + 2] = b;
246  oklab(r, g, b, LATTICE_LAB, i * 3);
247}
248
249const word = (i: number) =>
250  ((((i >> 8) & 15) * 17) << 16) | ((((i >> 4) & 15) * 17) << 8) | ((i & 15) * 17);
251
252function distance(lab: Float64Array, o: number, L: number, A: number, B: number) {
253  return (lab[o]! - L) ** 2 + (lab[o + 1]! - A) ** 2 + (lab[o + 2]! - B) ** 2;
254}
255
256/** The (up to) 8 lattice colours around an OKLab colour, into `out`. */
257function corners(L: number, A: number, B: number, out: Int32Array) {
258  linear(L, A, B, scratch);
259  const lo = [0, 0, 0];
260  const hi = [0, 0, 0];
261  for (let c = 0; c < 3; c++) {
262    const v = srgb(scratch[c]!) * 15;
263    lo[c] = Math.min(15, Math.floor(v));
264    hi[c] = Math.min(15, lo[c]! + 1);
265  }
266  for (let k = 0; k < 8; k++) {
267    out[k] =
268      ((k & 4 ? hi[0]! : lo[0]!) << 8) | ((k & 2 ? hi[1]! : lo[1]!) << 4) | (k & 1 ? hi[2]! : lo[2]!);
269  }
270}
271
272const around = new Int32Array(8);
273
274function nearest(L: number, A: number, B: number): number {
275  corners(L, A, B, around);
276  let best = around[0]!;
277  let bestD = Infinity;
278  for (const i of around) {
279    const d = distance(LATTICE_LAB, i * 3, L, A, B);
280    if (d < bestD) {
281      bestD = d;
282      best = i;
283    }
284  }
285
286  return best;
287}
288
289const mixed = new Float64Array(3);
290
291/**
292 * The glyphs a cell mixes two colours with, and the share the first gets:
293 * quadrants, the quarter turning from cell to cell and the checker flipping,
294 * so the dither is a fine irregular checker. Lower eighths and left blocks
295 * were tried (2026-10-07): neighbours pick alike, and their edges line up
296 * into streaks across or down the picture.
297 */
298function mixers(row: number, col: number) {
299  const turn = (row * 3 + col) % 4;
300
301  return [
302    [[0x2598, 0x2597, 0x259d, 0x2596][turn]!, 1 / 4],
303    [(row + col) % 2 ? 0x259a : 0x259e, 1 / 2],
304    [[0x259f, 0x259b, 0x2599, 0x259c][turn]!, 3 / 4],
305  ] as const;
306}
307
308/**
309 * A flat colour on the lattice: the nearest lattice colour, or that and
310 * another mixed in the cell (`mixers`), whichever looks closest. Returns what
311 * is drawn and its OKLab colour.
312 */
313function mix(L: number, A: number, B: number, row: number, col: number) {
314  const near = nearest(L, A, B);
315  let glyph = 0x20, fg = DEFAULT, bg = word(near);
316  let bestD = distance(LATTICE_LAB, near * 3, L, A, B);
317  let shown = [LATTICE_LAB[near * 3]!, LATTICE_LAB[near * 3 + 1]!, LATTICE_LAB[near * 3 + 2]!];
318  if (bestD < QUIET * QUIET) return { glyph, fg, bg, shown, quiet: true };
319
320  for (const other of around) {
321    if (other === near) continue;
322    for (const [mixer, f] of mixers(row, col)) {
323      oklab(
324        f * LATTICE_LIN[near * 3]! + (1 - f) * LATTICE_LIN[other * 3]!,
325        f * LATTICE_LIN[near * 3 + 1]! + (1 - f) * LATTICE_LIN[other * 3 + 1]!,
326        f * LATTICE_LIN[near * 3 + 2]! + (1 - f) * LATTICE_LIN[other * 3 + 2]!,
327        mixed,
328        0,
329      );
330      const d = distance(mixed, 0, L, A, B);
331      if (d < bestD) {
332        bestD = d;
333        glyph = mixer;
334        fg = word(near);
335        bg = word(other);
336        shown = [mixed[0]!, mixed[1]!, mixed[2]!];
337      }
338    }
339  }
340
341  return { glyph, fg, bg, shown, quiet: false };
342}
343
344/**
345 * Box-filter taps along one axis: output `i` covers source
346 * `[i·step, (i+1)·step)`, clipped to the picture; weights in output units, so
347 * a sample wholly inside the picture sums to 1 and one past it to 0.
348 */
349function taps(size: number, count: number, step: number) {
350  const offset = new Int32Array(count + 1);
351  const index: number[] = [];
352  const weight: number[] = [];
353  for (let i = 0; i < count; i++) {
354    offset[i] = index.length;
355    const from = i * step;
356    const to = Math.min((i + 1) * step, size);
357    for (let s = Math.floor(from); s < to; s++) {
358      const w = (Math.min(to, s + 1) - Math.max(from, s)) / step;
359      if (w > 0) {
360        index.push(s);
361        weight.push(w);
362      }
363    }
364  }
365  offset[count] = index.length;
366
367  return { offset, index: Int32Array.from(index), weight: Float32Array.from(weight) };
368}
369
370/**
371 * The samples of a `columns × rows` box with the picture placed at its top
372 * left, aspect exact for cells `aspect` times as tall as wide (a part row or
373 * column past it is transparent): OKLab of the picture over `bg` (linear
374 * light), and coverage.
375 */
376function sample(img: Pixmap, columns: number, rows: number, aspect: number, bg: readonly number[]) {
377  const ratio = (aspect * img.width) / img.height;
378  const wide = Math.min(columns, rows * ratio);
379  // Ending on a half row (at most 1/4 row of stretch): the only glyphs with
380  // ink at a cell's top are ▀ and ▔, so a picture ending at 3/8 of a row
381  // could only show its edge as a blend.
382  const tall = Math.min(rows, Math.max(0.5, Math.round((wide / ratio) * 2) / 2));
383  const gw = columns * SX;
384  const gh = rows * SY;
385  const xs = taps(img.width, gw, img.width / (wide * SX));
386  const ys = taps(img.height, gh, img.height / (tall * SY));
387  const px = img.rgba;
388
389  // Across first: every source row, premultiplied linear RGBA.
390  const across = new Float32Array(img.height * gw * 4);
391  for (let y = 0; y < img.height; y++) {
392    for (let gx = 0; gx < gw; gx++) {
393      let r = 0, g = 0, b = 0, a = 0;
394      for (let t = xs.offset[gx]!; t < xs.offset[gx + 1]!; t++) {
395        const i = (y * img.width + xs.index[t]!) * 4;
396        const w = (xs.weight[t]! * px[i + 3]!) / 255;
397        r += w * LINEAR[px[i]!]!;
398        g += w * LINEAR[px[i + 1]!]!;
399        b += w * LINEAR[px[i + 2]!]!;
400        a += w;
401      }
402      const o = (y * gw + gx) * 4;
403      across[o] = r;
404      across[o + 1] = g;
405      across[o + 2] = b;
406      across[o + 3] = a;
407    }
408  }
409
410  const lab = new Float32Array(gw * gh * 3);
411  const alpha = new Float32Array(gw * gh);
412  for (let gy = 0; gy < gh; gy++) {
413    for (let gx = 0; gx < gw; gx++) {
414      let r = 0, g = 0, b = 0, a = 0;
415      for (let t = ys.offset[gy]!; t < ys.offset[gy + 1]!; t++) {
416        const o = (ys.index[t]! * gw + gx) * 4;
417        const w = ys.weight[t]!;
418        r += w * across[o]!;
419        g += w * across[o + 1]!;
420        b += w * across[o + 2]!;
421        a += w * across[o + 3]!;
422      }
423      a = Math.min(1, a);
424      const s = gy * gw + gx;
425      alpha[s] = a;
426      oklab(r + bg[0]! * (1 - a), g + bg[1]! * (1 - a), b + bg[2]! * (1 - a), lab, s * 3);
427    }
428  }
429
430  return { gw, lab, alpha };
431}
432
433/** 1 for each opaque cell that is even inside and on no gradient (EVEN, STEEP). */
434function flatCells(lab: Float32Array, alpha: Float32Array, gw: number, columns: number, rows: number) {
435  const mean = new Float64Array(columns * rows * 3);
436  const even = new Uint8Array(columns * rows);
437  for (let row = 0; row < rows; row++) {
438    for (let col = 0; col < columns; col++) {
439      let l = 0, a = 0, b = 0, sq = 0, cover = 0;
440      for (let k = 0; k < N; k++) {
441        const s = (row * SY + ((k / SX) | 0)) * gw + col * SX + (k % SX);
442        const L = lab[s * 3]!, A = lab[s * 3 + 1]!, B = lab[s * 3 + 2]!;
443        l += L;
444        a += A;
445        b += B;
446        sq += L * L + A * A + B * B;
447        cover += alpha[s]!;
448      }
449      const c = row * columns + col;
450      mean[c * 3] = l / N;
451      mean[c * 3 + 1] = a / N;
452      mean[c * 3 + 2] = b / N;
453      const spread = sq / N - (l * l + a * a + b * b) / (N * N);
454      even[c] = cover > N * 0.999 && spread < EVEN * EVEN ? 1 : 0;
455    }
456  }
457  const flat = new Uint8Array(columns * rows);
458  for (let row = 0; row < rows; row++) {
459    for (let col = 0; col < columns; col++) {
460      const c = row * columns + col;
461      if (!even[c]) continue;
462      // Whether a neighbour differs gently (a slope); a missing one mirrors
463      // the other, so a gradient reaches the picture's edge.
464      const slope = (r: number, k: number): boolean | undefined => {
465        if (r < 0 || r >= rows || k < 0 || k >= columns) return undefined;
466        const d = distance(mean, (r * columns + k) * 3, mean[c * 3]!, mean[c * 3 + 1]!, mean[c * 3 + 2]!);
467        return d >= EVEN * EVEN && d < STEEP * STEEP;
468      };
469      const axis = (a: boolean | undefined, b: boolean | undefined) => (a ?? b ?? false) && (b ?? a ?? false);
470      // Up to 3 cells away: a gradient of one sRGB step a cell is under EVEN
471      // next door and would band.
472      let onGradient = false;
473      for (let k = 1; k <= 3 && !onGradient; k++) {
474        onGradient =
475          axis(slope(row, col - k), slope(row, col + k)) || axis(slope(row - k, col), slope(row + k, col));
476      }
477      flat[c] = onGradient ? 0 : 1;
478    }
479  }
480
481  // What each flat cell is drawn as: its nearest lattice colour.
482  const fill = new Int32Array(columns * rows).fill(-1);
483  for (let c = 0; c < columns * rows; c++) {
484    if (flat[c]) fill[c] = nearest(mean[c * 3]!, mean[c * 3 + 1]!, mean[c * 3 + 2]!);
485  }
486
487  return { flat, fill };
488}
489
490export type RenderOptions = {
491  /** Block Elements only (the default), or with the Powerline wedges. */
492  glyphs?: Glyphs;
493  /** Colours on a Raster's 4-bit lattice (the default), or exact. */
494  lattice?: boolean;
495  /** A cell's height over its width (DEFAULT_ASPECT). */
496  aspect?: number;
497  /** The terminal's background (a dark guess by default). */
498  background?: Backdrop;
499};
500
501/**
502 * Raster words for a picture in a `columns × rows` box: per cell a glyph,
503 * a foreground and a background (`[codePoint, fg, bg]`, colours 0xRRGGBB or
504 * DEFAULT), row-major.
505 */
506export function render(
507  img: Pixmap,
508  columns: number,
509  rows: number,
510  options: RenderOptions = {},
511): Uint32Array {
512  const shapes = SETS[options.glyphs ?? "blocks"];
513  const onLattice = options.lattice !== false;
514  const background = options.background ?? DARK;
515  const { lin: BG, lab: BG_LAB } = backdrop(background.color);
516  const { gw, lab, alpha } = sample(img, columns, rows, options.aspect ?? DEFAULT_ASPECT, BG);
517  const words = new Uint32Array(columns * rows * 3);
518  // Per sample: L, a, b and coverage, the last so a picture's edge is a
519  // split of its own and transparency never merges with a dark colour.
520  const cell = new Float32Array(N * 4);
521  const t = new Float64Array(4);
522  const p = new Float64Array(4);
523  // Error handed on (OKLab), this row and the next, a column of margin each side.
524  let err = new Float64Array((columns + 2) * 3);
525  let next = new Float64Array((columns + 2) * 3);
526  const { flat, fill } = onLattice
527    ? flatCells(lab, alpha, gw, columns, rows)
528    : { flat: new Uint8Array(columns * rows), fill: new Int32Array(columns * rows).fill(-1) };
529  /** A flat neighbour drawn as lattice colour `i`. */
530  const besideFill = (row: number, col: number, i: number) =>
531    [[-1, 0], [1, 0], [0, -1], [0, 1]].some(([dr, dc]) => {
532      const r = row + dr!, k = col + dc!;
533      return r >= 0 && r < rows && k >= 0 && k < columns && fill[r * columns + k] === i;
534    });
535
536  for (let row = 0; row < rows; row++) {
537    for (let col = 0; col < columns; col++) {
538      const e = (col + 1) * 3;
539      const isFlat = flat[row * columns + col] === 1;
540      t.fill(0);
541      let sq = 0;
542      for (let k = 0; k < N; k++) {
543        const s = (row * SY + ((k / SX) | 0)) * gw + col * SX + (k % SX);
544        const a = alpha[s]!;
545        for (let ch = 0; ch < 4; ch++) {
546          const v = ch < 3 ? lab[s * 3 + ch]! + (isFlat ? 0 : err[e + ch]! * a) : a * EDGE;
547          cell[k * 4 + ch] = v;
548          t[ch]! += v;
549          sq += v * v;
550        }
551      }
552      const w = (row * columns + col) * 3;
553      const opaque = t[3]! > N * EDGE * 0.999;
554
555      // The best split, against a plain cell. Scores are Σ|x|² less the
556      // error left; a plain cell leaves Σ|x − mean|².
557      let best: Shape | undefined;
558      let bestScore = (t[0]! ** 2 + t[1]! ** 2 + t[2]! ** 2 + t[3]! ** 2) / N + N * FLAT;
559      if (sq - bestScore + N * FLAT > 1e-9) {
560        for (const sh of shapes) {
561          const m = sh.mask;
562          p.fill(0);
563          for (let k = 0; k < N; k++) {
564            const v = m[k]!;
565            if (v === 0) continue;
566            p[0]! += v * cell[k * 4]!;
567            p[1]! += v * cell[k * 4 + 1]!;
568            p[2]! += v * cell[k * 4 + 2]!;
569            p[3]! += v * cell[k * 4 + 3]!;
570          }
571          const n1 = sh.n, n2 = N - sh.n;
572          // A clear inside needs the inverse glyph to show the terminal's colour.
573          if (!opaque && sh.inverse === undefined && p[3]! / n1 < CLEAR * EDGE) continue;
574          // Means c1 = P/n, c2 = Q/(N−n); the blend m·c1 + (1−m)·c2 leaves
575          // Σ|x|² − (2c1·P + 2c2·Q − a|c1|² − 2b c1·c2 − c|c2|²).
576          let score = 0;
577          for (let ch = 0; ch < 4; ch++) {
578            const pin = p[ch]!, pout = t[ch]! - pin;
579            const c1 = pin / n1, c2 = pout / n2;
580            score += 2 * c1 * pin + 2 * c2 * pout - sh.a * c1 * c1 - 2 * sh.b * c1 * c2 - sh.c * c2 * c2;
581          }
582          if (score > bestScore) {
583            bestScore = score;
584            best = sh;
585          }
586        }
587      }
588
589      // The sides: OKLab means and coverage (one side for a plain cell).
590      let n1 = N, n2 = 0;
591      p.set(t);
592      if (best !== undefined) {
593        p.fill(0);
594        const m = best.mask;
595        for (let k = 0; k < N; k++) {
596          const v = m[k]!;
597          if (v === 0) continue;
598          for (let ch = 0; ch < 4; ch++) p[ch]! += v * cell[k * 4 + ch]!;
599        }
600        n1 = best.n;
601        n2 = N - best.n;
602      }
603      const in0 = p[0]! / n1, in1 = p[1]! / n1, in2 = p[2]! / n1;
604      const out0 = n2 ? (t[0]! - p[0]!) / n2 : 0;
605      const out1 = n2 ? (t[1]! - p[1]!) / n2 : 0;
606      const out2 = n2 ? (t[2]! - p[2]!) / n2 : 0;
607      const inClear = p[3]! / n1 < CLEAR * EDGE;
608      const outClear = n2 === 0 || (t[3]! - p[3]!) / n2 < CLEAR * EDGE;
609      const mean0 = t[0]! / N, mean1 = t[1]! / N, mean2 = t[2]! / N;
610      // Judged on the picture's own colour, before the error handed in: a
611      // background beside an edge stays the background, the error dropped.
612      const [e0, e1, e2] = isFlat ? [0, 0, 0] : [err[e]!, err[e + 1]!, err[e + 2]!];
613      const nearBackground = (L: number, A: number, B: number) =>
614        background.exact &&
615        distance(BG_LAB, 0, L - e0, A - e1, B - e2) < NEAR_BACKGROUND * NEAR_BACKGROUND;
616
617      // What is drawn, and the error a dithered cell leaves (handed on).
618      let glyph: number, fg: number, bg: number;
619      let r0 = 0, r1 = 0, r2 = 0;
620
621      const faint =
622        best !== undefined &&
623        (in0 - out0) ** 2 + (in1 - out1) ** 2 + (in2 - out2) ** 2 < FAINT * FAINT;
624      if (inClear && outClear) {
625        glyph = 0x20;
626        fg = DEFAULT;
627        bg = DEFAULT;
628      } else if (best === undefined || (opaque && onLattice && faint)) {
629        // One colour: the cell's mean.
630        if (nearBackground(mean0, mean1, mean2)) {
631          glyph = 0x20;
632          fg = DEFAULT;
633          bg = DEFAULT;
634        } else if (isFlat) {
635          glyph = 0x20;
636          fg = DEFAULT;
637          bg = word(nearest(mean0, mean1, mean2));
638        } else if (
639          onLattice &&
640          besideFill(row, col, nearest(mean0, mean1, mean2)) &&
641          distance(LATTICE_LAB, nearest(mean0, mean1, mean2) * 3, mean0, mean1, mean2) < SEAM * SEAM
642        ) {
643          // A gradient leaving a flat fill: carry on the fill's plain colour
644          // until the gradient has moved off it; dithered at once, the first
645          // cells off the fill show as specks.
646          glyph = 0x20;
647          fg = DEFAULT;
648          bg = word(nearest(mean0, mean1, mean2));
649        } else if (onLattice) {
650          const drawn = mix(mean0, mean1, mean2, row, col);
651          ({ glyph, fg, bg } = drawn);
652          if (!drawn.quiet) {
653            r0 = mean0 - drawn.shown[0]!;
654            r1 = mean1 - drawn.shown[1]!;
655            r2 = mean2 - drawn.shown[2]!;
656          }
657        } else {
658          glyph = 0x20;
659          fg = DEFAULT;
660          bg = packLab(mean0, mean1, mean2);
661        }
662      } else {
663        // Two sides. Each: the terminal's colour (clear, or next to it), or
664        // the nearest lattice colour (or the exact one). The rounding stays
665        // here: handed on along an edge, it beads the edge's neighbours.
666        const side = (clear: boolean, L: number, A: number, B: number) => {
667          if (clear || nearBackground(L, A, B)) return DEFAULT;
668          return onLattice ? word(nearest(L, A, B)) : packLab(L, A, B);
669        };
670        const inside = side(inClear, in0, in1, in2);
671        const outside = side(outClear, out0, out1, out2);
672        const sh = best!;
673        if (inside === DEFAULT && sh.inverse !== undefined) {
674          glyph = sh.inverse;
675          fg = outside;
676          bg = DEFAULT;
677        } else {
678          glyph = sh.glyph;
679          // The terminal's colour as ink: only an explicit colour can say it.
680          fg =
681            inside === DEFAULT
682              ? onLattice
683                ? word(nearest(BG_LAB[0]!, BG_LAB[1]!, BG_LAB[2]!))
684                : background.color
685              : inside;
686          bg = outside;
687        }
688      }
689
690      words[w] = glyph;
691      words[w + 1] = fg;
692      words[w + 2] = bg;
693
694      // Floyd–Steinberg: 7/16 right, 3/16 below left, 5/16 below, 1/16 below right.
695      if (onLattice && !isFlat && t[3]! > N * EDGE * 0.5) {
696        const rs = [r0, r1, r2].map((v) => Math.max(-0.05, Math.min(0.05, v)));
697        for (let ch = 0; ch < 3; ch++) {
698          const v = rs[ch]!;
699          err[e + 3 + ch]! += (v * 7) / 16;
700          next[e - 3 + ch]! += (v * 3) / 16;
701          next[e + ch]! += (v * 5) / 16;
702          next[e + 3 + ch]! += v / 16;
703        }
704      }
705    }
706    [err, next] = [next, err];
707    next.fill(0);
708  }
709
710  return words;
711}
712
713/**
714 * The words cut into stacked Rasters' `cells`, each at most PAIRS cells (so
715 * at most PAIRS pairs: nothing is snapped), strips as even as that allows.
716 */
717export function strips(
718  words: Uint32Array,
719  columns: number,
720  rows: number,
721): { rows: number; cells: string }[] {
722  const count = Math.ceil((columns * rows) / PAIRS);
723  const each = Math.max(1, Math.min(Math.ceil(rows / count), Math.floor(PAIRS / columns)));
724  const out: { rows: number; cells: string }[] = [];
725  for (let top = 0; top < rows; top += each) {
726    const n = Math.min(each, rows - top);
727    const part = words.subarray(top * columns * 3, (top + n) * columns * 3);
728    out.push({
729      rows: n,
730      cells: new Uint8Array(part.buffer, part.byteOffset, part.byteLength).toBase64(),
731    });
732  }
733
734  return out;
735}
736

1// GIF decoding: the first frame, drawn on the logical screen with what is
2// not covered transparent (as browsers show it), interlaced or not.
3
4import type { Pixmap } from "./pixels";
5
6export function isGif(bytes: Uint8Array): boolean {
7  const head = String.fromCharCode(...bytes.subarray(0, 6));
8  return head === "GIF87a" || head === "GIF89a";
9}
10
11const u16 = (b: Uint8Array, i: number) => b[i]! | (b[i + 1]! << 8);
12
13/** Decodes a GIF's first frame; `maxPixels` refuses anything bigger. */
14export function decodeGif(bytes: Uint8Array, maxPixels: number): Pixmap {
15  if (!isGif(bytes)) throw new Error("not a GIF");
16  const width = u16(bytes, 6);
17  const height = u16(bytes, 8);
18  if (!(width > 0 && height > 0)) throw new Error("GIF has no size");
19  if (width * height > maxPixels) throw new Error(`${width}×${height} is too large to preview`);
20
21  const flags = bytes[10]!;
22  let pos = 13;
23  let globalTable: Uint8Array | undefined;
24  if (flags & 0x80) {
25    const size = 3 << ((flags & 7) + 1);
26    globalTable = bytes.subarray(pos, pos + size);
27    pos += size;
28  }
29
30  let transparent = -1;
31  while (pos < bytes.length) {
32    const block = bytes[pos++]!;
33    if (block === 0x21) {
34      const label = bytes[pos++]!;
35      if (label === 0xf9 && bytes[pos] === 4) {
36        // Graphic Control Extension: its transparency flag and index.
37        if (bytes[pos + 1]! & 1) transparent = bytes[pos + 4]!;
38      }
39      pos = skipBlocks(bytes, pos);
40    } else if (block === 0x2c) {
41      return frame(bytes, pos, width, height, globalTable, transparent);
42    } else if (block === 0x3b) {
43      break;
44    } else {
45      throw new Error("unknown GIF block");
46    }
47  }
48  throw new Error("GIF has no frame");
49}
50
51function skipBlocks(bytes: Uint8Array, pos: number): number {
52  while (pos < bytes.length) {
53    const size = bytes[pos++]!;
54    if (size === 0) return pos;
55    pos += size;
56  }
57
58  return pos;
59}
60
61function frame(
62  bytes: Uint8Array,
63  pos: number,
64  width: number,
65  height: number,
66  globalTable: Uint8Array | undefined,
67  transparent: number,
68): Pixmap {
69  const left = u16(bytes, pos);
70  const top = u16(bytes, pos + 2);
71  const w = u16(bytes, pos + 4);
72  const h = u16(bytes, pos + 6);
73  const flags = bytes[pos + 8]!;
74  pos += 9;
75  let colors = globalTable;
76  if (flags & 0x80) {
77    const size = 3 << ((flags & 7) + 1);
78    colors = bytes.subarray(pos, pos + size);
79    pos += size;
80  }
81  if (colors === undefined) throw new Error("GIF has no colour table");
82
83  const minCodeSize = bytes[pos++]!;
84  if (minCodeSize < 2 || minCodeSize > 11) throw new Error("bad GIF code size");
85  // The image data's sub-blocks, joined.
86  const parts: Uint8Array[] = [];
87  let length = 0;
88  while (pos < bytes.length) {
89    const size = bytes[pos++]!;
90    if (size === 0) break;
91    const part = bytes.subarray(pos, pos + size);
92    parts.push(part);
93    length += part.length;
94    pos += size;
95  }
96  const data = new Uint8Array(length);
97  for (let i = 0, o = 0; i < parts.length; o += parts[i]!.length, i++) data.set(parts[i]!, o);
98
99  const indices = lzw(data, minCodeSize, w * h);
100  const rows = flags & 0x40 ? interlacedRows(h) : Array.from({ length: h }, (_, y) => y);
101  const rgba = new Uint8Array(width * height * 4);
102  const entries = Math.floor(colors.length / 3);
103  for (let r = 0; r < h; r++) {
104    const y = top + rows[r]!;
105    if (y >= height) continue;
106    for (let x = 0; x < w; x++) {
107      const ox = left + x;
108      if (ox >= width) continue;
109      const i = indices[r * w + x]!;
110      if (i === transparent || i >= entries) continue;
111      const o = (y * width + ox) * 4;
112      rgba[o] = colors[i * 3]!;
113      rgba[o + 1] = colors[i * 3 + 1]!;
114      rgba[o + 2] = colors[i * 3 + 2]!;
115      rgba[o + 3] = 255;
116    }
117  }
118
119  return { width, height, rgba };
120}
121
122/** The image row each stored row is, for an interlaced frame `h` rows tall. */
123function interlacedRows(h: number): number[] {
124  const rows: number[] = [];
125  for (const [start, step] of [[0, 8], [4, 8], [2, 4], [1, 2]] as const) {
126    for (let y = start; y < h; y += step) rows.push(y);
127  }
128
129  return rows;
130}
131
132/** LZW codes to `count` colour indices; a short stream leaves zeros. */
133function lzw(data: Uint8Array, minCodeSize: number, count: number): Uint8Array {
134  const out = new Uint8Array(count);
135  const clear = 1 << minCodeSize;
136  const eoi = clear + 1;
137  const prefix = new Int16Array(4096);
138  const suffix = new Uint8Array(4096);
139  const first = new Uint8Array(4096);
140  const length = new Uint16Array(4096);
141  for (let i = 0; i < clear; i++) {
142    suffix[i] = i;
143    first[i] = i;
144    length[i] = 1;
145  }
146
147  let size = minCodeSize + 1;
148  let next = eoi + 1;
149  let prev = -1;
150  let o = 0;
151  let buf = 0;
152  let cnt = 0;
153  let pos = 0;
154  while (o < count) {
155    while (cnt < size) {
156      if (pos >= data.length) return out;
157      buf |= data[pos++]! << cnt;
158      cnt += 8;
159    }
160    const code = buf & ((1 << size) - 1);
161    buf >>>= size;
162    cnt -= size;
163
164    if (code === clear) {
165      size = minCodeSize + 1;
166      next = eoi + 1;
167      prev = -1;
168      continue;
169    }
170    if (code === eoi) break;
171
172    if (prev >= 0) {
173      // The new entry: the previous string plus the first index of this one
174      // (of the previous one, for the code being defined right now).
175      if (code > next) throw new Error("bad GIF code");
176      if (next < 4096) {
177        prefix[next] = prev;
178        suffix[next] = code === next ? first[prev]! : first[code]!;
179        first[next] = first[prev]!;
180        length[next] = length[prev]! + 1;
181        next++;
182        if (next === 1 << size && size < 12) size++;
183      }
184    } else if (code >= next) {
185      throw new Error("bad GIF code");
186    }
187
188    // Write the string of `code`, back to front.
189    const n = length[code]!;
190    let at = o + n - 1;
191    for (let c = code; c >= 0 && at >= o; c = prefix[c]!, at--) {
192      if (at < count) out[at] = suffix[c]!;
193      if (length[c] === 1) break;
194    }
195    o += n;
196    prev = code;
197  }
198
199  return out;
200}
201

1// JPEG decoding: baseline, extended and progressive Huffman-coded JPEG at
2// 8 bits, any sampling factors, restart intervals; greyscale, YCbCr, RGB and
3// Adobe CMYK/YCCK. Arithmetic coding, 12-bit, lossless and hierarchical JPEG
4// are refused (the caller falls back to ffmpeg). Chroma is upsampled by
5// replication, as libjpeg does with fancy upsampling off. EXIF orientation is
6// not applied (neither did the ffmpeg decode this replaces).
7
8import type { Pixmap } from "./pixels";
9
10/** Zigzag index to natural (row-major) index, padded for a corrupt run past 63. */
11const ZIGZAG = Int32Array.from([
12  0, 1, 8, 16, 9, 2, 3, 10, 17, 24, 32, 25, 18, 11, 4, 5, 12, 19, 26, 33, 40, 48, 41, 34, 27, 20,
13  13, 6, 7, 14, 21, 28, 35, 42, 49, 56, 57, 50, 43, 36, 29, 22, 15, 23, 30, 37, 44, 51, 58, 59, 52,
14  45, 38, 31, 39, 46, 53, 60, 61, 54, 47, 55, 62, 63, ...Array.from({ length: 16 }, () => 63),
15]);
16
17/** The 1-D IDCT basis, COS[x * 8 + u] = C(u)/2 · cos((2x+1)uπ/16). */
18const COS = Float32Array.from({ length: 64 }, (_, i) => {
19  const x = i >> 3, u = i & 7;
20  return ((u === 0 ? Math.SQRT1_2 : 1) * Math.cos(((2 * x + 1) * u * Math.PI) / 16)) / 2;
21});
22
23type Huffman = {
24  /** By the next 8 bits: `(length << 8) | value` for codes up to 8 bits, else 0. */
25  lookup: Uint16Array;
26  maxcode: Int32Array;
27  valptr: Int32Array;
28  mincode: Int32Array;
29  values: Uint8Array;
30};
31
32type Component = {
33  id: number;
34  h: number;
35  v: number;
36  tq: number;
37  /** Blocks across and down that hold picture (a non-interleaved scan's MCUs). */
38  blocksPerLine: number;
39  blocksPerColumn: number;
40  /** Blocks across and down as stored: whole MCUs. */
41  stride: number;
42  rowsStored: number;
43  coefs: Int16Array;
44  dc?: Huffman;
45  ac?: Huffman;
46  pred: number;
47};
48
49type Frame = {
50  progressive: boolean;
51  width: number;
52  height: number;
53  components: Component[];
54  maxH: number;
55  maxV: number;
56  mcusPerLine: number;
57  mcusPerColumn: number;
58};
59
60export function isJpeg(bytes: Uint8Array): boolean {
61  return bytes[0] === 0xff && bytes[1] === 0xd8 && bytes[2] === 0xff;
62}
63
64const u16 = (b: Uint8Array, i: number) => (b[i]! << 8) | b[i + 1]!;
65
66function huffman(counts: Uint8Array, values: Uint8Array): Huffman {
67  const lookup = new Uint16Array(256);
68  const maxcode = new Int32Array(18).fill(-1);
69  const valptr = new Int32Array(17);
70  const mincode = new Int32Array(17);
71  let code = 0;
72  let k = 0;
73  for (let len = 1; len <= 16; len++) {
74    const n = counts[len - 1]!;
75    valptr[len] = k;
76    mincode[len] = code;
77    for (let i = 0; i < n; i++, k++, code++) {
78      if (code >= 1 << len) throw new Error("bad JPEG Huffman table");
79      if (len <= 8) {
80        const shift = 8 - len;
81        for (let j = 0; j < 1 << shift; j++) lookup[(code << shift) | j] = (len << 8) | values[k]!;
82      }
83    }
84    if (n) maxcode[len] = code - 1;
85    code <<= 1;
86  }
87
88  return { lookup, maxcode, valptr, mincode, values };
89}
90
91/** Entropy-coded bits, most significant first, byte stuffing undone. */
92class Bits {
93  readonly data: Uint8Array;
94  pos: number;
95  buf = 0;
96  cnt = 0;
97  /** A marker was reached: zeros are read from there on. */
98  atMarker = false;
99
100  constructor(data: Uint8Array, pos: number) {
101    this.data = data;
102    this.pos = pos;
103  }
104
105  fill() {
106    const data = this.data;
107    while (this.cnt <= 24) {
108      let b = 0;
109      if (!this.atMarker && this.pos < data.length) {
110        b = data[this.pos]!;
111        if (b === 0xff) {
112          if (data[this.pos + 1] === 0) {
113            this.pos += 2;
114          } else {
115            this.atMarker = true;
116            b = 0;
117          }
118        } else {
119          this.pos++;
120        }
121      }
122      this.buf = (this.buf << 8) | b;
123      this.cnt += 8;
124    }
125  }
126
127  bits(n: number): number {
128    if (this.cnt < n) this.fill();
129    this.cnt -= n;
130    return (this.buf >>> this.cnt) & ((1 << n) - 1);
131  }
132
133  /** `bits(s)` read as a signed coefficient (the JPEG EXTEND procedure). */
134  extend(s: number): number {
135    if (s === 0) return 0;
136    if (s > 16) throw new Error("bad JPEG coefficient size");
137    const v = this.bits(s);
138    return v < 1 << (s - 1) ? v - (1 << s) + 1 : v;
139  }
140
141  decode(h: Huffman): number {
142    if (this.cnt < 16) this.fill();
143    const e = h.lookup[(this.buf >>> (this.cnt - 8)) & 255]!;
144    if (e) {
145      this.cnt -= e >> 8;
146      return e & 255;
147    }
148    for (let len = 9; len <= 16; len++) {
149      const code = (this.buf >>> (this.cnt - len)) & ((1 << len) - 1);
150      if (code <= h.maxcode[len]!) {
151        this.cnt -= len;
152        return h.values[h.valptr[len]! + code - h.mincode[len]!]!;
153      }
154    }
155    throw new Error("bad JPEG Huffman code");
156  }
157
158  /** Where the next marker starts, from the current position on. */
159  nextMarker(): number {
160    const data = this.data;
161    let p = this.pos;
162    while (p + 1 < data.length) {
163      const n = data[p + 1]!;
164      if (data[p] === 0xff && n !== 0 && n !== 0xff && !(n >= 0xd0 && n <= 0xd7)) break;
165      p++;
166    }
167
168    return p;
169  }
170
171  /** Drops the bits left before a restart marker, and the marker. */
172  restart() {
173    const data = this.data;
174    let p = this.pos;
175    while (p + 1 < data.length && !(data[p] === 0xff && data[p + 1] !== 0 && data[p + 1] !== 0xff)) p++;
176    if (data[p + 1]! >= 0xd0 && data[p + 1]! <= 0xd7) p += 2;
177    this.pos = p;
178    this.buf = 0;
179    this.cnt = 0;
180    this.atMarker = false;
181  }
182}
183
184/** Decodes a JPEG; `maxPixels` refuses anything bigger before decoding. */
185export function decodeJpeg(bytes: Uint8Array, maxPixels: number): Pixmap {
186  if (!isJpeg(bytes)) throw new Error("not a JPEG");
187
188  const quant: (Int32Array | undefined)[] = [];
189  const dcTables: (Huffman | undefined)[] = [];
190  const acTables: (Huffman | undefined)[] = [];
191  let frame: Frame | undefined;
192  let restartInterval = 0;
193  let adobe: number | undefined;
194  let decodedAny = false;
195
196  let pos = 2;
197  for (;;) {
198    while (pos < bytes.length && bytes[pos] !== 0xff) pos++;
199    while (pos < bytes.length && bytes[pos] === 0xff) pos++;
200    if (pos >= bytes.length) break;
201    const marker = bytes[pos++]!;
202    if (marker === 0xd9) break;
203    if (marker === 0xd8 || marker === 0x01 || (marker >= 0xd0 && marker <= 0xd7)) continue;
204
205    const length = u16(bytes, pos);
206    const seg = bytes.subarray(pos + 2, pos + length);
207    if (seg.length !== length - 2) break;
208    pos += length;
209
210    if (marker === 0xc0 || marker === 0xc1 || marker === 0xc2) {
211      frame = readFrame(seg, marker === 0xc2, maxPixels);
212    } else if (marker === 0xc4) {
213      for (let p = 0; p < seg.length; ) {
214        const tc = seg[p]! >> 4, th = seg[p]! & 15;
215        const counts = seg.subarray(p + 1, p + 17);
216        const total = counts.reduce((a, b) => a + b, 0);
217        const table = huffman(counts, seg.subarray(p + 17, p + 17 + total));
218        (tc === 0 ? dcTables : acTables)[th] = table;
219        p += 17 + total;
220      }
221    } else if (marker === 0xdb) {
222      for (let p = 0; p < seg.length; ) {
223        const wide = seg[p]! >> 4, tq = seg[p]! & 15;
224        const table = new Int32Array(64);
225        for (let i = 0; i < 64; i++) {
226          table[ZIGZAG[i]!] = wide ? u16(seg, p + 1 + i * 2) : seg[p + 1 + i]!;
227        }
228        quant[tq] = table;
229        p += 1 + (wide ? 128 : 64);
230      }
231    } else if (marker === 0xdd) {
232      restartInterval = u16(seg, 0);
233    } else if (marker === 0xee) {
234      if (String.fromCharCode(...seg.subarray(0, 5)) === "Adobe" && seg.length >= 12) adobe = seg[11]!;
235    } else if (marker === 0xda) {
236      if (frame === undefined) throw new Error("JPEG scan before its frame");
237      const n = seg[0]!;
238      const scan: Component[] = [];
239      for (let i = 0; i < n; i++) {
240        const id = seg[1 + i * 2]!, tables = seg[2 + i * 2]!;
241        const c = frame.components.find((c) => c.id === id);
242        if (c === undefined) throw new Error("JPEG scan names no component");
243        c.dc = dcTables[tables >> 4];
244        c.ac = acTables[tables & 15];
245        scan.push(c);
246      }
247      const at = 1 + n * 2;
248      const ss = seg[at]!, se = seg[at + 1]!, ah = seg[at + 2]! >> 4, al = seg[at + 2]! & 15;
249      const bits = new Bits(bytes, pos);
250      try {
251        decodeScan(bits, frame, scan, restartInterval, ss, se, ah, al);
252        decodedAny = true;
253      } catch (error) {
254        // A damaged or cut-off file: draw what came before, as viewers do.
255        if (!decodedAny && !bits.atMarker && bits.pos < bytes.length) throw error;
256        decodedAny = true;
257        break;
258      }
259      pos = bits.nextMarker();
260    } else if (
261      (marker >= 0xc3 && marker <= 0xc7) ||
262      (marker >= 0xc9 && marker <= 0xcb) ||
263      (marker >= 0xcd && marker <= 0xcf)
264    ) {
265      throw new Error(marker >= 0xc9 ? "arithmetic-coded JPEG" : "lossless or hierarchical JPEG");
266    }
267  }
268
269  if (frame === undefined || !decodedAny) throw new Error("JPEG has no image data");
270
271  return output(frame, quant, adobe);
272}
273
274function readFrame(seg: Uint8Array, progressive: boolean, maxPixels: number): Frame {
275  if (seg[0] !== 8) throw new Error(`${seg[0]}-bit JPEG`);
276  const height = u16(seg, 1);
277  const width = u16(seg, 3);
278  if (!(width > 0 && height > 0)) throw new Error("JPEG has no size");
279  if (width * height > maxPixels) throw new Error(`${width}×${height} is too large to preview`);
280  const n = seg[5]!;
281  if (n !== 1 && n !== 3 && n !== 4) throw new Error(`JPEG with ${n} components`);
282
283  const parts = Array.from({ length: n }, (_, i) => ({
284    id: seg[6 + i * 3]!,
285    h: seg[7 + i * 3]! >> 4,
286    v: seg[7 + i * 3]! & 15,
287    tq: seg[8 + i * 3]!,
288  }));
289  if (parts.some((p) => p.h < 1 || p.h > 4 || p.v < 1 || p.v > 4)) throw new Error("bad JPEG sampling");
290  const maxH = Math.max(...parts.map((p) => p.h));
291  const maxV = Math.max(...parts.map((p) => p.v));
292  const mcusPerLine = Math.ceil(width / (8 * maxH));
293  const mcusPerColumn = Math.ceil(height / (8 * maxV));
294  const components = parts.map((p): Component => {
295    const stride = mcusPerLine * p.h;
296    const rowsStored = mcusPerColumn * p.v;
297    return {
298      ...p,
299      blocksPerLine: Math.ceil(Math.ceil((width * p.h) / maxH) / 8),
300      blocksPerColumn: Math.ceil(Math.ceil((height * p.v) / maxV) / 8),
301      stride,
302      rowsStored,
303      coefs: new Int16Array(stride * rowsStored * 64),
304      pred: 0,
305    };
306  });
307
308  return { progressive, width, height, components, maxH, maxV, mcusPerLine, mcusPerColumn };
309}
310
311function decodeScan(
312  bits: Bits,
313  frame: Frame,
314  scan: Component[],
315  restartInterval: number,
316  ss: number,
317  se: number,
318  ah: number,
319  al: number,
320) {
321  let eobrun = 0;
322  const table = (h: Huffman | undefined) => {
323    if (h === undefined) throw new Error("JPEG Huffman table missing");
324    return h;
325  };
326
327  const baseline = (c: Component, at: number) => {
328    const b = c.coefs;
329    const t = bits.decode(table(c.dc));
330    c.pred += bits.extend(t);
331    b[at] = c.pred;
332    const ac = table(c.ac);
333    for (let k = 1; k < 64; ) {
334      const rs = bits.decode(ac);
335      const s = rs & 15, r = rs >> 4;
336      if (s === 0) {
337        if (r < 15) break;
338        k += 16;
339        continue;
340      }
341      k += r;
342      if (k > 63) break;
343      b[at + ZIGZAG[k]!] = bits.extend(s);
344      k++;
345    }
346  };
347  const dcFirst = (c: Component, at: number) => {
348    const t = bits.decode(table(c.dc));
349    c.pred += bits.extend(t);
350    c.coefs[at] = c.pred * (1 << al);
351  };
352  const dcRefine = (c: Component, at: number) => {
353    if (bits.bits(1)) c.coefs[at]! |= 1 << al;
354  };
355  const acFirst = (c: Component, at: number) => {
356    if (eobrun > 0) {
357      eobrun--;
358      return;
359    }
360    const b = c.coefs;
361    const ac = table(c.ac);
362    for (let k = ss; k <= se; ) {
363      const rs = bits.decode(ac);
364      const s = rs & 15, r = rs >> 4;
365      if (s === 0) {
366        if (r < 15) {
367          eobrun = (1 << r) - 1 + (r ? bits.bits(r) : 0);
368          break;
369        }
370        k += 16;
371        continue;
372      }
373      k += r;
374      if (k > 63) break;
375      b[at + ZIGZAG[k]!] = bits.extend(s) * (1 << al);
376      k++;
377    }
378  };
379  // Successive approximation of AC coefficients: libjpeg's decode_mcu_AC_refine.
380  const acRefine = (c: Component, at: number) => {
381    const b = c.coefs;
382    const p1 = 1 << al;
383    const m1 = -1 << al;
384    let k = ss;
385    if (eobrun <= 0) {
386      const ac = table(c.ac);
387      for (; k <= se; k++) {
388        const rs = bits.decode(ac);
389        let r = rs >> 4;
390        let s = rs & 15;
391        if (s) {
392          s = bits.bits(1) ? p1 : m1;
393        } else if (r !== 15) {
394          eobrun = (1 << r) + (r ? bits.bits(r) : 0);
395          break;
396        }
397        do {
398          const z = at + ZIGZAG[k]!;
399          if (b[z] !== 0) {
400            if (bits.bits(1) && (b[z]! & p1) === 0) b[z]! += b[z]! >= 0 ? p1 : m1;
401          } else if (--r < 0) {
402            break;
403          }
404          k++;
405        } while (k <= se);
406        if (s && k <= 63) b[at + ZIGZAG[k]!] = s;
407      }
408    }
409    if (eobrun > 0) {
410      for (; k <= se; k++) {
411        const z = at + ZIGZAG[k]!;
412        if (b[z] !== 0 && bits.bits(1) && (b[z]! & p1) === 0) b[z]! += b[z]! >= 0 ? p1 : m1;
413      }
414      eobrun--;
415    }
416  };
417
418  const block = !frame.progressive
419    ? baseline
420    : ss === 0
421      ? ah === 0
422        ? dcFirst
423        : dcRefine
424      : ah === 0
425        ? acFirst
426        : acRefine;
427  if (frame.progressive && ss === 0 && se !== 0) throw new Error("bad progressive JPEG scan");
428
429  for (const c of scan) c.pred = 0;
430  const single = scan.length === 1 ? scan[0]! : undefined;
431  const total = single
432    ? single.blocksPerLine * single.blocksPerColumn
433    : frame.mcusPerLine * frame.mcusPerColumn;
434
435  for (let n = 0; n < total; ) {
436    const stop = restartInterval > 0 ? Math.min(total, n + restartInterval) : total;
437    for (; n < stop; n++) {
438      if (single) {
439        const row = (n / single.blocksPerLine) | 0;
440        const col = n % single.blocksPerLine;
441        block(single, (row * single.stride + col) * 64);
442      } else {
443        const mr = (n / frame.mcusPerLine) | 0;
444        const mc = n % frame.mcusPerLine;
445        for (const c of scan) {
446          for (let v = 0; v < c.v; v++) {
447            for (let h = 0; h < c.h; h++) {
448              block(c, ((mr * c.v + v) * c.stride + mc * c.h + h) * 64);
449            }
450          }
451        }
452      }
453    }
454    if (n < total) {
455      bits.restart();
456      eobrun = 0;
457      for (const c of scan) c.pred = 0;
458    }
459  }
460}
461
462/** Dequantizes and inverse-transforms one component into 8-bit samples. */
463function plane(c: Component, q: Int32Array): Uint8Array {
464  const width = c.stride * 8;
465  const out = new Uint8Array(width * c.rowsStored * 8);
466  const f = new Float32Array(64);
467  const t = new Float32Array(64);
468  for (let by = 0; by < c.rowsStored; by++) {
469    for (let bx = 0; bx < c.stride; bx++) {
470      const at = (by * c.stride + bx) * 64;
471      const base = by * 8 * width + bx * 8;
472      let flat = true;
473      for (let i = 1; i < 64; i++) {
474        if (c.coefs[at + i] !== 0) {
475          flat = false;
476          break;
477        }
478      }
479      if (flat) {
480        const v = clamp((c.coefs[at]! * q[0]!) / 8 + 128);
481        for (let y = 0; y < 8; y++) out.fill(v, base + y * width, base + y * width + 8);
482        continue;
483      }
484      for (let i = 0; i < 64; i++) f[i] = c.coefs[at + i]! * q[i]!;
485      // Rows: t[v][x] = Σu COS[x][u] · F[v][u].
486      for (let v = 0; v < 8; v++) {
487        const r = v * 8;
488        for (let x = 0; x < 8; x++) {
489          const k = x * 8;
490          t[r + x] =
491            COS[k]! * f[r]! + COS[k + 1]! * f[r + 1]! + COS[k + 2]! * f[r + 2]! + COS[k + 3]! * f[r + 3]! +
492            COS[k + 4]! * f[r + 4]! + COS[k + 5]! * f[r + 5]! + COS[k + 6]! * f[r + 6]! + COS[k + 7]! * f[r + 7]!;
493        }
494      }
495      // Columns: out[y][x] = Σv COS[y][v] · t[v][x].
496      for (let y = 0; y < 8; y++) {
497        const k = y * 8;
498        const o = base + y * width;
499        for (let x = 0; x < 8; x++) {
500          out[o + x] = clamp(
501            COS[k]! * t[x]! + COS[k + 1]! * t[8 + x]! + COS[k + 2]! * t[16 + x]! + COS[k + 3]! * t[24 + x]! +
502              COS[k + 4]! * t[32 + x]! + COS[k + 5]! * t[40 + x]! + COS[k + 6]! * t[48 + x]! +
503              COS[k + 7]! * t[56 + x]! + 128,
504          );
505        }
506      }
507    }
508  }
509
510  return out;
511}
512
513const clamp = (v: number) => (v <= 0 ? 0 : v >= 255 ? 255 : Math.round(v));
514
515function output(frame: Frame, quant: (Int32Array | undefined)[], adobe: number | undefined): Pixmap {
516  const { width, height, components, maxH, maxV } = frame;
517  const planes = components.map((c) => {
518    const q = quant[c.tq];
519    if (q === undefined) throw new Error("JPEG quantization table missing");
520    const stride = c.stride * 8;
521    return {
522      data: plane(c, q),
523      stride,
524      xs: Int32Array.from({ length: width }, (_, x) => Math.min(stride - 1, ((x * c.h) / maxH) | 0)),
525      ys: Int32Array.from({ length: height }, (_, y) => ((y * c.v) / maxV) | 0),
526    };
527  });
528
529  const ids = components.map((c) => c.id);
530  const n = components.length;
531  // Three components are RGB when an Adobe marker says so (transform 0) or,
532  // without one, when they are named R, G, B; YCbCr otherwise. Four are
533  // Adobe's inverted CMYK, as YCCK under transform 2.
534  const rgb = n === 3 && (adobe === 0 || (adobe === undefined && ids.join() === "82,71,66"));
535  const ycc = (n === 3 && !rgb) || (n === 4 && adobe === 2);
536  const inverted = n === 4 && adobe !== undefined;
537
538  const rgba = new Uint8Array(width * height * 4);
539  const [p0, p1, p2, p3] = planes;
540  for (let y = 0; y < height; y++) {
541    const r0 = p0!.ys[y]! * p0!.stride;
542    const r1 = p1 ? p1.ys[y]! * p1.stride : 0;
543    const r2 = p2 ? p2.ys[y]! * p2.stride : 0;
544    const r3 = p3 ? p3.ys[y]! * p3.stride : 0;
545    for (let x = 0; x < width; x++) {
546      const o = (y * width + x) * 4;
547      const a = p0!.data[r0 + p0!.xs[x]!]!;
548      if (n === 1) {
549        rgba[o] = rgba[o + 1] = rgba[o + 2] = a;
550        rgba[o + 3] = 255;
551        continue;
552      }
553      const b = p1!.data[r1 + p1!.xs[x]!]!;
554      const c = p2!.data[r2 + p2!.xs[x]!]!;
555      let r = a, g = b, bl = c;
556      if (ycc) {
557        r = clamp(a + 1.402 * (c - 128));
558        g = clamp(a - 0.344136 * (b - 128) - 0.714136 * (c - 128));
559        bl = clamp(a + 1.772 * (b - 128));
560      }
561      if (n === 4) {
562        const k = p3!.data[r3 + p3!.xs[x]!]!;
563        // Ink to light: inverted values multiply straight; YCCK's colour
564        // channels come out as ink, so they are flipped first.
565        const [cc, mm, yy] = ycc ? [255 - r, 255 - g, 255 - bl] : [r, g, bl];
566        if (inverted) {
567          r = Math.round((cc * k) / 255);
568          g = Math.round((mm * k) / 255);
569          bl = Math.round((yy * k) / 255);
570        } else {
571          r = Math.round(((255 - cc) * (255 - k)) / 255);
572          g = Math.round(((255 - mm) * (255 - k)) / 255);
573          bl = Math.round(((255 - yy) * (255 - k)) / 255);
574        }
575      }
576      rgba[o] = r;
577      rgba[o + 1] = g;
578      rgba[o + 2] = bl;
579      rgba[o + 3] = 255;
580    }
581  }
582
583  return { width, height, rgba };
584}
585

1// PNG decoding: every colour type and bit depth, tRNS, all five filters and
2// Adam7 interlacing, to 8-bit RGBA. Gamma and colour profiles are ignored (the
3// picture is drawn as sRGB). CRCs are not checked.
4
5import { inflate } from "./inflate";
6import type { Pixmap } from "./pixels";
7
8const SIGNATURE = [137, 80, 78, 71, 13, 10, 26, 10];
9
10type Pass = readonly [x0: number, y0: number, dx: number, dy: number];
11
12/** Adam7: x start, y start, x step, y step of each pass. */
13const ADAM7: readonly Pass[] = [
14  [0, 0, 8, 8],
15  [4, 0, 8, 8],
16  [0, 4, 4, 8],
17  [2, 0, 4, 4],
18  [0, 2, 2, 4],
19  [1, 0, 2, 2],
20  [0, 1, 1, 2],
21];
22const WHOLE: readonly Pass[] = [[0, 0, 1, 1]];
23
24const CHANNELS: Record<number, number> = { 0: 1, 2: 3, 3: 1, 4: 2, 6: 4 };
25const DEPTHS: Record<number, number[]> = {
26  0: [1, 2, 4, 8, 16],
27  2: [8, 16],
28  3: [1, 2, 4, 8],
29  4: [8, 16],
30  6: [8, 16],
31};
32
33export function isPng(bytes: Uint8Array): boolean {
34  return SIGNATURE.every((b, i) => bytes[i] === b);
35}
36
37const u32 = (b: Uint8Array, i: number) =>
38  ((b[i]! << 24) | (b[i + 1]! << 16) | (b[i + 2]! << 8) | b[i + 3]!) >>> 0;
39
40/** Decodes a PNG; `maxPixels` refuses anything bigger before inflating. */
41export function decodePng(bytes: Uint8Array, maxPixels: number): Pixmap {
42  if (!isPng(bytes)) throw new Error("not a PNG");
43
44  let width = 0, height = 0, depth = 0, colorType = 0, interlace = 0;
45  let palette: Uint8Array | undefined;
46  let trns: Uint8Array | undefined;
47  const idat: Uint8Array[] = [];
48  let idatLength = 0;
49
50  for (let pos = 8; pos + 8 <= bytes.length; ) {
51    const length = u32(bytes, pos);
52    const type = String.fromCharCode(bytes[pos + 4]!, bytes[pos + 5]!, bytes[pos + 6]!, bytes[pos + 7]!);
53    const body = bytes.subarray(pos + 8, pos + 8 + length);
54    if (body.length !== length) throw new Error("PNG ends inside a chunk");
55    pos += 12 + length;
56
57    if (type === "IHDR") {
58      width = u32(body, 0);
59      height = u32(body, 4);
60      depth = body[8]!;
61      colorType = body[9]!;
62      interlace = body[12]!;
63      if (body[10] !== 0 || body[11] !== 0 || interlace > 1) throw new Error("unknown PNG method");
64    } else if (type === "PLTE") {
65      palette = body;
66    } else if (type === "tRNS") {
67      trns = body;
68    } else if (type === "IDAT") {
69      idat.push(body);
70      idatLength += body.length;
71    } else if (type === "IEND") {
72      break;
73    }
74  }
75
76  const channels = CHANNELS[colorType];
77  if (channels === undefined || !DEPTHS[colorType]!.includes(depth)) {
78    throw new Error(`PNG colour type ${colorType} at depth ${depth}`);
79  }
80  if (!(width > 0 && height > 0)) throw new Error("PNG has no size");
81  if (width * height > maxPixels) throw new Error(`${width}×${height} is too large to preview`);
82  if (colorType === 3 && palette === undefined) throw new Error("PNG palette missing");
83  if (idat.length === 0) throw new Error("PNG has no image data");
84
85  const compressed = new Uint8Array(idatLength);
86  for (let i = 0, o = 0; i < idat.length; o += idat[i]!.length, i++) compressed.set(idat[i]!, o);
87
88  const bitsPerPixel = channels * depth;
89  const bpp = Math.max(1, bitsPerPixel >> 3);
90  const passes = interlace ? ADAM7 : WHOLE;
91  const sizes = passes.map(([x0, y0, dx, dy]) => {
92    const w = width > x0 ? Math.ceil((width - x0) / dx) : 0;
93    const h = height > y0 ? Math.ceil((height - y0) / dy) : 0;
94    return { w, h, rowBytes: Math.ceil((w * bitsPerPixel) / 8) };
95  });
96  const total = sizes.reduce((sum, s) => sum + (s.w && s.h ? s.h * (1 + s.rowBytes) : 0), 0);
97  const raw = inflate(compressed, total);
98
99  const rgba = new Uint8Array(width * height * 4);
100  const toRgba = converter(colorType, depth, palette, trns);
101  let at = 0;
102  passes.forEach(([x0, y0, dx, dy], p) => {
103    const { w, h, rowBytes } = sizes[p]!;
104    if (w === 0 || h === 0) return;
105    const row = new Uint8Array(w * 4);
106    let prev: Uint8Array | undefined;
107    for (let y = 0; y < h; y++) {
108      const filter = raw[at]!;
109      const line = raw.subarray(at + 1, at + 1 + rowBytes);
110      at += 1 + rowBytes;
111      unfilter(filter, line, prev, bpp);
112      prev = line;
113      toRgba(line, w, row);
114      const oy = y0 + y * dy;
115      if (dx === 1) {
116        rgba.set(row, oy * width * 4);
117      } else {
118        for (let x = 0; x < w; x++) {
119          const o = (oy * width + x0 + x * dx) * 4;
120          rgba[o] = row[x * 4]!;
121          rgba[o + 1] = row[x * 4 + 1]!;
122          rgba[o + 2] = row[x * 4 + 2]!;
123          rgba[o + 3] = row[x * 4 + 3]!;
124        }
125      }
126    }
127  });
128
129  return { width, height, rgba };
130}
131
132function unfilter(filter: number, line: Uint8Array, prev: Uint8Array | undefined, bpp: number) {
133  const n = line.length;
134  switch (filter) {
135    case 0:
136      return;
137    case 1:
138      for (let i = bpp; i < n; i++) line[i] = (line[i]! + line[i - bpp]!) & 255;
139      return;
140    case 2:
141      if (prev) for (let i = 0; i < n; i++) line[i] = (line[i]! + prev[i]!) & 255;
142      return;
143    case 3:
144      for (let i = 0; i < n; i++) {
145        const left = i >= bpp ? line[i - bpp]! : 0;
146        const up = prev ? prev[i]! : 0;
147        line[i] = (line[i]! + ((left + up) >> 1)) & 255;
148      }
149      return;
150    case 4:
151      for (let i = 0; i < n; i++) {
152        const a = i >= bpp ? line[i - bpp]! : 0;
153        const b = prev ? prev[i]! : 0;
154        const c = i >= bpp && prev ? prev[i - bpp]! : 0;
155        const pa = Math.abs(b - c);
156        const pb = Math.abs(a - c);
157        const pc = Math.abs(a + b - 2 * c);
158        const pred = pa <= pb && pa <= pc ? a : pb <= pc ? b : c;
159        line[i] = (line[i]! + pred) & 255;
160      }
161      return;
162    default:
163      throw new Error(`unknown PNG filter ${filter}`);
164  }
165}
166
167/** A function that writes `w` pixels of an unfiltered line as RGBA. */
168function converter(
169  colorType: number,
170  depth: number,
171  palette: Uint8Array | undefined,
172  trns: Uint8Array | undefined,
173): (line: Uint8Array, w: number, out: Uint8Array) => void {
174  // A sample of `depth` bits: index i of the line's samples.
175  const sample =
176    depth === 8
177      ? (line: Uint8Array, i: number) => line[i]!
178      : depth === 16
179        ? (line: Uint8Array, i: number) => (line[i * 2]! << 8) | line[i * 2 + 1]!
180        : (line: Uint8Array, i: number) => {
181            const bit = i * depth;
182            return (line[bit >> 3]! >> (8 - depth - (bit & 7))) & ((1 << depth) - 1);
183          };
184  const max = (1 << depth) - 1;
185  const to8 = (v: number) => (depth === 16 ? v >> 8 : depth === 8 ? v : Math.round((v * 255) / max));
186  const key = (i: number) => (trns && trns.length >= i * 2 + 2 ? (trns[i * 2]! << 8) | trns[i * 2 + 1]! : -1);
187
188  switch (colorType) {
189    case 0: {
190      const clear = key(0);
191      return (line, w, out) => {
192        for (let x = 0; x < w; x++) {
193          const v = sample(line, x);
194          const g = to8(v);
195          out[x * 4] = out[x * 4 + 1] = out[x * 4 + 2] = g;
196          out[x * 4 + 3] = v === clear ? 0 : 255;
197        }
198      };
199    }
200    case 2: {
201      const [kr, kg, kb] = [key(0), key(1), key(2)];
202      return (line, w, out) => {
203        for (let x = 0; x < w; x++) {
204          const r = sample(line, x * 3), g = sample(line, x * 3 + 1), b = sample(line, x * 3 + 2);
205          out[x * 4] = to8(r);
206          out[x * 4 + 1] = to8(g);
207          out[x * 4 + 2] = to8(b);
208          out[x * 4 + 3] = r === kr && g === kg && b === kb ? 0 : 255;
209        }
210      };
211    }
212    case 3: {
213      const pal = palette!;
214      const entries = Math.floor(pal.length / 3);
215      return (line, w, out) => {
216        for (let x = 0; x < w; x++) {
217          const i = sample(line, x);
218          if (i < entries) {
219            out[x * 4] = pal[i * 3]!;
220            out[x * 4 + 1] = pal[i * 3 + 1]!;
221            out[x * 4 + 2] = pal[i * 3 + 2]!;
222          } else {
223            out[x * 4] = out[x * 4 + 1] = out[x * 4 + 2] = 0;
224          }
225          out[x * 4 + 3] = trns && i < trns.length ? trns[i]! : 255;
226        }
227      };
228    }
229    case 4:
230      return (line, w, out) => {
231        for (let x = 0; x < w; x++) {
232          const g = to8(sample(line, x * 2));
233          out[x * 4] = out[x * 4 + 1] = out[x * 4 + 2] = g;
234          out[x * 4 + 3] = to8(sample(line, x * 2 + 1));
235        }
236      };
237    default:
238      return (line, w, out) => {
239        for (let x = 0; x < w; x++) {
240          out[x * 4] = to8(sample(line, x * 4));
241          out[x * 4 + 1] = to8(sample(line, x * 4 + 1));
242          out[x * 4 + 2] = to8(sample(line, x * 4 + 2));
243          out[x * 4 + 3] = to8(sample(line, x * 4 + 3));
244        }
245      };
246  }
247}
248

1// WebP: the RIFF container, lossy (VP8) with or without an alpha chunk,
2// lossless (VP8L), and an animation's first frame on a transparent canvas.
3
4import type { Pixmap } from "./pixels";
5import { decodeVp8, vp8ToRgba } from "./vp8";
6import { decodeVp8l, decodeVp8lStream } from "./vp8l";
7
8const ascii = (b: Uint8Array, at: number) => String.fromCharCode(b[at]!, b[at + 1]!, b[at + 2]!, b[at + 3]!);
9const u24 = (b: Uint8Array, at: number) => b[at]! | (b[at + 1]! << 8) | (b[at + 2]! << 16);
10const u32 = (b: Uint8Array, at: number) => (u24(b, at) + b[at + 3]! * 0x1000000);
11
12export function isWebp(bytes: Uint8Array): boolean {
13  return bytes.length >= 12 && ascii(bytes, 0) === "RIFF" && ascii(bytes, 8) === "WEBP";
14}
15
16type Chunk = { id: string; body: Uint8Array };
17
18function* chunks(bytes: Uint8Array, from: number, to: number): Generator<Chunk> {
19  for (let pos = from; pos + 8 <= to; ) {
20    const size = u32(bytes, pos + 4);
21    const body = bytes.subarray(pos + 8, Math.min(to, pos + 8 + size));
22    yield { id: ascii(bytes, pos), body };
23    pos += 8 + size + (size & 1);
24  }
25}
26
27/** Decodes a WebP's first image; `maxPixels` refuses anything bigger. */
28export function decodeWebp(bytes: Uint8Array, maxPixels: number): Pixmap {
29  if (!isWebp(bytes)) throw new Error("not a WebP");
30  const end = Math.min(bytes.length, 8 + u32(bytes, 4));
31  let alpha: Uint8Array | undefined;
32  for (const { id, body } of chunks(bytes, 12, end)) {
33    if (id === "ALPH") {
34      alpha = body;
35    } else if (id === "VP8 " || id === "VP8L") {
36      return frame(id, body, alpha, maxPixels);
37    } else if (id === "ANMF") {
38      return firstFrame(body, maxPixels, bytes);
39    }
40  }
41  throw new Error("WebP has no image");
42}
43
44function frame(id: string, body: Uint8Array, alpha: Uint8Array | undefined, maxPixels: number): Pixmap {
45  if (id === "VP8L") {
46    const { width, height, argb } = decodeVp8l(body, maxPixels);
47    const rgba = new Uint8Array(width * height * 4);
48    for (let i = 0; i < argb.length; i++) {
49      const v = argb[i]!;
50      rgba[i * 4] = (v >>> 16) & 255;
51      rgba[i * 4 + 1] = (v >>> 8) & 255;
52      rgba[i * 4 + 2] = v & 255;
53      rgba[i * 4 + 3] = v >>> 24;
54    }
55    return { width, height, rgba };
56  }
57  const f = decodeVp8(body, maxPixels);
58  const rgba = vp8ToRgba(f);
59  if (alpha !== undefined) {
60    const a = decodeAlpha(alpha, f.width, f.height, maxPixels);
61    for (let i = 0; i < a.length; i++) rgba[i * 4 + 3] = a[i]!;
62  }
63
64  return { width: f.width, height: f.height, rgba };
65}
66
67/** An ALPH chunk: header byte, then raw or VP8L-coded alpha, then unfiltered. */
68function decodeAlpha(chunk: Uint8Array, width: number, height: number, maxPixels: number): Uint8Array {
69  if (chunk.length < 2) throw new Error("bad WebP alpha");
70  const method = chunk[0]! & 3;
71  const filter = (chunk[0]! >> 2) & 3;
72  if (method > 1 || chunk[0]! >> 6) throw new Error("bad WebP alpha");
73  const data = chunk.subarray(1);
74  const out = new Uint8Array(width * height);
75  if (method === 0) {
76    if (data.length < out.length) throw new Error("WebP alpha ends early");
77    out.set(data.subarray(0, out.length));
78  } else {
79    const argb = decodeVp8lStream(data, width, height, maxPixels);
80    for (let i = 0; i < out.length; i++) out[i] = (argb[i]! >>> 8) & 255;
81  }
82  if (filter === 0) return out;
83
84  // libwebp's unfilters (dsp/filters.c), row by row, in place.
85  for (let y = 0; y < height; y++) {
86    const row = y * width;
87    const prev = row - width;
88    if (y === 0 || filter === 1) {
89      let pred = y === 0 ? 0 : out[prev]!;
90      for (let x = 0; x < width; x++) {
91        out[row + x] = (out[row + x]! + pred) & 255;
92        pred = out[row + x]!;
93      }
94    } else if (filter === 2) {
95      for (let x = 0; x < width; x++) out[row + x] = (out[row + x]! + out[prev + x]!) & 255;
96    } else {
97      let topLeft = out[prev]!;
98      let left = topLeft;
99      for (let x = 0; x < width; x++) {
100        const top = out[prev + x]!;
101        const g = left + top - topLeft;
102        left = (out[row + x]! + (g < 0 ? 0 : g > 255 ? 255 : g)) & 255;
103        topLeft = top;
104        out[row + x] = left;
105      }
106    }
107  }
108
109  return out;
110}
111
112/** An animation's first frame, placed on a transparent canvas. */
113function firstFrame(anmf: Uint8Array, maxPixels: number, file: Uint8Array): Pixmap {
114  // The canvas size is in the VP8X chunk, which comes first.
115  const vp8x = chunks(file, 12, file.length).next().value;
116  if (!vp8x || vp8x.id !== "VP8X" || vp8x.body.length < 10) throw new Error("bad animated WebP");
117  const width = u24(vp8x.body, 4) + 1;
118  const height = u24(vp8x.body, 7) + 1;
119  if (width * height > maxPixels) throw new Error(`${width}×${height} is too large to preview`);
120  const x0 = u24(anmf, 0) * 2;
121  const y0 = u24(anmf, 3) * 2;
122
123  let alpha: Uint8Array | undefined;
124  let pic: Pixmap | undefined;
125  for (const { id, body } of chunks(anmf, 16, anmf.length)) {
126    if (id === "ALPH") alpha = body;
127    else if (id === "VP8 " || id === "VP8L") {
128      pic = frame(id, body, alpha, maxPixels);
129      break;
130    }
131  }
132  if (pic === undefined) throw new Error("animated WebP has no frame");
133
134  const rgba = new Uint8Array(width * height * 4);
135  for (let y = 0; y < pic.height && y0 + y < height; y++) {
136    const w = Math.min(pic.width, width - x0);
137    if (w <= 0) break;
138    rgba.set(pic.rgba.subarray(y * pic.width * 4, (y * pic.width + w) * 4), ((y0 + y) * width + x0) * 4);
139  }
140
141  return { width, height, rgba };
142}
143

1// zlib decompression (RFC 1950 around RFC 1951 DEFLATE), for PNG's image
2// data. The hooks environment has no DecompressionStream and no WebAssembly,
3// so this is plain code: canonical Huffman codes looked up through one table
4// per code, indexed by the next `bits` bits of input (least significant first).
5
6const LENGTH_BASE = [
7  3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131,
8  163, 195, 227, 258,
9];
10const LENGTH_EXTRA = [
11  0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0,
12];
13const DIST_BASE = [
14  1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049,
15  3073, 4097, 6145, 8193, 12289, 16385, 24577,
16];
17const DIST_EXTRA = [
18  0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13,
19];
20/** The order code-length code lengths are sent in. */
21const CL_ORDER = [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15];
22
23/** Entries `(symbol << 4) | length`, 0 where no code lands. */
24type Table = { codes: Int32Array; bits: number };
25
26function table(lengths: ArrayLike<number>): Table {
27  let bits = 0;
28  const count = new Int32Array(16);
29  for (let i = 0; i < lengths.length; i++) {
30    const len = lengths[i]!;
31    count[len]!++;
32    if (len > bits) bits = len;
33  }
34  count[0] = 0;
35  const next = new Int32Array(16);
36  for (let len = 1, code = 0; len <= 15; len++) {
37    code = (code + count[len - 1]!) << 1;
38    next[len] = code;
39  }
40  const size = 1 << bits;
41  const codes = new Int32Array(size);
42  for (let sym = 0; sym < lengths.length; sym++) {
43    const len = lengths[sym]!;
44    if (len === 0) continue;
45    let code = next[len]!++;
46    let reversed = 0;
47    for (let i = 0; i < len; i++) {
48      reversed = (reversed << 1) | (code & 1);
49      code >>= 1;
50    }
51    for (let j = reversed; j < size; j += 1 << len) codes[j] = (sym << 4) | len;
52  }
53
54  return { codes, bits };
55}
56
57const FIXED_LIT = table(
58  Array.from({ length: 288 }, (_, i) => (i < 144 ? 8 : i < 256 ? 9 : i < 280 ? 7 : 8)),
59);
60const FIXED_DIST = table(Array.from({ length: 30 }, () => 5));
61
62/**
63 * Inflates a zlib stream. `size` is the expected output length: the buffer
64 * is made that big, and decoding stops once it is full (a PNG's data past its
65 * last row means nothing, and a stream that would run on is cut there).
66 */
67export function inflate(data: Uint8Array, size: number): Uint8Array {
68  if (data.length < 2 || (data[0]! & 0x0f) !== 8 || ((data[0]! << 8) | data[1]!) % 31 !== 0) {
69    throw new Error("not a zlib stream");
70  }
71  if (data[1]! & 0x20) throw new Error("zlib preset dictionary");
72
73  const out = new Uint8Array(size);
74  let o = 0;
75  let pos = 2;
76  // Bit buffer, least significant bit first. Reads past the end are zeros;
77  // `pos` keeps counting so a stream that ends early is caught.
78  let buf = 0;
79  let cnt = 0;
80  const end = data.length;
81
82  for (let last = 0; !last && o < size; ) {
83    while (cnt < 3) {
84      buf |= (pos < end ? data[pos]! : 0) << cnt;
85      pos++;
86      cnt += 8;
87    }
88    last = buf & 1;
89    const type = (buf >>> 1) & 3;
90    buf >>>= 3;
91    cnt -= 3;
92
93    if (type === 0) {
94      // Stored: the rest of this byte is dropped, then LEN, NLEN and the bytes.
95      buf >>>= cnt & 7;
96      cnt -= cnt & 7;
97      pos -= cnt >> 3;
98      buf = 0;
99      cnt = 0;
100      if (pos + 4 > end) throw new Error("deflate stream ends early");
101      const len = data[pos]! | (data[pos + 1]! << 8);
102      const nlen = data[pos + 2]! | (data[pos + 3]! << 8);
103      if ((len ^ 0xffff) !== nlen) throw new Error("bad stored block");
104      pos += 4;
105      if (pos + len > end) throw new Error("deflate stream ends early");
106      const n = Math.min(len, size - o);
107      out.set(data.subarray(pos, pos + n), o);
108      o += n;
109      pos += len;
110      continue;
111    }
112
113    let lit = FIXED_LIT;
114    let dist = FIXED_DIST;
115    if (type === 2) {
116      while (cnt < 14) {
117        buf |= (pos < end ? data[pos]! : 0) << cnt;
118        pos++;
119        cnt += 8;
120      }
121      const hlit = (buf & 31) + 257;
122      const hdist = ((buf >>> 5) & 31) + 1;
123      const hclen = ((buf >>> 10) & 15) + 4;
124      buf >>>= 14;
125      cnt -= 14;
126      const cl = new Uint8Array(19);
127      for (let i = 0; i < hclen; i++) {
128        while (cnt < 3) {
129          buf |= (pos < end ? data[pos]! : 0) << cnt;
130          pos++;
131          cnt += 8;
132        }
133        cl[CL_ORDER[i]!] = buf & 7;
134        buf >>>= 3;
135        cnt -= 3;
136      }
137      const clt = table(cl);
138      const lens = new Uint8Array(hlit + hdist);
139      for (let i = 0; i < lens.length; ) {
140        while (cnt < 15) {
141          buf |= (pos < end ? data[pos]! : 0) << cnt;
142          pos++;
143          cnt += 8;
144        }
145        const entry = clt.codes[buf & ((1 << clt.bits) - 1)]!;
146        if (entry === 0) throw new Error("bad code length code");
147        buf >>>= entry & 15;
148        cnt -= entry & 15;
149        const sym = entry >> 4;
150        if (sym < 16) {
151          lens[i++] = sym;
152          continue;
153        }
154        let repeat: number;
155        let value = 0;
156        if (sym === 16) {
157          if (i === 0) throw new Error("bad code length repeat");
158          value = lens[i - 1]!;
159          repeat = 3 + (buf & 3);
160          buf >>>= 2;
161          cnt -= 2;
162        } else if (sym === 17) {
163          repeat = 3 + (buf & 7);
164          buf >>>= 3;
165          cnt -= 3;
166        } else {
167          repeat = 11 + (buf & 127);
168          buf >>>= 7;
169          cnt -= 7;
170        }
171        if (i + repeat > lens.length) throw new Error("bad code length repeat");
172        lens.fill(value, i, i + repeat);
173        i += repeat;
174      }
175      lit = table(lens.subarray(0, hlit));
176      dist = table(lens.subarray(hlit));
177    } else if (type !== 1) {
178      throw new Error("bad deflate block type");
179    }
180
181    const litMask = (1 << lit.bits) - 1;
182    const distMask = (1 << dist.bits) - 1;
183    for (;;) {
184      while (cnt < 15) {
185        buf |= (pos < end ? data[pos]! : 0) << cnt;
186        pos++;
187        cnt += 8;
188      }
189      const entry = lit.codes[buf & litMask]!;
190      if (entry === 0) throw new Error("bad literal/length code");
191      buf >>>= entry & 15;
192      cnt -= entry & 15;
193      const sym = entry >> 4;
194      if (sym < 256) {
195        if (o >= size) break;
196        out[o++] = sym;
197        continue;
198      }
199      if (sym === 256) break;
200
201      const li = sym - 257;
202      if (li >= 29) throw new Error("bad length code");
203      let length = LENGTH_BASE[li]!;
204      const lx = LENGTH_EXTRA[li]!;
205      while (cnt < 15 + lx) {
206        buf |= (pos < end ? data[pos]! : 0) << cnt;
207        pos++;
208        cnt += 8;
209      }
210      if (lx) {
211        length += buf & ((1 << lx) - 1);
212        buf >>>= lx;
213        cnt -= lx;
214      }
215      const de = dist.codes[buf & distMask]!;
216      if (de === 0) throw new Error("bad distance code");
217      buf >>>= de & 15;
218      cnt -= de & 15;
219      const ds = de >> 4;
220      if (ds >= 30) throw new Error("bad distance code");
221      const dx = DIST_EXTRA[ds]!;
222      while (cnt < dx) {
223        buf |= (pos < end ? data[pos]! : 0) << cnt;
224        pos++;
225        cnt += 8;
226      }
227      const distance = DIST_BASE[ds]! + (buf & ((1 << dx) - 1));
228      buf >>>= dx;
229      cnt -= dx;
230      if (distance > o) throw new Error("distance before the start");
231      const stop = Math.min(o + length, size);
232      for (; o < stop; o++) out[o] = out[o - distance]!;
233      if (o >= size) break;
234    }
235    if (pos - (cnt >> 3) > end) throw new Error("deflate stream ends early");
236  }
237  if (o < size) throw new Error("deflate stream ends early");
238
239  return out;
240}
241

1// WebP lossy (VP8 key frame, RFC 6386) decoding to RGBA. A port of libwebp's
2// decoder (vp8_dec.c, tree_dec.c, quant_dec.c, frame_dec.c, dsp/dec.c,
3// dsp/upsampling.c, dsp/yuv.h), so the output is libwebp's to the bit:
4// prediction from unfiltered neighbours, the same in-loop filter, and the
5// same "fancy" chroma upsampling and fixed-point YUV to RGB.
6
7import {
8  AC_TABLE,
9  BANDS,
10  BMODES_PROBA,
11  CAT3,
12  CAT4,
13  CAT5,
14  CAT6,
15  COEFFS_PROBA0,
16  COEFFS_UPDATE_PROBA,
17  DC_TABLE,
18  ZIGZAG,
19} from "./webp-tables";
20
21const CATS = [CAT3, CAT4, CAT5, CAT6];
22
23// The reconstruction buffer, as libwebp lays it out: a stride of 32, the
24// row above and the column left of each plane kept beside it.
25const BPS = 32;
26const Y_OFF = BPS + 8;
27const U_OFF = Y_OFF + BPS * 16 + BPS;
28const V_OFF = U_OFF + 16;
29const YUV_SIZE = BPS * 17 + BPS * 9;
30/** Where 4x4 block n starts inside the 16x16 one. */
31const SCAN = Array.from({ length: 16 }, (_, n) => (n & 3) * 4 + (n >> 2) * 4 * BPS);
32
33/** The boolean entropy decoder (RFC 6386 section 7); past the end, zeros. */
34class BoolReader {
35  readonly data: Uint8Array;
36  pos: number;
37  readonly end: number;
38  value: number;
39  range = 255;
40  bitCount = 0;
41  /** Bytes read past the end. */
42  over = 0;
43
44  constructor(data: Uint8Array, start: number, end: number) {
45    this.data = data;
46    this.pos = start;
47    this.end = end;
48    this.value = (this.next() << 8) | this.next();
49  }
50
51  next(): number {
52    if (this.pos < this.end) return this.data[this.pos++]!;
53    this.over++;
54    return 0;
55  }
56
57  bit(prob: number): number {
58    const split = 1 + (((this.range - 1) * prob) >> 8);
59    const big = split << 8;
60    let bit: number;
61    if (this.value >= big) {
62      bit = 1;
63      this.range -= split;
64      this.value -= big;
65    } else {
66      bit = 0;
67      this.range = split;
68    }
69    while (this.range < 128) {
70      this.value <<= 1;
71      this.range <<= 1;
72      if (++this.bitCount === 8) {
73        this.bitCount = 0;
74        this.value |= this.next();
75      }
76    }
77
78    return bit;
79  }
80
81  value_(bits: number): number {
82    let v = 0;
83    while (bits-- > 0) v |= this.bit(0x80) << bits;
84    return v;
85  }
86
87  flag(): number {
88    return this.bit(0x80);
89  }
90
91  signed(bits: number): number {
92    const v = this.value_(bits);
93    return this.flag() ? -v : v;
94  }
95}
96
97type Quant = { y1: number[]; y2: number[]; uv: number[] };
98type FilterInfo = { limit: number; ilevel: number; hev: number; inner: number };
99
100const clip = (v: number, max: number) => (v < 0 ? 0 : v > max ? max : v);
101const clip1 = (v: number) => (v < 0 ? 0 : v > 255 ? 255 : v);
102const sclip1 = (v: number) => (v < -128 ? -128 : v > 127 ? 127 : v);
103const sclip2 = (v: number) => (v < -16 ? -16 : v > 15 ? 15 : v);
104const mul1 = (a: number) => ((a * 20091) >> 16) + a;
105const mul2 = (a: number) => (a * 35468) >> 16;
106const avg3 = (a: number, b: number, c: number) => (a + 2 * b + c + 2) >> 2;
107const avg2 = (a: number, b: number) => (a + b + 1) >> 1;
108
109export type Vp8Frame = {
110  width: number;
111  height: number;
112  y: Uint8Array;
113  u: Uint8Array;
114  v: Uint8Array;
115  yStride: number;
116  uvStride: number;
117};
118
119/** Decodes a `VP8 ` chunk's payload to Y, U and V planes. */
120export function decodeVp8(data: Uint8Array, maxPixels: number): Vp8Frame {
121  if (data.length < 10) throw new Error("WebP data ends early");
122  const tag = data[0]! | (data[1]! << 8) | (data[2]! << 16);
123  if (tag & 1) throw new Error("WebP lossy data is not a key frame");
124  if (((tag >> 1) & 7) > 3 || !((tag >> 4) & 1)) throw new Error("bad WebP key frame");
125  if (data[3] !== 0x9d || data[4] !== 0x01 || data[5] !== 0x2a) throw new Error("bad WebP key frame");
126  const partLength = tag >>> 5;
127  const width = ((data[7]! << 8) | data[6]!) & 0x3fff;
128  const height = ((data[9]! << 8) | data[8]!) & 0x3fff;
129  if (!(width > 0 && height > 0)) throw new Error("WebP image has no size");
130  if (width * height > maxPixels) throw new Error(`${width}×${height} is too large to preview`);
131  const mbW = (width + 15) >> 4;
132  const mbH = (height + 15) >> 4;
133
134  let pos = 10;
135  if (pos + partLength > data.length) throw new Error("WebP data ends early");
136  const br = new BoolReader(data, pos, pos + partLength);
137  pos += partLength;
138  br.flag(); // colour space
139  br.flag(); // clamping type
140
141  // Segments (9.3).
142  const useSegment = br.flag();
143  let updateMap = 0;
144  let absoluteDelta = 1;
145  const quantizer = [0, 0, 0, 0];
146  const strength = [0, 0, 0, 0];
147  const segProbs = [255, 255, 255];
148  if (useSegment) {
149    updateMap = br.flag();
150    if (br.flag()) {
151      absoluteDelta = br.flag();
152      for (let s = 0; s < 4; s++) quantizer[s] = br.flag() ? br.signed(7) : 0;
153      for (let s = 0; s < 4; s++) strength[s] = br.flag() ? br.signed(6) : 0;
154    }
155    if (updateMap) for (let s = 0; s < 3; s++) segProbs[s] = br.flag() ? br.value_(8) : 255;
156  }
157
158  // Loop filter (9.4).
159  const simple = br.flag();
160  const level = br.value_(6);
161  const sharpness = br.value_(3);
162  const useLfDelta = br.flag();
163  const refDelta = [0, 0, 0, 0];
164  const modeDelta = [0, 0, 0, 0];
165  if (useLfDelta && br.flag()) {
166    for (let i = 0; i < 4; i++) if (br.flag()) refDelta[i] = br.signed(6);
167    for (let i = 0; i < 4; i++) if (br.flag()) modeDelta[i] = br.signed(6);
168  }
169  const filterType = level === 0 ? 0 : simple ? 1 : 2;
170
171  // Token partitions (9.5).
172  const numParts = 1 << br.value_(2);
173  let partStart = pos + 3 * (numParts - 1);
174  if (partStart > data.length) throw new Error("WebP data ends early");
175  const parts: BoolReader[] = [];
176  let left = data.length - partStart;
177  for (let p = 0; p < numParts - 1; p++) {
178    const at = pos + 3 * p;
179    const size = Math.min(left, data[at]! | (data[at + 1]! << 8) | (data[at + 2]! << 16));
180    parts.push(new BoolReader(data, partStart, partStart + size));
181    partStart += size;
182    left -= size;
183  }
184  if (partStart >= data.length) throw new Error("WebP data ends early");
185  parts.push(new BoolReader(data, partStart, data.length));
186
187  // Quantizers (9.6).
188  const baseQ = br.value_(7);
189  const dqY1Dc = br.flag() ? br.signed(4) : 0;
190  const dqY2Dc = br.flag() ? br.signed(4) : 0;
191  const dqY2Ac = br.flag() ? br.signed(4) : 0;
192  const dqUvDc = br.flag() ? br.signed(4) : 0;
193  const dqUvAc = br.flag() ? br.signed(4) : 0;
194  const quants: Quant[] = [];
195  for (let s = 0; s < 4; s++) {
196    if (!useSegment && s > 0) {
197      quants.push(quants[0]!);
198      continue;
199    }
200    const q = useSegment ? quantizer[s]! + (absoluteDelta ? 0 : baseQ) : baseQ;
201    const y2ac = (AC_TABLE[clip(q + dqY2Ac, 127)]! * 101581) >> 16;
202    quants.push({
203      y1: [DC_TABLE[clip(q + dqY1Dc, 127)]!, AC_TABLE[clip(q, 127)]!],
204      y2: [DC_TABLE[clip(q + dqY2Dc, 127)]! * 2, y2ac < 8 ? 8 : y2ac],
205      uv: [DC_TABLE[clip(q + dqUvDc, 117)]!, AC_TABLE[clip(q + dqUvAc, 127)]!],
206    });
207  }
208
209  br.flag(); // update_proba: ignored, as libwebp does
210
211  // Token probabilities (13.4) and the skip flag's.
212  const proba = new Uint8Array(COEFFS_PROBA0.length);
213  for (let i = 0; i < proba.length; i++) {
214    proba[i] = br.bit(COEFFS_UPDATE_PROBA[i]!) ? br.value_(8) : COEFFS_PROBA0[i]!;
215  }
216  const useSkip = br.flag();
217  const skipProb = useSkip ? br.value_(8) : 0;
218  /** Offset of the probabilities for type t at coefficient n (band), context 0. */
219  const bandAt = Array.from({ length: 4 }, (_, t) =>
220    Int32Array.from({ length: 17 }, (_, n) => (t * 8 + BANDS[n]!) * 33),
221  );
222
223  // Filter strength per segment and per i4x4/i16x16.
224  const strengths: FilterInfo[][] = [];
225  for (let s = 0; s < 4; s++) {
226    const base = useSegment ? strength[s]! + (absoluteDelta ? 0 : level) : level;
227    const pair: FilterInfo[] = [];
228    for (let i4x4 = 0; i4x4 <= 1; i4x4++) {
229      let lvl = base;
230      if (useLfDelta) {
231        lvl += refDelta[0]!;
232        if (i4x4) lvl += modeDelta[0]!;
233      }
234      lvl = clip(lvl, 63);
235      let ilevel = lvl;
236      if (sharpness > 0) {
237        ilevel >>= sharpness > 4 ? 2 : 1;
238        if (ilevel > 9 - sharpness) ilevel = 9 - sharpness;
239      }
240      if (ilevel < 1) ilevel = 1;
241      pair.push({
242        limit: filterType > 0 && lvl > 0 ? 2 * lvl + ilevel : 0,
243        ilevel,
244        hev: lvl >= 40 ? 2 : lvl >= 15 ? 1 : 0,
245        inner: i4x4,
246      });
247    }
248    strengths.push(pair);
249  }
250
251  // State.
252  const yStride = mbW * 16;
253  const uvStride = mbW * 8;
254  const Y = new Uint8Array(yStride * mbH * 16);
255  const U = new Uint8Array(uvStride * mbH * 8);
256  const V = new Uint8Array(uvStride * mbH * 8);
257  const intraT = new Uint8Array(4 * mbW);
258  const intraL = new Uint8Array(4);
259  const topNz = new Uint8Array(mbW);
260  const topNzDc = new Uint8Array(mbW);
261  const topY = new Uint8Array(yStride);
262  const topU = new Uint8Array(uvStride);
263  const topV = new Uint8Array(uvStride);
264  const buf = new Uint8Array(YUV_SIZE);
265  // One row of macroblocks, parsed then reconstructed.
266  const isI4 = new Uint8Array(mbW);
267  const imodes = new Uint8Array(mbW * 16);
268  const uvMode = new Uint8Array(mbW);
269  const segment = new Uint8Array(mbW);
270  const skipFlag = new Uint8Array(mbW);
271  const coeffs = new Int16Array(mbW * 384);
272  // The whole frame's filter settings, applied once all is reconstructed.
273  const fLimit = new Int32Array(mbW * mbH);
274  const fIlevel = new Int32Array(mbW * mbH);
275  const fHev = new Int32Array(mbW * mbH);
276  const fInner = new Uint8Array(mbW * mbH);
277  const dc = new Int16Array(16);
278
279  function largeValue(t: BoolReader, p: number): number {
280    if (!t.bit(proba[p + 3]!)) {
281      return t.bit(proba[p + 4]!) ? 3 + t.bit(proba[p + 5]!) : 2;
282    }
283    if (!t.bit(proba[p + 6]!)) {
284      if (!t.bit(proba[p + 7]!)) return 5 + t.bit(159);
285      return 7 + 2 * t.bit(165) + t.bit(145);
286    }
287    const b1 = t.bit(proba[p + 8]!);
288    const b0 = t.bit(proba[p + 9 + b1]!);
289    const cat = 2 * b1 + b0;
290    let v = 0;
291    for (const pr of CATS[cat]!) v += v + t.bit(pr);
292    return v + 3 + (8 << cat);
293  }
294
295  /** Coefficients of one 4x4 block from n on; the last non-zero position plus one. */
296  function getCoeffs(
297    t: BoolReader,
298    type: number,
299    ctx: number,
300    dq: number[],
301    n: number,
302    out: Int16Array,
303    at: number,
304  ): number {
305    const bands = bandAt[type]!;
306    let p = bands[n]! + ctx * 11;
307    for (; n < 16; ++n) {
308      if (!t.bit(proba[p]!)) return n;
309      while (!t.bit(proba[p + 1]!)) {
310        p = bands[++n]!;
311        if (n === 16) return 16;
312      }
313      const next = bands[n + 1]!;
314      let v: number;
315      if (!t.bit(proba[p + 2]!)) {
316        v = 1;
317        p = next + 11;
318      } else {
319        v = largeValue(t, p);
320        p = next + 22;
321      }
322      out[at + ZIGZAG[n]!] = (t.bit(0x80) ? -v : v) * dq[n > 0 ? 1 : 0]!;
323    }
324
325    return 16;
326  }
327
328  const nzCode = (bits: number, nz: number, dcNz: number) =>
329    (bits << 2) | (nz > 3 ? 3 : nz > 1 ? 2 : dcNz);
330
331  let leftNz = 0;
332  let leftNzDc = 0;
333
334  /** libwebp's ParseResiduals: true when every coefficient is zero. */
335  function residuals(t: BoolReader, mbX: number): boolean {
336    const q = quants[segment[mbX]!]!;
337    const base = mbX * 384;
338    coeffs.fill(0, base, base + 384);
339    let first: number;
340    let acType: number;
341    if (!isI4[mbX]) {
342      dc.fill(0);
343      const nz = getCoeffs(t, 1, topNzDc[mbX]! + leftNzDc, q.y2, 0, dc, 0);
344      topNzDc[mbX] = leftNzDc = nz > 0 ? 1 : 0;
345      wht(dc, coeffs, base);
346      first = 1;
347      acType = 0;
348    } else {
349      first = 0;
350      acType = 3;
351    }
352
353    let tnz = topNz[mbX]! & 0x0f;
354    let lnz = leftNz & 0x0f;
355    let nonZeroY = 0;
356    let at = base;
357    for (let y = 0; y < 4; y++) {
358      let l = lnz & 1;
359      let bits = 0;
360      for (let x = 0; x < 4; x++) {
361        const nz = getCoeffs(t, acType, l + (tnz & 1), q.y1, first, coeffs, at);
362        l = nz > first ? 1 : 0;
363        tnz = (tnz >> 1) | (l << 7);
364        bits = nzCode(bits, nz, coeffs[at] !== 0 ? 1 : 0);
365        at += 16;
366      }
367      tnz >>= 4;
368      lnz = (lnz >> 1) | (l << 7);
369      nonZeroY = (nonZeroY << 8) | bits;
370    }
371    let outT = tnz;
372    let outL = lnz >> 4;
373
374    let nonZeroUv = 0;
375    for (let ch = 0; ch < 4; ch += 2) {
376      let bits = 0;
377      tnz = topNz[mbX]! >> (4 + ch);
378      lnz = leftNz >> (4 + ch);
379      for (let y = 0; y < 2; y++) {
380        let l = lnz & 1;
381        for (let x = 0; x < 2; x++) {
382          const nz = getCoeffs(t, 2, l + (tnz & 1), q.uv, 0, coeffs, at);
383          l = nz > 0 ? 1 : 0;
384          tnz = (tnz >> 1) | (l << 3);
385          bits = nzCode(bits, nz, coeffs[at] !== 0 ? 1 : 0);
386          at += 16;
387        }
388        tnz >>= 2;
389        lnz = (lnz >> 1) | (l << 5);
390      }
391      nonZeroUv |= bits << (4 * ch);
392      outT |= (tnz << 4) << ch;
393      outL |= (lnz & 0xf0) << ch;
394    }
395    topNz[mbX] = outT & 0xff;
396    leftNz = outL & 0xff;
397
398    return (nonZeroY | nonZeroUv) === 0;
399  }
400
401  function intraModes(mbX: number) {
402    segment[mbX] = updateMap
403      ? !br.bit(segProbs[0]!)
404        ? br.bit(segProbs[1]!)
405        : br.bit(segProbs[2]!) + 2
406      : 0;
407    skipFlag[mbX] = useSkip ? br.bit(skipProb) : 0;
408    const top = 4 * mbX;
409    isI4[mbX] = br.bit(145) ? 0 : 1;
410    if (!isI4[mbX]) {
411      const mode = br.bit(156) ? (br.bit(128) ? 1 : 3) : br.bit(163) ? 2 : 0; // TM, H : V, DC
412      imodes[mbX * 16] = mode;
413      intraT.fill(mode, top, top + 4);
414      intraL.fill(mode);
415    } else {
416      for (let y = 0; y < 4; y++) {
417        let ymode = intraL[y]!;
418        for (let x = 0; x < 4; x++) {
419          const p = (intraT[top + x]! * 10 + ymode) * 9;
420          const pr = (i: number) => BMODES_PROBA[p + i]!;
421          ymode = !br.bit(pr(0))
422            ? 0 // B_DC_PRED
423            : !br.bit(pr(1))
424              ? 1 // B_TM_PRED
425              : !br.bit(pr(2))
426                ? 2 // B_VE_PRED
427                : !br.bit(pr(3))
428                  ? !br.bit(pr(4))
429                    ? 3 // B_HE_PRED
430                    : !br.bit(pr(5))
431                      ? 4 // B_RD_PRED
432                      : 5 // B_VR_PRED
433                  : !br.bit(pr(6))
434                    ? 6 // B_LD_PRED
435                    : !br.bit(pr(7))
436                      ? 7 // B_VL_PRED
437                      : !br.bit(pr(8))
438                        ? 8 // B_HD_PRED
439                        : 9; // B_HU_PRED
440          intraT[top + x] = ymode;
441        }
442        for (let x = 0; x < 4; x++) imodes[mbX * 16 + y * 4 + x] = intraT[top + x]!;
443        intraL[y] = ymode;
444      }
445    }
446    uvMode[mbX] = !br.bit(142) ? 0 : !br.bit(114) ? 2 : br.bit(183) ? 1 : 3; // DC, V, TM, H
447  }
448
449  for (let mbY = 0; mbY < mbH; mbY++) {
450    for (let mbX = 0; mbX < mbW; mbX++) intraModes(mbX);
451    if (br.over > 8) throw new Error("WebP data ends early");
452    const t = parts[mbY & (numParts - 1)]!;
453    for (let mbX = 0; mbX < mbW; mbX++) {
454      let skip = skipFlag[mbX]!;
455      if (!skip) {
456        skip = residuals(t, mbX) ? 1 : 0;
457      } else {
458        leftNz = topNz[mbX] = 0;
459        if (!isI4[mbX]) leftNzDc = topNzDc[mbX] = 0;
460        coeffs.fill(0, mbX * 384, mbX * 384 + 384);
461      }
462      if (filterType > 0) {
463        const info = strengths[segment[mbX]!]![isI4[mbX]!]!;
464        const i = mbY * mbW + mbX;
465        fLimit[i] = info.limit;
466        fIlevel[i] = info.ilevel;
467        fHev[i] = info.hev;
468        fInner[i] = info.inner | (skip ? 0 : 1);
469      }
470    }
471    if (t.over > 8) throw new Error("WebP data ends early");
472    leftNz = 0;
473    leftNzDc = 0;
474    intraL.fill(0);
475    reconstructRow(mbY);
476  }
477
478  function reconstructRow(mbY: number) {
479    for (let j = 0; j < 16; j++) buf[Y_OFF + j * BPS - 1] = 129;
480    for (let j = 0; j < 8; j++) {
481      buf[U_OFF + j * BPS - 1] = 129;
482      buf[V_OFF + j * BPS - 1] = 129;
483    }
484    if (mbY > 0) {
485      buf[Y_OFF - 1 - BPS] = buf[U_OFF - 1 - BPS] = buf[V_OFF - 1 - BPS] = 129;
486    } else {
487      buf.fill(127, Y_OFF - BPS - 1, Y_OFF - BPS - 1 + 21);
488      buf.fill(127, U_OFF - BPS - 1, U_OFF - BPS - 1 + 9);
489      buf.fill(127, V_OFF - BPS - 1, V_OFF - BPS - 1 + 9);
490    }
491
492    for (let mbX = 0; mbX < mbW; mbX++) {
493      if (mbX > 0) {
494        for (let j = -1; j < 16; j++) buf.copyWithin(Y_OFF + j * BPS - 4, Y_OFF + j * BPS + 12, Y_OFF + j * BPS + 16);
495        for (let j = -1; j < 8; j++) {
496          buf.copyWithin(U_OFF + j * BPS - 4, U_OFF + j * BPS + 4, U_OFF + j * BPS + 8);
497          buf.copyWithin(V_OFF + j * BPS - 4, V_OFF + j * BPS + 4, V_OFF + j * BPS + 8);
498        }
499      }
500      if (mbY > 0) {
501        buf.set(topY.subarray(mbX * 16, mbX * 16 + 16), Y_OFF - BPS);
502        buf.set(topU.subarray(mbX * 8, mbX * 8 + 8), U_OFF - BPS);
503        buf.set(topV.subarray(mbX * 8, mbX * 8 + 8), V_OFF - BPS);
504      }
505      const base = mbX * 384;
506
507      if (isI4[mbX]) {
508        const tr = Y_OFF - BPS + 16;
509        if (mbY > 0) {
510          if (mbX >= mbW - 1) buf.fill(topY[mbX * 16 + 15]!, tr, tr + 4);
511          else buf.set(topY.subarray((mbX + 1) * 16, (mbX + 1) * 16 + 4), tr);
512        }
513        for (let k = 1; k <= 3; k++) buf.copyWithin(tr + k * 4 * BPS, tr, tr + 4);
514        for (let n = 0; n < 16; n++) {
515          const dst = Y_OFF + SCAN[n]!;
516          predLuma4(imodes[mbX * 16 + n]!, buf, dst);
517          transform(coeffs, base + n * 16, buf, dst);
518        }
519      } else {
520        predLuma16(checkMode(mbX, mbY, imodes[mbX * 16]!), buf, Y_OFF);
521        for (let n = 0; n < 16; n++) transform(coeffs, base + n * 16, buf, Y_OFF + SCAN[n]!);
522      }
523      const uvPred = checkMode(mbX, mbY, uvMode[mbX]!);
524      predChroma8(uvPred, buf, U_OFF);
525      predChroma8(uvPred, buf, V_OFF);
526      for (let k = 0; k < 4; k++) {
527        const off = (k & 1) * 4 + (k >> 1) * 4 * BPS;
528        transform(coeffs, base + (16 + k) * 16, buf, U_OFF + off);
529        transform(coeffs, base + (20 + k) * 16, buf, V_OFF + off);
530      }
531
532      if (mbY < mbH - 1) {
533        topY.set(buf.subarray(Y_OFF + 15 * BPS, Y_OFF + 15 * BPS + 16), mbX * 16);
534        topU.set(buf.subarray(U_OFF + 7 * BPS, U_OFF + 7 * BPS + 8), mbX * 8);
535        topV.set(buf.subarray(V_OFF + 7 * BPS, V_OFF + 7 * BPS + 8), mbX * 8);
536      }
537      for (let j = 0; j < 16; j++) {
538        Y.set(buf.subarray(Y_OFF + j * BPS, Y_OFF + j * BPS + 16), (mbY * 16 + j) * yStride + mbX * 16);
539      }
540      for (let j = 0; j < 8; j++) {
541        U.set(buf.subarray(U_OFF + j * BPS, U_OFF + j * BPS + 8), (mbY * 8 + j) * uvStride + mbX * 8);
542        V.set(buf.subarray(V_OFF + j * BPS, V_OFF + j * BPS + 8), (mbY * 8 + j) * uvStride + mbX * 8);
543      }
544    }
545  }
546
547  // In-loop filter, macroblock by macroblock in raster order.
548  if (filterType > 0) {
549    for (let mbY = 0; mbY < mbH; mbY++) {
550      for (let mbX = 0; mbX < mbW; mbX++) {
551        const i = mbY * mbW + mbX;
552        const limit = fLimit[i]!;
553        if (limit === 0) continue;
554        const ilevel = fIlevel[i]!;
555        const hev = fHev[i]!;
556        const inner = fInner[i]!;
557        const y = mbY * 16 * yStride + mbX * 16;
558        if (filterType === 1) {
559          if (mbX > 0) simpleH16(Y, y, yStride, limit + 4);
560          if (inner) for (let k = 4; k < 16; k += 4) simpleH16(Y, y + k, yStride, limit);
561          if (mbY > 0) simpleV16(Y, y, yStride, limit + 4);
562          if (inner) for (let k = 4; k < 16; k += 4) simpleV16(Y, y + k * yStride, yStride, limit);
563        } else {
564          const uv = mbY * 8 * uvStride + mbX * 8;
565          if (mbX > 0) {
566            loop26(Y, y, 1, yStride, 16, limit + 4, ilevel, hev);
567            loop26(U, uv, 1, uvStride, 8, limit + 4, ilevel, hev);
568            loop26(V, uv, 1, uvStride, 8, limit + 4, ilevel, hev);
569          }
570          if (inner) {
571            for (let k = 4; k < 16; k += 4) loop24(Y, y + k, 1, yStride, 16, limit, ilevel, hev);
572            loop24(U, uv + 4, 1, uvStride, 8, limit, ilevel, hev);
573            loop24(V, uv + 4, 1, uvStride, 8, limit, ilevel, hev);
574          }
575          if (mbY > 0) {
576            loop26(Y, y, yStride, 1, 16, limit + 4, ilevel, hev);
577            loop26(U, uv, uvStride, 1, 8, limit + 4, ilevel, hev);
578            loop26(V, uv, uvStride, 1, 8, limit + 4, ilevel, hev);
579          }
580          if (inner) {
581            for (let k = 4; k < 16; k += 4) loop24(Y, y + k * yStride, yStride, 1, 16, limit, ilevel, hev);
582            loop24(U, uv + 4 * uvStride, uvStride, 1, 8, limit, ilevel, hev);
583            loop24(V, uv + 4 * uvStride, uvStride, 1, 8, limit, ilevel, hev);
584          }
585        }
586      }
587    }
588  }
589
590  return { width, height, y: Y, u: U, v: V, yStride, uvStride };
591}
592
593/** DC_PRED at the frame's edges becomes its no-top / no-left variants. */
594function checkMode(mbX: number, mbY: number, mode: number): number {
595  if (mode !== 0) return mode;
596  if (mbX === 0) return mbY === 0 ? 6 : 5;
597  return mbY === 0 ? 4 : 0;
598}
599
600/** The inverse Walsh-Hadamard transform into each 4x4 block's DC. */
601function wht(input: Int16Array, out: Int16Array, at: number) {
602  const tmp = new Int32Array(16);
603  for (let i = 0; i < 4; i++) {
604    const a0 = input[i]! + input[12 + i]!;
605    const a1 = input[4 + i]! + input[8 + i]!;
606    const a2 = input[4 + i]! - input[8 + i]!;
607    const a3 = input[i]! - input[12 + i]!;
608    tmp[i] = a0 + a1;
609    tmp[8 + i] = a0 - a1;
610    tmp[4 + i] = a3 + a2;
611    tmp[12 + i] = a3 - a2;
612  }
613  for (let i = 0; i < 4; i++) {
614    const dc = tmp[i * 4]! + 3;
615    const a0 = dc + tmp[3 + i * 4]!;
616    const a1 = tmp[1 + i * 4]! + tmp[2 + i * 4]!;
617    const a2 = tmp[1 + i * 4]! - tmp[2 + i * 4]!;
618    const a3 = dc - tmp[3 + i * 4]!;
619    const o = at + i * 64;
620    out[o] = (a0 + a1) >> 3;
621    out[o + 16] = (a3 + a2) >> 3;
622    out[o + 32] = (a0 - a1) >> 3;
623    out[o + 48] = (a3 - a2) >> 3;
624  }
625}
626
627const idct = new Int32Array(16);
628
629/** Adds one 4x4 block's inverse DCT to the prediction (none if all zero). */
630function transform(c: Int16Array, at: number, b: Uint8Array, dst: number) {
631  let any = 0;
632  for (let i = 0; i < 16; i++) any |= c[at + i]!;
633  if (any === 0) return;
634  for (let i = 0; i < 4; i++) {
635    const a = c[at + i]! + c[at + 8 + i]!;
636    const bb = c[at + i]! - c[at + 8 + i]!;
637    const cc = mul2(c[at + 4 + i]!) - mul1(c[at + 12 + i]!);
638    const d = mul1(c[at + 4 + i]!) + mul2(c[at + 12 + i]!);
639    idct[i * 4] = a + d;
640    idct[i * 4 + 1] = bb + cc;
641    idct[i * 4 + 2] = bb - cc;
642    idct[i * 4 + 3] = a - d;
643  }
644  for (let i = 0; i < 4; i++) {
645    const dc = idct[i]! + 4;
646    const a = dc + idct[8 + i]!;
647    const bb = dc - idct[8 + i]!;
648    const cc = mul2(idct[4 + i]!) - mul1(idct[12 + i]!);
649    const d = mul1(idct[4 + i]!) + mul2(idct[12 + i]!);
650    const o = dst + i * BPS;
651    b[o] = clip1(b[o]! + ((a + d) >> 3));
652    b[o + 1] = clip1(b[o + 1]! + ((bb + cc) >> 3));
653    b[o + 2] = clip1(b[o + 2]! + ((bb - cc) >> 3));
654    b[o + 3] = clip1(b[o + 3]! + ((a - d) >> 3));
655  }
656}
657
658function trueMotion(b: Uint8Array, dst: number, size: number) {
659  const topLeft = b[dst - BPS - 1]!;
660  for (let y = 0; y < size; y++) {
661    const left = b[dst + y * BPS - 1]!;
662    for (let x = 0; x < size; x++) b[dst + y * BPS + x] = clip1(b[dst - BPS + x]! + left - topLeft);
663  }
664}
665
666function fill(b: Uint8Array, dst: number, size: number, v: number) {
667  for (let y = 0; y < size; y++) b.fill(v, dst + y * BPS, dst + y * BPS + size);
668}
669
670function predLuma16(mode: number, b: Uint8Array, dst: number) {
671  let dc: number;
672  switch (mode) {
673    case 1:
674      return trueMotion(b, dst, 16);
675    case 2:
676      for (let y = 0; y < 16; y++) b.copyWithin(dst + y * BPS, dst - BPS, dst - BPS + 16);
677      return;
678    case 3:
679      for (let y = 0; y < 16; y++) b.fill(b[dst + y * BPS - 1]!, dst + y * BPS, dst + y * BPS + 16);
680      return;
681    case 4: // no top
682      dc = 8;
683      for (let j = 0; j < 16; j++) dc += b[dst - 1 + j * BPS]!;
684      return fill(b, dst, 16, dc >> 4);
685    case 5: // no left
686      dc = 8;
687      for (let i = 0; i < 16; i++) dc += b[dst + i - BPS]!;
688      return fill(b, dst, 16, dc >> 4);
689    case 6:
690      return fill(b, dst, 16, 0x80);
691    default:
692      dc = 16;
693      for (let j = 0; j < 16; j++) dc += b[dst - 1 + j * BPS]! + b[dst + j - BPS]!;
694      return fill(b, dst, 16, dc >> 5);
695  }
696}
697
698function predChroma8(mode: number, b: Uint8Array, dst: number) {
699  let dc: number;
700  switch (mode) {
701    case 1:
702      return trueMotion(b, dst, 8);
703    case 2:
704      for (let y = 0; y < 8; y++) b.copyWithin(dst + y * BPS, dst - BPS, dst - BPS + 8);
705      return;
706    case 3:
707      for (let y = 0; y < 8; y++) b.fill(b[dst + y * BPS - 1]!, dst + y * BPS, dst + y * BPS + 8);
708      return;
709    case 4: // no top
710      dc = 4;
711      for (let i = 0; i < 8; i++) dc += b[dst - 1 + i * BPS]!;
712      return fill(b, dst, 8, dc >> 3);
713    case 5: // no left
714      dc = 4;
715      for (let i = 0; i < 8; i++) dc += b[dst + i - BPS]!;
716      return fill(b, dst, 8, dc >> 3);
717    case 6:
718      return fill(b, dst, 8, 0x80);
719    default:
720      dc = 8;
721      for (let i = 0; i < 8; i++) dc += b[dst + i - BPS]! + b[dst - 1 + i * BPS]!;
722      return fill(b, dst, 8, dc >> 4);
723  }
724}
725
726function predLuma4(mode: number, b: Uint8Array, dst: number) {
727  const at = (x: number, y: number) => b[dst + x + y * BPS]!;
728  const set = (x: number, y: number, v: number) => {
729    b[dst + x + y * BPS] = v;
730  };
731  const I = at(-1, 0), J = at(-1, 1), K = at(-1, 2), L = at(-1, 3);
732  const X = at(-1, -1);
733  const A = at(0, -1), B = at(1, -1), C = at(2, -1), D = at(3, -1);
734  const E = at(4, -1), F = at(5, -1), G = at(6, -1), H = at(7, -1);
735  switch (mode) {
736    case 0: {
737      // DC
738      const dc = (A + B + C + D + I + J + K + L + 4) >> 3;
739      return fill(b, dst, 4, dc);
740    }
741    case 1:
742      return trueMotion(b, dst, 4);
743    case 2: {
744      // VE: smoothed top
745      const vals = [avg3(X, A, B), avg3(A, B, C), avg3(B, C, D), avg3(C, D, E)];
746      for (let y = 0; y < 4; y++) for (let x = 0; x < 4; x++) set(x, y, vals[x]!);
747      return;
748    }
749    case 3: {
750      // HE: smoothed left
751      const rows = [avg3(X, I, J), avg3(I, J, K), avg3(J, K, L), avg3(K, L, L)];
752      for (let y = 0; y < 4; y++) for (let x = 0; x < 4; x++) set(x, y, rows[y]!);
753      return;
754    }
755    case 4: // RD
756      set(0, 3, avg3(J, K, L));
757      set(1, 3, avg3(I, J, K)), set(0, 2, avg3(I, J, K));
758      set(2, 3, avg3(X, I, J)), set(1, 2, avg3(X, I, J)), set(0, 1, avg3(X, I, J));
759      for (const [x, y] of [[3, 3], [2, 2], [1, 1], [0, 0]]) set(x!, y!, avg3(A, X, I));
760      for (const [x, y] of [[3, 2], [2, 1], [1, 0]]) set(x!, y!, avg3(B, A, X));
761      set(3, 1, avg3(C, B, A)), set(2, 0, avg3(C, B, A));
762      set(3, 0, avg3(D, C, B));
763      return;
764    case 5: // VR
765      set(0, 0, avg2(X, A)), set(1, 2, avg2(X, A));
766      set(1, 0, avg2(A, B)), set(2, 2, avg2(A, B));
767      set(2, 0, avg2(B, C)), set(3, 2, avg2(B, C));
768      set(3, 0, avg2(C, D));
769      set(0, 3, avg3(K, J, I));
770      set(0, 2, avg3(J, I, X));
771      set(0, 1, avg3(I, X, A)), set(1, 3, avg3(I, X, A));
772      set(1, 1, avg3(X, A, B)), set(2, 3, avg3(X, A, B));
773      set(2, 1, avg3(A, B, C)), set(3, 3, avg3(A, B, C));
774      set(3, 1, avg3(B, C, D));
775      return;
776    case 6: // LD
777      set(0, 0, avg3(A, B, C));
778      set(1, 0, avg3(B, C, D)), set(0, 1, avg3(B, C, D));
779      for (const [x, y] of [[2, 0], [1, 1], [0, 2]]) set(x!, y!, avg3(C, D, E));
780      for (const [x, y] of [[3, 0], [2, 1], [1, 2], [0, 3]]) set(x!, y!, avg3(D, E, F));
781      for (const [x, y] of [[3, 1], [2, 2], [1, 3]]) set(x!, y!, avg3(E, F, G));
782      set(3, 2, avg3(F, G, H)), set(2, 3, avg3(F, G, H));
783      set(3, 3, avg3(G, H, H));
784      return;
785    case 7: // VL
786      set(0, 0, avg2(A, B));
787      set(1, 0, avg2(B, C)), set(0, 2, avg2(B, C));
788      set(2, 0, avg2(C, D)), set(1, 2, avg2(C, D));
789      set(3, 0, avg2(D, E)), set(2, 2, avg2(D, E));
790      set(0, 1, avg3(A, B, C));
791      set(1, 1, avg3(B, C, D)), set(0, 3, avg3(B, C, D));
792      set(2, 1, avg3(C, D, E)), set(1, 3, avg3(C, D, E));
793      set(3, 1, avg3(D, E, F)), set(2, 3, avg3(D, E, F));
794      set(3, 2, avg3(E, F, G));
795      set(3, 3, avg3(F, G, H));
796      return;
797    case 8: // HD
798      set(0, 0, avg2(I, X)), set(2, 1, avg2(I, X));
799      set(0, 1, avg2(J, I)), set(2, 2, avg2(J, I));
800      set(0, 2, avg2(K, J)), set(2, 3, avg2(K, J));
801      set(0, 3, avg2(L, K));
802      set(3, 0, avg3(A, B, C));
803      set(2, 0, avg3(X, A, B));
804      set(1, 0, avg3(I, X, A)), set(3, 1, avg3(I, X, A));
805      set(1, 1, avg3(J, I, X)), set(3, 2, avg3(J, I, X));
806      set(1, 2, avg3(K, J, I)), set(3, 3, avg3(K, J, I));
807      set(1, 3, avg3(L, K, J));
808      return;
809    default: // 9: HU
810      set(0, 0, avg2(I, J));
811      set(2, 0, avg2(J, K)), set(0, 1, avg2(J, K));
812      set(2, 1, avg2(K, L)), set(0, 2, avg2(K, L));
813      set(1, 0, avg3(I, J, K));
814      set(3, 0, avg3(J, K, L)), set(1, 1, avg3(J, K, L));
815      set(3, 1, avg3(K, L, L)), set(1, 2, avg3(K, L, L));
816      for (const [x, y] of [[3, 2], [2, 2], [0, 3], [1, 3], [2, 3], [3, 3]]) set(x!, y!, L);
817      return;
818  }
819}
820
821// Loop filter primitives (RFC 6386 section 15, libwebp dsp/dec.c).
822
823function doFilter2(b: Uint8Array, p: number, step: number) {
824  const p1 = b[p - 2 * step]!, p0 = b[p - step]!, q0 = b[p]!, q1 = b[p + step]!;
825  const a = 3 * (q0 - p0) + sclip1(p1 - q1);
826  const a1 = sclip2((a + 4) >> 3);
827  const a2 = sclip2((a + 3) >> 3);
828  b[p - step] = clip1(p0 + a2);
829  b[p] = clip1(q0 - a1);
830}
831
832function doFilter4(b: Uint8Array, p: number, step: number) {
833  const p1 = b[p - 2 * step]!, p0 = b[p - step]!, q0 = b[p]!, q1 = b[p + step]!;
834  const a = 3 * (q0 - p0);
835  const a1 = sclip2((a + 4) >> 3);
836  const a2 = sclip2((a + 3) >> 3);
837  const a3 = (a1 + 1) >> 1;
838  b[p - 2 * step] = clip1(p1 + a3);
839  b[p - step] = clip1(p0 + a2);
840  b[p] = clip1(q0 - a1);
841  b[p + step] = clip1(q1 - a3);
842}
843
844function doFilter6(b: Uint8Array, p: number, step: number) {
845  const p2 = b[p - 3 * step]!, p1 = b[p - 2 * step]!, p0 = b[p - step]!;
846  const q0 = b[p]!, q1 = b[p + step]!, q2 = b[p + 2 * step]!;
847  const a = sclip1(3 * (q0 - p0) + sclip1(p1 - q1));
848  const a1 = (27 * a + 63) >> 7;
849  const a2 = (18 * a + 63) >> 7;
850  const a3 = (9 * a + 63) >> 7;
851  b[p - 3 * step] = clip1(p2 + a3);
852  b[p - 2 * step] = clip1(p1 + a2);
853  b[p - step] = clip1(p0 + a1);
854  b[p] = clip1(q0 - a1);
855  b[p + step] = clip1(q1 - a2);
856  b[p + 2 * step] = clip1(q2 - a3);
857}
858
859const hev = (b: Uint8Array, p: number, step: number, thresh: number) =>
860  Math.abs(b[p - 2 * step]! - b[p - step]!) > thresh || Math.abs(b[p + step]! - b[p]!) > thresh;
861
862const needsFilter = (b: Uint8Array, p: number, step: number, t: number) =>
863  4 * Math.abs(b[p - step]! - b[p]!) + Math.abs(b[p - 2 * step]! - b[p + step]!) <= t;
864
865function needsFilter2(b: Uint8Array, p: number, step: number, t: number, it: number): boolean {
866  const p3 = b[p - 4 * step]!, p2 = b[p - 3 * step]!, p1 = b[p - 2 * step]!, p0 = b[p - step]!;
867  const q0 = b[p]!, q1 = b[p + step]!, q2 = b[p + 2 * step]!, q3 = b[p + 3 * step]!;
868  if (4 * Math.abs(p0 - q0) + Math.abs(p1 - q1) > t) return false;
869  return (
870    Math.abs(p3 - p2) <= it &&
871    Math.abs(p2 - p1) <= it &&
872    Math.abs(p1 - p0) <= it &&
873    Math.abs(q3 - q2) <= it &&
874    Math.abs(q2 - q1) <= it &&
875    Math.abs(q1 - q0) <= it
876  );
877}
878
879/** Across a horizontal edge at `p` (16 pixels along the row). */
880function simpleV16(b: Uint8Array, p: number, stride: number, thresh: number) {
881  const t2 = 2 * thresh + 1;
882  for (let i = 0; i < 16; i++) if (needsFilter(b, p + i, stride, t2)) doFilter2(b, p + i, stride);
883}
884
885/** Across a vertical edge at `p` (16 pixels down the column). */
886function simpleH16(b: Uint8Array, p: number, stride: number, thresh: number) {
887  const t2 = 2 * thresh + 1;
888  for (let i = 0; i < 16; i++) if (needsFilter(b, p + i * stride, 1, t2)) doFilter2(b, p + i * stride, 1);
889}
890
891function loop26(b: Uint8Array, p: number, hstride: number, vstride: number, size: number, thresh: number, ithresh: number, hevThresh: number) {
892  const t2 = 2 * thresh + 1;
893  for (let i = 0; i < size; i++, p += vstride) {
894    if (needsFilter2(b, p, hstride, t2, ithresh)) {
895      if (hev(b, p, hstride, hevThresh)) doFilter2(b, p, hstride);
896      else doFilter6(b, p, hstride);
897    }
898  }
899}
900
901function loop24(b: Uint8Array, p: number, hstride: number, vstride: number, size: number, thresh: number, ithresh: number, hevThresh: number) {
902  const t2 = 2 * thresh + 1;
903  for (let i = 0; i < size; i++, p += vstride) {
904    if (needsFilter2(b, p, hstride, t2, ithresh)) {
905      if (hev(b, p, hstride, hevThresh)) doFilter2(b, p, hstride);
906      else doFilter4(b, p, hstride);
907    }
908  }
909}
910
911// YUV to RGB, libwebp's fixed point (BT.601, limited range).
912const multHi = (v: number, c: number) => (v * c) >> 8;
913const clip8 = (v: number) => ((v & ~16383) === 0 ? v >> 6 : v < 0 ? 0 : 255);
914
915function putRgb(out: Uint8Array, o: number, y: number, u: number, v: number) {
916  out[o] = clip8(multHi(y, 19077) + multHi(v, 26149) - 14234);
917  out[o + 1] = clip8(multHi(y, 19077) - multHi(u, 6419) - multHi(v, 13320) + 8708);
918  out[o + 2] = clip8(multHi(y, 19077) + multHi(u, 33050) - 17685);
919}
920
921/**
922 * One or two output rows from one row of chroma above and one below
923 * (libwebp's UpsampleRgbaLinePair): each chroma sample is weighted 9-3-3-1
924 * by distance, the "fancy" upsampling libwebp does by default.
925 */
926function upsamplePair(
927  f: Vp8Frame,
928  out: Uint8Array,
929  topRow: number,
930  bottomRow: number,
931  topUv: number,
932  curUv: number,
933) {
934  const w = f.width;
935  const Y = f.y, U = f.u, V = f.v;
936  const ty = topRow * f.yStride;
937  const by = bottomRow * f.yStride;
938  const tu = topUv * f.uvStride;
939  const cu = curUv * f.uvStride;
940  const to = topRow * w * 4;
941  const bo = bottomRow * w * 4;
942  const hasBottom = bottomRow >= 0;
943  const last = (w - 1) >> 1;
944
945  let tlU = U[tu]!, tlV = V[tu]!;
946  let lU = U[cu]!, lV = V[cu]!;
947  putRgb(out, to, Y[ty]!, (3 * tlU + lU + 2) >> 2, (3 * tlV + lV + 2) >> 2);
948  if (hasBottom) putRgb(out, bo, Y[by]!, (3 * lU + tlU + 2) >> 2, (3 * lV + tlV + 2) >> 2);
949  for (let x = 1; x <= last; x++) {
950    const tU = U[tu + x]!, tV = V[tu + x]!;
951    const cU = U[cu + x]!, cV = V[cu + x]!;
952    const avgU = tlU + tU + lU + cU + 8;
953    const avgV = tlV + tV + lV + cV + 8;
954    const d12U = (avgU + 2 * (tU + lU)) >> 3, d12V = (avgV + 2 * (tV + lV)) >> 3;
955    const d03U = (avgU + 2 * (tlU + cU)) >> 3, d03V = (avgV + 2 * (tlV + cV)) >> 3;
956    putRgb(out, to + (2 * x - 1) * 4, Y[ty + 2 * x - 1]!, (d12U + tlU) >> 1, (d12V + tlV) >> 1);
957    putRgb(out, to + 2 * x * 4, Y[ty + 2 * x]!, (d03U + tU) >> 1, (d03V + tV) >> 1);
958    if (hasBottom) {
959      putRgb(out, bo + (2 * x - 1) * 4, Y[by + 2 * x - 1]!, (d03U + lU) >> 1, (d03V + lV) >> 1);
960      putRgb(out, bo + 2 * x * 4, Y[by + 2 * x]!, (d12U + cU) >> 1, (d12V + cV) >> 1);
961    }
962    tlU = tU;
963    tlV = tV;
964    lU = cU;
965    lV = cV;
966  }
967  if (!(w & 1)) {
968    putRgb(out, to + (w - 1) * 4, Y[ty + w - 1]!, (3 * tlU + lU + 2) >> 2, (3 * tlV + lV + 2) >> 2);
969    if (hasBottom) {
970      putRgb(out, bo + (w - 1) * 4, Y[by + w - 1]!, (3 * lU + tlU + 2) >> 2, (3 * lV + tlV + 2) >> 2);
971    }
972  }
973}
974
975/** The frame as RGBA, alpha 255 (libwebp's EmitFancyRGB over the whole frame). */
976export function vp8ToRgba(f: Vp8Frame): Uint8Array {
977  const { width: w, height: h } = f;
978  const out = new Uint8Array(w * h * 4);
979  upsamplePair(f, out, 0, -1, 0, 0);
980  let y = 0;
981  let uv = 0;
982  for (; y + 2 < h; y += 2) {
983    upsamplePair(f, out, y + 1, y + 2, uv, uv + 1);
984    uv++;
985  }
986  if (!(h & 1)) upsamplePair(f, out, h - 1, -1, uv, uv);
987  for (let i = 3; i < out.length; i += 4) out[i] = 255;
988
989  return out;
990}
991

1// WebP lossless (VP8L, RFC 9649) decoding, to ARGB words. Also decodes the
2// headerless image stream a lossy WebP's alpha chunk carries. Follows
3// libwebp's decoder (vp8l_dec.c, lossless.c), whose behaviour at the edges
4// (first row and column predictors, colour-cache timing, palette tail) is
5// the format's.
6
7import { CODE_LENGTH_CODE_ORDER, CODE_TO_PLANE } from "./webp-tables";
8
9const NUM_LITERAL = 256;
10const NUM_LENGTH = 24;
11/** Alphabet sizes: green (with lengths), red, blue, alpha, distance. */
12const ALPHABET = [NUM_LITERAL + NUM_LENGTH, NUM_LITERAL, NUM_LITERAL, NUM_LITERAL, 40];
13const COLOR_HASH = 0x1e35a7bd;
14
15/** Bits least significant first; reads past the end are zeros. */
16export class LsbBits {
17  readonly data: Uint8Array;
18  pos: number;
19  buf = 0;
20  cnt = 0;
21
22  constructor(data: Uint8Array, pos = 0) {
23    this.data = data;
24    this.pos = pos;
25  }
26
27  fill() {
28    const data = this.data;
29    while (this.cnt <= 24) {
30      this.buf |= (this.pos < data.length ? data[this.pos]! : 0) << this.cnt;
31      this.pos++;
32      this.cnt += 8;
33    }
34  }
35
36  read(n: number): number {
37    if (n === 0) return 0;
38    if (this.cnt < n) this.fill();
39    const v = this.buf & ((1 << n) - 1);
40    this.buf >>>= n;
41    this.cnt -= n;
42    return v;
43  }
44
45  /** True once more bits were taken than the data holds. */
46  overrun(): boolean {
47    return this.pos - (this.cnt >> 3) > this.data.length;
48  }
49}
50
51/** A canonical prefix code: an 8-bit lookup for short codes, counting for long ones. */
52type Code = {
53  /** The symbol of a one-symbol code, which takes no bits; else -1. */
54  single: number;
55  /** By the next 8 bits: `(length << 16) | symbol` for codes up to 8 bits, else 0. */
56  root: Int32Array;
57  count: Int32Array;
58  first: Int32Array;
59  index: Int32Array;
60  sorted: Int32Array;
61};
62
63function buildCode(lengths: Uint8Array): Code {
64  const count = new Int32Array(16);
65  let used = 0;
66  let last = 0;
67  for (let s = 0; s < lengths.length; s++) {
68    if (lengths[s]) {
69      count[lengths[s]!]!++;
70      used++;
71      last = s;
72    }
73  }
74  if (used === 0) throw new Error("empty WebP prefix code");
75  const empty = new Int32Array(0);
76  if (used === 1) {
77    return { single: last, root: empty, count, first: empty, index: empty, sorted: empty };
78  }
79  const first = new Int32Array(16);
80  const index = new Int32Array(16);
81  for (let len = 1, code = 0, idx = 0; len <= 15; len++) {
82    first[len] = code;
83    index[len] = idx;
84    if (code + count[len]! > 1 << len) throw new Error("bad WebP prefix code");
85    code = (code + count[len]!) << 1;
86    idx += count[len]!;
87  }
88  const sorted = new Int32Array(used);
89  const next = index.slice();
90  for (let s = 0; s < lengths.length; s++) if (lengths[s]) sorted[next[lengths[s]!]!++] = s;
91
92  const root = new Int32Array(256);
93  for (let len = 1; len <= 8; len++) {
94    for (let k = 0; k < count[len]!; k++) {
95      let code = first[len]! + k;
96      let reversed = 0;
97      for (let i = 0; i < len; i++) {
98        reversed = (reversed << 1) | (code & 1);
99        code >>= 1;
100      }
101      for (let j = reversed; j < 256; j += 1 << len) root[j] = (len << 16) | sorted[index[len]! + k]!;
102    }
103  }
104
105  return { single: -1, root, count, first, index, sorted };
106}
107
108function readSymbol(code: Code, br: LsbBits): number {
109  if (code.single >= 0) return code.single;
110  if (br.cnt < 15) br.fill();
111  const e = code.root[br.buf & 255]!;
112  if (e) {
113    const len = e >>> 16;
114    br.buf >>>= len;
115    br.cnt -= len;
116    return e & 0xffff;
117  }
118  // Longer than 8 bits: the code read most significant bit first.
119  let c = 0;
120  for (let i = 0; i < 8; i++) c = (c << 1) | ((br.buf >>> i) & 1);
121  for (let len = 9; len <= 15; len++) {
122    c = (c << 1) | ((br.buf >>> (len - 1)) & 1);
123    const off = c - code.first[len]!;
124    if (off >= 0 && off < code.count[len]!) {
125      br.buf >>>= len;
126      br.cnt -= len;
127      return code.sorted[code.index[len]! + off]!;
128    }
129  }
130  throw new Error("bad WebP prefix code");
131}
132
133/** One prefix code from the stream (simple or normal form). */
134function readCode(br: LsbBits, alphabet: number): Code {
135  const lengths = new Uint8Array(alphabet);
136  if (br.read(1)) {
137    // Simple: one or two symbols, each one bit long.
138    const two = br.read(1);
139    const s0 = br.read(br.read(1) ? 8 : 1);
140    if (s0 >= alphabet) throw new Error("bad WebP prefix code");
141    lengths[s0] = 1;
142    if (two) {
143      const s1 = br.read(8);
144      if (s1 >= alphabet) throw new Error("bad WebP prefix code");
145      lengths[s1] = 1;
146    }
147  } else {
148    const clLengths = new Uint8Array(19);
149    const n = br.read(4) + 4;
150    for (let i = 0; i < n; i++) clLengths[CODE_LENGTH_CODE_ORDER[i]!] = br.read(3);
151    const cl = buildCode(clLengths);
152    let max = alphabet;
153    if (br.read(1)) {
154      max = 2 + br.read(2 + 2 * br.read(3));
155      if (max > alphabet) throw new Error("bad WebP code lengths");
156    }
157    let prev = 8;
158    for (let s = 0; s < alphabet; ) {
159      if (max-- === 0) break;
160      const len = readSymbol(cl, br);
161      if (len < 16) {
162        lengths[s++] = len;
163        if (len !== 0) prev = len;
164        continue;
165      }
166      const repeat = len === 16 ? 3 + br.read(2) : len === 17 ? 3 + br.read(3) : 11 + br.read(7);
167      if (s + repeat > alphabet) throw new Error("bad WebP code lengths");
168      lengths.fill(len === 16 ? prev : 0, s, s + repeat);
169      s += repeat;
170    }
171  }
172  if (br.overrun()) throw new Error("WebP data ends early");
173
174  return buildCode(lengths);
175}
176
177const subSample = (size: number, bits: number) => (size + (1 << bits) - 1) >> bits;
178
179/** Length and distance values: a prefix symbol plus extra bits. */
180function prefixValue(symbol: number, br: LsbBits): number {
181  if (symbol < 4) return symbol + 1;
182  const extra = (symbol - 2) >> 1;
183  return ((2 + (symbol & 1)) << extra) + br.read(extra) + 1;
184}
185
186function planeToDistance(width: number, code: number): number {
187  if (code > 120) return code - 120;
188  const d = CODE_TO_PLANE[code - 1]!;
189  const dist = (d >> 4) * width + (8 - (d & 15));
190
191  return dist >= 1 ? dist : 1;
192}
193
194type Transform = { type: number; bits: number; xsize: number; data: Uint32Array };
195
196/**
197 * An entropy-coded image of `width × height` pixels (`level0`: the main
198 * image, with transforms and meta prefix codes). Returns its pixels, still
199 * transformed, and the transforms to undo, in reading order.
200 */
201function imageStream(
202  br: LsbBits,
203  xsize: number,
204  ysize: number,
205  level0: boolean,
206  maxPixels: number,
207): { pixels: Uint32Array; transforms: Transform[] } {
208  const transforms: Transform[] = [];
209  let width = xsize;
210  if (level0) {
211    let seen = 0;
212    while (br.read(1)) {
213      const type = br.read(2);
214      if (seen & (1 << type)) throw new Error("repeated WebP transform");
215      seen |= 1 << type;
216      if (type === 0 || type === 1) {
217        const bits = br.read(3) + 2;
218        const data = imageStream(br, subSample(width, bits), subSample(ysize, bits), false, maxPixels).pixels;
219        transforms.push({ type, bits, xsize: width, data });
220      } else if (type === 3) {
221        const colors = br.read(8) + 1;
222        const bits = colors > 16 ? 0 : colors > 4 ? 1 : colors > 2 ? 2 : 3;
223        const table = imageStream(br, colors, 1, false, maxPixels).pixels;
224        // Delta-coded per channel; the rest of the 2^(8 >> bits) entries are zero.
225        const map = new Uint32Array(1 << (8 >> bits));
226        let prev = 0;
227        for (let i = 0; i < colors && i < map.length; i++) {
228          prev = addPixels(table[i]!, prev);
229          map[i] = prev;
230        }
231        transforms.push({ type, bits, xsize: width, data: map });
232        width = subSample(width, bits);
233      } else {
234        transforms.push({ type, bits: 0, xsize: width, data: new Uint32Array(0) });
235      }
236    }
237  }
238
239  let cacheBits = 0;
240  if (br.read(1)) {
241    cacheBits = br.read(4);
242    if (cacheBits < 1 || cacheBits > 11) throw new Error("bad WebP colour cache");
243  }
244
245  // Meta prefix codes: which group of codes each tile uses.
246  let metaBits = 0;
247  let metaWidth = 0;
248  let meta: Uint32Array | undefined;
249  let groupCount = 1;
250  if (level0 && br.read(1)) {
251    metaBits = br.read(3) + 2;
252    metaWidth = subSample(width, metaBits);
253    meta = imageStream(br, metaWidth, subSample(ysize, metaBits), false, maxPixels).pixels;
254    for (let i = 0; i < meta.length; i++) {
255      meta[i] = (meta[i]! >> 8) & 0xffff;
256      if (meta[i]! >= groupCount) groupCount = meta[i]! + 1;
257    }
258  }
259  const used = new Uint8Array(groupCount);
260  if (meta) for (const g of meta) used[g] = 1;
261  else used[0] = 1;
262  const groups: Code[][] = new Array(groupCount);
263  for (let g = 0; g < groupCount; g++) {
264    const codes: Code[] = [];
265    for (let j = 0; j < 5; j++) {
266      codes.push(readCode(br, ALPHABET[j]! + (j === 0 && cacheBits ? 1 << cacheBits : 0)));
267    }
268    if (used[g]) groups[g] = codes;
269  }
270
271  if (width * ysize > maxPixels) throw new Error("WebP image too large");
272  const pixels = imageData(br, width, ysize, groups, meta, metaBits, metaWidth, cacheBits);
273
274  return { pixels, transforms };
275}
276
277function imageData(
278  br: LsbBits,
279  width: number,
280  height: number,
281  groups: Code[][],
282  meta: Uint32Array | undefined,
283  metaBits: number,
284  metaWidth: number,
285  cacheBits: number,
286): Uint32Array {
287  const total = width * height;
288  const out = new Uint32Array(total);
289  const cache = cacheBits ? new Uint32Array(1 << cacheBits) : undefined;
290  const shift = 32 - cacheBits;
291  const mask = metaBits ? (1 << metaBits) - 1 : -1;
292  const groupAt = (x: number, y: number) =>
293    meta ? groups[meta[(y >> metaBits) * metaWidth + (x >> metaBits)]!]! : groups[0]!;
294
295  let x = 0;
296  let y = 0;
297  let pos = 0;
298  let cached = 0;
299  let group = groupAt(0, 0);
300  while (pos < total) {
301    if ((x & mask) === 0) group = groupAt(x, y);
302    const green = readSymbol(group[0]!, br);
303    if (green < NUM_LITERAL) {
304      const red = readSymbol(group[1]!, br);
305      const blue = readSymbol(group[2]!, br);
306      const alpha = readSymbol(group[3]!, br);
307      out[pos++] = ((alpha << 24) | (red << 16) | (green << 8) | blue) >>> 0;
308      if (++x >= width) {
309        x = 0;
310        y++;
311      }
312    } else if (green < NUM_LITERAL + NUM_LENGTH) {
313      const length = prefixValue(green - NUM_LITERAL, br);
314      const dist = planeToDistance(width, prefixValue(readSymbol(group[4]!, br), br));
315      if (dist > pos || length > total - pos) throw new Error("bad WebP back-reference");
316      for (let k = 0; k < length; k++) out[pos + k] = out[pos + k - dist]!;
317      pos += length;
318      x += length;
319      while (x >= width) {
320        x -= width;
321        y++;
322      }
323      if (x & mask && pos < total) group = groupAt(x, y);
324    } else {
325      if (cache === undefined) throw new Error("bad WebP colour cache code");
326      while (cached < pos) {
327        const v = out[cached++]!;
328        cache[Math.imul(v, COLOR_HASH) >>> shift] = v;
329      }
330      const key = green - NUM_LITERAL - NUM_LENGTH;
331      if (key >= cache.length) throw new Error("bad WebP colour cache code");
332      out[pos++] = cache[key]!;
333      if (++x >= width) {
334        x = 0;
335        y++;
336      }
337    }
338    if (br.overrun()) throw new Error("WebP data ends early");
339  }
340
341  return out;
342}
343
344/** Per-channel sum mod 256 of two ARGB words. */
345function addPixels(a: number, b: number): number {
346  const ag = ((a & 0xff00ff00) + (b & 0xff00ff00)) & 0xff00ff00;
347  const rb = ((a & 0x00ff00ff) + (b & 0x00ff00ff)) & 0x00ff00ff;
348
349  return (ag | rb) >>> 0;
350}
351
352const average2 = (a: number, b: number) => ((((a ^ b) & 0xfefefefe) >>> 1) + ((a & b) >>> 0)) >>> 0;
353
354const clip255 = (v: number) => (v < 0 ? 0 : v > 255 ? 255 : v);
355
356function select(t: number, l: number, tl: number): number {
357  let d = 0;
358  for (let s = 0; s < 32; s += 8) {
359    const a = (t >>> s) & 255, b = (l >>> s) & 255, c = (tl >>> s) & 255;
360    d += Math.abs(b - c) - Math.abs(a - c);
361  }
362
363  return d <= 0 ? t : l;
364}
365
366function addSubtractFull(l: number, t: number, tl: number): number {
367  let out = 0;
368  for (let s = 0; s < 32; s += 8) {
369    out |= clip255(((l >>> s) & 255) + ((t >>> s) & 255) - ((tl >>> s) & 255)) << s;
370  }
371
372  return out >>> 0;
373}
374
375function addSubtractHalf(l: number, t: number, tl: number): number {
376  const ave = average2(l, t);
377  let out = 0;
378  for (let s = 0; s < 32; s += 8) {
379    const a = (ave >>> s) & 255;
380    out |= clip255(a + Math.trunc((a - ((tl >>> s) & 255)) / 2)) << s;
381  }
382
383  return out >>> 0;
384}
385
386function predict(mode: number, px: Uint32Array, i: number, w: number): number {
387  const L = px[i - 1]!, T = px[i - w]!, TR = px[i - w + 1]!, TL = px[i - w - 1]!;
388  switch (mode) {
389    case 0:
390      return 0xff000000;
391    case 1:
392      return L;
393    case 2:
394      return T;
395    case 3:
396      return TR;
397    case 4:
398      return TL;
399    case 5:
400      return average2(average2(L, TR), T);
401    case 6:
402      return average2(L, TL);
403    case 7:
404      return average2(L, T);
405    case 8:
406      return average2(TL, T);
407    case 9:
408      return average2(T, TR);
409    case 10:
410      return average2(average2(L, TL), average2(T, TR));
411    case 11:
412      return select(T, L, TL);
413    case 12:
414      return addSubtractFull(L, T, TL);
415    case 13:
416      return addSubtractHalf(L, T, TL);
417    default:
418      return 0xff000000; // 14 and 15 are unused; libwebp predicts black
419  }
420}
421
422/** Undoes the transforms in place where it can; returns the final pixels. */
423function undo(pixels: Uint32Array, transforms: Transform[], height: number): Uint32Array {
424  let px = pixels;
425  for (let t = transforms.length - 1; t >= 0; t--) {
426    const { type, bits, xsize: w, data } = transforms[t]!;
427    if (type === 0) {
428      px[0] = addPixels(px[0]!, 0xff000000);
429      for (let x = 1; x < w; x++) px[x] = addPixels(px[x]!, px[x - 1]!);
430      const tiles = subSample(w, bits);
431      for (let y = 1; y < height; y++) {
432        const row = y * w;
433        px[row] = addPixels(px[row]!, px[row - w]!);
434        const modes = (y >> bits) * tiles;
435        for (let x = 1; x < w; x++) {
436          const mode = (data[modes + (x >> bits)]! >> 8) & 15;
437          px[row + x] = addPixels(px[row + x]!, predict(mode, px, row + x, w));
438        }
439      }
440    } else if (type === 1) {
441      const tiles = subSample(w, bits);
442      for (let y = 0; y < height; y++) {
443        for (let x = 0; x < w; x++) {
444          const code = data[(y >> bits) * tiles + (x >> bits)]!;
445          const g2r = (code << 24) >> 24, g2b = (code << 16) >> 24, r2b = (code << 8) >> 24;
446          const i = y * w + x;
447          const argb = px[i]!;
448          const green = (argb << 16) >> 24;
449          const red = (((argb >>> 16) & 255) + ((g2r * green) >> 5)) & 255;
450          let blue = (argb & 255) + ((g2b * green) >> 5);
451          blue = (blue + ((r2b * ((red << 24) >> 24)) >> 5)) & 255;
452          px[i] = ((argb & 0xff00ff00) | (red << 16) | blue) >>> 0;
453        }
454      }
455    } else if (type === 2) {
456      for (let i = 0; i < px.length; i++) {
457        const argb = px[i]!;
458        const green = (argb >>> 8) & 255;
459        const rb = ((argb & 0x00ff00ff) + ((green << 16) | green)) & 0x00ff00ff;
460        px[i] = ((argb & 0xff00ff00) | rb) >>> 0;
461      }
462    } else {
463      const packed = subSample(w, bits);
464      const out = new Uint32Array(w * height);
465      const per = 8 >> bits;
466      const countMask = (1 << bits) - 1;
467      const bitMask = (1 << per) - 1;
468      for (let y = 0; y < height; y++) {
469        let src = y * packed;
470        let word = 0;
471        for (let x = 0; x < w; x++) {
472          if ((x & countMask) === 0) word = (px[src++]! >> 8) & 255;
473          out[y * w + x] = data[word & bitMask]!;
474          word >>= per;
475        }
476      }
477      px = out;
478    }
479  }
480
481  return px;
482}
483
484/** A complete VP8L bitstream (the `VP8L` chunk's payload) to ARGB words. */
485export function decodeVp8l(
486  data: Uint8Array,
487  maxPixels: number,
488): { width: number; height: number; argb: Uint32Array } {
489  if (data[0] !== 0x2f) throw new Error("not a WebP lossless stream");
490  const br = new LsbBits(data, 1);
491  const width = br.read(14) + 1;
492  const height = br.read(14) + 1;
493  br.read(1); // alpha_is_used: a hint only
494  if (br.read(3) !== 0) throw new Error("unknown WebP lossless version");
495  if (width * height > maxPixels) throw new Error(`${width}×${height} is too large to preview`);
496  const { pixels, transforms } = imageStream(br, width, height, true, maxPixels);
497
498  return { width, height, argb: undo(pixels, transforms, height) };
499}
500
501/** A headerless VP8L image stream of known size (an ALPH chunk's lossless alpha). */
502export function decodeVp8lStream(data: Uint8Array, width: number, height: number, maxPixels: number): Uint32Array {
503  const br = new LsbBits(data, 0);
504  const { pixels, transforms } = imageStream(br, width, height, true, maxPixels);
505
506  return undo(pixels, transforms, height);
507}
508