1537 Commits
Author SHA1 Message Date
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
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 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 24807c63d1 Merge compound dictionaries at qualities 10 and 11 into m7a-speed 2026-10-27 12:40:14 +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 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 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 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 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 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 7875e0bd41 std/brotli: size the q10/q11 workbuf with a practical metablock bound
workbuf_len's minimum now assumes at most (n / 16) + 1 blocks per
category and (n / 64) + 64 first-phase clusters (measured maxima are
about 1/83 and 1/258 of n), and 16 BackwardMatches per byte at
quality 11 (measured maximum about 7.4). The maximum stays the C
worst case. Add q10/q11 mimic tests and workbuf_len checks, and use
the minimum in the tests' encode plan driver.
2026-10-27 03:07:53 +00:00
Claude c8bd30dd43 std/brotli: report a too-short q10/q11 workbuf as bad workbuf length 2026-10-27 02:53:07 +00:00
Claude bef6ffc1bd std/brotli: fix the Zopfli starting distance cache order
Also run the encoder parity harness at qualities up to 11, using the
workbuf_len minimum.
2026-10-27 02:43:46 +00:00
Claude 0b9cfddf3c std/brotli: let a shorter encoder workbuf work for short inputs
Move the ring buffer to the end of the workbuf layout (at qualities 2 to
9). A workbuf shorter than workbuf_len now works if it holds the input
so far (plus 16 bytes of slack) in the ring buffer region and the input
stays short enough for the ring buffer never to wrap. This matters most
for large-window brotli, where workbuf_len at lgwin 30 is more than
2 GiB, mostly for a ring buffer that short inputs never touch.

The parity harness now also checks its large-window configurations with
the shortest such workbuf (and that one byte less fails).
2026-10-27 02:36:23 +00:00
Claude 361091fee6 std/brotli: add quality 10 and 11 (Zopfli) encoder, untested
Port H10 (hash_to_binary_tree_inc.h), literal_cost.c,
backward_references_hq.c, the static dictionary match finder
(static_dict.c) and the quality 10+ parts of the metablock writer,
using the metablock_builder. The variable-size Zopfli and
metablock_builder scratch lives in a new workbuf layout region.
2026-10-27 02:36:05 +00:00
Claude 8b0c3204a0 std/brotli: add large-window encoding at qualities 3 to 9
Port the composite hashers H35, H55 and H65 (hash_composite_inc.h) and
the rolling hashers HROLLING_FAST and HROLLING (hash_rolling_inc.h),
which ChooseHasher picks for lgwin above 24, and drop the
"#unsupported encoder quality" gate for the large-window quirk at
qualities 3 to 9. The workbuf's hasher region now includes the rolling
hasher's 64 MiB table when a composite hasher can be chosen.

Extend the encoder parity harness with a large-window grid (lgwin 10 to
30 at qualities 2 to 9) and a -lw option that runs only that grid.
2026-10-27 02:13:21 +00:00
Claude b10d57f20f Merge branch 'm4b-metablock' into m4a-encoder-core
# Conflicts:
#	std/brotli/README.md
2026-10-27 01:26:59 +00:00
Claude 314b20e832 std/brotli: use metablock_builder's distance and RLE helpers in the encoder
This removes the encoder's copies of PrefixEncodeCopyDistance,
CommandRestoreDistanceCode, BrotliInitDistanceParams and
BrotliOptimizeHuffmanCountsForRle. The shared BrotliInitDistanceParams
also handles large-window distance params (used at quality 2).
2026-10-27 01:15:03 +00:00
Claude 5393d92234 std/brotli: document the metablock builder and add golden tests
Bound the number of block types by the number of symbols in
workbuf_len_worst_case, document the metablock_builder interface and its
workbuf layout in README.md, and add deterministic bit cost and
build_meta_block tests (with golden values from libbrotlienc v1.2.1) to
test/c/std/brotli.c.
2026-10-27 01:12:51 +00:00
Claude abecc768e5 Merge branch 'm4b-metablock' into m4a-encoder-core
# Conflicts:
#	release/c/wuffs-unsupported-snapshot.c
2026-10-27 01:10:29 +00:00
Claude e66b315284 std/brotli: fix the UTF-8 prefix LUT; extend the encoder parity test to qualities 2 to 9 2026-10-27 01:04:57 +00:00
Claude 9ad7ae6d69 std/brotli: add metablock_builder.workbuf_len_worst_case
Give the metablock builder an upper bound on the workbuf length that
build_meta_block needs, expose it through the metablock_tester and check
it against the high water mark in the parity harness. Add shard options
(-largeoff, -edge, -manytypes) and a stress phase that reaches 256 block
types to the harness.
2026-10-27 01:03:11 +00:00
Claude 09d4b23d09 std/brotli: WIP encoder qualities 2 to 9 (EncodeData, hashers, greedy metablocks) 2026-10-27 00:58:17 +00:00
Claude 202b406248 std/brotli: port block_splitter.c, cluster.c and metablock.c
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.
2026-10-27 00:52:42 +00:00
Claude 88c32bc668 std/brotli: port bit_cost.c and histogram.c for the encoder
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).
2026-10-27 00:16:37 +00:00
Claude d74d28bef9 Merge branch 'm1c-decoder-extensions' into claude/project-thread-0izcgq
Combines the encoder (quality 0 and 1) with the decoder's large-window
mode and custom dictionaries. The test and mimic files take both sides'
new sections; the fuzzer gains the std/softfloat module that the
encoder now pulls into std/brotli.

Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_011NoosQNe7DKWnqDCBeqw1p
2026-10-26 23:59:14 +00:00
Claude ca1ba9d134 std/brotli: add an encoder for quality levels 0 and 1
Adds a brotli encoder (std/brotli's encoder struct, a base.io_transformer)
whose output is byte-identical to libbrotlienc v1.2.1 for quality levels 0
and 1, mirroring encode.c's BrotliEncoderCompressStream(Fast),
compress_fragment.c and compress_fragment_two_pass.c, plus the entropy
coding and bit stream helpers they need. Every double operation goes
through std/softfloat, following the C evaluation order exactly.

Parameters are quirks (encode_quirks.wuffs) that mirror
BrotliEncoderSetParameter, sanitized at the first transform_io call.
Each transform_io resumption corresponds to one C call with available_in
equal to the readable src length; a closed src is FINISH; request_flush!
and request_emit_metadata! make the next resumption a FLUSH or
EMIT_METADATA call. Qualities 2 to 11 return "#unsupported encoder
quality" for now. Encoder tables are generated by
script/print-brotli-tables.go -encoder.

Tests: round trips through the Wuffs decoder over the corpus and synthetic
inputs; with -mimic, byte-exact comparisons against libbrotlienc over
quality × window × mode × input chunking × flush schedule × metadata ×
size hint. script/manual-test-brotli-encoder-parity.c runs the full
grid: 86,268 configurations, zero mismatches.

Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_011NoosQNe7DKWnqDCBeqw1p
2026-10-26 23:55:56 +00:00
Claude b9be8feaee std/brotli: large-window mode, custom dictionaries and a fuzzer
Completes the decoder's feature set relative to libbrotlidec v1.2.1:

- QUIRK_LARGE_WINDOW mirrors BROTLI_DECODER_PARAM_LARGE_WINDOW: the
  large-window WBITS escape, window bits up to 30, the 544-symbol distance
  alphabet and 64-bit distance arithmetic, with workbuf_len growing to
  (1 << 30) + 542 when the quirk is set.
- decoder.add_dictionary! mirrors BrotliDecoderAttachDictionary for raw
  (LZ77 prefix) and serialized shared dictionaries: compound-dictionary
  distance mapping, the shared-dictionary parser (custom word lists,
  transform lists including the SHIFT transforms, context-dependent
  dictionary selection, prefix dictionaries) and all of its validation.
  Wuffs structs cannot hold slices, so the dictionary bytes are copied
  into the front of the caller's workbuf; the layout is documented in
  the README. Serialized dictionaries are accepted as in a
  BROTLI_EXPERIMENTAL build of libbrotli.
- fuzz/c/std/brotli_fuzzer.c, exercising the quirk, dictionaries and
  random I/O limits.

Tests: new golden vectors for large windows (including a 17 MiB
far-distance stream generated in the test), raw and serialized
dictionaries, nine more malformed inputs, and mimic comparisons that
attach the same dictionaries to libbrotlidec. Differential runs over
2.7 million mutated large-window and dictionary streams found no
divergence from libbrotlidec.

Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_011NoosQNe7DKWnqDCBeqw1p
2026-10-26 23:45:06 +00:00
Claude f33e9f3377 std/softfloat: add bit-exact IEEE 754 binary64/binary32 arithmetic
Wuffs the Language has no floating point types, but some reference
implementations (notably the brotli encoder) make decisions with double and
float arithmetic and libm's log2. Porting them with byte-identical output
needs bit-exact floating point results.

This package implements f64 and f32 add, sub, mul, div, fma, comparisons,
min/max, integer conversions and f64<->f32 conversions on bit patterns,
with round-to-nearest-even, subnormals, infinities and NaNs, following the
structure of Berkeley SoftFloat 3. It also ports glibc 2.39's x86-64
__log2_fma log2 implementation (the variant selected on CPUs with FMA and
AVX2), following the shipped machine code's fused operations.

Verification: test/c/std/softfloat.c checks every operation against the C
compiler's native arithmetic on edge cases and random operands. The
script/manual-test-softfloat-*.c programs run 10^8 random operations per
operation group and compare log2_u64 against libm for every integer in
[1, 2^32) plus 10^7 larger values; all with zero mismatches.

Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_011NoosQNe7DKWnqDCBeqw1p
2026-10-26 22:46:32 +00:00
Nigel Tao 4be865da25 base: fix parse_number_f64("0.000...0001e30001")
Updates PR #184
2026-10-21 12:24:09 +11:00
Nigel Tao d54d330601 base: let parse_number_xxx return "arg too long"
Updates PR #184
2026-10-21 12:04:44 +11:00
Nigel Tao 7f70dda95c release: wuffs gen -version=0.4.0-alpha.12 2026-10-20 14:35:26 +11:00
Nigel Tao 0baab7fe72 release: spin in v0.3.6
This copies wuffs-v0.3.c from the v0.3 branch to the main branch. The
main branch is currently working on an unstable v0.4.
2026-10-20 14:32:33 +11:00
Nigel Tao c99f5af9fe base: fix parse_number_f64, 801 digits before '.'
Fixes #183
2026-10-20 14:09:09 +11:00
sabith saheb 9d41525a2f base: don't read past the end of the slice in parse_number_{u64,f64} 2026-10-19 12:59:04 +05:30
Nigel Tao 2a6876f8bb release: wuffs gen -version=0.4.0-alpha.11 2026-10-18 18:17:12 +11:00
Nigel Tao c677bef7fd std/png: parse cICP chunk
Updates #180
2026-10-18 18:13:59 +11:00
Nigel Tao 1f513d8023 cgen: tweak arm_neon_utility.make_u16x4_multiple
The -O3 codegen is the same (https://godbolt.org/z/5ecWrEq77) but this
avoids compound literals, not part of C++11, and can trigger "compound
literals are a C99-specific feature [-Werror,-Wc99-extensions]".

Fixes #181
2026-10-06 22:30:32 +11:00
Nigel Tao 89b7cc7a36 base: add WUFFS_BASE__MIME_TYPE__ETC 2026-10-05 16:55:53 +11:00
Nigel Tao 3d46062176 cgen: note that base.io_buffer__struct is linear 2026-09-15 10:42:51 +10:00
Nigel Tao 466cf6f15d std/webp: tweak workbuf_len determination 2026-08-10 09:23:05 +10:00
Nigel Tao 59176bb0c7 base: fix color_u64_argb_nonpremul for 64-bit 2026-08-07 09:09:42 +10:00
Nigel Tao 16d6267451 base: specialize swizzle_ycca for bgra_premul 2026-08-06 15:13:04 +10:00
Nigel Tao 0fe5509f1b base: avoid (NULL + 0) in slice functions
Fixes #178
2026-08-06 12:09:47 +10:00
Nigel Tao 7b71d6840a base: rename color_u32_at color_u32_argb_premul_at 2026-08-06 11:53:49 +10:00