veridian_kernel/media/image_codecs/gif.rs
1//! GIF decoder (87a/89a) with LZW decompression.
2//!
3//! Supports global/local color tables, animation frames, disposal methods,
4//! transparency, and interlaced rendering.
5
6#![allow(dead_code)]
7
8use alloc::vec::Vec;
9
10use super::{read_le_u16, DecodedImage, ImageCodecError};
11
12// ============================================================================
13// GIF DECODER (87a / 89a)
14// ============================================================================
15
16/// GIF header magic bytes.
17pub(crate) const GIF87A: &[u8; 6] = b"GIF87a";
18pub(crate) const GIF89A: &[u8; 6] = b"GIF89a";
19
20/// A decoded GIF with potentially multiple frames for animation.
21#[derive(Debug, Clone, PartialEq)]
22pub struct DecodedGif {
23 /// Logical screen width.
24 pub width: u32,
25 /// Logical screen height.
26 pub height: u32,
27 /// Decoded frames (at least one for static GIFs).
28 pub frames: Vec<GifFrame>,
29 /// Number of times to loop (0 = infinite).
30 pub loop_count: u32,
31}
32
33/// A single GIF animation frame.
34#[derive(Debug, Clone, PartialEq)]
35pub struct GifFrame {
36 /// RGBA8888 pixel data for the full logical screen.
37 pub image: DecodedImage,
38 /// Delay in hundredths of a second (0 = no delay).
39 pub delay_cs: u16,
40 /// Disposal method for this frame.
41 pub disposal: GifDisposal,
42}
43
44/// GIF frame disposal methods.
45#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
46pub enum GifDisposal {
47 /// No disposal specified -- leave frame in place.
48 #[default]
49 None,
50 /// Do not dispose -- leave graphic in place.
51 DoNotDispose,
52 /// Restore to background color.
53 RestoreBackground,
54 /// Restore to previous frame content.
55 RestorePrevious,
56}
57
58/// Decode a GIF image (including animated GIFs).
59pub fn decode_gif(data: &[u8]) -> Result<DecodedGif, ImageCodecError> {
60 if data.len() < 13 {
61 return Err(ImageCodecError::TruncatedData);
62 }
63
64 // Verify signature
65 let sig = &data[0..6];
66 if sig != GIF87A && sig != GIF89A {
67 return Err(ImageCodecError::InvalidSignature);
68 }
69
70 // Logical screen descriptor
71 let screen_width = read_le_u16(data, 6) as u32;
72 let screen_height = read_le_u16(data, 8) as u32;
73
74 if screen_width == 0 || screen_height == 0 {
75 return Err(ImageCodecError::InvalidDimensions);
76 }
77
78 let packed = data[10];
79 let has_gct = (packed & 0x80) != 0;
80 let gct_size_bits = (packed & 0x07) as u32;
81 let _bg_color_index = data[11];
82 let _pixel_aspect = data[12];
83
84 let mut pos: usize = 13;
85
86 // Read Global Color Table
87 let mut global_ct: Vec<(u8, u8, u8)> = Vec::new();
88 if has_gct {
89 let gct_entries = 1u32 << (gct_size_bits + 1);
90 let gct_bytes = (gct_entries as usize) * 3;
91 if pos + gct_bytes > data.len() {
92 return Err(ImageCodecError::TruncatedData);
93 }
94 for i in 0..gct_entries as usize {
95 let off = pos + i * 3;
96 global_ct.push((data[off], data[off + 1], data[off + 2]));
97 }
98 pos += gct_bytes;
99 }
100
101 let mut frames: Vec<GifFrame> = Vec::new();
102 let mut loop_count: u32 = 1;
103
104 // Graphics control extension state
105 let mut gce_delay: u16 = 0;
106 let mut gce_disposal = GifDisposal::None;
107 let mut gce_transparent: Option<u8> = None;
108
109 // For "Restore Previous" disposal
110 let mut previous_canvas: Option<DecodedImage> = None;
111
112 while pos < data.len() {
113 match data[pos] {
114 0x2C => {
115 // Image descriptor
116 if pos + 10 > data.len() {
117 return Err(ImageCodecError::TruncatedData);
118 }
119
120 let img_left = read_le_u16(data, pos + 1) as u32;
121 let img_top = read_le_u16(data, pos + 3) as u32;
122 let img_width = read_le_u16(data, pos + 5) as u32;
123 let img_height = read_le_u16(data, pos + 7) as u32;
124 let img_packed = data[pos + 9];
125 let has_lct = (img_packed & 0x80) != 0;
126 let is_interlaced = (img_packed & 0x40) != 0;
127 let lct_size_bits = (img_packed & 0x07) as u32;
128
129 pos += 10;
130
131 // Read local color table if present
132 let color_table: &[(u8, u8, u8)];
133 let local_ct: Vec<(u8, u8, u8)>;
134 if has_lct {
135 let lct_entries = 1u32 << (lct_size_bits + 1);
136 let lct_bytes = (lct_entries as usize) * 3;
137 if pos + lct_bytes > data.len() {
138 return Err(ImageCodecError::TruncatedData);
139 }
140 let mut lct = Vec::with_capacity(lct_entries as usize);
141 for i in 0..lct_entries as usize {
142 let off = pos + i * 3;
143 lct.push((data[off], data[off + 1], data[off + 2]));
144 }
145 pos += lct_bytes;
146 local_ct = lct;
147 color_table = &local_ct;
148 } else {
149 local_ct = Vec::new();
150 let _ = &local_ct; // suppress unused warning
151 color_table = &global_ct;
152 }
153
154 // Read LZW compressed image data
155 if pos >= data.len() {
156 return Err(ImageCodecError::TruncatedData);
157 }
158 let min_code_size = data[pos];
159 pos += 1;
160
161 // Collect sub-blocks
162 let mut lzw_data: Vec<u8> = Vec::new();
163 loop {
164 if pos >= data.len() {
165 break;
166 }
167 let block_size = data[pos] as usize;
168 pos += 1;
169 if block_size == 0 {
170 break;
171 }
172 if pos + block_size > data.len() {
173 return Err(ImageCodecError::TruncatedData);
174 }
175 lzw_data.extend_from_slice(&data[pos..pos + block_size]);
176 pos += block_size;
177 }
178
179 // LZW decompress
180 let pixels = lzw_decompress(&lzw_data, min_code_size)?;
181
182 // Build the canvas for this frame
183 // Start from previous frame (or blank)
184 let mut canvas = if let Some(last) = frames.last() {
185 // Apply disposal of previous frame
186 match last.disposal {
187 GifDisposal::None | GifDisposal::DoNotDispose => last.image.clone(),
188 GifDisposal::RestoreBackground => {
189 DecodedImage::new(screen_width, screen_height)
190 }
191 GifDisposal::RestorePrevious => previous_canvas
192 .clone()
193 .unwrap_or_else(|| DecodedImage::new(screen_width, screen_height)),
194 }
195 } else {
196 DecodedImage::new(screen_width, screen_height)
197 };
198
199 // Save canvas before drawing (for RestorePrevious)
200 if gce_disposal == GifDisposal::RestorePrevious {
201 previous_canvas = Some(canvas.clone());
202 }
203
204 // Map pixel indices to the canvas
205 let pixel_count = (img_width as usize) * (img_height as usize);
206
207 if is_interlaced {
208 // GIF interlace: 4 passes
209 // Pass 1: rows 0, 8, 16, ... (start=0, step=8)
210 // Pass 2: rows 4, 12, 20, ... (start=4, step=8)
211 // Pass 3: rows 2, 6, 10, ... (start=2, step=4)
212 // Pass 4: rows 1, 3, 5, ... (start=1, step=2)
213 const INTERLACE_PASSES: [(usize, usize); 4] = [(0, 8), (4, 8), (2, 4), (1, 2)];
214
215 let mut src_idx: usize = 0;
216 for &(start, step) in &INTERLACE_PASSES {
217 let mut row = start;
218 while row < img_height as usize {
219 for col in 0..img_width as usize {
220 if src_idx < pixels.len() && src_idx < pixel_count {
221 let ci = pixels[src_idx] as usize;
222 if ci < color_table.len() {
223 let skip =
224 gce_transparent.is_some_and(|t| t as usize == ci);
225 if !skip {
226 let (r, g, b) = color_table[ci];
227 canvas.set_pixel(
228 img_left + col as u32,
229 img_top + row as u32,
230 r,
231 g,
232 b,
233 255,
234 );
235 }
236 }
237 }
238 src_idx += 1;
239 }
240 row += step;
241 }
242 }
243 } else {
244 // Non-interlaced: sequential rows
245 for (idx, &ci_byte) in pixels.iter().enumerate().take(pixel_count) {
246 let ci = ci_byte as usize;
247 let row = idx / img_width as usize;
248 let col = idx % img_width as usize;
249 if ci < color_table.len() {
250 let skip = gce_transparent.is_some_and(|t| t as usize == ci);
251 if !skip {
252 let (r, g, b) = color_table[ci];
253 canvas.set_pixel(
254 img_left + col as u32,
255 img_top + row as u32,
256 r,
257 g,
258 b,
259 255,
260 );
261 }
262 }
263 }
264 }
265
266 frames.push(GifFrame {
267 image: canvas,
268 delay_cs: gce_delay,
269 disposal: gce_disposal,
270 });
271
272 // Reset GCE state for next frame
273 gce_delay = 0;
274 gce_disposal = GifDisposal::None;
275 gce_transparent = None;
276 }
277 0x21 => {
278 // Extension block
279 if pos + 2 > data.len() {
280 return Err(ImageCodecError::TruncatedData);
281 }
282 let label = data[pos + 1];
283 pos += 2;
284
285 match label {
286 0xF9 => {
287 // Graphics Control Extension
288 if pos >= data.len() {
289 return Err(ImageCodecError::TruncatedData);
290 }
291 let block_size = data[pos] as usize;
292 pos += 1;
293 if pos + block_size > data.len() || block_size < 4 {
294 return Err(ImageCodecError::TruncatedData);
295 }
296
297 let gce_packed = data[pos];
298 gce_disposal = match (gce_packed >> 2) & 0x07 {
299 0 => GifDisposal::None,
300 1 => GifDisposal::DoNotDispose,
301 2 => GifDisposal::RestoreBackground,
302 3 => GifDisposal::RestorePrevious,
303 _ => GifDisposal::None,
304 };
305 gce_delay = read_le_u16(data, pos + 1);
306 let has_transparent = (gce_packed & 0x01) != 0;
307 if has_transparent {
308 gce_transparent = Some(data[pos + 3]);
309 } else {
310 gce_transparent = None;
311 }
312
313 pos += block_size;
314 // Skip block terminator
315 if pos < data.len() && data[pos] == 0 {
316 pos += 1;
317 }
318 }
319 0xFF => {
320 // Application Extension (check for NETSCAPE2.0 loop)
321 if pos >= data.len() {
322 return Err(ImageCodecError::TruncatedData);
323 }
324 let block_size = data[pos] as usize;
325 pos += 1;
326
327 if block_size == 11
328 && pos + 11 <= data.len()
329 && &data[pos..pos + 11] == b"NETSCAPE2.0"
330 {
331 pos += block_size;
332 // Read sub-block with loop count
333 if pos < data.len() {
334 let sub_size = data[pos] as usize;
335 pos += 1;
336 if sub_size >= 3 && pos + sub_size <= data.len() {
337 if data[pos] == 1 {
338 loop_count = read_le_u16(data, pos + 1) as u32;
339 }
340 pos += sub_size;
341 }
342 }
343 } else {
344 pos += block_size;
345 }
346
347 // Skip remaining sub-blocks
348 gif_skip_sub_blocks(data, &mut pos);
349 }
350 _ => {
351 // Skip unknown extension sub-blocks
352 gif_skip_sub_blocks(data, &mut pos);
353 }
354 }
355 }
356 0x3B => {
357 // Trailer (end of GIF)
358 break;
359 }
360 _ => {
361 pos += 1;
362 }
363 }
364 }
365
366 if frames.is_empty() {
367 return Err(ImageCodecError::CorruptData);
368 }
369
370 Ok(DecodedGif {
371 width: screen_width,
372 height: screen_height,
373 frames,
374 loop_count,
375 })
376}
377
378/// Skip GIF sub-blocks until block terminator (0x00).
379fn gif_skip_sub_blocks(data: &[u8], pos: &mut usize) {
380 while *pos < data.len() {
381 let block_size = data[*pos] as usize;
382 *pos += 1;
383 if block_size == 0 {
384 break;
385 }
386 *pos += block_size;
387 }
388}
389
390// ============================================================================
391// LZW DECOMPRESSION (for GIF)
392// ============================================================================
393
394/// LZW decompression for GIF image data.
395fn lzw_decompress(data: &[u8], min_code_size: u8) -> Result<Vec<u8>, ImageCodecError> {
396 if min_code_size > 11 {
397 return Err(ImageCodecError::Unsupported);
398 }
399
400 let clear_code: u16 = 1 << min_code_size;
401 let eoi_code: u16 = clear_code + 1;
402
403 let mut code_size: u8 = min_code_size + 1;
404 let mut next_code: u16 = eoi_code + 1;
405 let max_table_size: usize = 4096;
406
407 // LZW code table: each entry is (prefix_code, suffix_byte)
408 // Entries 0..clear_code are initialized as single-byte strings
409 let mut table_prefix: Vec<u16> = alloc::vec![0u16; max_table_size];
410 let mut table_suffix: Vec<u8> = alloc::vec![0u8; max_table_size];
411 let mut table_len: Vec<u16> = alloc::vec![0u16; max_table_size];
412
413 // Initialize table
414 for i in 0..clear_code {
415 table_prefix[i as usize] = 0;
416 table_suffix[i as usize] = i as u8;
417 table_len[i as usize] = 1;
418 }
419
420 let mut output: Vec<u8> = Vec::new();
421 let mut bit_pos: usize = 0;
422 let total_bits = data.len() * 8;
423
424 // Read a code from the bit stream
425 let read_code = |bit_pos: &mut usize, code_size: u8| -> Result<u16, ImageCodecError> {
426 if *bit_pos + code_size as usize > total_bits {
427 return Err(ImageCodecError::TruncatedData);
428 }
429 let mut code: u16 = 0;
430 for i in 0..code_size {
431 let byte_idx = (*bit_pos + i as usize) / 8;
432 let bit_idx = (*bit_pos + i as usize) % 8;
433 if byte_idx < data.len() && (data[byte_idx] >> bit_idx) & 1 != 0 {
434 code |= 1 << i;
435 }
436 }
437 *bit_pos += code_size as usize;
438 Ok(code)
439 };
440
441 // Expect initial clear code
442 let first = read_code(&mut bit_pos, code_size)?;
443 if first != clear_code {
444 // Some GIFs don't start with clear code; reset anyway
445 code_size = min_code_size + 1;
446 next_code = eoi_code + 1;
447 }
448
449 // Read first real code
450 let mut prev_code = read_code(&mut bit_pos, code_size)?;
451 if prev_code == eoi_code {
452 return Ok(output);
453 }
454 if prev_code < clear_code {
455 output.push(prev_code as u8);
456 }
457
458 // Temporary buffer for string output
459 let mut string_buf: Vec<u8> = Vec::with_capacity(max_table_size);
460
461 while let Ok(code) = read_code(&mut bit_pos, code_size) {
462 if code == eoi_code {
463 break;
464 }
465
466 if code == clear_code {
467 code_size = min_code_size + 1;
468 next_code = eoi_code + 1;
469
470 // Read next code after clear
471 prev_code = match read_code(&mut bit_pos, code_size) {
472 Ok(c) => c,
473 Err(_) => break,
474 };
475 if prev_code == eoi_code {
476 break;
477 }
478 if prev_code < clear_code {
479 output.push(prev_code as u8);
480 }
481 continue;
482 }
483
484 // Output the string for this code
485 string_buf.clear();
486
487 if (code as usize) < next_code as usize {
488 // Code is in the table -- output its string
489 let mut c = code;
490 while c >= clear_code && c != eoi_code {
491 let ci = c as usize;
492 if ci >= max_table_size {
493 return Err(ImageCodecError::DecompressionError);
494 }
495 string_buf.push(table_suffix[ci]);
496 c = table_prefix[ci];
497 }
498 string_buf.push(c as u8);
499 string_buf.reverse();
500 } else if code == next_code {
501 // Special case: code not yet in table
502 let mut c = prev_code;
503 while c >= clear_code && c != eoi_code {
504 let ci = c as usize;
505 if ci >= max_table_size {
506 return Err(ImageCodecError::DecompressionError);
507 }
508 string_buf.push(table_suffix[ci]);
509 c = table_prefix[ci];
510 }
511 string_buf.push(c as u8);
512 string_buf.reverse();
513 // Append first character of string
514 if let Some(&first_char) = string_buf.first() {
515 string_buf.push(first_char);
516 }
517 } else {
518 return Err(ImageCodecError::DecompressionError);
519 }
520
521 output.extend_from_slice(&string_buf);
522
523 // Add new entry to table
524 if (next_code as usize) < max_table_size {
525 let ni = next_code as usize;
526 table_prefix[ni] = prev_code;
527 table_suffix[ni] = if let Some(&first) = string_buf.first() {
528 first
529 } else {
530 0
531 };
532 table_len[ni] = table_len[prev_code as usize] + 1;
533 next_code += 1;
534
535 // Increase code size when needed
536 if next_code > (1 << code_size) && code_size < 12 {
537 code_size += 1;
538 }
539 }
540
541 prev_code = code;
542 }
543
544 Ok(output)
545}
546
547// ============================================================================
548// TESTS
549// ============================================================================
550
551#[cfg(test)]
552mod tests {
553 #[allow(unused_imports)]
554 use alloc::vec;
555
556 use super::*;
557
558 #[test]
559 fn test_gif_signature_check() {
560 let bad = [0u8; 13];
561 assert_eq!(decode_gif(&bad), Err(ImageCodecError::InvalidSignature));
562 }
563
564 #[test]
565 fn test_gif_too_short() {
566 let data = b"GIF89";
567 assert_eq!(decode_gif(data), Err(ImageCodecError::TruncatedData));
568 }
569
570 #[test]
571 fn test_gif_disposal_default() {
572 assert_eq!(GifDisposal::default(), GifDisposal::None);
573 }
574
575 #[test]
576 fn test_lzw_decompress_basic() {
577 // Minimal LZW stream: clear code, code 0, EOI
578 // min_code_size=2 => clear=4, eoi=5, initial code_size=3
579 // Codes: 4 (clear), 0, 5 (eoi)
580 // In bits (3 bits each, LSB first):
581 // 4 = 100, 0 = 000, 5 = 101
582 // Packed: 100 000 101 = byte 0: 00000100 = 0x04, byte 1: 00000101 >> shifted
583 // Actually LSB: bits 0-2 = 100(4), bits 3-5 = 000(0), bits 6-8 = 101(5)
584 // byte 0: bits 0-7: bit0=0,bit1=0,bit2=1,bit3=0,bit4=0,bit5=0,bit6=1,bit7=0 =
585 // 0x44 byte 1: bit8=1 => 0x01
586 let data = vec![0x44, 0x01];
587 let result = lzw_decompress(&data, 2).unwrap();
588 assert_eq!(result, vec![0]);
589 }
590
591 #[test]
592 fn test_lzw_decompress_multi() {
593 // min_code_size=2 => clear=4, eoi=5, code_size=3
594 // Stream: clear(4), 0, 1, 2, 3, eoi(5)
595 // 3-bit codes packed LSB-first:
596 // 4=100, 0=000, 1=001, 2=010, 3=011, 5=101
597 // bits: 100 000 001 010 011 101
598 // byte 0 (bits 0-7): 00000100 = 0x04
599 // byte 1 (bits 8-15): 01001001 = 0x49
600 // byte 2 (bits 16-17): 01 => but we need 011 101
601 // bits 16-18: 011 = 3
602 // bits 19-21: 101 = 5
603 // byte 2 (bits 16-23): 10101 011 => but reversed: 011 101 00 = 01110100 = no...
604 // Let me recalculate carefully:
605 // bit 0-2: 100 (4) => byte0 bits 0-2
606 // bit 3-5: 000 (0) => byte0 bits 3-5
607 // bit 6-8: 001 (1) => byte0 bits 6-7, byte1 bit 0
608 // bit 9-11: 010 (2) => byte1 bits 1-3
609 // bit 12-14: 011 (3) => byte1 bits 4-6
610 // bit 15-17: 101 (5) => byte1 bit 7, byte2 bits 0-1
611 // byte0 = bit7..bit0 = 0 1 | 0 0 0 | 1 0 0 = 01000100 = 0x44
612 // Wait, LSB first means bit 0 is the least significant bit of byte 0.
613 // byte0: bits 0,1,2,3,4,5,6,7
614 // 1,0,0,0,0,0,1,0 (code 4 = 100 at bits 0-2, code 0 = 000 at bits 3-5,
615 // code 1's first bit at 6,7) code 4 = 100: bit0=0, bit1=0, bit2=1 =>
616 // positions 0,1,2 of stream Hmm actually: code value 4 in binary = 100.
617 // LSB first: bit0=0, bit1=0, bit2=1. So byte0 bits 0..7: 0(4.b0)
618 // 0(4.b1) 1(4.b2) 0(0.b0) 0(0.b1) 0(0.b2) 1(1.b0) 0(1.b1)
619 // byte0 = 0b01000100 = 0x44
620 // byte1 bits 0..7: 0(1.b2) 0(2.b0) 1(2.b1) 0(2.b2) 1(3.b0) 1(3.b1) 0(3.b2)
621 // 1(5.b0) byte1 = 0b10110010 = nope, let me be more careful
622 // 1.b2=0, 2.b0=0, 2.b1=1, 2.b2=0, 3.b0=1, 3.b1=1, 3.b2=0, 5.b0=1
623 // byte1 = bit0=0, bit1=0, bit2=1, bit3=0, bit4=1, bit5=1, bit6=0, bit7=1
624 // byte1 = 0b10110100 = 0xB4
625 // byte2 bits 0..1: 5.b1=0, 5.b2=1
626 // byte2 = 0b00000010 = 0x02
627 let data = vec![0x44, 0xB4, 0x02];
628 let result = lzw_decompress(&data, 2).unwrap();
629 assert_eq!(result, vec![0, 1, 2, 3]);
630 }
631
632 #[test]
633 fn test_gif_minimal_valid() {
634 // Build a minimal valid 1x1 GIF89a with a single red pixel
635 let mut gif = Vec::new();
636
637 // Header
638 gif.extend_from_slice(b"GIF89a");
639
640 // Logical Screen Descriptor
641 gif.push(1);
642 gif.push(0); // width = 1
643 gif.push(1);
644 gif.push(0); // height = 1
645 gif.push(0x80); // GCT flag set, 2 colors (size bits = 0 => 2^(0+1)=2 entries)
646 gif.push(0); // bg color index
647 gif.push(0); // pixel aspect ratio
648
649 // Global Color Table (2 entries = 6 bytes)
650 gif.extend_from_slice(&[0, 0, 0]); // color 0: black
651 gif.extend_from_slice(&[255, 0, 0]); // color 1: red
652
653 // Image Descriptor
654 gif.push(0x2C);
655 gif.push(0);
656 gif.push(0); // left = 0
657 gif.push(0);
658 gif.push(0); // top = 0
659 gif.push(1);
660 gif.push(0); // width = 1
661 gif.push(1);
662 gif.push(0); // height = 1
663 gif.push(0); // no LCT, not interlaced
664
665 // LZW min code size
666 gif.push(2);
667
668 // LZW data sub-block: clear(4), 1(red), eoi(5)
669 // min_code_size=2, code_size=3
670 // 4=100, 1=001, 5=101 packed LSB first:
671 // bits 0-2: 0,0,1 (value 4)
672 // bits 3-5: 1,0,0 (value 1)
673 // bits 6-8: 1,0,1 (value 5)
674 // byte0: bit0=0 bit1=0 bit2=1 bit3=1 bit4=0 bit5=0 bit6=1 bit7=0 = 0b01001100 =
675 // 0x4C byte1: bit0=1 = 0x01
676 gif.push(2); // sub-block size
677 gif.push(0x4C);
678 gif.push(0x01);
679 gif.push(0); // block terminator
680
681 // Trailer
682 gif.push(0x3B);
683
684 let result = decode_gif(&gif).unwrap();
685 assert_eq!(result.width, 1);
686 assert_eq!(result.height, 1);
687 assert_eq!(result.frames.len(), 1);
688 // The pixel should be red
689 let (r, g, b, a) = result.frames[0].image.get_pixel(0, 0);
690 assert_eq!((r, g, b, a), (255, 0, 0, 255));
691 }
692}