oxipng-bytes: smaller lossless PNGs, within an instruction budget

oxipng is the lossless PNG optimiser behind Squoosh and many image pipelines. This project asks for smaller files from it on images nobody has seen, with every pixel kept exactly, at about the compute upstream spends: a gain here is a change upstream can take as its default. PROGRAM.md is the agents' brief; this file is the project's record.

The upstream

src/ is oxipng v10.2.1's library (oxipng/oxipng 36f3ef8, 2026-09-02, MIT, LICENSE-oxipng), as it is but for two things:

• its command line (src/main.rs, src/cli.rs) isn't here: nothing builds it;
• RowFilter::try_from (src/filters/mod.rs) matches on the value instead of transmuting it: the same function without unsafe, which Cargo.toml forbids (PROGRAM.md, "Code boundary").

Cargo.toml keeps upstream's dependencies, features and release profile, and adds the workspace (the program harness/arh-png) and the unsafe_code = "forbid" lint. Cargo.lock is upstream's, narrowed to what the build uses. The incumbent is upstream: the program runs Options::from_preset(2), oxipng's default, and scores exactly 1.0 by definition.

The project's own repository is the platform's (an admin's import): autoresearch.toml names no upstream, which would be the repository holding this project, and oxipng/oxipng doesn't.

How a run is scored

The worker hands the grader its optimiser, a static executable; the grader runs it on each image under QEMU 11.1.2's user-mode emulator with an instruction-counting plugin, in a Landlock and seccomp sandbox, and checks every output with libpng and pypng (PROGRAM.md). The score is the mean over the images of output bytes / upstream preset 2's bytes. Instructions are capped at 4x upstream's on each image and 1.25x over the run.

Why instructions: wall time and CPU seconds vary from run to run and machine to machine; the eval VMs have no performance counters; the emulator's count is exact. The same program on the same image gives the same count everywhere, so a budget at the edge is decided the same way on every run, and contributors can see their counts before they submit. Measured: repeated runs count the same to the instruction, also side by side under load; the emulator's output is byte-identical to the native program's.

That needed work, because the emulator passes the host through: its randomness (Rust's HashMap keys), its clocks and time-stamp counter, and its randomised address layout. Any of them changed a count from run to run, by a few dozen instructions in a billion for upstream and arbitrarily for a program that reads the clock, enough to decide a run at the budget's edge either way. Now:

• the plugin (grader/native/insncap.c) answers the program's system calls: clocks from the instruction count, getrandom from a fixed seed, and ENOSYS for anything a single-threaded filter doesn't need (files, the pid, threads, timers);
• the patched emulator (grader/native/qemu.patch) steps the time-stamp counter by a fixed amount a read, and runs the program in a guest address space it reserves and lays out alone (-R, 2 GiB), checking every load and store against it before it happens;
• a rep-prefixed string instruction counts each memory access it makes, so a 1 MiB rep movsb costs about two million, not one.

These are the platform's instruction-count kit (sdk/insncap), vendored here verbatim.

Why the emulator's count holds: a user-mode emulator doesn't isolate the program's memory from its own, so the patched emulator checks every load and store the program makes against the program's reserved space before it happens, and ends a run that reaches outside it (escape): the count is out of its reach (sdk/insncap/README.md lists every path QEMU takes from a guest address to a host one, and what covers it). src/ is safe Rust as well (unsafe_code = "forbid", which no attribute in src/ can lift), and the dependencies are fixed. And the program's system calls are the plugin's first and the sandbox's after: no files, no network, no process, and one thread.

The images

Every image, in the sample and in the held-out set, is a seeded derivative of a licensed source (tools/corpus.py): a crop, a rescale, a composite or a re-encoding that exists nowhere else, so no table of known images' outputs can match one. The categories, and the held-out set's counts (the sample's in brackets):

category	from	made by	held-out (sample)
photo	NASA Image and Video Library (US Government works); Wikimedia Commons featured pictures (CC0, CC BY, CC BY-SA, public domain)	scaled 0.5-1, cropped to 256-768 px a side	20 (4)
screenshot	Wikimedia Commons screenshots of free software (GPL, LGPL, CC licences)	cropped to 320-1024 x 240-768 px	25 (5)
diagram	Wikimedia Commons SVG charts, rendered by Wikimedia	scaled to 400-900 px wide	25 (5)
icon	Twemoji (CC BY 4.0)	3-25 emoji composited on a 128-512 px canvas	25 (5)
pixel	Wikimedia Commons pixel art	cropped, scaled 1-4x by nearest neighbour, often a palette image	20 (4)
edge	PngSuite (free for any purpose)	as it is: 16-bit, gray, low bit depths, transparency, interlacing	5 (1)

Each is then encoded as unoptimised PNGs often are (zlib level 1-9, no filtering), sometimes widened (palette to RGB, gray to RGB, 8 bits to 16) or interlaced, and given metadata at seeded rates: sRGB, an ICC profile (Display P3 or sGrey, Compact-ICC-Profiles, CC0), gAMA and cHRM, text (the source's URL, licence and credit), pHYs, eXIf. No image has bKGD, sBIT, hIST, sPLT or tIME.

• The sample (sample/) is 24 images, published with sample/items.jsonl: each image's sha256, its sources and their licences, and upstream's instructions and bytes on it.
• The held-out set is 120 images built the same way from a secret seed and sources the sample doesn't use (a source is the sample's or the held-out set's by its sha256). PngSuite's small set of files is the one source both may use. The platform stages one held-out file, so the set goes up as one uncompressed tar, items.tar: its items.jsonl and the images it names, at the archive's top, nothing else (the grader refuses a link, a path, a name twice or a file items.jsonl doesn't name). From the set's directory: tar -cf ../items.tar items.jsonl *.png; then arh run --heldout ../items.tar runs on it.
• tools/corpus.py builds either from its recipe; the same recipe makes the same bytes.

The metric and the MMI

mean_size_ratio: the mean over the images of output bytes / upstream's bytes (ref in items.jsonl), each image weighted the same. The incumbent's item scores are all exactly 1.0, so the noise floor is the platform's minimum for a deterministic metric, 0.1%, and the MMI is 0.25%: on the sample, as if every image lost a quarter of a percent (about 4,900 of its 1,975,567 bytes). What guards the generalisation is the held-out images, never visible and existing nowhere public, and the hold at 12 steps (about 3%) at once: PROGRAM.md, "The MMI".

The ladder

On the sample, natively (oxipng's command line at v10.2.1, one thread):

settings	mean ratio	bytes	CPU time	x upstream
-o2 (upstream, the incumbent)	1.0000	1,975,567	5.1 s	1.0
-o3	0.9960	1,961,172	9.4 s	1.9
-o4	0.9855	1,955,566	12.3 s	2.4
-o5	0.9836	1,952,041	47.9 s	9.4
-o6 (-omax the same)	0.9830	1,950,324	76.3 s	15
-o2 --zopfli	0.9725	1,948,265	186.1 s	37

Brute force runs out fast: the budget is 1.25x upstream's instructions over the run, so preset 4's settings are already over it, and preset 6 saves only 0.25 points more than preset 4 for six times the work. Zopfli saves 2.75% of the mean ratio but 1.4% of the bytes, so its gain is larger on the small images, which the mean weighs as much as the large ones. A gain has to come from choosing better, not searching more.

Budget and time

Upstream, measured under the grader's emulator (items.jsonl's instructions): 23.6 billion instructions on the sample's 24 images (5.4 megapixels, about 4,400 a pixel) and 87.7 billion on the held-out set's 120 (23.4 megapixels). A run may spend 1.25x upstream's total over the held-out set, and at most 4x upstream's count on any one image; a program over either fails the run (over_run_budget, over_image_budget).

The emulator runs at about 1/22 of native speed. On a shared 48-core build host, measuring upstream over the sample took 119 s (about 200 million instructions a second) and, with the host far busier (load 200), 486 s. A run at the whole budget (110 billion instructions) is then 9 to 38 minutes of emulation, plus each image's checks; run_timeout_s is 7200 s on cpu-m (the score doesn't depend on speed, so the deadline leaves room for a contended pool).

Measuring

The grader's image measures any optimiser the way a run does, without the budget (grader/measure.py): its count and bytes on each image.

docker build -f dockerfile.worker -t oxipng-bytes-worker .
docker build -f dockerfile.grader -t oxipng-bytes-grader .
docker create --name w oxipng-bytes-worker && docker cp w:/app/bin/arh-png . && docker rm w
docker run --rm -v "$PWD/arh-png:/w/arh-png:ro" -v "$PWD/sample:/eval:ro" oxipng-bytes-grader \
  python measure.py /w/arh-png /eval

Each line is {"file", "instructions", "ref"}; set the instructions against items.jsonl's: 4x on any image and 1.25x in total are the caps. The counts are exact, so this is the run's own answer.

Running it

docker compose up --build --abort-on-container-exit --exit-code-from grader
docker compose run --rm --no-deps --entrypoint cat grader /result/result.json
docker compose down --volumes

arh run (the platform's CLI, cli/README.md) runs the same three commands and prints the result.

Licences

The project's own files are MIT (LICENSE); oxipng's are MIT (LICENSE-oxipng); the dependencies keep theirs. The sample's images carry their sources' licences, named per image in sample/items.jsonl (CC BY and CC BY-SA sources credited there and in each image's text chunks where it has them).