1pub 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#[derive(Clone, Copy, Debug, PartialEq, Eq, Default)]
52pub enum DisposalMode {
53 #[default]
55 Auto,
56 None,
58 Keep,
60 Background,
62 Previous,
64}
65
66#[derive(Clone, Copy, Debug, PartialEq, Eq, Default)]
68pub enum LzwClearMode {
69 #[default]
71 WhenFull,
72 Deferred,
74 Adaptive,
76}
77
78#[derive(Clone, Copy, Debug, PartialEq, Eq, Default)]
80pub enum PaletteMode {
81 Global,
83 #[default]
85 Local,
86 Auto,
88}
89
90#[derive(Clone, Copy, Debug, PartialEq, Eq, Default)]
92pub enum QuantizerKind {
93 #[default]
95 Octree,
96 MedianCut,
98}
99
100#[derive(Clone, Debug)]
102pub struct GifOptions {
103 pub max_colors: u16,
105 pub transparency: bool,
107 pub alpha_threshold: u8,
109 pub dither: bool,
111 pub diff_rects: bool,
113 pub palette_mode: PaletteMode,
115 pub quantizer: QuantizerKind,
117 pub disposal: DisposalMode,
119 pub lossy: u8,
122 pub lzw_clear: LzwClearMode,
124 pub interlace: bool,
126 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 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 pub fn transparency(mut self, on: bool) -> Self {
161 self.transparency = on;
162 self
163 }
164 pub fn alpha_threshold(mut self, t: u8) -> Self {
166 self.alpha_threshold = t;
167 self
168 }
169 pub fn dither(mut self, on: bool) -> Self {
171 self.dither = on;
172 self
173 }
174 pub fn diff_rects(mut self, on: bool) -> Self {
176 self.diff_rects = on;
177 self
178 }
179 pub fn palette_mode(mut self, mode: PaletteMode) -> Self {
181 self.palette_mode = mode;
182 self
183 }
184 pub fn quantizer(mut self, q: QuantizerKind) -> Self {
186 self.quantizer = q;
187 self
188 }
189 pub fn disposal(mut self, mode: DisposalMode) -> Self {
191 self.disposal = mode;
192 self
193 }
194 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 pub fn lzw_clear(mut self, mode: LzwClearMode) -> Self {
202 self.lzw_clear = mode;
203 self
204 }
205 pub fn interlace(mut self, on: bool) -> Self {
207 self.interlace = on;
208 self
209 }
210 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
223pub struct GifEncoder {
229 width: u32,
230 height: u32,
231 plays: u32,
232 opts: GifOptions,
233 frames: Vec<Frame>,
234}
235
236pub 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 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 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 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 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 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 pub fn options(mut self, opts: GifOptions) -> Self {
400 self.opts = opts;
401 self
402 }
403
404 pub fn colors(mut self, n: u16) -> Self {
406 self.opts = self.opts.colors(n);
407 self
408 }
409 pub fn transparency(mut self, on: bool) -> Self {
411 self.opts = self.opts.transparency(on);
412 self
413 }
414 pub fn alpha_threshold(mut self, t: u8) -> Self {
416 self.opts = self.opts.alpha_threshold(t);
417 self
418 }
419 pub fn dither(mut self, on: bool) -> Self {
421 self.opts = self.opts.dither(on);
422 self
423 }
424 pub fn diff_rects(mut self, on: bool) -> Self {
426 self.opts = self.opts.diff_rects(on);
427 self
428 }
429 pub fn palette_mode(mut self, mode: PaletteMode) -> Self {
431 self.opts = self.opts.palette_mode(mode);
432 self
433 }
434 pub fn quantizer(mut self, q: QuantizerKind) -> Self {
436 self.opts = self.opts.quantizer(q);
437 self
438 }
439 pub fn disposal(mut self, mode: DisposalMode) -> Self {
441 self.opts = self.opts.disposal(mode);
442 self
443 }
444 pub fn lossy(mut self, loss: u8) -> Self {
446 self.opts = self.opts.lossy(loss);
447 self
448 }
449 pub fn lzw_clear(mut self, mode: LzwClearMode) -> Self {
451 self.opts = self.opts.lzw_clear(mode);
452 self
453 }
454 pub fn interlace(mut self, on: bool) -> Self {
456 self.opts = self.opts.interlace(on);
457 self
458 }
459 pub fn comment(mut self, bytes: impl AsRef<[u8]>) -> Self {
461 self.opts = self.opts.comment(bytes);
462 self
463 }
464
465 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 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 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 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
507pub 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 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, 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 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
845fn 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 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 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 let need_diff_tr = opts.diff_rects && !first;
897 let tr = if need_diff_tr && tr.is_none() {
898 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; 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 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 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 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 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 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 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 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
1337struct 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 if node.leaf {
1430 return false;
1431 }
1432 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
1491fn 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 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 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 fn image_sizes(gif: &[u8]) -> Vec<(u16, u16)> {
1873 let mut out = Vec::new();
1874 let mut i = 13; 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 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 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}