Repository: shssoichiro/oxipng (language: rust)

Issue:
Program seems to find new compressions to make after multiple runs (?)
See my commits here https://github.com/EnderNon/Wynntils-jpegnoise-fix

So basically what happened was:

- Ran these for initial commit: 
  - `oxipng -o max --strip all --alpha **/*.png` in `common/src/main/resources/assets/wynntils/textures`, 
  - then ran `oxipng -o max --strip all --alpha logo.png` in `common/src/main/resources/assets/wynntils`
  - creating the commit [refactor: compress every image lossless](https://github.com/EnderNon/Wynntils-jpegnoise-fix/commit/912deb350bf33fd2a8f6baf38ffba125f31d4b8a)
- Realised logo.png became slightly dimmer, 
  - so I regenerated file from before I touched it, with `oxipng -o max --strip safe --alpha **/*.png`
  - creating the commit [fix: use '--strip safe' on logo.png instead. Full command: 'oxipng -o max --strip safe --alpha logo.png'](https://github.com/EnderNon/Wynntils-jpegnoise-fix/commit/f1575e60c2961e7b115dc82f8bbfcf8d525e5328)
 - Then a contributor to upstream Wynntils asked to see what happens if you were to run the first command from the first commit again. 
   - It modified some files here, creating this commit [run oxipng again](https://github.com/EnderNon/Wynntils-jpegnoise-fix/commit/709da7cf2aba4b085fd00c5ffea8a6e4ed031143)
 - Running it again afterwards showed in the output that there was no new differences. 
So for some reason, running the command once wasn't enough to achieve max savings - running it twice was necessary. Seems like a bug.


Discussion / hints:
Hi @EnderNon, thanks for the report.

Analysis of map_icon.png: The palette sorting evaluations are all tied for best result. When this happens it chooses the one that was performed first.
In the first run, the luma sort is performed first and this is what is selected for the output. In the second run, the luma sort is skipped because it is the same as the input, so the battiato sort is selected instead. The input "baseline" is always evaluated *last*, so it is never preferred in the case of a tie and is why a second run may give a different result. A third run would end up the same as the first and can therefore never produce further improvement.

I'll have to consider if there's anything we can improve here but my initial thought is to just keep it as-is. If we were to change it to, e.g., prefer the input baseline in the case of a tie, then you would be stuck with the first result and never achieve the smaller size of the second run.
A somewhat naive initial idea I'm thinking is that choosing one of the tied sorts at random, or from some tuned probability distribution, could be an improvement overall if the expected final size is less than just always sticking with the first, but doing that comes with its own set of gotchas related to reproducibility... Perhaps there is something better than that though.
Maybe, [if running multi-threaded anyway, run _all_ of these tied (& close-to-tied) palette sorts in parallel](https://github.com/shssoichiro/oxipng/issues/561)?  Kinda like CPUs do predictive branching?
> A somewhat naive initial idea I'm thinking is that choosing one of the tied sorts at random, or from some tuned probability distribution, could be an improvement overall if the expected final size is less than just always sticking with the first, but doing that comes with its own set of gotchas related to reproducibility... Perhaps there is something better than that though.

Yeah, determinism is important. Perhaps we could just adjust the order so that, e.g. mzeng is preferred if we know it's usually the best one.

> Maybe, if running multi-threaded anyway, run _all_ of these tied (& close-to-tied) palette sorts in parallel? Kinda like CPUs do predictive branching?

Indeed, I still plan to get around to #523 someday...

Fix patch:
diff --git a/src/evaluate.rs b/src/evaluate.rs
index b3801fac..dd60aee6 100644
--- a/src/evaluate.rs
+++ b/src/evaluate.rs
@@ -23,7 +23,7 @@ pub(crate) struct Candidate {
     pub idat_data: Vec<u8>,
     pub filtered: Vec<u8>,
     pub filter: RowFilter,
-    // first wins tie-breaker
+    // For determining tie-breaker
     nth: usize,
 }
 
@@ -32,9 +32,9 @@ impl Candidate {
         (
             self.idat_data.len() + self.image.key_chunks_size(),
             self.image.data.len(),
-            self.image.ihdr.bit_depth,
             self.filter,
-            self.nth,
+            // Prefer the later image added (e.g. baseline, which is always added last)
+            usize::MAX - self.nth,
         )
     }
 }


Test patch: