Skip to main content

threers_codec/gif/
mod.rs

1//! GIF89a animated GIF encoder — pure Rust, wasm-safe.
2//!
3//! Companion to [`crate::apng`]: same RGBA frame API, with production
4//! knobs for palette size, transparency, dithering, dirty-rect differencing,
5//! local/global palettes, octree quantization, disposal, lossy differencing,
6//! LZW clear policies, comments, and interlacing.
7//!
8//! [`GifWriter`] writes local-palette GIFs incrementally to any [`std::io::Write`].
9//! Decoding is provided by [`decode`] (`GifDecoder` / [`decode_gif`]).
10//!
11//! # Streaming
12//!
13//! [`GifEncoder::encode_iter`] consumes frames as they arrive. With
14//! [`PaletteMode::Local`] (default for streaming) only the previous canvas is
15//! retained — no full-sequence buffer. [`PaletteMode::Global`] still collects
16//! frames once to build a shared palette.
17//!
18//! # Examples
19//!
20//! ```
21//! # #[cfg(feature = "gif")] {
22//! use threers_codec::gif::{GifEncoder, PaletteMode};
23//! let mut enc = GifEncoder::new(2, 2, 1)
24//!     .colors(4)
25//!     .dither(false)
26//!     .diff_rects(false)
27//!     .palette_mode(PaletteMode::Global)
28//!     .transparency(false);
29//! enc.add_frame(&[255, 0, 0, 255, 0, 255, 0, 255, 0, 0, 255, 255, 255, 255, 0, 255], 1, 10);
30//! let gif = enc.finish();
31//! assert_eq!(&gif[..6], b"GIF89a");
32//! # }
33//! ```
34
35pub mod decode;
36
37#[allow(deprecated)]
38pub use decode::DecodedFrame;
39pub use decode::{
40    decode_gif, DisposalMethod, GifDecoder, GifError, GifFrame, GifFrameMeta, GifInfo, GifVersion,
41};
42
43use std::collections::HashMap;
44use std::io::{self, Write};
45
46/// How a frame's pixels are disposed before the following frame.
47///
48/// Matches the GIF89a Graphic Control Extension disposal field. [`Self::Auto`]
49/// picks Keep / Background / Previous from the composited canvas to shrink
50/// subsequent dirty rectangles while remaining decoder-compatible.
51#[derive(Clone, Copy, Debug, PartialEq, Eq, Default)]
52pub enum DisposalMode {
53    /// Choose Keep, Background, or Previous based on the next frame.
54    #[default]
55    Auto,
56    /// Disposal 0 — no action required after the frame.
57    None,
58    /// Disposal 1 — leave pixels in place for the next frame.
59    Keep,
60    /// Disposal 2 — restore the frame rectangle to background (transparent).
61    Background,
62    /// Disposal 3 — restore the canvas as it was before this frame was drawn.
63    Previous,
64}
65
66/// Policy used to clear the GIF LZW dictionary during compression.
67#[derive(Clone, Copy, Debug, PartialEq, Eq, Default)]
68pub enum LzwClearMode {
69    /// Clear as soon as the table fills (4096 entries). Broadest compatibility.
70    #[default]
71    WhenFull,
72    /// Freeze inserts at capacity; clear when the match rate drops.
73    Deferred,
74    /// May clear before the table fills when compression ratio worsens.
75    Adaptive,
76}
77
78/// How the color table(s) are chosen.
79#[derive(Clone, Copy, Debug, PartialEq, Eq, Default)]
80pub enum PaletteMode {
81    /// One global palette from all frames (best size when colors are shared).
82    Global,
83    /// Per-frame local color table (better quality on scene changes).
84    #[default]
85    Local,
86    /// Global when it fits; otherwise fall back to local for that frame.
87    Auto,
88}
89
90/// Quantization algorithm for reducing opaque colors.
91#[derive(Clone, Copy, Debug, PartialEq, Eq, Default)]
92pub enum QuantizerKind {
93    /// Gervautz–Purgathofer octree (default — good quality / speed).
94    #[default]
95    Octree,
96    /// Classic median-cut.
97    MedianCut,
98}
99
100/// Tunables for [`GifEncoder`] / [`GifWriter`] / [`encode_gif`].
101#[derive(Clone, Debug)]
102pub struct GifOptions {
103    /// Max palette entries including the transparent slot (`2..=256`).
104    pub max_colors: u16,
105    /// Map low-alpha pixels to a reserved transparent index.
106    pub transparency: bool,
107    /// `alpha < threshold` → transparent when [`Self::transparency`] is on.
108    pub alpha_threshold: u8,
109    /// Floyd–Steinberg dithering after quantization.
110    pub dither: bool,
111    /// Encode only changed bounding boxes; unchanged pixels → transparent.
112    pub diff_rects: bool,
113    /// Global, per-frame local, or automatic palette selection.
114    pub palette_mode: PaletteMode,
115    /// Octree (default) or median-cut color reduction.
116    pub quantizer: QuantizerKind,
117    /// Frame disposal policy (see [`DisposalMode`]).
118    pub disposal: DisposalMode,
119    /// Loss tolerance (`0..=100`) for dirty-pixel detection and index coherence.
120    /// `0` is lossless relative to the other options; higher values shrink files.
121    pub lossy: u8,
122    /// When to emit LZW clear codes (see [`LzwClearMode`]).
123    pub lzw_clear: LzwClearMode,
124    /// Write frames with the GIF interlacing flag and 4-pass row order.
125    pub interlace: bool,
126    /// Comment extension payloads written after the header.
127    pub comments: Vec<Vec<u8>>,
128}
129
130impl Default for GifOptions {
131    fn default() -> Self {
132        Self {
133            max_colors: 256,
134            transparency: true,
135            alpha_threshold: 128,
136            dither: true,
137            diff_rects: true,
138            palette_mode: PaletteMode::Local,
139            quantizer: QuantizerKind::Octree,
140            disposal: DisposalMode::Auto,
141            lossy: 0,
142            lzw_clear: LzwClearMode::WhenFull,
143            interlace: false,
144            comments: Vec::new(),
145        }
146    }
147}
148
149impl GifOptions {
150    /// Clamp palette size to `2..=256`.
151    pub fn colors(mut self, n: u16) -> Self {
152        assert!(
153            (2..=256).contains(&n),
154            "GIF palette size must be 2..=256 (got {n})"
155        );
156        self.max_colors = n;
157        self
158    }
159    /// Enable or disable the transparent palette index.
160    pub fn transparency(mut self, on: bool) -> Self {
161        self.transparency = on;
162        self
163    }
164    /// Alpha cutoff for treating a pixel as transparent.
165    pub fn alpha_threshold(mut self, t: u8) -> Self {
166        self.alpha_threshold = t;
167        self
168    }
169    /// Enable or disable Floyd–Steinberg dithering.
170    pub fn dither(mut self, on: bool) -> Self {
171        self.dither = on;
172        self
173    }
174    /// Enable or disable dirty-rectangle frame differencing.
175    pub fn diff_rects(mut self, on: bool) -> Self {
176        self.diff_rects = on;
177        self
178    }
179    /// Select global / local / auto palettes.
180    pub fn palette_mode(mut self, mode: PaletteMode) -> Self {
181        self.palette_mode = mode;
182        self
183    }
184    /// Select the quantizer used when colors exceed the palette budget.
185    pub fn quantizer(mut self, q: QuantizerKind) -> Self {
186        self.quantizer = q;
187        self
188    }
189    /// Override automatic disposal selection.
190    pub fn disposal(mut self, mode: DisposalMode) -> Self {
191        self.disposal = mode;
192        self
193    }
194    /// Lossiness `0..=100` (`0` preserves exact indexing decisions).
195    pub fn lossy(mut self, loss: u8) -> Self {
196        assert!(loss <= 100, "GIF lossy setting must be 0..=100");
197        self.lossy = loss;
198        self
199    }
200    /// LZW dictionary clear policy.
201    pub fn lzw_clear(mut self, mode: LzwClearMode) -> Self {
202        self.lzw_clear = mode;
203        self
204    }
205    /// Emit interlaced image descriptors.
206    pub fn interlace(mut self, on: bool) -> Self {
207        self.interlace = on;
208        self
209    }
210    /// Append a GIF comment extension (may be called multiple times).
211    pub fn comment(mut self, bytes: impl AsRef<[u8]>) -> Self {
212        self.comments.push(bytes.as_ref().to_vec());
213        self
214    }
215}
216
217struct Frame {
218    rgba: Vec<u8>,
219    delay_num: u16,
220    delay_den: u16,
221}
222
223/// Builds an animated GIF from RGBA frames.
224///
225/// Buffer frames with [`Self::add_frame`] / [`Self::add_frame_owned`], then
226/// [`Self::finish`], or stream with [`Self::encode_iter`]. For writing directly
227/// to a file or socket, prefer [`GifWriter`].
228pub struct GifEncoder {
229    width: u32,
230    height: u32,
231    plays: u32,
232    opts: GifOptions,
233    frames: Vec<Frame>,
234}
235
236/// Incremental GIF writer using per-frame local palettes.
237///
238/// Writes the header immediately, then one image block per [`Self::write_frame`].
239/// Does **not** support [`PaletteMode::Global`] (returns `InvalidInput`);
240/// [`PaletteMode::Auto`] is treated as local.
241///
242/// # Example
243///
244/// ```
245/// # #[cfg(feature = "gif")] {
246/// use threers_codec::gif::{GifOptions, GifWriter, PaletteMode};
247/// let mut out = Vec::new();
248/// let opts = GifOptions::default()
249///     .colors(8)
250///     .dither(false)
251///     .diff_rects(false)
252///     .transparency(false)
253///     .palette_mode(PaletteMode::Local);
254/// let mut w = GifWriter::new(&mut out, 2, 2, 1, opts).unwrap();
255/// w.write_frame(&[255, 0, 0, 255, 0, 255, 0, 255, 0, 0, 255, 255, 255, 255, 0, 255], 1, 10).unwrap();
256/// w.finish().unwrap();
257/// assert_eq!(&out[..6], b"GIF89a");
258/// # }
259/// ```
260pub struct GifWriter<W: Write> {
261    out: W,
262    width: usize,
263    height: usize,
264    opts: GifOptions,
265    canvas: Vec<u8>,
266    pending: Option<Frame>,
267    frames_written: usize,
268}
269
270impl<W: Write> GifWriter<W> {
271    /// Create a writer and emit the GIF header (+ optional Netscape loop / comments).
272    pub fn new(
273        mut out: W,
274        width: u32,
275        height: u32,
276        plays: u32,
277        mut opts: GifOptions,
278    ) -> io::Result<Self> {
279        if width == 0 || height == 0 || width > u16::MAX as u32 || height > u16::MAX as u32 {
280            return Err(io::Error::new(
281                io::ErrorKind::InvalidInput,
282                "invalid GIF dimensions",
283            ));
284        }
285        if opts.palette_mode == PaletteMode::Global {
286            return Err(io::Error::new(
287                io::ErrorKind::InvalidInput,
288                "GifWriter does not support global palettes",
289            ));
290        }
291        opts.palette_mode = PaletteMode::Local;
292        write_header(&mut out, width, height, plays, None, 0)?;
293        write_comments(&mut out, &opts.comments)?;
294        Ok(Self {
295            out,
296            width: width as usize,
297            height: height as usize,
298            canvas: vec![0; width as usize * height as usize * 4],
299            opts,
300            pending: None,
301            frames_written: 0,
302        })
303    }
304
305    /// Queue one RGBA frame. Delay is `delay_num / delay_den` seconds
306    /// (converted to GIF centiseconds). The previous frame may be flushed now
307    /// so automatic disposal can inspect this frame.
308    pub fn write_frame(&mut self, rgba: &[u8], delay_num: u16, delay_den: u16) -> io::Result<()> {
309        if rgba.len() != self.canvas.len() {
310            return Err(io::Error::new(io::ErrorKind::InvalidInput, "rgba size"));
311        }
312        if self.pending.is_some() {
313            self.flush_pending(Some(rgba))?;
314        }
315        self.pending = Some(Frame {
316            rgba: rgba.to_vec(),
317            delay_num,
318            delay_den: delay_den.max(1),
319        });
320        Ok(())
321    }
322
323    /// Flush any pending frame, then write a Comment Extension block.
324    pub fn write_comment(&mut self, text: &[u8]) -> io::Result<()> {
325        self.flush_pending(None)?;
326        write_comment(&mut self.out, text)
327    }
328
329    fn flush_pending(&mut self, next: Option<&[u8]>) -> io::Result<()> {
330        let Some(frame) = self.pending.take() else {
331            return Ok(());
332        };
333        let previous = (self.frames_written != 0).then_some(self.canvas.as_slice());
334        let (rect, indexed, palette, transparent, _) = prepare_frame(
335            self.width,
336            self.height,
337            &frame.rgba,
338            previous,
339            &self.opts,
340            true,
341        );
342        let disposal = choose_disposal(
343            self.width,
344            self.height,
345            &self.canvas,
346            &frame.rgba,
347            next,
348            rect,
349            transparent.is_some(),
350            &self.opts,
351        );
352        write_image(
353            &mut self.out,
354            delay_to_cs(frame.delay_num, frame.delay_den),
355            disposal,
356            transparent,
357            rect,
358            &indexed,
359            &palette,
360            true,
361            &self.opts,
362        )?;
363        advance_canvas(
364            self.width,
365            self.height,
366            &mut self.canvas,
367            &frame.rgba,
368            rect,
369            disposal,
370            &self.opts,
371        );
372        self.frames_written += 1;
373        Ok(())
374    }
375
376    /// Flush the last pending frame, write the trailer (`0x3B`), and return the
377    /// underlying writer.
378    pub fn finish(mut self) -> io::Result<W> {
379        self.flush_pending(None)?;
380        self.out.write_all(&[0x3B])?;
381        Ok(self.out)
382    }
383}
384
385impl GifEncoder {
386    /// New encoder; defaults enable dithering, dirty-rects, and local palettes.
387    pub fn new(width: u32, height: u32, plays: u32) -> Self {
388        assert!(width > 0 && height > 0 && width <= 0xFFFF && height <= 0xFFFF);
389        Self {
390            width,
391            height,
392            plays,
393            opts: GifOptions::default(),
394            frames: Vec::new(),
395        }
396    }
397
398    /// Replace every option at once.
399    pub fn options(mut self, opts: GifOptions) -> Self {
400        self.opts = opts;
401        self
402    }
403
404    /// [`GifOptions::colors`].
405    pub fn colors(mut self, n: u16) -> Self {
406        self.opts = self.opts.colors(n);
407        self
408    }
409    /// [`GifOptions::transparency`].
410    pub fn transparency(mut self, on: bool) -> Self {
411        self.opts = self.opts.transparency(on);
412        self
413    }
414    /// [`GifOptions::alpha_threshold`].
415    pub fn alpha_threshold(mut self, t: u8) -> Self {
416        self.opts = self.opts.alpha_threshold(t);
417        self
418    }
419    /// [`GifOptions::dither`].
420    pub fn dither(mut self, on: bool) -> Self {
421        self.opts = self.opts.dither(on);
422        self
423    }
424    /// [`GifOptions::diff_rects`].
425    pub fn diff_rects(mut self, on: bool) -> Self {
426        self.opts = self.opts.diff_rects(on);
427        self
428    }
429    /// [`GifOptions::palette_mode`].
430    pub fn palette_mode(mut self, mode: PaletteMode) -> Self {
431        self.opts = self.opts.palette_mode(mode);
432        self
433    }
434    /// [`GifOptions::quantizer`].
435    pub fn quantizer(mut self, q: QuantizerKind) -> Self {
436        self.opts = self.opts.quantizer(q);
437        self
438    }
439    /// [`GifOptions::disposal`].
440    pub fn disposal(mut self, mode: DisposalMode) -> Self {
441        self.opts = self.opts.disposal(mode);
442        self
443    }
444    /// [`GifOptions::lossy`].
445    pub fn lossy(mut self, loss: u8) -> Self {
446        self.opts = self.opts.lossy(loss);
447        self
448    }
449    /// [`GifOptions::lzw_clear`].
450    pub fn lzw_clear(mut self, mode: LzwClearMode) -> Self {
451        self.opts = self.opts.lzw_clear(mode);
452        self
453    }
454    /// [`GifOptions::interlace`].
455    pub fn interlace(mut self, on: bool) -> Self {
456        self.opts = self.opts.interlace(on);
457        self
458    }
459    /// [`GifOptions::comment`].
460    pub fn comment(mut self, bytes: impl AsRef<[u8]>) -> Self {
461        self.opts = self.opts.comment(bytes);
462        self
463    }
464
465    /// Add a frame by moving RGBA bytes (no extra clone of the pixel buffer).
466    pub fn add_frame_owned(&mut self, rgba: Vec<u8>, delay_num: u16, delay_den: u16) {
467        assert_eq!(
468            rgba.len(),
469            (self.width * self.height * 4) as usize,
470            "rgba size"
471        );
472        self.frames.push(Frame {
473            rgba,
474            delay_num,
475            delay_den: delay_den.max(1),
476        });
477    }
478
479    /// Add a frame from a borrowed RGBA buffer (one copy into the encoder).
480    pub fn add_frame(&mut self, rgba: &[u8], delay_num: u16, delay_den: u16) {
481        self.add_frame_owned(rgba.to_vec(), delay_num, delay_den);
482    }
483
484    /// Serialize all buffered frames.
485    pub fn finish(self) -> Vec<u8> {
486        assert!(!self.frames.is_empty(), "GIF needs at least one frame");
487        let frames = self
488            .frames
489            .into_iter()
490            .map(|f| (f.rgba, f.delay_num, f.delay_den));
491        encode_sequence(self.width, self.height, self.plays, &self.opts, frames)
492    }
493
494    /// Encode an iterator of `(rgba, delay_num, delay_den)` frames.
495    ///
496    /// With [`PaletteMode::Local`] this streams (keeps only the previous canvas).
497    /// With [`PaletteMode::Global`] / [`PaletteMode::Auto`] it may buffer frames
498    /// to build a shared palette.
499    pub fn encode_iter<I>(self, frames: I) -> Vec<u8>
500    where
501        I: IntoIterator<Item = (Vec<u8>, u16, u16)>,
502    {
503        encode_sequence(self.width, self.height, self.plays, &self.opts, frames)
504    }
505}
506
507/// Encode RGBA frames to a GIF byte stream (same options as [`GifEncoder`]).
508pub fn encode_gif<I>(width: u32, height: u32, plays: u32, opts: &GifOptions, frames: I) -> Vec<u8>
509where
510    I: IntoIterator<Item = (Vec<u8>, u16, u16)>,
511{
512    assert!(width > 0 && height > 0 && width <= 0xFFFF && height <= 0xFFFF);
513    encode_sequence(width, height, plays, opts, frames)
514}
515
516fn encode_sequence<I>(width: u32, height: u32, plays: u32, opts: &GifOptions, frames: I) -> Vec<u8>
517where
518    I: IntoIterator<Item = (Vec<u8>, u16, u16)>,
519{
520    let w = width as usize;
521    let h = height as usize;
522    let expected = w * h * 4;
523
524    match opts.palette_mode {
525        PaletteMode::Local => encode_streaming(width, height, plays, opts, frames, expected),
526        PaletteMode::Global | PaletteMode::Auto => {
527            let collected: Vec<_> = frames
528                .into_iter()
529                .map(|(rgba, n, d)| {
530                    assert_eq!(rgba.len(), expected, "rgba size");
531                    (rgba, n, d.max(1))
532                })
533                .collect();
534            assert!(!collected.is_empty(), "GIF needs at least one frame");
535            if opts.palette_mode == PaletteMode::Global {
536                encode_with_global(width, height, plays, opts, &collected)
537            } else {
538                // Auto: try global; if any frame's opaque unique colors exceed
539                // budget badly, still use global for shared look — local only
540                // when global palette is a poor fit for a frame (re-encode that
541                // frame with LCT). Simplified: use global if total unique ≤ budget,
542                // else stream local.
543                let opaque_unique = count_opaque_unique(&collected, opts);
544                if opaque_unique <= opts.max_colors as usize {
545                    encode_with_global(width, height, plays, opts, &collected)
546                } else {
547                    encode_streaming(width, height, plays, opts, collected, expected)
548                }
549            }
550        }
551    }
552}
553
554fn count_opaque_unique(frames: &[(Vec<u8>, u16, u16)], opts: &GifOptions) -> usize {
555    let mut set = HashMap::<[u8; 3], ()>::new();
556    for (rgba, _, _) in frames {
557        for px in rgba.as_chunks::<4>().0 {
558            if !(opts.transparency && px[3] < opts.alpha_threshold) {
559                set.insert([px[0], px[1], px[2]], ());
560            }
561        }
562    }
563    set.len()
564}
565
566fn encode_streaming<I>(
567    width: u32,
568    height: u32,
569    plays: u32,
570    opts: &GifOptions,
571    frames: I,
572    expected: usize,
573) -> Vec<u8>
574where
575    I: IntoIterator<Item = (Vec<u8>, u16, u16)>,
576{
577    let w = width as usize;
578    let h = height as usize;
579    let mut out = Vec::new();
580    write_header(&mut out, width, height, plays, /*gct*/ None, 0).unwrap();
581    write_comments(&mut out, &opts.comments).unwrap();
582    let mut iter = frames.into_iter();
583    let mut pending = iter.next().map(|(r, n, d)| (r, n, d.max(1)));
584    assert!(pending.is_some(), "GIF needs at least one frame");
585    let mut canvas = vec![0u8; expected];
586    let mut frame_no = 0usize;
587    while let Some((rgba, dnum, dden)) = pending.take() {
588        assert_eq!(rgba.len(), expected, "rgba size");
589        pending = iter.next().map(|(r, n, d)| (r, n, d.max(1)));
590        if let Some((next, _, _)) = &pending {
591            assert_eq!(next.len(), expected, "rgba size");
592        }
593        let (rect, indexed, palette, transparent, _) = prepare_frame(
594            w,
595            h,
596            &rgba,
597            (frame_no != 0).then_some(canvas.as_slice()),
598            opts,
599            true,
600        );
601        let disposal = choose_disposal(
602            w,
603            h,
604            &canvas,
605            &rgba,
606            pending.as_ref().map(|f| f.0.as_slice()),
607            rect,
608            transparent.is_some(),
609            opts,
610        );
611        write_image(
612            &mut out,
613            delay_to_cs(dnum, dden),
614            disposal,
615            transparent,
616            rect,
617            &indexed,
618            &palette,
619            true,
620            opts,
621        )
622        .unwrap();
623        advance_canvas(w, h, &mut canvas, &rgba, rect, disposal, opts);
624        frame_no += 1;
625    }
626    out.push(0x3B);
627    out
628}
629
630fn encode_with_global(
631    width: u32,
632    height: u32,
633    plays: u32,
634    opts: &GifOptions,
635    frames: &[(Vec<u8>, u16, u16)],
636) -> Vec<u8> {
637    let w = width as usize;
638    let h = height as usize;
639    let (global_pal, global_tr) = build_palette_from_frames(frames, opts);
640    let bg = global_tr.unwrap_or(0);
641    let mut out = Vec::new();
642    write_header(&mut out, width, height, plays, Some(&global_pal), bg).unwrap();
643    write_comments(&mut out, &opts.comments).unwrap();
644    let mut canvas = vec![0u8; w * h * 4];
645
646    for (frame_no, (rgba, dnum, dden)) in frames.iter().enumerate() {
647        let delay = delay_to_cs(*dnum, *dden);
648        let (rect, indexed, _pal, transparent, _) = prepare_frame_with_palette(
649            w,
650            h,
651            rgba,
652            (frame_no != 0).then_some(canvas.as_slice()),
653            opts,
654            &global_pal,
655            global_tr,
656            false,
657        );
658        let disposal = choose_disposal(
659            w,
660            h,
661            &canvas,
662            rgba,
663            frames.get(frame_no + 1).map(|f| f.0.as_slice()),
664            rect,
665            transparent.or(global_tr).is_some(),
666            opts,
667        );
668        write_image(
669            &mut out,
670            delay,
671            disposal,
672            transparent.or(global_tr),
673            rect,
674            &indexed,
675            &global_pal,
676            false,
677            opts,
678        )
679        .unwrap();
680        advance_canvas(w, h, &mut canvas, rgba, rect, disposal, opts);
681    }
682    out.push(0x3B);
683    out
684}
685
686#[derive(Clone, Copy)]
687struct Rect {
688    x: u16,
689    y: u16,
690    w: u16,
691    h: u16,
692}
693
694fn full_rect(w: usize, h: usize) -> Rect {
695    Rect {
696        x: 0,
697        y: 0,
698        w: w as u16,
699        h: h as u16,
700    }
701}
702
703#[allow(clippy::too_many_arguments)]
704fn choose_disposal(
705    w: usize,
706    h: usize,
707    canvas: &[u8],
708    rgba: &[u8],
709    next: Option<&[u8]>,
710    rect: Rect,
711    has_transparency: bool,
712    opts: &GifOptions,
713) -> u8 {
714    match opts.disposal {
715        DisposalMode::None => return 0,
716        DisposalMode::Keep => return 1,
717        DisposalMode::Background => return 2,
718        DisposalMode::Previous => return 3,
719        DisposalMode::Auto => {}
720    }
721
722    let initially_empty = canvas.as_chunks::<4>().0.iter().all(|p| p[3] == 0);
723    if initially_empty && has_transparency {
724        return 2;
725    }
726    let Some(next) = next else {
727        return if initially_empty {
728            0
729        } else if has_transparency {
730            2
731        } else {
732            1
733        };
734    };
735
736    let mut displayed = canvas.to_vec();
737    compose_source(&mut displayed, rgba, opts);
738    let mut background = displayed.clone();
739    clear_rect(w, &mut background, rect);
740    let previous = canvas;
741
742    let score = |candidate: &[u8]| -> usize {
743        let mut min_x = w;
744        let mut min_y = h;
745        let mut max_x = 0usize;
746        let mut max_y = 0usize;
747        let mut changed = false;
748        for (pixel, (desired, under)) in next
749            .as_chunks::<4>()
750            .0
751            .iter()
752            .zip(candidate.as_chunks::<4>().0)
753            .enumerate()
754        {
755            let desired_tr = opts.transparency && desired[3] < opts.alpha_threshold;
756            let under_tr = opts.transparency && under[3] < opts.alpha_threshold;
757            // A transparent source pixel cannot erase an opaque canvas pixel.
758            if desired_tr && !under_tr {
759                return usize::MAX;
760            }
761            if pixels_differ(desired, under, opts) {
762                let x = pixel % w;
763                let y = pixel / w;
764                changed = true;
765                min_x = min_x.min(x);
766                min_y = min_y.min(y);
767                max_x = max_x.max(x);
768                max_y = max_y.max(y);
769            }
770        }
771        if changed {
772            (max_x - min_x + 1) * (max_y - min_y + 1)
773        } else {
774            0
775        }
776    };
777    let candidates = [
778        (1u8, score(&displayed)),
779        (2, score(&background)),
780        (3, score(previous)),
781    ];
782    let best = candidates
783        .into_iter()
784        .min_by_key(|(mode, area)| {
785            (
786                *area,
787                match mode {
788                    1 => 0,
789                    2 => 1,
790                    _ => 2,
791                },
792            )
793        })
794        .unwrap()
795        .0;
796    if initially_empty && best == 1 {
797        0
798    } else {
799        best
800    }
801}
802
803fn compose_source(canvas: &mut [u8], rgba: &[u8], opts: &GifOptions) {
804    for (dst, src) in canvas
805        .as_chunks_mut::<4>()
806        .0
807        .iter_mut()
808        .zip(rgba.as_chunks::<4>().0)
809    {
810        if !(opts.transparency && src[3] < opts.alpha_threshold)
811            && (dst[3] == 0 || pixels_differ(dst, src, opts))
812        {
813            dst.copy_from_slice(src);
814            dst[3] = 255;
815        }
816    }
817}
818
819fn clear_rect(stride_w: usize, canvas: &mut [u8], rect: Rect) {
820    for y in rect.y as usize..rect.y as usize + rect.h as usize {
821        for x in rect.x as usize..rect.x as usize + rect.w as usize {
822            canvas[(y * stride_w + x) * 4..(y * stride_w + x + 1) * 4].fill(0);
823        }
824    }
825}
826
827fn advance_canvas(
828    w: usize,
829    _h: usize,
830    canvas: &mut [u8],
831    rgba: &[u8],
832    rect: Rect,
833    disposal: u8,
834    opts: &GifOptions,
835) {
836    let previous = (disposal == 3).then(|| canvas.to_vec());
837    compose_source(canvas, rgba, opts);
838    if disposal == 2 {
839        clear_rect(w, canvas, rect);
840    } else if let Some(previous) = previous {
841        canvas.copy_from_slice(&previous);
842    }
843}
844
845/// Returns (rect, indices row-major in rect, palette, transparent, disposal).
846fn prepare_frame(
847    w: usize,
848    h: usize,
849    rgba: &[u8],
850    prev: Option<&[u8]>,
851    opts: &GifOptions,
852    local: bool,
853) -> (Rect, Vec<u8>, Vec<[u8; 3]>, Option<u8>, u8) {
854    let (palette, transparent) = if local {
855        build_palette_region(rgba, w, h, full_rect(w, h), opts)
856    } else {
857        unreachable!()
858    };
859    prepare_frame_with_palette(w, h, rgba, prev, opts, &palette, transparent, local)
860}
861
862#[allow(clippy::too_many_arguments)]
863fn prepare_frame_with_palette(
864    w: usize,
865    h: usize,
866    rgba: &[u8],
867    prev: Option<&[u8]>,
868    opts: &GifOptions,
869    palette: &[[u8; 3]],
870    transparent: Option<u8>,
871    _local: bool,
872) -> (Rect, Vec<u8>, Vec<[u8; 3]>, Option<u8>, u8) {
873    let first = prev.is_none();
874    let mut tr = transparent;
875
876    // Dirty rect against previous canvas.
877    let rect = if opts.diff_rects && !first {
878        dirty_rect(w, h, rgba, prev.unwrap(), opts).unwrap_or_else(|| full_rect(w, h))
879    } else {
880        full_rect(w, h)
881    };
882
883    // Rebuild local palette from the dirty region when local + diff.
884    let palette_owned: Vec<[u8; 3]>;
885    let pal: &[[u8; 3]] = if _local && opts.diff_rects && !first {
886        let (p, t) = build_palette_region(rgba, w, h, rect, opts);
887        tr = t.or(tr);
888        palette_owned = p;
889        &palette_owned
890    } else {
891        palette_owned = palette.to_vec();
892        &palette_owned
893    };
894
895    // Ensure we have a transparent index when using diff-rects (unchanged → skip).
896    let need_diff_tr = opts.diff_rects && !first;
897    let tr = if need_diff_tr && tr.is_none() {
898        // Steal last slot / append if room.
899        let mut p = palette_owned.clone();
900        let idx = if p.len() < opts.max_colors as usize {
901            let i = p.len();
902            p.push([0, 0, 0]);
903            i as u8
904        } else {
905            (p.len() - 1) as u8
906        };
907        let indexed = index_region(w, h, rgba, prev, rect, &p, Some(idx), opts);
908        let disposal = 1; // do not dispose
909        return (rect, indexed, p, Some(idx), disposal);
910    } else {
911        tr
912    };
913
914    let indexed = index_region(w, h, rgba, prev, rect, pal, tr, opts);
915
916    // Disposal: first transparent frame → restore bg; diff frames → keep;
917    // full opaque replace → none.
918    let disposal = if first && tr.is_some() {
919        2
920    } else if opts.diff_rects && !first {
921        1
922    } else if tr.is_some() {
923        2
924    } else {
925        0
926    };
927
928    (rect, indexed, pal.to_vec(), tr, disposal)
929}
930
931fn dirty_rect(w: usize, h: usize, cur: &[u8], prev: &[u8], opts: &GifOptions) -> Option<Rect> {
932    let mut min_x = w;
933    let mut min_y = h;
934    let mut max_x = 0usize;
935    let mut max_y = 0usize;
936    let mut any = false;
937    for y in 0..h {
938        for x in 0..w {
939            let i = (y * w + x) * 4;
940            if pixels_differ(&cur[i..i + 4], &prev[i..i + 4], opts) {
941                any = true;
942                min_x = min_x.min(x);
943                min_y = min_y.min(y);
944                max_x = max_x.max(x);
945                max_y = max_y.max(y);
946            }
947        }
948    }
949    if !any {
950        // Zero-delay empty change: encode 1×1 transparent.
951        return Some(Rect {
952            x: 0,
953            y: 0,
954            w: 1,
955            h: 1,
956        });
957    }
958    Some(Rect {
959        x: min_x as u16,
960        y: min_y as u16,
961        w: (max_x - min_x + 1) as u16,
962        h: (max_y - min_y + 1) as u16,
963    })
964}
965
966fn pixels_differ(a: &[u8], b: &[u8], opts: &GifOptions) -> bool {
967    let a_tr = opts.transparency && a[3] < opts.alpha_threshold;
968    let b_tr = opts.transparency && b[3] < opts.alpha_threshold;
969    if a_tr != b_tr {
970        return true;
971    }
972    if a_tr {
973        return false;
974    }
975    if opts.lossy == 0 {
976        return a[0] != b[0] || a[1] != b[1] || a[2] != b[2];
977    }
978    dist2([a[0], a[1], a[2]], [b[0], b[1], b[2]]) > lossy_dist2(opts.lossy)
979}
980
981#[allow(clippy::too_many_arguments)]
982fn index_region(
983    stride_w: usize,
984    _stride_h: usize,
985    rgba: &[u8],
986    prev: Option<&[u8]>,
987    rect: Rect,
988    palette: &[[u8; 3]],
989    transparent: Option<u8>,
990    opts: &GifOptions,
991) -> Vec<u8> {
992    let rw = rect.w as usize;
993    let rh = rect.h as usize;
994    let mut out = vec![0u8; rw * rh];
995
996    if opts.dither {
997        // Working buffer of RGB(A) errors as f32 in the rect.
998        let mut work = vec![0f32; rw * rh * 4];
999        for ly in 0..rh {
1000            for lx in 0..rw {
1001                let x = rect.x as usize + lx;
1002                let y = rect.y as usize + ly;
1003                let i = (y * stride_w + x) * 4;
1004                let o = (ly * rw + lx) * 4;
1005                work[o] = rgba[i] as f32;
1006                work[o + 1] = rgba[i + 1] as f32;
1007                work[o + 2] = rgba[i + 2] as f32;
1008                work[o + 3] = rgba[i + 3] as f32;
1009            }
1010        }
1011        for ly in 0..rh {
1012            for lx in 0..rw {
1013                let x = rect.x as usize + lx;
1014                let y = rect.y as usize + ly;
1015                let i = (y * stride_w + x) * 4;
1016                let o = (ly * rw + lx) * 4;
1017                let pi = ly * rw + lx;
1018
1019                // Unchanged vs previous → transparent (diff mode).
1020                if let (Some(prev), Some(ti)) = (prev, transparent)
1021                    && opts.diff_rects
1022                    && !pixels_differ(&rgba[i..i + 4], &prev[i..i + 4], opts)
1023                {
1024                    out[pi] = ti;
1025                    continue;
1026                }
1027                if let Some(t) = transparent
1028                    && opts.transparency
1029                    && work[o + 3] < opts.alpha_threshold as f32
1030                {
1031                    out[pi] = t;
1032                    continue;
1033                }
1034
1035                let rgb = [
1036                    work[o].clamp(0.0, 255.0).round() as u8,
1037                    work[o + 1].clamp(0.0, 255.0).round() as u8,
1038                    work[o + 2].clamp(0.0, 255.0).round() as u8,
1039                ];
1040                let neighbor = if lx > 0 {
1041                    Some(out[pi - 1])
1042                } else if ly > 0 {
1043                    Some(out[pi - rw])
1044                } else {
1045                    None
1046                };
1047                let idx = nearest_index_lossy(rgb, palette, transparent, neighbor, opts.lossy);
1048                out[pi] = idx;
1049                let q = palette[idx as usize];
1050                let er = work[o] - q[0] as f32;
1051                let eg = work[o + 1] - q[1] as f32;
1052                let eb = work[o + 2] - q[2] as f32;
1053                // Floyd–Steinberg
1054                let disperse = |work: &mut [f32], lx2: i32, ly2: i32, fr: f32| {
1055                    if lx2 < 0 || ly2 < 0 || lx2 >= rw as i32 || ly2 >= rh as i32 {
1056                        return;
1057                    }
1058                    let j = ((ly2 as usize) * rw + lx2 as usize) * 4;
1059                    work[j] += er * fr;
1060                    work[j + 1] += eg * fr;
1061                    work[j + 2] += eb * fr;
1062                };
1063                disperse(&mut work, lx as i32 + 1, ly as i32, 7.0 / 16.0);
1064                disperse(&mut work, lx as i32 - 1, ly as i32 + 1, 3.0 / 16.0);
1065                disperse(&mut work, lx as i32, ly as i32 + 1, 5.0 / 16.0);
1066                disperse(&mut work, lx as i32 + 1, ly as i32 + 1, 1.0 / 16.0);
1067            }
1068        }
1069    } else {
1070        for ly in 0..rh {
1071            for lx in 0..rw {
1072                let x = rect.x as usize + lx;
1073                let y = rect.y as usize + ly;
1074                let i = (y * stride_w + x) * 4;
1075                let pi = ly * rw + lx;
1076                if let (Some(prev), Some(ti)) = (prev, transparent)
1077                    && opts.diff_rects
1078                    && !pixels_differ(&rgba[i..i + 4], &prev[i..i + 4], opts)
1079                {
1080                    out[pi] = ti;
1081                    continue;
1082                }
1083                if let Some(t) =
1084                    transparent.filter(|_| opts.transparency && rgba[i + 3] < opts.alpha_threshold)
1085                {
1086                    out[pi] = t;
1087                } else {
1088                    let neighbor = if lx > 0 {
1089                        Some(out[pi - 1])
1090                    } else if ly > 0 {
1091                        Some(out[pi - rw])
1092                    } else {
1093                        None
1094                    };
1095                    out[pi] = nearest_index_lossy(
1096                        [rgba[i], rgba[i + 1], rgba[i + 2]],
1097                        palette,
1098                        transparent,
1099                        neighbor,
1100                        opts.lossy,
1101                    );
1102                }
1103            }
1104        }
1105    }
1106    out
1107}
1108
1109fn write_header(
1110    out: &mut impl Write,
1111    width: u32,
1112    height: u32,
1113    plays: u32,
1114    gct: Option<&[[u8; 3]]>,
1115    bg: u8,
1116) -> io::Result<()> {
1117    out.write_all(b"GIF89a")?;
1118    out.write_all(&(width as u16).to_le_bytes())?;
1119    out.write_all(&(height as u16).to_le_bytes())?;
1120    if let Some(pal) = gct {
1121        let bits = palette_bits(pal.len());
1122        let size = 1usize << bits;
1123        out.write_all(&[0x80 | (((bits - 1) as u8) << 4) | ((bits - 1) as u8), bg, 0])?;
1124        for i in 0..size {
1125            if i < pal.len() {
1126                out.write_all(&pal[i])?;
1127            } else {
1128                out.write_all(&[0, 0, 0])?;
1129            }
1130        }
1131    } else {
1132        // No global table — size bits 0, flag clear.
1133        out.write_all(&[0, 0, 0])?;
1134    }
1135
1136    if plays != 1 {
1137        out.write_all(&[0x21, 0xFF, 0x0B])?;
1138        out.write_all(b"NETSCAPE2.0")?;
1139        out.write_all(&[0x03, 0x01])?;
1140        let loops = if plays == 0 {
1141            0u16
1142        } else {
1143            plays.saturating_sub(1).min(u16::MAX as u32) as u16
1144        };
1145        out.write_all(&loops.to_le_bytes())?;
1146        out.write_all(&[0x00])?;
1147    }
1148    Ok(())
1149}
1150
1151#[allow(clippy::too_many_arguments)]
1152fn write_image(
1153    out: &mut impl Write,
1154    delay_cs: u16,
1155    disposal: u8,
1156    transparent: Option<u8>,
1157    rect: Rect,
1158    indices: &[u8],
1159    palette: &[[u8; 3]],
1160    local_table: bool,
1161    opts: &GifOptions,
1162) -> io::Result<()> {
1163    out.write_all(&[0x21, 0xF9, 0x04])?;
1164    let mut packed = (disposal & 7) << 2;
1165    if transparent.is_some() {
1166        packed |= 0x01;
1167    }
1168    out.write_all(&[packed])?;
1169    out.write_all(&delay_cs.to_le_bytes())?;
1170    out.write_all(&[transparent.unwrap_or(0), 0x00])?;
1171
1172    out.write_all(&[0x2C])?;
1173    out.write_all(&rect.x.to_le_bytes())?;
1174    out.write_all(&rect.y.to_le_bytes())?;
1175    out.write_all(&rect.w.to_le_bytes())?;
1176    out.write_all(&rect.h.to_le_bytes())?;
1177
1178    let bits = palette_bits(palette.len().max(2));
1179    let size = 1usize << bits;
1180    if local_table {
1181        out.write_all(&[0x80 | if opts.interlace { 0x40 } else { 0 } | ((bits - 1) as u8)])?;
1182        for i in 0..size {
1183            if i < palette.len() {
1184                out.write_all(&palette[i])?;
1185            } else {
1186                out.write_all(&[0, 0, 0])?;
1187            }
1188        }
1189    } else {
1190        out.write_all(&[if opts.interlace { 0x40 } else { 0 }])?;
1191    }
1192
1193    let min_code_size = bits.max(2) as u8;
1194    let reordered;
1195    let indices = if opts.interlace {
1196        reordered = interlace_indices(indices, rect.w as usize, rect.h as usize);
1197        &reordered
1198    } else {
1199        indices
1200    };
1201    let lzw = lzw_encode(indices, min_code_size, opts.lzw_clear);
1202    out.write_all(&[min_code_size])?;
1203    write_sub_blocks(out, &lzw)?;
1204    Ok(())
1205}
1206
1207fn interlace_indices(indices: &[u8], w: usize, h: usize) -> Vec<u8> {
1208    let mut out = Vec::with_capacity(indices.len());
1209    for (start, step) in [(0usize, 8usize), (4, 8), (2, 4), (1, 2)] {
1210        for y in (start..h).step_by(step) {
1211            out.extend_from_slice(&indices[y * w..(y + 1) * w]);
1212        }
1213    }
1214    out
1215}
1216
1217fn write_comment(out: &mut impl Write, text: &[u8]) -> io::Result<()> {
1218    out.write_all(&[0x21, 0xFE])?;
1219    write_sub_blocks(out, text)
1220}
1221
1222fn write_comments(out: &mut impl Write, comments: &[Vec<u8>]) -> io::Result<()> {
1223    for comment in comments {
1224        write_comment(out, comment)?;
1225    }
1226    Ok(())
1227}
1228
1229fn delay_to_cs(num: u16, den: u16) -> u16 {
1230    let cs = (u32::from(num) * 100) / u32::from(den.max(1));
1231    cs.min(u16::MAX as u32) as u16
1232}
1233
1234fn palette_bits(n: usize) -> usize {
1235    let mut b = 1;
1236    while (1 << b) < n.max(2) {
1237        b += 1;
1238    }
1239    b.clamp(1, 8)
1240}
1241
1242fn build_palette_from_frames(
1243    frames: &[(Vec<u8>, u16, u16)],
1244    opts: &GifOptions,
1245) -> (Vec<[u8; 3]>, Option<u8>) {
1246    let mut samples = Vec::new();
1247    let mut needs_tr = false;
1248    for (rgba, _, _) in frames {
1249        for px in rgba.as_chunks::<4>().0 {
1250            if opts.transparency && px[3] < opts.alpha_threshold {
1251                needs_tr = true;
1252            } else {
1253                samples.push([px[0], px[1], px[2]]);
1254            }
1255        }
1256    }
1257    finish_palette(samples, needs_tr, opts)
1258}
1259
1260fn build_palette_region(
1261    rgba: &[u8],
1262    w: usize,
1263    _h: usize,
1264    rect: Rect,
1265    opts: &GifOptions,
1266) -> (Vec<[u8; 3]>, Option<u8>) {
1267    let mut samples = Vec::new();
1268    let mut needs_tr = false;
1269    for ly in 0..rect.h as usize {
1270        for lx in 0..rect.w as usize {
1271            let x = rect.x as usize + lx;
1272            let y = rect.y as usize + ly;
1273            let i = (y * w + x) * 4;
1274            if opts.transparency && rgba[i + 3] < opts.alpha_threshold {
1275                needs_tr = true;
1276            } else {
1277                samples.push([rgba[i], rgba[i + 1], rgba[i + 2]]);
1278            }
1279        }
1280    }
1281    finish_palette(samples, needs_tr, opts)
1282}
1283
1284fn finish_palette(
1285    samples: Vec<[u8; 3]>,
1286    needs_tr: bool,
1287    opts: &GifOptions,
1288) -> (Vec<[u8; 3]>, Option<u8>) {
1289    let max_colors = opts.max_colors as usize;
1290    let max_opaque = if needs_tr {
1291        max_colors.saturating_sub(1).max(1)
1292    } else {
1293        max_colors
1294    };
1295
1296    // Fast path: unique colors already fit.
1297    let mut counts: HashMap<[u8; 3], u32> = HashMap::new();
1298    for c in &samples {
1299        *counts.entry(*c).or_insert(0) += 1;
1300    }
1301    let mut palette = if counts.len() <= max_opaque {
1302        let mut v: Vec<_> = counts.into_iter().collect();
1303        v.sort_by(|a, b| b.1.cmp(&a.1).then_with(|| a.0.cmp(&b.0)));
1304        v.into_iter().map(|(c, _)| c).collect()
1305    } else {
1306        match opts.quantizer {
1307            QuantizerKind::Octree => octree_quantize(&samples, max_opaque),
1308            QuantizerKind::MedianCut => {
1309                let mut v: Vec<_> = counts.into_iter().collect();
1310                v.sort_by(|a, b| b.1.cmp(&a.1).then_with(|| a.0.cmp(&b.0)));
1311                median_cut(&v, max_opaque)
1312            }
1313        }
1314    };
1315
1316    if palette.is_empty() {
1317        palette.push([0, 0, 0]);
1318    }
1319    if palette.len() > max_opaque {
1320        palette.truncate(max_opaque);
1321    }
1322
1323    let transparent = if needs_tr {
1324        let idx = palette.len();
1325        if idx < max_colors {
1326            palette.push([0, 0, 0]);
1327            Some(idx as u8)
1328        } else {
1329            Some((palette.len() - 1) as u8)
1330        }
1331    } else {
1332        None
1333    };
1334    (palette, transparent)
1335}
1336
1337// ---- Octree quantizer -------------------------------------------------------
1338
1339struct OctNode {
1340    children: [Option<Box<OctNode>>; 8],
1341    leaf: bool,
1342    count: u32,
1343    r: u64,
1344    g: u64,
1345    b: u64,
1346}
1347
1348impl OctNode {
1349    fn new_leaf() -> Self {
1350        Self {
1351            children: Default::default(),
1352            leaf: true,
1353            count: 0,
1354            r: 0,
1355            g: 0,
1356            b: 0,
1357        }
1358    }
1359    fn new_branch() -> Self {
1360        Self {
1361            children: Default::default(),
1362            leaf: false,
1363            count: 0,
1364            r: 0,
1365            g: 0,
1366            b: 0,
1367        }
1368    }
1369}
1370
1371fn octree_quantize(samples: &[[u8; 3]], max_colors: usize) -> Vec<[u8; 3]> {
1372    let mut root = OctNode::new_branch();
1373    let mut leaf_count = 0usize;
1374    for c in samples {
1375        insert_color(&mut root, *c, 0, &mut leaf_count);
1376        while leaf_count > max_colors {
1377            if !reduce_tree(&mut root, &mut leaf_count) {
1378                break;
1379            }
1380        }
1381    }
1382    let mut out = Vec::new();
1383    collect_leaves(&root, &mut out);
1384    if out.is_empty() {
1385        out.push([0, 0, 0]);
1386    }
1387    if out.len() > max_colors {
1388        out.truncate(max_colors);
1389    }
1390    out
1391}
1392
1393fn child_index(rgb: [u8; 3], level: u8) -> usize {
1394    let shift = 7 - level;
1395    (((rgb[0] >> shift) & 1) << 2 | ((rgb[1] >> shift) & 1) << 1 | ((rgb[2] >> shift) & 1)) as usize
1396}
1397
1398fn insert_color(node: &mut OctNode, rgb: [u8; 3], level: u8, leaf_count: &mut usize) {
1399    if node.leaf || level == 8 {
1400        if !node.leaf {
1401            node.leaf = true;
1402            *leaf_count += 1;
1403        }
1404        node.count += 1;
1405        node.r += rgb[0] as u64;
1406        node.g += rgb[1] as u64;
1407        node.b += rgb[2] as u64;
1408        return;
1409    }
1410    let i = child_index(rgb, level);
1411    if node.children[i].is_none() {
1412        if level == 7 {
1413            node.children[i] = Some(Box::new(OctNode::new_leaf()));
1414            *leaf_count += 1;
1415        } else {
1416            node.children[i] = Some(Box::new(OctNode::new_branch()));
1417        }
1418    }
1419    insert_color(
1420        node.children[i].as_mut().unwrap(),
1421        rgb,
1422        level + 1,
1423        leaf_count,
1424    );
1425}
1426
1427fn reduce_tree(node: &mut OctNode, leaf_count: &mut usize) -> bool {
1428    // Find a deepest foldable branch (has only leaf children) and fold it.
1429    if node.leaf {
1430        return false;
1431    }
1432    // Prefer reducing deeper first.
1433    for i in 0..8 {
1434        if let Some(ch) = node.children[i].as_mut()
1435            && !ch.leaf
1436            && reduce_tree(ch, leaf_count)
1437        {
1438            return true;
1439        }
1440    }
1441    let mut child_leaves = 0;
1442    let mut has_branch = false;
1443    for c in &node.children {
1444        match c {
1445            Some(ch) if ch.leaf => child_leaves += 1,
1446            Some(ch) if !ch.leaf => has_branch = true,
1447            _ => {}
1448        }
1449    }
1450    if !has_branch && child_leaves > 0 {
1451        let mut count = 0u32;
1452        let mut r = 0u64;
1453        let mut g = 0u64;
1454        let mut b = 0u64;
1455        for c in &mut node.children {
1456            if let Some(ch) = c.take() {
1457                count += ch.count;
1458                r += ch.r;
1459                g += ch.g;
1460                b += ch.b;
1461                *leaf_count -= 1;
1462            }
1463        }
1464        node.leaf = true;
1465        node.count = count;
1466        node.r = r;
1467        node.g = g;
1468        node.b = b;
1469        *leaf_count += 1;
1470        return true;
1471    }
1472    false
1473}
1474
1475fn collect_leaves(node: &OctNode, out: &mut Vec<[u8; 3]>) {
1476    if node.leaf {
1477        if node.count > 0 {
1478            out.push([
1479                (node.r / node.count as u64) as u8,
1480                (node.g / node.count as u64) as u8,
1481                (node.b / node.count as u64) as u8,
1482            ]);
1483        }
1484        return;
1485    }
1486    for ch in node.children.iter().flatten() {
1487        collect_leaves(ch, out);
1488    }
1489}
1490
1491// ---- Median-cut (fallback) --------------------------------------------------
1492
1493fn median_cut(colors: &[([u8; 3], u32)], max_colors: usize) -> Vec<[u8; 3]> {
1494    #[derive(Clone)]
1495    struct Box {
1496        colors: Vec<([u8; 3], u32)>,
1497    }
1498    impl Box {
1499        fn range_channel(&self) -> usize {
1500            let mut min = [255u8; 3];
1501            let mut max = [0u8; 3];
1502            for (c, _) in &self.colors {
1503                for i in 0..3 {
1504                    min[i] = min[i].min(c[i]);
1505                    max[i] = max[i].max(c[i]);
1506                }
1507            }
1508            let ranges = [
1509                max[0] as i32 - min[0] as i32,
1510                max[1] as i32 - min[1] as i32,
1511                max[2] as i32 - min[2] as i32,
1512            ];
1513            ranges
1514                .iter()
1515                .enumerate()
1516                .max_by_key(|&(_, r)| r)
1517                .map(|(i, _)| i)
1518                .unwrap_or(0)
1519        }
1520        fn average(&self) -> [u8; 3] {
1521            let mut sum = [0u64; 3];
1522            let mut n = 0u64;
1523            for (c, w) in &self.colors {
1524                let w = *w as u64;
1525                for i in 0..3 {
1526                    sum[i] += c[i] as u64 * w;
1527                }
1528                n += w;
1529            }
1530            if n == 0 {
1531                return [0, 0, 0];
1532            }
1533            [(sum[0] / n) as u8, (sum[1] / n) as u8, (sum[2] / n) as u8]
1534        }
1535    }
1536
1537    let mut boxes = vec![Box {
1538        colors: colors.to_vec(),
1539    }];
1540    while boxes.len() < max_colors {
1541        let Some(idx) = boxes
1542            .iter()
1543            .enumerate()
1544            .filter(|(_, b)| b.colors.len() >= 2)
1545            .max_by_key(|(_, b)| {
1546                let ch = b.range_channel();
1547                let mut min = 255u8;
1548                let mut max = 0u8;
1549                for (c, _) in &b.colors {
1550                    min = min.min(c[ch]);
1551                    max = max.max(c[ch]);
1552                }
1553                (max as u32).saturating_sub(min as u32)
1554            })
1555            .map(|(i, _)| i)
1556        else {
1557            break;
1558        };
1559        let mut box_ = boxes.swap_remove(idx);
1560        let ch = box_.range_channel();
1561        box_.colors.sort_by_key(|(c, _)| c[ch]);
1562        let mid = box_.colors.len() / 2;
1563        let right = box_.colors.split_off(mid);
1564        boxes.push(Box {
1565            colors: box_.colors,
1566        });
1567        boxes.push(Box { colors: right });
1568    }
1569    boxes.into_iter().map(|b| b.average()).collect()
1570}
1571
1572fn nearest_index(rgb: [u8; 3], palette: &[[u8; 3]], transparent: Option<u8>) -> u8 {
1573    let limit = transparent.map(|t| t as usize).unwrap_or(palette.len());
1574    let mut best = 0usize;
1575    let mut best_d = u32::MAX;
1576    for (i, c) in palette
1577        .iter()
1578        .enumerate()
1579        .take(limit.max(1).min(palette.len()))
1580    {
1581        let d = dist2(rgb, *c);
1582        if d < best_d {
1583            best_d = d;
1584            best = i;
1585            if d == 0 {
1586                break;
1587            }
1588        }
1589    }
1590    best as u8
1591}
1592
1593fn nearest_index_lossy(
1594    rgb: [u8; 3],
1595    palette: &[[u8; 3]],
1596    transparent: Option<u8>,
1597    neighbor: Option<u8>,
1598    lossy: u8,
1599) -> u8 {
1600    if lossy > 0
1601        && let Some(index) = neighbor
1602    {
1603        let i = index as usize;
1604        if i < palette.len()
1605            && transparent != Some(index)
1606            && dist2(rgb, palette[i]) <= lossy_dist2(lossy)
1607        {
1608            return index;
1609        }
1610    }
1611    nearest_index(rgb, palette, transparent)
1612}
1613
1614fn lossy_dist2(lossy: u8) -> u32 {
1615    let channel = u32::from(lossy) * 255 / 100;
1616    channel * channel * 3
1617}
1618
1619fn dist2(a: [u8; 3], b: [u8; 3]) -> u32 {
1620    let dr = a[0] as i32 - b[0] as i32;
1621    let dg = a[1] as i32 - b[1] as i32;
1622    let db = a[2] as i32 - b[2] as i32;
1623    (dr * dr + dg * dg + db * db) as u32
1624}
1625
1626fn lzw_encode(indices: &[u8], min_code_size: u8, mode: LzwClearMode) -> Vec<u8> {
1627    let clear = 1u16 << min_code_size;
1628    let end = clear + 1;
1629    let mut code_size = min_code_size as u32 + 1;
1630    let mut next_code = end + 1;
1631    let mut dict = HashMap::<u32, u16>::new();
1632    let mut out_bits = BitPacker::new();
1633    out_bits.write(clear, code_size);
1634    if indices.is_empty() {
1635        out_bits.write(end, code_size);
1636        return out_bits.finish();
1637    }
1638    let mut w = indices[0] as u16;
1639    let mut hits = 0usize;
1640    let mut misses = 0usize;
1641    let mut frozen_hits = 0usize;
1642    let mut frozen_misses = 0usize;
1643    for &k in &indices[1..] {
1644        let key = ((w as u32) << 8) | k as u32;
1645        if let Some(&code) = dict.get(&key) {
1646            hits += 1;
1647            if next_code >= 4096 {
1648                frozen_hits += 1;
1649            }
1650            w = code;
1651            continue;
1652        }
1653        misses += 1;
1654        if next_code >= 4096 {
1655            frozen_misses += 1;
1656        }
1657        out_bits.write(w, code_size);
1658        if next_code < 4096 {
1659            dict.insert(key, next_code);
1660            // Bump width when the code we just assigned fills the current
1661            // alphabet — *before* advancing `next_code` (GIF LZW quirk).
1662            if next_code == (1 << code_size) && code_size < 12 {
1663                code_size += 1;
1664            }
1665            next_code += 1;
1666        } else {
1667            let clear_now = match mode {
1668                LzwClearMode::WhenFull => true,
1669                LzwClearMode::Deferred => {
1670                    frozen_misses >= 256 && frozen_hits.saturating_mul(4) < frozen_misses
1671                }
1672                LzwClearMode::Adaptive => frozen_misses >= 128 && frozen_hits < frozen_misses,
1673            };
1674            if clear_now {
1675                out_bits.write(clear, code_size);
1676                dict.clear();
1677                code_size = min_code_size as u32 + 1;
1678                next_code = end + 1;
1679                hits = 0;
1680                misses = 0;
1681                frozen_hits = 0;
1682                frozen_misses = 0;
1683            }
1684        }
1685        if mode == LzwClearMode::Adaptive
1686            && next_code < 4096
1687            && next_code > end + 512
1688            && misses >= 512
1689            && misses > hits.saturating_mul(3)
1690        {
1691            out_bits.write(clear, code_size);
1692            dict.clear();
1693            code_size = min_code_size as u32 + 1;
1694            next_code = end + 1;
1695            hits = 0;
1696            misses = 0;
1697            frozen_hits = 0;
1698            frozen_misses = 0;
1699        }
1700        w = k as u16;
1701    }
1702    out_bits.write(w, code_size);
1703    out_bits.write(end, code_size);
1704    out_bits.finish()
1705}
1706
1707struct BitPacker {
1708    buf: Vec<u8>,
1709    cur: u32,
1710    bits: u32,
1711}
1712
1713impl BitPacker {
1714    fn new() -> Self {
1715        Self {
1716            buf: Vec::new(),
1717            cur: 0,
1718            bits: 0,
1719        }
1720    }
1721    fn write(&mut self, code: u16, nbits: u32) {
1722        self.cur |= (code as u32) << self.bits;
1723        self.bits += nbits;
1724        while self.bits >= 8 {
1725            self.buf.push((self.cur & 0xFF) as u8);
1726            self.cur >>= 8;
1727            self.bits -= 8;
1728        }
1729    }
1730    fn finish(mut self) -> Vec<u8> {
1731        if self.bits > 0 {
1732            self.buf.push((self.cur & 0xFF) as u8);
1733        }
1734        self.buf
1735    }
1736}
1737
1738fn write_sub_blocks(out: &mut impl Write, data: &[u8]) -> io::Result<()> {
1739    let mut i = 0;
1740    while i < data.len() {
1741        let n = (data.len() - i).min(255);
1742        out.write_all(&[n as u8])?;
1743        out.write_all(&data[i..i + n])?;
1744        i += n;
1745    }
1746    out.write_all(&[0x00])
1747}
1748
1749#[cfg(test)]
1750fn gct_size_from_gif(gif: &[u8]) -> Option<usize> {
1751    let packed = gif[10];
1752    if packed & 0x80 == 0 {
1753        return None;
1754    }
1755    Some(1usize << ((packed & 0x07) + 1))
1756}
1757
1758#[cfg(test)]
1759mod tests {
1760    use super::*;
1761
1762    fn solid(w: u32, h: u32, r: u8, g: u8, b: u8, a: u8) -> Vec<u8> {
1763        let mut v = vec![0u8; (w * h * 4) as usize];
1764        for p in v.chunks_mut(4) {
1765            p[0] = r;
1766            p[1] = g;
1767            p[2] = b;
1768            p[3] = a;
1769        }
1770        v
1771    }
1772
1773    #[test]
1774    fn header_trailer_netscape() {
1775        let mut enc = GifEncoder::new(4, 4, 0)
1776            .dither(false)
1777            .diff_rects(false)
1778            .palette_mode(PaletteMode::Global)
1779            .transparency(false);
1780        enc.add_frame_owned(solid(4, 4, 255, 255, 255, 255), 1, 10);
1781        enc.add_frame_owned(solid(4, 4, 200, 0, 0, 255), 1, 10);
1782        let gif = enc.finish();
1783        assert_eq!(&gif[..6], b"GIF89a");
1784        assert_eq!(*gif.last().unwrap(), 0x3B);
1785        assert!(gif.windows(11).any(|w| w == b"NETSCAPE2.0"));
1786    }
1787
1788    #[test]
1789    fn transparency_gce_flag() {
1790        let mut enc = GifEncoder::new(2, 2, 1)
1791            .dither(false)
1792            .diff_rects(false)
1793            .transparency(true);
1794        let mut rgba = solid(2, 2, 255, 0, 0, 255);
1795        rgba[7] = 0;
1796        enc.add_frame_owned(rgba, 1, 10);
1797        let gif = enc.finish();
1798        let gce = gif.windows(2).position(|w| w == [0x21, 0xF9]).unwrap();
1799        assert_eq!(gif[gce + 3] & 1, 1);
1800    }
1801
1802    #[test]
1803    fn colors_4_global_gct() {
1804        let mut enc = GifEncoder::new(8, 8, 1)
1805            .colors(4)
1806            .dither(false)
1807            .diff_rects(false)
1808            .palette_mode(PaletteMode::Global)
1809            .transparency(false);
1810        let mut rgba = vec![0u8; 8 * 8 * 4];
1811        for (i, p) in rgba.chunks_mut(4).enumerate() {
1812            let c = [[255, 0, 0], [0, 255, 0], [0, 0, 255], [255, 255, 0]][i % 4];
1813            p[..3].copy_from_slice(&c);
1814            p[3] = 255;
1815        }
1816        enc.add_frame_owned(rgba, 1, 10);
1817        let gif = enc.finish();
1818        assert_eq!(gct_size_from_gif(&gif), Some(4));
1819    }
1820
1821    #[test]
1822    fn dirty_rect_shrinks_second_frame() {
1823        let w = 32u32;
1824        let h = 32u32;
1825        let mut with_diff = GifEncoder::new(w, h, 1)
1826            .colors(16)
1827            .dither(false)
1828            .diff_rects(true)
1829            .palette_mode(PaletteMode::Local)
1830            .transparency(true);
1831        let mut no_diff = GifEncoder::new(w, h, 1)
1832            .colors(16)
1833            .dither(false)
1834            .diff_rects(false)
1835            .palette_mode(PaletteMode::Local)
1836            .transparency(true);
1837
1838        let f0 = solid(w, h, 0, 0, 0, 255);
1839        let mut f1 = solid(w, h, 0, 0, 0, 255);
1840        for y in 10..14 {
1841            for x in 10..14 {
1842                let i = ((y * w + x) * 4) as usize;
1843                f1[i] = 255;
1844            }
1845        }
1846        with_diff.add_frame_owned(f0.clone(), 1, 10);
1847        with_diff.add_frame_owned(f1.clone(), 1, 10);
1848        no_diff.add_frame_owned(f0, 1, 10);
1849        no_diff.add_frame_owned(f1, 1, 10);
1850
1851        let a = with_diff.finish();
1852        let b = no_diff.finish();
1853        assert!(
1854            a.len() < b.len(),
1855            "diff-rect GIF should be smaller: {} vs {}",
1856            a.len(),
1857            b.len()
1858        );
1859
1860        // Parse image descriptor sizes correctly (skip LCT / LZW).
1861        let sizes = image_sizes(&a);
1862        assert!(sizes.len() >= 2, "expected ≥2 images, got {sizes:?}");
1863        assert_eq!(sizes[0], (32, 32));
1864        assert!(
1865            sizes[1].0 <= 8 && sizes[1].1 <= 8,
1866            "dirty rect should be small, got {:?}",
1867            sizes[1]
1868        );
1869    }
1870
1871    /// Walk GIF89a and collect `(width, height)` from each Image Descriptor.
1872    fn image_sizes(gif: &[u8]) -> Vec<(u16, u16)> {
1873        let mut out = Vec::new();
1874        let mut i = 13; // after header + LSD (no GCT when local-only stream)
1875                        // Skip GCT if present.
1876        let packed = gif[10];
1877        if packed & 0x80 != 0 {
1878            let n = 1usize << ((packed & 7) + 1);
1879            i = 13 + n * 3;
1880        }
1881        while i < gif.len() {
1882            match gif[i] {
1883                0x3B => break,
1884                0x21 => {
1885                    // Extension.
1886                    i += 1;
1887                    if i >= gif.len() {
1888                        break;
1889                    }
1890                    let label = gif[i];
1891                    i += 1;
1892                    if label == 0xFF || label == 0xF9 || label == 0xFE || label == 0x01 {
1893                        while i < gif.len() {
1894                            let sz = gif[i] as usize;
1895                            i += 1;
1896                            if sz == 0 {
1897                                break;
1898                            }
1899                            i += sz;
1900                        }
1901                    }
1902                }
1903                0x2C => {
1904                    if i + 10 > gif.len() {
1905                        break;
1906                    }
1907                    let iw = u16::from_le_bytes([gif[i + 5], gif[i + 6]]);
1908                    let ih = u16::from_le_bytes([gif[i + 7], gif[i + 8]]);
1909                    out.push((iw, ih));
1910                    let ipacked = gif[i + 9];
1911                    i += 10;
1912                    if ipacked & 0x80 != 0 {
1913                        let n = 1usize << ((ipacked & 7) + 1);
1914                        i += n * 3;
1915                    }
1916                    // LZW: min code size + sub-blocks.
1917                    i += 1;
1918                    while i < gif.len() {
1919                        let sz = gif[i] as usize;
1920                        i += 1;
1921                        if sz == 0 {
1922                            break;
1923                        }
1924                        i += sz;
1925                    }
1926                }
1927                _ => i += 1,
1928            }
1929        }
1930        out
1931    }
1932
1933    #[test]
1934    fn streaming_encode_iter() {
1935        let frames = (0..3).map(|f| {
1936            let mut rgba = solid(8, 8, 10, 20, 30, 255);
1937            rgba[0] = (f * 40) as u8;
1938            (rgba, 1u16, 10u16)
1939        });
1940        let gif = GifEncoder::new(8, 8, 0)
1941            .colors(32)
1942            .dither(true)
1943            .diff_rects(true)
1944            .palette_mode(PaletteMode::Local)
1945            .encode_iter(frames);
1946        assert_eq!(&gif[..6], b"GIF89a");
1947    }
1948
1949    #[test]
1950    fn lossy_zero_is_identical() {
1951        let frames = vec![
1952            (solid(8, 8, 10, 20, 30, 255), 1, 10),
1953            (solid(8, 8, 11, 21, 31, 255), 1, 10),
1954        ];
1955        let baseline = encode_gif(8, 8, 0, &GifOptions::default(), frames.clone());
1956        let explicit = encode_gif(8, 8, 0, &GifOptions::default().lossy(0), frames);
1957        assert_eq!(baseline, explicit);
1958    }
1959
1960    #[test]
1961    fn gif_writer_matches_local_encode() {
1962        let frames = vec![
1963            (solid(4, 4, 20, 30, 40, 255), 1, 10),
1964            (solid(4, 4, 50, 60, 70, 255), 2, 10),
1965        ];
1966        let expected = encode_gif(4, 4, 0, &GifOptions::default(), frames.clone());
1967        let mut writer = GifWriter::new(Vec::new(), 4, 4, 0, GifOptions::default()).unwrap();
1968        for (rgba, n, d) in frames {
1969            writer.write_frame(&rgba, n, d).unwrap();
1970        }
1971        assert_eq!(writer.finish().unwrap(), expected);
1972    }
1973
1974    #[test]
1975    fn comment_extension_is_emitted() {
1976        let opts = GifOptions::default().comment(b"hello");
1977        let gif = encode_gif(1, 1, 1, &opts, vec![(solid(1, 1, 0, 0, 0, 255), 1, 10)]);
1978        assert!(gif.windows(2).any(|w| w == [0x21, 0xFE]));
1979        assert!(gif.windows(5).any(|w| w == b"hello"));
1980    }
1981
1982    #[test]
1983    fn interlace_descriptor_bit_is_set() {
1984        let opts = GifOptions::default().interlace(true);
1985        let gif = encode_gif(2, 2, 1, &opts, vec![(solid(2, 2, 1, 2, 3, 255), 1, 10)]);
1986        let image = gif.iter().position(|&b| b == 0x2C).unwrap();
1987        assert_ne!(gif[image + 9] & 0x40, 0);
1988    }
1989
1990    #[test]
1991    fn alternate_lzw_clear_modes_form_gifs() {
1992        for mode in [LzwClearMode::Deferred, LzwClearMode::Adaptive] {
1993            let opts = GifOptions::default().lzw_clear(mode);
1994            let gif = encode_gif(
1995                32,
1996                32,
1997                1,
1998                &opts,
1999                vec![(solid(32, 32, 12, 34, 56, 255), 1, 10)],
2000            );
2001            assert_eq!(&gif[..6], b"GIF89a");
2002            assert_eq!(gif.last(), Some(&0x3B));
2003        }
2004    }
2005
2006    #[test]
2007    fn auto_disposal_handles_transparent_hole() {
2008        let opaque = solid(3, 3, 255, 0, 0, 255);
2009        let mut hole = opaque.clone();
2010        hole[(4 * 4) + 3] = 0;
2011        let gif = encode_gif(
2012            3,
2013            3,
2014            1,
2015            &GifOptions::default().dither(false),
2016            vec![(opaque, 1, 10), (hole, 1, 10)],
2017        );
2018        let gce = gif.windows(2).position(|w| w == [0x21, 0xF9]).unwrap();
2019        let disposal = (gif[gce + 3] >> 2) & 7;
2020        assert!(disposal == 2 || disposal == 3, "got disposal {disposal}");
2021    }
2022
2023    #[test]
2024    fn octree_reduces_colors() {
2025        let mut samples = Vec::new();
2026        for r in (0..256).step_by(2) {
2027            for g in (0..256).step_by(4) {
2028                samples.push([r as u8, g as u8, 128]);
2029            }
2030        }
2031        let pal = octree_quantize(&samples, 16);
2032        assert!(pal.len() <= 16, "got {}", pal.len());
2033        assert!(!pal.is_empty());
2034    }
2035}