--- title: "Zstandard decoder: behavior" url: https://recursiveai.org/onearchive/docs/zstd-decoder/ description: "Normative notes for RecursiveAI.OneCompress.Zstd's decoder. The format itself is RFC 8878; this page records what the format leaves to the decoder and the…" version: "0.7.0-preview.1" source: https://github.com/recursive-ai-oss/onearchive-csharp/blob/3fa11f22dbe4e13c90ae9c63f393e945a0c09bba/docs/zstd-decoder.md --- # Zstandard decoder: behavior Normative notes for `RecursiveAI.OneCompress.Zstd`'s decoder. The format itself is RFC 8878; this page records what the format leaves to the decoder and the choices made, so another implementation can match them. ## What is decoded - Zstandard frames (RFC 8878 §3.1.1) and skippable frames (§3.1.2), one after another. Skippable frames are handed to `ZstdDecompressionOptions.SkippableFrameHandler` (variant = low four bits of the magic number, payload as a span). Without a handler they are skipped without being read into memory. - Raw, RLE and compressed blocks; raw, RLE, compressed (one and four streams) and treeless literals; predefined, RLE, FSE-compressed and repeat sequence tables; Huffman weights stored directly or FSE-compressed; repeat offsets with the literals-length-zero rule. - Window descriptors and single-segment frames; the content size field in all four widths; the dictionary ID field; the content checksum (low 32 bits of XXH64, seed 0), verified unless `VerifyChecksum` is false. - Dictionaries in the Zstandard dictionary format (entropy tables and repeat offsets, content) and raw-content dictionaries. ## Choices the format leaves open | Matter | Choice | |---|---| | Maximum window | `MaxWindowSize`, default 8 MiB. A larger declared window raises `CompressionLimitException` before any buffer is reserved. For single-segment frames the window is the content size. | | Maximum output | `MaxOutputSize`, default 1 GiB, counted across frames since the last `Reset`. A frame whose declared content size exceeds what remains is refused up front; for other frames the count is checked as blocks are produced. | | Memory of a streaming decoder | The decoder keeps a window of up to `2 x window size` (the history plus one block), grown in steps as output appears, never reserved up front from the header. Frames above 1 GiB of window therefore need `Array.MaxLength / 2`; they raise a limit exception rather than a framework `OutOfMemoryException`. A caller that gives a buffer large enough for a whole frame whose size is declared bypasses the window entirely: the output buffer is the history. | | Declared size on one-shot calls | `Zstd.Decompress` allocates the declared size only when it is at most `1 MiB + 255 x input length`; otherwise it starts small and grows, so a tiny input cannot make it reserve the whole limit. | | Content size mismatch | A frame that decodes to a different size than it declares is corrupt. | | Block sizes | A block (content and decoded size) larger than `min(window size, 128 KiB)` is corrupt. | | Offsets | A match offset must be at most the window size and at most the bytes produced so far in the frame plus the dictionary content; the dictionary is reachable only while the frame's output is within its window (RFC 8878 §5). Offset codes above 31 are rejected. | | FSE table descriptions | Accuracy log at most 9 (literals and match lengths), 8 (offsets), 6 (Huffman weights). A description that does not complete its probabilities, or names symbols beyond the table's alphabet, is corrupt. A table of a single symbol is accepted in FSE-compressed mode. | | Huffman | Weights up to 11; the implied last weight must complete a power of two with at least one weight-1 symbol; the code depth is at most 11. A stream that does not end exactly at its first bit is corrupt. A four-stream block with fewer than four literals whose last stream would be negative is corrupt. | | Sequence section | A sequence count of zero must end the block; reserved mode bits must be zero; the sequence bitstream must be consumed exactly. | | Dictionary selection | A frame naming an ID is matched against `Dictionaries`, then `Dictionary` (a raw-content dictionary with ID 0 matches any ID). A frame naming no ID uses `Dictionary`. A frame naming an unknown ID raises `CompressionDictionaryException`. | | Dictionary validation | Formatted dictionaries: magic, ID, tables, three repeat offsets (each at least 1 and at most the content size), content. Raw content: at least 8 bytes. | | Empty input | Decoding zero bytes is an error (a stream needs at least one frame); it raises a truncated `CompressionFormatException`. | | Trailing bytes | Anything after a frame must be another frame or a skippable frame; otherwise the magic number is reported as wrong. | | Skippable payloads | Buffered only when a handler is set, up to `MaxSkippableFrameSize` (default 1 MiB). | ## Streaming `ZstdDecoder.Decompress(source, destination, out consumed, out written)` accepts any split of input and output. It returns `Done` at the end of each frame (and each skippable frame), `DestinationTooSmall` when output is pending, and `NeedMoreData` when it used all input mid-frame. Compressed blocks (at most 128 KiB) are decoded only once complete, from the caller's span when it already holds the whole block and from a reused internal buffer otherwise. Raw and RLE blocks stream through. ## Hot-path safety The decoder is written on spans. Nothing in `src/` uses `Unsafe` or `MemoryMarshal` unless this page lists it. `src/OneCompress/Zstd/Raw.cs` is the only file that skips bounds checks: `Get`, `Ref`, `ReadUInt64`, `Copy16`, `Copy8` and `Set`. Each states the bound its caller guarantees (a table index below the table's size, a copy inside a buffer that was checked or kept 32 bytes short of its end). With the `Checked` configuration every one of them is an ordinary checked access, and the tests and the fuzzer run that way. ## Sequence loop Blocks with fewer than 4 sequences run the plain loop over the tier-3 sequence decoder, because setting up the fast loops costs more than they save. Blocks with 4 to 63 sequences (the size of game payloads) run `RunSmall`, one function that also handles the last sequence and the stream's start. Larger blocks run `RunFast`, with a second instance that stops its refill short of the stream's start so that only the last sequence needs the careful path. - The three FSE tables' rows are expanded when the block's tables are known (`FseDecodingTable.FillSequenceEntries`) and stored in one array, so a state indexes it directly. A row is one 64-bit value: next-state baseline (16 bits), total bits (8), state bits (8), extra bits (8) and the baseline value (24). - Each sequence reads the bitstream once into a 64-bit register and cuts the six fields from it with the bit counts held in the rows; sequences that need more than 56 bits take a slower read. - Literals are copied with 16-byte moves. The literals buffer keeps 32 bytes of slack for that, and raw literals up to 4096 bytes are copied into it. - Matches with an offset of 8 or more copy 8 or 16 bytes at a time; offsets below 8 use a pattern fill; matches that reach into a dictionary are copied inline when 32 bytes of dictionary follow the match, otherwise by the careful path. - Corrupt data, a copy that would pass the safe end of the output buffer and anything else unusual goes to `RunGeneral`, which checks every bound and is the only code that raises errors. ## Literals The four-stream Huffman loop keeps one register per stream with a marker bit above the data, so the bits used come from a trailing-zero count, and it refills in batches sized for the worst case. A single-stream section of 32 or more literals that uses a dictionary's table decodes two symbols per lookup from a pair table built on first use (published with an `Interlocked` exchange; the dictionary is shared between threads and the table is never changed after it is published). ## Speed Bar rows are in `docs/zstd-decoder-bench.md` (method: memory to memory, warm, best of the pass, against `zstd -b -e` on the same frames; `tools/zstd-decode-bench/run.sh` and `game.sh`). With the `Checked` configuration the decoder is about 27% slower than with the unchecked accessors (silesia.tar, level 3 frames, x64: 1787 against 1315 MB/s).