This PR allows the Brute filter parameters to be configured rather than
using fixed constants. It also tweaks the presets to take advantage of
these new options:
o3: level=1, lines=3 (fractionally worse/faster)
o4: level=1, lines=4 (same as before)
o5: level=4, lines=4 (fractionally better/slower)
o6: level=5, lines=8 (slightly better/slower)
The parameters can be explicitly set in both the API and the CLI.
This is a collection of all the BC breaks mentioned in #714, except for
11 which I'm not including for now.
Fixes#658.
Fixes#660.
It might be best to review each commit individually, referencing the
notes in #714 and #660 (I just didn't want to create a dozen separate
PRs).
This is an experiment I started a while ago before life happened. It
reduces memory usage of fast evaluation (-o2 and lower), bringing it
inline with normal (slow) evaluation. It does this by not retaining the
filtered image data of the evaluations, but instead retaining the row
filters that were used in each line so it can be quickly re-filtered
when required. This does incur a tiny performance penalty, but it's
negligible even at `-o0`.
Although this is fully functional, there are a few rough spots in the
code so I'm just opening it as a draft for now.
```
PR -sao6
70.08 real 614.36 user 2.66 sys
2024243200 maximum resident set size
1839339520 peak memory footprint
PR -sao2
11.16 real 60.85 user 1.33 sys
1982562304 maximum resident set size
1842173824 peak memory footprint
PR -sao2 -t1
55.11 real 53.85 user 0.76 sys
429457408 maximum resident set size
245008064 peak memory footprint
master -sao6
67.70 real 616.07 user 2.72 sys
2043379712 maximum resident set size
1838340416 peak memory footprint
master -sao2
11.53 real 60.63 user 1.25 sys
2753396736 maximum resident set size
2283741440 peak memory footprint
master -sao2 -t1
54.29 real 53.55 user 0.72 sys
626311168 maximum resident set size
305252544 peak memory footprint
```
Note that this involves some refactoring of `RowFilter` and the new
`FilterStrategy`. These are breaking changes so it will ultimately be
destined for v10. One advantage to this new structure is it opens the
door for future changes such as allowing the Brute strategy to take a
parameter for the number of lines.
#719 is failing tests due to requiring a newer version of rust than we
currently specify. This PR updates to 1.85.1 and sets the edition to
2024.
I've also updated dependencies and runner images, using the ubuntu arm
runner which removes the need for qemu and other hacks.
Closes#719.
Two key changes here:
- Removed some defunct reduction benches and added some more alpha
reduction benches.
- Changed use of `chunks()` to `chunks_exact()` where appropriate to
improve performance. (As a byproduct, this also fixes a potential crash
if a malformed file has a PLTE chunk that isn't a multiple of 3.)
If no palette reduction occurred (or palette reductions were off), a
fully transparent palette entry may not have been zeroed to black. By
ensuring this gets cleaned in the `indexed_to_channels` transformation,
we may able to achieve a grayscale conversion that would otherwise have
been RGB.
This is the final piece of the puzzle in #649 to achieve better file
sizes on the first run and avoid further changes on a second run.
Results from the images in #649 (combining this PR and #673):
9.1.3 1st run: 2,191,773
9.1.3 2nd run: 2,191,629
PR 1st run: 2,191,380
PR 2nd run: 2,191,380
This PR adds the modified zeng ("mzeng") palette sorting method, in
addition to the existing luma and battiato methods. Speed is very
similar to the battiato method with slightly better results on average.
Resulting sizes from two different image sets (all indexed or able to be
indexed):
| | master | PR |
|-|-|-|
| Set 1 | 29,647,156 | 29,555,697 |
| Set 2 | 23,732,133 | 23,570,862 |
Additionally, I've added a new "first colour" heuristic for both the
mzeng and battiato methods: We use the most popular colour overall, but
only if it covers at least 15% of the image. This provided 13k savings
on Set 2 vs the edge colour heuristic (which is still used in the luma
sort).
This adds a new palette sorting algorithm that attempts to minimise
entropy by an approximate solution to the Traveling Salesman Problem.
The algorithm comes from "An efficient Re-indexing algorithm for
color-mapped images" by Battiato et al
(https://ieeexplore.ieee.org/document/1344033).
It's fast and effective and works in addition to the luma sort (which
remains the single most effective sort). In order to keep lower presets
fast though, I've only enabled this for o3 and higher.
Results on a set of 190 indexed images at `-o5`:
18,932,727 bytes - master
18,578,306 bytes - PR
18,559,863 bytes - PR + #509
(These images may be particularly suited to alternative sorting methods
- the gains here are not necessarily what should be expected on average)
Note I looked into the 120 different palette sorting methods from
TruePNG, as mentioned in #74 (and seen in action in the Zopfli KrzYmod
fork). They're... largely ineffective. The combination of all 120
methods are outperformed by just the existing luma sort plus this new
one. That's not to say there's nothing further to be gained from them,
but trying to brute force all the combinations definitely seems like a
bad idea. There are other algorithms I hope to explore in future...
@ace-dent Thought this might interest you
UPDATE: I realised a quick tweak to alpha values in the luma sort can
provide a great improvement on images with transparency. The following
numbers were taken with PR #509 as base.
`-o2`:
19,065,549 bytes - base (luma sort)
18,949,747 bytes - modified luma sort
`-o5`:
18,922,165 bytes - base (luma sort)
18,559,863 bytes - new sorting algorithm + luma sort
18,544,813 bytes - new sorting algorithm + modified luma sort
* Add .whitesource configuration file
* Experimental: allow Zopfli to use any size BufWriter
* Allow user to specify the output buffer size as well
* Allow user to specify maximum block splits
* Reformat and fix warnings
* Use deflater on iCCP chunk as well
* Bug fix: need to implement Zlib format
* Make functions const when possible
* Switch to using zopfli::Options in prep for https://github.com/zopfli-rs/zopfli/pull/21
* Switch to using zopfli::Options in prep for https://github.com/zopfli-rs/zopfli/pull/21
* Cargo fmt
* Fix compilation
* Fix tests
* Fix more lints
* Fix more lints
* Fix compilation more
---------
Co-authored-by: mend-bolt-for-github[bot] <42819689+mend-bolt-for-github[bot]@users.noreply.github.com>
Co-authored-by: Chris Hennick <hennickc@amazon.com>
Co-authored-by: Chris Hennick <4961925+Pr0methean@users.noreply.github.com>
* Keep track of number of pixels in each scanline
* Expand depth to 8-bit
* Attempt expand bit depth
* Simplify tracking of reduction_occurred
* Fix test
* Simplify depth handling in reductions
* Add tests for disabled reductions
* Fix bKGD conversion from gray to palette
* Allow grayscale reduction from 16 to 4 or less
* Refactor reduction evaluation sequence
* Separate palette into new file
* Refactor filters as enum
* Include filter byte in filter output
* Add entropy filter
* Add bigrams filter
* Add bigram entropy filter
* Add brute filter
* Replace bit-vec
* Add tests and benches
* Show filters in help
* Use FxHasher in color to palette
* Use windows function for minor improvement
* Switch main compressor to libdeflate
* Use libdeflater in evaluate
* Use libdeflater to inflate
* Use libdeflater crc
* Tidy up
* Fix benches
* Allow libdeflater/freestanding feature
* Fix building without zopfli
* Update and optimize dependencies
These changes update the dependencies to their latest versions, fixing
some known issues that prevented doing so in the first place.
In addition, the direct dependency on byteorder was dropped in favor
of stdlib functions that have been stabilized for some time in Rust, and
the transitive dependency on chrono, pulled by stderrlog, was also
dropped, which had been affected by security issues and improperly
maintained in the past:
- https://github.com/cardoe/stderrlog-rs/issues/31
- https://www.reddit.com/r/rust/comments/ts84n4/chrono_or_time_03/
* Run rustfmt
* Bump MSRV to 1.56.1
Updating to this patch version should not be cumbersome for end-users,
and it is required by a transitive dependency.
* Bump MSRV to 1.57.0
os_str_bytes requires it.
* Add initial support for changing Zopfli iterations
PR https://github.com/shssoichiro/oxipng/pull/445 did some dependency
updates, which included using the latest zopfli version. The latest
version of this crate exposes new options in its API that allow users to
choose the desired number of Zopfli compression iterations, which
may greatly affect execution time. In fact, other optimizers such as
zopflipng dynamically select this number depending on the input file
size (see: https://github.com/shssoichiro/oxipng/issues/414).
As a first step towards making OxiPNG deal with Zopfli better, let's add
the necessary options for libraries to be able to choose the number of
iterations. This number is still fixed to 15 as before when using the
CLI.
* Fix Clippy lint
Co-authored-by: Josh Holmer <jholmer.in@gmail.com>
For RGB(A) images that contain gray colors, this reduction can achieve
significant space savings. However, in the absence of gamma correction
data, some PNG decoders assume more exotic color spaces for grayscale
images instead of the ubiquitous sRGB. This results in gamma
miscorrection, and for the end user this means that colors will look
wrong, like "washed-out". Java's ImageIO class, which is popular in the
JVM world to read PNG files, uses rather unconventional defaults, as
explained in this StackOverflow question: https://stackoverflow.com/questions/31312645/java-imageio-grayscale-png-issue
Gamma miscorrection problems aside, OxiPNG currently tries hard to
reduce RGB(A) images to grayscale, because it expects that reduction to
be quite effective. However, in some cases, OxiPNG generates smaller
PNG files when reducing grasycale RGB(A) images to paletted color than
actual grayscale color. For example, let's say that "~/gray.png" is a
256x256 RGBA image entirely filled with (119, 119, 119, 255) pixels.
OxiPNG, by default, reduces this image to grayscale and achieves a
68.23% decrease:
$ cargo build --release && target/release/oxipng -omax --out ~/out.png ~/gray.png
Processing: /home/user/gray.png
256x256 pixels, PNG format
4x8 bits/pixel, RGBA
IDAT size = 604 bytes
File size = 661 bytes
Reducing image to 1x4 bits/pixel, Grayscale
Trying: 144 combinations
Found better combination:
zc = 6 zs = 0 f = 0 153 bytes
IDAT size = 153 bytes (451 bytes decrease)
file size = 210 bytes (451 bytes = 68.23% decrease)
Output: /home/user/out.png
However, if the --ng option that this commit adds is used to skip the
grayscale reduction step, OxiPNG reduces to a single color palette
instead, which is much more efficient, achieving a 84.42% decrease:
$ cargo build --release && target/release/oxipng -omax --ng --out ~/out.png ~/gray.png
Processing: /home/alejandro/gray.png
256x256 pixels, PNG format
4x8 bits/pixel, RGBA
IDAT size = 604 bytes
File size = 661 bytes
Reducing image to 1 bits/pixel, 1 colors in palette
Trying: 144 combinations
Found better combination:
zc = 3 zs = 3 f = 0 31 bytes
IDAT size = 31 bytes (573 bytes decrease)
file size = 103 bytes (558 bytes = 84.42% decrease)
Output: /home/alejandro/out.png
While OxiPNG should arguably be made smarter to better handle these
cases, in the meantime, adding an option to manually skip that grayscale
reduction can't hurt. In fact, it may even help users achieving the most
out of current versions of OxiPNG, and developers reasoning about what
makes a grayscale-like RGB(A) image compress better with a color
palette.
Due to the reasons stated above, this adds a simple "grayscale_reduction"
option to the Options struct, and a "no-grayscale-reduction" command
line switch, that makes OxiPNG not try this problematic grayscale
reduction on RGB(A) images.
This allows to configure or compile away logging in the library from a single place in Rust apps.
For the CLI side, the usage and output remained the same, except it's now colour-coded.
Fixes#217.
libdeflater is a Rust wrapper around
[libdeflate](https://github.com/ebiggers/libdeflate) - an alternative
heavily optimised library for deflate/zlib/gzip compression and
decompression that is intended for situations where upper bounds of the
output are well-known.
In my benchmarks on test files in the repo it has shown to be usually
both slightly faster and providing better compressed output than
cloudflare-zlib, but in some cases showing the opposite, so rather
than swapping defaults, it's currently provided as another option,
similarly to zopfli.
Since it's not strictly better in all cases, I'm not providing median
numbers, but you can check distribution histograms for time and size
differences here (all using `oxipng -o 6 -t 6 -P`):
https://docs.google.com/spreadsheets/d/1WOKgeYZBhLkQvMGAC36snN4azilElzOFhx63RJu0EZY/edit?usp=sharing
* Fix verbose message
* No cloning when restoring original data
* Make reductions return a new uncompressed image
Partially fixes#145
* Async reduction evaluator
* Assert
* Faster bit depth check
* Also try 4-bit depth for small-depth images
* Skip test when using miniz
* Ensure palette is trimmed after depth reduction
Fixes#159
* Fudge factor for reductions to prefer better reductions even if gzip estimation says otherwise
* Move reductions to a module. Make copy instead of changing in-place.
* Alpha reductions
* Immutable color reductions
* Immutable interlace reductions
