- encode_float.wuffs: package-private fast paths for the f32/f64 add, sub,
mul, compare and int conversion calls in the encoder's hot loops. Calling
std/softfloat is a cross-package public call (a receiver check, never
inlined). Each fast path returns exactly the softfloat result and falls
back to it for the uncommon cases. script/manual-test-brotli-float.c
cross-checks them against hardware float and double arithmetic.
- Zopfli update_nodes: compute a length's cost only when its copy code
changes, hoist the distance cache values and the continuation byte, and
use a table for small int to f32 conversions.
- FindBlocks: memoize (block_switch_bitcost + insert_cost) for capped costs
and skip the subtraction for costs at or above a per-byte threshold
(S(c) = c - min_cost is monotone, so such costs would be capped anyway).
- BrotliPopulationCost: per-call memo of each count's term and depth, and
skip the zero terms of the entropy sums.
- std/softfloat: a 64-bit f32_add_mags.
Output is unchanged (mimic tests on gcc and clang, parity sweeps).
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01UZ978BikvkegL2JUkqoB1e
Each bit_cost (one in the encoder, one in its metablock_builder) has a
64Ki-entry FastLog2 cache. The metablock_builder filled all of it before
building each quality 10 or 11 metablock (about 20 ms per encoder, since
each entry is an exact software log2), and the encoder's own cache was
never filled, so the quality 10 and 11 literal cost estimates computed
one software log2 per input byte.
Instead, a bitmap (zeroed when the struct is initialized) records which
cache entries are valid, and the new fast_log2_memo fills an entry the
first time it is needed. Typically only a few thousand entries are used.
bits_entropy, population_cost and their callers become impure (!) to
call it. The values are computed by the same functions, so the results
are unchanged.
On alice29 at quality 10, the encoder executes about 20% fewer
instructions, and a 1000-byte input takes 6 ms instead of 21 ms.
Add the metablock_builder struct, mirroring BrotliSplitBlock (with its
MyRand sampling, InitialEntropyCodes, RefineEntropyCodes, FindBlocks,
RemapBlockIds, BuildBlockHistograms and ClusterBlocks), the histogram
clustering functions (BrotliCompareAndPushToQueue,
BrotliHistogramCombine, BrotliHistogramBitCostDistance,
BrotliHistogramRemap, BrotliHistogramReindex, BrotliClusterHistograms),
BrotliInitDistanceParams, BrotliBuildMetaBlock (including the distance
parameter search) and BrotliOptimizeHistograms (with
BrotliOptimizeHuffmanCountsForRle). All memory that the C code
allocates lives in a caller-supplied workbuf, carved out by a bump
allocator.
bit_cost gets an optional 64Ki-entry FastLog2 cache (filled by the
same softfloat log2), which makes the clustering several times faster.
Extend the metablock_tester and the parity harness to compare
SplitBlock, ClusterHistograms*, BuildMetaBlock and OptimizeHistograms
results with libbrotlienc v1.2.1.
Add the bit_cost struct (encode_bit_cost.wuffs, encode_histogram.wuffs):
BrotliBitsEntropy, BrotliPopulationCost{Literal,Command,Distance},
FastLog2, the histogram helpers and BrotliBuildHistogramsWithContext,
with doubles computed by std/softfloat in the C code's operation order.
Histograms and commands are little-endian byte slices with the C structs'
memory layout.
Add a test-only metablock_tester struct and the
script/manual-test-brotli-metablock-parity.c harness, which compares
BitsEntropy and PopulationCost* bit for bit with libbrotlienc v1.2.1
(200000 random histograms: 0 mismatches).