Skip to main content

day_script/
png.rs

1// Copyright © The Daybrite Project
2// SPDX-License-Identifier: MPL-2.0
3
4//! A small PNG reader for the `sample_pixel` step (docs/testing.md): the in-process capture
5//! arrives as PNG bytes, and a test asks for the color of one point of it. It reads the
6//! formats a window capture is written in, 8- and 16-bit gray, gray-alpha, RGB and RGBA,
7//! non-interlaced, into RGBA8, with its own inflate (RFC 1951) rather than a dependency: this
8//! engine is linked into every app, and the reader is a few hundred lines.
9
10/// A decoded image: `rgba` holds `width * height` pixels, four bytes each, row by row.
11pub struct Rgba {
12    pub width: usize,
13    pub height: usize,
14    pub rgba: Vec<u8>,
15}
16
17impl Rgba {
18    /// The pixel at (`x`, `y`) as `[r, g, b, a]`, or `None` outside the image.
19    #[must_use]
20    pub fn pixel(&self, x: usize, y: usize) -> Option<[u8; 4]> {
21        if x >= self.width || y >= self.height {
22            return None;
23        }
24        let i = (y * self.width + x) * 4;
25        Some([
26            self.rgba[i],
27            self.rgba[i + 1],
28            self.rgba[i + 2],
29            self.rgba[i + 3],
30        ])
31    }
32}
33
34/// Decode `bytes` as a PNG.
35///
36/// # Errors
37///
38/// Returns an error when `bytes` is not a PNG, is truncated or corrupt, or uses a color type, bit
39/// depth or interlacing this decoder does not support.
40pub fn decode(bytes: &[u8]) -> Result<Rgba, String> {
41    const SIGNATURE: [u8; 8] = [0x89, b'P', b'N', b'G', 0x0d, 0x0a, 0x1a, 0x0a];
42    if bytes.len() < 8 || bytes[..8] != SIGNATURE {
43        return Err("not a PNG".into());
44    }
45    let mut pos = 8;
46    let mut header: Option<(usize, usize, u8, u8, u8)> = None;
47    let mut data = Vec::new();
48    while pos + 8 <= bytes.len() {
49        let len = u32::from_be_bytes([bytes[pos], bytes[pos + 1], bytes[pos + 2], bytes[pos + 3]])
50            as usize;
51        let kind = &bytes[pos + 4..pos + 8];
52        let body = bytes
53            .get(pos + 8..pos + 8 + len)
54            .ok_or("truncated PNG chunk")?;
55        match kind {
56            b"IHDR" => {
57                if body.len() < 13 {
58                    return Err("short IHDR".into());
59                }
60                let be = |i: usize| {
61                    u32::from_be_bytes([body[i], body[i + 1], body[i + 2], body[i + 3]]) as usize
62                };
63                header = Some((be(0), be(4), body[8], body[9], body[12]));
64            }
65            b"IDAT" => data.extend_from_slice(body),
66            b"IEND" => break,
67            _ => {}
68        }
69        // Length, type, body and CRC.
70        pos += 12 + len;
71    }
72    let (width, height, depth, color, interlace) = header.ok_or("no IHDR")?;
73    if interlace != 0 {
74        return Err("interlaced PNG".into());
75    }
76    let channels = match color {
77        0 => 1,
78        2 => 3,
79        4 => 2,
80        6 => 4,
81        _ => return Err(format!("PNG color type {color}")),
82    };
83    if depth != 8 && depth != 16 {
84        return Err(format!("PNG bit depth {depth}"));
85    }
86    let bytes_per_sample = usize::from(depth / 8);
87    let bpp = channels * bytes_per_sample;
88    let stride = width * bpp;
89    // A zlib stream: a two-byte header, the deflate data, then a checksum this ignores.
90    let raw = inflate(data.get(2..).ok_or("empty IDAT")?)?;
91    if raw.len() < height * (stride + 1) {
92        return Err("short image data".into());
93    }
94    let mut pixels = vec![0u8; height * stride];
95    for y in 0..height {
96        let filter = raw[y * (stride + 1)];
97        let line = &raw[y * (stride + 1) + 1..(y + 1) * (stride + 1)];
98        for x in 0..stride {
99            let a = if x >= bpp {
100                pixels[y * stride + x - bpp]
101            } else {
102                0
103            };
104            let b = if y > 0 {
105                pixels[(y - 1) * stride + x]
106            } else {
107                0
108            };
109            let c = if x >= bpp && y > 0 {
110                pixels[(y - 1) * stride + x - bpp]
111            } else {
112                0
113            };
114            let v = line[x];
115            pixels[y * stride + x] = match filter {
116                0 => v,
117                1 => v.wrapping_add(a),
118                2 => v.wrapping_add(b),
119                3 => v.wrapping_add(u16::midpoint(u16::from(a), u16::from(b)) as u8),
120                4 => v.wrapping_add(paeth(a, b, c)),
121                f => return Err(format!("PNG filter {f}")),
122            };
123        }
124    }
125    let mut rgba = Vec::with_capacity(width * height * 4);
126    for px in pixels.chunks_exact(bpp) {
127        // The high byte of a 16-bit sample is its 8-bit value.
128        let s = |i: usize| px[i * bytes_per_sample];
129        match channels {
130            1 => rgba.extend_from_slice(&[s(0), s(0), s(0), 255]),
131            2 => rgba.extend_from_slice(&[s(0), s(0), s(0), s(1)]),
132            3 => rgba.extend_from_slice(&[s(0), s(1), s(2), 255]),
133            _ => rgba.extend_from_slice(&[s(0), s(1), s(2), s(3)]),
134        }
135    }
136    Ok(Rgba {
137        width,
138        height,
139        rgba,
140    })
141}
142
143fn paeth(a: u8, b: u8, c: u8) -> u8 {
144    let p = i16::from(a) + i16::from(b) - i16::from(c);
145    let (pa, pb, pc) = (
146        (p - i16::from(a)).abs(),
147        (p - i16::from(b)).abs(),
148        (p - i16::from(c)).abs(),
149    );
150    if pa <= pb && pa <= pc {
151        a
152    } else if pb <= pc {
153        b
154    } else {
155        c
156    }
157}
158
159// ---------------------------------------------------------------------------
160// Inflate (RFC 1951), after zlib's `puff`: canonical Huffman codes decoded a bit at a time.
161// ---------------------------------------------------------------------------
162
163struct Bits<'a> {
164    data: &'a [u8],
165    pos: usize,
166    bit: u32,
167    count: u32,
168}
169
170impl Bits<'_> {
171    fn need(&mut self, n: u32) -> Result<u32, String> {
172        let mut val = self.bit;
173        while self.count < n {
174            let byte = *self.data.get(self.pos).ok_or("deflate data ran out")?;
175            self.pos += 1;
176            val |= u32::from(byte) << self.count;
177            self.count += 8;
178        }
179        self.bit = val >> n;
180        self.count -= n;
181        Ok(val & ((1u32 << n) - 1))
182    }
183}
184
185/// A canonical Huffman code: how many codes of each length, and the symbols in code order.
186struct Huffman {
187    counts: [u16; 16],
188    symbols: Vec<u16>,
189}
190
191impl Huffman {
192    fn new(lengths: &[u8]) -> Huffman {
193        let mut counts = [0u16; 16];
194        for &l in lengths {
195            counts[usize::from(l)] += 1;
196        }
197        counts[0] = 0;
198        let mut offs = [0u16; 16];
199        for i in 1..16 {
200            offs[i] = offs[i - 1] + counts[i - 1];
201        }
202        let mut symbols = vec![0u16; lengths.len()];
203        for (sym, &l) in lengths.iter().enumerate() {
204            if l != 0 {
205                symbols[usize::from(offs[usize::from(l)])] = sym as u16;
206                offs[usize::from(l)] += 1;
207            }
208        }
209        Huffman { counts, symbols }
210    }
211
212    fn decode(&self, bits: &mut Bits) -> Result<u16, String> {
213        let (mut code, mut first, mut index) = (0i32, 0i32, 0i32);
214        for len in 1..16 {
215            code |= bits.need(1)? as i32;
216            let count = i32::from(self.counts[len]);
217            if code - count < first {
218                return self
219                    .symbols
220                    .get((index + (code - first)) as usize)
221                    .copied()
222                    .ok_or_else(|| "bad Huffman symbol".to_string());
223            }
224            index += count;
225            first += count;
226            first <<= 1;
227            code <<= 1;
228        }
229        Err("bad Huffman code".into())
230    }
231}
232
233const LEN_BASE: [u16; 29] = [
234    3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131,
235    163, 195, 227, 258,
236];
237const LEN_EXTRA: [u8; 29] = [
238    0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0,
239];
240const DIST_BASE: [u16; 30] = [
241    1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537,
242    2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577,
243];
244const DIST_EXTRA: [u8; 30] = [
245    0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13,
246    13,
247];
248
249/// Inflate a raw deflate stream.
250///
251/// # Errors
252///
253/// Returns an error when the stream is truncated or is not valid deflate data.
254pub fn inflate(data: &[u8]) -> Result<Vec<u8>, String> {
255    let mut bits = Bits {
256        data,
257        pos: 0,
258        bit: 0,
259        count: 0,
260    };
261    let mut out = Vec::new();
262    loop {
263        let last = bits.need(1)?;
264        match bits.need(2)? {
265            0 => {
266                // Stored: byte-aligned, a length and its complement, then the bytes as they are.
267                bits.bit = 0;
268                bits.count = 0;
269                let p = bits.pos;
270                let hdr = data.get(p..p + 4).ok_or("short stored block")?;
271                let len = usize::from(u16::from_le_bytes([hdr[0], hdr[1]]));
272                let body = data.get(p + 4..p + 4 + len).ok_or("short stored block")?;
273                out.extend_from_slice(body);
274                bits.pos = p + 4 + len;
275            }
276            1 => {
277                let mut lengths = [0u8; 288];
278                lengths[..144].fill(8);
279                lengths[144..256].fill(9);
280                lengths[256..280].fill(7);
281                lengths[280..].fill(8);
282                let lit = Huffman::new(&lengths);
283                let dist = Huffman::new(&[5u8; 30]);
284                codes(&mut bits, &mut out, &lit, &dist)?;
285            }
286            2 => {
287                const ORDER: [usize; 19] = [
288                    16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15,
289                ];
290                let nlen = bits.need(5)? as usize + 257;
291                let ndist = bits.need(5)? as usize + 1;
292                let ncode = bits.need(4)? as usize + 4;
293                let mut code_lengths = [0u8; 19];
294                for &i in ORDER.iter().take(ncode) {
295                    code_lengths[i] = bits.need(3)? as u8;
296                }
297                let lencode = Huffman::new(&code_lengths);
298                let mut lengths = vec![0u8; nlen + ndist];
299                let mut i = 0;
300                while i < nlen + ndist {
301                    let sym = lencode.decode(&mut bits)?;
302                    let (value, repeat) = match sym {
303                        0..=15 => (sym as u8, 1),
304                        16 => {
305                            let prev = *lengths
306                                .get(i.wrapping_sub(1))
307                                .ok_or("repeat with no previous length")?;
308                            (prev, 3 + bits.need(2)? as usize)
309                        }
310                        17 => (0, 3 + bits.need(3)? as usize),
311                        _ => (0, 11 + bits.need(7)? as usize),
312                    };
313                    for _ in 0..repeat {
314                        *lengths.get_mut(i).ok_or("too many code lengths")? = value;
315                        i += 1;
316                    }
317                }
318                let lit = Huffman::new(&lengths[..nlen]);
319                let dist = Huffman::new(&lengths[nlen..]);
320                codes(&mut bits, &mut out, &lit, &dist)?;
321            }
322            _ => return Err("bad deflate block type".into()),
323        }
324        if last == 1 {
325            return Ok(out);
326        }
327    }
328}
329
330fn codes(bits: &mut Bits, out: &mut Vec<u8>, lit: &Huffman, dist: &Huffman) -> Result<(), String> {
331    loop {
332        let sym = lit.decode(bits)?;
333        match sym {
334            0..=255 => out.push(sym as u8),
335            256 => return Ok(()),
336            _ => {
337                let i = usize::from(sym - 257);
338                let len = usize::from(*LEN_BASE.get(i).ok_or("bad length code")?)
339                    + bits.need(u32::from(LEN_EXTRA[i]))? as usize;
340                let d = usize::from(dist.decode(bits)?);
341                let back = usize::from(*DIST_BASE.get(d).ok_or("bad distance code")?)
342                    + bits.need(u32::from(DIST_EXTRA[d]))? as usize;
343                if back > out.len() {
344                    return Err("distance before the start".into());
345                }
346                let from = out.len() - back;
347                for k in 0..len {
348                    let b = out[from + k];
349                    out.push(b);
350                }
351            }
352        }
353    }
354}
355
356#[cfg(test)]
357mod tests {
358    use super::decode;
359
360    /// Encode with the `png` crate (a dev-dependency only), decode with this reader.
361    fn roundtrip(
362        color: png::ColorType,
363        depth: png::BitDepth,
364        w: u32,
365        h: u32,
366        data: &[u8],
367    ) -> super::Rgba {
368        let mut buf = Vec::new();
369        {
370            let mut enc = png::Encoder::new(&mut buf, w, h);
371            enc.set_color(color);
372            enc.set_depth(depth);
373            enc.set_compression(png::Compression::Balanced);
374            let mut writer = enc.write_header().expect("header");
375            writer.write_image_data(data).expect("data");
376        }
377        decode(&buf).expect("decodes")
378    }
379
380    #[test]
381    fn reads_rgba_and_rgb_with_every_filter_the_encoder_picks() {
382        let (w, h) = (37u32, 23u32);
383        let mut data = Vec::new();
384        for y in 0..h {
385            for x in 0..w {
386                data.extend_from_slice(&[(x * 7) as u8, (y * 11) as u8, ((x ^ y) * 5) as u8, 200]);
387            }
388        }
389        let img = roundtrip(png::ColorType::Rgba, png::BitDepth::Eight, w, h, &data);
390        assert_eq!((img.width, img.height), (37, 23));
391        assert_eq!(img.rgba, data);
392
393        let rgb: Vec<u8> = data.chunks(4).flat_map(|p| [p[0], p[1], p[2]]).collect();
394        let img = roundtrip(png::ColorType::Rgb, png::BitDepth::Eight, w, h, &rgb);
395        assert_eq!(img.pixel(3, 4), Some([21, 44, 35, 255]));
396    }
397
398    #[test]
399    fn reads_gray_and_sixteen_bit_and_refuses_what_it_cannot() {
400        let img = roundtrip(
401            png::ColorType::Grayscale,
402            png::BitDepth::Eight,
403            2,
404            1,
405            &[9, 250],
406        );
407        assert_eq!(img.pixel(1, 0), Some([250, 250, 250, 255]));
408        let img = roundtrip(
409            png::ColorType::Rgb,
410            png::BitDepth::Sixteen,
411            1,
412            1,
413            &[1, 0, 2, 0, 3, 0],
414        );
415        assert_eq!(img.pixel(0, 0), Some([1, 2, 3, 255]));
416        assert!(img.pixel(1, 0).is_none());
417        assert!(decode(b"not a png").is_err());
418    }
419
420    #[test]
421    fn a_large_flat_image_inflates_through_long_back_references() {
422        let (w, h) = (300u32, 200u32);
423        let data = vec![128u8; (w * h * 4) as usize];
424        let img = roundtrip(png::ColorType::Rgba, png::BitDepth::Eight, w, h, &data);
425        assert_eq!(img.pixel(299, 199), Some([128, 128, 128, 128]));
426    }
427}