A compressed block (block type 2, see blocks) is a literals section followed by a sequences section. The literals are the bytes not found in earlier data; each sequence says how many literals to copy, then how long a match to copy and from how far back. This page summarises RFC 8878, section 3.1.1.3.
Literals section
The header’s first byte: bits 0 and 1 are Literals_Block_Type, bits 2
and 3 Size_Format; the sizes follow in the remaining bits, little-endian.
| Type | Name | Content |
|---|---|---|
0 | Raw | The literals as they are. |
1 | RLE | One byte, repeated Regenerated_Size times. |
2 | Compressed | A Huffman tree description, then 1 or 4 Huffman-coded streams. |
3 | Treeless | Huffman-coded streams that reuse the previous block’s tree. |
| Types | Size_Format | Header | Sizes |
|---|---|---|---|
| Raw, RLE | 00 or 10 (1 bit) | 1 byte | Regenerated size: 5 bits |
| Raw, RLE | 01 | 2 bytes | Regenerated size: 12 bits |
| Raw, RLE | 11 | 3 bytes | Regenerated size: 20 bits |
| Compressed, Treeless | 00 | 3 bytes | 1 stream; regenerated and compressed sizes 10 bits each |
| Compressed, Treeless | 01 | 3 bytes | 4 streams; 10 bits each |
| Compressed, Treeless | 10 | 4 bytes | 4 streams; 14 bits each |
| Compressed, Treeless | 11 | 5 bytes | 4 streams; 18 bits each |
The compressed size includes the tree description. With four streams, a 6-byte jump
table (three 2-byte sizes of streams 1 to 3) comes first; stream 4 takes the rest.
Each of the first three streams decodes to (Regenerated_Size + 3) / 4
bytes, and the fourth to what remains.
Huffman tree description
The tree is sent as a weight for each symbol from 0 up; the last symbol’s weight is
not sent but worked out so that the weights add up to a power of two. A weight
w > 0 means a code of Max_Number_of_Bits + 1 − w bits; 0
means the byte does not occur. Codes are at most 11 bits.
- Header byte below 128: it is the size of FSE-compressed weights that follow (two interleaved FSE states, accuracy log up to 6).
- Header byte 128 or more:
header − 127weights follow directly, 4 bits each, two to a byte, high nibble first.
Huffman streams are read backwards, from the end, starting after the last set bit of the final byte (a padding marker).
Sequences section
| Field | Description |
|---|---|
Number_of_Sequences | First byte b0: 0 means no sequences, and the section ends here; below 128, b0; below 255, ((b0 − 128) << 8) + b1; 255, b1 + (b2 << 8) + 7F00. |
Symbol_Compression_Modes | One byte: bits 7–6 literal lengths mode, 5–4 offsets mode, 3–2 match lengths mode, 1–0 reserved (0). |
| Tables | For each of the three, in that order, what its mode needs. |
| Bitstream | The sequences, read backwards like the Huffman streams. |
| Mode | Name | Table |
|---|---|---|
0 | Predefined_Mode | The default distribution; nothing stored. |
1 | RLE_Mode | One byte: the only code used. |
2 | FSE_Compressed_Mode | An FSE table description: 4 bits accuracy log − 5, then the normalised counts. |
3 | Repeat_Mode | Reuse the table from the previous block. |
Decoding: read the initial states for literal lengths, offsets and match lengths; then for each sequence read the offset, match length and literal length extra bits, and update the states in the order literal lengths, match lengths, offsets (except after the last sequence). The highest accuracy logs allowed are 9 for literal and match lengths and 8 for offsets.
Literal length codes
Codes 0 to 15 are the length itself, with no extra bits. Above that, length = baseline + the extra bits:
| Code | Baseline | Extra bits | Code | Baseline | Extra bits |
|---|---|---|---|---|---|
| 16 | 16 | 1 | 26 | 128 | 7 |
| 17 | 18 | 1 | 27 | 256 | 8 |
| 18 | 20 | 1 | 28 | 512 | 9 |
| 19 | 22 | 1 | 29 | 1024 | 10 |
| 20 | 24 | 2 | 30 | 2048 | 11 |
| 21 | 28 | 2 | 31 | 4096 | 12 |
| 22 | 32 | 3 | 32 | 8192 | 13 |
| 23 | 40 | 3 | 33 | 16384 | 14 |
| 24 | 48 | 4 | 34 | 32768 | 15 |
| 25 | 64 | 6 | 35 | 65536 | 16 |
Match length codes
Codes 0 to 31 mean lengths 3 to 34, with no extra bits. Above that:
| Code | Baseline | Extra bits | Code | Baseline | Extra bits |
|---|---|---|---|---|---|
| 32 | 35 | 1 | 43 | 131 | 7 |
| 33 | 37 | 1 | 44 | 259 | 8 |
| 34 | 39 | 1 | 45 | 515 | 9 |
| 35 | 41 | 1 | 46 | 1027 | 10 |
| 36 | 43 | 2 | 47 | 2051 | 11 |
| 37 | 47 | 2 | 48 | 4099 | 12 |
| 38 | 51 | 3 | 49 | 8195 | 13 |
| 39 | 59 | 3 | 50 | 16387 | 14 |
| 40 | 67 | 4 | 51 | 32771 | 15 |
| 41 | 83 | 4 | 52 | 65539 | 16 |
| 42 | 99 | 5 |
Offset codes and repeat offsets
Offset code N gives Offset_Value = (1 << N) + N
extra bits. Decoders must accept codes up to 31; values above 3 are a new offset of
Offset_Value − 3. Values 1 to 3 pick a repeat offset:
| Offset_Value | Literal length > 0 | Literal length = 0 |
|---|---|---|
| 1 | Repeat offset 1 | Repeat offset 2 |
| 2 | Repeat offset 2 | Repeat offset 3 |
| 3 | Repeat offset 3 | Repeat offset 1 − 1 |
The three repeat offsets start as 1, 4 and 8 in each frame (or come from the dictionary), and are updated like a most-recently-used list after each sequence.
Default distributions
Normalised counts used by Predefined_Mode, where −1 marks a “less than 1” probability:
- Literal lengths, accuracy log 6: 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 lengths, accuracy log 6: 1, 4, 3, 2, 2, 2, 2, 2, 2, then 37 ones, then seven −1.
- Offsets, accuracy log 5: 1, 1, 1, 1, 1, 1, 2, 2, 2, then 15 ones, then five −1.