v0.5.17

• The decoder now rejects a meta-block that runs out of its single-type block
  count with InvalidDataKind::MetaBlock. RFC 7932 sets that count to
  16777216, and C Brotli rejects the same streams with
  BROTLI_DECODER_ERROR_FORMAT_BLOCK_SWITCH. Earlier versions counted from
  u64::MAX and accepted these RFC-invalid streams.

• Clarified ParallelTaskQueue documentation: stopped executors can leave
  blocking I/O and writer finalization waiting indefinitely; dropping queue
  handles or tasks reports closure or abandonment errors when observed. Tasks
  already held by executors must still be run or dropped.

v0.5.16

Faster compression of small inputs and at qualities 5-11, and faster decoding
of dictionary-heavy text. Output is byte-identical at every quality: each
change below was checked against the previous build on alice29.txt,
lcet10.txt, mapsdatazrh, plrabn12.txt, 64x and monkey at 100 B, 1 KiB,
16 KiB, 200 KB and 1 MB, q0-q11 (q10/q11 up to 200 KB), and the C-reference
test suites pass. Time against v0.5.15 (min of 7 interleaved runs per case,
one pinned core, i7-13700KF under WSL2; single-call compression of the
corpus prefix):

input	change
alice29.txt 1 KiB, q1 / q4 / q9	-10% / -16% / -10%
alice29.txt 16 KiB, q5	-7%
lcet10.txt (426 KB), q5 / q6 / q7 / q9	-5.5% / -4.6% / -3.1% / -3.2%
mapsdatazrh (285 KB), q1 / q4 / q5 / q7	-11% / -2.5% / -3.3% / -2.3%
3.85 MB mixed corpus, q5 / q9	-5.0% / -8.9%
lcet10.txt / mapsdatazrh 64 KiB, q11	-5.1% / -4.3%
decode alice29.txt 16 KiB q5 / lcet10.txt 64 KiB q11	-7.8% / -15.9%
q0, q2, q3, q10, mapsdatazrh q9, decoding 1 MB	within +-1.8% (noise)

• Prefix codes sort their leaves by bucket. create_huffman_tree, which
  builds every prefix code except the q0/q1 literal one, ordered leaves with
  the reference's shell sort. It breaks ties by descending symbol, so the
  order is total, and a bucket sort reaches it: leaves are counted per count
  (exactly below 64, per power of two above), placed by descending symbol,
  and only the power-of-two buckets are sorted afterwards. One array serves
  as each bucket's start and cursor. Fewer than 13 leaves keep the
  reference's insertion sort. The q0/q1 literal builder compares counts
  only, so its order among equal counts is the shell sort's own, and it
  keeps that sort. A test compares the bucket sort with the shell sort on
  heavily tied, sparse and full-range histograms up to the 704-symbol
  command alphabet. Alone it cut 1 KiB inputs at q4-q9 by 1.8-7.7% of
  instructions (callgrind).
• Mask scans around the prefix-code builders. The used-symbol passes of
  the bucket sort, convert_bit_depths_to_symbols, the run and trailing-zero
  scans of write_huffman_tree and the front passes of
  optimize_huffman_counts_for_rle (now one walk instead of three) compare
  sixteen entries at once and walk the bit mask (shared::scan). That code
  runs outside the encoders' SIMD entries, so it uses the target's baseline
  level, fixed at compile time (shared::baseline: SSE2, NEON or scalar
  lanes). With the bucket sort, 1 KiB inputs at q3-q9 compress 8-13% faster
  in instructions and 7-16% in time. Tests run every scan on the scalar,
  baseline and detected levels against the plain loop.
• Quality 1 packs literals four at a time. It accumulated literal codes
  until the next would overflow the bit writer's 56 bits, a branch per
  literal; it now writes four codes per call (at most 14 bits each) and the
  rest in one more, as quality 0 already did. Binary input, where most bytes
  are literals, compresses 10-11% faster at q1.
• Next-position bucket prefetch at qualities 5-9. The bucket tables
  outgrow L2 from q6 up, and the load of a bucket's newest slot was the most
  sampled instruction of the search. Each search now hints the bucket of the
  next position, and a match the one after it, with an L1 read prefetch
  through the branches crate (prefetcht0 on x86-64, prfm pldl1keep on
  AArch64), which keeps the inline assembly out of this crate. The reference
  prefetches at the start of each search instead; that placement measured
  slower on binary input (q7 +2%). It is a hint only. Text compresses
  3-5.5% faster at q5-q9 on x86-64, the 3.85 MB corpus 5-9%.
• Quality 11 replays repeated distance-cache probes. 44-57% of the start
  positions update_nodes tries at a byte carry the same distance cache as
  an earlier one there, and such a start finds exactly the same copies. Their
  hits (code, length) are now recorded per start and replayed through the
  same pricing in the same order, skipping the probes: 6-11% fewer
  instructions and 4-6% less time at q11. Quality 10, which tries one start
  per byte, compiles the replay out.
• Built-in dictionary words decode with fixed-size copies. Every built-in
  prefix and suffix is at most eight bytes and a word at most 24, so the
  decoder copies them as fixed 8- and 32-byte moves into its scratch instead
  of three variable-length memcpy calls per reference; an out-of-line exact
  copy handles the last words of the table. Dictionary-heavy text decodes
  3-8% faster in instructions; a test checks all 121 transforms against the
  general transform.
• The bucket prefetch also runs on AArch64. shared::baseline::prefetch
  now calls branches::prefetch_read_data instead of _mm_prefetch through
  fearless_simd::kernel!, which only reached x86-64. It stays a read hint,
  as in the reference: the bucket is read before it is written.

v0.5.15

• Parallel segments at qualities 2-9 copy from the input before them. Each
  segment's part takes the last quarter of a segment before it, within the
  window's backward limit, as history it has already emitted, the way brotli
  1.0's BrotliEncoderSetCustomDictionary primed an encoder: the bytes fill
  the window and match finder, nothing is written for them, and the decoder,
  which has decoded the parts before, holds them. Before, every segment started
  from nothing. Batches read the history with each segment; streams keep it
  across parts, so after a Flush it may come from several short ones. With
  1 MiB segments (one task, best of 7, Apple M5 Pro), alice29.txt repeated to
  4 MiB is 51,261 bytes at q6 (its segments compressed separately: 203,708);
  seq 1 1300000 at q6 with a 22-bit window 376,734 bytes instead of 390,766;
  three copies of /usr/share/dict/words and mixed binary input 0.2-0.6%
  smaller. The
  hashing costs time: q9 with a 22-bit window took 11-12% longer on seq and
  mixed input, q6 2-9%; repetitive text got faster. Qualities 0-1 and 10-11 are
  unchanged. Parallel output at qualities 2-9 changes and still decodes with
  Google's decoder, checked on batches and on streams flushed at random points.
  Serial output is unchanged.

v0.5.14

• Parallel segments at qualities 2-9 copy from the input before them. Each
  segment's part takes the last quarter of a segment before it, within the
  window's backward limit, as history it has already emitted, the way brotli
  1.0's BrotliEncoderSetCustomDictionary primed an encoder: the bytes fill
  the window and match finder, nothing is written for them, and the decoder,
  which has decoded the parts before, holds them. Before, every segment started
  from nothing. Batches read the history with each segment; streams keep it
  across parts, so after a Flush it may come from several short ones. With
  1 MiB segments (one task, best of 7, Apple M5 Pro), alice29.txt repeated to
  4 MiB is 51,261 bytes at q6 (its segments compressed separately: 203,708);
  seq 1 1300000 at q6 with a 22-bit window 376,734 bytes instead of 390,766;
  three copies of /usr/share/dict/words and mixed binary input 0.2-0.6%
  smaller. The
  hashing costs time: q9 with a 22-bit window took 11-12% longer on seq and
  mixed input, q6 2-9%; repetitive text got faster. Qualities 0-1 and 10-11 are
  unchanged. Parallel output at qualities 2-9 changes and still decodes with
  Google's decoder, checked on batches and on streams flushed at random points.
  Serial output is unchanged.

v0.5.13

• Parallel segments at qualities 2-9 use the short distance codes again. An
  independent fragment wrote every copy distance in full, because the
  decoder's distance cache at its start is left by the fragments before it.
  It now starts with distances that never match in all four cache slots, so a
  short code only refers to a slot the fragment's own copies filled, and the
  rest of the fragment encodes distances as a serial stream does. Input with
  one repeated distance shrinks most: 9.3 MB of seq 1 1300000 at q6 with
  1 MiB segments gives 387,467 bytes instead of 2,210,113 (serial 377,638,
  the 1 MiB segments compressed separately 392,833), and one 1 MiB segment
  as a fragment 70,714 instead of 358,630 (serial 71,446). Text without
  such repeats is within 0.1%: three copies of /usr/share/dict/words at q6
  give 2,295,903 bytes instead of 2,297,066. Parallel output at these
  qualities changes; it still decodes with Google's decoder, checked on
  seq, text, random and mixed input at q2-9 with 64 KiB and 1 MiB segments
  and windows of 16, 19 and 22 bits. Speed now matches serial compression of
  the same segments (one task, best of 7, Apple M5 Pro, lgwin 19): seq q6
  102 ms (serial 101 ms, before 96 ms), q9 222 ms (serial 223 ms, before
  192 ms, when the explicit distances skipped the cache work); text within
  1%. Qualities 0-1 and 10-11 keep writing explicit distances in fragments.
  Regression tests check that a q2-9 fragment stays within 5% of a serial
  stream and that a fragment repeating at the distances a fresh cache starts
  with decodes after one that left other distances in the decoder's cache.

v0.5.12

• A reused quality 5 or 6 compressor takes the dense bucket table from its second stream on once the input reaches a sixty-fourth of the table (16 and 32 KiB with the 14-bit shapes, 64 KiB with the 15-bit H6 q6 shape), as qualities 7-9 already did; before, incompressible and binary inputs below the first-stream limit stayed on the slower on-demand layout however often the compressor was reused. Output is unchanged. Measured with a scratch harness (reused Compressor, best of 2-3 runs, one pinned core, Intel i7-13700KF, WSL2, C identity checked): random 64 KiB q6 115 -> 67 us (C 85-92 us), random 32-64 KiB q6 0.54-0.73x the previous time, binary 16-24 KiB q5 0.88x; text, JSON and repetitive input from 4 to 128 KiB within the +-4% noise. Such a compressor now retains about 1-2 MiB more (q6 random 64 KiB: 1.4 -> 3.5 MiB, what text of the same size already retained). Cold one-shot calls are unchanged. Reported in issue #5.
• Parallel memory staging doubles a task's buffer, capped at its staged-payload bound, instead of reserving each appended part exactly. Output and memory accounting are unchanged; a single-segment part is still handed over without spare capacity. A 256 MiB random input at q0 with 64 KiB segments and four tasks took 114-119 ms instead of 143-191 ms; with 4 MiB segments the two are about 4% apart. Reported in issue #5.

v0.5.11

• Add Apache 2.0 license
• ParallelEncoderSession and ParallelEncoderSessionOwned have
  process_uninit, which delivers into &mut [MaybeUninit<u8>] such as
  Vec::spare_capacity_mut without zeroing it first. It produces the same
  bytes, counts, statuses and errors as process, writes nothing past
  produced, and may be mixed with process on one stream. The AFL parallel
  target alternates the two.
• Parallel streams have std::io adapters. ParallelCompressor::writer(sink, window)
  returns a ParallelEncoderWriter and ParallelCompressor::reader(source, window)
  a ParallelEncoderReader, each beside the ParallelTaskQueue their segment
  tasks go to, as start does. Both drive the parallel session and produce its
  bytes, so without a flush the output is byte-identical to prepare_slice
  however writes or source reads are split. Unlike process, they block in
  wait while the window is full or a part is pending, so the queue must run
  on other threads. The writer keeps EncoderWriter's transactional guarantees:
  nothing is lost to short writes or sink errors, Write::flush is
  Operation::Flush, and finish returns the adapter inside FinishError for
  a retry. reader.into_parts() returns read-ahead source bytes as
  EncoderReaderParts. ParallelEncodeError now converts into
  std::io::Error, taking the kind of its root cause through StreamFailed and
  BatchFailed and never Interrupted or WouldBlock. The AFL parallel
  target also drives both adapters.

v0.5.10

• Parallel compression accepts input incrementally. ParallelCompressor::start(window)
  returns a ParallelEncoderSession and a ParallelTaskQueue;
  into_session(window) returns the owned ParallelEncoderSessionOwned. Each
  full segment the session accepts becomes a task on the queue, which the
  caller's executors drain with for task in queue { task.run() }; finished
  parts are delivered in input order through process, flush and finish,
  which never block, while wait blocks for one completion. window bounds the
  segments queued, running or awaiting delivery, and so the session's memory;
  a full window reports the new ParallelEncoderStatus::Pending. Without a
  flush the stream is byte-identical to prepare_slice over the same bytes for
  any chunking, window and execution order, including the serial fallback for
  small inputs. Finishing, failing or dropping the session closes the queue, so
  executor loops end; dropping every queue handle fails the stream with the new
  ParallelEncodeError::TaskQueueClosed instead of hanging, and failures are
  reported as the new ParallelEncodeError::StreamFailed with the cause as its
  source. Batch output is unchanged; batch completions now use an unbounded
  ID channel.
• Measured with cargo bench --bench parallel -- 'parallel/q(1|5)/text-(1|16)MiB/(tasks|stream-tasks)/'
  (Alice cycled to 1 and 16 MiB, 256 KiB and 4 MiB segments, 64 KiB input
  calls and output buffer, Apple M5 Pro, Rayon pool of four): streaming costs
  0.2-2.9% against the batch with one inline task (q5 16 MiB 8.08 -> 8.32 ms)
  and 1.3-8.5% with four executors (q1 16 MiB 3.47 -> 3.74 ms, q5 16 MiB
  2.18 -> 2.37 ms, q5 1 MiB 1.97 -> 2.07 ms): the session copies input into its
  segments and output through the caller's buffer, where the batch reads the
  slice in place. Output sizes are identical.

v0.5.9

• The four-slot quick match finders (H4 and H54, quality 4) measure a candidate through one out-of-line call that also cuts the current window, instead of cutting it in front of the slot loop at every position. The shallow static-dictionary probe (qualities 2 and 4) copies the search result only when its bucket holds a word. Output is unchanged. Quality 4 runs 1-3.5% faster on 2-170 KB web assets streamed in 32 KiB chunks, and the quality 4 criterion cases improve by a median of 2.3%; qualities 2 and 3 move by at most 3% on individual cases, with a median change below 1%.

v0.5.8

• A reused Compressor keeps its encoder across a change of window, block
  size or size hint at qualities 0-9. A pooled compressor that serves inputs
  of different sizes declares a different window for each; that used to
  rebuild the encoder every time. Qualities 0 and 1 now only update the
  fragment limit and the stream header. Qualities 2-9 keep the ring buffer's
  allocation under the new geometry and keep the match finder as long as the
  window still resolves to the same one. Quality, mode, distance layout and
  context modeling still decide whether the encoder can be reused.
• When the size hint or window selects a different match finder at qualities
  5-9 (chain finders below a 16-bit window and bucket finders above it, H5/H6
  at the one-mebibyte hint, or quick storage for short inputs), only the
  finder is replaced. The old finder's dense bucket tables and chain slots are
  parked and handed to the next finder of the same kind without zeroing.
  Parked storage counts towards Compressor::retained_bytes.
  RetentionPolicy::Bounded drops it first and releases the workspace only
  if the compressor is still over the ceiling. A bucket finder that is still
  on its sparse layout rebuilds its index after such a switch.
• The chain match finders H40, H41 and H42 make the number of cached
  distances they check a compile-time parameter, so the probe loops have a
  fixed trip count. H40 and H41 allocate their single bank when they are
  created. The hop loop takes the bank as a fixed-length slice, rereads the
  current position's comparison bytes only when the best length changes, and
  bounds its reads by the masked window. Results are unchanged.
• Small encoder paths drop redundant work: the static-dictionary word test
  rejects most entries with one 8-byte XOR, Huffman literal emission walks a
  contiguous slice when the insert does not wrap the ring buffer, and the
  Huffman RLE count optimizer fills runs with slice writes instead of indexed
  loops.
• New differential tests against Google C cover reused small-window
  compressors, compressors reconfigured across windows, alternating short and
  long inputs, and inputs on both sides of the large-input hint. A regression
  test checks that Bounded trimming drops parked storage before it drops the
  encoder. The RLE optimizer is checked against a line-by-line transcription
  of the C reference on 4000 random histograms.