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/// A PNG read as far as its header: the size is known, the pixels are not decoded yet.
35///
36/// `sample_pixel` wants one point of a window capture. Decoding the whole capture for it held
37/// three full copies of a 2560×1600 window (the inflated stream, the unfiltered rows and the
38/// RGBA expansion) and took about a second and a half per step in a debug build; a
39/// [`pixel`](Png::pixel) read stops inflating at the pixel's row and keeps two rows.
40pub struct Png {
41    pub width: usize,
42    pub height: usize,
43    channels: usize,
44    bytes_per_sample: usize,
45    /// The zlib stream: every IDAT body, joined.
46    data: Vec<u8>,
47}
48
49impl Png {
50    /// Read `bytes`'s header and gather its image data, without inflating it.
51    ///
52    /// # Errors
53    ///
54    /// Returns an error when `bytes` is not a PNG, is truncated, or uses a color type, bit
55    /// depth or interlacing this reader does not support.
56    pub fn read(bytes: &[u8]) -> Result<Png, String> {
57        const SIGNATURE: [u8; 8] = [0x89, b'P', b'N', b'G', 0x0d, 0x0a, 0x1a, 0x0a];
58        if bytes.len() < 8 || bytes[..8] != SIGNATURE {
59            return Err("not a PNG".into());
60        }
61        let mut pos = 8;
62        let mut header: Option<(usize, usize, u8, u8, u8)> = None;
63        let mut data = Vec::new();
64        while pos + 8 <= bytes.len() {
65            let len =
66                u32::from_be_bytes([bytes[pos], bytes[pos + 1], bytes[pos + 2], bytes[pos + 3]])
67                    as usize;
68            let kind = &bytes[pos + 4..pos + 8];
69            let body = bytes
70                .get(pos + 8..pos + 8 + len)
71                .ok_or("truncated PNG chunk")?;
72            match kind {
73                b"IHDR" => {
74                    if body.len() < 13 {
75                        return Err("short IHDR".into());
76                    }
77                    let be = |i: usize| {
78                        u32::from_be_bytes([body[i], body[i + 1], body[i + 2], body[i + 3]])
79                            as usize
80                    };
81                    header = Some((be(0), be(4), body[8], body[9], body[12]));
82                }
83                b"IDAT" => data.extend_from_slice(body),
84                b"IEND" => break,
85                _ => {}
86            }
87            // Length, type, body and CRC.
88            pos += 12 + len;
89        }
90        let (width, height, depth, color, interlace) = header.ok_or("no IHDR")?;
91        if interlace != 0 {
92            return Err("interlaced PNG".into());
93        }
94        let channels = match color {
95            0 => 1,
96            2 => 3,
97            4 => 2,
98            6 => 4,
99            _ => return Err(format!("PNG color type {color}")),
100        };
101        if depth != 8 && depth != 16 {
102            return Err(format!("PNG bit depth {depth}"));
103        }
104        Ok(Png {
105            width,
106            height,
107            channels,
108            bytes_per_sample: usize::from(depth / 8),
109            data,
110        })
111    }
112
113    /// The pixel at (`x`, `y`) as `[r, g, b, a]`, or `None` outside the image. Only the rows
114    /// down to `y` are inflated and unfiltered.
115    ///
116    /// # Errors
117    ///
118    /// Returns an error when the image data is truncated or corrupt.
119    pub fn pixel(&self, x: usize, y: usize) -> Result<Option<[u8; 4]>, String> {
120        if x >= self.width || y >= self.height {
121            return Ok(None);
122        }
123        let bpp = self.bpp();
124        let mut found = None;
125        self.rows(y + 1, |row, line| {
126            if row == y {
127                found = Some(self.rgba_of(&line[x * bpp..(x + 1) * bpp]));
128            }
129        })?;
130        Ok(found)
131    }
132
133    /// Bytes per pixel.
134    fn bpp(&self) -> usize {
135        self.channels * self.bytes_per_sample
136    }
137
138    /// One pixel's samples as RGBA8.
139    fn rgba_of(&self, px: &[u8]) -> [u8; 4] {
140        // The high byte of a 16-bit sample is its 8-bit value.
141        let s = |i: usize| px[i * self.bytes_per_sample];
142        match self.channels {
143            1 => [s(0), s(0), s(0), 255],
144            2 => [s(0), s(0), s(0), s(1)],
145            3 => [s(0), s(1), s(2), 255],
146            _ => [s(0), s(1), s(2), s(3)],
147        }
148    }
149
150    /// Inflate and unfilter the first `rows` rows, handing each to `row` in order. Only the
151    /// row being built and the one above it, which the filters read, are kept.
152    fn rows(&self, rows: usize, mut row: impl FnMut(usize, &[u8])) -> Result<(), String> {
153        let bpp = self.bpp();
154        let stride = self.width * bpp;
155        // Each row is a filter byte, then its samples.
156        let need = rows * (stride + 1);
157        // A zlib stream: a two-byte header, the deflate data, then a checksum this ignores.
158        let raw = inflate_up_to(self.data.get(2..).ok_or("empty IDAT")?, need)?;
159        if raw.len() < need {
160            return Err("short image data".into());
161        }
162        let mut above = vec![0u8; stride];
163        let mut line = vec![0u8; stride];
164        for (y, filtered) in raw[..need].chunks_exact(stride + 1).enumerate() {
165            let (filter, samples) = (filtered[0], &filtered[1..]);
166            for x in 0..stride {
167                let a = if x >= bpp { line[x - bpp] } else { 0 };
168                let b = above[x];
169                let c = if x >= bpp { above[x - bpp] } else { 0 };
170                let v = samples[x];
171                line[x] = match filter {
172                    0 => v,
173                    1 => v.wrapping_add(a),
174                    2 => v.wrapping_add(b),
175                    3 => v.wrapping_add(u16::midpoint(u16::from(a), u16::from(b)) as u8),
176                    4 => v.wrapping_add(paeth(a, b, c)),
177                    f => return Err(format!("PNG filter {f}")),
178                };
179            }
180            row(y, &line);
181            std::mem::swap(&mut above, &mut line);
182        }
183        Ok(())
184    }
185}
186
187/// Decode `bytes` as a PNG.
188///
189/// # Errors
190///
191/// Returns an error when `bytes` is not a PNG, is truncated or corrupt, or uses a color type, bit
192/// depth or interlacing this decoder does not support.
193pub fn decode(bytes: &[u8]) -> Result<Rgba, String> {
194    let png = Png::read(bytes)?;
195    let bpp = png.bpp();
196    let mut rgba = Vec::with_capacity(png.width * png.height * 4);
197    png.rows(png.height, |_, line| {
198        for px in line.chunks_exact(bpp) {
199            rgba.extend_from_slice(&png.rgba_of(px));
200        }
201    })?;
202    Ok(Rgba {
203        width: png.width,
204        height: png.height,
205        rgba,
206    })
207}
208
209fn paeth(a: u8, b: u8, c: u8) -> u8 {
210    let p = i16::from(a) + i16::from(b) - i16::from(c);
211    let (pa, pb, pc) = (
212        (p - i16::from(a)).abs(),
213        (p - i16::from(b)).abs(),
214        (p - i16::from(c)).abs(),
215    );
216    if pa <= pb && pa <= pc {
217        a
218    } else if pb <= pc {
219        b
220    } else {
221        c
222    }
223}
224
225// ---------------------------------------------------------------------------
226// Inflate (RFC 1951), after zlib's `puff`: canonical Huffman codes decoded a bit at a time.
227// ---------------------------------------------------------------------------
228
229struct Bits<'a> {
230    data: &'a [u8],
231    pos: usize,
232    bit: u32,
233    count: u32,
234}
235
236impl Bits<'_> {
237    fn need(&mut self, n: u32) -> Result<u32, String> {
238        let mut val = self.bit;
239        while self.count < n {
240            let byte = *self.data.get(self.pos).ok_or("deflate data ran out")?;
241            self.pos += 1;
242            val |= u32::from(byte) << self.count;
243            self.count += 8;
244        }
245        self.bit = val >> n;
246        self.count -= n;
247        Ok(val & ((1u32 << n) - 1))
248    }
249}
250
251/// A canonical Huffman code: how many codes of each length, and the symbols in code order.
252struct Huffman {
253    counts: [u16; 16],
254    symbols: Vec<u16>,
255}
256
257impl Huffman {
258    fn new(lengths: &[u8]) -> Huffman {
259        let mut counts = [0u16; 16];
260        for &l in lengths {
261            counts[usize::from(l)] += 1;
262        }
263        counts[0] = 0;
264        let mut offs = [0u16; 16];
265        for i in 1..16 {
266            offs[i] = offs[i - 1] + counts[i - 1];
267        }
268        let mut symbols = vec![0u16; lengths.len()];
269        for (sym, &l) in lengths.iter().enumerate() {
270            if l != 0 {
271                symbols[usize::from(offs[usize::from(l)])] = sym as u16;
272                offs[usize::from(l)] += 1;
273            }
274        }
275        Huffman { counts, symbols }
276    }
277
278    fn decode(&self, bits: &mut Bits) -> Result<u16, String> {
279        let (mut code, mut first, mut index) = (0i32, 0i32, 0i32);
280        for len in 1..16 {
281            code |= bits.need(1)? as i32;
282            let count = i32::from(self.counts[len]);
283            if code - count < first {
284                return self
285                    .symbols
286                    .get((index + (code - first)) as usize)
287                    .copied()
288                    .ok_or_else(|| "bad Huffman symbol".to_string());
289            }
290            index += count;
291            first += count;
292            first <<= 1;
293            code <<= 1;
294        }
295        Err("bad Huffman code".into())
296    }
297}
298
299const LEN_BASE: [u16; 29] = [
300    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,
301    163, 195, 227, 258,
302];
303const LEN_EXTRA: [u8; 29] = [
304    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,
305];
306const DIST_BASE: [u16; 30] = [
307    1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537,
308    2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577,
309];
310const DIST_EXTRA: [u8; 30] = [
311    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,
312    13,
313];
314
315/// Inflate a raw deflate stream.
316///
317/// # Errors
318///
319/// Returns an error when the stream is truncated or is not valid deflate data.
320pub fn inflate(data: &[u8]) -> Result<Vec<u8>, String> {
321    inflate_up_to(data, usize::MAX)
322}
323
324/// The most [`inflate_up_to`] reserves ahead: a header's claim, not yet borne out by data.
325const MAX_RESERVE: usize = 64 << 20;
326
327/// Inflate a raw deflate stream until at least `limit` bytes are out (or the stream ends),
328/// into a buffer reserved for `limit` up front rather than grown by doubling.
329fn inflate_up_to(data: &[u8], limit: usize) -> Result<Vec<u8>, String> {
330    let mut bits = Bits {
331        data,
332        pos: 0,
333        bit: 0,
334        count: 0,
335    };
336    let mut out = Vec::with_capacity(limit.min(MAX_RESERVE));
337    loop {
338        if out.len() >= limit {
339            return Ok(out);
340        }
341        let last = bits.need(1)?;
342        match bits.need(2)? {
343            0 => {
344                // Stored: byte-aligned, a length and its complement, then the bytes as they are.
345                bits.bit = 0;
346                bits.count = 0;
347                let p = bits.pos;
348                let hdr = data.get(p..p + 4).ok_or("short stored block")?;
349                let len = usize::from(u16::from_le_bytes([hdr[0], hdr[1]]));
350                let body = data.get(p + 4..p + 4 + len).ok_or("short stored block")?;
351                out.extend_from_slice(body);
352                bits.pos = p + 4 + len;
353            }
354            1 => {
355                let mut lengths = [0u8; 288];
356                lengths[..144].fill(8);
357                lengths[144..256].fill(9);
358                lengths[256..280].fill(7);
359                lengths[280..].fill(8);
360                let lit = Huffman::new(&lengths);
361                let dist = Huffman::new(&[5u8; 30]);
362                codes(&mut bits, &mut out, &lit, &dist, limit)?;
363            }
364            2 => {
365                const ORDER: [usize; 19] = [
366                    16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15,
367                ];
368                let nlen = bits.need(5)? as usize + 257;
369                let ndist = bits.need(5)? as usize + 1;
370                let ncode = bits.need(4)? as usize + 4;
371                let mut code_lengths = [0u8; 19];
372                for &i in ORDER.iter().take(ncode) {
373                    code_lengths[i] = bits.need(3)? as u8;
374                }
375                let lencode = Huffman::new(&code_lengths);
376                let mut lengths = vec![0u8; nlen + ndist];
377                let mut i = 0;
378                while i < nlen + ndist {
379                    let sym = lencode.decode(&mut bits)?;
380                    let (value, repeat) = match sym {
381                        0..=15 => (sym as u8, 1),
382                        16 => {
383                            let prev = *lengths
384                                .get(i.wrapping_sub(1))
385                                .ok_or("repeat with no previous length")?;
386                            (prev, 3 + bits.need(2)? as usize)
387                        }
388                        17 => (0, 3 + bits.need(3)? as usize),
389                        _ => (0, 11 + bits.need(7)? as usize),
390                    };
391                    for _ in 0..repeat {
392                        *lengths.get_mut(i).ok_or("too many code lengths")? = value;
393                        i += 1;
394                    }
395                }
396                let lit = Huffman::new(&lengths[..nlen]);
397                let dist = Huffman::new(&lengths[nlen..]);
398                codes(&mut bits, &mut out, &lit, &dist, limit)?;
399            }
400            _ => return Err("bad deflate block type".into()),
401        }
402        if last == 1 {
403            return Ok(out);
404        }
405    }
406}
407
408/// Decode one block's codes into `out`, stopping early once `out` holds `limit` bytes.
409fn codes(
410    bits: &mut Bits,
411    out: &mut Vec<u8>,
412    lit: &Huffman,
413    dist: &Huffman,
414    limit: usize,
415) -> Result<(), String> {
416    loop {
417        if out.len() >= limit {
418            return Ok(());
419        }
420        let sym = lit.decode(bits)?;
421        match sym {
422            0..=255 => out.push(sym as u8),
423            256 => return Ok(()),
424            _ => {
425                let i = usize::from(sym - 257);
426                let len = usize::from(*LEN_BASE.get(i).ok_or("bad length code")?)
427                    + bits.need(u32::from(LEN_EXTRA[i]))? as usize;
428                let d = usize::from(dist.decode(bits)?);
429                let back = usize::from(*DIST_BASE.get(d).ok_or("bad distance code")?)
430                    + bits.need(u32::from(DIST_EXTRA[d]))? as usize;
431                if back > out.len() {
432                    return Err("distance before the start".into());
433                }
434                let from = out.len() - back;
435                if back >= len {
436                    out.extend_from_within(from..from + len);
437                } else {
438                    // An overlapping copy repeats the bytes it has just written.
439                    for k in 0..len {
440                        let b = out[from + k];
441                        out.push(b);
442                    }
443                }
444            }
445        }
446    }
447}
448
449#[cfg(test)]
450mod tests {
451    use super::{Png, decode};
452
453    /// Encode with the `png` crate (a dev-dependency only), decode with this reader.
454    fn roundtrip(
455        color: png::ColorType,
456        depth: png::BitDepth,
457        w: u32,
458        h: u32,
459        data: &[u8],
460    ) -> super::Rgba {
461        let mut buf = Vec::new();
462        {
463            let mut enc = png::Encoder::new(&mut buf, w, h);
464            enc.set_color(color);
465            enc.set_depth(depth);
466            enc.set_compression(png::Compression::Balanced);
467            let mut writer = enc.write_header().expect("header");
468            writer.write_image_data(data).expect("data");
469        }
470        decode(&buf).expect("decodes")
471    }
472
473    #[test]
474    fn reads_rgba_and_rgb_with_every_filter_the_encoder_picks() {
475        let (w, h) = (37u32, 23u32);
476        let mut data = Vec::new();
477        for y in 0..h {
478            for x in 0..w {
479                data.extend_from_slice(&[(x * 7) as u8, (y * 11) as u8, ((x ^ y) * 5) as u8, 200]);
480            }
481        }
482        let img = roundtrip(png::ColorType::Rgba, png::BitDepth::Eight, w, h, &data);
483        assert_eq!((img.width, img.height), (37, 23));
484        assert_eq!(img.rgba, data);
485
486        let rgb: Vec<u8> = data.chunks(4).flat_map(|p| [p[0], p[1], p[2]]).collect();
487        let img = roundtrip(png::ColorType::Rgb, png::BitDepth::Eight, w, h, &rgb);
488        assert_eq!(img.pixel(3, 4), Some([21, 44, 35, 255]));
489    }
490
491    #[test]
492    fn reads_gray_and_sixteen_bit_and_refuses_what_it_cannot() {
493        let img = roundtrip(
494            png::ColorType::Grayscale,
495            png::BitDepth::Eight,
496            2,
497            1,
498            &[9, 250],
499        );
500        assert_eq!(img.pixel(1, 0), Some([250, 250, 250, 255]));
501        let img = roundtrip(
502            png::ColorType::Rgb,
503            png::BitDepth::Sixteen,
504            1,
505            1,
506            &[1, 0, 2, 0, 3, 0],
507        );
508        assert_eq!(img.pixel(0, 0), Some([1, 2, 3, 255]));
509        assert!(img.pixel(1, 0).is_none());
510        assert!(decode(b"not a png").is_err());
511    }
512
513    #[test]
514    fn one_pixel_reads_the_same_as_a_whole_decode() {
515        let (w, h) = (41u32, 29u32);
516        let mut data = Vec::new();
517        for y in 0..h {
518            for x in 0..w {
519                data.extend_from_slice(&[(x * 13) as u8, (y * 7) as u8, ((x * y) % 251) as u8, 99]);
520            }
521        }
522        let mut buf = Vec::new();
523        {
524            let mut enc = png::Encoder::new(&mut buf, w, h);
525            enc.set_color(png::ColorType::Rgba);
526            enc.set_depth(png::BitDepth::Eight);
527            enc.set_compression(png::Compression::Balanced);
528            let mut writer = enc.write_header().expect("header");
529            writer.write_image_data(&data).expect("data");
530        }
531        let whole = decode(&buf).expect("decodes");
532        let png = Png::read(&buf).expect("reads");
533        assert_eq!((png.width, png.height), (41, 29));
534        for (x, y) in [(0, 0), (40, 0), (17, 11), (0, 28), (40, 28)] {
535            assert_eq!(png.pixel(x, y).expect("inflates"), whole.pixel(x, y));
536        }
537        assert_eq!(png.pixel(41, 0).expect("in range check"), None);
538        assert_eq!(png.pixel(0, 29).expect("in range check"), None);
539    }
540
541    #[test]
542    fn a_large_flat_image_inflates_through_long_back_references() {
543        let (w, h) = (300u32, 200u32);
544        let data = vec![128u8; (w * h * 4) as usize];
545        let img = roundtrip(png::ColorType::Rgba, png::BitDepth::Eight, w, h, &data);
546        assert_eq!(img.pixel(299, 199), Some([128, 128, 128, 128]));
547    }
548}