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

png/
adam7.rs
