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 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 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 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 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
159struct 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
185struct 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
249pub 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 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 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}