1use std::ops::Range;
6
7use pltrs_core::alloc::{self, OutOfMemory};
8
9use crate::deflate::encode::RowSource;
10
11#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
13pub enum FilterType {
14 None,
16 Sub,
18 Up,
20 Average,
22 Paeth,
24}
25
26impl FilterType {
27 const TRIED: [Self; 3] = [Self::Up, Self::Sub, Self::Paeth];
30
31 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 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#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
57pub enum FilterStrategy {
58 #[default]
62 Adaptive,
63 Fixed(FilterType),
65}
66
67#[derive(Debug)]
72pub(crate) struct FilteredRows<'a> {
73 data: &'a [u8],
74 row_bytes: usize,
75 stride: usize,
76 strategy: FilterStrategy,
77 filtered_row: Option<usize>,
79 filtered: Vec<u8>,
81 candidate: Vec<u8>,
83 zero_row: Vec<u8>,
85}
86
87impl<'a> FilteredRows<'a> {
88 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 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
172const CHUNK: usize = 1024;
177
178#[derive(Clone, Copy, Debug)]
180struct Row<'a> {
181 stride: usize,
184 previous: &'a [u8],
186 current: &'a [u8],
188}
189
190impl Row<'_> {
191 fn apply(self, filter: FilterType, out: &mut [u8], range: Range<usize>) {
194 let Self {
195 stride,
196 previous,
197 current,
198 } = self;
199 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 ¤t[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 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
260fn chunk_score(filtered: &[u8]) -> u32 {
263 filtered
264 .iter()
265 .map(|&byte| u32::from((byte as i8).unsigned_abs()))
266 .sum()
267}
268
269fn 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
281pub(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
317fn average(left: u8, up: u8) -> u8 {
320 left.midpoint(up)
321}
322
323fn 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 const ALL: [FilterType; 5] = [
346 FilterType::None,
347 FilterType::Sub,
348 FilterType::Up,
349 FilterType::Average,
350 FilterType::Paeth,
351 ];
352
353 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 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 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 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}