bread-theme: native Rust palette extraction replacing wal -i #30
Loading…
Add table
Add a link
Reference in a new issue
No description provided.
Delete branch "%!s()"
Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?
Reimplement
output::palette_from_imagenatively, keeping its signature so callers don't change. Target: the same output pywal gives for the same image, as close as possible (user requirement).What wal actually does (installed pywal source,
pywal/backends/wal.py+pywal/colors.py):magick "<img>[0]" -resize 25% -colors N -unique-colors txt:-, N starting at 16, retried up to 35, stopping at the first N whose output has more than 16 lines.re.search("#.{6}").color1..color6arecolors[8]..colors[13]of that ordered list (fromadjust()'scolors[:1] + colors[8:16] + colors[8:-1]).Implementation (reworked after review, PR #36):
bread-theme/src/extract.rsis a port of the ImageMagick 7.1.2 Q16-HDRI code that determines that output: geometry.cParseMetaGeometry; resize.c default filter selection (Lanczos, or Mitchell for alpha/PseudoClass input), SincFast/CubicBC kernels and the two-pass HorizontalFilter/VerticalFilter order with alpha blending and unclamped float quantums; quantize.cQuantizeImage(depth 3 for N in 16..35 with the default dither, 8 for gray),ClassifyImageColors,ReduceImageColors/Reduce/PruneChild,DefineImageColormap, and the Riemersma dither with its error queue and 6-bit closest-colour cache; histogram.cUniqueImageColorsorder (blue most significant, red least, first appearance within a leaf); color.cGetColorTuplehex output, including pywal's truncation of 16-bit#RRRRGGGGBBBBto#RRRRGG.bread-theme/src/jpeg.rsports libjpeg-turbo 3.2's default decode (islow IDCT, fancy upsampling, YCbCr tables), so JPEG samples are byte-identical to what ImageMagick decodes. Unsupported JPEG variants fall back to theimagecrate.[0]) and BMP. A decode error is anErr. Images where wal itself would give up (fewer than 16 unique colours) get bread's curated defaults.pywal_colors()returns the full list.bread-theme noticeprints them. The crate licence isMIT AND ImageMagick AND IJG AND BSD-3-Clause.Measured fidelity (bread-theme/scripts/compare-pywal.py, ImageMagick 7.1.2-31 Q16-HDRI)
The previous octree approximation scored 0/30 on fixtures and 0/120 on the real corpus, with 7 near-black outputs.
Timing (release, best of 3), native vs uncached
wal -i: 4K PNG 0.09 s vs 0.29 s, 4K RGBA PNG 0.10 s vs 0.36 s, 4K JPEG 0.16 s vs 0.30 s, 8192x5956 progressive JPEG needing 8 retries 2.5 s vs 9.9 s.Remaining deviations: none measured. Untested corners: JPEG variants handed to the
imagecrate (arithmetic coding, 12-bit, lossless, CMYK, block-smoothed progressive), animated WebP, bitfield-alpha BMP, PNG gAMA=1.0, and ties in quantize-error sorting within 1e-12.Tests: exact per-slot and full-list golden tests for every fixture, determinism, 16-bit truncation, GIF first frame, JPEG bit-exactness against IM-decoded references, histogram order, geometry/filter unit tests, no near-black accents on real photos, and decode errors staying
Err.Part of epic PYWAL.
PR: #36
Native Rust extractor implemented in bread-theme/src/extract.rs, reproducing wal's real pipeline (25% resize, octree quantize, colors[8..14]) per the updated issue body. Measured fidelity numbers and the approximation's limits are documented there and in the PR.
Review: changes requested. Full checklist is on bread-ecosystem#36 (#36 (comment)).
Fidelity against real pywal, re-measured by the reviewer:
quantize_like_wal(extract.rs:175-199) falls through toby_depth[8], the full distinct-colour list, when no octree level has 16 to 35 buckets.This does not meet the requirement of matching pywal as closely as possible.
What to do:
UniqueImageColorstraversal. It orders with blue as the most significant bit and red as the least;bucket_keycurrently has red as the most significant.Rework happens on the existing branch feature/native-palette, and PR #36 stays open. Do not open a second PR for this key.
Rework pushed to the existing PR: #36 (commits
6e34f3band3758f0c; summary at #36 (comment)).The extractor is now a port of ImageMagick's resize/quantize/dither/unique-colors pipeline, plus a libjpeg-turbo-exact JPEG decoder. All accents and full colour lists match real pywal: 84/84 on the fixtures and 132/132 on 21 real wallpapers plus the BOS default, with 0 near-black outputs. It is faster than
wal -i(4K: 0.09-0.16 s vs 0.29-0.36 s). WebP, GIF and BMP now decode. Numbers are in the issue body.Second-round review: parity is confirmed, but one robustness fix is needed. The full review is #36 (comment)
I measured parity independently against real
wal -irun in an isolated HOME:Change requested:
bread-theme/src/jpeg.rs:355-365(also:439,:480): the coefficient and output buffers are sized from the SOF header with no cap. A 22 KB JPEG whose SOF declares 65500x65500 drove RSS to 11.4 GB before oomd killed it. The port runs beforeimage::load_from_memory(extract.rs:204vs:217), so it bypasses theimagecrate's 512 MiB limit. Add a documented allocation budget with checked multiplication in the SOF branch. When the budget is exceeded, return None or Err. Add a test with a tiny JPEG that declares a huge SOF.imagepath an explicitimage::Limitsthat matches that budget. Make truncated JPEGs either libjpeg-exact orErr; today they returnOkwith only 1/6 accents matching. Reword the leftover pywal comments listed in the PR comment.Licensing items (the SPDX over-inclusion of BSD-3-Clause, ImageMagick's upstream NOTICE text, the IJG notice for consumer binaries such as breadpaper) are flagged for the user's decision and are not part of this rework.
Rework happens on the existing branch feature/native-palette, and PR #36 stays open. Do not open a second PR for this key.
Round-3 fixes pushed to the existing PR: #36 (commit
c29a829), CI green.Allocation cap: all three JPEG-port buffers sized from the untrusted SOF header (coefficients, planes, output) now check against one documented 2 GiB budget before allocating anything. The 22 KB / 65500x65500 crafted header is now rejected before allocating (regression test added); a real 16K 16-bit RGBA wallpaper still decodes fine (verified, heavy ignored test). The image-crate path (png/webp/gif/bmp) now uses the same 2 GiB figure as an explicit image::Limits instead of that crate's undocumented 512 MiB default (which was too small for a real 12000x8000 16-bit RGBA PNG). Truncated mid-scan JPEGs now fail outright (UnexpectedEof) instead of returning wrong colours.
Also (per user's licensing decision): split the extractor into a new bread-palette-extract crate licensed "ImageMagick AND IJG", bread-theme back to plain MIT with the extractor behind a new off-by-default extract feature. Full details on the PR.
Parity re-verified: 84/84 accents, 243/243 full-list entries exact, matching pre-move numbers.
Third-round review of PR #36 (
c29a829): changes requested. Full review: #36 (comment)imagecrate, whose max_alloc caps only its own output buffer. A 22 KB file declaring 20000x20000 used 1.9 GB RSS and 21 s of CPU, then returned a garbage palette. Make a budget rejection a hardInvalidDataerror inSource::open(bread-palette-extract/src/extract.rs:201-237, jpeg.rs:423), and add a wal_colors-level test for it.palette_from_imageslicing plus its default-accent fallback) has no test any more. golden.rs re-implements the slice itself. Add acfg(all(test, feature = "extract"))test in output.rs.Verified OK: feature gating (no image/extract dependency without the feature), all three bread-theme workflows pass
--features extractand ship the combined LICENSE, and the licence expressionImageMagick AND IJGis correct. Parity after the move: 21/21 real wallpapers match realwal -ion color1..6, and 336/336 on the full lists.Rework happens on the existing branch
feature/native-palette, and PR #36 stays open. Do not open a second PR for this key.