Module sequences 

Sequences that come into the encoder from outside, or go out of it: a parse of the input into literal runs and matches, laid out as the C ZSTD_Sequence so the C entry points pass caller arrays straight through.

• SequenceReplay is a Matcher that searches nothing and reports a given parse instead, so a frame is built from it by the ordinary block pipeline (C ZSTD_compressSequences).
• SequenceProducer is a parser asked for each block in place of the built-in match finder (C ZSTD_registerSequenceProducer).
• FrameCompressor::set_sequence_capture records the parse the built-in match finder chose (C ZSTD_generateSequences).

Structs

ExternalSequence

One sequence of a parse: lit_len literal bytes, then match_len bytes copied from offset bytes back. A sequence with offset == 0 and match_len == 0 carries only literals and ends a block (a block delimiter). Laid out as the C ZSTD_Sequence.

RebuiltSource

The input a parse decodes to, rebuilt from its literals as it is read, as a decoder would (C ZSTD_compressSequencesAndLiterals takes the literals rather than the input). Matches reaching before the start read from dict; literals past the last sequence are the trailing ones. Only the last window bytes are held for the matches to copy from (more only while a match reaching further, into the dictionary, is being copied), so a frame is built from it without the whole input in memory.

SequenceProducerError

Why a SequenceProducer gave no parse for a block.

SequenceReplay

A Matcher that reports a given parse instead of searching, so the ordinary block pipeline builds a frame from it (C ZSTD_compressSequences). The parse is consumed as blocks are cut: wherever the encoder ends a block, a sequence running across the cut is split there, and a match piece shorter than MIN_MATCH goes out as literals. Block delimiters, if any, end blocks: each delimited region is a block of its own, cut further only where it exceeds the block size.

Enums

SequenceError

Why a parse cannot build a valid frame.

Constants

MIN_MATCH

The shortest match a sequence can carry (RFC 8878 3.1.1.3.2.1.1: match length codes start at 3).

Traits

SequenceProducer

A parser asked for each block in place of the built-in match finder (C ZSTD_registerSequenceProducer). Its parse covers the block alone, with no history before it.

Functions

merge_block_delimiters

Remove every block delimiter from sequences, handing its literals to the sequence after it, and return how many sequences remain at the front (C ZSTD_mergeBlockDelimiters). A final delimiter’s literals become the parse’s trailing literals, which no sequence carries.

parse_reproduces

Check that sequences decodes to src: every match copies the bytes the input holds where it lands, out of src itself or, reaching before the start, out of the tail of dict. A parse that validate_parse accepts can still describe different bytes; compressing it would make a frame that decodes to them, not to src.

producer_parse_heap_bytes

Heap bytes a compressor keeps for a SequenceProducer’s parse of blocks up to block_size bytes: room for sequence_bound sequences, as many as a parse it can use holds, kept from block to block (upstream reserves the same for its external sequences, zstd_compress.c:2236-2239).

sequence_bound

Upper bound on the sequences a parse of src_size bytes can hold, block delimiters included (C ZSTD_sequenceBound): one per minimal match, and one delimiter per smallest block.

validate_parse

Check that sequences is a parse of src_len bytes a decoder can follow: every match at least MIN_MATCH bytes (literals with no match are a delimiter, offset 0), every offset within what is decoded so far plus dict_len bytes of dictionary while that fits the window, and within window after. With explicit_delimiters the parse must cover the input exactly and each delimited block hold at most max_block bytes; without, bytes past the parse are trailing literals.