Record your screen, ship a demo. Free and open-source, GPU-accelerated, no watermarks, no subscriptions. Windows, macOS, Linux. Actively maintained.
TypeScript cross-platformelectronffmpegopen-sourceproduct-demorustscreen-capturescreen-recorderscreen-recordingscreen-studioscreencastspeech-to-texttypescriptvideo-editingvideo-editorwaylandwgpuwhisper
//! Native GIF export pipeline.
//!
//! This is now the ONLY GIF path: the renderer-side `gif.js` exporter it
//! originally sat beside — and the `NATIVE_GIF_EXPORT_ENABLED` flag that
//! chose between them — were deleted when GIF moved over for good. Same
//! compositor as the MP4 path (D3D11 on Windows, Metal on macOS), but the
//! per-frame output is a 256-color GIF89a file written from scratch in
//! pure Rust.
//!
//! ## Why pure Rust, not ffmpeg
//!
//! The compositor's ffmpeg bindings are `avformat` / `avcodec` / `avutil` /
//! `swscale` / `swresample` only — **no `libavfilter`**
//! (see `crates/compositor/Cargo.toml` and `crates/compositor/build.rs`).
//! ffmpeg's `palettegen` + `paletteuse` live in `libavfilter` and aren't
//! buildable here, and ffmpeg's `gif` codec in libavcodec still expects
//! pre-quantized `PAL8` frames — it refuses to do the quantize step
//! itself. So the "ffmpeg GIF muxer" route would have been a
//! write-our-own-palette-and-LZW path either way. The CPU readback
//! (the dominant per-frame cost — see the bench in
//! `crates/poc-d3d/src/bench.rs`) already lands us on CPU regardless, so
//! skipping a swscale round-trip and writing the format directly in this
//! crate costs no extra dependency, stays inside the LGPL-only ffmpeg
//! pin we already have, and keeps the readback/quantize/LZW layers
//! auditable in one file.
//!
//! ## What's in this file
//!
//! - `export_gif` — the orchestrator. Drives `pipeline::walk_composited_timeline`,
//! the SAME clip walk the MP4 exporter uses, so clip iteration, speed
//! segments and output-time decoder advancement have exactly one
//! definition. Per output frame the walk composes, then this module does
//! `Compositor::readback_direct` → palette on the export thread, hands the
//! frame to a `FrameEncoder` worker for the mapping (optional fused
//! Floyd-Steinberg) and LZW, and writes the results back in order with
//! `GifWriter::write_frame`. Reports the same `GifStats` shape the MP4
//! `pipeline::Stats` returns.
//!
//! It previously ran its own loop over the live-preview `Player`, stepping
//! one SOURCE frame per OUTPUT frame — which made a 30 s/60 fps recording
//! export as 6 s of content stretched over 30 s, and could not decode files
//! the MP4 path handled. `tests/export_timing.rs` pins the behaviour.
//! - `GifWriter` — GIF89a format writer: header, optional Netscape 2.0
//! loop extension, per-frame Graphics Control Extension + Image
//! Descriptor + LZW image data, trailer. Pure std `Write`.
//! - `lzw_compress` — GIF's LZW variant. Codes 0..255 are the palette;
//! code 256 = clear, 257 = EOI; codes 258+ are the string table.
//! Packed LSB-first into the output byte stream. Code size starts at
//! `min_code_size + 1` (9 for 8-bit palette) and grows to 12 as the
//! table fills; when the table hits 4096, a clear code resets it.
//! - `build_palette_median_cut` — 256-color palette via median-cut on
//! the frame's color histogram. Cheap enough at the GIF frame sizes
//! we ship (≤ 480p) and good enough for screen content; the
//! requantize-every-30-frames cadence trades a small per-frame
//! color drift for keeping the palette adapted to the timeline.
//! - `map_to_indices` — exact nearest-color search over the palette
//! sorted by red (`SortedPalette`), which prunes most of the 256
//! entries per pixel.
//! - `map_to_indices_dithered` — the same search with Floyd-Steinberg
//! error diffusion fused into it (alpha left as the readback emitted
//! it), two row-buffers so the working set is O(width) per row. Fused
//! because the error worth diffusing is `pixel - palette[chosen]`,
//! which doesn't exist until the entry has been picked.
//!
//! ## Honest signal
//!
//! The wall-time is the only honest signal here: GIF's quality is a
//! user-visible trade-off the user already accepted when they picked
//! the format, and 256-color quantization dominates per-frame CPU. The
//! bench in `crates/poc-d3d/src/bench.rs` is the only check that
//! catches a "this is fine in micro-benchmarks but the readback kills
//! the loop" regression. See the `Native GIF export — initial bench`
//! section of `technical-documentation/engineering/rendering-performance.md`.
use crate::compositor::Compositor;
use crate::config::Cfg;
use crate::d3d::Gpu;
use crate::export_control::{with_staged_output, ExportControl};
use crate::pipeline::{ClipSource, Decoder};
use crate::timeline_walk::walk_composited_timeline;
use anyhow::{anyhow, bail, Context, Result};
use std::collections::{BTreeMap, HashMap};
use std::fs::File;
use std::io::{BufWriter, Write};
use std::path::Path;
use std::sync::{mpsc, Arc, Mutex};
use std::time::Instant;
/// Default output width/height. GIF is 8-bit indexed; smaller frames look
/// better than 1080p under the same palette budget. The user-facing
/// `ExportDialog` can request a different size via `GifExportParams`.
pub const DEFAULT_GIF_WIDTH: u32 = 854;
pub const DEFAULT_GIF_HEIGHT: u32 = 480;
/// Default output framerate. The compositor's decode is decoupled from
/// this; we just subsample frames to hit it.
pub const DEFAULT_GIF_FPS: u32 = 12;
/// Re-quantize the palette every N frames. The user-visible drift on a
/// screen-recording timeline is small within a few seconds, and
/// rebuilding the histogram + median-cut is O(n) on a 410 k-pixel frame
/// — caching amortizes the cost. 30 frames at 12 fps is one re-quant
/// per 2.5 s, the rough interval at which a recording's colour palette
/// tends to shift.
const PALETTE_REQUANTIZE_EVERY: u64 = 30;
/// Number of palette entries per frame. GIF supports up to 256
/// (`2_u16.pow(8)`), which is also what the standard web palette
/// assumes. 256 is the default; the spec allows smaller (4 / 8 / 16 /
/// 32 / 64 / 128) but 256 looks meaningfully better on screen
/// recordings and the cost difference is tiny.
const PALETTE_COLORS: usize = 256;
/// Wall-time / size / fps summary for a GIF export, shaped like
/// `pipeline::Stats` so the bench and the napi binding can pass it
/// through without a second struct.
pub struct GifStats {
pub frames: u64,
pub wall_s: f64,
pub fps: f64,
/// Duration of the resulting GIF (seconds) = `frames / fps`. Distinct
/// from `wall_s` (real render time).
pub video_duration_s: f64,
/// Size of the GIF file on disk, in bytes. Read after the writer
/// drops so it includes the trailer.
pub file_bytes: u64,
}
/// Optional knobs for `export_gif`. The same shape as the future
/// `ExportGifParams` block in the TS contract.
#[derive(Debug, Clone)]
pub struct GifExportParams {
pub width: Option<u32>,
pub height: Option<u32>,
pub fps: Option<u32>,
/// How many times the animation plays: `None` or `0` → forever (the
/// historical GIF default), `1` → once, `n` → n times.
pub loop_count: Option<u16>,
/// Floyd-Steinberg dithering at quantization. Default ON: the median
/// cut spreads its 256 entries over the whole frame, so a gradient
/// wallpaper gets a few dozen of them and, mapped to the nearest one,
/// breaks into flat bands. Error diffusion keeps its local average on
/// the ramp, and leaves a flat area flat: a colour that is in the
/// palette has no error to spread.
pub dither: bool,
}
impl Default for GifExportParams {
fn default() -> Self {
Self {
width: Some(DEFAULT_GIF_WIDTH),
height: Some(DEFAULT_GIF_HEIGHT),
fps: Some(DEFAULT_GIF_FPS),
loop_count: None, // infinite
dither: true,
}
}
}
/// The count to write in the Netscape 2.0 loop block for `loop_count` plays,
/// or `None` for no block. Viewers read the block's count as repeats after
/// the first play (Chromium, Firefox, ffmpeg's `-loop`), and 0 as forever, so
/// a GIF that plays once must carry no block at all: a count of 1 plays twice.
fn netscape_repeats(loop_count: Option<u16>) -> Option<u16> {
match loop_count {
None | Some(0) => Some(0),
Some(1) => None,
Some(plays) => Some(plays - 1),
}
}
/// Drive a multiclip GIF export end-to-end.
///
/// Deliberately the same shape as `pipeline::run_composited_multi`, and
/// deliberately driven by the same `walk_composited_timeline`: the clip walk,
/// the speed segments and the output-time decoder advancement are the video
/// exporter's, not a second implementation. Only the per-frame sink differs —
/// MP4 hands the composed texture to a hardware NV12 encoder, GIF reads it back
/// to the CPU and quantizes it to 256 colours.
///
/// Publish only a finished GIF; errors leave an existing destination intact.
pub fn export_gif(
clips: &[ClipSource],
out_path: &Path,
gpu: &Gpu,
comp: &Compositor,
cfg: &Cfg,
params: &GifExportParams,
progress: &mut dyn FnMut(u64),
) -> Result<GifStats> {
export_gif_cancellable(clips, out_path, gpu, comp, cfg, params, progress, &ExportControl::default())
}
pub fn export_gif_cancellable(
clips: &[ClipSource],
out_path: &Path,
gpu: &Gpu,
comp: &Compositor,
cfg: &Cfg,
params: &GifExportParams,
progress: &mut dyn FnMut(u64),
control: &ExportControl,
) -> Result<GifStats> {
with_staged_output(out_path, control, |file, staging_path| {
export_gif_inner(clips, staging_path, file, gpu, comp, cfg, params, progress, control)
})
}
fn export_gif_inner(
clips: &[ClipSource],
out_path: &Path,
file: File,
gpu: &Gpu,
comp: &Compositor,
cfg: &Cfg,
params: &GifExportParams,
progress: &mut dyn FnMut(u64),
control: &ExportControl,
) -> Result<GifStats> {
control.check()?;
if clips.is_empty() {
bail!("export_gif: aucun clip à exporter");
}
// The caller builds the compositor at the output size (same contract as
// `run_composited_multi` / `ExportParams`), so these must agree with what
// `readback_direct` hands back — asserted per frame below.
let width = params.width.unwrap_or(DEFAULT_GIF_WIDTH);
let height = params.height.unwrap_or(DEFAULT_GIF_HEIGHT);
let fps = params.fps.unwrap_or(DEFAULT_GIF_FPS).max(1);
let dither = params.dither;
// Set up the GIF writer up front: file + global header. We use a
// per-frame local palette (the standard "high-quality" form: a
// palette tuned to each frame's colours), so the global palette in
// the header is empty.
let mut writer = BufWriter::new(file);
// GIF frame delays are integer centiseconds, which can't express most
// fps exactly (15 fps = 6.67 cs). Each frame's delay comes from
// `frame_delay_cs`, which accumulates the fractional remainder
// (15 fps → 7,7,6,…) so playback length tracks frames / fps. The sum of
// delays actually written is kept for `video_duration_s`.
let mut total_delay_cs: u64 = 0;
// Cached palette: rebuilt on a schedule (`PALETTE_REQUANTIZE_EVERY`),
// shared with the workers mapping the frames that use it.
let mut palette_rgb: Arc<Vec<u8>> = Arc::new(vec![0u8; PALETTE_COLORS * 3]);
let t0 = Instant::now();
let scene = comp.scene_snapshot();
let frames = {
let mut gw = GifWriter::new(&mut writer, width as u16, height as u16)?;
gw.write_header()?;
if let Some(repeats) = netscape_repeats(params.loop_count) {
gw.write_netscape_loop(repeats)?;
}
let mut screen_decs: HashMap<String, Decoder> = HashMap::new();
let mut webcam_decs: HashMap<String, Decoder> = HashMap::new();
screen_decs.insert(clips[0].screen.clone(), unsafe {
Decoder::open_for_export(&clips[0].screen, gpu)?
});
// Mapping and LZW are over 90 % of a frame's time and need nothing but
// the frame and its palette, so they run on a pool, one frame per
// worker. This thread decodes, composes, reads back, builds the
// palette, and writes the encoded frames back in order.
let workers = std::thread::available_parallelism().map_or(1, |n| n.get());
let (job_tx, job_rx) = mpsc::sync_channel::<FrameJob>(workers);
let job_rx = Mutex::new(job_rx);
let frames = std::thread::scope(|scope| -> Result<u64> {
let (done_tx, done_rx) = mpsc::channel::<EncodedFrame>();
for _ in 0..workers {
let (job_rx, done_tx) = (&job_rx, done_tx.clone());
scope.spawn(move || {
let mut enc = FrameEncoder::new(width, height, dither);
loop {
// Bound first: a guard in a `while let` scrutinee would be
// held through `encode` and serialise the pool. `recv`
// fails once the walk is over and the sender dropped.
let Ok(job) = job_rx.lock().unwrap().recv() else { break };
if done_tx.send(enc.encode(job)).is_err() {
break;
}
}
});
}
drop(done_tx);
// Frames come back out of order; write each once its turn comes.
let mut pending: BTreeMap<u64, EncodedFrame> = BTreeMap::new();
let in_flight_max = 2 * workers as u64;
let mut written: u64 = 0;
// Writes what is next in line, returns how many frames are written.
let mut write_ready = |pending: &mut BTreeMap<u64, EncodedFrame>| -> Result<u64> {
while let Some(f) = pending.remove(&written) {
let delay_cs = frame_delay_cs(written, fps);
total_delay_cs += delay_cs as u64;
gw.write_frame(&f.lzw, &f.palette_rgb, delay_cs)?;
written += 1;
progress(written);
}
Ok(written)
};
let frames = unsafe {
walk_composited_timeline(
clips,
gpu,
comp,
cfg,
fps as i32,
&scene,
&mut screen_decs,
&mut webcam_decs,
&mut |frame_index| {
control.check()?;
// CPU readback of the staged RT (RGBA8 tightly-packed,
// `width * height * 4` bytes), and the reason GIF can't
// use the MP4 zero-copy sink.
let (rw, rh, rgba) = comp.readback_direct().map_err(|e| {
anyhow!("export_gif: readback @ frame {frame_index}: {e:#}")
})?;
debug_assert_eq!(rw, width);
debug_assert_eq!(rh, height);
// Refresh the palette on a schedule. Building the histogram
// and running median-cut is O(unique colors) — fast enough at
// 480p on our 30-frame cadence.
if frame_index % PALETTE_REQUANTIZE_EVERY == 0 {
let mut p = vec![0u8; PALETTE_COLORS * 3];
build_palette_median_cut(&rgba, PALETTE_COLORS, &mut p);
palette_rgb = Arc::new(p);
}
// Bound what is submitted but not yet written: behind one slow
// frame the rest would pile up in `pending`, each holding its
// encoded buffer. The frame that blocks the window is already
// submitted, so waiting on `done_rx` always makes progress.
while frame_index - write_ready(&mut pending)? >= in_flight_max {
let f = done_rx
.recv()
.map_err(|_| anyhow!("export_gif: encoder worker died"))?;
pending.insert(f.index, f);
}
let job =
FrameJob { index: frame_index, rgba, palette_rgb: palette_rgb.clone() };
job_tx.send(job).map_err(|_| anyhow!("export_gif: encoder worker died"))?;
for f in done_rx.try_iter() {
pending.insert(f.index, f);
}
write_ready(&mut pending).map(|_| ())
},
// GIF has no audio track, so clip boundaries need no work.
&mut |_, _, _, _| control.check(),
)?
};
drop(job_tx);
while write_ready(&mut pending)? < frames {
control.check()?;
let f = done_rx.recv().map_err(|_| anyhow!("export_gif: encoder worker died"))?;
pending.insert(f.index, f);
}
Ok(frames)
})?;
control.check()?;
gw.finish()?;
frames
};
// Drop the writer before stat-ing the file so the trailer is
// flushed.
writer.flush().context("flushing completed GIF")?;
drop(writer);
let wall_s = t0.elapsed().as_secs_f64();
let fps_actual = if wall_s > 0.0 { frames as f64 / wall_s } else { 0.0 };
// From the delays actually written, not from the requested fps.
let video_duration_s = total_delay_cs as f64 / 100.0;
let file_bytes = std::fs::metadata(out_path).map(|m| m.len()).unwrap_or(0);
Ok(GifStats { frames, wall_s, fps: fps_actual, video_duration_s, file_bytes })
}
/// One frame for an encoder worker: its pixels and the palette to map them to.
struct FrameJob {
index: u64,
rgba: Vec<u8>,
palette_rgb: Arc<Vec<u8>>,
}
/// A frame ready to write: its indices, LZW-encoded, and its palette.
struct EncodedFrame {
index: u64,
lzw: Vec<u8>,
palette_rgb: Arc<Vec<u8>>,
}
/// A worker's scratch buffers, reused across the frames it encodes.
struct FrameEncoder {
width: u32,
height: u32,
dither: bool,
indices: Vec<u8>,
// Two rows of Floyd-Steinberg error, 3 channels per pixel.
err_cur: Vec<f32>,
err_next: Vec<f32>,
}
impl FrameEncoder {
fn new(width: u32, height: u32, dither: bool) -> Self {
let w = width as usize;
FrameEncoder {
width,
height,
dither,
indices: vec![0u8; w * height as usize],
err_cur: vec![0.0f32; w * 3],
err_next: vec![0.0f32; w * 3],
}
}
fn encode(&mut self, job: FrameJob) -> EncodedFrame {
// The dither pass diffuses the error against the CHOSEN palette
// entry, so it runs fused with the mapping — see
// `map_to_indices_dithered`.
if self.dither {
map_to_indices_dithered(
&job.palette_rgb,
&job.rgba,
self.width,
self.height,
&mut self.err_cur,
&mut self.err_next,
&mut self.indices,
);
} else {
map_to_indices(&job.palette_rgb, &job.rgba, &mut self.indices);
}
let mut lzw = Vec::new();
lzw_compress(&self.indices, 8, &mut lzw);
EncodedFrame { index: job.index, lzw, palette_rgb: job.palette_rgb }
}
}
// =====================================================================
// GIF89a format writer (pure std::io::Write).
// =====================================================================
//
// Spec reference: GIF89a Appendix F (LZW) and the Lempel-Ziv-Welch
// variant. Code packing is LSB-first into the byte stream (the LSB of
// each code goes into the LSB of the byte), and bytes are written in
// order. A sub-block of N LZW bytes is preceded by a 1-byte length N
// (1..=255); a 0x00 byte terminates the sub-block stream. The image
// descriptor's LCT size field uses the same `2^N` encoding as the
// header's GCT size field.
struct GifWriter<W: Write> {
w: W,
width: u16,
height: u16,
/// Set by `finish`, so `Drop` does not append a second trailer.
finished: bool,
}
impl<W: Write> GifWriter<W> {
fn new(w: W, width: u16, height: u16) -> Result<Self> {
if width == 0 || height == 0 {
bail!("gif: dimensions must be > 0 (got {width}x{height})");
}
Ok(GifWriter {
w,
width,
height,
finished: false,
})
}
/// Write the GIF89a header + Logical Screen Descriptor. No global
/// color table: every frame carries a local palette, which the
/// GIF89a spec specifically allows and which gives per-frame
/// colour fidelity that a single global table can't match.
fn write_header(&mut self) -> Result<()> {
self.w.write_all(b"GIF89a")?;
// Logical screen descriptor.
self.w.write_all(&self.width.to_le_bytes())?;
self.w.write_all(&self.height.to_le_bytes())?;
// Packed byte: GCT flag (bit 7) = 0, color resolution
// (bits 4-6) = 7 (8 bits/channel), sort flag (bit 3) = 0,
// GCT size (bits 0-2) = 0 (no GCT). The upper nibble is the
// raw value; the GCT size is `(n + 1)` where the table has
// `2^(n+1)` entries. 0 here = "no GCT" (flag bit is 0
// anyway).
self.w.write_all(&[0b0_111_0_000])?;
// Background color index (unused, no GCT) and pixel aspect
// ratio (0 = unspecified, the common case).
self.w.write_all(&[0, 0])?;
Ok(())
}
/// Write a Netscape 2.0 application extension block driving the
/// GIF loop counter. `loop_count == 0` means infinite — the
/// historical GIF default and what most viewers assume.
fn write_netscape_loop(&mut self, loop_count: u16) -> Result<()> {
self.w.write_all(&[0x21, 0xFF, 0x0B])?;
self.w.write_all(b"NETSCAPE2.0")?;
self.w.write_all(&[0x03, 0x01])?;
self.w.write_all(&loop_count.to_le_bytes())?;
self.w.write_all(&[0x00])?;
Ok(())
}
/// Write one animated frame: Graphics Control Extension (delay
/// only — no transparency, no disposal), Image Descriptor, local
/// color table, and `lzw`, the frame's indices as `lzw_compress`
/// encodes them with a minimum code size of 8.
fn write_frame(&mut self, lzw: &[u8], palette_rgb: &[u8], delay_cs: u16) -> Result<()> {
debug_assert_eq!(palette_rgb.len(), PALETTE_COLORS * 3);
// Graphics Control Extension: delay only. The disposal
// method is "leave in place" (0) and the transparent flag
// is off, so a frame with overlapping dimensions is
// composited on top of the previous frame.
self.w.write_all(&[0x21, 0xF9, 0x04])?;
// Packed: 3 reserved (0) | 3 disposal (0 = leave in
// place) | 1 user input (0) | 1 transparent (0). 0x00
// throughout.
self.w.write_all(&[0x00])?;
self.w.write_all(&delay_cs.to_le_bytes())?;
// Transparent color index (unused — `0` is the conventional
// "no transparency" sentinel).
self.w.write_all(&[0x00])?;
// Block terminator.
self.w.write_all(&[0x00])?;
// Image Descriptor.
self.w.write_all(&[0x2C])?;
self.w.write_all(&0u16.to_le_bytes())?; // left
self.w.write_all(&0u16.to_le_bytes())?; // top
self.w.write_all(&self.width.to_le_bytes())?;
self.w.write_all(&self.height.to_le_bytes())?;
// Packed: LCT flag (bit 7) = 1, interlace (bit 6) = 0,
// sort (bit 5) = 0, reserved (bits 3-4) = 0, LCT size
// (bits 0-2) = 7 (i.e. 2^(7+1) = 256 entries).
self.w.write_all(&[0b1_0_0_00_111])?;
// Local color table.
self.w.write_all(palette_rgb)?;
// LZW image data: `LZW minimum code size` byte, then
// sub-blocks of compressed bytes, then a 0x00 terminator.
// LZW min code size is 8 for a 256-color palette.
self.w.write_all(&[8])?;
write_sub_blocks(&mut self.w, lzw)?;
self.w.write_all(&[0x00])?; // image data terminator
Ok(())
}
/// Write the trailer byte (`0x3B`) and flush. Callers should
/// typically rely on `Drop` instead — this exists for the bench
/// path that wants an explicit "we're done, no more frames"
/// signal.
fn finish(&mut self) -> Result<()> {
if self.finished {
return Ok(());
}
self.finished = true;
self.w.write_all(&[0x3B])?;
self.w.flush()?;
Ok(())
}
}
impl<W: Write> Drop for GifWriter<W> {
fn drop(&mut self) {
// Best-effort trailer for the paths that bail out before calling
// `finish`. Skipped when `finish` already wrote one — two trailer
// bytes are tolerated by most decoders but rejected by strict ones.
// We intentionally don't propagate the result — `Drop` can't return
// errors. The resulting file will be truncated/invalid, which the
// caller will detect on the next read.
if self.finished {
return;
}
let _ = self.w.write_all(&[0x3B]);
let _ = self.w.flush();
}
}
/// Write a stream of bytes as a sequence of GIF sub-blocks (max 255
/// bytes per sub-block, preceded by a 1-byte length, terminated by
/// `0x00`).
fn write_sub_blocks<W: Write>(w: &mut W, data: &[u8]) -> Result<()> {
let mut pos = 0;
while pos < data.len() {
let chunk = (data.len() - pos).min(255);
w.write_all(&[chunk as u8])?;
w.write_all(&data[pos..pos + chunk])?;
pos += chunk;
}
Ok(())
}
// =====================================================================
// LZW encoder (GIF89a variant).
// =====================================================================
//
// The GIF LZW variant:
// - LZW min code size = log2(max color + 1). For 256 colors: 8.
// - Initial code size = min code size + 1 = 9.
// - Clear code = 2^min_code_size = 256.
// - EOI code = clear code + 1 = 257.
// - First free code = 258.
// - Codes 0..256+1 are the initial table (literal codes plus the
// clear and EOI sentinels); codes 258+ are added as the encoder
// walks the input.
// - Code size bumps from 9 to 12 as the table fills; at 12 bits
// the table holds 4096 codes (0..4095). Adding the 4096th
// "missing pair" triggers a clear code, table reset, and the
// encoder starts over. The bump lands one code LATER than the
// table boundary suggests, because the decoder's table lags
// ours by one entry — see the note at the `code_size += 1`.
// - Codes are packed LSB-first into the byte stream; the
// bit-buffer drains into output bytes as soon as 8 bits have
// accumulated.
fn lzw_compress(indices: &[u8], min_code_size: u8, out: &mut Vec<u8>) {
let clear_code: u16 = 1u16 << min_code_size;
let eoi_code: u16 = clear_code + 1;
let initial_code_size: u8 = min_code_size + 1;
let mut table: HashMap<(u16, u8), u16> = HashMap::new();
let mut code_size: u8 = initial_code_size;
let mut next_code: u16 = eoi_code + 1;
let mut bit_buffer: u32 = 0;
let mut bits_in_buffer: u8 = 0;
// Helper closure: pack `code` at the current `code_size` into
// the bit buffer, draining whole bytes into `out` as they fill
// up. Code packing is LSB-first (the LSB of the code goes into
// the LSB of the current byte), and codes are written into
// `out` in stream order — which is the canonical GIF behaviour.
// Captures `out` mutably; the bit buffer and code size are
// passed in to keep the closure a small mutator rather than a
// re-borrow of the whole function.
let mut emit = |code: u16, code_size: u8, buf: &mut u32, n: &mut u8| {
*buf |= (code as u32) << *n;
*n += code_size;
while *n >= 8 {
out.push((*buf & 0xFF) as u8);
*buf >>= 8;
*n -= 8;
}
};
// Always start with a clear code — the decoder also requires
// it. (Empty streams still need the clear + EOI pair.)
emit(clear_code, code_size, &mut bit_buffer, &mut bits_in_buffer);
if indices.is_empty() {
emit(eoi_code, code_size, &mut bit_buffer, &mut bits_in_buffer);
// Pad the final byte with zeros to a full byte.
if bits_in_buffer > 0 {
out.push(bit_buffer as u8);
}
return;
}
let mut prefix: u16 = indices[0] as u16;
for &k in &indices[1..] {
let key = (prefix, k);
if let Some(&code) = table.get(&key) {
prefix = code;
continue;
}
// Miss: emit the prefix code at the current size, then
// add the new entry.
emit(prefix, code_size, &mut bit_buffer, &mut bits_in_buffer);
if next_code <= 4095 {
table.insert(key, next_code);
next_code += 1;
// Bump code_size one entry AFTER the table outgrows
// it, not on the boundary itself. The missing `+ 1`
// is what black-framed every exported GIF.
//
// The decoder builds its table one entry behind the
// encoder: it can only add `(prev, first_byte(cur))`
// once it has read the code that FOLLOWS. So when we
// have just inserted code 511 (`next_code == 512`),
// the decoder still holds 511 entries and still reads
// at 9 bits. Bumping here sends the next code out at
// 10 bits while the decoder reads 9 — the stream
// desyncs a few hundred codes in and every pixel
// after that is garbage. Deferring by one
// (`next_code == 513`) puts both bumps on the same
// code, which is what the reference encoder does too
// (it tests the PRE-insert `free_ent > maxcode`
// after emitting, not before).
if code_size < 12 && next_code == (1u16 << code_size) + 1 {
code_size += 1;
}
} else {
// Table full (next_code is 4096). Emit a clear
// code, reset the table, and start over. The
// decoder will see this clear code and rebuild
// the table the same way.
emit(clear_code, code_size, &mut bit_buffer, &mut bits_in_buffer);
table.clear();
code_size = initial_code_size;
next_code = eoi_code + 1;
}
prefix = k as u16;
}
// Flush: emit the final prefix, then EOI, then pad the bit
// buffer to a byte boundary.
emit(prefix, code_size, &mut bit_buffer, &mut bits_in_buffer);
emit(eoi_code, code_size, &mut bit_buffer, &mut bits_in_buffer);
if bits_in_buffer > 0 {
out.push(bit_buffer as u8);
}
}
// =====================================================================
// Median-cut palette builder.
// =====================================================================
//
// The standard Heckbert "Color Image Quantization for Frame Buffer
// Display" algorithm, with two pragmatic choices:
//
// 1. We work on a histogram of distinct colors (not on the raw
// pixel stream). The number of distinct colors on a screen
// recording frame is typically ≪ pixel count (10k–100k
// distinct colors in 410k pixels), which keeps the per-split
// sort cheap. Building the histogram is O(n) on pixel count.
// 2. We split by finding the longest channel axis and bisecting
// at the median (count-weighted) of that axis. A full sort
// per split dominates the cost; we sort by a single key (the
// chosen channel) which is `O(k log k)` per split, summed
// across `num_colors` splits.
fn build_palette_median_cut(rgba: &[u8], num_colors: usize, out_palette: &mut [u8]) {
debug_assert_eq!(out_palette.len(), num_colors * 3);
debug_assert!(num_colors > 0);
// 1. Histogram of distinct colors. Bumping the counter is a
// single hashmap insert/update per pixel — O(n) total, with
// cache-friendly bulk iteration over the RGBA buffer.
let mut histogram: HashMap<[u8; 3], u32> = HashMap::new();
for chunk in rgba.chunks_exact(4) {
let color = [chunk[0], chunk[1], chunk[2]];
*histogram.entry(color).or_insert(0) += 1;
}
if histogram.is_empty() {
// Shouldn't happen with a real readback, but fall back to
// a black palette if it does.
for chunk in out_palette.chunks_exact_mut(3) {
chunk[0] = 0;
chunk[1] = 0;
chunk[2] = 0;
}
return;
}
// Collapse the histogram into a sorted vector for the split
// step. We allocate this fresh each call — `requantize_every`
// frames is the only call site, and the cost (one allocation +
// one memcpy from the hashmap) is well under a millisecond at
// 480p.
//
// Sorted, because a `HashMap` iterates in a per-process random
// order and the axis sorts below are stable: equal channel values
// kept that order, so the same frame got a different palette on
// every run and no two exports were byte-identical.
let mut entries: Vec<([u8; 3], u32)> = histogram.into_iter().collect();
entries.sort_unstable();
// 2. Repeatedly split the bucket with the longest channel
// range until we have `num_colors` buckets. The split is
// count-weighted: the median of the channel values by
// cumulative count, not by raw position.
let mut buckets: Vec<Vec<([u8; 3], u32)>> = vec![entries];
while buckets.len() < num_colors {
// Find the bucket with the largest total range across
// channels. Ties break by index (earlier split first),
// which is reproducible across machines.
let mut best_idx: usize = 0;
let mut best_range: u32 = 0;
for (i, b) in buckets.iter().enumerate() {
if b.len() < 2 {
continue;
}
let r = channel_range(b, 0);
let g = channel_range(b, 1);
let bl = channel_range(b, 2);
let m = r.max(g).max(bl);
if m > best_range {
best_range = m;
best_idx = i;
}
}
if best_range == 0 {
// All remaining buckets are uniform; no further
// refinement possible. Pad with the average of
// the largest bucket so the palette still has
// the requested entry count (or close to it).
break;
}
// Split `best_idx` along the longest axis. Count-weighted
// median: find the channel value where the cumulative
// count crosses half the bucket's total.
let axis = {
let b = &buckets[best_idx];
let r = channel_range(b, 0);
let g = channel_range(b, 1);
let bl = channel_range(b, 2);
if r >= g && r >= bl {
0
} else if g >= bl {
1
} else {
2
}
};
let bucket = buckets.remove(best_idx);
let total: u64 = bucket.iter().map(|(_, c)| *c as u64).sum();
let half = total / 2;
// Sort by the chosen axis. A full sort is the right call
// here — the bucket is at most the size of the histogram
// (typically 10k–100k entries), and a single sort is
// cheaper than trying to find the median in O(n) and then
// partitioning, which has worse constants in Rust.
let mut sorted = bucket;
sorted.sort_by_key(|(c, _)| c[axis]);
// Walk the sorted bucket accumulating counts; the first
// entry past `half` is the split point.
let mut acc: u64 = 0;
let mut split = sorted.len();
for (i, (_, count)) in sorted.iter().enumerate() {
acc += *count as u64;
if acc >= half {
split = i + 1;
break;
}
}
// split in (0, len) by construction (the bucket has ≥ 2
// entries and half < total), but guard against an edge
// case where every entry sits on one side of the median.
if split == 0 {
split = 1;
} else if split >= sorted.len() {
split = sorted.len() - 1;
}
let mut right = sorted.split_off(split);
if right.is_empty() {
// Defensive: shouldn't happen with a valid split
// point, but if it does we don't want to lose
// entries.
right = sorted.split_off(sorted.len() - 1);
}
buckets.push(sorted);
buckets.push(right);
}
// 3. Average each bucket (count-weighted) to get one palette
// entry per bucket. If we have fewer than `num_colors`
// buckets (all-uniform early exit), duplicate the largest
// bucket's average to fill the rest.
for (i, chunk) in out_palette.chunks_exact_mut(3).enumerate() {
let bucket = buckets.get(i).filter(|b| !b.is_empty());
let (r, g, b) = match bucket {
Some(b) => {
let mut r_sum: u64 = 0;
let mut g_sum: u64 = 0;
let mut b_sum: u64 = 0;
let mut n: u64 = 0;
for (color, count) in b {
r_sum += color[0] as u64 * *count as u64;
g_sum += color[1] as u64 * *count as u64;
b_sum += color[2] as u64 * *count as u64;
n += *count as u64;
}
if n == 0 {
(0u8, 0u8, 0u8)
} else {
((r_sum / n) as u8, (g_sum / n) as u8, (b_sum / n) as u8)
}
}
None => {
// Pad: reuse the first non-empty bucket's
// average. (`buckets` is non-empty because
// the histogram is non-empty.)
if let Some(b) = buckets.first().filter(|b| !b.is_empty()) {
let mut r_sum: u64 = 0;
let mut g_sum: u64 = 0;
let mut b_sum: u64 = 0;
let mut n: u64 = 0;
for (color, count) in b {
r_sum += color[0] as u64 * *count as u64;
g_sum += color[1] as u64 * *count as u64;
b_sum += color[2] as u64 * *count as u64;
n += *count as u64;
}
if n == 0 {
(0u8, 0u8, 0u8)
} else {
((r_sum / n) as u8, (g_sum / n) as u8, (b_sum / n) as u8)
}
} else {
(0u8, 0u8, 0u8)
}
}
};
chunk[0] = r;
chunk[1] = g;
chunk[2] = b;
}
}
fn channel_range(bucket: &[([u8; 3], u32)], channel: usize) -> u32 {
if bucket.is_empty() {
return 0;
}
let min = bucket.iter().map(|(c, _)| c[channel]).min().unwrap() as u32;
let max = bucket.iter().map(|(c, _)| c[channel]).max().unwrap() as u32;
max - min
}
// =====================================================================
// Nearest-color index mapping.
// =====================================================================
//
// Exact nearest palette entry by squared distance, through
// `SortedPalette`.
fn map_to_indices(palette_rgb: &[u8], rgba: &[u8], indices: &mut [u8]) {
let npix = indices.len();
debug_assert_eq!(rgba.len(), npix * 4);
debug_assert_eq!(palette_rgb.len(), PALETTE_COLORS * 3);
let pal = SortedPalette::new(palette_rgb);
let mut hint = 0;
for i in 0..npix {
let base = i * 4;
// Integer channels: every distance is an integer below 2^24, so the
// f32 search finds exactly what an i32 one would.
let (idx, pos) = pal.nearest(
rgba[base] as f32,
rgba[base + 1] as f32,
rgba[base + 2] as f32,
hint,
);
indices[i] = idx;
hint = pos;
}
}
/// The palette sorted by red, for an exact nearest-colour search that skips
/// most of it.
///
/// A brute-force scan of all 256 entries per pixel was 92 % of a dithered
/// export's wall time (172 ms per 864×480 frame, measured): the arg-min does not
/// autovectorize. Here the scan starts at the pixel's red value and walks out
/// both ways, stopping once the red distance alone exceeds the best full
/// distance, since no entry further along can be closer.
///
/// Exact, not approximate: same distance formula, and ties go to the lowest
/// palette index, as in the scan it replaces — the exported GIF is
/// byte-identical.
struct SortedPalette {
r: [f32; PALETTE_COLORS],
g: [f32; PALETTE_COLORS],
b: [f32; PALETTE_COLORS],
/// Palette index of each sorted entry.
idx: [u8; PALETTE_COLORS],
}
impl SortedPalette {
fn new(palette_rgb: &[u8]) -> Self {
let mut order: Vec<usize> = (0..PALETTE_COLORS).collect();
order.sort_by_key(|&k| palette_rgb[k * 3]);
let mut p = SortedPalette {
r: [0.0; PALETTE_COLORS],
g: [0.0; PALETTE_COLORS],
b: [0.0; PALETTE_COLORS],
idx: [0; PALETTE_COLORS],
};
for (s, &k) in order.iter().enumerate() {
p.r[s] = palette_rgb[k * 3] as f32;
p.g[s] = palette_rgb[k * 3 + 1] as f32;
p.b[s] = palette_rgb[k * 3 + 2] as f32;
p.idx[s] = k as u8;
}
p
}
/// Nearest entry to `(cr, cg, cb)`, as `(palette index, sorted position)`.
/// `hint` is a sorted position to seed the bound with — the previous
/// pixel's answer, usually the right one again.
fn nearest(&self, cr: f32, cg: f32, cb: f32, hint: usize) -> (u8, usize) {
let dist = |s: usize| {
let dr = cr - self.r[s];
let dg = cg - self.g[s];
let db = cb - self.b[s];
dr * dr + dg * dg + db * db
};
let mut best = hint;
let mut best_dist = dist(hint);
// Lowest palette index wins a tie, as in a 0..256 scan with `<`.
let consider = |s: usize, best: &mut usize, best_dist: &mut f32| {
let d = dist(s);
if d < *best_dist || (d == *best_dist && self.idx[s] < self.idx[*best]) {
*best_dist = d;
*best = s;
}
};
// `dist >= dr * dr` holds in f32 too (adding non-negatives never
// rounds below an operand), so stopping on `>` loses no entry,
// tied ones included.
let start = self.r.partition_point(|&r| r < cr);
for s in start..PALETTE_COLORS {
let dr = self.r[s] - cr;
if dr * dr > best_dist {
break;
}
consider(s, &mut best, &mut best_dist);
}
for s in (0..start).rev() {
let dr = cr - self.r[s];
if dr * dr > best_dist {
break;
}
consider(s, &mut best, &mut best_dist);
}
(self.idx[best], best)
}
}
/// Nearest-palette mapping with Floyd-Steinberg error diffusion, fused.
///
/// Fused on purpose. A separate dither pass has nothing to diffuse against:
/// quantizing to `round()` of an already-integer channel gives an error of
/// exactly zero for every pixel, so the whole pass is a no-op that still costs
/// a full float traversal. The error that matters is `pixel - palette[chosen]`,
/// which only exists once the palette entry has been picked — hence one loop.
///
/// Kernel is the standard 7/16 right, 3/16 below-left, 5/16 below,
/// 1/16 below-right. Two row buffers keep the working set at O(width).
#[allow(clippy::too_many_arguments)]
fn map_to_indices_dithered(
palette_rgb: &[u8],
rgba: &[u8],
width: u32,
height: u32,
err_cur: &mut [f32],
err_next: &mut [f32],
indices: &mut [u8],
) {
let w = width as usize;
let h = height as usize;
debug_assert_eq!(indices.len(), w * h);
debug_assert_eq!(palette_rgb.len(), PALETTE_COLORS * 3);
err_cur.fill(0.0);
err_next.fill(0.0);
let pal = SortedPalette::new(palette_rgb);
let mut hint = 0;
for y in 0..h {
for x in 0..w {
let base = (y * w + x) * 4;
let e = x * 3;
// Channel value carrying the error diffused into this pixel.
let cr = (rgba[base] as f32 + err_cur[e]).clamp(0.0, 255.0);
let cg = (rgba[base + 1] as f32 + err_cur[e + 1]).clamp(0.0, 255.0);
let cb = (rgba[base + 2] as f32 + err_cur[e + 2]).clamp(0.0, 255.0);
let (idx, pos) = pal.nearest(cr, cg, cb, hint);
hint = pos;
let best_idx = idx as usize;
indices[y * w + x] = idx;
// THE error: distance to the colour actually written.
let er = cr - palette_rgb[best_idx * 3] as f32;
let eg = cg - palette_rgb[best_idx * 3 + 1] as f32;
let eb = cb - palette_rgb[best_idx * 3 + 2] as f32;
let mut spread = |slot: &mut [f32], idx: usize, f: f32| {
slot[idx] += er * f;
slot[idx + 1] += eg * f;
slot[idx + 2] += eb * f;
};
if x + 1 < w {
spread(err_cur, e + 3, 7.0 / 16.0);
spread(err_next, e + 3, 1.0 / 16.0);
}
if x > 0 {
spread(err_next, e - 3, 3.0 / 16.0);
}
spread(err_next, e, 5.0 / 16.0);
}
// Next row becomes current; clear the far row for reuse.
err_cur.copy_from_slice(err_next);
err_next.fill(0.0);
}
}
// =====================================================================
// Tests.
// =====================================================================
//
// These tests run under `cargo test -p openscreen-compositor` and
// don't need a GPU — they exercise the GIF89a writer, the LZW
// encoder, the median-cut palette, the nearest-color mapping, and
// the Floyd-Steinberg dither. The full `export_gif` pipeline
// (Player + GPU + readback) is exercised by the bench, not here.
/// Delay in centiseconds for frame `index` at `fps`: the difference between
/// the rounded end and start times of the frame, so the fractional remainder
/// carries over and the running total stays within half a centisecond of
/// `(index + 1) * 100 / fps`. Never 0 (browsers treat 0 as "as fast as
/// possible" / 10 cs).
fn frame_delay_cs(index: u64, fps: u32) -> u16 {
let fps = fps.max(1) as u64;
let rounded_cs = |n: u64| (n * 200 + fps) / (2 * fps);
(rounded_cs(index + 1) - rounded_cs(index)).clamp(1, u16::MAX as u64) as u16
}
#[cfg(test)]
mod tests {
use super::*;
use std::io::Cursor;
#[test]
fn a_gif_that_plays_once_carries_no_loop_block() {
assert_eq!(netscape_repeats(None), Some(0));
assert_eq!(netscape_repeats(Some(0)), Some(0));
assert_eq!(netscape_repeats(Some(1)), None);
assert_eq!(netscape_repeats(Some(3)), Some(2));
}
#[test]
fn frame_delays_sum_to_programme_duration() {
for fps in [15u32, 30, 12, 20, 25, 24, 60] {
for n in [1u64, 2, 3, 7, 100, 508, 10_000] {
let delays: Vec<u16> = (0..n).map(|i| frame_delay_cs(i, fps)).collect();
assert!(delays.iter().all(|&d| d >= 1), "fps {fps}: zero delay");
let sum: u64 = delays.iter().map(|&d| d as u64).sum();
let expected = (n as f64 * 100.0 / fps as f64).round() as i64;
assert!((sum as i64 - expected).abs() <= 1, "fps {fps} n {n}: {sum} vs {expected}");
}
}
// 15 fps alternates 7/7/6 rather than a flat (fast) 6.
let d: Vec<u16> = (0..3).map(|i| frame_delay_cs(i, 15)).collect();
assert_eq!(d.iter().sum::<u16>(), 20);
}
/// The most basic round-trip: write a 2×2 frame and check the
/// file is well-formed GIF89a. No decode — we just walk the
/// output bytes and confirm the structural shape.
#[test]
fn gif_writer_writes_exactly_one_trailer() {
// `finish` writes 0x3B, and so does `Drop`. Without the guard the file
// ends `3B 3B`, which strict decoders reject.
let mut buf = Vec::new();
{
let mut gw = GifWriter::new(&mut buf, 2, 2).unwrap();
gw.write_header().unwrap();
gw.finish().unwrap();
}
assert_eq!(buf.last(), Some(&0x3B));
assert_ne!(
buf[buf.len() - 2],
0x3B,
"trailer written twice: {:02X?}",
&buf[buf.len() - 2..]
);
}
#[test]
fn gif_writer_drop_still_terminates_without_finish() {
// The bail-out paths never call `finish`; `Drop` must still close the file.
let mut buf = Vec::new();
{
let mut gw = GifWriter::new(&mut buf, 2, 2).unwrap();
gw.write_header().unwrap();
}
assert_eq!(buf.last(), Some(&0x3B));
}
#[test]
fn gif_writer_writes_minimal_header() {
let mut buf = Vec::new();
{
let mut gw = GifWriter::new(&mut buf, 2, 2).unwrap();
gw.write_header().unwrap();
gw.write_netscape_loop(0).unwrap();
let palette = vec![0u8; PALETTE_COLORS * 3];
let mut lzw = Vec::new();
lzw_compress(&[0u8; 4], 8, &mut lzw);
gw.write_frame(&lzw, &palette, 10).unwrap();
gw.finish().unwrap();
}
// Magic.
assert_eq!(&buf[0..6], b"GIF89a");
// Width / height (LE u16).
assert_eq!(&buf[6..8], &2u16.to_le_bytes());
assert_eq!(&buf[8..10], &2u16.to_le_bytes());
// Packed byte: GCT flag = 0, color res = 7, sort = 0, GCT
// size = 0.
assert_eq!(buf[10], 0b0_111_0_000);
// Background + aspect: 0, 0.
assert_eq!(buf[11], 0);
assert_eq!(buf[12], 0);
// Netscape loop extension.
assert_eq!(&buf[13..16], &[0x21, 0xFF, 0x0B]);
assert_eq!(&buf[16..27], b"NETSCAPE2.0");
// Trailer at the end.
assert_eq!(*buf.last().unwrap(), 0x3B);
}
/// Reference GIF89a LZW decoder (spec Appendix F), for the
/// round-trip tests below.
///
/// It exists because "the output is a non-empty byte stream" —
/// all the assertion these tests used to make — passes happily on
/// a stream no decoder can read. The encoder bumped its code size
/// one code too early, every GIF the app exported decoded to black,
/// and the whole suite stayed green: `export_timing.rs` reads the
/// frame PALETTES, which are written outside the LZW data and were
/// perfectly fine. Nothing in the repo ever decoded a pixel.
///
/// So this is deliberately an INDEPENDENT implementation, written
/// from the spec rather than by mirroring `lzw_compress`: a decoder
/// derived from the encoder would have reproduced the same
/// off-by-one and agreed with it. Its output was cross-checked
/// against macOS ImageIO (`sips -s format png`) on real frames.
///
/// Table lags the encoder's by one entry by construction: an entry
/// can only be completed once the FOLLOWING code is known.
fn lzw_decompress(data: &[u8], min_code_size: u8) -> Vec<u8> {
let clear_code: u16 = 1u16 << min_code_size;
let eoi_code: u16 = clear_code + 1;
let mut code_size: u8 = min_code_size + 1;
// Literals, then two placeholders so indices line up with the
// clear / EOI codes: `dict.len()` is then exactly the encoder's
// `next_code`.
let fresh = || -> Vec<Vec<u8>> {
let mut d: Vec<Vec<u8>> = (0..clear_code).map(|i| vec![i as u8]).collect();
d.push(Vec::new());
d.push(Vec::new());
d
};
let mut dict = fresh();
let mut out: Vec<u8> = Vec::new();
let mut prev: Option<u16> = None;
let mut bitpos: usize = 0;
let total_bits = data.len() * 8;
loop {
assert!(
bitpos + code_size as usize <= total_bits,
"truncated LZW stream at bit {bitpos} of {total_bits}"
);
// LSB-first: bit i of the code is bit i of the stream.
let mut code: u16 = 0;
for i in 0..code_size as usize {
let bit = (data[(bitpos + i) / 8] >> ((bitpos + i) % 8)) & 1;
code |= (bit as u16) << i;
}
bitpos += code_size as usize;
if code == clear_code {
dict = fresh();
code_size = min_code_size + 1;
prev = None;
continue;
}
if code == eoi_code {
break;
}
// Either a known entry, or the KwKwK case: the code the
// encoder just added, which we can only reconstruct from
// the previous entry plus its own first byte.
let entry: Vec<u8> = if (code as usize) < dict.len() {
dict[code as usize].clone()
} else {
let p = prev.unwrap_or_else(|| {
panic!("first code after a clear must be a literal, got {code}")
});
let mut e = dict[p as usize].clone();
e.push(dict[p as usize][0]);
e
};
assert!(!entry.is_empty(), "code {code} resolved to an empty entry");
out.extend_from_slice(&entry);
if let Some(p) = prev {
if dict.len() < 4096 {
let mut new_entry = dict[p as usize].clone();
new_entry.push(entry[0]);
dict.push(new_entry);
if code_size < 12 && dict.len() == (1usize << code_size) {
code_size += 1;
}
}
}
prev = Some(code);
}
out
}
fn assert_lzw_round_trips(name: &str, pixels: &[u8]) {
let mut compressed = Vec::new();
lzw_compress(pixels, 8, &mut compressed);
let decoded = lzw_decompress(&compressed, 8);
assert_eq!(
decoded.len(),
pixels.len(),
"{name}: decoded {} pixels, expected {}",
decoded.len(),
pixels.len()
);
if let Some(i) = (0..pixels.len()).find(|&i| decoded[i] != pixels[i]) {
panic!(
"{name}: first mismatch at pixel {i} (expected {}, got {})",
pixels[i], decoded[i]
);
}
}
/// A stream long enough to cross the 9→10 bit boundary must survive a
/// decode. This is THE regression test: the encoder used to bump its
/// code size one code before the decoder does, so everything past
/// roughly the 255th code came back as garbage — which is what made
/// exported GIFs render black.
#[test]
fn lzw_round_trips_across_the_code_size_boundary() {
// Long runs plus slow variation — the shape of a real
// screen-recording frame, and enough misses to walk 9 → 10 → 11.
let pixels: Vec<u8> = (0..200_000u32).map(|i| ((i / 97) % 251) as u8).collect();
assert_lzw_round_trips("gradient-ish", &pixels);
}
/// Table-full path: 4096 entries, a clear code, and a reset mid-stream.
/// Pseudo-random data fills the table fast and forces several clears.
#[test]
fn lzw_round_trips_through_table_full_clears() {
let mut seed = 0x1234_5678u32;
let pixels: Vec<u8> = (0..DEFAULT_GIF_WIDTH * DEFAULT_GIF_HEIGHT)
.map(|_| {
seed = seed.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
(seed >> 24) as u8
})
.collect();
assert_lzw_round_trips("noise (forces clears)", &pixels);
}
/// The degenerate shapes: uniform frame (one long run), two-colour
/// alternation (table grows without ever repeating), single pixel.
#[test]
fn lzw_round_trips_degenerate_frames() {
assert_lzw_round_trips("uniform", &vec![42u8; 100_000]);
assert_lzw_round_trips(
"alternating",
&(0..50_000).map(|i| (i % 2) as u8).collect::<Vec<_>>(),
);
assert_lzw_round_trips("single pixel", &[7]);
}
/// The LZW encoder must produce a clear code at the start and
/// an EOI at the end — checked by decoding, since a stream that
/// merely "isn't empty" proves nothing.
#[test]
fn lzw_compress_emits_clear_and_eoi() {
let pixels: Vec<u8> = (0..200).map(|i| (i % 4) as u8).collect();
let mut out = Vec::new();
lzw_compress(&pixels, 8, &mut out);
assert!(!out.is_empty());
// The leading clear code (256, 9 bits, LSB-first) occupies the
// first byte and the low bit of the second.
assert_eq!(out[0], 0x00);
assert_eq!(out[1] & 0x01, 0x01);
// And the whole thing decodes back to what went in — which is
// only possible if the EOI is there and the bits line up.
assert_lzw_round_trips("short run", &pixels);
}
/// LZW on an empty input still emits clear + EOI. This is the
/// documented behaviour and the decoder requires it.
#[test]
fn lzw_compress_empty_still_has_clear_eoi() {
let mut out = Vec::new();
lzw_compress(&[], 8, &mut out);
assert!(!out.is_empty());
assert!(lzw_decompress(&out, 8).is_empty());
}
/// End-to-end through the container: write a frame with `GifWriter`,
/// then pull the LZW payload back out of the file bytes and decode it.
/// Covers the sub-block chunking and the image-descriptor layout as
/// well as the codec — the encoder and the container have to agree for
/// the pixels to survive.
#[test]
fn written_frame_decodes_back_to_the_same_indices() {
// 64×64 with a diagonal pattern: enough distinct index runs that a
// desynced code size would show up, and >255 compressed bytes so
// the sub-block chunking is exercised.
let (w, h) = (64usize, 64usize);
let indices: Vec<u8> = (0..w * h).map(|i| ((i / 7 + i % 13) % 251) as u8).collect();
let palette = vec![0u8; PALETTE_COLORS * 3];
let mut buf = Vec::new();
{
let mut gw = GifWriter::new(&mut buf, w as u16, h as u16).unwrap();
gw.write_header().unwrap();
gw.write_netscape_loop(0).unwrap();
let mut lzw = Vec::new();
lzw_compress(&indices, 8, &mut lzw);
gw.write_frame(&lzw, &palette, 8).unwrap();
gw.finish().unwrap();
}
// Walk to the image descriptor (0x2C), skip its 9-byte body and the
// 256-entry local table, then reassemble the sub-block chain.
let img = buf.iter().position(|&b| b == 0x2C).expect("image descriptor");
let mut p = img + 10 + PALETTE_COLORS * 3;
assert_eq!(buf[p], 8, "LZW minimum code size");
p += 1;
let mut payload = Vec::new();
while buf[p] != 0 {
let len = buf[p] as usize;
payload.extend_from_slice(&buf[p + 1..p + 1 + len]);
p += 1 + len;
}
assert_eq!(lzw_decompress(&payload, 8), indices);
}
/// Median-cut on a 2-color image should produce 2 distinct
/// palette entries (and pad the rest with the same average).
#[test]
fn median_cut_handles_two_color_image() {
let rgba: Vec<u8> = (0..100)
.flat_map(|i| if i % 2 == 0 { [255, 0, 0, 255] } else { [0, 0, 255, 255] })
.collect();
let mut palette = vec![0u8; 256 * 3];
build_palette_median_cut(&rgba, 256, &mut palette);
// The first entries should be near pure red and pure blue;
// the rest pad to the bucket average (whichever the
// algorithm picked first).
let has_red = palette.chunks_exact(3).any(|c| c[0] > 200 && c[1] < 50 && c[2] < 50);
let has_blue = palette.chunks_exact(3).any(|c| c[2] > 200 && c[0] < 50 && c[1] < 50);
assert!(has_red, "median-cut dropped red");
assert!(has_blue, "median-cut dropped blue");
}
/// The same frame must give the same palette, so an export is reproducible.
/// Many colours share channel values here, which is where the histogram's
/// iteration order used to leak into the splits.
#[test]
fn median_cut_is_deterministic() {
let mut seed = 0x2545_F491u32;
let rgba: Vec<u8> = (0..50_000)
.flat_map(|_| {
seed = seed.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
let level = |shift: u32| ((seed >> shift) % 11) as u8 * 25;
[level(8), level(14), level(20), 255]
})
.collect();
let mut first = vec![0u8; 256 * 3];
build_palette_median_cut(&rgba, 256, &mut first);
for _ in 0..8 {
let mut again = vec![0u8; 256 * 3];
build_palette_median_cut(&rgba, 256, &mut again);
assert_eq!(again, first);
}
}
/// Median-cut on a uniform image (single color) must not
/// loop forever and must produce a non-empty palette.
#[test]
fn median_cut_uniform_image_does_not_hang() {
let rgba = vec![128u8; 4 * 100];
let mut palette = vec![0u8; 256 * 3];
build_palette_median_cut(&rgba, 256, &mut palette);
// Every entry is near gray.
for chunk in palette.chunks_exact(3) {
assert!((chunk[0] as i32 - 128).abs() < 4);
assert!((chunk[1] as i32 - 128).abs() < 4);
assert!((chunk[2] as i32 - 128).abs() < 4);
}
}
/// Nearest-color mapping: every index is in [0, 256) and the
/// output length matches the input.
#[test]
fn map_to_indices_covers_all_pixels() {
// Use `wrapping_mul` so the test palette stays inside u8
// without overflowing (the production palette is built by
// median-cut and never overflows, but a test palette
// built from a closed-form expression can).
let palette: Vec<u8> = (0..256u32)
.flat_map(|i| {
let i = i as u8;
[i.wrapping_mul(3), i.wrapping_mul(5), i.wrapping_mul(7)]
})
.collect();
let rgba: Vec<u8> = (0..1000u32)
.flat_map(|i| {
let i = i as u8;
[i, i.wrapping_mul(2), i.wrapping_mul(3), 255]
})
.collect();
let mut indices = vec![0u8; 1000];
map_to_indices(&palette, &rgba, &mut indices);
assert_eq!(indices.len(), 1000);
for &idx in &indices {
assert!((idx as usize) < PALETTE_COLORS);
}
}
/// The dither path doesn't crash on a 1×1 image (the boundary
/// cases — `x + 1 < w`, `x > 0` — are where off-by-one errors
/// show up) and maps the single pixel into the palette.
#[test]
fn dithered_mapping_handles_one_by_one() {
let rgba = vec![100u8, 150, 200, 255];
let palette = vec![0u8; PALETTE_COLORS * 3];
let mut err_cur = vec![0.0f32; 3];
let mut err_next = vec![0.0f32; 3];
let mut indices = vec![0u8; 1];
map_to_indices_dithered(
&palette,
&rgba,
1,
1,
&mut err_cur,
&mut err_next,
&mut indices,
);
assert!((indices[0] as usize) < PALETTE_COLORS);
}
/// What the dithering is for: a smooth ramp against a palette too coarse for it. That is
/// what a real frame hands a wallpaper gradient, since the median cut spreads 256 entries
/// over the whole frame, not over the one gradient. Nearest-colour mapping flattens the ramp
/// into wide bands; Floyd-Steinberg keeps its local average on the ramp.
#[test]
fn dithering_keeps_a_gradient_on_its_ramp_where_plain_mapping_bands() {
let (w, h) = (512usize, 8usize);
let ramp = |x: usize| (64 + x / 4) as u8; // grey 64..=191, a new level every 4 px
let rgba: Vec<u8> = (0..h)
.flat_map(|_| (0..w).flat_map(move |x| [ramp(x), ramp(x), ramp(x), 255]))
.collect();
// 16 greys, 17 levels apart, repeated to fill the 256 entries.
let palette: Vec<u8> =
(0..PALETTE_COLORS).flat_map(|i| [((i % 16) * 17) as u8; 3]).collect();
let mut plain = vec![0u8; w * h];
map_to_indices(&palette, &rgba, &mut plain);
let mut dithered = vec![0u8; w * h];
let (mut err_cur, mut err_next) = (vec![0.0f32; w * 3], vec![0.0f32; w * 3]);
map_to_indices_dithered(
&palette,
&rgba,
w as u32,
h as u32,
&mut err_cur,
&mut err_next,
&mut dithered,
);
// RMS distance between the ramp and a 16-px moving average of what a row maps to: the
// eye averages neighbouring pixels, so this is the banding it sees.
let row = h / 2;
let banding = |indices: &[u8]| -> f64 {
let k = 16;
let grey = |x: usize| palette[indices[row * w + x] as usize * 3] as f64;
let sq: Vec<f64> = (0..=w - k)
.map(|x0| {
let seen = (x0..x0 + k).map(grey).sum::<f64>() / k as f64;
let truth = (x0..x0 + k).map(|x| ramp(x) as f64).sum::<f64>() / k as f64;
(seen - truth).powi(2)
})
.collect();
(sq.iter().sum::<f64>() / sq.len() as f64).sqrt()
};
let (plain_err, dithered_err) = (banding(&plain), banding(&dithered));
assert!(plain_err > 3.0, "this palette should band the ramp (error {plain_err:.2})");
assert!(
dithered_err < 1.5,
"dithering left the ramp banded: {dithered_err:.2} vs {plain_err:.2} undithered"
);
}
/// The pruned search must pick exactly what a full scan picks, ties to the
/// lowest index included, on both paths. The palette repeats entries (the
/// median cut pads with duplicates) and shares red values, which is where
/// ties and the pruning bound meet.
#[test]
fn sorted_palette_search_matches_a_full_scan() {
let mut seed = 0x9E37_79B9u32;
let mut next = || {
seed = seed.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
(seed >> 24) as u8
};
let palette: Vec<u8> = (0..PALETTE_COLORS)
.flat_map(|i| match i % 5 {
0 => [i as u8 & 0xF0, 128, 64],
_ => [next(), next(), next()],
})
.collect();
let (w, h) = (97usize, 61usize);
let rgba: Vec<u8> = (0..w * h).flat_map(|_| [next(), next(), next(), 255]).collect();
let full_scan = |c: [f32; 3]| -> u8 {
let mut best = (f32::MAX, 0usize);
for k in 0..PALETTE_COLORS {
let d: Vec<f32> = (0..3).map(|j| c[j] - palette[k * 3 + j] as f32).collect();
let dist = d[0] * d[0] + d[1] * d[1] + d[2] * d[2];
if dist < best.0 {
best = (dist, k);
}
}
best.1 as u8
};
let mut plain = vec![0u8; w * h];
map_to_indices(&palette, &rgba, &mut plain);
for (i, px) in rgba.chunks_exact(4).enumerate() {
let k = full_scan([px[0] as f32, px[1] as f32, px[2] as f32]);
assert_eq!(plain[i], k, "pixel {i}");
}
// The dithered path, replayed with a full scan.
let mut dithered = vec![0u8; w * h];
let (mut err_cur, mut err_next) = (vec![0.0f32; w * 3], vec![0.0f32; w * 3]);
map_to_indices_dithered(
&palette,
&rgba,
w as u32,
h as u32,
&mut err_cur,
&mut err_next,
&mut dithered,
);
let (mut cur, mut nxt) = (vec![0.0f32; w * 3], vec![0.0f32; w * 3]);
for y in 0..h {
for x in 0..w {
let (base, e) = ((y * w + x) * 4, x * 3);
let c: Vec<f32> =
(0..3).map(|j| (rgba[base + j] as f32 + cur[e + j]).clamp(0.0, 255.0)).collect();
let k = full_scan([c[0], c[1], c[2]]);
assert_eq!(dithered[y * w + x], k, "dithered pixel ({x}, {y})");
for j in 0..3 {
let err = c[j] - palette[k as usize * 3 + j] as f32;
if x + 1 < w {
cur[e + 3 + j] += err * (7.0 / 16.0);
nxt[e + 3 + j] += err * (1.0 / 16.0);
}
if x > 0 {
nxt[e - 3 + j] += err * (3.0 / 16.0);
}
nxt[e + j] += err * (5.0 / 16.0);
}
}
cur.copy_from_slice(&nxt);
nxt.fill(0.0);
}
}
/// The export dithers unless told not to: without it every gradient wallpaper bands.
#[test]
fn gif_export_dithers_by_default() {
assert!(GifExportParams::default().dither);
}
/// `GifWriter::new` rejects zero dimensions.
#[test]
fn gif_writer_rejects_zero_dimensions() {
let mut buf = Vec::new();
assert!(GifWriter::new(&mut buf, 0, 100).is_err());
assert!(GifWriter::new(&mut buf, 100, 0).is_err());
}
/// Sub-block writer chops a 600-byte payload into 3 blocks
/// (255 + 255 + 90). The terminator byte is written by the
/// caller, not by `write_sub_blocks` itself — it's a
/// stream-of-sub-blocks, and the terminator's position is a
/// concern of the GIF89a container.
#[test]
fn sub_blocks_chop_at_255() {
let mut buf = Vec::new();
let payload = vec![0xAAu8; 600];
write_sub_blocks(&mut Cursor::new(&mut buf), &payload).unwrap();
// 3 size bytes (255, 255, 90) + 600 payload bytes = 603.
assert_eq!(buf.len(), 603);
assert_eq!(buf[0], 255);
assert_eq!(buf[256], 255); // start of the second block
assert_eq!(buf[512], 90); // start of the third block
// No terminator in `write_sub_blocks` itself — the
// last byte is the last data byte of the third block.
assert_eq!(*buf.last().unwrap(), 0xAA);
}
}