Debian Codegraph @

.cargo/vendor/png/src/adam7.rs

raw
1 //! Utility functions related to handling of
2 //! [the Adam7 algorithm](https://en.wikipedia.org/wiki/Adam7_algorithm).
3 use core::ops::RangeTo;
4
5 /// Describes which stage of
6 /// [the Adam7 algorithm](https://en.wikipedia.org/wiki/Adam7_algorithm)
7 /// applies to a decoded row.
8 ///
9 /// See also [Reader.next_interlaced_row](crate::decoder::Reader::next_interlaced_row).
10 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
11 pub struct Adam7Info {
12 /// The Adam7 pass number, 1..7.
13 pub(crate) pass: u8,
14 /// The index of the line within this pass.
15 pub(crate) line: u32,
16 /// The original pixel count.
17 pub(crate) width: u32,
18 /// How many Adam7 samples there are.
19 pub(crate) samples: u32,
20 }
21
22 /// The index of a bit in the image buffer.
23 ///
24 /// We do not use a pure `usize` to avoid overflows on 32-bit targets.
25 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
26 struct BitPostion {
27 byte: usize,
28 /// [0..8)
29 bit: u8,
30 }
31
32 impl Adam7Info {
33 /// Creates a new `Adam7Info`. May panic if the arguments are out of range (e.g. if `pass` is
34 /// 0 or greater than 8).
35 ///
36 /// * `pass` corresponds to a pass of the
37 /// [the Adam7 algorithm](https://en.wikipedia.org/wiki/Adam7_algorithm)
38 /// * `line` is the number of a line within a pass (starting with 0). For example,
39 /// in an image of height 8, `line` can be beteween `0..4` in the 7th `pass`
40 /// (those 4 interlaced rows correspond to 2nd, 4th, 6th, and 8th row of the full image).
41 /// * `width` describes how many pixels are in a full row of the image. The bytes in each
42 /// passline of the Adam7 are calculated from this number.
43 ///
44 /// Note that in typical usage, `Adam7Info`s are returned by [Reader.next_interlaced_row]
45 /// and there is no need to create them by calling `Adam7Info::new`. `Adam7Info::new` is
46 /// nevertheless exposed as a public API, because it helps to provide self-contained example
47 /// usage of [expand_interlaced_row](crate::expand_interlaced_row).
48 pub fn new(pass: u8, line: u32, width: u32) -> Self {
49 assert!(1 <= pass && pass <= 7);
50 assert!(width > 0);
51
52 let info = PassConstants::PASSES[pass as usize - 1];
53 let samples = info.count_samples(width);
54
55 Self {
56 pass,
57 line,
58 width,
59 samples,
60 }
61 }
62
63 fn pass_constants(&self) -> PassConstants {
64 PassConstants::PASSES[self.pass as usize - 1]
65 }
66
67 /// How often to repeat a pixel.
68 fn splat_pixel_repeat(self, idx: usize) -> u8 {
69 let pass = self.pass_constants();
70 let x_pixel = idx as u32 * u32::from(pass.x_sampling) + u32::from(pass.x_offset);
71 (self.width - x_pixel).min(pass.splat_x_repeat().into()) as u8
72 }
73
74 fn splat_line_repeat(self, height: u32) -> u8 {
75 let pass = self.pass_constants();
76 let y_line = self.line * u32::from(pass.y_sampling) + u32::from(pass.y_offset);
77 (height - y_line).min(pass.splat_y_repeat().into()) as u8
78 }
79 }
80
81 #[derive(Clone, Copy)]
82 struct PassConstants {
83 x_sampling: u8,
84 x_offset: u8,
85 y_sampling: u8,
86 y_offset: u8,
87 }
88
89 impl PassConstants {
90 const fn splat_x_repeat(self) -> u8 {
91 self.x_sampling - self.x_offset
92 }
93
94 const fn splat_y_repeat(self) -> u8 {
95 self.y_sampling - self.y_offset
96 }
97
98 fn count_samples(self, width: u32) -> u32 {
99 width
100 .saturating_sub(u32::from(self.x_offset))
101 .div_ceil(u32::from(self.x_sampling))
102 }
103
104 fn count_lines(self, height: u32) -> u32 {
105 height
106 .saturating_sub(u32::from(self.y_offset))
107 .div_ceil(u32::from(self.y_sampling))
108 }
109
110 /// The constants associated with each of the 7 passes. Note that it is 0-indexed while the
111 /// pass number (as per specification) is 1-indexed.
112 pub const PASSES: [Self; 7] = {
113 // Shortens the constructor for readability, retains clear argument order below.
114 const fn new(x_sampling: u8, x_offset: u8, y_sampling: u8, y_offset: u8) -> PassConstants {
115 PassConstants {
116 x_sampling,
117 x_offset,
118 y_sampling,
119 y_offset,
120 }
121 }
122
123 [
124 new(8, 0, 8, 0),
125 new(8, 4, 8, 0),
126 new(4, 0, 8, 4),
127 new(4, 2, 4, 0),
128 new(2, 0, 4, 2),
129 new(2, 1, 2, 0),
130 new(1, 0, 2, 1),
131 ]
132 };
133 }
134
135 /// This iterator iterates over the different passes of an image Adam7 encoded
136 /// PNG image
137 /// The pattern is:
138 /// 16462646
139 /// 77777777
140 /// 56565656
141 /// 77777777
142 /// 36463646
143 /// 77777777
144 /// 56565656
145 /// 77777777
146 ///
147 #[derive(Clone)]
148 pub(crate) struct Adam7Iterator {
149 line: u32,
150 lines: u32,
151 line_width: u32,
152 current_pass: u8,
153 width: u32,
154 height: u32,
155 }
156
157 impl Adam7Iterator {
158 pub fn new(width: u32, height: u32) -> Adam7Iterator {
159 let mut this = Adam7Iterator {
160 line: 0,
161 lines: 0,
162 line_width: 0,
163 current_pass: 1,
164 width,
165 height,
166 };
167 this.init_pass();
168 this
169 }
170
171 /// Calculates the bounds of the current pass
172 fn init_pass(&mut self) {
173 let info = PassConstants::PASSES[self.current_pass as usize - 1];
174 self.line_width = info.count_samples(self.width);
175 self.lines = info.count_lines(self.height);
176 self.line = 0;
177 }
178 }
179
180 /// Iterates over `Adam7Info`s.
181 impl Iterator for Adam7Iterator {
182 type Item = Adam7Info;
183 fn next(&mut self) -> Option<Self::Item> {
184 if self.line < self.lines && self.line_width > 0 {
185 let this_line = self.line;
186 self.line += 1;
187 Some(Adam7Info {
188 pass: self.current_pass,
189 line: this_line,
190 width: self.width,
191 samples: self.line_width,
192 })
193 } else if self.current_pass < 7 {
194 self.current_pass += 1;
195 self.init_pass();
196 self.next()
197 } else {
198 None
199 }
200 }
201 }
202
203 /// The algorithm to use when progressively filling pixel data from Adam7 interlaced passes.
204 ///
205 /// Adam7 interlacing is a technique optionally used in PNG by which only a sub-sample of pixel
206 /// data is encoded in the beginning of the image data chunks, followed by progressively larger
207 /// subsets of the data in subsequent passes. Therefore a 'rough image' is available after ust a
208 /// very tiny fraction of the data has been read which can be advantageous for loading an image
209 /// from a slow IO medium while optimizing time-to-first-meaningful-paint and then replacing the
210 /// presented data as it is streamed in.
211 ///
212 /// There are trade-offs to make here. The strictly necessary requirement for an implementation is
213 /// that the exact image is recovered after all passes are applied. However the intermediate states
214 /// of the output are left to the implementation, as long as it follows the restriction of
215 /// resulting in the intended image when all passes have been applied.
216 #[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
217 #[non_exhaustive]
218 pub enum Adam7Variant {
219 /// This is the adam7 de-interlace we do by default. Only pixels related to the pass are
220 /// written. The output buffer should not be directly used for presentation until all passes
221 /// are complete. At least the invalid pixels in the buffer should be masked. However, this
222 /// performs the least amount of writes and is optimal when you're only reading full frames.
223 ///
224 /// This corresponds to [`crate::expand_interlaced_row`].
225 #[default]
226 Sparse,
227 /// A variant of the Adam7 de-interlace that ensures that all pixels are initialized after each
228 /// pass, and are progressively refined towards the final image. Performs more writes than the
229 /// other variant as some pixels are touched repeatedly, but ensures the buffer can be used as
230 /// directly as possible for presentation.
231 ///
232 /// This corresponds to [`crate::splat_interlaced_row`].
233 Splat,
234 }
235
236 fn subbyte_values<const N: usize>(
237 scanline: &[u8],
238 bit_pos: [u8; N],
239 mask: u8,
240 ) -> impl Iterator<Item = u8> + '_ {
241 (scanline.iter().copied()).flat_map(move |value| bit_pos.map(|n| (value >> n) & mask))
242 }
243
244 /// Given `row_stride`, interlace `info`, and bits-per-pixel, produce an iterator of bit positions
245 /// of pixels to copy from the input scanline to the image buffer. The positions are expressed as
246 /// bit offsets from position (0,0) in the frame that is currently being decoded.
247 ///
248 /// This should only be used with `bits_pp < 8`.
249 fn expand_adam7_bits(
250 row_stride_in_bytes: usize,
251 info: &Adam7Info,
252 bits_pp: u8,
253 ) -> impl Iterator<Item = BitPostion> {
254 debug_assert!(bits_pp == 1 || bits_pp == 2 || bits_pp == 4);
255 let (line_mul, line_off, samp_mul, samp_off) = {
256 let constants = info.pass_constants();
257 (
258 // Convert each to their respectively required type from u8.
259 usize::from(constants.y_sampling),
260 usize::from(constants.y_offset),
261 u64::from(constants.x_sampling),
262 u64::from(constants.x_offset),
263 )
264 };
265
266 // the equivalent line number in progressive scan
267 let prog_line = line_mul * info.line as usize + line_off;
268 let byte_start = prog_line * row_stride_in_bytes;
269
270 // In contrast to `subbyte_values` we *must* be precise with our length here.
271 (0..u64::from(info.samples))
272 // Bounded by u32::MAX * 8 * 4 + 16 so does not overflow `u64`.
273 .map(move |i| (i * samp_mul + samp_off) * u64::from(bits_pp))
274 .map(move |i| BitPostion {
275 // Bounded by the buffer size which already exists.
276 byte: byte_start + (i / 8) as usize,
277 bit: i as u8 % 8,
278 })
279 }
280
281 fn expand_adam7_bytes(
282 row_stride_in_bytes: usize,
283 info: &Adam7Info,
284 bytes_pp: u8,
285 ) -> impl Iterator<Item = usize> {
286 let (line_mul, line_off, samp_mul, samp_off) = {
287 let constants = info.pass_constants();
288 (
289 // Convert each to their respectively required type from u8.
290 usize::from(constants.y_sampling),
291 usize::from(constants.y_offset),
292 u64::from(constants.x_sampling),
293 u64::from(constants.x_offset),
294 )
295 };
296
297 // the equivalent line number in progressive scan
298 let prog_line = line_mul * info.line as usize + line_off;
299 let byte_start = prog_line * row_stride_in_bytes;
300
301 (0..u64::from(info.samples))
302 .map(move |i| (i * samp_mul + samp_off) * u64::from(bytes_pp))
303 // Bounded by the allocated buffer size so must fit in `usize`
304 .map(move |i| i as usize + byte_start)
305 }
306
307 /// Copies pixels from `interlaced_row` into the right location in `img`.
308 ///
309 /// First bytes of `img` should belong to the top-left corner of the currently decoded frame.
310 ///
311 /// `img_row_stride` specifies an offset in bytes between subsequent rows of `img`.
312 /// This can be the width of the current frame being decoded, but this is not required - a bigger
313 /// stride may be useful if the frame being decoded is a sub-region of `img`.
314 ///
315 /// `interlaced_row` and `interlace_info` typically come from
316 /// [crate::decoder::Reader::next_interlaced_row], but this is not required. In particular, before
317 /// calling `expand_interlaced_row` one may need to expand the decoded row, so that its format and
318 /// `bits_per_pixel` matches that of `img`. Note that in initial Adam7 passes the `interlaced_row`
319 /// may contain less pixels that the width of the frame being decoded (e.g. it contains only 1/8th
320 /// of pixels in the initial pass).
321 ///
322 /// Example:
323 ///
324 /// ```
325 /// use png::{expand_interlaced_row, Adam7Info};
326 /// let info = Adam7Info::new(5, 0, 8);
327 /// let mut img = vec![0; 8 * 8];
328 /// let row = vec![1, 2, 3, 4];
329 /// expand_interlaced_row(&mut img, 8, &row, &info, 8);
330 /// assert_eq!(&img, &[
331 /// 0, 0, 0, 0, 0, 0, 0, 0,
332 /// 0, 0, 0, 0, 0, 0, 0, 0,
333 /// 1, 0, 2, 0, 3, 0, 4, 0, // <= this is where the 1st line of 5s appears
334 /// 0, 0, 0, 0, 0, 0, 0, 0, // in the schematic drawing of the passes at
335 /// 0, 0, 0, 0, 0, 0, 0, 0, // https://en.wikipedia.org/wiki/Adam7_algorithm
336 /// 0, 0, 0, 0, 0, 0, 0, 0,
337 /// 0, 0, 0, 0, 0, 0, 0, 0,
338 /// 0, 0, 0, 0, 0, 0, 0, 0,
339 /// ]);
340 /// ```
341 pub fn expand_pass(
342 img: &mut [u8],
343 img_row_stride: usize,
344 interlaced_row: &[u8],
345 interlace_info: &Adam7Info,
346 bits_per_pixel: u8,
347 ) {
348 match bits_per_pixel {
349 // Note: for 1, 2, 4 multiple runs through the iteration will access the same byte in `img`
350 // so we can not iterate over `&mut u8` values. A better strategy would write multiple bit
351 // groups in one go. This would then also not be as bounds-check heavy?
352 1 => {
353 const BIT_POS_1: [u8; 8] = [7, 6, 5, 4, 3, 2, 1, 0];
354 let bit_indices = expand_adam7_bits(img_row_stride, interlace_info, 1);
355 for (pos, px) in bit_indices.zip(subbyte_values(interlaced_row, BIT_POS_1, 0b1)) {
356 let shift = 8 - bits_per_pixel - pos.bit;
357 img[pos.byte] |= px << shift;
358 }
359 }
360 2 => {
361 const BIT_POS_2: [u8; 4] = [6, 4, 2, 0];
362 let bit_indices = expand_adam7_bits(img_row_stride, interlace_info, 2);
363
364 for (pos, px) in bit_indices.zip(subbyte_values(interlaced_row, BIT_POS_2, 0b11)) {
365 let shift = 8 - bits_per_pixel - pos.bit;
366 img[pos.byte] |= px << shift;
367 }
368 }
369 4 => {
370 const BIT_POS_4: [u8; 2] = [4, 0];
371 let bit_indices = expand_adam7_bits(img_row_stride, interlace_info, 4);
372
373 for (pos, px) in bit_indices.zip(subbyte_values(interlaced_row, BIT_POS_4, 0b1111)) {
374 let shift = 8 - bits_per_pixel - pos.bit;
375 img[pos.byte] |= px << shift;
376 }
377 }
378 // While caught by the below loop, we special case this for codegen. The effects are
379 // massive when the compiler uses the constant chunk size in particular for this case where
380 // no more copy_from_slice is being issued by everything happens in the register alone.
381 8 => {
382 let byte_indices = expand_adam7_bytes(img_row_stride, interlace_info, 1);
383
384 for (bytepos, &px) in byte_indices.zip(interlaced_row) {
385 img[bytepos] = px;
386 }
387 }
388 16 => {
389 let byte_indices = expand_adam7_bytes(img_row_stride, interlace_info, 2);
390
391 for (bytepos, px) in byte_indices.zip(interlaced_row.chunks(2)) {
392 img[bytepos..][..2].copy_from_slice(px);
393 }
394 }
395 _ => {
396 debug_assert!(bits_per_pixel % 8 == 0);
397 let bytes_pp = bits_per_pixel / 8;
398 let byte_indices = expand_adam7_bytes(img_row_stride, interlace_info, bytes_pp);
399
400 for (bytepos, px) in byte_indices.zip(interlaced_row.chunks(bytes_pp.into())) {
401 img[bytepos..][..px.len()].copy_from_slice(px);
402 }
403 }
404 }
405 }
406
407 /// Expand pass, but also ensure that after each pass the whole image has been initialized up to
408 /// the data available. In constrast to `expand_pass` there are no holes left in the image.
409 ///
410 /// For instance, consider the first pass which is an eighth subsampling of the original image.
411 /// Here's a side by-side of pixel data written from each of the two algorithms:
412 ///
413 /// ```text
414 /// normal: splat:
415 /// 1------- 11111111
416 /// -------- 11111111
417 /// -------- 11111111
418 /// -------- 11111111
419 /// -------- 11111111
420 /// -------- 11111111
421 /// -------- 11111111
422 /// ```
423 ///
424 /// Data written in previous passes must not be modified. We 'weave' the data of passes and repeat
425 /// them in the neighbouring pixels until their subsampling alignment. For details, see the
426 /// `x_repeat` and `y_repeat` data. Thus the 4th pass would look like this:
427 ///
428 /// ```text
429 /// normal: splat:
430 /// --4---4- --44--44
431 /// -------- --44--44
432 /// -------- --44--44
433 /// --4---4- --44--44
434 /// -------- --44--44
435 /// -------- --44--44
436 /// -------- --44--44
437 /// ```
438 ///
439 pub fn expand_pass_splat(
440 img: &mut [u8],
441 img_row_stride: usize,
442 interlaced_row: &[u8],
443 interlace_info: &Adam7Info,
444 bits_per_pixel: u8,
445 ) {
446 fn expand_bits_to_img(
447 img: &mut [u8],
448 px: u8,
449 mut pos: BitPostion,
450 repeat: RangeTo<u8>,
451 bpp: u8,
452 ) {
453 let (mut into, mut tail) = img[pos.byte..].split_first_mut().unwrap();
454 let mask = (1u8 << bpp) - 1;
455
456 for _ in 0..repeat.end {
457 if pos.bit >= 8 {
458 pos.byte += 1;
459 pos.bit -= 8;
460
461 (into, tail) = tail.split_first_mut().unwrap();
462 }
463
464 let shift = 8 - bpp - pos.bit;
465 // Preserve all other bits, but be prepared for existing bits
466 let pre = (*into >> shift) & mask;
467 *into ^= (pre ^ px) << shift;
468
469 pos.bit += bpp;
470 }
471 }
472
473 let height = (img.len() / img_row_stride) as u32;
474 let y_repeat = interlace_info.splat_line_repeat(height);
475 debug_assert!(y_repeat > 0);
476
477 match bits_per_pixel {
478 // Note: for 1, 2, 4 multiple runs through the iteration will access the same byte in `img`
479 // so we can not iterate over `&mut u8` values. A better strategy would write multiple bit
480 // groups in one go. This would then also not be as bounds-check heavy?
481 1 => {
482 const BIT_POS_1: [u8; 8] = [7, 6, 5, 4, 3, 2, 1, 0];
483
484 for offset in 0..y_repeat {
485 let bit_indices = expand_adam7_bits(img_row_stride, interlace_info, 1);
486 let line_offset = usize::from(offset) * img_row_stride;
487
488 for (idx, (mut pos, px)) in bit_indices
489 .zip(subbyte_values(interlaced_row, BIT_POS_1, 0b1))
490 .enumerate()
491 {
492 let x_repeat = interlace_info.splat_pixel_repeat(idx);
493 debug_assert!(x_repeat > 0);
494 pos.byte += line_offset;
495 expand_bits_to_img(img, px, pos, ..x_repeat, bits_per_pixel);
496 }
497 }
498 }
499 2 => {
500 const BIT_POS_2: [u8; 4] = [6, 4, 2, 0];
501
502 for offset in 0..y_repeat {
503 let bit_indices = expand_adam7_bits(img_row_stride, interlace_info, 2);
504 let line_offset = usize::from(offset) * img_row_stride;
505
506 for (idx, (mut pos, px)) in bit_indices
507 .zip(subbyte_values(interlaced_row, BIT_POS_2, 0b11))
508 .enumerate()
509 {
510 let x_repeat = interlace_info.splat_pixel_repeat(idx);
511 pos.byte += line_offset;
512 expand_bits_to_img(img, px, pos, ..x_repeat, bits_per_pixel);
513 }
514 }
515 }
516 4 => {
517 const BIT_POS_4: [u8; 2] = [4, 0];
518
519 for offset in 0..y_repeat {
520 let bit_indices = expand_adam7_bits(img_row_stride, interlace_info, 4);
521 let line_offset = usize::from(offset) * img_row_stride;
522
523 for (idx, (mut pos, px)) in bit_indices
524 .zip(subbyte_values(interlaced_row, BIT_POS_4, 0b1111))
525 .enumerate()
526 {
527 let x_repeat = interlace_info.splat_pixel_repeat(idx);
528 pos.byte += line_offset;
529 expand_bits_to_img(img, px, pos, ..x_repeat, bits_per_pixel);
530 }
531 }
532 }
533 // While caught by the below loop, we special case this for codegen. The effects are
534 // massive when the compiler uses the constant chunk size in particular for this case where
535 // no more copy_from_slice is being issued by everything happens in the register alone.
536 8 => {
537 for offset in 0..y_repeat {
538 let byte_indices = expand_adam7_bytes(img_row_stride, interlace_info, 1);
539 let line_offset = usize::from(offset) * img_row_stride;
540
541 for (idx, (bytepos, px)) in byte_indices.zip(interlaced_row).enumerate() {
542 let x_repeat = usize::from(interlace_info.splat_pixel_repeat(idx));
543 debug_assert!(x_repeat > 0);
544 img[line_offset + bytepos..][..x_repeat].fill(*px);
545 }
546 }
547 }
548 _ => {
549 debug_assert!(bits_per_pixel % 8 == 0);
550 let bytes = bits_per_pixel / 8;
551 let chunk = usize::from(bytes);
552
553 for offset in 0..y_repeat {
554 let byte_indices = expand_adam7_bytes(img_row_stride, interlace_info, bytes);
555 let line_offset = usize::from(offset) * img_row_stride;
556
557 for (idx, (bytepos, px)) in byte_indices
558 .zip(interlaced_row.chunks_exact(chunk))
559 .enumerate()
560 {
561 let x_repeat = usize::from(interlace_info.splat_pixel_repeat(idx));
562 let target = &mut img[line_offset + bytepos..][..chunk * x_repeat];
563
564 for target in target.chunks_exact_mut(chunk) {
565 target.copy_from_slice(px);
566 }
567 }
568 }
569 }
570 }
571 }
572
573 #[cfg(test)]
574 mod tests {
575 use super::*;
576
577 #[test]
578 fn test_adam7() {
579 /*
580 1646
581 7777
582 5656
583 7777
584 */
585 let it = Adam7Iterator::new(4, 4);
586 let passes: Vec<_> = it.collect();
587 assert_eq!(
588 &*passes,
589 &[
590 Adam7Info {
591 pass: 1,
592 line: 0,
593 samples: 1,
594 width: 4,
595 },
596 Adam7Info {
597 pass: 4,
598 line: 0,
599 samples: 1,
600 width: 4,
601 },
602 Adam7Info {
603 pass: 5,
604 line: 0,
605 samples: 2,
606 width: 4,
607 },
608 Adam7Info {
609 pass: 6,
610 line: 0,
611 samples: 2,
612 width: 4,
613 },
614 Adam7Info {
615 pass: 6,
616 line: 1,
617 samples: 2,
618 width: 4,
619 },
620 Adam7Info {
621 pass: 7,
622 line: 0,
623 samples: 4,
624 width: 4,
625 },
626 Adam7Info {
627 pass: 7,
628 line: 1,
629 samples: 4,
630 width: 4,
631 }
632 ]
633 );
634 }
635
636 #[test]
637 fn test_subbyte_pixels() {
638 const BIT_POS_1: [u8; 8] = [7, 6, 5, 4, 3, 2, 1, 0];
639
640 let scanline = &[0b10101010, 0b10101010];
641 let pixels = subbyte_values(scanline, BIT_POS_1, 1).collect::<Vec<_>>();
642
643 assert_eq!(pixels.len(), 16);
644 assert_eq!(pixels, [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]);
645 }
646
647 #[test]
648 fn test_expand_adam7_bits() {
649 let width = 32;
650 let bits_pp = 1;
651 let stride = width / 8;
652 let info =
653 |pass, line, img_width| create_adam7_info_for_tests(pass, line as u32, img_width);
654
655 let expected = |offset: usize, step: usize, count: usize| {
656 (0..count)
657 .map(move |i| step * i + offset)
658 .map(|i| BitPostion {
659 byte: i / 8,
660 bit: (i % 8) as u8,
661 })
662 .collect::<Vec<_>>()
663 };
664
665 for line_no in 0..8 {
666 let start = 8 * line_no * width;
667
668 assert_eq!(
669 expand_adam7_bits(stride, &info(1, line_no, width), bits_pp).collect::<Vec<_>>(),
670 expected(start, 8, 4)
671 );
672
673 let start = start + 4;
674
675 assert_eq!(
676 expand_adam7_bits(stride, &info(2, line_no, width), bits_pp).collect::<Vec<_>>(),
677 expected(start, 8, 4)
678 );
679
680 let start = (8 * line_no + 4) * width;
681
682 assert_eq!(
683 expand_adam7_bits(stride, &info(3, line_no, width), bits_pp).collect::<Vec<_>>(),
684 expected(start, 4, 8)
685 );
686 }
687
688 for line_no in 0..16 {
689 let start = 4 * line_no * width + 2;
690
691 assert_eq!(
692 expand_adam7_bits(stride, &info(4, line_no, width), bits_pp).collect::<Vec<_>>(),
693 expected(start, 4, 8)
694 );
695
696 let start = (4 * line_no + 2) * width;
697
698 assert_eq!(
699 expand_adam7_bits(stride, &info(5, line_no, width), bits_pp).collect::<Vec<_>>(),
700 expected(start, 2, 16)
701 )
702 }
703
704 for line_no in 0..32 {
705 let start = 2 * line_no * width + 1;
706
707 assert_eq!(
708 expand_adam7_bits(stride, &info(6, line_no, width), bits_pp).collect::<Vec<_>>(),
709 expected(start, 2, 16),
710 "line_no: {}",
711 line_no
712 );
713
714 let start = (2 * line_no + 1) * width;
715
716 assert_eq!(
717 expand_adam7_bits(stride, &info(7, line_no, width), bits_pp).collect::<Vec<_>>(),
718 expected(start, 1, 32)
719 );
720 }
721 }
722
723 #[test]
724 fn test_expand_adam7_bits_independent_row_stride() {
725 let pass = 1;
726 let line_no = 1;
727 let width = 32;
728 let info = create_adam7_info_for_tests;
729
730 {
731 let stride = width;
732 assert_eq!(
733 expand_adam7_bytes(stride, &info(pass, line_no, width), 1).collect::<Vec<_>>(),
734 [2048, 2112, 2176, 2240].map(|n| n / 8),
735 );
736 }
737
738 {
739 let stride = 10000;
740 assert_eq!(
741 expand_adam7_bytes(stride, &info(pass, line_no, width), 1).collect::<Vec<_>>(),
742 [640000, 640064, 640128, 640192].map(|n| n / 8),
743 );
744 }
745 }
746
747 #[test]
748 fn test_expand_pass_subbyte() {
749 let mut img = [0u8; 8];
750 let width = 8;
751 let stride = width / 8;
752 let bits_pp = 1;
753 let info = create_adam7_info_for_tests;
754
755 expand_pass(&mut img, stride, &[0b10000000], &info(1, 0, width), bits_pp);
756 assert_eq!(img, [0b10000000u8, 0, 0, 0, 0, 0, 0, 0]);
757
758 expand_pass(&mut img, stride, &[0b10000000], &info(2, 0, width), bits_pp);
759 assert_eq!(img, [0b10001000u8, 0, 0, 0, 0, 0, 0, 0]);
760
761 expand_pass(&mut img, stride, &[0b11000000], &info(3, 0, width), bits_pp);
762 assert_eq!(img, [0b10001000u8, 0, 0, 0, 0b10001000, 0, 0, 0]);
763
764 expand_pass(&mut img, stride, &[0b11000000], &info(4, 0, width), bits_pp);
765 assert_eq!(img, [0b10101010u8, 0, 0, 0, 0b10001000, 0, 0, 0]);
766
767 expand_pass(&mut img, stride, &[0b11000000], &info(4, 1, width), bits_pp);
768 assert_eq!(img, [0b10101010u8, 0, 0, 0, 0b10101010, 0, 0, 0]);
769
770 expand_pass(&mut img, stride, &[0b11110000], &info(5, 0, width), bits_pp);
771 assert_eq!(img, [0b10101010u8, 0, 0b10101010, 0, 0b10101010, 0, 0, 0]);
772
773 expand_pass(&mut img, stride, &[0b11110000], &info(5, 1, width), bits_pp);
774 assert_eq!(
775 img,
776 [0b10101010u8, 0, 0b10101010, 0, 0b10101010, 0, 0b10101010, 0]
777 );
778
779 expand_pass(&mut img, stride, &[0b11110000], &info(6, 0, width), bits_pp);
780 assert_eq!(
781 img,
782 [0b11111111u8, 0, 0b10101010, 0, 0b10101010, 0, 0b10101010, 0]
783 );
784
785 expand_pass(&mut img, stride, &[0b11110000], &info(6, 1, width), bits_pp);
786 assert_eq!(
787 img,
788 [0b11111111u8, 0, 0b11111111, 0, 0b10101010, 0, 0b10101010, 0]
789 );
790
791 expand_pass(&mut img, stride, &[0b11110000], &info(6, 2, width), bits_pp);
792 assert_eq!(
793 img,
794 [0b11111111u8, 0, 0b11111111, 0, 0b11111111, 0, 0b10101010, 0]
795 );
796
797 expand_pass(&mut img, stride, &[0b11110000], &info(6, 3, width), bits_pp);
798 assert_eq!(
799 [0b11111111u8, 0, 0b11111111, 0, 0b11111111, 0, 0b11111111, 0],
800 img
801 );
802
803 expand_pass(&mut img, stride, &[0b11111111], &info(7, 0, width), bits_pp);
804 assert_eq!(
805 [
806 0b11111111u8,
807 0b11111111,
808 0b11111111,
809 0,
810 0b11111111,
811 0,
812 0b11111111,
813 0
814 ],
815 img
816 );
817
818 expand_pass(&mut img, stride, &[0b11111111], &info(7, 1, width), bits_pp);
819 assert_eq!(
820 [
821 0b11111111u8,
822 0b11111111,
823 0b11111111,
824 0b11111111,
825 0b11111111,
826 0,
827 0b11111111,
828 0
829 ],
830 img
831 );
832
833 expand_pass(&mut img, stride, &[0b11111111], &info(7, 2, width), bits_pp);
834 assert_eq!(
835 [
836 0b11111111u8,
837 0b11111111,
838 0b11111111,
839 0b11111111,
840 0b11111111,
841 0b11111111,
842 0b11111111,
843 0
844 ],
845 img
846 );
847
848 expand_pass(&mut img, stride, &[0b11111111], &info(7, 3, width), bits_pp);
849 assert_eq!(
850 [
851 0b11111111u8,
852 0b11111111,
853 0b11111111,
854 0b11111111,
855 0b11111111,
856 0b11111111,
857 0b11111111,
858 0b11111111
859 ],
860 img
861 );
862 }
863
864 // We use 4bpp as representative for bit-fiddling passes bpp 1, 2, 4. The choice was made
865 // because it is succinct to write in hex so one can read this and understand it.
866 #[test]
867 fn test_expand_pass_splat_4bpp() {
868 let width = 8;
869 let bits_pp = 4;
870
871 let mut img = [0u8; 8];
872 let stride = width / 2;
873
874 let passes: &[(&'static [u8], &'static [u8])] = &[
875 (&[0x10], &[0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11]), // pass 1, 0
876 (&[0x20], &[0x11, 0x11, 0x22, 0x22, 0x11, 0x11, 0x22, 0x22]), // pass 2, 0
877 // no third pass..
878 (&[0x4a], &[0x11, 0x44, 0x22, 0xaa, 0x11, 0x44, 0x22, 0xaa]), // pass 4, 0
879 // no fifth pass..
880 (
881 &[0x6b, 0x6b],
882 &[0x16, 0x4b, 0x26, 0xab, 0x16, 0x4b, 0x26, 0xab],
883 ), // pass 6, 0
884 (
885 &[0x7c, 0xc7, 0x7c, 0x7c],
886 &[0x16, 0x4b, 0x26, 0xab, 0x7c, 0xc7, 0x7c, 0x7c],
887 ), // pass 7, 0
888 ];
889
890 let adam7 = Adam7Iterator::new(8, 2);
891 for ((data, expected), adam7_info) in passes.iter().zip(adam7) {
892 expand_pass_splat(&mut img, stride, data, &adam7_info, bits_pp);
893 assert_eq!(img, *expected, "{img:x?} {expected:x?} {adam7_info:?}");
894 }
895 }
896
897 /// Check that our different Adam7 strategies lead to the same result once all interlace lines
898 /// have been applied.
899 #[test]
900 fn adam7_equivalence() {
901 // Choose ragged sizes to cover bugs that write outside etc.
902 const WIDTH: u32 = 8;
903 const HEIGHT: u32 = 8;
904
905 let interace_pool: Vec<_> = (0x42u8..).take(32).collect();
906
907 for &bpp in &[1u8, 2, 4, 8, 16, 24, 32][2..] {
908 let bytes_of = |pix: u32| (u32::from(bpp) * pix).next_multiple_of(8) as usize / 8;
909
910 let rowbytes = bytes_of(WIDTH);
911
912 // In the sparse case we do not promise to override all bits
913 let mut buf_sparse = vec![0x00; rowbytes * HEIGHT as usize];
914 // Whereas in the spat case we do, so we may as well set some arbitrary initial
915 let mut buf_splat = vec![0xaa; rowbytes * HEIGHT as usize];
916
917 // Now execute all the iterations, then compare buffers.
918 for adam7_info in Adam7Iterator::new(WIDTH, HEIGHT) {
919 let adam7_bytes = bytes_of(adam7_info.samples);
920 let interlace_line = &interace_pool[..adam7_bytes];
921
922 expand_pass(&mut buf_sparse, rowbytes, interlace_line, &adam7_info, bpp);
923 expand_pass_splat(&mut buf_splat, rowbytes, interlace_line, &adam7_info, bpp);
924 }
925
926 assert_eq!(
927 buf_sparse, buf_splat,
928 "{buf_sparse:x?} {buf_splat:x?} bpp={bpp}"
929 );
930 }
931 }
932
933 #[test]
934 fn test_expand_pass_splat_1bpp() {
935 let width = 8;
936 let bits_pp = 1;
937
938 let mut img = [0u8; 8];
939 let stride = 1;
940
941 // Since bits do not suffice to represent the pass number in pixels we choose interlace
942 // rows such that we toggle all affected bits each time. In particular the input bits that
943 // must not be used are set to the inverse.
944 let passes: &[(&'static [u8], &'static [u8])] = &[
945 (&[0x80], &[0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]), // pass 1, 0
946 (&[0x7f], &[0xf0, 0xf0, 0xf0, 0xf0, 0xf0, 0xf0, 0xf0, 0xf0]), // pass 2, 0
947 (&[0xc0], &[0xf0, 0xf0, 0xf0, 0xf0, 0xff, 0xff, 0xff, 0xff]), // pass 3, 0
948 (&[0x3f], &[0xc0, 0xc0, 0xc0, 0xc0, 0xff, 0xff, 0xff, 0xff]), // pass 4, 0
949 (&[0x3f], &[0xc0, 0xc0, 0xc0, 0xc0, 0xcc, 0xcc, 0xcc, 0xcc]), // pass 4, 1
950 (&[0xf0], &[0xc0, 0xc0, 0xff, 0xff, 0xcc, 0xcc, 0xcc, 0xcc]), // pass 5, 0
951 (&[0xf0], &[0xc0, 0xc0, 0xff, 0xff, 0xcc, 0xcc, 0xff, 0xff]), // pass 5, 1
952 (&[0x0f], &[0x80, 0x80, 0xff, 0xff, 0xcc, 0xcc, 0xff, 0xff]), // pass 6, 0
953 (&[0x0f], &[0x80, 0x80, 0xaa, 0xaa, 0xcc, 0xcc, 0xff, 0xff]), // pass 6, 1
954 (&[0x0f], &[0x80, 0x80, 0xaa, 0xaa, 0x88, 0x88, 0xff, 0xff]), // pass 6, 2
955 (&[0x0f], &[0x80, 0x80, 0xaa, 0xaa, 0x88, 0x88, 0xaa, 0xaa]), // pass 6, 3
956 (&[0xff], &[0x80, 0xff, 0xaa, 0xaa, 0x88, 0x88, 0xaa, 0xaa]), // pass 7, 0
957 (&[0xff], &[0x80, 0xff, 0xaa, 0xff, 0x88, 0x88, 0xaa, 0xaa]), // pass 7, 1
958 (&[0xff], &[0x80, 0xff, 0xaa, 0xff, 0x88, 0xff, 0xaa, 0xaa]), // pass 7, 2
959 (&[0xff], &[0x80, 0xff, 0xaa, 0xff, 0x88, 0xff, 0xaa, 0xff]), // pass 7, 3
960 ];
961
962 let adam7 = Adam7Iterator::new(width, 8);
963 for ((data, expected), adam7_info) in passes.iter().zip(adam7) {
964 expand_pass_splat(&mut img, stride, data, &adam7_info, bits_pp);
965 assert_eq!(img, *expected, "{img:x?} {expected:x?} {adam7_info:?}");
966 }
967 }
968
969 /// This test ensures that `expand_pass` works correctly on 32-bit machines, even when the indices
970 /// of individual bits in the target buffer can not be expressed within a `usize`. We ensure that
971 /// the output buffer size is between `usize::MAX / 8` and `isize::MAX` to trigger that condition.
972 #[cfg(target_pointer_width = "32")]
973 #[test]
974 fn regression_overflow_adam7_bitfill() {
975 fn multibyte_expand_pass_test_helper(width: usize, height: usize, bits_pp: u8) -> Vec<u8> {
976 let bytes_pp = bits_pp / 8;
977 let size = width * height * bytes_pp as usize;
978 let mut img = vec![0u8; size];
979 let img_row_stride = width * bytes_pp as usize;
980
981 for it in Adam7Iterator::new(width as u32, height as u32).into_iter() {
982 if it.pass != 7 {
983 continue;
984 }
985
986 if it.line != (width / 2) as u32 - 1 {
987 continue;
988 }
989
990 let interlace_size = it.width * (bytes_pp as u32);
991 // Ensure that expanded pixels are never empty bits. This differentiates the written bits
992 // from the initial bits that are all zeroed.
993 let interlaced_row: Vec<_> = (0..interlace_size).map(|_| 0xff).collect();
994
995 expand_pass(&mut img, img_row_stride, &interlaced_row, &it, bits_pp);
996 }
997
998 img
999 }
1000
1001 let expanded = multibyte_expand_pass_test_helper(1 << 14, 1 << 14, 32);
1002 assert_eq!(*expanded.last().unwrap(), 0xff);
1003 }
1004
1005 #[cfg(test)]
1006 fn create_adam7_info_for_tests(pass: u8, line: u32, img_width: usize) -> Adam7Info {
1007 let width = {
1008 let img_height = 8;
1009 Adam7Iterator::new(img_width as u32, img_height)
1010 .filter(|info| info.pass == pass)
1011 .map(|info| info.samples)
1012 .next()
1013 .unwrap()
1014 };
1015
1016 Adam7Info {
1017 pass,
1018 line,
1019 samples: width,
1020 width,
1021 }
1022 }
1023 }