Skip to content

gamut-png: entropy and bigram filter heuristics, with pruned two-tier trials #480

Description

@justin13888

gamut-png has one of the five filter-selection heuristics oxipng ships, and it is the one
oxipng demoted out of its own default preset.

Current state (src/filter.rs:26, src/encoder.rs:24-32): FilterStrategy::{None, Fixed, MinSumAbs, BruteForce}, where BruteForce tries six whole-image strategies, each fully
DEFLATEd at the final level, sequentially, with no pruning.

What is missing

technique note
Entropy min Shannon entropy of the filtered bytes. ~40 scalar lines.
Bigrams fewest distinct byte bigrams. ~40 scalar lines.
BigEnt min entropy over the bigram histogram.
Two-tier trial compress trials at a cheap level, re-encode only the winner at the real level. Level::Fast already exists; there is no such tier.
AtomicMin pruning a shared best-size-so-far, read before each trial, so a trial already over budget bails. Needs the deterministic tie-break tuple to keep output reproducible.
Per-line trial deflate oxipng's -f 9: actually deflate 2–16 lines with prior context.

oxipng's preset table is the evidence for the first two: MinSum is dropped from every preset
except -o 0 and -o 6
, and its default -o 2 is None, Sub, Entropy, Bigrams. That
demotion, by a project that benchmarks obsessively, is the strongest signal available — there are
no published byte tables, so gamut must measure it on its own corpus.

Negative result worth keeping

An oxipng contributor (an ECT author) reports that a genetic algorithm over filter choices
pngwolf's actual method — "did not prove helpful." Do not build one.

Verification

benches/encode.rs prints the size table and tests/size_contract.rs gates it, both landed in
#224. A new heuristic that does not beat MinSumAbs on gamut's corpus should be recorded as a
negative result in STATUS.md rather than merged.

Refs #224

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions