1 use crate::common::BytesPerPixel;
2 use std;
3 
4 /// The byte level filter applied to scanlines to prepare them for compression.
5 ///
6 /// Compression in general benefits from repetitive data. The filter is a content-aware method of
7 /// compressing the range of occurring byte values to help the compression algorithm. Note that
8 /// this does not operate on pixels but on raw bytes of a scanline.
9 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
10 #[repr(u8)]
11 pub enum FilterType {
12     NoFilter = 0,
13     Sub = 1,
14     Up = 2,
15     Avg = 3,
16     Paeth = 4,
17 }
18 
19 impl FilterType {
20     /// u8 -> Self. Temporary solution until Rust provides a canonical one.
from_u8(n: u8) -> Option<FilterType>21     pub fn from_u8(n: u8) -> Option<FilterType> {
22         match n {
23             0 => Some(FilterType::NoFilter),
24             1 => Some(FilterType::Sub),
25             2 => Some(FilterType::Up),
26             3 => Some(FilterType::Avg),
27             4 => Some(FilterType::Paeth),
28             _ => None,
29         }
30     }
31 }
32 
filter_paeth(a: u8, b: u8, c: u8) -> u833 fn filter_paeth(a: u8, b: u8, c: u8) -> u8 {
34     let ia = i16::from(a);
35     let ib = i16::from(b);
36     let ic = i16::from(c);
37 
38     let p = ia + ib - ic;
39 
40     let pa = (p - ia).abs();
41     let pb = (p - ib).abs();
42     let pc = (p - ic).abs();
43 
44     if pa <= pb && pa <= pc {
45         a
46     } else if pb <= pc {
47         b
48     } else {
49         c
50     }
51 }
52 
unfilter( filter: FilterType, tbpp: BytesPerPixel, previous: &[u8], current: &mut [u8], ) -> std::result::Result<(), &'static str>53 pub(crate) fn unfilter(
54     filter: FilterType,
55     tbpp: BytesPerPixel,
56     previous: &[u8],
57     current: &mut [u8],
58 ) -> std::result::Result<(), &'static str> {
59     use self::FilterType::*;
60     let bpp = tbpp.into_usize();
61     let len = current.len();
62 
63     fn require_length(slice: &[u8], length: usize) -> Result<&[u8], &'static str> {
64         match slice.get(..length) {
65             None => Err("Filtering failed: not enough data in previous row"),
66             Some(slice) => Ok(slice),
67         }
68     }
69 
70     match filter {
71         NoFilter => Ok(()),
72         Sub => {
73             let current = &mut current[..len];
74             for i in bpp..len {
75                 current[i] = current[i].wrapping_add(current[i - bpp]);
76             }
77             Ok(())
78         }
79         Up => {
80             let current = &mut current[..len];
81             let previous = require_length(previous, len)?;
82             for i in 0..len {
83                 current[i] = current[i].wrapping_add(previous[i]);
84             }
85             Ok(())
86         }
87         Avg => {
88             let current = &mut current[..len];
89             let previous = require_length(previous, len)?;
90             if bpp > len {
91                 return Err("Filtering failed: bytes per pixel is greater than length of row");
92             }
93 
94             for i in 0..bpp {
95                 current[i] = current[i].wrapping_add(previous[i] / 2);
96             }
97 
98             macro_rules! avg_tail {
99                 ($name:ident, $bpp:expr) => {
100                     fn $name(current: &mut [u8], previous: &[u8]) {
101                         let len = current.len();
102                         let current = &mut current[..len];
103                         let previous = &previous[..len];
104 
105                         let mut current = current.chunks_exact_mut($bpp);
106                         let mut previous = previous.chunks_exact($bpp);
107 
108                         let mut lprevious = current.next().unwrap();
109                         let _ = previous.next();
110 
111                         while let Some(pprevious) = previous.next() {
112                             let pcurrent = current.next().unwrap();
113 
114                             for i in 0..$bpp {
115                                 let lprev = lprevious[i];
116                                 let pprev = pprevious[i];
117                                 pcurrent[i] = pcurrent[i].wrapping_add(
118                                     ((u16::from(lprev) + u16::from(pprev)) / 2) as u8,
119                                 );
120                             }
121 
122                             lprevious = pcurrent;
123                         }
124                     }
125                 };
126             }
127 
128             avg_tail!(avg_tail_8, 8);
129             avg_tail!(avg_tail_6, 6);
130             avg_tail!(avg_tail_4, 4);
131             avg_tail!(avg_tail_3, 3);
132             avg_tail!(avg_tail_2, 2);
133             avg_tail!(avg_tail_1, 1);
134 
135             match tbpp {
136                 BytesPerPixel::Eight => avg_tail_8(current, previous),
137                 BytesPerPixel::Six => avg_tail_6(current, previous),
138                 BytesPerPixel::Four => avg_tail_4(current, previous),
139                 BytesPerPixel::Three => avg_tail_3(current, previous),
140                 BytesPerPixel::Two => avg_tail_2(current, previous),
141                 BytesPerPixel::One => avg_tail_1(current, previous),
142             }
143 
144             Ok(())
145         }
146         Paeth => {
147             let current = &mut current[..len];
148             let previous = require_length(previous, len)?;
149             if bpp > len {
150                 return Err("Filtering failed: bytes per pixel is greater than length of row");
151             }
152 
153             for i in 0..bpp {
154                 current[i] = current[i].wrapping_add(filter_paeth(0, previous[i], 0));
155             }
156 
157             let mut current = current.chunks_exact_mut(bpp);
158             let mut previous = previous.chunks_exact(bpp);
159 
160             let mut lprevious = current.next().unwrap();
161             let mut lpprevious = previous.next().unwrap();
162 
163             while let Some(pprevious) = previous.next() {
164                 let pcurrent = current.next().unwrap();
165 
166                 for i in 0..bpp {
167                     pcurrent[i] = pcurrent[i].wrapping_add(filter_paeth(
168                         lprevious[i],
169                         pprevious[i],
170                         lpprevious[i],
171                     ));
172                 }
173 
174                 lprevious = pcurrent;
175                 lpprevious = pprevious;
176             }
177 
178             Ok(())
179         }
180     }
181 }
182 
filter(method: FilterType, bpp: BytesPerPixel, previous: &[u8], current: &mut [u8])183 pub(crate) fn filter(method: FilterType, bpp: BytesPerPixel, previous: &[u8], current: &mut [u8]) {
184     use self::FilterType::*;
185     let bpp = bpp.into_usize();
186     let len = current.len();
187 
188     match method {
189         NoFilter => (),
190         Sub => {
191             for i in (bpp..len).rev() {
192                 current[i] = current[i].wrapping_sub(current[i - bpp]);
193             }
194         }
195         Up => {
196             for i in 0..len {
197                 current[i] = current[i].wrapping_sub(previous[i]);
198             }
199         }
200         Avg => {
201             for i in (bpp..len).rev() {
202                 current[i] = current[i].wrapping_sub(
203                     ((u16::from(current[i - bpp]) + u16::from(previous[i])) / 2) as u8,
204                 );
205             }
206 
207             for i in 0..bpp {
208                 current[i] = current[i].wrapping_sub(previous[i] / 2);
209             }
210         }
211         Paeth => {
212             for i in (bpp..len).rev() {
213                 current[i] = current[i].wrapping_sub(filter_paeth(
214                     current[i - bpp],
215                     previous[i],
216                     previous[i - bpp],
217                 ));
218             }
219 
220             for i in 0..bpp {
221                 current[i] = current[i].wrapping_sub(filter_paeth(0, previous[i], 0));
222             }
223         }
224     }
225 }
226 
227 #[cfg(test)]
228 mod test {
229     use super::{filter, unfilter, BytesPerPixel, FilterType};
230     use core::iter;
231 
232     #[test]
roundtrip()233     fn roundtrip() {
234         // A multiple of 8, 6, 4, 3, 2, 1
235         const LEN: u8 = 240;
236         let previous: Vec<_> = iter::repeat(1).take(LEN.into()).collect();
237         let mut current: Vec<_> = (0..LEN).collect();
238         let expected = current.clone();
239 
240         let mut roundtrip = |kind, bpp: BytesPerPixel| {
241             filter(kind, bpp, &previous, &mut current);
242             unfilter(kind, bpp, &previous, &mut current).expect("Unfilter worked");
243             assert_eq!(
244                 current, expected,
245                 "Filtering {:?} with {:?} does not roundtrip",
246                 bpp, kind
247             );
248         };
249 
250         let filters = [
251             FilterType::NoFilter,
252             FilterType::Sub,
253             FilterType::Up,
254             FilterType::Avg,
255             FilterType::Paeth,
256         ];
257 
258         let bpps = [
259             BytesPerPixel::One,
260             BytesPerPixel::Two,
261             BytesPerPixel::Three,
262             BytesPerPixel::Four,
263             BytesPerPixel::Six,
264             BytesPerPixel::Eight,
265         ];
266 
267         for &filter in filters.iter() {
268             for &bpp in bpps.iter() {
269                 roundtrip(filter, bpp);
270             }
271         }
272     }
273 }
274