1pub struct Rgba {
12 pub width: usize,
13 pub height: usize,
14 pub rgba: Vec<u8>,
15}
16
17impl Rgba {
18 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
33pub 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 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 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 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
153struct 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
179struct 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
243pub 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 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 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}