1pub struct Rgba {
12 pub width: usize,
13 pub height: usize,
14 pub rgba: Vec<u8>,
15}
16
17impl Rgba {
18 #[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
34pub struct Png {
41 pub width: usize,
42 pub height: usize,
43 channels: usize,
44 bytes_per_sample: usize,
45 data: Vec<u8>,
47}
48
49impl Png {
50 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 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 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 fn bpp(&self) -> usize {
135 self.channels * self.bytes_per_sample
136 }
137
138 fn rgba_of(&self, px: &[u8]) -> [u8; 4] {
140 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 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 let need = rows * (stride + 1);
157 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
187pub 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
225struct 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
251struct 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
315pub fn inflate(data: &[u8]) -> Result<Vec<u8>, String> {
321 inflate_up_to(data, usize::MAX)
322}
323
324const MAX_RESERVE: usize = 64 << 20;
326
327fn 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 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
408fn 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 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 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}