Quantization result depends on HashMap iteration order, so the same image quantizes differently on x86_64 and aarch64

[dustinkirkland]

pngquant --speed 1 --quality 85-95 (and any speed ≤ 7) produces a different palette and different pixels for the same input on x86_64 and on aarch64, with the same pngquant/libimagequant version. It is fully deterministic on each architecture (run to run, and independent of RAYON_NUM_THREADS), just not across them.

Found while building Noto Color Emoji in a Linux distribution: 92 of the 4,004 CBDT bitmaps differed between the two architectures' builds.

Cause

Histogram::finalize_builder (src/hist.rs) turns the colour hash map into the item list with

temp.extend(self.hashmap.values().map(|&(boost, color)| { ... }));

and everything after that is order-sensitive: the cluster bucketing assigns items[next_index] in that order, total_perceptual_weight is an f64 sum in that order, median cut's select_nth_unstable_by_key / sort_unstable_by_key resolve ties by position, and k-means chunks the slice with par_chunks_mut(256). U32Hasher makes the hash deterministic, but the iteration order of a HashMap also depends on the table's probe-group width, which is 16 bytes with hashbrown's SSE2 group on x86_64 and 8 bytes with the NEON group on aarch64 (hashbrown/src/control/group/{sse2,neon}.rs). Colliding keys therefore land in different buckets on the two architectures, the map iterates in a different order, and the small order-dependent differences are amplified by the refinement iterations into a different palette.

Evidence

• pngquant 3.0.3 packaged from source on both architectures, UN flag image from noto-emoji (136x128 RGBA): palette of 111 colours on x86_64, 120 on aarch64; other images 151 vs 142, 201 vs 219, 35 vs 37. Identical at --speed 8 and above (no k-means iterations, no feedback trials) and with a small fixed palette (pngquant 16).

• Not the SIMD f_pixel::diff: changing the x86_64 horizontal add to NEON's association order (r + (g + b)) changes nothing.

• Not libm: f32 powf/expf/logf fingerprints are identical on both.

• Adding one line after the temp.extend(...):

  temp.sort_unstable_by_key(|t| (t.color.r, t.color.g, t.color.b, t.color.a, t.cluster_index));

  makes the x86_64 build produce, for the UN flag, exactly the pixels and 120-colour palette the unpatched aarch64 build produces, and the aarch64 build with the same one-line change produces the same pixels and palettes as that patched x86_64 build for every sample (UN flag, U+1F92B, U+1F307, U+1F9D4+1F3FE, U+1F600). So with a deterministic histogram order the two architectures agree exactly; without it they do not.

Suggested fix

Sort temp by colour (or iterate the map in key order) before the cluster pass, as above; it costs one sort of the histogram (at most max_histogram_entries items) and makes the output a pure function of the input across platforms. Happy to send that as a PR if you would take it.

[dustinkirkland]

One more place reads the map in iteration order, pointed out in review of our downstream patch: init_posterize_bits rebuilds the map with self.hashmap.extend(old_hashmap.into_iter().map(|(k, v)| (k & new_posterize_mask, v))) when the histogram exceeds max_histogram_entries. extend overwrites, so when several old keys collapse to one posterized key, the (boost, rgba) that survives is whichever the old map yields last, which again depends on the bucket layout. Re-inserting in key order (collect, sort_unstable_by_key(|&(k, _)| k), then extend) makes that step deterministic too while keeping the last-wins semantics; summing the boosts of collapsed entries instead of overwriting would arguably be more correct, but that is a behaviour choice for you. With both sorts in place our x86_64 and aarch64 builds agree on every image we have tried.

[dustinkirkland]

A second, independent source, found while re-checking the fixed build at other quality settings: the hand-written SIMD f_pixel::diff implementations do not add the channel terms in the same order. The x86_64 path (and the scalar fallback) compute (r + g) + b; the NEON path uses vpaddq_f32(max, max) and ends up with r + (g + b). Float addition is not associative, so the distance metric itself differs by an ulp for some inputs, and the refinement loop turns that into a different palette: with both histogram sorts in place, noto-emoji's U+1F92B bitmap at --quality 0-100 still quantised differently on x86_64 and aarch64 (both 256 colours, different pixels), and an x86_64 build with the NEON association order reproduced the aarch64 output exactly.

Changing the NEON path to max_r[1] + max_r[2] + max_r[3] (same order as the other paths; one less instruction) fixes that. With the two histogram sorts and this, our x86_64 and aarch64 builds produce identical pixels and palettes on every image we have tried at both --quality 85-95 and --quality 0-100, including a 262,144-colour image at --speed 10 that goes through the posterize rehash. The same would presumably apply to the WASM SIMD128 path on main (f32x4 lane sums), which I have not tested.

[dustinkirkland]

Pull request with all three changes: #131 (histogram sorted before the cluster pass, posterize rehash re-inserted in key order, NEON diff adding in the same order as the other paths). cargo test passes on x86_64 and aarch64; the verification matrix is in the PR description.