Skip to main content

pltrs_codec/png/
filter.rs

1//! Scanline filters (PNG spec ยง9): each byte is predicted from the
2//! corresponding bytes of the pixel to its left, the pixel above and the
3//! pixel above-left, and only the prediction error is stored.
4
5use std::ops::Range;
6
7use pltrs_core::alloc::{self, OutOfMemory};
8
9use crate::deflate::encode::RowSource;
10
11/// A scanline filter type.
12#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
13pub enum FilterType {
14    /// Bytes are stored unchanged.
15    None,
16    /// Predict from the pixel to the left.
17    Sub,
18    /// Predict from the pixel above.
19    Up,
20    /// Predict from the mean of the left and upper pixels.
21    Average,
22    /// Predict with the Paeth predictor (left, above or above-left).
23    Paeth,
24}
25
26impl FilterType {
27    /// The filters [`FilterStrategy::Adaptive`] tries after none, in
28    /// Pillow's order.
29    const TRIED: [Self; 3] = [Self::Up, Self::Sub, Self::Paeth];
30
31    /// The filter with type byte `byte`.
32    pub(crate) const fn from_byte(byte: u8) -> Option<Self> {
33        match byte {
34            0 => Some(Self::None),
35            1 => Some(Self::Sub),
36            2 => Some(Self::Up),
37            3 => Some(Self::Average),
38            4 => Some(Self::Paeth),
39            _ => None,
40        }
41    }
42
43    /// The type byte that precedes each filtered row.
44    pub(crate) const fn byte(self) -> u8 {
45        match self {
46            Self::None => 0,
47            Self::Sub => 1,
48            Self::Up => 2,
49            Self::Average => 3,
50            Self::Paeth => 4,
51        }
52    }
53}
54
55/// How the encoder chooses a filter for each row.
56#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
57pub enum FilterStrategy {
58    /// Pillow's choice for each row: no filter, unless Up, then Sub, then
59    /// Paeth gives a smaller sum of absolute values (bytes read as signed),
60    /// a heuristic taken from libpng.
61    #[default]
62    Adaptive,
63    /// Use the same filter for every row.
64    Fixed(FilterType),
65}
66
67/// The filtered rows of an image, each prefixed with its filter type byte
68/// (what the `IDAT` stream compresses), made a row at a time as the
69/// compressor takes them rather than filtered into a copy of the whole
70/// image.
71#[derive(Debug)]
72pub(crate) struct FilteredRows<'a> {
73    data: &'a [u8],
74    row_bytes: usize,
75    stride: usize,
76    strategy: FilterStrategy,
77    /// The row last filtered, if any.
78    filtered_row: Option<usize>,
79    /// That row: its type byte, then its filtered bytes.
80    filtered: Vec<u8>,
81    /// Room for the other filters an adaptive choice tries.
82    candidate: Vec<u8>,
83    /// The row above the first.
84    zero_row: Vec<u8>,
85}
86
87impl<'a> FilteredRows<'a> {
88    /// The rows of `data` (each `row_bytes` long, pixels `stride` bytes
89    /// apart) filtered as `strategy` chooses.
90    ///
91    /// # Errors
92    ///
93    /// When the memory for a row cannot be allocated.
94    pub(crate) fn new(
95        data: &'a [u8],
96        row_bytes: usize,
97        stride: usize,
98        strategy: FilterStrategy,
99    ) -> Result<Self, OutOfMemory> {
100        let zeros = |len: usize| -> Result<Vec<u8>, OutOfMemory> {
101            let mut row = alloc::try_with_capacity(len)?;
102            row.resize(len, 0);
103            Ok(row)
104        };
105        Ok(Self {
106            data,
107            row_bytes,
108            stride,
109            strategy,
110            filtered_row: None,
111            filtered: zeros(row_bytes + 1)?,
112            candidate: zeros(row_bytes + 1)?,
113            zero_row: zeros(row_bytes)?,
114        })
115    }
116
117    /// Filters row `index` into `filtered`, unless it is there already.
118    fn filter_row(&mut self, index: usize) {
119        if self.filtered_row == Some(index) {
120            return;
121        }
122        let row_bytes = self.row_bytes;
123        let current = &self.data[index * row_bytes..(index + 1) * row_bytes];
124        let previous = match index.checked_sub(1) {
125            Some(above) => &self.data[above * row_bytes..index * row_bytes],
126            None => &self.zero_row,
127        };
128        let row = Row {
129            stride: self.stride,
130            previous,
131            current,
132        };
133        let filter = match self.strategy {
134            FilterStrategy::Fixed(filter) => {
135                row.apply(filter, &mut self.filtered[1..], 0..row_bytes);
136                filter
137            }
138            FilterStrategy::Adaptive => {
139                let mut best_filter = FilterType::None;
140                let mut best_score = row
141                    .scored(FilterType::None, &mut self.filtered[1..], u64::MAX)
142                    .expect("no row scores u64::MAX");
143                for filter in FilterType::TRIED {
144                    if best_score == 0 {
145                        break;
146                    }
147                    if let Some(score) = row.scored(filter, &mut self.candidate[1..], best_score) {
148                        best_score = score;
149                        best_filter = filter;
150                        std::mem::swap(&mut self.candidate, &mut self.filtered);
151                    }
152                }
153                best_filter
154            }
155        };
156        self.filtered[0] = filter.byte();
157        self.filtered_row = Some(index);
158    }
159}
160
161impl RowSource for FilteredRows<'_> {
162    fn rows(&self) -> usize {
163        self.data.len() / self.row_bytes
164    }
165
166    fn row(&mut self, index: usize) -> &[u8] {
167        self.filter_row(index);
168        &self.filtered
169    }
170}
171
172/// The bytes filtered and scored at a time. An adaptive choice stops
173/// trying a filter on a row once the sum so far is no better than the
174/// best filter's, and the sum of this many bytes fits a `u32`, which the
175/// compiler sums several bytes at a time.
176const CHUNK: usize = 1024;
177
178/// A scanline and the one above it, to be filtered.
179#[derive(Clone, Copy, Debug)]
180struct Row<'a> {
181    /// The distance from a byte to the corresponding one of the pixel to
182    /// its left.
183    stride: usize,
184    /// The row above (zeros above the first).
185    previous: &'a [u8],
186    /// The row filtered.
187    current: &'a [u8],
188}
189
190impl Row<'_> {
191    /// Writes the bytes `range` of the row filtered with `filter` into
192    /// the same bytes of `out`.
193    fn apply(self, filter: FilterType, out: &mut [u8], range: Range<usize>) {
194        let Self {
195            stride,
196            previous,
197            current,
198        } = self;
199        // The first pixel's bytes have no left neighbours, which count
200        // as zeros.
201        for i in range.start.min(stride)..range.end.min(stride) {
202            out[i] = current[i].wrapping_sub(predict(filter, 0, previous[i], 0));
203        }
204        let tail = range.start.max(stride)..range.end.max(stride);
205        let left = tail.start - stride..tail.end - stride;
206        let (out, current, up) = (
207            &mut out[tail.clone()],
208            &current[tail.clone()],
209            &previous[tail],
210        );
211        let (left, upper_left) = (&self.current[left.clone()], &previous[left]);
212        match filter {
213            FilterType::None => out.copy_from_slice(current),
214            FilterType::Sub => {
215                for ((o, &c), &left) in out.iter_mut().zip(current).zip(left) {
216                    *o = c.wrapping_sub(left);
217                }
218            }
219            FilterType::Up => {
220                for ((o, &c), &up) in out.iter_mut().zip(current).zip(up) {
221                    *o = c.wrapping_sub(up);
222                }
223            }
224            FilterType::Average => {
225                for ((o, &c), (&left, &up)) in out.iter_mut().zip(current).zip(left.iter().zip(up))
226                {
227                    *o = c.wrapping_sub(average(left, up));
228                }
229            }
230            FilterType::Paeth => {
231                let neighbours = left.iter().zip(up).zip(upper_left);
232                for ((o, &c), ((&left, &up), &upper_left)) in
233                    out.iter_mut().zip(current).zip(neighbours)
234                {
235                    *o = c.wrapping_sub(paeth(left, up, upper_left));
236                }
237            }
238        }
239    }
240
241    /// Writes the row filtered with `filter` into `out` and returns its
242    /// score (the sum of the filtered bytes' magnitudes, read as signed
243    /// values), unless the score reaches `bound`: then `out` holds part of
244    /// the filtered row only.
245    fn scored(self, filter: FilterType, out: &mut [u8], bound: u64) -> Option<u64> {
246        let mut score = 0;
247        let len = self.current.len();
248        for start in (0..len).step_by(CHUNK) {
249            let range = start..(start + CHUNK).min(len);
250            self.apply(filter, out, range.clone());
251            score += u64::from(chunk_score(&out[range]));
252            if score >= bound {
253                return None;
254            }
255        }
256        Some(score)
257    }
258}
259
260/// The sum of the magnitudes of at most [`CHUNK`] filtered bytes, read as
261/// signed values.
262fn chunk_score(filtered: &[u8]) -> u32 {
263    filtered
264        .iter()
265        .map(|&byte| u32::from((byte as i8).unsigned_abs()))
266        .sum()
267}
268
269/// What `filter` predicts a byte from: the corresponding bytes of the
270/// pixels to its left, above it and above-left.
271fn predict(filter: FilterType, left: u8, up: u8, upper_left: u8) -> u8 {
272    match filter {
273        FilterType::None => 0,
274        FilterType::Sub => left,
275        FilterType::Up => up,
276        FilterType::Average => average(left, up),
277        FilterType::Paeth => paeth(left, up, upper_left),
278    }
279}
280
281/// Reverses `filter` on `row` in place, given the already reconstructed
282/// `previous` row (all zeros for the first row).
283pub(crate) fn unfilter(filter: FilterType, stride: usize, previous: &[u8], row: &mut [u8]) {
284    let len = row.len();
285    match filter {
286        FilterType::None => {}
287        FilterType::Sub => {
288            for i in stride..len {
289                row[i] = row[i].wrapping_add(row[i - stride]);
290            }
291        }
292        FilterType::Up => {
293            for (byte, &up) in row.iter_mut().zip(previous) {
294                *byte = byte.wrapping_add(up);
295            }
296        }
297        FilterType::Average => {
298            for (byte, &up) in row[..stride].iter_mut().zip(previous) {
299                *byte = byte.wrapping_add(up / 2);
300            }
301            for i in stride..len {
302                row[i] = row[i].wrapping_add(average(row[i - stride], previous[i]));
303            }
304        }
305        FilterType::Paeth => {
306            for (byte, &up) in row[..stride].iter_mut().zip(previous) {
307                *byte = byte.wrapping_add(up);
308            }
309            for i in stride..len {
310                let predicted = paeth(row[i - stride], previous[i], previous[i - stride]);
311                row[i] = row[i].wrapping_add(predicted);
312            }
313        }
314    }
315}
316
317/// The Average filter's prediction: the mean of `left` and `up`, rounded
318/// down.
319fn average(left: u8, up: u8) -> u8 {
320    left.midpoint(up)
321}
322
323/// The Paeth predictor: whichever neighbour is closest to
324/// `left + up - upper_left`, preferring left, then up.
325fn paeth(left: u8, up: u8, upper_left: u8) -> u8 {
326    let (a, b, c) = (i16::from(left), i16::from(up), i16::from(upper_left));
327    let distance_left = (b - c).abs();
328    let distance_up = (a - c).abs();
329    let distance_upper_left = (a + b - 2 * c).abs();
330    if distance_left <= distance_up && distance_left <= distance_upper_left {
331        left
332    } else if distance_up <= distance_upper_left {
333        up
334    } else {
335        upper_left
336    }
337}
338
339#[cfg(test)]
340mod tests {
341    use super::*;
342    use crate::test_util::Rng;
343
344    /// Every filter, in the order of their type bytes.
345    const ALL: [FilterType; 5] = [
346        FilterType::None,
347        FilterType::Sub,
348        FilterType::Up,
349        FilterType::Average,
350        FilterType::Paeth,
351    ];
352
353    /// All the filtered rows of `data`.
354    fn filter_image(
355        data: &[u8],
356        row_bytes: usize,
357        stride: usize,
358        strategy: FilterStrategy,
359    ) -> Result<Vec<u8>, OutOfMemory> {
360        let mut rows = FilteredRows::new(data, row_bytes, stride, strategy)?;
361        Ok((0..rows.rows())
362            .flat_map(|index| rows.row(index).to_vec())
363            .collect())
364    }
365
366    #[test]
367    fn paeth_prefers_left_then_up() {
368        assert_eq!(paeth(10, 20, 15), 15);
369        assert_eq!(paeth(10, 20, 10), 20);
370        assert_eq!(paeth(10, 20, 30), 10);
371        assert_eq!(paeth(100, 0, 90), 0);
372        assert_eq!(paeth(50, 60, 55), 55);
373        assert_eq!(paeth(0, 0, 255), 0);
374        assert_eq!(paeth(9, 2, 7), 2);
375        assert_eq!(paeth(200, 100, 160), 160);
376    }
377
378    #[test]
379    fn every_filter_round_trips() {
380        let mut rng = Rng::new(21);
381        for stride in [1, 2, 3, 4, 6, 8] {
382            let row_bytes = stride * (1 + rng.below(20));
383            let image = rng.bytes(row_bytes * 5);
384            for filter in ALL {
385                let filtered =
386                    filter_image(&image, row_bytes, stride, FilterStrategy::Fixed(filter)).unwrap();
387                assert_eq!(filtered.len(), image.len() + 5);
388                let mut restored = vec![0; row_bytes];
389                let mut previous = vec![0; row_bytes];
390                for (index, line) in filtered.chunks_exact(row_bytes + 1).enumerate() {
391                    assert_eq!(FilterType::from_byte(line[0]), Some(filter));
392                    restored.copy_from_slice(&line[1..]);
393                    unfilter(filter, stride, &previous, &mut restored);
394                    let original = &image[index * row_bytes..(index + 1) * row_bytes];
395                    assert_eq!(
396                        restored, original,
397                        "{filter:?}, stride {stride}, row {index}"
398                    );
399                    previous.copy_from_slice(&restored);
400                }
401            }
402        }
403    }
404
405    #[test]
406    fn adaptive_choice_follows_content() {
407        // A horizontal gradient favours Sub; identical rows favour Up.
408        let gradient: Vec<u8> = (0..64).collect();
409        let filtered = filter_image(&gradient, 64, 1, FilterStrategy::Adaptive).unwrap();
410        assert_eq!(filtered[0], FilterType::Sub.byte());
411        let noise = Rng::new(22).bytes(64);
412        let filtered = filter_image(&noise.repeat(2), 64, 1, FilterStrategy::Adaptive).unwrap();
413        assert_eq!(filtered[65], FilterType::Up.byte());
414        assert!(filtered[66..].iter().all(|&b| b == 0));
415    }
416
417    #[test]
418    fn adaptive_choice_is_pillows_first_filter_of_smallest_score() {
419        // Rows of several chunks (filters are dropped part-way), of noise,
420        // a gradient, a repeated row and a constant one (scores tie).
421        let mut rng = Rng::new(24);
422        for stride in [1, 3, 4, 8] {
423            let row_bytes = stride * (2 * CHUNK / stride + 1 + rng.below(50));
424            let mut image = rng.bytes(row_bytes * 6);
425            for (i, byte) in image[row_bytes..2 * row_bytes].iter_mut().enumerate() {
426                *byte = (i / 7) as u8;
427            }
428            image.copy_within(row_bytes..2 * row_bytes, 2 * row_bytes);
429            image[4 * row_bytes..5 * row_bytes].fill(255);
430            let adaptive =
431                filter_image(&image, row_bytes, stride, FilterStrategy::Adaptive).unwrap();
432            let tried = [
433                FilterType::None,
434                FilterType::Up,
435                FilterType::Sub,
436                FilterType::Paeth,
437            ];
438            let fixed: Vec<Vec<u8>> = tried
439                .iter()
440                .map(|&f| {
441                    filter_image(&image, row_bytes, stride, FilterStrategy::Fixed(f)).unwrap()
442                })
443                .collect();
444            for line in (0..adaptive.len()).step_by(row_bytes + 1) {
445                let bytes = line..line + row_bytes + 1;
446                let score = |filtered: &Vec<u8>| -> u64 {
447                    filtered[line + 1..bytes.end]
448                        .iter()
449                        .map(|&b| u64::from((b as i8).unsigned_abs()))
450                        .sum()
451                };
452                let (first_smallest, _) = fixed
453                    .iter()
454                    .enumerate()
455                    .min_by_key(|&(index, filtered)| (score(filtered), index))
456                    .expect("four filters");
457                assert_eq!(
458                    adaptive[bytes.clone()],
459                    fixed[first_smallest][bytes],
460                    "stride {stride}, line at {line}"
461                );
462            }
463        }
464    }
465
466    #[test]
467    fn rows_are_made_again_anywhere() {
468        let image = Rng::new(23).bytes(40 * 6);
469        let all = filter_image(&image, 40, 4, FilterStrategy::Adaptive).unwrap();
470        let mut rows = FilteredRows::new(&image, 40, 4, FilterStrategy::Adaptive).unwrap();
471        for index in [5, 1, 1, 0, 3] {
472            assert_eq!(
473                rows.row(index),
474                &all[index * 41..(index + 1) * 41],
475                "row {index}"
476            );
477        }
478    }
479
480    #[test]
481    fn adaptive_choice_breaks_ties_as_pillow_does() {
482        // Up, Sub and Paeth score 6 on the second row, no filter 7 and
483        // Average 5: Pillow tries Up first, keeps it, and never tries
484        // Average.
485        let image = [2, 0, 3, 0, 3, 1, 1, 2];
486        let filtered = filter_image(&image, 4, 1, FilterStrategy::Adaptive).unwrap();
487        assert_eq!(filtered[0], FilterType::None.byte());
488        assert_eq!(filtered[5..], [FilterType::Up.byte(), 1, 1, 254, 2]);
489    }
490
491    #[test]
492    fn filter_bytes_round_trip() {
493        for filter in ALL {
494            assert_eq!(FilterType::from_byte(filter.byte()), Some(filter));
495        }
496        assert_eq!(FilterType::from_byte(5), None);
497    }
498}