Skip to main content

pltrs_codec/gif/
decode.rs

1//! Reading the first frame of a GIF file as Pillow opens it
2//! (`GifImagePlugin` and `GifDecode.c`): mode `P` with the frame's
3//! palette (its local table, else the global one) and the transparent
4//! index of its graphic control extension, or mode `L` when the palette
5//! is missing or is the identity grey ramp. The frame is drawn on a
6//! canvas of the logical screen (enlarged to hold the frame) filled with
7//! the transparent index, or index 0.
8
9use std::fmt;
10
11use super::lzw::{self, Finish, LzwError};
12use super::{EXTENSION, IMAGE, TRAILER};
13use crate::raster::{self, Palette, Pixels, Raster};
14
15/// At most this many pixels per byte of input: an LZW code of 12 bits
16/// stands for at most 4095 indices, so valid images stay well below.
17const MAX_PIXELS_PER_BYTE: u64 = 4096;
18/// The graphic control extension's label.
19const GRAPHIC_CONTROL: u8 = 0xF9;
20/// The comment extension's label.
21const COMMENT: u8 = 0xFE;
22/// The application extension's label.
23const APPLICATION: u8 = 0xFF;
24
25/// Why a GIF file could not be decoded.
26#[derive(Clone, Debug, PartialEq, Eq)]
27pub enum DecodeError {
28    /// The data does not start with a GIF signature.
29    NotGif,
30    /// The data ends inside a structure.
31    Truncated,
32    /// The file holds no image.
33    NoImage,
34    /// A graphic control extension too short for its fields.
35    MalformedExtension,
36    /// The frame, or the canvas, has no pixels.
37    EmptyImage,
38    /// The canvas has more pixels than the input can describe, or than
39    /// Pillow accepts.
40    TooLarge {
41        /// The canvas width.
42        width: u32,
43        /// The canvas height.
44        height: u32,
45    },
46    /// The LZW minimum code size is above 12.
47    InvalidCodeSize(u8),
48    /// The image data holds an invalid LZW code.
49    InvalidCode,
50    /// The image data ends before the frame is complete.
51    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/// A position in the file.
75#[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    /// The next data sub-block as Pillow's `GifImageFile.data` reads it:
101    /// `None` at a block terminator or the end of the data, and possibly
102    /// short when the data ends inside the block.
103    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    /// Skips sub-blocks up to the next terminator, or one that is empty
116    /// because the data ended.
117    fn skip_sub_blocks(&mut self) {
118        while self.sub_block().is_some_and(|block| !block.is_empty()) {}
119    }
120
121    /// A colour table of `2^bits` entries, or `None` when it is the
122    /// identity grey ramp, which Pillow does not treat as a palette.
123    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
131/// The bytes of image data, read from consecutive sub-blocks as Pillow's
132/// decoder reads them: a block's bytes are used only once it is whole,
133/// and a zero-length block is just an empty block.
134struct 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
158/// The frame's rectangle on the canvas and the order its rows arrive in.
159struct Frame {
160    canvas_width: usize,
161    left: usize,
162    top: usize,
163    width: usize,
164    height: usize,
165    /// The interlace pass (1 to 3 still to come after the current one)
166    /// or 0 when the rows are sequential or in the last pass.
167    pass: u8,
168    step: usize,
169    x: usize,
170    y: usize,
171}
172
173impl Frame {
174    /// Writes the next index; returns `true` once every row is written
175    /// (Pillow's `NEWLINE`).
176    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
196/// Decodes the first frame of a GIF file into the image Pillow opens:
197/// palette indices with the frame's palette and transparent index, or
198/// grey levels when there is no palette or it is the identity ramp.
199///
200/// # Errors
201///
202/// When the data is not a GIF file, has no image, is malformed or
203/// truncated, or claims more pixels than its size allows.
204pub 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
276/// Skips the blocks before the first image descriptor as Pillow's
277/// `GifImageFile._seek` does, returning the transparent index of the last
278/// graphic control extension that set one. Bytes that start no block are
279/// skipped; after an extension's first sub-block (comments excepted, and
280/// the loop count of a NETSCAPE2.0 extension read too), sub-blocks are
281/// skipped up to a terminator.
282fn 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    /// A GIF of `pixels` (RGBA) made by the encoder.
325    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    /// A hand-made GIF: a 4×4 screen, an interlaced 2×4 frame at (1, 0)
353    /// whose rows hold indices 0, 1, 2, 3.
354    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        // Rows arrive as 0, 2, 1, 3: indices 0 0, 2 2, 1 1, 3 3.
360        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        // The image is complete once its last data block is in.
412        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}