Assume None if the line is all zeros (#650)

andrews05 · web-flow · commit ca05d99be4e0 · 2024-11-28T17:21:10.000+01:00
#648 may have been a bit hasty - I realised afterward that there's a simpler way to achieve the same thing, and include the Brute filter as well. This reverts #648 and instead just picks None up front if the line is all zeros. This is guaranteed to be the chosen filter for MinSum, Entropy, Bigrams and BigEnt. It's almost certainly true for Brute as well but this is harder to prove. I've tested this across hundreds of images and found no change in output.
diff --git a/src/png/mod.rs b/src/png/mod.rs
@@ -341,17 +341,9 @@ impl PngImage {
         let mut prev_line = Vec::new();
         let mut prev_pass: Option<u8> = None;
         let mut f_buf = Vec::new();
-        let mut best_possible = 0;
         for line in self.scan_lines(false) {
             if prev_pass != line.pass || line.data.len() != prev_line.len() {
                 prev_line = vec![0; line.data.len()];
-                // Calculate the best possible result for this pass
-                best_possible = match filter {
-                    RowFilter::Entropy => ilog2i(line.data.len() as u32 + 1) as i32,
-                    RowFilter::Bigrams => 1,
-                    RowFilter::BigEnt => ilog2i(line.data.len() as u32) as i32,
-                    _ => 0,
-                }
             }
             // Alpha optimisation may alter the line data, so we need a mutable copy of it
             let mut line_data = line.data.to_vec();
@@ -368,6 +360,15 @@ impl PngImage {
                 prev_line = line_data;
             } else {
                 // Heuristic filter selection strategies
+
+                if line_data.iter().all(|&x| x == 0) {
+                    // Assume None if the line is all zeros
+                    filtered.push(RowFilter::None as u8);
+                    filtered.extend_from_slice(&line_data);
+                    prev_line = line_data;
+                    continue;
+                }
+
                 let mut best_line = Vec::new();
                 let mut best_line_raw = Vec::new();
                 // Avoid vertical filtering on first line of each interlacing pass
@@ -380,21 +381,17 @@ impl PngImage {
                     RowFilter::MinSum => {
                         // MSAD algorithm mentioned in libpng reference docs
                         // http://www.libpng.org/pub/png/book/chapter09.html
-                        let mut best_size = i32::MAX;
+                        let mut best_size = usize::MAX;
                         for f in try_filters {
                             f.filter_line(bpp, &mut line_data, &prev_line, &mut f_buf, alpha_bytes);
                             let size = f_buf.iter().fold(0, |acc, &x| {
                                 let signed = x as i8;
-                                acc + signed.unsigned_abs() as i32
+                                acc + signed.unsigned_abs() as usize
                             });
                             if size < best_size {
                                 best_size = size;
                                 std::mem::swap(&mut best_line, &mut f_buf);
                                 best_line_raw.clone_from(&line_data);
-                                if size == best_possible {
-                                    // Best possible result
-                                    break;
-                                }
                             }
                         }
                     }
@@ -418,33 +415,25 @@ impl PngImage {
                                 best_size = size;
                                 std::mem::swap(&mut best_line, &mut f_buf);
                                 best_line_raw.clone_from(&line_data);
-                                if size == best_possible {
-                                    // Best possible result
-                                    break;
-                                }
                             }
                         }
                     }
                     RowFilter::Bigrams => {
                         // Count distinct bigrams, from pngwolf
                         // https://bjoern.hoehrmann.de/pngwolf/
-                        let mut best_size = i32::MAX;
+                        let mut best_size = usize::MAX;
                         for f in try_filters {
                             f.filter_line(bpp, &mut line_data, &prev_line, &mut f_buf, alpha_bytes);
                             let mut set = bitarr![0; 0x10000];
                             for pair in f_buf.windows(2) {
                                 let bigram = (pair[0] as usize) << 8 | pair[1] as usize;
                                 set.set(bigram, true);
                             }
-                            let size = set.count_ones() as i32;
+                            let size = set.count_ones();
                             if size < best_size {
                                 best_size = size;
                                 std::mem::swap(&mut best_line, &mut f_buf);
                                 best_line_raw.clone_from(&line_data);
-                                if size == best_possible {
-                                    // Best possible result
-                                    break;
-                                }
                             }
                         }
                     }
@@ -465,10 +454,6 @@ impl PngImage {
                                 best_size = size;
                                 std::mem::swap(&mut best_line, &mut f_buf);
                                 best_line_raw.clone_from(&line_data);
-                                if size == best_possible {
-                                    // Best possible result
-                                    break;
-                                }
                             }
                         }
                     }
