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