png/
adam7.rs

1//! Utility functions related to handling of
2//! [the Adam7 algorithm](https://en.wikipedia.org/wiki/Adam7_algorithm).
3use 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)]
11pub 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)]
26struct BitPostion {
27    byte: usize,
28    /// [0..8)
29    bit: u8,
30}
31
32impl 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)]
82struct PassConstants {
83    x_sampling: u8,
84    x_offset: u8,
85    y_sampling: u8,
86    y_offset: u8,
87}
88
89impl 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)]
148pub(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
157impl 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.
181impl 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]
218pub 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
236fn 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`.
249fn 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
281fn 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/// ```
341pub 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///
439pub 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)]
574mod 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}
png/adam7.rs

png/
adam7.rs
