Roadmap: structured-zstd feature parity with C zstd

[polaz]

Project goal

structured-zstd is a drop-in replacement for libzstd / zstd CLI — same ABI / CLI / feature surface (a superset of upstream: every documented upstream symbol works, plus additional Rust-side higher-level streams). NOT a binary-parity port: compressed output bytes do not have to match upstream — the encoder may make different (and sometimes better) choices. Wire-format interop (frames round-trip both directions, decoder accepts any valid upstream frame) is required; byte-identical reproduction of donor output is not.

Past phases (Phase 1 correctness, Phase 2 coordinode critical path, Phase 3 perf-parity, Phase 4 SIMD, Phase 4B dictionary decode hot path, Phase 5 Fast donor port M1-M8, direct-write decode + skippable frames API + expect-validation setters) have all shipped. Tracking history lives in merged PRs and git log. This roadmap covers what's left.

---

Active path (sequential — do not branch)

#	Issue	What	Status
A1	✅ #246	DoS-safe rollback for the direct-decode path: malformed Compressed blocks past declared FCS return a structured error instead of a release-mode panic.	✅ DONE — reassessed: the direct-decode writers (sequence executor exec_sequence_inline/_avx2, Raw/RLE try_push, tail literals, match-repeat try_reserve) are all fallible as of #263, returning OutputBufferOverflow / FrameContentSizeMismatch; the heavy fallible-trait rewrite was unnecessary. #246 added the Compressed-block regression test + direct-path fuzz target and closed.
A2	✅ #247	Top-level CpuKernel dispatch at FrameDecoder / FrameCompressor entry + FSE Entry layout. One runtime detect → ZST propagated through HUF / FSE / SIMD-copy / bit-reader / match-copy via monomorphization. Lets default rustc build pick up BMI2/AVX2 at runtime without target-cpu=x86-64-v3 build override.	✅ DONE — all five parts merged: Part 1 FSE Entry (#252), Part 2 decoder dispatch (#254/#263 + #291 monolithic + #289/#292/#293/#294/#295 perf chain), Part 3 encoder Row-matcher dispatch (#305/#306), Part 4 memory-copy path parity (#256-#266), Part 5 kernel_* Cargo features (#307).
A3	#178	Negative-level decode + greedy-encode donor gap umbrella (parent for A2 + further sub-strategies).	OPEN — re-measured 2026-06-11: negative-level decode gap closed from 3-5× to 1.3-1.4× (z000033 L-1: c_stream 1.40×, rust_stream 1.32×); dedicated Greedy strategy landed (L5 on the Row finder, donor shape). Remaining: HUF burst monolith port (biggest decode lever on literal-heavy frames), encoder Fast/Dfast throughput (L1 now 0.57× donor, was 0.44×), btultra L18/L19 ratio (needs BT matcher).
A4	#111 Phase 7	Encoder per-level FFI parity tuning, lanes: compress (Fast/Dfast/Lazy/Greedy/Opt/BtUltra/BtUltra2) → decompress → memory → tooling. Phase 7pre enablement + baseline DONE. Currently active: 7-compress-fastest (Fast/Simple L-7..=1, throughput pure_rust ~205 MiB/s vs FFI ~360 MiB/s on i9-9900K, 0.57×).	OPEN — Phase 1-6 + 7pre done; Phase 7 lanes remaining. Merged (2026-06: #389/#390/#393/#394/#395): dfast donor greedy double-fast reshape + monolithic kernel; Greedy/Lazy band switched to the Row finder (donor resolveRowMatchFinderMode parity, mask iteration, 4-byte rep gate); L13-15 real Btlazy2 ladder; checksum default = reference API parity (off) with runtime toggle; per-block cache-hot decode hashing; zero-allocation reused-compressor path at every level band (musl compress-dict outsiders closed, 5.5×); donor FASTCOVER epoch trainer (dict-train 34× faster, now beats C 4×). Absorbs the block-splitter residual gaps that previously hung off the (now-closed) #23. Merged (#354): full LEVEL_TABLE → donor clevels.h alignment (L3/L4 dfast + L5 greedy + L6-15 lazy: window / hash / chain / 1<<searchLog values), per-strategy Option<…> config (no dead placeholder knobs), dfast hash sizing config-driven (was hardcoded DFAST_HASH_BITS), donor-correct pre-split (block-split level now keyed by strategy per donor splitLevels[] — Fast 0 / Dfast 1 / greedy-lazy 2 / lazy2-btlazy2 3 / bt 4, replacing #140's L11-15→0, L16-22→4 and now wired into the Fast one-shot loop too) + AVX2/VBMI2/BMI2 decode exec-macro monolith. z000033: ratio beats C across L1-L4/L11; encode +20-31% (block-split cost), decode −4.4% vs prior. Merged (#355): inline SIMD literal copy for medium-length runs on the encode path (7-compress-fastest throughput lane).
A6	✅ #184	Lazy band investigation — ratio + speed regressions vs FFI on L5-L15.	✅ DONE (#310) — row-matcher minMatch 6→5 (donor parity for the whole L5-15 row band): L5 greedy was +4.7% worse on z000033, now BEATS C; L6-15 all beat C, zero regression; came with −4.85% encode speed win. Residual ratio leads now sit on Fast/Dfast L1/L2 and btultra L18/L19 (separate, tracked under A4).
A7	✅ #27	ZSTD_CCtx_setParameter Rust-side surface — hard prereq for Phase 6.2 (FFI param wiring).	✅ DONE — configurable compression-parameters API shipped.

---

Phase 6 — C ABI / CLI drop-in parity (after active path stabilizes)

Target upstream version: v1.5.7. Vendored headers verbatim + hand-written extern "C" wrappers. Wire-format interop required, byte-identical compressed output NOT required.

Order	Issue	What	Est	Blocked by
6.1	✅ #126	C ABI core: cdylib + vendored headers + simple / context / error / frame-inspection wrappers	10-12d	A4 (#111 stable internal API)
6.2	#127	Advanced + streaming + dictionary C FFI surface, incl. ZSTD_c_nbWorkers inline wiring (does NOT depend on #19). Note: the stable ZDICT_* dictionary-builder slice already shipped early in 6.1 (#386) — remaining here is the advanced/streaming surface + ZSTD_CCtx_setParameter FFI wiring.	10-12d	6.1 ✅, A7 (#27) ✅ — unblocked, next
6.3	#128	zstd CLI v1.5.7 parity: argv[0] dispatch, env vars, dict, list / test, -T#	12-14d	6.1, 6.2
6.5	#130	Legacy frame decoders v0.1-v0.4 + per-version Cargo features	14-16d	6.1
6.6	#131	Legacy frame decoders v0.5-v0.7	10-12d	6.5
6.7	#132	Conformance (tests/playTests.sh) + cross-validation + ABI symbol snapshot + reverse-dep smoke	10-12d	6.3, 6.6

Phase 6.4 retired (original Cargo-features subtask folded into 6.5). Phase 6 total: ~66-78 working days.

---

Background / opportunistic

Picked up when active path is blocked or as filler. None block Phase 6.

Issue	What
#72	Parallel block decompression for multi-block frames
#205	HUF burst body x86-64 inline-asm experiment (BMI2) — independent stretch experiment; #247 Part 2 runtime dispatch landed but did NOT subsume this (hand-rolled asm replaces LLVM-generated burst body, separate concern).
✅ #211	Per-alloc-site memory tracker tooling — closed: shipped as the dhat-heap feature wired into the standalone profiling examples

---

Deferred — post-Phase 6 only

Issue	Why deferred
#19	Rust-side rayon MT compression. Strategy doc landed (3 BLOCKERS: matcher pool not per-task ::new(), raw-content prime semantics verification, streaming-shaped job API from day 1). Implementation deferred until drop-in parity (Phase 6) ships — Phase 6.2 (#127) wires ZSTD_c_nbWorkers inline without requiring this.

lsm-bilateral items shipped ahead of the deferral

These were executed early (consumed by coordinode-lsm-tree):

Issue	What	Status
✅ #172	Skippable-payload visitor callback on FrameDecoder (PR-B).	DONE
✅ #173	FrameEmitInfo block-layout introspection + opt-in per-block XXH64 sidecar (PR-C).	DONE
✅ #176	Skippable Frame Magic Allocations registry + bilateral hygiene policy docs (PR-A bundle).	DONE
✅ #177	Expected-field validation setters on FrameDecoder (expect_dict_id, expect_window_descriptor).	DONE
✅ #174	Block-precise error position on FrameDecoderError (PR-D): lsm-gated FailedToReadBlockHeaderAt / FailedToReadBlockBodyAt variants carrying block_index / frame_offset / FrameBlock.	DONE
✅ #175	Block-subset partial decode (range + recovery) + per-block decompressed byte ranges (PR-E).	DONE (#357)

---

Bilateral commitment status (lsm-tree)

Bilateral commitment with structured-world/coordinode-lsm-tree preserved — fully shipped: PR-A (#176), PR-B (#172), PR-C (#173), PR-D (#174), PR-E (#175). Cross-reference table kept for context:

zstd	lsm-tree counterpart	LSM-T#	Direction
✅ #176	#250	LSM-T1	spec cross-link

[polaz]

Roadmap actualized after merge of #56 (PR #76).

Updated:

• Marked perf: packed FSE Entry layout (4-byte entries + bulk table spreading) #56 as done (perf: packed FSE Entry layout (4-byte entries + bulk table spreading) #56) in Phase 3 table and dependency graph
• Updated Phase 4 dependency note for perf(decoding): SIMD HUF decode kernels with runtime CPU dispatch #66 (blocked-by prerequisite now closed)
• Removed perf: packed FSE Entry layout (4-byte entries + bulk table spreading) #56 from "next actions" list and renumbered remaining priorities
• Recalculated rough remaining estimates (Phase 3 and total)\n\nVerification source: issue perf: packed FSE Entry layout (4-byte entries + bulk table spreading) #56 state = CLOSED, PR perf(fse): pack decoder entries and align decode tables #76 state = MERGED.

[polaz]

Roadmap actualized (2026-04-07):

• Verified referenced issue states against repository issues (no status-marker mismatches found).
• Updated roadmap issue header with wtmp begins Thu Dec 18 20:35:54 EET 2025.
• Recalculated remaining estimate based on currently open roadmap issues:
  • Phase 3: ~5d 1h
  • Phase 4: ~11d 8h
  • Phase 5: ~20d 4h
  • Total: ~36d 13h (~37 working days).

No roadmap items were added/removed in this pass; execution order remains unchanged.

[polaz]

Roadmap actualized after merge of #47.

Changes applied:

• Marked perf(encoding): reuse encoded scratch buffer across streaming blocks #47 as completed in the Phase 3 table (3.10), parallelizable list, and dependency graph (done marker).
• Updated estimates: Phase 3 remaining changed from 5d 1h to 5d; total remaining changed from 36d 13h to 36d 12h.
• Updated Last actualized date to 2026-04-08.

No additional issue status changes were detected in this pass.

[polaz]

Roadmap actualization (2026-04-08):

• verified roadmap issue references against current GitHub issue states
• migrated completed entries from strikethrough format () to issue-mode format ()
• updated Phase 3 to mark as closed
• normalized closed blockers in dependency columns to

Current plan state: completed through Phase 3.11; next highest-impact open queue remains .

[polaz]

Roadmap actualization (2026-04-08):

• verified roadmap issue references against current GitHub issue states
• migrated completed entries from strikethrough format to issue-mode format (✅ #N)
• updated Phase 3 to mark ✅ perf(encoding): rebase HC table positions to remove 4 GiB Better level cutoff #51 as closed
• normalized closed blockers in dependency columns to ✅ #N

Current plan state: completed through Phase 3.11; next highest-impact open queue remains #68 -> #69 -> #66 -> #70 -> #67 -> #71.

Note: previous comment in this thread had shell-escaping artifacts; this comment is the corrected summary.

[polaz]

Roadmap actualized after merge of #67 (PR #84).

Updated in issue body:

• Marked Phase 3 as DONE ✅ and switched 3.12 to ✅ perf(encoding): implement row-based match finder for fast/dfast levels #67
• Updated Phase 3 parallelizable/dependency graph entries to completed state
• Removed perf(encoding): implement row-based match finder for fast/dfast levels #67 from next-actions queue and renumbered priorities
• Recalculated estimates:
  • Phase 3 remaining: ~0d
  • Phase 4: ~11d 8h
  • Phase 5: ~20d 4h
  • Total remaining: ~31d 12h (~32 working days)

Verification source:

• perf(encoding): implement row-based match finder for fast/dfast levels #67 state = CLOSED
• perf(decoding): SIMD wildcopy for literal and match memcpy #68, perf(decoding): branchless offset history, stride prefetch, BMI2 pext #69, perf(decoding): SIMD HUF decode kernels with runtime CPU dispatch #66, perf(encoding): SIMD match-length comparison (SSE4.2/AVX2/NEON) #70, perf: ARM platform optimizations (CRC32 hash, NEON copy, SVE2 histcnt) #71, feat: optimal parsing compression (btopt/btultra/btultra2 strategies) #22, feat: block splitting for improved compression ratio #23, feat: long distance matching (LDM) for compression #18, feat: magicless frame format support #26, feat: configurable compression parameters API #27, feat(encoding): Rust-side rayon-based multi-threaded compression (multi-frame concat) #19, perf(decoding): parallel block decompression for multi-block frames #72 = OPEN

[polaz]

Roadmap actualized after merge of PR #85 (2026-04-09).

Changes applied:

• Marked as complete in Phase 4 and updated critical-path note.
• Reordered next actions to start from (since is done).
• Recomputed remaining estimates: Phase 4 from to , total from to .
• Kept in Phase 4 as the encoding default small-input latency-cliff fix.

Also closed issue #68 explicitly (PR #85 did not auto-close it because it lacked a closing keyword).

[polaz]

Roadmap actualized after merge of PR #85 (2026-04-09).

Changes applied:

• Marked perf(decoding): SIMD wildcopy for literal and match memcpy #68 as complete in Phase 4 and updated critical-path note.
• Reordered next actions to start from perf(decoding): branchless offset history, stride prefetch, BMI2 pext #69 (since perf(decoding): SIMD wildcopy for literal and match memcpy #68 is done).
• Recomputed remaining estimates: Phase 4 from ~13d 8h to ~10d 8h, total from ~34d 16h to ~31d 16h.
• Kept perf(encoding): eliminate default-level small-input dfast reset/table clear cliff #88 in Phase 4 as the encoding default small-input latency-cliff fix.

Also closed issue #68 explicitly (PR #85 did not auto-close it because it lacked a closing keyword).

[polaz]

Roadmap actualization (2026-04-09):

• Marked ✅ perf(decoding): branchless offset history, stride prefetch, BMI2 pext #69 as completed (merged via PR perf(decoding): branchless offset history, prefetch pipeline, and BMI2 triple extract #90 on 2026-04-09).
• Updated Phase 4 critical path: next highest-impact item is now perf(decoding): SIMD HUF decode kernels with runtime CPU dispatch #66.
• Refreshed parallelization notes (removed perf(decoding): branchless offset history, stride prefetch, BMI2 pext #69 from open parallel set).
• Updated dependency graph to show ✅perf(decoding): branchless offset history, stride prefetch, BMI2 pext #69.
• Reordered "next actions" list (now starts with perf(decoding): SIMD HUF decode kernels with runtime CPU dispatch #66, perf(encoding): eliminate default-level small-input dfast reset/table clear cliff #88, perf(encoding): SIMD match-length comparison (SSE4.2/AVX2/NEON) #70).
• Recalculated estimates after perf(decoding): branchless offset history, stride prefetch, BMI2 pext #69 completion:
  • Phase 4 remaining: ~9d 4h (was ~10d 8h)
  • Total remaining: ~30d 12h (~31 working days) (was ~31d 16h).

[polaz]

ROADMAP actualized after merge of #66.

Updated in issue body:

• Marked ✅ perf(decoding): SIMD HUF decode kernels with runtime CPU dispatch #66 in Phase 4 table and dependency graph.
• Updated critical path and parallelization notes (next: perf(encoding): eliminate default-level small-input dfast reset/table clear cliff #88, perf(encoding): SIMD match-length comparison (SSE4.2/AVX2/NEON) #70, perf: ARM platform optimizations (CRC32 hash, NEON copy, SVE2 histcnt) #71, perf(decoding): pre-parsed dictionary handle for repeated dict decode #86).
• Reordered recommended next actions (removed closed perf(decoding): SIMD HUF decode kernels with runtime CPU dispatch #66).
• Recalculated estimates: Phase 4 remaining from ~9d 4h to ~5d 4h; total remaining from ~30d 12h to ~26d 12h.