Sequences Section

A compressed block is a succession of sequences . A sequence is a literal copy command, followed by a match copy command. A literal copy command specifies a length. It is the number of bytes to be copied (or extracted) from the Literals Section. A match copy command specifies an offset and a length.

When all sequences are decoded, if there are literals left in the literals section, these bytes are added at the end of the block.

This is described in more detail in Sequence Execution.

The Sequences_Section regroup all symbols required to decode commands. There are 3 symbol types : literals lengths, offsets and match lengths. They are encoded together, interleaved, in a single bitstream.

The Sequences_Section starts by a header, followed by optional probability tables for each symbol type, followed by the bitstream.

To decode the Sequences_Section, it’s required to know its size. Its size is deduced from the size of Literals_Section: Sequences_Section_Size = Block_Size - Literals_Section_Size.

Sequences_Section_Header

Consists of 2 items:

• Number_of_Sequences
• Symbol compression modes

Number_of_Sequences

This is a variable size field using between 1 and 3 bytes. Let’s call its first byte byte0.

• if (byte0 < 128) : Number_of_Sequences = byte0 . Uses 1 byte.
• if (byte0 < 255) : Number_of_Sequences = ((byte0 - 0x80) << 8) + byte1. Uses 2 bytes. Note that the 2 bytes format fully overlaps the 1 byte format.
• if (byte0 == 255): Number_of_Sequences = byte1 + (byte2<<8) + 0x7F00. Uses 3 bytes.

if (Number_of_Sequences == 0) : there are no sequences. The sequence section stops immediately, FSE tables used in Repeat_Mode aren’t updated. Block’s decompressed content is defined solely by the Literals Section content.

Symbol compression modes

This is a single byte, defining the compression mode of each symbol type.

The last field, Reserved, must be all-zeroes.

Literals_Lengths_Mode, Offsets_Mode and Match_Lengths_Mode define the Compression_Mode of literals lengths, offsets, and match lengths symbols respectively.

They follow the same enumeration :

• Predefined_Mode : A predefined FSE distribution table is used, defined in default distributions. No distribution table will be present.
• RLE_Mode : The table description consists of a single byte, which contains the symbol’s value. This symbol will be used for all sequences.
• FSE_Compressed_Mode : standard FSE compression. A distribution table will be present. The format of this distribution table is described in FSE Table Description. Note that the maximum allowed accuracy log for literals length and match length tables is 9, and the maximum accuracy log for the offsets table is 8. FSE_Compressed_Mode must not be used when only one symbol is present, RLE_Mode should be used instead (although any other mode will work).
• Repeat_Mode : The table used in the previous Compressed_Block with Number_of_Sequences > 0 will be used again, or if this is the first block, table in the dictionary will be used. Note that this includes RLE_mode, so if Repeat_Mode follows RLE_Mode, the same symbol will be repeated. It also includes Predefined_Mode, in which case Repeat_Mode will have same outcome as Predefined_Mode. No distribution table will be present. If this mode is used without any previous sequence table in the frame (nor dictionary) to repeat, this should be treated as corruption.

The codes for literals lengths, match lengths, and offsets.

Each symbol is a code in its own context, which specifies Baseline and Number_of_Bits to add. Codes are FSE compressed, and interleaved with raw additional bits in the same bitstream.

Literals length codes

Literals length codes are values ranging from 0 to 35 included. They define lengths from 0 to 131071 bytes. The literals length is equal to the decoded Baseline plus the result of reading Number_of_Bits bits from the bitstream, as a little-endian value.

Match length codes

Match length codes are values ranging from 0 to 52 included. They define lengths from 3 to 131074 bytes. The match length is equal to the decoded Baseline plus the result of reading Number_of_Bits bits from the bitstream, as a little-endian value.

Offset codes

Offset codes are values ranging from 0 to N.

A decoder is free to limit its maximum N supported. Recommendation is to support at least up to 22. For information, at the time of this writing. the reference decoder supports a maximum N value of 31.

An offset code is also the number of additional bits to read in little-endian fashion, and can be translated into an Offset_Value using the following formulas :

Offset_Value = (1 << offsetCode) + readNBits(offsetCode);
if (Offset_Value > 3) offset = Offset_Value - 3;

It means that maximum Offset_Value is (2^(N+1))-1 supporting back-reference distances up to (2^(N+1))-4, but is limited by maximum back-reference distance.

Offset_Value from 1 to 3 are special : they define “repeat codes”. This is described in more detail in Repeat Offsets.

Decoding Sequences

FSE bitstreams are read in reverse direction than written. In zstd, the compressor writes bits forward into a block and the decompressor must read the bitstream backwards.

To find the start of the bitstream it is therefore necessary to know the offset of the last byte of the block which can be found by counting Block_Size bytes after the block header.

After writing the last bit containing information, the compressor writes a single 1-bit and then fills the byte with 0-7 0 bits of padding. The last byte of the compressed bitstream cannot be 0 for that reason.

When decompressing, the last byte containing the padding is the first byte to read. The decompressor needs to skip 0-7 initial 0-bits and the first 1-bit it occurs. Afterwards, the useful part of the bitstream begins.

FSE decoding requires a ‘state’ to be carried from symbol to symbol. For more explanation on FSE decoding, see the FSE section.

For sequence decoding, a separate state keeps track of each literal lengths, offsets, and match lengths symbols. Some FSE primitives are also used. For more details on the operation of these primitives, see the FSE section.

Starting states

The bitstream starts with initial FSE state values, each using the required number of bits in their respective accuracy, decoded previously from their normalized distribution.

It starts by Literals_Length_State, followed by Offset_State, and finally Match_Length_State.

Reminder : always keep in mind that all values are read backward, so the ‘start’ of the bitstream is at the highest position in memory, immediately before the last 1-bit for padding.

After decoding the starting states, a single sequence is decoded Number_Of_Sequences times. These sequences are decoded in order from first to last. Since the compressor writes the bitstream in the forward direction, this means the compressor must encode the sequences starting with the last one and ending with the first.

Decoding a sequence

For each of the symbol types, the FSE state can be used to determine the appropriate code. The code then defines the Baseline and Number_of_Bits to read for each type. See the description of the codes for how to determine these values.

Decoding starts by reading the Number_of_Bits required to decode Offset. It then does the same for Match_Length, and then for Literals_Length. This sequence is then used for sequence execution.

If it is not the last sequence in the block, the next operation is to update states. Using the rules pre-calculated in the decoding tables, Literals_Length_State is updated, followed by Match_Length_State, and then Offset_State. See the FSE section for details on how to update states from the bitstream.

This operation will be repeated Number_of_Sequences times. At the end, the bitstream shall be entirely consumed, otherwise the bitstream is considered corrupted.

Default Distributions

If Predefined_Mode is selected for a symbol type, its FSE decoding table is generated from a predefined distribution table defined here. For details on how to convert this distribution into a decoding table, see the FSE section.

Literals Length

The decoding table uses an accuracy log of 6 bits (64 states).

short literalsLength_defaultDistribution[36] =
        { 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
          2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
         -1,-1,-1,-1 };

Match Length

The decoding table uses an accuracy log of 6 bits (64 states).

short matchLengths_defaultDistribution[53] =
        { 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
          1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
          1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,
         -1,-1,-1,-1,-1 };

Offset Codes

The decoding table uses an accuracy log of 5 bits (32 states), and supports a maximum N value of 28, allowing offset values up to 536,870,908 .

If any sequence in the compressed block requires a larger offset than this, it’s not possible to use the default distribution to represent it.

short offsetCodes_defaultDistribution[29] =
        { 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
          1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1 };

Sequence Execution

Once literals and sequences have been decoded, they are combined to produce the decoded content of a block.

Each sequence consists of a tuple of (literals_length, offset_value, match_length), decoded as described in the Sequences Section. To execute a sequence, first copy literals_length bytes from the decoded literals to the output.

Then match_length bytes are copied from previous decoded data. The offset to copy from is determined by offset_value: if offset_value > 3, then the offset is offset_value - 3. If offset_value is from 1-3, the offset is a special repeat offset value. See the repeat offset section for how the offset is determined in this case.

The offset is defined as from the current position, so an offset of 6 and a match length of 3 means that 3 bytes should be copied from 6 bytes back. Note that all offsets leading to previously decoded data must be smaller than Window_Size defined in Frame_Header_Descriptor.

Repeat offsets

As seen in Sequence Execution, the first 3 values define a repeated offset and we will call them Repeated_Offset1, Repeated_Offset2, and Repeated_Offset3. They are sorted in recency order, with Repeated_Offset1 meaning “most recent one”.

If offset_value == 1, then the offset used is Repeated_Offset1, etc.

There is an exception though, when current sequence’s literals_length = 0. In this case, repeated offsets are shifted by one, so an offset_value of 1 means Repeated_Offset2, an offset_value of 2 means Repeated_Offset3, and an offset_value of 3 means Repeated_Offset1 - 1.

In the final case, if Repeated_Offset1 - 1 evaluates to 0, then the data is considered corrupted.

For the first block, the starting offset history is populated with following values : Repeated_Offset1=1, Repeated_Offset2=4, Repeated_Offset3=8, unless a dictionary is used, in which case they come from the dictionary.

Then each block gets its starting offset history from the ending values of the most recent Compressed_Block. Note that blocks which are not Compressed_Block are skipped, they do not contribute to offset history.

Offset updates rules

During the execution of the sequences of a Compressed_Block, the Repeated_Offsets’ values are kept up to date, so that they always represent the three most-recently used offsets. In order to achieve that, they are updated after executing each sequence in the following way:

When the sequence’s offset_value does not refer to one of the Repeated_Offsets—when it has value greater than 3, or when it has value 3 and the sequence’s literals_length is zero—the Repeated_Offsets’ values are shifted back one, and Repeated_Offset1 takes on the value of the just-used offset.

Otherwise, when the sequence’s offset_value refers to one of the Repeated_Offsets—when it has value 1 or 2, or when it has value 3 and the sequence’s literals_length is non-zero—the Repeated_Offsets are re-ordered so that Repeated_Offset1 takes on the value of the used Repeated_Offset, and the existing values are pushed back from the first Repeated_Offset through to the Repeated_Offset selected by the offset_value. This effectively performs a single-stepped wrapping rotation of the values of these offsets, so that their order again reflects the recency of their use.

The following table shows the values of the Repeated_Offsets as a series of sequences are applied to them: