RFC 8878
Zstandard Compression and the 'application/zstd' Media Type
RFC 8878: Zstandard Compression and the 'application/zstd' Media Type 💖
okay bestie, this one is the Zstandard spec, the compression format behind all the zstd stuff you've seen everywhere ✨ It was written by Y. Collet and M. Kucherawy (Ed.), both at Facebook, and published in February 2021 as an Informational document under ISSN 2070-1721 🌸. It's the IETF's official RFC 8878 and it obsoletes RFC 8478, so 8478 is replaced by this one 🧚. It's labelled Informational, which is important, and we'll get to why in a sec 👀
Abstract
Zstandard, or "zstd" (pronounced "zee standard"), is a lossless data compression mechanism 💜. This document explains how it works and registers a media type, a content encoding, and a structured syntax suffix that you use when you send zstd-compressed content over MIME 🎀.
Yes, the word "standard" is in the name, but this doc is NOT an Internet Standards Track spec 🙈. It's published just for information, so please don't read the name and assume it's an official standard 💅
Status of This Memo
This document is not an Internet Standards Track specification, it's published for informational purposes 🦋.
It's an IETF product 🌈. It represents the consensus of the IETF community, it got public review, and the Internet Engineering Steering Group (IESG) approved it for publication ✨. Not everything the IESG approves can become an Internet Standard, though. Check Section 2 of RFC 7841 for the details 💖.
For the current status, any errata, and how to send feedback, go to https://www.rfc-editor.org/info/rfc8878 🫶.
Copyright Notice
Copyright (c) 2021 IETF Trust and the persons identified as the document authors. All rights reserved 💅.
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info), as they were on the day it was published 📜. Read those carefully, because they spell out what you're allowed to do with this document 🙈. Any Code Components pulled out of this document must include the Simplified BSD License text described in Section 4.e of the Trust Legal Provisions, and they come with no warranty, just like the Simplified BSD License says 🔥.
Table of Contents
1. Introduction
2. Definitions
3. Compression Algorithm
3.1. Frames
3.1.1. Zstandard Frames
3.1.1.1. Frame Header
3.1.1.2. Blocks
3.1.1.3. Compressed Blocks
3.1.1.4. Sequence Execution
3.1.1.5. Repeat Offsets
3.1.2. Skippable Frames
4. Entropy Encoding
4.1. FSE
4.1.1. FSE Table Description
4.2. Huffman Coding
4.2.1. Huffman Tree Description
4.2.1.1. Huffman Tree Header
4.2.1.2. FSE Compression of Huffman Weights
4.2.1.3. Conversion from Weights to Huffman Prefix Codes
4.2.2. Huffman-Coded Streams
5. Dictionary Format
6. Use of Dictionaries
7. IANA Considerations
7.1. The 'application/zstd' Media Type
7.2. Content Encoding
7.3. Structured Syntax Suffix
7.4. Dictionaries
8. Security Considerations
9. References
9.1. Normative References
9.2. Informative References
Appendix A. Decoding Tables for Predefined Codes
A.1. Literals Length Code Table
A.2. Match Length Code Table
A.3. Offset Code Table
Appendix B. Changes since RFC 8478
Acknowledgments
Authors' Addresses1. Introduction ✨
Zstandard, or "zstd" (pronounced "zee standard"), is a data compression mechanism 🍓. It's kind of like gzip [RFC1952], so if you know gzip, you're already halfway there 💖.
Again, the "standard" in the name doesn't make it an Internet Standards Track spec 🙈. Readers should know this document is just being published for information 💅.
This document describes the Zstandard format 🎀. It also covers how to transport a Zstandard-compressed data object: it registers a media type, a content encoding, and a structured syntax suffix so you can label that content when it shows up in a payload 🦋.
2. Definitions 📚
Some terms used throughout this document get defined here so everyone's on the same page 🫶.
- uncompressed: Describes an arbitrary set of bytes in their original form, before any compression touches them 🌸.
- compressed: Describes the result of running a set of bytes through this mechanism. The original input has been compressed 💜.
- decompressed: Describes the result of running a set of bytes through the reverse of this mechanism. When that works, the decompressed payload and the uncompressed payload are indistinguishable 🔥.
- encode: The process of turning data from one form into another. That can include compression, or it can mean other translations done as part of this spec 🧚.
- decode: The reverse of "encode". It's the process of undoing a previous encoding to get the original content back 👑.
- frame: Content compressed by Zstandard gets transformed into a Zstandard frame. You can append multiple frames into a single file or stream 🌈. A frame is completely independent, it has a defined beginning and end, and it has a set of parameters that tells the decoder how to decompress it ✨.
- block: A frame holds one or more blocks 💖. Each block contains arbitrary content, which its header describes. Every block has a guaranteed maximum content size that depends on the frame parameters 🎀. Unlike frames, each block depends on the blocks before it for proper decoding 🦋. But each block can be decompressed without waiting for the next one, which is what makes streaming operations possible 💅.
- natural order: The sequence or ordering of objects or values that's typical for that type of object or value 🌸. For example, a set of unique integers is in "natural order" if, as you move from one element to the next, the value never goes down 🍓.
The naming convention for identifiers in the specification is Mixed_Case_With_Underscores 🫶. Identifiers inside square brackets mean that identifier is optional in the context it's shown in 💜.
3. Compression Algorithm 🔥
This section describes the Zstandard algorithm 💅.
The whole point of this document is to define a lossless compressed data format that's a) independent of CPU type, operating system, file system, and character set, and b) suitable for file compression and for pipe and streaming compression, using the Zstandard algorithm 🎀. The spec assumes you've got some basic programming background, at the level of bits and other primitive data representations 🧚.
The data can be produced or consumed even from an arbitrarily long, sequentially presented input stream, using only a bounded amount of intermediate storage that's decided in advance 🌈. That's why it works in data communications ✨. The format uses the Zstandard compression method, plus an optional xxHash-64 checksum method [XXHASH] for detecting data corruption 💖.
The data format in this spec doesn't try to allow random access to compressed data 🙈.
Unless something below says otherwise, a compliant compressor must produce data sets that conform to the specifications here 📜. It doesn't need to support every option, though 💅.
A compliant decompressor must be able to decompress at least one working set of parameters that conforms to the specifications here 👑. It may also ignore informative fields, like the checksum 🌸. Whenever it doesn't support a parameter defined in the compressed stream, it must produce an unambiguous error code and an associated error message that explains which parameter is unsupported 🚨.
This spec is for software implementers who compress data into the Zstandard format, decompress data from it, or both 🫶. The Zstandard format is supported by an open-source reference implementation, written in portable C, and it's available at [ZSTD] 🍓.
3.1. Frames 🎀
Zstandard compressed data is made up of one or more frames 💜. Each frame is independent and can be decompressed independently of the other frames 🦋. The decompressed content of multiple concatenated frames is the concatenation of each frame's decompressed content 🌈.
There are two frame formats defined for Zstandard: Zstandard frames and skippable frames 🧚. Zstandard frames hold compressed data, while skippable frames hold custom user metadata ✨.
3.1.1. Zstandard Frames 💖
A single Zstandard frame is structured like this 🔥:
+--------------------+------------+
| Magic_Number | 4 bytes |
+--------------------+------------+
| Frame_Header | 2-14 bytes |
+--------------------+------------+
| Data_Block | n bytes |
+--------------------+------------+
| [More Data_Blocks] | |
+--------------------+------------+
| [Content_Checksum] | 4 bytes |
+--------------------+------------+
Table 1: The Structure of a
Single Zstandard Frame- Magic_Number: 4 bytes, in little-endian format. Value:
0xFD2FB528🌸. - Frame_Header: 2 to 14 bytes, detailed in Section 3.1.1.1 🎀.
- Data_Block: Detailed in Section 3.1.1.2 🦋. This is where the data lives 💅.
- Content_Checksum: An optional 32-bit checksum, only present if Content_Checksum_Flag is set 🫶. The content checksum is the result of the XXH64() hash function [XXHASH] digesting the original (decoded) data as input, with a seed of zero 🧚. The low 4 bytes of the checksum are stored in little-endian format 🌈.
The magic number was picked to be unlikely at the start of an arbitrary file 👀. It avoids trivial patterns (0x00, 0xFF, repeated bytes, increasing bytes, and so on), it contains byte values outside the ASCII range, and it doesn't map into UTF-8 space 🙈. All of that cuts down the odds of it showing up at the top of a text file 💜.
3.1.1.1. Frame Header 🎀
The frame header has a variable size, from a minimum of 2 bytes up to a maximum of 14 bytes, depending on the optional parameters 🦋. The structure of Frame_Header looks like this 💖:
+-------------------------+-----------+
| Frame_Header_Descriptor | 1 byte |
+-------------------------+-----------+
| [Window_Descriptor] | 0-1 byte |
+-------------------------+-----------+
| [Dictionary_ID] | 0-4 bytes |
+-------------------------+-----------+
| [Frame_Content_Size] | 0-8 bytes |
+-------------------------+-----------+
Table 2: The Structure of Frame_Headerthe frame header is literally the cover letter for your data 🌈✨ honestly the way it's built so the optional bits only show up when you need them is so iconic 😭🫶
3.1.1.1.1. Frame_Header_Descriptor ✨
okay bestie, the very first byte of the header is called the Frame_Header_Descriptor 🦋 It tells you which of the other fields are actually there, and decoding this one byte is enough to figure out how big the Frame_Header is 💅
+============+=========================+
| Bit Number | Field Name |
+============+=========================+
| 7-6 | Frame_Content_Size_Flag |
+------------+-------------------------+
| 5 | Single_Segment_Flag |
+------------+-------------------------+
| 4 | (unused) |
+------------+-------------------------+
| 3 | (reserved) |
+------------+-------------------------+
| 2 | Content_Checksum_Flag |
+------------+-------------------------+
| 1-0 | Dictionary_ID_Flag |
+------------+-------------------------+
Table 3: The Frame_Header_DescriptorIn Table 3, bit 7 is the highest bit, while bit 0 is the lowest one 🎀
3.1.1.1.1.1. Frame_Content_Size_Flag 🌸
This is a 2-bit flag (equivalent to Frame_Header_Descriptor right-shifted 6 bits) that tells you whether Frame_Content_Size (the decompressed data size) is provided within the header. Frame_Content_Size_Flag gives you FCS_Field_Size, which is the number of bytes Frame_Content_Size takes up, according to Table 4 🧚
+-------------------------+--------+---+---+---+
| Frame_Content_Size_Flag | 0 | 1 | 2 | 3 |
+-------------------------+--------+---+---+---+
| FCS_Field_Size | 0 or 1 | 2 | 4 | 8 |
+-------------------------+--------+---+---+---+
Table 4: Frame_Content_Size_Flag Provides
FCS_Field_SizeWhen Frame_Content_Size_Flag is 0, FCS_Field_Size depends on Single_Segment_Flag: if Single_Segment_Flag is set, FCS_Field_Size is 1. Otherwise, FCS_Field_Size is 0, and Frame_Content_Size is not provided 🙈
3.1.1.1.1.2. Single_Segment_Flag 🦋
If this flag is set, data must be regenerated within a single continuous memory segment 🧠
In this case, the Window_Descriptor byte gets skipped, but Frame_Content_Size is necessarily present 💖 As a consequence, the decoder must allocate a memory segment of a size equal to or larger than Frame_Content_Size.
To protect the decoder from unreasonable memory requirements, a decoder is allowed to reject a compressed frame that requests a memory size beyond the decoder's authorized range 🛡️
For broader compatibility, decoders are recommended to support memory sizes of at least 8 MB. This is only a recommendation, though. Each decoder is free to support higher or lower limits, depending on local limitations ✨
3.1.1.1.1.3. Unused Bit 🫧
A decoder compliant with this specification version shall not interpret this bit. It might be used in a future version to signal a property that is not mandatory to properly decode the frame. An encoder compliant with this specification must set this bit to zero 🌈
3.1.1.1.1.4. Reserved Bit 🔒
This bit is reserved for some future feature. Its value must be zero. A decoder compliant with this specification version must ensure it is not set. This bit may be used in a future revision to signal a feature that must be interpreted to decode the frame correctly 👑
3.1.1.1.1.5. Content_Checksum_Flag ✅
If this flag is set, a 32-bit Content_Checksum will be present at the frame's end. See the description of Content_Checksum above 💜
3.1.1.1.1.6. Dictionary_ID_Flag 📖
This is a 2-bit flag (= Frame_Header_Descriptor & 0x3) indicating whether a dictionary ID is provided within the header. It also specifies the size of this field as DID_Field_Size 🍓
+--------------------+---+---+---+---+
| Dictionary_ID_Flag | 0 | 1 | 2 | 3 |
+--------------------+---+---+---+---+
| DID_Field_Size | 0 | 1 | 2 | 4 |
+--------------------+---+---+---+---+
Table 5: Dictionary_ID_Flag3.1.1.1.2. Window Descriptor 🪟
This provides guarantees about the minimum memory buffer required to decompress a frame. It's super important for decoders, since it tells them how much memory to allocate 💅
The Window_Descriptor byte is optional. When Single_Segment_Flag is set, Window_Descriptor is not present. In this case, Window_Size is Frame_Content_Size, which can be any value from 0 to 2^(64) - 1 bytes (16 ExaBytes) 😭
+------------+----------+----------+
| Bit Number | 7-3 | 2-0 |
+------------+----------+----------+
| Field Name | Exponent | Mantissa |
+------------+----------+----------+
Table 6: Window_DescriptorThe minimum memory buffer size is called Window_Size. It's described by the following formulas:
windowLog = 10 + Exponent;
windowBase = 1 << windowLog;
windowAdd = (windowBase / 8) * Mantissa;
Window_Size = windowBase + windowAdd;The minimum Window_Size is 1 KB. The maximum Window_Size is (1<<41) + 7*(1<<38) bytes, which is 3.75 TB 🌟
In general, larger Window_Size values tend to improve the compression ratio, but at the cost of increased memory usage 🧁
To properly decode compressed data, a decoder will need to allocate a buffer of at least Window_Size bytes.
In order to protect decoders from unreasonable memory requirements, a decoder is allowed to reject a compressed frame that requests a memory size beyond the decoder's authorized range 🛡️
For improved interoperability, it's recommended for decoders to support values of Window_Size up to 8 MB, and for encoders not to generate frames requiring a Window_Size larger than 8 MB. It's merely a recommendation though, and decoders are free to support higher or lower limits, depending on local limitations 🎀
3.1.1.1.3. Dictionary_ID 📚
This is a field of variable size that contains the ID of the dictionary required to properly decode the frame. This field is optional. When it's not present, it's up to the decoder to know which dictionary to use 🌷
The Dictionary_ID field size is provided by DID_Field_Size. DID_Field_Size is directly derived from the value of Dictionary_ID_Flag. One byte can represent an ID from 0-255, 2 bytes can represent an ID from 0-65535, and 4 bytes can represent an ID from 0-4294967295. The format is little-endian 🫶
It is permitted to represent a small ID (for example, 13) with a large 4-byte dictionary ID, even if it's less efficient 🙃
Within private environments, any dictionary ID can be used. However, for frames and dictionaries distributed in public space, Dictionary_ID must be attributed carefully. The following ranges are reserved for use only with dictionaries that have been registered with IANA (see Section 7.4):
low range: <= 32767high range: >= (1 << 31)
Any other value for Dictionary_ID can be used by private arrangement between participants 🤝
Any payload presented for decompression that references an unregistered reserved dictionary ID results in an error 🚨
3.1.1.1.4. Frame_Content_Size 📏
This is the original (uncompressed) size. This information is optional. Frame_Content_Size uses a variable number of bytes, provided by FCS_Field_Size. FCS_Field_Size is provided by the value of Frame_Content_Size_Flag. FCS_Field_Size can be equal to 0 (not present), 1, 2, 4, or 8 bytes 🍭
+================+================+
| FCS Field Size | Range |
+================+================+
| 0 | unknown |
+----------------+----------------+
| 1 | 0 - 255 |
+----------------+----------------+
| 2 | 256 - 65791 |
+----------------+----------------+
| 4 | 0 - 2^(32) - 1 |
+----------------+----------------+
| 8 | 0 - 2^(64) - 1 |
+----------------+----------------+
Table 7: Frame_Content_SizeFrame_Content_Size format is little-endian. When FCS_Field_Size is 1, 4, or 8 bytes, the value is read directly. When FCS_Field_Size is 2, the offset of 256 is added. It's allowed to represent a small size (for example, 18) using any compatible variant 🌸
3.1.1.2. Blocks 🧱
After Magic_Number and Frame_Header, there are some number of blocks. Each frame must have at least 1 block, but there is no upper limit on the number of blocks per frame ✨
The structure of a block is as follows:
+==============+===============+
| Block_Header | Block_Content |
+==============+===============+
| 3 bytes | n bytes |
+--------------+---------------+
Table 8: The Structure of a
BlockBlock_Header uses 3 bytes, written using little-endian convention. It contains three fields:
+============+============+============+
| Last_Block | Block_Type | Block_Size |
+============+============+============+
| bit 0 | bits 1-2 | bits 3-23 |
+------------+------------+------------+
Table 9: Block_Header3.1.1.2.1. Last_Block 🏁
The lowest bit (Last_Block) signals whether this block is the last one. The frame will end after this last block. It may be followed by an optional Content_Checksum (see Section 3.1.1) 🎀
3.1.1.2.2. Block_Type 🧩
The next 2 bits represent the Block_Type. There are four block types 🌈
+=======+==================+
| Value | Block_Type |
+=======+==================+
| 0 | Raw_Block |
+-------+------------------+
| 1 | RLE_Block |
+-------+------------------+
| 2 | Compressed_Block |
+-------+------------------+
| 3 | Reserved |
+-------+------------------+
Table 10: The Four Block
TypesRaw_Block: This is an uncompressed block.Block_ContentcontainsBlock_Sizebytes 🫧RLE_Block: This is a single byte, repeatedBlock_Sizetimes.Block_Contentconsists of a single byte. On the decompression side, this byte must be repeatedBlock_Sizetimes 🔁Compressed_Block: This is a compressed block as described in Section 3.1.1.3.Block_Sizeis the length ofBlock_Content, namely the compressed data. The decompressed size is not known, but its maximum possible value is guaranteed (see below) 🗜️Reserved: This is not a block. This value cannot be used with the current specification. If such a value is present, it is considered to be corrupt data, and a compliant decoder must reject it 🚫
3.1.1.2.3. Block_Size ✨
okay so the upper 21 bits of Block_Header are the Block_Size 💅
When Block_Type is Compressed_Block or Raw_Block, Block_Size is the size of Block_Content. The Block_Header itself is not counted in there 🧁
When Block_Type is RLE_Block, Block_Content is always just 1 byte, so Block_Size tells you how many times that byte must be repeated 🔁
And Block_Size is capped by Block_Maximum_Size (more on that below) 🙈
3.1.1.2.4. Block_Content and Block_Maximum_Size 🌸
The size of Block_Content is limited by Block_Maximum_Size, which is the smallest of:
Window_Size- 128 KB
Block_Maximum_Size stays the same for a whole frame, and it applies to both the decompressed size and the compressed size of every block in that frame 💖
Why the limit? It's giving planning 🧠 A decoder can read this info at the start of a frame and use it to allocate its buffers. The size guarantees mean those buffers will be big enough for any block that follows in a valid frame. Chef's kiss 👑
If the compressed block ends up bigger than the uncompressed one, sending the uncompressed block (a Raw_Block) is recommended instead. Don't be extra 😭
3.1.1.3. Compressed Blocks 🦋
To decompress a compressed block, you need its compressed size, and that comes from the Block_Size field inside Block_Header ✨
A compressed block has two sections: a Literals_Section (Section 3.1.1.3.1) and a Sequences_Section (Section 3.1.1.3.2). Their results get combined to make the decompressed data during Sequence Execution (Section 3.1.1.4). Teamwork makes the dream work 🫶
To decode a compressed block, you need these things:
- Previous decoded data, going back up to a distance of
Window_Size, or to the beginning of the Frame, whichever is smaller.Single_Segment_Flagwill be set in the latter case. - The list of "recent offsets" from the previous
Compressed_Block. - The previous Huffman tree, which is required by the
Treeless_Literals_Blocktype. - The previous Finite State Entropy (FSE) decoding tables, which are required by
Repeat_Mode, one for each symbol type (literals length codes, match length codes, offset codes) 📚
Now, decoding tables don't always come from the previous Compressed_Block, so keep an eye out:
- Every decoding table can come from a dictionary 📖
- The Huffman tree comes from the previous
Compressed_Literals_Block🌈
3.1.1.3.1. Literals_Section_Header 🎀
All the literals get regrouped into the first part of the block. They can be decoded first and then copied during Sequence Execution (see Section 3.1.1.4), or they can be decoded on the flow during Sequence Execution. Two options, both iconic 💅
Literals can be stored uncompressed, or compressed with Huffman prefix codes. When they're compressed, an optional tree description can show up, followed by 1 or 4 streams 🧚
+----------------------------+
| Literals_Section_Header |
+----------------------------+
| [Huffman_Tree_Description] |
+----------------------------+
| [Jump_Table] |
+----------------------------+
| Stream_1 |
+----------------------------+
| [Stream_2] |
+----------------------------+
| [Stream_3] |
+----------------------------+
| [Stream_4] |
+----------------------------+Table 11: Compressed Literals
3.1.1.3.1.1. Literals_Section_Header 🦄
This field describes how the literals are packed. It's a byte-aligned, variable-size bit field, anywhere from 1 to 5 bytes, using little-endian convention. Bit-packing is a whole vibe 🫠
+---------------------+-----------+
| Literals_Block_Type | 2 bits |
+---------------------+-----------+
| Size_Format | 1-2 bits |
+---------------------+-----------+
| Regenerated_Size | 5-20 bits |
+---------------------+-----------+
| [Compressed_Size] | 0-18 bits |
+---------------------+-----------+Table 12: Literals_Section_Header
In this representation, bits at the top are the lowest bits. Keep that in mind, it's a little plot twist 🙃
The Literals_Block_Type field uses the two lowest bits of the first byte, and it describes four different block types:
+===========================+=======+
| Literals_Block_Type | Value |
+===========================+=======+
| Raw_Literals_Block | 0 |
+---------------------------+-------+
| RLE_Literals_Block | 1 |
+---------------------------+-------+
| Compressed_Literals_Block | 2 |
+---------------------------+-------+
| Treeless_Literals_Block | 3 |
+---------------------------+-------+Table 13: Literals_Block_Type
Raw_Literals_Block: Literals are stored uncompressed.Literals_Section_ContentisRegenerated_Size. 🌷RLE_Literals_Block: Literals are a single-byte value repeatedRegenerated_Sizetimes.Literals_Section_Contentis 1. 🔁Compressed_Literals_Block: This is a standard Huffman-compressed block that starts with a Huffman tree description. See details below.Literals_Section_ContentisCompressed_Size. 🍓Treeless_Literals_Block: This is a Huffman-compressed block that uses the Huffman tree from the previousCompressed_Literals_Block, or from a dictionary if there's no previous Huffman-compressed literals block. TheHuffman_Tree_Descriptiongets skipped. Note that if this mode is triggered without any previous Huffman table in the frame (or dictionary, per Section 5), it should be treated as data corruption.Literals_Section_ContentisCompressed_Size. 🚨
The Size_Format splits into two families:
- For
Raw_Literals_BlockandRLE_Literals_Block, you only need to decodeRegenerated_Size. There's noCompressed_Sizefield. - For
Compressed_BlockandTreeless_Literals_Block, you're required to decode bothCompressed_SizeandRegenerated_Size(the decompressed size). You also need to decode the number of streams (1 or 4) 🧮
For values spanning several bytes, the convention is little endian 💜
Size_Format for Raw_Literals_Block and RLE_Literals_Block uses 1 or 2 bits. Its value is (Literals_Section_Header[0]>>2) & 0x3.
Size_Format == 00 or 10:Size_Formatuses 1 bit.Regenerated_Sizeuses 5 bits (value 0-31).Literals_Section_Headeruses 1 byte.Regenerated_Size = Literal_Section_Header[0]>>3.Size_Format == 01:Size_Formatuses 2 bits.Regenerated_Sizeuses 12 bits (values 0-4095).Literals_Section_Headeruses 2 bytes.Regenerated_Size = (Literals_Section_Header[0]>>4) + (Literals_Section_Header[1]<<4).Size_Format == 11:Size_Formatuses 2 bits.Regenerated_Sizeuses 20 bits (values 0-1048575).Literals_Section_Headeruses 3 bytes.Regenerated_Size = (Literals_Section_Header[0]>>4) + (Literals_Section_Header[1]<<4) + (Literals_Section_Header[2]<<12).
Only Stream_1 is present for these cases. It's totally permitted to write a short value (like 13) in a long format, even if that's less efficient. Extra space, no crime 🙈
Size_Format for Compressed_Literals_Block and Treeless_Literals_Block always uses 2 bits:
Size_Format == 00: A single stream. BothRegenerated_SizeandCompressed_Sizeuse 10 bits (values 0-1023).Literals_Section_Headeruses 3 bytes.Size_Format == 01: 4 streams. BothRegenerated_SizeandCompressed_Sizeuse 10 bits (values 0-1023).Literals_Section_Headeruses 3 bytes.Size_Format == 10: 4 streams. BothRegenerated_SizeandCompressed_Sizeuse 14 bits (values 0-16383).Literals_Section_Headeruses 4 bytes.Size_Format == 11: 4 streams. BothRegenerated_SizeandCompressed_Sizeuse 18 bits (values 0-262143).Literals_Section_Headeruses 5 bytes.
Both the Compressed_Size and Regenerated_Size fields follow little-endian convention. Note that Compressed_Size includes the size of the Huffman_Tree_Description when it's present 🌸
3.1.1.3.1.2. Raw_Literals_Block 🌊
The data in Stream_1 is Regenerated_Size bytes long. It holds the raw literals data that gets used during Sequence Execution (Section 3.1.1.3.2) ✨
3.1.1.3.1.3. RLE_Literals_Block 🍭
Stream_1 is a single byte that should be repeated Regenerated_Size times to generate the decoded literals. One byte, many copies, very efficient energy 🔥
3.1.1.3.1.4. Compressed_Literals_Block and Treeless_Literals_Block 🧠
Both of these modes contain Huffman-coded data. For Treeless_Literals_Block, the Huffman table comes from the previously compressed literals block, or from a dictionary. See Section 5 for the dictionary side of things 📖
3.1.1.3.1.5. Huffman_Tree_Description 🌳
This section is only present when the Literals_Block_Type is Compressed_Literals_Block (2). The format of Huffman_Tree_Description can be found in Section 4.2.1. Its size gets figured out during the decoding process, and it must be used to determine where the streams begin 🗺️
Total_Streams_Size = Compressed_Size
- Huffman_Tree_Description_Size3.1.1.3.1.6. Jump_Table 🦋
The Jump_Table is only present when there are 4 Huffman-coded streams.
(Reminder: Huffman-compressed data consists of either 1 or 4 Huffman-coded streams. Bestie, don't forget this one 💅)
If only 1 stream is present, it's a single bitstream that occupies the entire remaining portion of the literals block, encoded as described in Section 4.2.2 🌙
If there are 4 streams, Literals_Section_Header only tells you the decompressed and compressed sizes of all 4 streams combined. The decompressed size of each stream is equal to (Regenerated_Size+3)/4, except for the last stream, which may be up to 3 bytes smaller, so the total matches the decompressed size specified in Regenerated_Size 🧮
The compressed size of each stream is given explicitly in the Jump_Table. The Jump_Table is 6 bytes long and has three 2-byte little-endian fields, which describe the compressed sizes of the first 3 streams. Stream4_Size gets computed from Total_Streams_Size minus the sizes of the other streams:
Stream4_Size = Total_Streams_Size - 6
- Stream1_Size - Stream2_Size
- Stream3_SizeNote that ifStream1_Size + Stream2_Size + Stream3_SizeexceedsTotal_Streams_Size, the data are considered corrupted. Red flag 🚩
Each of these 4 bitstreams is then decoded independently as a Huffman-coded stream, as described in Section 4.2.2. Four little streams, each doing their own thing 🫶
3.1.1.3.2. Sequences_Section 🎀
okay bestie, so a compressed block is basically a whole line-up of sequences 💖. each sequence is a literal copy command followed by a match copy command. the literal copy command gives a length, which is how many bytes get copied (or extracted) from the Literals_Section. the match copy command gives an offset AND a length 🔥.
once all the sequences are decoded, if there are still literals left in the Literals_Section, those bytes get tacked onto the end of the block ✨.
we go deeper on this in Section 3.1.1.4 🧚
the Sequences_Section is basically the bag of everything needed to decode commands 👑. there are three symbol types: literals length codes, offset codes, and match length codes. they're all encoded together, interleaved, in ONE single "bitstream" 🌈
the section kicks off with a header, then optional probability tables for each symbol type, and then the bitstream:
Sequences_Section_Header
[Literals_Length_Table]
[Offset_Table]
[Match_Length_Table]
bitStreamto decode the Sequences_Section, you need to know its size 🙈. and the good news is it gets deduced from the size of the Literals_Section:
Sequences_Section_Size = Block_Size - Literals_Section_Header -
Literals_Section_Content.3.1.1.3.2.1. Sequences_Section_Header 🦋
this header has two items:
Number_of_SequencesSymbol_Compression_Modes
Number_of_Sequences is a variable size field, using anywhere from 1 to 3 bytes. look at byte0 to see how many bytes it's using 💅
if (byte0 == 0): there are no sequences. the sequence section stops right here. Decompressed content is defined entirely as Literals_Section content. The FSE tables used inRepeat_Modeare not updated.if (byte0 < 128):Number_of_Sequences = byte0. Uses 1 byte.if (byte0 < 255):Number_of_Sequences = ((byte0 - 128) << 8) + byte1. Uses 2 bytes.if (byte0 == 255):Number_of_Sequences = byte1 + (byte2 << 8) + 0x7F00. Uses 3 bytes.
Symbol_Compression_Modes is a single byte, and it defines the compression mode of each symbol type 🍓
+============+======================+
| Bit Number | Field Name |
+============+======================+
| 7-6 | Literal_Lengths_Mode |
+------------+----------------------+
| 5-4 | Offsets_Mode |
+------------+----------------------+
| 3-2 | Match_Lengths_Mode |
+------------+----------------------+
| 1-0 | Reserved |
+------------+----------------------+
Table 14: Symbol_Compression_Modesthe last field, Reserved, must be all zeroes. no sneaking anything in there 🙅♀️
Literals_Lengths_Mode, Offsets_Mode, and Match_Lengths_Mode define the Compression_Mode of literals length codes, offset codes, and match length codes, respectively. they all follow the same enumeration, so it's giving consistency 💜
+=======+=====================+
| Value | Compression_Mode |
+=======+=====================+
| 0 | Predefined_Mode |
+-------+---------------------+
| 1 | RLE_Mode |
+-------+---------------------+
| 2 | FSE_Compressed_Mode |
+-------+---------------------+
| 3 | Repeat_Mode |
+-------+---------------------+
Table 15:
Literals_Lengths_Mode,
Offsets_Mode, and
Match_Lengths_Modehere's what each mode means, babe 🫶
Predefined_Mode: a predefined FSE (see Section 4.1) distribution table is used, as defined in Section 3.1.1.3.2.2. 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, so a distribution table will be present. The format of this distribution table is described in Section 4.1.1. Note that the maximum allowed accuracy log for literals length code and match length code tables is 9, and the maximum accuracy log for the offset code table is 8. this 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, the 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 the same outcome as Predefined_Mode. No distribution table will be present. If this mode is used without any previous sequence table in the frame (or dictionary; see Section 5) to repeat, this should be treated as corruption. 💀
3.1.1.3.2.1.1. Sequence Codes for Lengths and Offsets 🎀
Okay so every symbol is a code in its own context, and that code tells you the Baseline and Number_of_Bits to add. The codes are FSE compressed and get interleaved with raw additional bits in the same bitstream 🧚
Literals length codes are values from 0 to 35, inclusive. They define lengths from 0 to 131071 bytes. The literals length is the decoded Baseline plus the result of reading Number_of_Bits bits from the bitstream, read as a little-endian value 💅
+======================+==========+================+
| Literals_Length_Code | Baseline | Number_of_Bits |
+======================+==========+================+
| 0-15 | length | 0 |
+----------------------+----------+----------------+
| 16 | 16 | 1 |
+----------------------+----------+----------------+
| 17 | 18 | 1 |
+----------------------+----------+----------------+
| 18 | 20 | 1 |
+----------------------+----------+----------------+
| 19 | 22 | 1 |
+----------------------+----------+----------------+
| 20 | 24 | 2 |
+----------------------+----------+----------------+
| 21 | 28 | 2 |
+----------------------+----------+----------------+
| 22 | 32 | 3 |
+----------------------+----------+----------------+
| 23 | 40 | 3 |
+----------------------+----------+----------------+
| 24 | 48 | 4 |
+----------------------+----------+----------------+
| 25 | 64 | 6 |
+----------------------+----------+----------------+
| 26 | 128 | 7 |
+----------------------+----------+----------------+
| 27 | 256 | 8 |
+----------------------+----------+----------------+
| 28 | 512 | 9 |
+----------------------+----------+----------------+
| 29 | 1024 | 10 |
+----------------------+----------+----------------+
| 30 | 2048 | 11 |
+----------------------+----------+----------------+
| 31 | 4096 | 12 |
+----------------------+----------+----------------+
| 32 | 8192 | 13 |
+----------------------+----------+----------------+
| 33 | 16384 | 14 |
+----------------------+----------+----------------+
| 34 | 32768 | 15 |
+----------------------+----------+----------------+
| 35 | 65536 | 16 |
+----------------------+----------+----------------+
Table 16: Literals Length CodesMatch length codes are values from 0 to 52, inclusive. They define lengths from 3 to 131074 bytes. The match length is the decoded Baseline plus the result of reading Number_of_Bits bits from the bitstream, again as a little-endian value 🦋
+===================+=======================+================+
| Match_Length_Code | Baseline | Number_of_Bits |
+===================+=======================+================+
| 0-31 | Match_Length_Code + 3 | 0 |
+-------------------+-----------------------+----------------+
| 32 | 35 | 1 |
+-------------------+-----------------------+----------------+
| 33 | 37 | 1 |
+-------------------+-----------------------+----------------+
| 34 | 39 | 1 |
+-------------------+-----------------------+----------------+
| 35 | 41 | 1 |
+-------------------+-----------------------+----------------+
| 36 | 43 | 2 |
+-------------------+-----------------------+----------------+
| 37 | 47 | 2 |
+-------------------+-----------------------+----------------+
| 38 | 51 | 3 |
+-------------------+-----------------------+----------------+
| 39 | 59 | 3 |
+-------------------+-----------------------+----------------+
| 40 | 67 | 4 |
+-------------------+-----------------------+----------------+
| 41 | 83 | 4 |
+-------------------+-----------------------+----------------+
| 42 | 99 | 5 |
+-------------------+-----------------------+----------------+
| 43 | 131 | 7 |
+-------------------+-----------------------+----------------+
| 44 | 259 | 8 |
+-------------------+-----------------------+----------------+
| 45 | 515 | 9 |
+-------------------+-----------------------+----------------+
| 46 | 1027 | 10 |
+-------------------+-----------------------+----------------+
| 47 | 2051 | 11 |
+-------------------+-----------------------+----------------+
| 48 | 4099 | 12 |
+-------------------+-----------------------+----------------+
| 49 | 8195 | 13 |
+-------------------+-----------------------+----------------+
| 50 | 16387 | 14 |
+-------------------+-----------------------+----------------+
| 51 | 32771 | 15 |
+-------------------+-----------------------+----------------+
| 52 | 65539 | 16 |
+-------------------+-----------------------+----------------+
Table 17: Match Length CodesOffset codes are values from 0 to N 🌸
A decoder is free to limit its maximum supported value for N. Support for values of at least 22 is recommended. At the time of writing, the reference decoder supports a maximum N value of 31. Ngl, the reference decoder going up to 31 is a whole flex 💪
An offset code is also the number of additional bits to read, in little-endian fashion, and it can be turned into an Offset_Value with these formulas:
Offset_Value = (1 << offsetCode) + readNBits(offsetCode);
if (Offset_Value > 3) Offset = Offset_Value - 3;So the maximum Offset_Value is (2^(N+1)) - 1, which supports a back-reference distance up to (2^(N+1)) - 4. It is still limited by the maximum back-reference distance (see Section 3.1.1.1.2) 🔥
Offset_Value from 1 to 3 is special, bestie! Those define "repeat codes". This is described in more detail in Section 3.1.1.5 ✨
3.1.1.3.2.1.2. Decoding Sequences 🧠
FSE bitstreams are read in the reverse of the direction they were written. In zstd, the compressor writes bits forward into a block, so the decompressor has to read the bitstream backwards. It's giving plot twist energy 😭
To find the start of the bitstream, you need to know the offset of the last byte of the block. You can find that by counting Block_Size bytes after the block header.
After writing the last bit that contains information, the compressor writes a single 1 bit and then fills the rest of the byte with zero bits. That's why the last byte of the compressed bitstream cannot be zero 🙈
When decompressing, the last byte containing the padding is the first byte to read. The decompressor needs to skip the up to 7 bits of 0-padding, as well as the first 1 bit that shows up. After that, 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 Section 4.1.
For sequence decoding, a separate state keeps track of each literals length, offset, and match length code. Some FSE primitives are also used. For more details on how these primitives operate, see Section 4.1.
The bitstream starts with initial FSE state values. Each one uses the required number of bits in its respective accuracy, and they were decoded earlier from their normalized distribution. It starts with Literals_Length_State, followed by Offset_State, and finally Match_Length_State 👑
Note that all values are read backward, so the 'start' of the bitstream is at the highest position in memory, right before the last 1 bit used 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, the compressor has to encode the sequences starting with the last one and ending with the first. Big brain move 🧚
For each of the symbol types, the FSE state can be used to figure out the right code. The code then defines the Baseline and Number_of_Bits to read for each type. You can find the description of how to work these values out in Section 3.1.1.3.2.1.
Decoding starts by reading the Number_of_Bits required to decode the offset. It does the same for Match_Length and then for Literals_Length. That sequence is then used for Sequence Execution (see Section 3.1.1.4) 💖
If it is not the last sequence in the block, the next operation is to update the states. Using the rules precalculated in the decoding tables, Literals_Length_State is updated first, followed by Match_Length_State, and then Offset_State. See Section 4.1 for details on how to update states from the bitstream.
This operation is repeated Number_of_Sequences times. At the end, the bitstream shall be entirely consumed. Otherwise, the bitstream is considered corrupted. No cap, that's a hard requirement 💀
3.1.1.3.2.2. 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 turn this distribution into a decoding table, see Section 4.1 🍓
3.1.1.3.2.2.1. Literals Length Codes 💜
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
};3.1.1.3.2.2.2. Match Length Codes ⭐
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
};3.1.1.3.2.2.3. Offset Codes ✨
okay so the decoding table here uses an accuracy log of 5 bits (32 states) 🧮 and it supports a max N value of 28, which means offset values can go all the way up to 536,870,908. that's a LOT of room 😭🫶
but here's the tea: if any sequence in the compressed block needs an offset bigger than that, the default distribution just can't handle it 💀 no cap, you'd have to use something else 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
};3.1.1.4. Sequence Execution 🎀
okay this part is giving "putting the puzzle together" energy 🧩 once the literals and sequences are decoded, they get combined to make the decoded content of a block. iconic behavior 👑
each sequence is a tuple of (literals_length, offset_value, match_length), decoded the way we talked about in Section 3.1.1.3.2. to run a sequence, you first copy literals_length bytes from the decoded literals over to the output 📝
then you copy match_length bytes from previously decoded data. the offset you copy from depends on 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 Section 3.1.1.5 for how that one gets figured out 🦋
the offset is measured from the current position (after you've copied the literals), so an offset of 6 with a match length of 3 means you copy 3 bytes from 6 bytes back 🌸 and bestie, every offset that points at previously decoded data must be smaller than Window_Size, which is defined in Frame_Header_Descriptor (Section 3.1.1.1.1). non-negotiable 💅
3.1.1.5. Repeat Offsets 🔁
as we saw above, the first three values define a repeated offset. we're gonna call them Repeated_Offset1, Repeated_Offset2, and Repeated_Offset3 🫶 they're sorted in recency order, so Repeated_Offset1 means "most recent one" 💜
if offset_value is 1, then the offset used is Repeated_Offset1, and so on 🍓
there's one plot twist though 😭 when the current sequence's literals_length is 0, the repeated offsets get shifted by 1. 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_byte. the way that this one's sneaky, I'm obsessed 🙈
for the first block, the starting offset history gets filled with Repeated_Offset1 (1), Repeated_Offset2 (4), and Repeated_Offset3 (8). the exception is if a dictionary is being used, then those values come from the dictionary instead 🧚
after that, each block picks up its starting offset history from the ending values of the most recent Compressed_Block. blocks that aren't Compressed_Block just get skipped, so they don't contribute to offset history at all. not me being picky, it's just how it works ✨
while the sequences of a Compressed_Block are running, the Repeated_Offsets stay up to date, so they always represent the three most recently used offsets. to keep that true, they get updated after each sequence like this:
When the sequence's offset_value doesn't refer to one of the Repeated_Offsets (when it's greater than 3, or when it's 3 and the sequence's literals_length is zero), the Repeated_Offsets get shifted back one, and Repeated_Offset1 takes on the value of the offset that was just used 🌈
Otherwise, when the sequence's offset_value does refer to one of the Repeated_Offsets (when it's 1 or 2, or when it's 3 and the sequence's literals_length is non-zero), the Repeated_Offsets get reordered. Repeated_Offset1 takes on the value of the used Repeated_Offset, and the existing values get pushed back from the first Repeated_Offset through to the one picked by the offset_value. it's basically a single-stepped wrapping rotation, so the order always matches how recently each one got used 💖
here's the table showing how the Repeated_Offsets change as a series of sequences gets applied to them 📊
+=======+==========+===========+===========+===========+============+
|offset_|literals_ | Repeated_ | Repeated_ | Repeated_ |Comment |
| value | length | Offset1 | Offset2 | Offset3 | |
+=======+==========+===========+===========+===========+============+
| | | 1 | 4 | 8 |starting |
| | | | | |values |
+-------+----------+-----------+-----------+-----------+------------+
| 1114| 11 | 1111 | 1 | 4 |non-repeat |
+-------+----------+-----------+-----------+-----------+------------+
| 1| 22 | 1111 | 1 | 4 |repeat 1; no|
| | | | | |change |
+-------+----------+-----------+-----------+-----------+------------+
| 2225| 22 | 2222 | 1111 | 1 |non-repeat |
+-------+----------+-----------+-----------+-----------+------------+
| 1114| 111 | 1111 | 2222 | 1111 |non-repeat |
+-------+----------+-----------+-----------+-----------+------------+
| 3336| 33 | 3333 | 1111 | 2222 |non-repeat |
+-------+----------+-----------+-----------+-----------+------------+
| 2| 22 | 1111 | 3333 | 2222 |repeat 2; |
| | | | | |swap 1 & 2 |
+-------+----------+-----------+-----------+-----------+------------+
| 3| 33 | 2222 | 1111 | 3333 |repeat 3; |
| | | | | |rotate 3 to |
| | | | | |1 |
+-------+----------+-----------+-----------+-----------+------------+
| 1| 0 | 2221 | 2222 | 1111 |insert |
| | | | | |resolved |
| | | | | |offset |
+-------+----------+-----------+-----------+-----------+------------+
| 1| 0 | 2222 | 2221 | 3333 |repeat 2 |
+-------+----------+-----------+-----------+-----------+------------+
Table 18: Repeated_Offsets3.1.2. Skippable Frames 🦋
this is where we get to slip user-defined metadata into a flow of concatenated frames 🧃
here's the layout:
+==============+============+===========+
| Magic_Number | Frame_Size | User_Data |
+==============+============+===========+
| 4 bytes | 4 bytes | n bytes |
+--------------+------------+-----------+
Table 19: Skippable Framesskippable frames defined in this spec are compatible with skippable frames in [LZ4] 🫶 so they play nice with the other kids
from a compliant decoder's point of view, skippable frames just need to be skipped. their content gets ignored, and decoding picks back up right after the skippable frame 🌸
🚨 okay, real talk, this one's serious. a skippable frame can be used to watermark a stream of concatenated frames by embedding any kind of tracking information, even just a Universally Unique Identifier (UUID). anyone who's wary of that should scan the stream of concatenated frames to try to detect such frames, whether that's for analysis or for removal. protect your stream, bestie 🛡️💜
here are the fields:
- Magic_Number: 4 bytes, little-endian format. Value: 0x184D2A5?, which means any value from 0x184D2A50 to 0x184D2A5F. All 16 values are valid for identifying a skippable frame. this spec doesn't detail any specific tagging methods for skippable frames 🧚
- Frame_Size: this is the size, in bytes, of the following User_Data (without including the magic number or the size field itself). it's 4 bytes in little-endian format, unsigned 32 bits. that means User_Data can't be bigger than (2^(32) -1) bytes 📏
- User_Data: this field can be anything. the decoder just skips over it 🫧
4. Entropy Encoding 🌈
okay so two types of entropy encoding show up in the Zstandard format: FSE and Huffman 💅 Huffman is used to compress literals, and FSE handles everything else, which is Literals_Length_Code, Match_Length_Code, and the offset codes. FSE also compresses the Huffman headers 💖
4.1. FSE 🔮
FSE, short for Finite State Entropy, is an entropy codec based on [ANS] ✨ FSE encoding and decoding both involve a state that gets carried over between symbols, so decoding has to happen in the opposite direction from encoding. that's why all FSE bitstreams are read from end to beginning 🙃 quick note: the order of the bits in the stream does NOT get reversed. they're just read in the reverse order from the one they were written in 🧠
if you want the deep dive on FSE, check out "FiniteStateEntropy" [FSE] 📚
FSE decoding uses a decoding table with a power-of-2 size, and each entry has three elements: Symbol, Num_Bits, and Baseline 🎀 the base 2 logarithm of the table size is its Accuracy_Log. an FSE state value is just an index into this table 🫶
to get the initial state value, consume Accuracy_Log bits from the stream as a little-endian value. the next symbol in the stream is the Symbol listed in the table for that state. to get the next state value, the decoder should consume Num_Bits bits from the stream as a little-endian value and add it to Baseline 🦋
4.1.1. FSE Table Description
okay bestie, before you can decode any FSE stream you have to build the decoding table first, and zstd has a very specific way of encoding those table descriptions 💅✨
An FSE distribution table describes the probabilities of all symbols from 0 to the last present one (that one included), on a normalized scale of (1 << Accuracy_Log). Also, there have to be two or more symbols with nonzero probability 🙈
The bitstream is read forward, in little-endian fashion 🎀. You don't need to know its exact size ahead of time, because the decoding process discovers it and reports it back. The bitstream starts by telling you which scale it's operating on. If low4bits is the lowest 4 bits of the first byte, then Accuracy_Log = low4bits + 5. ✨
After that comes each symbol value, from 0 up to the last present one. The number of bits each field uses is variable and depends on:
- Remaining probabilities + 1: For example, say Accuracy_Log is 8 and 100 probability points have already been handed out. The decoder can read any value from 0 to
(256 - 100 + 1) == 157, inclusive. So it has to readlog_(2)sup(157) == 8bits. 🧮 - Value decoded: Small values use 1 fewer bit 🦋. For example, if values from 0 to 157 (inclusive) are possible, then
255 - 157 = 98values are left in an 8-bit field. The first 98 values (so 0 to 97) only use 7 bits, and values from 98 to 157 use 8 bits. This all happens through the scheme in Table 20:
+============+===============+===========+
| Value Read | Value Decoded | Bits Used |
+============+===============+===========+
| 0 - 97 | 0 - 97 | 7 |
+------------+---------------+-----------+
| 98 - 127 | 98 - 127 | 8 |
+------------+---------------+-----------+
| 128 - 225 | 0 - 97 | 7 |
+------------+---------------+-----------+
| 226 - 255 | 128 - 157 | 8 |
+------------+---------------+-----------+Table 20: Values Decoded
Symbol probabilities get read one by one, in order. Each probability comes from the Value Decoded using P = Value - 1. That means the value 0 turns into the negative probability -1 🌀. This is a special one that means "less than 1". Its effect on the distribution table is described below. When you're calculating the total allocated probability points, it counts as 1.
When a symbol has a probability of zero, it's followed by a 2-bit repeat flag. That flag tells you how many zero-probability symbols come after the current one, anywhere from 0 to 3. If it's a 3, then another 2-bit repeat flag follows, and so on 🔁.
Once the last symbol brings the cumulated total up to (1 << Accuracy_Log), decoding is complete 🎉. But if the last symbol pushes the cumulated total above (1 << Accuracy_Log), the distribution is considered corrupted 💀.
Finally, the decoder can work out how many bytes were used in this whole process and how many symbols are present. The bitstream consumes a round number of bytes, so any leftover bits in the last byte are just unused 🍓.
The context where the table is going to be used specifies an expected number of symbols. That expected number never goes above 256. If the number of decoded symbols isn't equal to the expected number, the header should be considered corrupt 😭.
The normalized probability distribution is enough to build a unique decoding table. The table has a size of (1 << Accuracy_Log). Each cell describes the symbol that gets decoded, plus the instructions for getting the next state 🧚.
Symbols are scanned in their natural order for the "less than 1" probabilities we talked about above. Each of those symbols gets a single cell, starting from the end of the table and working backwards 🔙. These symbols define a full state reset, and that reset reads Accuracy_Log bits.
All remaining symbols get allocated in their natural order. Starting from symbol 0 and table position 0, each symbol gets as many cells as its probability says. The cell allocation is spread out, not linear 🌸. Each successor position follows this rule:
position += (tableSize >> 1) + (tableSize >> 3) + 3;
position &= tableSize - 1;A position gets skipped if it's already occupied by a "less than 1" probability symbol 🙅♀️. The position doesn't reset between symbols. It just keeps iterating through each position in the table, and switches to the next symbol once enough states have been allocated to the current one. ✨
The result is a list of state values, and each state decodes the current symbol 💜.
To get the Number_of_Bits and Baseline needed for the next state, you first have to sort all the states in their natural order. The lower states need 1 more bit than the higher ones. You repeat this for each symbol 🫶.
For example, say a symbol has a probability of 5, so it gets five state values. The states are sorted in natural order. The next power of 2 is 8. The space of probabilities is divided into 8 equal parts. If Accuracy_Log is 7, that defines 128 states, and each share (divided by 8) is 16 in size. To reach 8, the 8 - 5 = 3 lowest states count "double", which doubles the number of shares (32 in width) and requires 1 more bit in the process 👑.
Baseline gets assigned starting from the higher states that use fewer bits, moving along naturally, then resuming at the first state. Each one takes its allocated width out of the Baseline 🎀:
+----------------+-------+-------+--------+------+-------+
| state order | 0 | 1 | 2 | 3 | 4 |
+----------------+-------+-------+--------+------+-------+
| width | 32 | 32 | 32 | 16 | 16 |
+----------------+-------+-------+--------+------+-------+
| Number_of_Bits | 5 | 5 | 5 | 4 | 4 |
+----------------+-------+-------+--------+------+-------+
| range number | 2 | 4 | 6 | 0 | 1 |
+----------------+-------+-------+--------+------+-------+
| Baseline | 32 | 64 | 96 | 0 | 16 |
+----------------+-------+-------+--------+------+-------+
| range | 32-63 | 64-95 | 96-127 | 0-15 | 16-31 |
+----------------+-------+-------+--------+------+-------+Table 21: Baseline Assignments
The next state is determined from the current state by reading the required Number_of_Bits and adding the specified Baseline 🦋.
See Appendix A for the results of this process as applied to the default distributions 📖.
4.2. Huffman Coding
Zstandard Huffman-coded streams are read backwards, similar to the FSE bitstreams 🔄. So to find the start of the bitstream, you need to know the offset of the last byte of the Huffman-coded stream.
After writing the last bit that holds information, the compressor writes a single 1 bit and then fills the rest of the byte with 0 bits 🖊️. That's why the last byte of the compressed bitstream can't be 0.
When decompressing, the last byte (the one with the padding) is the first byte you read 👀. The decompressor needs to skip the up to 7 bits of 0-padding, plus that first 1 bit. After that, the useful part of the bitstream begins ✨.
The bitstream contains Huffman-coded symbols in little-endian order, using the codes defined by the method below 💖.
4.2.1. Huffman Tree Description
Prefix coding represents symbols from an a priori known alphabet with bit sequences (codewords), one codeword per symbol 🌈. Different symbols can be represented by bit sequences of different lengths, but a parser can always parse an encoded string unambiguously, symbol by symbol 🧩.
Given an alphabet with known symbol frequencies, the Huffman algorithm lets you build an optimal prefix code, using the fewest bits of any possible prefix code for that alphabet 🏆.
The prefix code must not exceed a maximum code length. More bits improve accuracy, but they make the header bigger and need more memory or more complex decoding operations 😵💫. This specification limits the maximum code length to 11 bits 🚧.
All literal values from zero (included) to the last present one (excluded) are represented by Weight, with values from 0 to Max_Number_of_Bits. Transforming from Weight to Number_of_Bits follows this pseudocode 💅:
if Weight == 0
Number_of_Bits = 0
else
Number_of_Bits = Max_Number_of_Bits + 1 - WeightThe last symbol's Weight is deduced from the previously decoded ones, by completing to the nearest power of 2. That power of 2 gives Max_Number_of_Bits the depth of the current tree 🌳.
For example, say we need to describe this Huffman tree 🎀:
+===============+================+
| Literal Value | Number_of_Bits |
+===============+================+
| 0 | 1 |
+---------------+----------------+
| 1 | 2 |
+---------------+----------------+
| 2 | 3 |
+---------------+----------------+
| 3 | 0 |
+---------------+----------------+
| 4 | 4 |
+---------------+----------------+
| 5 | 4 |
+---------------+----------------+Table 22: Huffman Tree
The tree depth is 4, since its longest element uses 4 bits. (The longest elements are the ones with the smallest frequencies 🐢.) Value 5 isn't listed, because it can be figured out from the values for 0-4. Values above 5 aren't listed either, since they're all 0. Values from 0 to 4 get listed using Weight instead of Number_of_Bits. The pseudocode to determine Weight is:
if Number_of_Bits == 0
Weight = 0
else
Weight = Max_Number_of_Bits + 1 - Number_of_BitsThat gives the following series of weights 📊:
+===============+========+
| Literal Value | Weight |
+===============+========+
| 0 | 4 |
+---------------+--------+
| 1 | 3 |
+---------------+--------+
| 2 | 2 |
+---------------+--------+
| 3 | 0 |
+---------------+--------+
| 4 | 1 |
+---------------+--------+Table 23: Weights
The decoder does the inverse operation. Having collected the weights of literals from 0 to 4, it knows the last literal, 5, is present with a nonzero Weight 🕵️♀️. The Weight of 5 can be determined by advancing to the next power of 2. The sum of 2^((Weight-1)) (excluding 0's) is 15. The nearest power of 2 is 16. So Max_Number_of_Bits = 4 and Weight[5] = 16 - 15 = 1 🎉.
4.2.1.1. Huffman Tree Header ✨
okay so this is a single byte (0-255) and it tells you how the series of weights is encoded 🎀
headerByte < 128: the series of weights is compressed using FSE (see below). The length of the FSE-compressed series is equal toheaderByte(0-127).headerByte >= 128: this is a direct representation, where each Weight is written straight into a 4-bit field (0-15) 🍓. They're encoded forward, 2 weights to a byte, with the first weight in the top 4 bits and the second in the bottom 4. For example, you could read the weights like this:
Weight[0] = (Byte[0] >> 4)
Weight[1] = (Byte[0] & 0xf),
etc.The full representation takes up ceiling(Number_of_Symbols/2) bytes, so it only uses full bytes even when Number_of_Symbols is odd. Number_of_Symbols = headerByte - 127, and the max is 255 - 127 = 128 ✨. If any literal has a value over 128, raw header mode is not possible and it is necessary to use FSE compression. No exceptions bestie 💅
4.2.1.2. FSE Compression of Huffman Weights
in this case the series of Huffman weights gets compressed with FSE 🧚. It's a single bitstream with two interleaved states, and they share one distribution table.
To decode an FSE bitstream, you need to know its compressed size, and that's given by headerByte. You also need its maximum possible decompressed size, which is 255, since literal values go from 0 to 255 and the last symbol's Weight isn't represented 🙈.
An FSE bitstream starts with a header that describes the probability distribution, and that creates a decoding table. For a list of Huffman weights, the maximum accuracy log is 6 bits. For more details, see Section 4.1.1 🦋.
The Huffman header compression uses two states that share the same FSE distribution table. The first state (State1) encodes the even-numbered index symbols, and the second (State2) encodes the odd-numbered index symbols. State1 gets initialized first, then State2, and they take turns decoding one symbol and updating their state. For more details on these FSE operations, see Section 4.1 💜.
The number of symbols to decode is set by tracking the bitStream overflow condition: if updating the state after decoding a symbol would need more bits than are left in the stream, extra bits are assumed to be zero. Then the symbols for each of the final states get decoded and the process is complete ✨.
4.2.1.3. Conversion from Weights to Huffman Prefix Codes
okay now every present symbol has a Weight value 🌈. You can turn weights into Number_of_Bits with this formula:
if Weight > 0
Number_of_Bits = Max_Number_of_Bits + 1 - Weight
else
Number_of_Bits = 0Symbols get sorted by Weight. Within the same Weight, symbols keep their natural sequential order. Symbols with a Weight of zero get removed. Then, starting from the lowest Weight, prefix codes are handed out in sequential order 👑.
For example, say this list of weights has been decoded:
+=========+========+
| Literal | Weight |
+=========+========+
| 0 | 4 |
+---------+--------+
| 1 | 3 |
+---------+--------+
| 2 | 2 |
+---------+--------+
| 3 | 0 |
+---------+--------+
| 4 | 1 |
+---------+--------+
| 5 | 1 |
+---------+--------+Table 24: Decoded Weights
Sorting by weight and then natural sequential order gives this distribution:
+=========+========+================+==============+
| Literal | Weight | Number_Of_Bits | Prefix Codes |
+=========+========+================+==============+
| 3 | 0 | 0 | N/A |
+---------+--------+----------------+--------------+
| 4 | 1 | 4 | 0000 |
+---------+--------+----------------+--------------+
| 5 | 1 | 4 | 0001 |
+---------+--------+----------------+--------------+
| 2 | 2 | 3 | 001 |
+---------+--------+----------------+--------------+
| 1 | 3 | 2 | 01 |
+---------+--------+----------------+--------------+
| 0 | 4 | 1 | 1 |
+---------+--------+----------------+--------------+Table 25: Sorting by Weight
4.2.2. Huffman-Coded Streams
now that you've got a Huffman decoding table, you can decode a Huffman-coded stream 🫶.
Each bitstream has to be read backward, starting from the end and going up to the beginning. That's why you need to know the size of each bitstream 🙃.
You also need to know exactly which bit is the last one. That's detected by a final bit flag: the highest bit of the last byte is the final-bit-flag. So a last byte of 0 isn't possible, and the final-bit-flag itself isn't part of the useful bitstream. That means the last byte holds between 0 and 7 useful bits 💀.
Starting from the end, you read the bitstream in a little-endian fashion, keeping track of the bits you've already used. Since the bitstream is encoded in reverse order, starting from the end, you read the symbols in forward order 🔥.
For example, if the literal sequence "0145" was encoded using the prefix code above, it would be encoded (in reverse order) like this:
+=========+==========+
| Symbol | Encoding |
+=========+==========+
| 5 | 0000 |
+---------+----------+
| 4 | 0001 |
+---------+----------+
| 1 | 01 |
+---------+----------+
| 0 | 1 |
+---------+----------+
| Padding | 00001 |
+---------+----------+Table 26: Literal Sequence "0145"
This results in the following 2-byte bitstream:
00010000 00001101Here's an alternative representation with the symbol codes separated by underscores:
0001_0000 00001_1_01Read the highest Max_Number_of_Bits bits, compare the extracted value to the decoding table, and that tells you which symbol to decode and how many bits to discard 🍓.
Keep going until you've decoded the required number of symbols per stream. If a bitstream isn't entirely and exactly consumed, meaning it doesn't end up at exactly its beginning position with all bits used, the decoding process is considered faulty 😭.
5. Dictionary Format
Zstandard is compatible with "raw content" dictionaries 📖. They're free of any format restriction, except that they must be at least 8 bytes. These dictionaries work as if they were just the content part of a formatted dictionary 🌸.
That said, dictionaries created by zstd --train in the reference implementation follow a specific format, which is described here ✨.
Dictionaries aren't included in the compressed content. They're provided out of band. The Dictionary_ID tells you which one to use, but this specification doesn't describe how you get the dictionary before compression or decompression 🦋.
A dictionary has a size, defined either by a buffer limit or a file size. The general format is:
+==============+===============+================+=========+
| Magic_Number | Dictionary_ID | Entropy_Tables | Content |
+==============+===============+================+=========+Table 27: Dictionary General Format
- Magic_Number: a 4 byte ID with the value
0xEC30A437, in little-endian format 🎀. - Dictionary_ID: 4 bytes, stored in little-endian format. It can be any value except 0 (which means no Dictionary_ID). Decoders use it to check that they're using the correct dictionary 🔍. If the frame is going to be distributed in a private environment, any Dictionary_ID can be used. But for public distribution of compressed frames, these ranges are reserved and shall not be used:
low range: <= 32767
high range: >= (2^(31))- Entropy_Tables: these follow the same format as the tables in compressed blocks. See the relevant FSE and Huffman sections for how to decode them 🧠. They're stored in this order: Huffman table for literals, FSE table for offsets, FSE table for match lengths, and FSE table for literals lengths. These tables populate the Repeat Stats literals mode and Repeat distribution mode for sequence decoding. After them come 3 offset values that populate the repeat offsets (instead of using
{1,4,8}). They're stored in order, 4 bytes little-endian each, for a total of 12 bytes. Each repeat offset must have a value less than the dictionary size 💖. - Content: the rest of the dictionary is its content 📚. The content acts as a "past" in front of the data being compressed or decompressed, so sequence commands can reference it. As long as the amount of data decoded from this frame is less than or equal to Window_Size, sequence commands may specify offsets longer than the total length of decoded output so far to reference back into the dictionary, even parts of the dictionary with offsets larger than Window_Size. Once the total output has surpassed Window_Size, though, this is no longer allowed and the dictionary is no longer accessible 🔒.
6. Use of Dictionaries
Provisioning for use of dictionaries with zstd is being explored 🌈. See, for example, [DICT-SEC]. The likely outcome is a registry of well-tested dictionaries optimized for different use cases, plus identifiers for each one, possibly with a private negotiation mechanism for using unregistered dictionaries 🧚.
To keep things compatible with the future spec for using dictionaries with zstd payloads, especially with MIME, content encoded with the media type registered here should not use a dictionary 🙈. The exception might be the private dictionary negotiation suggested above, which isn't part of this specification.
7. IANA Considerations ✨
IANA has updated two previously existing registrations and made one new registration, as described below 📝.
7.1. The 'application/zstd' Media Type ✨
okay so 'application/zstd' is the label you slap on a block of data that's been zstd-compressed 🎁 it's just a stream of bytes, exactly as this doc describes. IANA added it to the "Media Types" registry, and it looks like this:
Type name: application
Subtype name: zstd
Required parameters: N/A
Optional parameters: N/A
Encoding considerations: binary
Security considerations: See Section 8 of RFC 8878.
Interoperability considerations: N/A
Published specification: RFC 8878
Applications which use this media type: anywhere data size is an
issue
Fragment identifier considerations: No fragment identifiers are
defined for this type.
Additional information:
Deprecated alias names for this type: N/A
Magic number(s): 4 bytes, little-endian format.
Value: 0xFD2FB528
File extension(s): zst
Macintosh file type code(s): N/A
Person & email address to contact for further information: Yann
Collet <cyan@fb.com>
Intended usage: common
Restrictions on usage: N/A
Author: Murray S. Kucherawy
Change Controller: IETF
Provisional registration: no
For further information: See [ZSTD]7.2. Content Encoding 🫶
IANA also dropped an entry into the "HTTP Content Coding Registry" (which lives inside the "Hypertext Transfer Protocol (HTTP) Parameters" registry) 💅 here's the entry:
Name: zstd
Description: A stream of bytes compressed using the Zstandard
protocol
Reference: RFC 88787.3. Structured Syntax Suffix 🎀
IANA registered this one in the "Structured Syntax Suffix" registry:
Name: Zstandard
+suffix: +zstd
Encoding Considerations: binary
Interoperability Considerations: N/A
Fragment Identifier Considerations: The syntax and semantics of
fragment identifiers specified for +zstd should be as specified
for 'application/zstd'.
Security Considerations: See Section 8 of RFC 8878.
Contact: Refer to the author for the 'application/zstd' media type.
Author/Change Controller: IETF7.4. Dictionaries 🧚
okay the future is looking so cute ✨ people are cooking up dictionaries that make compression and decompression super tuned for particular kinds of data. to make a dictionary public, you'd need to register a code point from the reserved range covered in Section 3.1.1.1.3 and tie it to that specific dictionary 🔥
rn there are no dictionaries published for public use, so this document hasn't asked IANA to make a registry for them yet 🌸
8. Security Considerations 🔐
okay this section is serious bestie, but I'm still gonna make it fun 😭
Any data-compression method works by cutting down redundancy in the data. Zstandard is no exception, so the usual precautions apply 💀
Never compress a message whose content has to stay secret together with a message a third party generated. That kind of compression can be used to guess the secret message by analyzing how much the entropy drops. The Compression Ratio Info-leak Made Easy (CRIME) attack [CRIME] is a famous example of this 🙈
A decoder has to be able to detect and stop any kind of data tampering inside the compressed frame, so it doesn't trigger system faults like reading or writing outside its allowed memory ranges 🚨 a language that guarantees memory safety or careful bounds checking can handle this. Watch out especially for Number_of_Sequences values that make the decoder read into the block header (and past it), and for a Frame_Content_Size that's smaller than the real decompressed data, which an attacker could use to try to trigger a buffer overflow 😱 we highly recommend fuzz-testing your decoder. That means giving it invalid, unexpected, or random input and checking that it stays safe. Doing this helps you harden it so it can spot bad frames and deal with them without any nasty side effects 🫠
An attacker can also send correctly formed compressed frames that need unreasonable amounts of memory. A decoder must always keep control of its memory requirements and enforce some limits (specific to its system) so memory use stays protected from scenarios like that 🛡️
Compression can get better by training a dictionary on a bunch of related content payloads. That dictionary then has to be available at the decoder, or decompressing the payload won't be possible 🧠 this document doesn't say how to get a dictionary for a given compressed payload. Still, third-party dictionaries can interact in unexpected ways with a decoder, which could lead to memory or other resource-exhaustion attacks. We expect a forthcoming RFC about dictionary acquisition and transmission to cover this in more detail in its Security Considerations section, but we're flagging it now out of an abundance of caution ⚠️
As discussed in Section 3.1.2, arbitrary user metadata can be stored in skippable frames. Those frames are ignored during decompression of the data, but they can be used as a watermark to track the path of the compressed payload. 👀
9. References 📚
9.1. Normative References
[ZSTD] "Zstandard", <http://www.zstd.net>.9.2. Informative References
[ANS] Duda, J., "Asymmetric numeral systems: entropy coding
combining speed of Huffman coding with compression rate of
arithmetic coding", January 2014,
<https://arxiv.org/pdf/1311.2540>.
[CRIME] "CRIME", June 2018, <https://en.wikipedia.org/w/
index.php?title=CRIME&oldid=844538656>.
[DICT-SEC] Handte, F., "Security Considerations Regarding Compression
Dictionaries", Work in Progress, Internet-Draft, draft-
handte-httpbis-dict-sec-00, 29 October 2019,
<https://tools.ietf.org/html/draft-handte-httpbis-dict-
sec-00>.
[Err5786] RFC Errata, "Erratum ID 5786", RFC 8478,
<https://www.rfc-editor.org/errata/eid5786>.
[Err6303] RFC Errata, "Erratum ID 6303", RFC 8478,
<https://www.rfc-editor.org/errata/eid6303>.
[FSE] "FiniteStateEntropy", commit 12a533a, July 2020,
<https://github.com/Cyan4973/FiniteStateEntropy/>.
[LZ4] "LZ4 Frame Format Description", commit ec735ac, January
2019, <https://github.com/lz4/lz4/blob/master/doc/
lz4_Frame_format.md>.
[RFC1952] Deutsch, P., "GZIP file format specification version 4.3",
RFC 1952, DOI 10.17487/RFC1952, May 1996,
<https://www.rfc-editor.org/info/rfc1952>.
[XXHASH] "xxHash", <http://www.xxhash.org>.Appendix A. Decoding Tables for Predefined Codes 🧮
okay this appendix is all about the FSE decoding tables for the predefined literals length, match length, and offset codes 🦋 they were built with the algorithm from Section 4.1.1 above. Think of them as worked examples: you can use them to double-check that your implementation built its decoding tables correctly ✨
A.1. Literals Length Code Table ✨
okay so this is the big literals length table, and it's giving spreadsheet energy 🧚 the columns are State, Symbol, Number_Of_Bits, and Base, and it runs from state 0 all the way down to state 63 💅 literally the whole thing is laid out right here, so just scroll and vibe 🎀
+=======+========+================+======+
| State | Symbol | Number_Of_Bits | Base |
+=======+========+================+======+
| 0 | 0 | 0 | 0 |
+-------+--------+----------------+------+
| 0 | 0 | 4 | 0 |
+-------+--------+----------------+------+
| 1 | 0 | 4 | 16 |
+-------+--------+----------------+------+
| 2 | 1 | 5 | 32 |
+-------+--------+----------------+------+
| 3 | 3 | 5 | 0 |
+-------+--------+----------------+------+
| 4 | 4 | 5 | 0 |
+-------+--------+----------------+------+
| 5 | 6 | 5 | 0 |
+-------+--------+----------------+------+
| 6 | 7 | 5 | 0 |
+-------+--------+----------------+------+
| 7 | 9 | 5 | 0 |
+-------+--------+----------------+------+
| 8 | 10 | 5 | 0 |
+-------+--------+----------------+------+
| 9 | 12 | 5 | 0 |
+-------+--------+----------------+------+
| 10 | 14 | 6 | 0 |
+-------+--------+----------------+------+
| 11 | 16 | 5 | 0 |
+-------+--------+----------------+------+
| 12 | 18 | 5 | 0 |
+-------+--------+----------------+------+
| 13 | 19 | 5 | 0 |
+-------+--------+----------------+------+
| 14 | 21 | 5 | 0 |
+-------+--------+----------------+------+
| 15 | 22 | 5 | 0 |
+-------+--------+----------------+------+
| 16 | 24 | 5 | 0 |
+-------+--------+----------------+------+
| 17 | 25 | 5 | 32 |
+-------+--------+----------------+------+
| 18 | 26 | 5 | 0 |
+-------+--------+----------------+------+
| 19 | 27 | 6 | 0 |
+-------+--------+----------------+------+
| 20 | 29 | 6 | 0 |
+-------+--------+----------------+------+
| 21 | 31 | 6 | 0 |
+-------+--------+----------------+------+
| 22 | 0 | 4 | 32 |
+-------+--------+----------------+------+
| 23 | 1 | 4 | 0 |
+-------+--------+----------------+------+
| 24 | 2 | 5 | 0 |
+-------+--------+----------------+------+
| 25 | 4 | 5 | 32 |
+-------+--------+----------------+------+
| 26 | 5 | 5 | 0 |
+-------+--------+----------------+------+
| 27 | 7 | 5 | 32 |
+-------+--------+----------------+------+
| 28 | 8 | 5 | 0 |
+-------+--------+----------------+------+
| 29 | 10 | 5 | 32 |
+-------+--------+----------------+------+
| 30 | 11 | 5 | 0 |
+-------+--------+----------------+------+
| 31 | 13 | 6 | 0 |
+-------+--------+----------------+------+
| 32 | 16 | 5 | 32 |
+-------+--------+----------------+------+
| 33 | 17 | 5 | 0 |
+-------+--------+----------------+------+
| 34 | 19 | 5 | 32 |
+-------+--------+----------------+------+
| 35 | 20 | 5 | 0 |
+-------+--------+----------------+------+
| 36 | 22 | 5 | 32 |
+-------+--------+----------------+------+
| 37 | 23 | 5 | 0 |
+-------+--------+----------------+------+
| 38 | 25 | 4 | 0 |
+-------+--------+----------------+------+
| 39 | 25 | 4 | 16 |
+-------+--------+----------------+------+
| 40 | 26 | 5 | 32 |
+-------+--------+----------------+------+
| 41 | 28 | 6 | 0 |
+-------+--------+----------------+------+
| 42 | 30 | 6 | 0 |
+-------+--------+----------------+------+
| 43 | 0 | 4 | 48 |
+-------+--------+----------------+------+
| 44 | 1 | 4 | 16 |
+-------+--------+----------------+------+
| 45 | 2 | 5 | 32 |
+-------+--------+----------------+------+
| 46 | 3 | 5 | 32 |
+-------+--------+----------------+------+
| 47 | 5 | 5 | 32 |
+-------+--------+----------------+------+
| 48 | 6 | 5 | 32 |
+-------+--------+----------------+------+
| 49 | 8 | 5 | 32 |
+-------+--------+----------------+------+
| 50 | 9 | 5 | 32 |
+-------+--------+----------------+------+
| 51 | 11 | 5 | 32 |
+-------+--------+----------------+------+
| 52 | 12 | 5 | 32 |
+-------+--------+----------------+------+
| 53 | 15 | 6 | 0 |
+-------+--------+----------------+------+
| 54 | 17 | 5 | 32 |
+-------+--------+----------------+------+
| 55 | 18 | 5 | 32 |
+-------+--------+----------------+------+
| 56 | 20 | 5 | 32 |
+-------+--------+----------------+------+
| 57 | 21 | 5 | 32 |
+-------+--------+----------------+------+
| 58 | 23 | 5 | 32 |
+-------+--------+----------------+------+
| 59 | 24 | 5 | 32 |
+-------+--------+----------------+------+
| 60 | 35 | 6 | 0 |
+-------+--------+----------------+------+
| 61 | 34 | 6 | 0 |
+-------+--------+----------------+------+
| 62 | 33 | 6 | 0 |
+-------+--------+----------------+------+
| 63 | 32 | 6 | 0 |
+-------+--------+----------------+------+
Table 28: Literals Length CodeA.2. Match Length Code Table ✨
okay bestie, this is the match length table 🎀 it's the lookup that tells the decoder how to read each code, and it's giving very organized energy 💅
+=======+========+================+======+
| State | Symbol | Number_Of_Bits | Base |
+=======+========+================+======+
| 0 | 0 | 0 | 0 |
+-------+--------+----------------+------+
| 0 | 0 | 6 | 0 |
+-------+--------+----------------+------+
| 1 | 1 | 4 | 0 |
+-------+--------+----------------+------+
| 2 | 2 | 5 | 32 |
+-------+--------+----------------+------+
| 3 | 3 | 5 | 0 |
+-------+--------+----------------+------+
| 4 | 5 | 5 | 0 |
+-------+--------+----------------+------+
| 5 | 6 | 5 | 0 |
+-------+--------+----------------+------+
| 6 | 8 | 5 | 0 |
+-------+--------+----------------+------+
| 7 | 10 | 6 | 0 |
+-------+--------+----------------+------+
| 8 | 13 | 6 | 0 |
+-------+--------+----------------+------+
| 9 | 16 | 6 | 0 |
+-------+--------+----------------+------+
| 10 | 19 | 6 | 0 |
+-------+--------+----------------+------+
| 11 | 22 | 6 | 0 |
+-------+--------+----------------+------+
| 12 | 25 | 6 | 0 |
+-------+--------+----------------+------+
| 13 | 28 | 6 | 0 |
+-------+--------+----------------+------+
| 14 | 31 | 6 | 0 |
+-------+--------+----------------+------+
| 15 | 33 | 6 | 0 |
+-------+--------+----------------+------+
| 16 | 35 | 6 | 0 |
+-------+--------+----------------+------+
| 17 | 37 | 6 | 0 |
+-------+--------+----------------+------+
| 18 | 39 | 6 | 0 |
+-------+--------+----------------+------+
| 19 | 41 | 6 | 0 |
+-------+--------+----------------+------+
| 20 | 43 | 6 | 0 |
+-------+--------+----------------+------+
| 21 | 45 | 6 | 0 |
+-------+--------+----------------+------+
| 22 | 1 | 4 | 16 |
+-------+--------+----------------+------+
| 23 | 2 | 4 | 0 |
+-------+--------+----------------+------+
| 24 | 3 | 5 | 32 |
+-------+--------+----------------+------+
| 25 | 4 | 5 | 0 |
+-------+--------+----------------+------+
| 26 | 6 | 5 | 32 |
+-------+--------+----------------+------+
| 27 | 7 | 5 | 0 |
+-------+--------+----------------+------+
| 28 | 9 | 6 | 0 |
+-------+--------+----------------+------+
| 29 | 12 | 6 | 0 |
+-------+--------+----------------+------+
| 30 | 15 | 6 | 0 |
+-------+--------+----------------+------+
| 31 | 18 | 6 | 0 |
+-------+--------+----------------+------+
| 32 | 21 | 6 | 0 |
+-------+--------+----------------+------+
| 33 | 24 | 6 | 0 |
+-------+--------+----------------+------+
| 34 | 27 | 6 | 0 |
+-------+--------+----------------+------+
| 35 | 30 | 6 | 0 |
+-------+--------+----------------+------+
| 36 | 32 | 6 | 0 |
+-------+--------+----------------+------+
| 37 | 34 | 6 | 0 |
+-------+--------+----------------+------+
| 38 | 36 | 6 | 0 |
+-------+--------+----------------+------+
| 39 | 38 | 6 | 0 |
+-------+--------+----------------+------+
| 40 | 40 | 6 | 0 |
+-------+--------+----------------+------+
| 41 | 42 | 6 | 0 |
+-------+--------+----------------+------+
| 42 | 44 | 6 | 0 |
+-------+--------+----------------+------+
| 43 | 1 | 4 | 32 |
+-------+--------+----------------+------+
| 44 | 1 | 4 | 48 |
+-------+--------+----------------+------+
| 45 | 2 | 4 | 16 |
+-------+--------+----------------+------+
| 46 | 4 | 5 | 32 |
+-------+--------+----------------+------+
| 47 | 5 | 5 | 32 |
+-------+--------+----------------+------+
| 48 | 7 | 5 | 32 |
+-------+--------+----------------+------+
| 49 | 8 | 5 | 32 |
+-------+--------+----------------+------+
| 50 | 11 | 6 | 0 |
+-------+--------+----------------+------+
| 51 | 14 | 6 | 0 |
+-------+--------+----------------+------+
| 52 | 17 | 6 | 0 |
+-------+--------+----------------+------+
| 53 | 20 | 6 | 0 |
+-------+--------+----------------+------+
| 54 | 23 | 6 | 0 |
+-------+--------+----------------+------+
| 55 | 26 | 6 | 0 |
+-------+--------+----------------+------+
| 56 | 29 | 6 | 0 |
+-------+--------+----------------+------+
| 57 | 52 | 6 | 0 |
+-------+--------+----------------+------+
| 58 | 51 | 6 | 0 |
+-------+--------+----------------+------+
| 59 | 50 | 6 | 0 |
+-------+--------+----------------+------+
| 60 | 49 | 6 | 0 |
+-------+--------+----------------+------+
| 61 | 48 | 6 | 0 |
+-------+--------+----------------+------+
| 62 | 47 | 6 | 0 |
+-------+--------+----------------+------+
| 63 | 46 | 6 | 0 |
+-------+--------+----------------+------+
Table 29: Match Length Code TableA.3. Offset Code Table 🦋
Okay bestie, this is the offset code table, and it's giving lookup table energy ✨ Every row is a state, with the symbol, how many bits to read, and the base value. 💖
+=======+========+================+======+
| State | Symbol | Number_Of_Bits | Base |
+=======+========+================+======+
| 0 | 0 | 0 | 0 |
+-------+--------+----------------+------+
| 0 | 0 | 5 | 0 |
+-------+--------+----------------+------+
| 1 | 6 | 4 | 0 |
+-------+--------+----------------+------+
| 2 | 9 | 5 | 0 |
+-------+--------+----------------+------+
| 3 | 15 | 5 | 0 |
+-------+--------+----------------+------+
| 4 | 21 | 5 | 0 |
+-------+--------+----------------+------+
| 5 | 3 | 5 | 0 |
+-------+--------+----------------+------+
| 6 | 7 | 4 | 0 |
+-------+--------+----------------+------+
| 7 | 12 | 5 | 0 |
+-------+--------+----------------+------+
| 8 | 18 | 5 | 0 |
+-------+--------+----------------+------+
| 9 | 23 | 5 | 0 |
+-------+--------+----------------+------+
| 10 | 5 | 5 | 0 |
+-------+--------+----------------+------+
| 11 | 8 | 4 | 0 |
+-------+--------+----------------+------+
| 12 | 14 | 5 | 0 |
+-------+--------+----------------+------+
| 13 | 20 | 5 | 0 |
+-------+--------+----------------+------+
| 14 | 2 | 5 | 0 |
+-------+--------+----------------+------+
| 15 | 7 | 4 | 16 |
+-------+--------+----------------+------+
| 16 | 11 | 5 | 0 |
+-------+--------+----------------+------+
| 17 | 17 | 5 | 0 |
+-------+--------+----------------+------+
| 18 | 22 | 5 | 0 |
+-------+--------+----------------+------+
| 19 | 4 | 5 | 0 |
+-------+--------+----------------+------+
| 20 | 8 | 4 | 16 |
+-------+--------+----------------+------+
| 21 | 13 | 5 | 0 |
+-------+--------+----------------+------+
| 22 | 19 | 5 | 0 |
+-------+--------+----------------+------+
| 23 | 1 | 5 | 0 |
+-------+--------+----------------+------+
| 24 | 6 | 4 | 16 |
+-------+--------+----------------+------+
| 25 | 10 | 5 | 0 |
+-------+--------+----------------+------+
| 26 | 16 | 5 | 0 |
+-------+--------+----------------+------+
| 27 | 28 | 5 | 0 |
+-------+--------+----------------+------+
| 28 | 27 | 5 | 0 |
+-------+--------+----------------+------+
| 29 | 26 | 5 | 0 |
+-------+--------+----------------+------+
| 30 | 25 | 5 | 0 |
+-------+--------+----------------+------+
| 31 | 24 | 5 | 0 |
+-------+--------+----------------+------+Table 30: Offset Code 🌸
Appendix B. Changes since RFC 8478 💅
Here's the tea on what's different from RFC 8478 ☕ Every change is listed below, no cap:
- Applied errata [Err5786] and [Err6303]. 🔥
- Clarified forward compatibility regarding dictionaries. 📚
- Clarified application of Block_Maximum_Size. 🧩
- Added structured media type suffix registration. 🎀
- Clarified that the content checksum is always 4 bytes. 🔢
- Clarified handling of reserved and corrupt inputs. 🙈
- Added fragment identifier considerations to the media type registration. 🦋
Acknowledgments 🫶
zstd was made by Yann Collet, and she's an absolute legend for it 👑 🧚
Felix Handte and Nick Terrell gave feedback that shaped this revision and RFC 8478, so they get all the flowers 💐 RFC 8478 also got contributions from Bobo Bose-Kolanu, Kyle Nekritz, and David Schleimer, who are seriously iconic 🌈 💜
Authors' Addresses 🎀
Yann Collet
Facebook
1 Hacker Way
Menlo Park, CA 94025
United States of America
Email: cyan@fb.comMurray S. Kucherawy (editor)
Facebook
1 Hacker Way
Menlo Park, CA 94025
United States of America
Email: msk@fb.com📦 where this page comes from
- ietf: rfc8878 2021-02
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms