1//! Utility functions related to handling of
2//! [the Adam7 algorithm](https://en.wikipedia.org/wiki/Adam7_algorithm).
3
4/// Describes which stage of
5/// [the Adam7 algorithm](https://en.wikipedia.org/wiki/Adam7_algorithm)
6/// applies to a decoded row.
7///
8/// See also [Reader.next_interlaced_row](crate::decoder::Reader::next_interlaced_row).
9#[derive(Clone, Copy, Debug, PartialEq, Eq)]
10pub struct Adam7Info {
11 pub(crate) pass: u8,
12 pub(crate) line: u32,
13 pub(crate) width: u32,
14}
15
16impl Adam7Info {
17 /// Creates a new `Adam7Info`. May panic if the arguments are out of range (e.g. if `pass` is
18 /// 0 or greater than 8).
19 ///
20 /// * `pass` corresponds to a pass of the
21 /// [the Adam7 algorithm](https://en.wikipedia.org/wiki/Adam7_algorithm)
22 /// * `line` is the number of a line within a pass (starting with 0). For example,
23 /// in an image of height 8, `line` can be beteween `0..4` in the 7th `pass`
24 /// (those 4 interlaced rows correspond to 2nd, 4th, 6th, and 8th row of the full image).
25 /// * `width` describes how many pixels are in an interlaced row. For example,
26 /// in the 7th `pass`, the `width` is be the same as full image width, but in
27 /// in the 1st `pass`, the `width` is be 1/8th of the image width (rounded up as
28 /// necessary).
29 ///
30 /// Note that in typical usage, `Adam7Info`s are returned by [Reader.next_interlaced_row]
31 /// and there is no need to create them by calling `Adam7Info::new`. `Adam7Info::new` is
32 /// nevertheless exposed as a public API, because it helps to provide self-contained example
33 /// usage of [expand_interlaced_row](crate::expand_interlaced_row).
34 pub fn new(pass: u8, line: u32, width: u32) -> Self {
35 assert!(1 <= pass && pass <= 7);
36 assert!(width > 0);
37 Self { pass, line, width }
38 }
39}
40
41/// This iterator iterates over the different passes of an image Adam7 encoded
42/// PNG image
43/// The pattern is:
44/// 16462646
45/// 77777777
46/// 56565656
47/// 77777777
48/// 36463646
49/// 77777777
50/// 56565656
51/// 77777777
52///
53#[derive(Clone)]
54pub(crate) struct Adam7Iterator {
55 line: u32,
56 lines: u32,
57 line_width: u32,
58 current_pass: u8,
59 width: u32,
60 height: u32,
61}
62
63impl Adam7Iterator {
64 pub fn new(width: u32, height: u32) -> Adam7Iterator {
65 let mut this = Adam7Iterator {
66 line: 0,
67 lines: 0,
68 line_width: 0,
69 current_pass: 1,
70 width,
71 height,
72 };
73 this.init_pass();
74 this
75 }
76
77 /// Calculates the bounds of the current pass
78 fn init_pass(&mut self) {
79 let w = f64::from(self.width);
80 let h = f64::from(self.height);
81 let (line_width, lines) = match self.current_pass {
82 1 => (w / 8.0, h / 8.0),
83 2 => ((w - 4.0) / 8.0, h / 8.0),
84 3 => (w / 4.0, (h - 4.0) / 8.0),
85 4 => ((w - 2.0) / 4.0, h / 4.0),
86 5 => (w / 2.0, (h - 2.0) / 4.0),
87 6 => ((w - 1.0) / 2.0, h / 2.0),
88 7 => (w, (h - 1.0) / 2.0),
89 _ => unreachable!(),
90 };
91 self.line_width = line_width.ceil() as u32;
92 self.lines = lines.ceil() as u32;
93 self.line = 0;
94 }
95}
96
97/// Iterates over `Adam7Info`s.
98impl Iterator for Adam7Iterator {
99 type Item = Adam7Info;
100 fn next(&mut self) -> Option<Self::Item> {
101 if self.line < self.lines && self.line_width > 0 {
102 let this_line: u32 = self.line;
103 self.line += 1;
104 Some(Adam7Info {
105 pass: self.current_pass,
106 line: this_line,
107 width: self.line_width,
108 })
109 } else if self.current_pass < 7 {
110 self.current_pass += 1;
111 self.init_pass();
112 self.next()
113 } else {
114 None
115 }
116 }
117}
118
119fn subbyte_pixels(scanline: &[u8], bits_pp: usize) -> impl Iterator<Item = u8> + '_ {
120 (0..scanline.len() * 8)
121 .step_by(step:bits_pp)
122 .map(move |bit_idx: usize| {
123 let byte_idx: usize = bit_idx / 8;
124
125 // sub-byte samples start in the high-order bits
126 let rem: usize = 8 - bit_idx % 8 - bits_pp;
127
128 match bits_pp {
129 // evenly divides bytes
130 1 => (scanline[byte_idx] >> rem) & 1,
131 2 => (scanline[byte_idx] >> rem) & 3,
132 4 => (scanline[byte_idx] >> rem) & 15,
133 _ => unreachable!(),
134 }
135 })
136}
137
138/// Given `row_stride`, interlace `info`, and bits-per-pixel, produce an iterator of bit positions
139/// of pixels to copy from the input scanline to the image buffer. The positions are expressed as
140/// bit offsets from position (0,0) in the frame that is currently being decoded.
141fn expand_adam7_bits(
142 row_stride_in_bytes: usize,
143 info: &Adam7Info,
144 bits_pp: usize,
145) -> impl Iterator<Item = usize> {
146 let line_no = info.line as usize;
147 let pass = info.pass;
148 let interlaced_width = info.width as usize;
149
150 let (line_mul, line_off, samp_mul, samp_off) = match pass {
151 1 => (8, 0, 8, 0),
152 2 => (8, 0, 8, 4),
153 3 => (8, 4, 4, 0),
154 4 => (4, 0, 4, 2),
155 5 => (4, 2, 2, 0),
156 6 => (2, 0, 2, 1),
157 7 => (2, 1, 1, 0),
158 _ => {
159 // `Adam7Info.pass` is a non-`pub`lic field. `InterlaceInfo` is expected
160 // to maintain an invariant that `pass` is valid.
161 panic!("Invalid `Adam7Info.pass`");
162 }
163 };
164
165 // the equivalent line number in progressive scan
166 let prog_line = line_mul * line_no + line_off;
167 let line_start = prog_line * row_stride_in_bytes * 8;
168
169 (0..interlaced_width)
170 .map(move |i| i * samp_mul + samp_off)
171 .map(move |i| i * bits_pp)
172 .map(move |bits_offset| bits_offset + line_start)
173}
174
175/// Copies pixels from `interlaced_row` into the right location in `img`.
176///
177/// First bytes of `img` should belong to the top-left corner of the currently decoded frame.
178///
179/// `img_row_stride` specifies an offset in bytes between subsequent rows of `img`.
180/// This can be the width of the current frame being decoded, but this is not required - a bigger
181/// stride may be useful if the frame being decoded is a sub-region of `img`.
182///
183/// `interlaced_row` and `interlace_info` typically come from
184/// [crate::decoder::Reader::next_interlaced_row], but this is not required. In particular, before
185/// calling `expand_interlaced_row` one may need to expand the decoded row, so that its format and
186/// `bits_per_pixel` matches that of `img`. Note that in initial Adam7 passes the `interlaced_row`
187/// may contain less pixels that the width of the frame being decoded (e.g. it contains only 1/8th
188/// of pixels in the initial pass).
189///
190/// Example:
191///
192/// ```
193/// use png::{expand_interlaced_row, Adam7Info};
194/// let info = Adam7Info::new(5, 0, 4); // 1st line of 5th pass has 4 pixels.
195/// let mut img = vec![0; 8 * 8];
196/// let row = vec![1, 2, 3, 4];
197/// expand_interlaced_row(&mut img, 8, &row, &info, 8);
198/// assert_eq!(&img, &[
199/// 0, 0, 0, 0, 0, 0, 0, 0,
200/// 0, 0, 0, 0, 0, 0, 0, 0,
201/// 1, 0, 2, 0, 3, 0, 4, 0, // <= this is where the 1st line of 5s appears
202/// 0, 0, 0, 0, 0, 0, 0, 0, // in the schematic drawing of the passes at
203/// 0, 0, 0, 0, 0, 0, 0, 0, // https://en.wikipedia.org/wiki/Adam7_algorithm
204/// 0, 0, 0, 0, 0, 0, 0, 0,
205/// 0, 0, 0, 0, 0, 0, 0, 0,
206/// 0, 0, 0, 0, 0, 0, 0, 0,
207/// ]);
208/// ```
209pub fn expand_pass(
210 img: &mut [u8],
211 img_row_stride: usize,
212 interlaced_row: &[u8],
213 interlace_info: &Adam7Info,
214 bits_per_pixel: u8,
215) {
216 let bits_pp: usize = bits_per_pixel as usize;
217
218 let bit_indices: impl Iterator = expand_adam7_bits(row_stride_in_bytes:img_row_stride, interlace_info, bits_pp);
219
220 if bits_pp < 8 {
221 for (pos: usize, px: u8) in bit_indices.zip(subbyte_pixels(scanline:interlaced_row, bits_pp)) {
222 let rem: usize = 8 - pos % 8 - bits_pp;
223 img[pos / 8] |= px << rem as u8;
224 }
225 } else {
226 let bytes_pp: usize = bits_pp / 8;
227
228 for (bitpos: usize, px: &[u8]) in bit_indices.zip(interlaced_row.chunks(chunk_size:bytes_pp)) {
229 for (offset: usize, val: &u8) in px.iter().enumerate() {
230 img[bitpos / 8 + offset] = *val;
231 }
232 }
233 }
234}
235
236#[test]
237fn test_adam7() {
238 /*
239 1646
240 7777
241 5656
242 7777
243 */
244 let it = Adam7Iterator::new(4, 4);
245 let passes: Vec<_> = it.collect();
246 assert_eq!(
247 &*passes,
248 &[
249 Adam7Info {
250 pass: 1,
251 line: 0,
252 width: 1
253 },
254 Adam7Info {
255 pass: 4,
256 line: 0,
257 width: 1
258 },
259 Adam7Info {
260 pass: 5,
261 line: 0,
262 width: 2
263 },
264 Adam7Info {
265 pass: 6,
266 line: 0,
267 width: 2
268 },
269 Adam7Info {
270 pass: 6,
271 line: 1,
272 width: 2
273 },
274 Adam7Info {
275 pass: 7,
276 line: 0,
277 width: 4
278 },
279 Adam7Info {
280 pass: 7,
281 line: 1,
282 width: 4
283 }
284 ]
285 );
286}
287
288#[test]
289fn test_subbyte_pixels() {
290 let scanline = &[0b10101010, 0b10101010];
291
292 let pixels = subbyte_pixels(scanline, 1).collect::<Vec<_>>();
293 assert_eq!(pixels.len(), 16);
294 assert_eq!(pixels, [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]);
295}
296
297#[test]
298fn test_expand_adam7_bits() {
299 let width = 32;
300 let bits_pp = 1;
301 let stride = width / 8;
302 let info = |pass, line, img_width| create_adam7_info_for_tests(pass, line as u32, img_width);
303
304 let expected = |offset: usize, step: usize, count: usize| {
305 (0..count)
306 .map(move |i| step * i + offset)
307 .collect::<Vec<_>>()
308 };
309
310 for line_no in 0..8 {
311 let start = 8 * line_no * width;
312
313 assert_eq!(
314 expand_adam7_bits(stride, &info(1, line_no, width), bits_pp).collect::<Vec<_>>(),
315 expected(start, 8, 4)
316 );
317
318 let start = start + 4;
319
320 assert_eq!(
321 expand_adam7_bits(stride, &info(2, line_no, width), bits_pp).collect::<Vec<_>>(),
322 expected(start, 8, 4)
323 );
324
325 let start = (8 * line_no + 4) * width;
326
327 assert_eq!(
328 expand_adam7_bits(stride, &info(3, line_no, width), bits_pp).collect::<Vec<_>>(),
329 expected(start, 4, 8)
330 );
331 }
332
333 for line_no in 0..16 {
334 let start = 4 * line_no * width + 2;
335
336 assert_eq!(
337 expand_adam7_bits(stride, &info(4, line_no, width), bits_pp).collect::<Vec<_>>(),
338 expected(start, 4, 8)
339 );
340
341 let start = (4 * line_no + 2) * width;
342
343 assert_eq!(
344 expand_adam7_bits(stride, &info(5, line_no, width), bits_pp).collect::<Vec<_>>(),
345 expected(start, 2, 16)
346 )
347 }
348
349 for line_no in 0..32 {
350 let start = 2 * line_no * width + 1;
351
352 assert_eq!(
353 expand_adam7_bits(stride, &info(6, line_no, width), bits_pp).collect::<Vec<_>>(),
354 expected(start, 2, 16),
355 "line_no: {}",
356 line_no
357 );
358
359 let start = (2 * line_no + 1) * width;
360
361 assert_eq!(
362 expand_adam7_bits(stride, &info(7, line_no, width), bits_pp).collect::<Vec<_>>(),
363 expected(start, 1, 32)
364 );
365 }
366}
367
368#[test]
369fn test_expand_adam7_bits_independent_row_stride() {
370 let pass = 1;
371 let line_no = 1;
372 let width = 32;
373 let bits_pp = 8;
374 let info = create_adam7_info_for_tests;
375
376 {
377 let stride = width;
378 assert_eq!(
379 expand_adam7_bits(stride, &info(pass, line_no, width), bits_pp).collect::<Vec<_>>(),
380 vec![2048, 2112, 2176, 2240],
381 );
382 }
383
384 {
385 let stride = 10000;
386 assert_eq!(
387 expand_adam7_bits(stride, &info(pass, line_no, width), bits_pp).collect::<Vec<_>>(),
388 vec![640000, 640064, 640128, 640192],
389 );
390 }
391}
392
393#[test]
394fn test_expand_pass_subbyte() {
395 let mut img = [0u8; 8];
396 let width = 8;
397 let stride = width / 8;
398 let bits_pp = 1;
399 let info = create_adam7_info_for_tests;
400
401 expand_pass(&mut img, stride, &[0b10000000], &info(1, 0, width), bits_pp);
402 assert_eq!(img, [0b10000000u8, 0, 0, 0, 0, 0, 0, 0]);
403
404 expand_pass(&mut img, stride, &[0b10000000], &info(2, 0, width), bits_pp);
405 assert_eq!(img, [0b10001000u8, 0, 0, 0, 0, 0, 0, 0]);
406
407 expand_pass(&mut img, stride, &[0b11000000], &info(3, 0, width), bits_pp);
408 assert_eq!(img, [0b10001000u8, 0, 0, 0, 0b10001000, 0, 0, 0]);
409
410 expand_pass(&mut img, stride, &[0b11000000], &info(4, 0, width), bits_pp);
411 assert_eq!(img, [0b10101010u8, 0, 0, 0, 0b10001000, 0, 0, 0]);
412
413 expand_pass(&mut img, stride, &[0b11000000], &info(4, 1, width), bits_pp);
414 assert_eq!(img, [0b10101010u8, 0, 0, 0, 0b10101010, 0, 0, 0]);
415
416 expand_pass(&mut img, stride, &[0b11110000], &info(5, 0, width), bits_pp);
417 assert_eq!(img, [0b10101010u8, 0, 0b10101010, 0, 0b10101010, 0, 0, 0]);
418
419 expand_pass(&mut img, stride, &[0b11110000], &info(5, 1, width), bits_pp);
420 assert_eq!(
421 img,
422 [0b10101010u8, 0, 0b10101010, 0, 0b10101010, 0, 0b10101010, 0]
423 );
424
425 expand_pass(&mut img, stride, &[0b11110000], &info(6, 0, width), bits_pp);
426 assert_eq!(
427 img,
428 [0b11111111u8, 0, 0b10101010, 0, 0b10101010, 0, 0b10101010, 0]
429 );
430
431 expand_pass(&mut img, stride, &[0b11110000], &info(6, 1, width), bits_pp);
432 assert_eq!(
433 img,
434 [0b11111111u8, 0, 0b11111111, 0, 0b10101010, 0, 0b10101010, 0]
435 );
436
437 expand_pass(&mut img, stride, &[0b11110000], &info(6, 2, width), bits_pp);
438 assert_eq!(
439 img,
440 [0b11111111u8, 0, 0b11111111, 0, 0b11111111, 0, 0b10101010, 0]
441 );
442
443 expand_pass(&mut img, stride, &[0b11110000], &info(6, 3, width), bits_pp);
444 assert_eq!(
445 [0b11111111u8, 0, 0b11111111, 0, 0b11111111, 0, 0b11111111, 0],
446 img
447 );
448
449 expand_pass(&mut img, stride, &[0b11111111], &info(7, 0, width), bits_pp);
450 assert_eq!(
451 [
452 0b11111111u8,
453 0b11111111,
454 0b11111111,
455 0,
456 0b11111111,
457 0,
458 0b11111111,
459 0
460 ],
461 img
462 );
463
464 expand_pass(&mut img, stride, &[0b11111111], &info(7, 1, width), bits_pp);
465 assert_eq!(
466 [
467 0b11111111u8,
468 0b11111111,
469 0b11111111,
470 0b11111111,
471 0b11111111,
472 0,
473 0b11111111,
474 0
475 ],
476 img
477 );
478
479 expand_pass(&mut img, stride, &[0b11111111], &info(7, 2, width), bits_pp);
480 assert_eq!(
481 [
482 0b11111111u8,
483 0b11111111,
484 0b11111111,
485 0b11111111,
486 0b11111111,
487 0b11111111,
488 0b11111111,
489 0
490 ],
491 img
492 );
493
494 expand_pass(&mut img, stride, &[0b11111111], &info(7, 3, width), bits_pp);
495 assert_eq!(
496 [
497 0b11111111u8,
498 0b11111111,
499 0b11111111,
500 0b11111111,
501 0b11111111,
502 0b11111111,
503 0b11111111,
504 0b11111111
505 ],
506 img
507 );
508}
509
510#[cfg(test)]
511fn create_adam7_info_for_tests(pass: u8, line: u32, img_width: usize) -> Adam7Info {
512 let width = {
513 let img_height = 8;
514 Adam7Iterator::new(img_width as u32, img_height)
515 .filter(|info| info.pass == pass)
516 .map(|info| info.width)
517 .next()
518 .unwrap()
519 };
520
521 Adam7Info { pass, line, width }
522}
523