Skip to content

ProCraft for Android: An Android native painting app written in Rust

Rust
16.8 KB
Raw Blame
//! Reading animated GIFs: each frame drawn over the canvas as the frames before it left it (kept,
//! cleared to nothing, or put back as it was), with how long it shows. A damaged file gives the
//! frames before the damage.

/// The most pixels a GIF's canvas may have.
const MOST_PIXELS: u64 = 4096 * 4096;
/// Frames shown for at most a hundredth of a second play, as browsers play them, at this.
const SHORTEST_MS: u32 = 100;

/// The canvas's size, if `bytes` is a GIF of a size read here.
pub fn size(bytes: &[u8]) -> Option<(u32, u32)> {
    screen(bytes)
}

/// How many frames the GIF `bytes` has (none if it isn't one), without decoding them.
pub fn frame_count(bytes: &[u8]) -> usize {
    let mut count = 0;
    walk(bytes, |_, _| {
        count += 1;
        Some(())
    });
    count
}

/// Gives `frame` each frame of the GIF `bytes` in order (straight RGBA, the canvas's size, and how
/// long it shows, ms) until it returns false. The canvas's size and how many frames it was given,
/// or none if it isn't a GIF.
pub fn frames(bytes: &[u8], mut frame: impl FnMut(&[u8], u32) -> bool) -> Option<(u32, u32, usize)> {
    let (w, h) = screen(bytes)?;
    let (wu, hu) = (w as usize, h as usize);
    let mut canvas = vec![0u8; wu * hu * 4];
    let mut given = 0;
    let mut stopped = false;
    walk(bytes, |image, data| {
        if stopped {
            return None;
        }
        // a frame may be no bigger than a canvas may (it can be bigger than its own canvas)
        let count = u64::from(image.width) * u64::from(image.height);
        let indices = lzw(data, image.min_code, usize::try_from(count).ok().filter(|_| count <= MOST_PIXELS)?)?;
        let before = (image.disposal == 3).then(|| canvas.clone());
        draw(&mut canvas, wu, hu, &image, &indices);
        given += 1;
        let ms = if image.delay <= 1 { SHORTEST_MS } else { u32::from(image.delay) * 10 };
        if !frame(&canvas, ms) {
            stopped = true;
            return None;
        }
        match (image.disposal, before) {
            (2, _) => clear(&mut canvas, wu, hu, &image),
            (3, Some(b)) => canvas = b,
            _ => {}
        }
        Some(())
    });
    Some((w, h, given))
}

/// A frame's place, palette and how it shows (from the control block before it).
struct Image<'a> {
    left: u16,
    top: u16,
    width: u16,
    height: u16,
    interlaced: bool,
    palette: &'a [u8],
    min_code: u8,
    transparent: Option<u8>,
    delay: u16,
    disposal: u8,
}

/// The canvas's size, if `bytes` is a GIF of a size read here.
fn screen(bytes: &[u8]) -> Option<(u32, u32)> {
    let mut r = Reader { b: bytes, at: 0 };
    let sig = r.take(6)?;
    if sig != b"GIF87a" && sig != b"GIF89a" {
        return None;
    }
    let (w, h) = (u32::from(r.u16()?), u32::from(r.u16()?));
    (w > 0 && h > 0 && u64::from(w) * u64::from(h) <= MOST_PIXELS).then_some((w, h))
}

/// Calls `each` with every frame and its compressed data, in order, until the end, damage, or
/// `each` giving none.
fn walk<'a>(bytes: &'a [u8], mut each: impl FnMut(Image<'a>, &[u8]) -> Option<()>) {
    if screen(bytes).is_none() {
        return;
    }
    let mut r = Reader { b: bytes, at: 10 };
    let mut go = || -> Option<()> {
        let packed = r.u8()?;
        r.take(2)?;
        let global = if packed & 0x80 != 0 { Some(r.take(3 << ((packed & 7) + 1))?) } else { None };
        let (mut transparent, mut delay, mut disposal) = (None, 0, 0);
        loop {
            match r.u8()? {
                0x21 => {
                    let label = r.u8()?;
                    let block = r.blocks()?;
                    if label == 0xF9 && block.len() >= 4 {
                        let flags = *block.first()?;
                        disposal = (flags >> 2) & 7;
                        delay = u16::from_le_bytes([*block.get(1)?, *block.get(2)?]);
                        transparent = (flags & 1 != 0).then_some(*block.get(3)?);
                    }
                }
                0x2C => {
                    let (left, top, width, height) = (r.u16()?, r.u16()?, r.u16()?, r.u16()?);
                    let packed = r.u8()?;
                    let local = if packed & 0x80 != 0 { Some(r.take(3 << ((packed & 7) + 1))?) } else { None };
                    let min_code = r.u8()?;
                    let data = r.blocks()?;
                    let palette = local.or(global)?;
                    let image = Image {
                        left,
                        top,
                        width,
                        height,
                        interlaced: packed & 0x40 != 0,
                        palette,
                        min_code,
                        transparent,
                        delay,
                        disposal,
                    };
                    each(image, &data)?;
                    // a control block is for the next frame only
                    (transparent, delay, disposal) = (None, 0, 0);
                }
                _ => return None,
            }
        }
    };
    let _ = go();
}

/// Draws a frame's colours over the canvas (its transparent ones leave what is there).
fn draw(canvas: &mut [u8], w: usize, h: usize, image: &Image<'_>, indices: &[u8]) {
    let (fw, fh) = (usize::from(image.width), usize::from(image.height));
    // interlaced: every eighth row from 0, every eighth from 4, every fourth from 2, the rest
    let rows: Vec<usize> = if image.interlaced {
        (0..fh).step_by(8).chain((4..fh).step_by(8)).chain((2..fh).step_by(4)).chain((1..fh).step_by(2)).collect()
    } else {
        (0..fh).collect()
    };
    for (i, row) in rows.into_iter().enumerate() {
        let y = usize::from(image.top) + row;
        if y >= h {
            continue;
        }
        for col in 0..fw {
            let x = usize::from(image.left) + col;
            let Some(&index) = indices.get(i * fw + col) else { return };
            if x >= w || Some(index) == image.transparent {
                continue;
            }
            let at = usize::from(index) * 3;
            if let (Some(&[r, g, b]), Some(px)) =
                (image.palette.get(at..at + 3), canvas.get_mut((y * w + x) * 4..(y * w + x) * 4 + 4))
            {
                px.copy_from_slice(&[r, g, b, 255]);
            }
        }
    }
}

/// Clears a frame's place to nothing.
fn clear(canvas: &mut [u8], w: usize, h: usize, image: &Image<'_>) {
    let (x0, y0) = (usize::from(image.left).min(w), usize::from(image.top).min(h));
    let (x1, y1) = ((x0 + usize::from(image.width)).min(w), (y0 + usize::from(image.height)).min(h));
    for y in y0..y1 {
        if let Some(row) = canvas.get_mut((y * w + x0) * 4..(y * w + x1) * 4) {
            row.fill(0);
        }
    }
}

/// The colour indices `data` holds (LZW, codes from `min_code + 1` bits growing to 12), `count` of
/// them: short data padded with the first colour.
fn lzw(data: &[u8], min_code: u8, count: usize) -> Option<Vec<u8>> {
    if !(1..=11).contains(&min_code) {
        return None;
    }
    const NONE: u16 = u16::MAX;
    let clear = 1u16 << min_code;
    let end = clear + 1;
    // each code: the code before its last colour, its last colour, and its first
    let mut prefix = vec![NONE; 4096];
    let mut suffix = vec![0u8; 4096];
    let mut first = vec![0u8; 4096];
    for c in 0..clear {
        let c8 = (c & 0xFF) as u8;
        *suffix.get_mut(usize::from(c))? = c8;
        *first.get_mut(usize::from(c))? = c8;
    }
    let mut out = Vec::with_capacity(count);
    let (mut next, mut size, mut prev) = (end + 1, u32::from(min_code) + 1, None::<u16>);
    let (mut acc, mut bits, mut at) = (0u32, 0u32, 0usize);
    let mut string = Vec::with_capacity(4096);
    'codes: while out.len() < count {
        while bits < size {
            let Some(&byte) = data.get(at) else { break 'codes };
            acc |= u32::from(byte) << bits;
            bits += 8;
            at += 1;
        }
        let code = (acc & ((1 << size) - 1)) as u16;
        acc >>= size;
        bits -= size;
        if code == clear {
            (next, size, prev) = (end + 1, u32::from(min_code) + 1, None);
            continue;
        }
        if code == end {
            break;
        }
        let Some(p) = prev else {
            if code >= clear {
                break;
            }
            out.push((code & 0xFF) as u8);
            prev = Some(code);
            continue;
        };
        // a code not yet made is the one before with its own first colour again
        let (start, tail) = if code < next {
            (code, None)
        } else if code == next {
            (p, Some(*first.get(usize::from(p))?))
        } else {
            break;
        };
        string.clear();
        string.extend(tail);
        let mut c = start;
        loop {
            string.push(*suffix.get(usize::from(c))?);
            if c < clear {
                break;
            }
            c = *prefix.get(usize::from(c))?;
            if c == NONE || string.len() > 4096 {
                break 'codes;
            }
        }
        out.extend(string.iter().rev().take(count - out.len()));
        if next < 4096 {
            let n = usize::from(next);
            *prefix.get_mut(n)? = p;
            *suffix.get_mut(n)? = *first.get(usize::from(start))?;
            *first.get_mut(n)? = *first.get(usize::from(p))?;
            next += 1;
            if u32::from(next) == 1 << size && size < 12 {
                size += 1;
            }
        }
        prev = Some(code);
    }
    out.resize(count, 0);
    Some(out)
}

struct Reader<'a> {
    b: &'a [u8],
    at: usize,
}

impl<'a> Reader<'a> {
    fn take(&mut self, n: usize) -> Option<&'a [u8]> {
        let s = self.b.get(self.at..self.at.checked_add(n)?)?;
        self.at += n;
        Some(s)
    }

    fn u8(&mut self) -> Option<u8> {
        self.take(1)?.first().copied()
    }

    fn u16(&mut self) -> Option<u16> {
        let b = self.take(2)?;
        Some(u16::from_le_bytes([*b.first()?, *b.get(1)?]))
    }

    /// Sub-blocks (each a length, then that many bytes) up to an empty one, joined.
    fn blocks(&mut self) -> Option<Vec<u8>> {
        let mut out = Vec::new();
        loop {
            let n = usize::from(self.u8()?);
            if n == 0 {
                return Some(out);
            }
            out.extend_from_slice(self.take(n)?);
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    /// LZW codes for `indices` (no compression: a clear code before every few, so the code size
    /// stays `min + 1`), packed as a GIF packs them.
    fn compress(indices: &[u8], min: u8) -> Vec<u8> {
        let clear = 1u32 << min;
        let size = u32::from(min) + 1;
        let mut codes = vec![clear];
        for (i, &v) in indices.iter().enumerate() {
            if i > 0 && i % ((1 << size) - clear as usize - 2).max(1) == 0 {
                codes.push(clear);
            }
            codes.push(u32::from(v));
        }
        codes.push(clear + 1);
        let (mut out, mut acc, mut bits) = (Vec::new(), 0u32, 0u32);
        for c in codes {
            acc |= c << bits;
            bits += size;
            while bits >= 8 {
                out.push((acc & 0xFF) as u8);
                acc >>= 8;
                bits -= 8;
            }
        }
        if bits > 0 {
            out.push(acc as u8);
        }
        out
    }

    fn blocks(data: &[u8]) -> Vec<u8> {
        let mut out = Vec::new();
        for chunk in data.chunks(255) {
            out.push(chunk.len() as u8);
            out.extend_from_slice(chunk);
        }
        out.push(0);
        out
    }

    /// A 4 × 2 GIF of red, green, blue and white: frame 1 all red, frame 2 a green square at
    /// (1, 0) whose second pixel is transparent, shown for 0.5 s then cleared, frame 3 blue at
    /// (3, 1).
    fn sample() -> Vec<u8> {
        let mut g = b"GIF89a".to_vec();
        g.extend_from_slice(&[4, 0, 2, 0, 0x81, 0, 0]);
        g.extend_from_slice(&[255, 0, 0, 0, 255, 0, 0, 0, 255, 255, 255, 255]);
        let frame = |g: &mut Vec<u8>, control: [u8; 4], place: [u16; 4], indices: &[u8]| {
            g.extend_from_slice(&[0x21, 0xF9, 4]);
            g.extend_from_slice(&control);
            g.push(0);
            g.push(0x2C);
            for v in place {
                g.extend_from_slice(&v.to_le_bytes());
            }
            g.push(0);
            g.push(2);
            g.extend(blocks(&compress(indices, 2)));
        };
        frame(&mut g, [0, 10, 0, 0], [0, 0, 4, 2], &[0; 8]);
        frame(&mut g, [(2 << 2) | 1, 50, 0, 3], [1, 0, 2, 1], &[1, 3]);
        frame(&mut g, [0, 0, 0, 0], [3, 1, 1, 1], &[2]);
        g.push(0x3B);
        g
    }

    fn px(f: &[u8], x: usize, y: usize) -> [u8; 4] {
        let i = (y * 4 + x) * 4;
        [f[i], f[i + 1], f[i + 2], f[i + 3]]
    }

    #[test]
    fn frames_build_on_each_other_and_show_for_their_time() {
        let g = sample();
        assert_eq!(frame_count(&g), 3);
        let mut seen = Vec::new();
        assert_eq!(
            frames(&g, |f, ms| {
                seen.push((f.to_vec(), ms));
                true
            }),
            Some((4, 2, 3))
        );
        let (red, green, blue) = ([255, 0, 0, 255], [0, 255, 0, 255], [0, 0, 255, 255]);
        // a tenth of a second; the green over the red, its transparent pixel leaving the red
        assert_eq!(seen[0].1, 100);
        assert_eq!((px(&seen[1].0, 1, 0), px(&seen[1].0, 2, 0), px(&seen[1].0, 0, 0)), (green, red, red));
        assert_eq!(seen[1].1, 500);
        // then cleared to nothing where it was; a frame with no time plays at a tenth of a second
        assert_eq!((px(&seen[2].0, 1, 0), px(&seen[2].0, 3, 1), px(&seen[2].0, 0, 1)), ([0; 4], blue, red));
        assert_eq!(seen[2].1, 100);
        // stopping early
        let mut n = 0;
        assert_eq!(
            frames(&g, |_, _| {
                n += 1;
                false
            })
            .map(|f| f.2),
            Some(1)
        );
    }

    /// LZW as GIF encoders write it: strings grow in the table, and so do the codes.
    fn encode(indices: &[u8], min: u8) -> Vec<u8> {
        let clear = 1u32 << min;
        let mut table = std::collections::HashMap::new();
        let (mut next, mut size) = (clear + 2, u32::from(min) + 1);
        let mut codes = vec![(clear, size)];
        let mut w: Option<u32> = None;
        for &c in indices {
            let Some(p) = w else {
                w = Some(u32::from(c));
                continue;
            };
            if let Some(&code) = table.get(&(p, c)) {
                w = Some(code);
                continue;
            }
            codes.push((p, size));
            if next < 4096 {
                table.insert((p, c), next);
                if next == 1 << size && size < 12 {
                    size += 1;
                }
                next += 1;
            }
            w = Some(u32::from(c));
        }
        codes.extend(w.map(|p| (p, size)));
        codes.push((clear + 1, size));
        let (mut out, mut acc, mut bits) = (Vec::new(), 0u64, 0u32);
        for (c, n) in codes {
            acc |= u64::from(c) << bits;
            bits += n;
            while bits >= 8 {
                out.push((acc & 0xFF) as u8);
                acc >>= 8;
                bits -= 8;
            }
        }
        if bits > 0 {
            out.push(acc as u8);
        }
        out
    }

    #[test]
    fn codes_longer_than_the_first_size_decode() {
        // repeating runs: the table fills with longer strings and the codes grow past 3 bits
        let indices: Vec<u8> = (0..2000).map(|i| (i / 7 % 4) as u8).collect();
        let data = encode(&indices, 2);
        assert!(data.len() < indices.len() / 4, "{} bytes", data.len());
        assert_eq!(lzw(&data, 2, indices.len()).unwrap(), indices);
        // eight-bit colours
        let indices: Vec<u8> = (0..5000u32).map(|i| ((i * 37) % 251) as u8).collect();
        assert_eq!(lzw(&encode(&indices, 8), 8, indices.len()).unwrap(), indices);
    }

    #[test]
    fn other_files_and_damaged_ones_are_refused_or_cut_short() {
        assert_eq!(frame_count(b"not a picture"), 0);
        assert!(frames(b"GIF89a\0\0\0\0", |_, _| true).is_none());
        let g = sample();
        // cut in its last frame: the two before it come
        assert_eq!(frames(&g[..g.len() - 6], |_, _| true).map(|f| f.2), Some(2));
        // a frame far bigger than any canvas (a few bytes asking for gigabytes) ends it there
        let mut huge = b"GIF89a".to_vec();
        huge.extend_from_slice(&[1, 0, 1, 0, 0x80, 0, 0, 0, 0, 0, 255, 255, 255]);
        for _ in 0..2 {
            huge.extend_from_slice(&[0x2C, 0, 0, 0, 0, 0xFF, 0xFF, 0xFF, 0xFF, 0, 2, 0]);
        }
        huge.push(0x3B);
        assert_eq!(frame_count(&huge), 2);
        assert_eq!(frames(&huge, |_, _| true).map(|f| f.2), Some(0));
        crate::damaged::survives("GIF", &g, |b| {
            let _ = frames(b, |_, _| true);
            let _ = frame_count(b);
        });
    }
}