4133 Commits
Author SHA1 Message Date
ddidderr 7121776bf0 Merge pull request #2 from ddidderr/claude/project-thread-ctw1hr
std/brotli: speed up the encoder (all qualities) and the decoder, byte-exactly
2026-10-28 18:10:09 +01:00
Claude fbae955a74 std/brotli: speed up qualities 0 to 9 and the decoder
Encoder (output stays byte-exact with libbrotlienc v1.2.1):
- H58/H68 (q5-6): match the tags 8 at a time (SWAR, like
  GetMatchingTagMask's non-SSE2 code) and visit the matches with a de
  Bruijn ctz; inline the bucket entry check into the H5/H6 and H58/H68
  loops, caching the 4 bytes compared at best_len; a dedicated H58/H68
  store and hash.
- find_last_distances caches the current byte at best_len.
- ctz64 and a branch-free log2_floor_non_zero (de Bruijn tables), and
  find_match_length_with_limit uses ctz.
- load32le, load64le, peek_u16, poke_u16 and poke_u32 use one bounds
  check each.

Decoder (same output and statuses):
- The literal fast path keeps pos and the counts in local variables.
- Copies of at most 16 bytes, with a distance of at least 16, copy 16
  bytes (like the C code; the window gap keeps the extra bytes unread).

script/manual-test-brotli-float.c also checks log2_floor_non_zero (every
u32) and ctz64.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01UZ978BikvkegL2JUkqoB1e
2026-10-28 08:50:15 +00:00
Claude 044437a8ec std/brotli: speed up the encoder at qualities 10 and 11, byte-exactly
- 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
2026-10-27 23:21:31 +00:00
ddidderr 8ac9e2fd4c Merge pull request #1 from ddidderr/claude/project-thread-0izcgq
std/brotli: byte-exact brotli v1.2.1 decoder and encoder, plus std/softfloat
2026-10-27 20:26:10 +01:00
Claude d95d2ea7f9 std/brotli: record the final fuzzing results and speed
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01UZ978Fjdsyig4v3wYAZRg5
2026-10-27 19:00:55 +00:00
Claude c9bb73e3bf fuzz/c/std: enlarge the brotli fuzzer's encoder dst; clarify brcat's parity claim
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01UZ978Fjdsyig4v3wYAZRg5
2026-10-27 17:27:38 +00:00
Claude 7d040276e5 fuzz/c/std: report metadata in the brotli fuzzer
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01UZ978Fjdsyig4v3wYAZRg5
2026-10-27 17:07:04 +00:00
Claude c17d9a9147 std/brotli: update the docs and changelog for the finished port
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01UZ978Fjdsyig4v3wYAZRg5
2026-10-27 17:06:08 +00:00
Claude 2fc6b96e38 example/brcat: add a brotli decoder and encoder example
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01UZ978Fjdsyig4v3wYAZRg5
2026-10-27 17:06:08 +00:00
Claude bc1b5fcd49 std/brotli: add QUIRK_REPORT_METADATA
The decoder can now report metadata blocks, like libbrotlidec's
BrotliDecoderSetMetadataCallbacks: transform_io returns
"@metadata reported", metadata_length gives the block's length and the
block's contents are written to dst. The differential fuzzer compares
the reported metadata with libbrotlidec's callbacks.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01UZ978Fjdsyig4v3wYAZRg5
2026-10-27 17:06:08 +00:00
Claude 5d6de9880f Remove the M7b handoff note
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01UZ978Fjdsyig4v3wYAZRg5
2026-10-27 16:54:20 +00:00
Claude 3f993a33d2 Add the M7b brotli fuzzing handoff note 2026-10-27 16:49:12 +00:00
Claude 8dcecc67af std/brotli: document the uninitialized ring buffer tail reads
libbrotlienc can read the uninitialized tail of a ring buffer that it grew
after a short first write, and the Wuffs encoder reads the corresponding
workbuf bytes, so both outputs can depend on memory contents (and agree
when the memory does). The fuzzer reruns a mismatch with zeroed memory for
both encoders and counts it as uninit_tail when the outputs then agree and
Wuffs' output decodes.
2026-10-27 16:47:03 +00:00
Claude 73de2fe182 Merge claude/project-thread-0izcgq (speed work) 2026-10-27 15:13:58 +00:00
Claude dbd5a00715 std/brotli: fix long zero runs in the fast Huffman tree encoding
build_and_store_huffman_tree_fast_generic indexed the 704-entry
ZERO_REPS and NON_ZERO_REPS tables with reps & 511, so a run of more
than 511 equal code lengths (e.g. unused command codes between 75 and
688 in a quality 2 metablock of more than 128 commands) was written
wrongly and the stream did not decode. Found by the differential
fuzzer (quality 2, lgwin 10).
2026-10-27 14:20:18 +00:00
Claude a856d133d9 script: hash the seed in the brotli fuzzer
Seeding SplitMix64 with seed * 0x9E3779B97F4A7C15 made consecutive seeds
generate the same sequence shifted by one number, so shards with
consecutive seeds repeated each other's cases.
2026-10-27 14:01:14 +00:00
Claude 8a8df6667a std/brotli: document and test a libbrotlienc metadata stale pointer bug
At qualities 0 and 1, a metadata block whose body went through the C
encoder's tiny_buf_ leaves next_out_ pointing at remaining_metadata_bytes_,
and a later flush's padding bits overwrite it, so every later
BrotliEncoderCompressStream call fails. Wuffs produces the same bytes and
does not mirror the failure. The fuzzer recognizes the corrupted C state.
2026-10-27 13:25:23 +00:00
Claude 0e0674d62b script: no Wuffs-only zero-length dst calls with a stream offset in the brotli fuzzer's API mode 2026-10-27 12:57:24 +00:00
Claude 8ce9c3f552 script: fuzz encoder dictionaries at qualities 10 and 11 2026-10-27 12:41:05 +00:00
Claude 24807c63d1 Merge compound dictionaries at qualities 10 and 11 into m7a-speed 2026-10-27 12:40:14 +00:00
Claude c5c1c00ba6 Merge claude/project-thread-0izcgq (q10/q11 dictionaries) 2026-10-27 12:38:06 +00:00
Claude 6fb1f22c00 std/brotli: document the stream offset flush failure 2026-10-27 12:17:36 +00:00
Claude 85fd6770d5 std/brotli: add decoder fast paths
Add non-coroutine read_symbol_fast and read_bits_fast helpers that are
tried before the coroutine versions, and a process_commands_fast loop
that keeps a 64-bit read-ahead bit buffer and hands back the whole
unconsumed bytes when it exits. process_commands now tracks its position
in a command (cmd_state) so that both loops can resume each other.
LZ77 copies that neither wrap nor reach the ring buffer's end are done in
chunks of at most the distance, which matches a byte-by-byte copy.

Output is unchanged. On alice29 (decoder reused) decoding is about 1.8x
to 2.1x faster for q1, q5, q9 and q11 inputs.
2026-10-27 12:10:41 +00:00
Claude c805b6f6b2 std/brotli: record the q10/q11 dictionary parity results 2026-10-27 10:57:52 +00:00
Claude 0c238497fb script: accept the stream offset flush failure in the brotli fuzzer when both encoders agree 2026-10-27 10:57:15 +00:00
Claude 4dff581dd0 script: check the softfloat comparisons in manual-test-softfloat-sweep.c
Add f32_compare and f64_compare, which run the cmp, eq, ne, lt, le, gt,
ge, min and max functions on every pair of 594 structured values
against the hardware's comparison operators.
2026-10-27 10:43:02 +00:00
Claude 44a9ca086c std/softfloat: compare non-negative, non-NaN operands directly
The f64 and f32 comparison, min and max functions now compare the bit
patterns directly when neither operand is negative or a NaN, and call
the unchanged general code (now f64_cmp_slow and f32_cmp_slow)
otherwise. Results are unchanged: the ops harness and the old-vs-new
differential test report zero mismatches.
2026-10-27 10:30:04 +00:00
Claude ab5930ffbb std/softfloat: return early for zero operands, merge the f64 add/sub fast paths and add a faster f32_from_u32
f64_add and f64_sub now share one fast path for normal operands
(f64_add_normal) and both return early when one operand is zero. The f32
add and sub do the same, and f32_from_u32 converts values below 2^24
directly. All results are unchanged: the sweep, the old-vs-new
differential test and the ops harness report zero mismatches.
2026-10-27 10:18:57 +00:00
Claude 49356e06e4 std/brotli: fill the FastLog2 caches lazily
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.
2026-10-27 09:57:01 +00:00
Claude 86d8c8e9e6 fuzz/c/std: cap the brotli fuzzer's encoder input lengths
Large inputs at qualities 10 and 11 made some fuzz inputs take tens of
seconds under sanitizers.
2026-10-27 09:36:06 +00:00
Claude 1d1c338981 std/softfloat: add fast paths for f32 and f64 add, sub and mul
f32_add, f32_sub and f32_mul now compute the result directly in binary32
when both operands are normal and the result is normal (or overflows),
instead of always going through f64. f64_add and f64_sub get a similar
fast path for normal operands. Every other case takes the previous code
path, so results (including NaN payloads) are unchanged.

Add script/manual-test-softfloat-sweep.c, which checks the f32 and f64
add, sub, mul and div operations over every pair of operand exponents
with many mantissa patterns, and the f32 conversions, against the
hardware and (bit-for-bit, NaNs included) the via-f64 definitions.
2026-10-27 09:26:09 +00:00
Claude 39f68cb02b fuzz/c/std: add an encoder round trip to the brotli fuzzer
The fuzzer also encodes its input, with encoder parameters (quality, lgwin,
large window, mode, lgblock, literal context modeling, size hint, npostfix,
ndirect, a raw dictionary), chunking, flushes, metadata blocks and dst limits
derived from the input's hash, and checks that decoding gives the input back.
Add plain text seeds.
2026-10-27 09:20:56 +00:00
Claude 2241af92c1 std/brotli: document the split-input BLOCK_LENGTH_1 difference
libbrotlidec's internal input buffer, used after it rolls back a partially
read command, distance or block switch, makes it run out of input (and check
for an overrun metablock) at more points than the Wuffs decoder. Found by
differential fuzzing; add a mimic test that pins the behavior.
2026-10-27 09:14:05 +00:00
Claude d89864223e script: add replay and API edge case modes to the brotli fuzzer 2026-10-27 09:12:22 +00:00
Claude f6798c006d script: use the smallest dictionary grid at q10/q11 for big inputs
Like the regular grid, qualities 10 and 11 use the smallest dictionary
configuration set for inputs longer than 64 KiB.
2026-10-27 09:08:15 +00:00
Claude 6568bc1b75 std/brotli: document compound dictionaries at qualities 10 and 11
Describe the Zopfli path's dictionary lookups, the extra quality 11
BackwardMatch storage in workbuf_len and drop the TODO items.
2026-10-27 09:08:15 +00:00
Claude ec99ba2a01 std/brotli: support compound dictionaries at qualities 10 and 11
Mirror the Zopfli path's compound dictionary code in
backward_references_hq.c and hash.h: LookupAllCompoundDictionaryMatches,
FindAllCompoundDictionaryMatches, MergeMatches, the lz_matches_offset
and shadow_matches scratch space, the gap in ComputeDistanceShortcut,
UpdateNodes (including its compound dictionary last distance branch)
and BrotliZopfliCreateCommands, and the dictionary distance passed to
FindAllMatchesH10.

Remove the quality 10 and 11 dictionary gate (and its now unused
status), size the quality 11 variable region for the shadow matches
and turn the gate's test into a byte-exact check. The mimic dictionary
grid, big and rejections tests now also cover qualities 10 and 11.
2026-10-27 09:02:50 +00:00
Claude ef6ac20062 script: add the encoder mode to the differential brotli fuzzer 2026-10-27 09:00:11 +00:00
Claude 7191bab983 script: add a differential brotli fuzzer (decoder mode) 2026-10-27 08:54:18 +00:00
Claude d72d46ea97 std/brotli: fix the q10/q11 speed estimate 2026-10-27 07:30:48 +00:00
Claude 7d78d4ecaf std/brotli: record the quality 10 and 11 parity results 2026-10-27 07:30:43 +00:00
Claude 3f60ead4fc script: allow encoder parity workbufs of up to 12 GiB, link libbrotlidec 2026-10-27 06:10:02 +00:00
Claude ed7afaeab9 Merge claude/project-thread-0izcgq (encoder raw dictionaries)
At qualities 10 and 11, attaching a dictionary makes transform_io
return "#unsupported encoder quality" until the Zopfli path's compound
dictionary lookups are ported.
2026-10-27 06:06:39 +00:00
Claude 8116438ae8 std/brotli: record the encoder dictionary parity results 2026-10-27 05:30:41 +00:00
Claude 36a4380062 std/brotli: test encoder dictionaries and document them
Add mimic_brotli_encode_with_dictionaries to the mimic library and
encoder dictionary tests: the add_dictionary API, its workbuf
accounting and rejection cases (matching libbrotlienc's default build),
a parity grid over qualities 0 to 9 with several dictionary sets, stream
offsets, large window, flushes and metadata, and dictionaries of 2 to
33 MiB, each round tripped through both decoders.

Document the encoder's dictionary API, workbuf layout and differences
from the C code.
2026-10-27 05:28:37 +00:00
Claude aabdeaf4b0 std/brotli: add encoder raw (prefix) dictionaries
Mirror BrotliEncoderPrepareDictionary (BROTLI_SHARED_DICTIONARY_RAW),
CreatePreparedDictionary and BrotliEncoderAttachPreparedDictionary as
encoder.add_dictionary, with the prepared hash tables (slot offsets,
heads and items) in the workbuf after the dictionary bytes, and the
compound dictionary search (FindCompoundDictionaryMatch and
LookupCompoundDictionaryMatch) for the hashers whose
CreateBackwardReferences variant enables it, the compound dictionary
gap for static dictionary distances and the compound branch of
ExtendLastCommand.

Extend the encoder parity script with a -dict grid that also checks
round trips through libbrotlidec and the Wuffs decoder.
2026-10-27 04:54:39 +00:00
Claude 7d58caf91c Merge claude/project-thread-0izcgq (large window at qualities 3 to 9)
Put the q10/q11 variable region before the ring buffer (now the last
region), growing it (and moving the ring buffer) at the first
transform_io call to use a workbuf longer than workbuf_len's minimum.
Large window now also works at qualities 10 and 11.
2026-10-27 04:46:52 +00:00
Claude b52e608b7c std/brotli: record the large-window parity test results 2026-10-27 04:18:32 +00:00
Claude 2236afbd96 script: add a -oneshot option to the encoder parity harness 2026-10-27 03:13:45 +00:00
Claude ccc46dee9e std/brotli: document the quality 10 and 11 encoder 2026-10-27 03:11:46 +00:00