1use std::fmt;
10
11use super::lzw::{self, Finish, LzwError};
12use super::{EXTENSION, IMAGE, TRAILER};
13use crate::raster::{self, Palette, Pixels, Raster};
14
15const MAX_PIXELS_PER_BYTE: u64 = 4096;
18const GRAPHIC_CONTROL: u8 = 0xF9;
20const COMMENT: u8 = 0xFE;
22const APPLICATION: u8 = 0xFF;
24
25#[derive(Clone, Debug, PartialEq, Eq)]
27pub enum DecodeError {
28 NotGif,
30 Truncated,
32 NoImage,
34 MalformedExtension,
36 EmptyImage,
38 TooLarge {
41 width: u32,
43 height: u32,
45 },
46 InvalidCodeSize(u8),
48 InvalidCode,
50 Incomplete,
52}
53
54impl fmt::Display for DecodeError {
55 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
56 match self {
57 Self::NotGif => f.write_str("not a GIF file"),
58 Self::Truncated => f.write_str("the GIF data ends early"),
59 Self::NoImage => f.write_str("the GIF file holds no image"),
60 Self::MalformedExtension => f.write_str("malformed GIF graphic control extension"),
61 Self::EmptyImage => f.write_str("the GIF image has no pixels"),
62 Self::TooLarge { width, height } => {
63 write!(f, "a {width} × {height} GIF image is too large to decode")
64 }
65 Self::InvalidCodeSize(bits) => write!(f, "invalid GIF LZW code size {bits}"),
66 Self::InvalidCode => f.write_str("corrupt GIF image data"),
67 Self::Incomplete => f.write_str("the GIF image data ends before the image does"),
68 }
69 }
70}
71
72impl std::error::Error for DecodeError {}
73
74#[derive(Debug)]
76struct Reader<'a> {
77 data: &'a [u8],
78 pos: usize,
79}
80
81impl<'a> Reader<'a> {
82 fn bytes(&mut self, n: usize) -> Result<&'a [u8], DecodeError> {
83 let bytes = self
84 .data
85 .get(self.pos..self.pos + n)
86 .ok_or(DecodeError::Truncated)?;
87 self.pos += n;
88 Ok(bytes)
89 }
90
91 fn byte(&mut self) -> Result<u8, DecodeError> {
92 Ok(self.bytes(1)?[0])
93 }
94
95 fn u16(&mut self) -> Result<u16, DecodeError> {
96 let bytes = self.bytes(2)?;
97 Ok(u16::from_le_bytes([bytes[0], bytes[1]]))
98 }
99
100 fn sub_block(&mut self) -> Option<&'a [u8]> {
104 let len = usize::from(*self.data.get(self.pos)?);
105 self.pos += 1;
106 if len == 0 {
107 return None;
108 }
109 let end = (self.pos + len).min(self.data.len());
110 let block = &self.data[self.pos..end];
111 self.pos = end;
112 Some(block)
113 }
114
115 fn skip_sub_blocks(&mut self) {
118 while self.sub_block().is_some_and(|block| !block.is_empty()) {}
119 }
120
121 fn color_table(&mut self, bits: u8) -> Result<Option<Vec<[u8; 3]>>, DecodeError> {
124 let table = self.bytes(3 << bits)?;
125 let colors = table.as_chunks::<3>().0.to_vec();
126 let ramp = (0..=255).zip(&colors).all(|(i, &c)| c == [i; 3]);
127 Ok((!ramp).then_some(colors))
128 }
129}
130
131struct SubBlockBytes<'a> {
135 data: &'a [u8],
136 pos: usize,
137 left: usize,
138}
139
140impl Iterator for SubBlockBytes<'_> {
141 type Item = u8;
142
143 fn next(&mut self) -> Option<u8> {
144 while self.left == 0 {
145 let len = usize::from(*self.data.get(self.pos)?);
146 if self.data.len() - self.pos - 1 < len {
147 return None;
148 }
149 self.pos += 1;
150 self.left = len;
151 }
152 self.left -= 1;
153 self.pos += 1;
154 Some(self.data[self.pos - 1])
155 }
156}
157
158struct Frame {
160 canvas_width: usize,
161 left: usize,
162 top: usize,
163 width: usize,
164 height: usize,
165 pass: u8,
168 step: usize,
169 x: usize,
170 y: usize,
171}
172
173impl Frame {
174 fn put(&mut self, canvas: &mut [u8], index: u8) -> bool {
177 canvas[(self.top + self.y) * self.canvas_width + self.left + self.x] = index;
178 self.x += 1;
179 if self.x < self.width {
180 return false;
181 }
182 self.x = 0;
183 self.y += self.step;
184 while self.y >= self.height {
185 (self.y, self.step, self.pass) = match self.pass {
186 1 => (4, 8, 2),
187 2 => (2, 4, 3),
188 3 => (1, 2, 0),
189 _ => return true,
190 };
191 }
192 false
193 }
194}
195
196pub fn decode(data: &[u8]) -> Result<Raster, DecodeError> {
205 let mut reader = Reader { data, pos: 0 };
206 let header = reader.bytes(6).map_err(|_| DecodeError::NotGif)?;
207 if header != b"GIF87a" && header != b"GIF89a" {
208 return Err(DecodeError::NotGif);
209 }
210 let (screen_width, screen_height) = (reader.u16()?, reader.u16()?);
211 let flags = reader.byte()?;
212 reader.bytes(2)?;
213 let global = if flags & 0x80 != 0 {
214 reader.color_table((flags & 7) + 1)?
215 } else {
216 None
217 };
218 let transparent = read_extensions(&mut reader)?;
219 let (left, top) = (reader.u16()?, reader.u16()?);
220 let (width, height) = (reader.u16()?, reader.u16()?);
221 let flags = reader.byte()?;
222 let palette = if flags & 0x80 != 0 {
223 reader.color_table((flags & 7) + 1)?
224 } else {
225 global
226 };
227 let min_code_size = reader.byte()?;
228 let canvas_width = u32::from(screen_width).max(u32::from(left) + u32::from(width));
229 let canvas_height = u32::from(screen_height).max(u32::from(top) + u32::from(height));
230 if width == 0 || height == 0 {
231 return Err(DecodeError::EmptyImage);
232 }
233 if !raster::fits(canvas_width, canvas_height, data.len(), MAX_PIXELS_PER_BYTE) {
234 return Err(DecodeError::TooLarge {
235 width: canvas_width,
236 height: canvas_height,
237 });
238 }
239 let mut canvas = vec![transparent.unwrap_or(0); canvas_width as usize * canvas_height as usize];
240 let interlaced = flags & 0x40 != 0;
241 let mut frame = Frame {
242 canvas_width: canvas_width as usize,
243 left: usize::from(left),
244 top: usize::from(top),
245 width: usize::from(width),
246 height: usize::from(height),
247 pass: u8::from(interlaced),
248 step: if interlaced { 8 } else { 1 },
249 x: 0,
250 y: 0,
251 };
252 let bytes = SubBlockBytes {
253 data,
254 pos: reader.pos,
255 left: 0,
256 };
257 let finish = lzw::decompress(bytes, min_code_size, |index| frame.put(&mut canvas, index))
258 .map_err(|err| match err {
259 LzwError::InvalidCodeSize => DecodeError::InvalidCodeSize(min_code_size),
260 LzwError::InvalidCode => DecodeError::InvalidCode,
261 LzwError::Truncated => DecodeError::Truncated,
262 })?;
263 if finish == Finish::EndCode {
264 return Err(DecodeError::Incomplete);
265 }
266 let pixels = match palette {
267 Some(colors) => Pixels::Indexed {
268 palette: Palette::new(colors, transparent),
269 indices: canvas,
270 },
271 None => Pixels::Gray(canvas),
272 };
273 Ok(Raster::new(canvas_width, canvas_height, pixels))
274}
275
276fn read_extensions(reader: &mut Reader<'_>) -> Result<Option<u8>, DecodeError> {
283 let mut transparent = None;
284 loop {
285 match reader.byte().map_err(|_| DecodeError::NoImage)? {
286 IMAGE => return Ok(transparent),
287 TRAILER => return Err(DecodeError::NoImage),
288 EXTENSION => {
289 let label = reader.byte()?;
290 let block = reader.sub_block();
291 match (label, block) {
292 (GRAPHIC_CONTROL, Some(block)) => {
293 let [flags, _, _, rest @ ..] = block else {
294 return Err(DecodeError::MalformedExtension);
295 };
296 if flags & 1 == 1 {
297 let index = rest.first().ok_or(DecodeError::MalformedExtension)?;
298 transparent = Some(*index);
299 }
300 }
301 (COMMENT, first) => {
302 if first.is_some_and(|block| !block.is_empty()) {
303 reader.skip_sub_blocks();
304 }
305 continue;
306 }
307 (APPLICATION, Some(block)) if block.starts_with(b"NETSCAPE2.0") => {
308 reader.sub_block();
309 }
310 _ => {}
311 }
312 reader.skip_sub_blocks();
313 }
314 _ => {}
315 }
316 }
317}
318
319#[cfg(test)]
320mod tests {
321 use super::*;
322 use crate::gif::{GifEncoder, GifFrame};
323
324 fn encoded(width: u32, height: u32, pixels: &[u8]) -> Vec<u8> {
326 let frames = [GifFrame { pixels, delay: 1 }];
327 GifEncoder::new().encode(width, height, &frames).unwrap()
328 }
329
330 #[test]
331 fn encoder_output_decodes_to_its_colours() {
332 let pixels: Vec<u8> = (0..6 * 5)
333 .flat_map(|i| [(i * 40 % 256) as u8, 10, 200, 255])
334 .collect();
335 let image = decode(&encoded(6, 5, &pixels)).unwrap();
336 assert_eq!((image.width(), image.height()), (6, 5));
337 let rgba: Vec<u8> = image.to_rgba8().into_iter().flatten().collect();
338 assert_eq!(rgba, pixels);
339 }
340
341 #[test]
342 fn transparency_becomes_alpha_zero() {
343 let pixels = [[0, 0, 0, 0], [255, 0, 0, 255]].concat();
344 let image = decode(&encoded(2, 1, &pixels)).unwrap();
345 let Pixels::Indexed { palette, indices } = image.pixels() else {
346 panic!("a palette image");
347 };
348 assert_eq!(palette.rgba(indices[0])[3], 0);
349 assert_eq!(palette.rgba(indices[1]), [255, 0, 0, 255]);
350 }
351
352 fn interlaced() -> Vec<u8> {
355 let mut gif = b"GIF89a\x04\x00\x04\x00\x80\x00\x00".to_vec();
356 gif.extend_from_slice(&[0, 0, 0, 10, 10, 10]);
357 gif.extend_from_slice(&[EXTENSION, GRAPHIC_CONTROL, 4, 1, 0, 0, 1, 0]);
358 gif.extend_from_slice(&[IMAGE, 1, 0, 0, 0, 2, 0, 4, 0, 0x40, 2]);
359 let indices = [0, 0, 2, 2, 1, 1, 3, 3];
361 let packed = lzw::compress(&indices, 2);
362 gif.push(u8::try_from(packed.len()).unwrap());
363 gif.extend_from_slice(&packed);
364 gif.extend_from_slice(&[0, TRAILER]);
365 gif
366 }
367
368 #[test]
369 fn interlaced_frames_land_on_a_transparent_canvas() {
370 let image = decode(&interlaced()).unwrap();
371 let Pixels::Indexed { palette, indices } = image.pixels() else {
372 panic!("a palette image");
373 };
374 assert_eq!(palette.transparent(), Some(1));
375 assert_eq!(
376 indices,
377 &[1, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 3, 3, 1],
378 "rows 0 to 3 of the frame, the rest the transparent index"
379 );
380 }
381
382 #[test]
383 fn grey_ramps_are_not_palettes() {
384 let mut gif = interlaced();
385 gif[13..19].copy_from_slice(&[0, 0, 0, 1, 1, 1]);
386 assert!(matches!(decode(&gif).unwrap().pixels(), Pixels::Gray(_)));
387 }
388
389 #[test]
390 fn bad_files_are_rejected() {
391 assert_eq!(decode(b"GIF8"), Err(DecodeError::NotGif));
392 assert_eq!(decode(b"PNG89a\0\0\0\0\0\0\0"), Err(DecodeError::NotGif));
393 assert_eq!(
394 decode(b"GIF89a\x01\x00\x01\x00\x00\x00\x00;"),
395 Err(DecodeError::NoImage)
396 );
397 let mut huge = b"GIF89a\xff\xff\xff\xff\x00\x00\x00".to_vec();
398 huge.extend_from_slice(&[IMAGE, 0, 0, 0, 0, 1, 0, 1, 0, 0, 2, 2, 0x4C, 0x01, 0]);
399 assert!(matches!(decode(&huge), Err(DecodeError::TooLarge { .. })));
400 let mut empty = interlaced();
401 empty[32] = 0;
402 assert_eq!(decode(&empty), Err(DecodeError::EmptyImage));
403 let mut code_size = interlaced();
404 code_size[37] = 13;
405 assert_eq!(decode(&code_size), Err(DecodeError::InvalidCodeSize(13)));
406 }
407
408 #[test]
409 fn truncations_and_corruptions_never_panic() {
410 let gif = interlaced();
411 let complete = gif.len() - 2;
413 for len in 0..complete {
414 assert!(decode(&gif[..len]).is_err(), "truncated to {len}");
415 }
416 assert!(decode(&gif[..complete]).is_ok());
417 let mut rng = crate::test_util::Rng::new(11);
418 let big = encoded(
419 23,
420 17,
421 &(0..23 * 17 * 4)
422 .map(|i| (i * 7 % 251) as u8)
423 .collect::<Vec<_>>(),
424 );
425 for _ in 0..3000 {
426 let mut corrupt = big.clone();
427 for _ in 0..=rng.below(4) {
428 let at = rng.below(corrupt.len());
429 corrupt[at] ^= 1 << rng.below(8);
430 }
431 let _ = decode(&corrupt);
432 }
433 }
434}