RFC 8478

Part 1 of 9 🌸

Hey bestie 💖 okay so this is RFC 8478, called Zstandard Compression and the application/zstd Media Type. It's an Informational doc, not a Standards Track spec, even though the name has "standard" in it 💀. It was written by Y. Collet and M. Kucherawy (the Ed. means editor 🫶) from Facebook, published in October 2018 with ISSN 2070-1721. The title block doesn't list any RFCs it obsoletes or updates, so this one is a fresh start 🦋

Abstract 💖

So zstd (say it "zee standard" 🎀) is a data compression mechanism, and this doc describes how it works. It also registers a media type and a content encoding for sending zstd-compressed stuff through MIME (Multipurpose Internet Mail Extensions) 📬

Despite the word "standard" in its name, readers are warned that this doc is not an Internet Standards Track spec. It's just published for info, nothing more 🙈

Status of This Memo

Okay, status check ✨ This doc is not an Internet Standards Track spec. It's published for informational purposes.

It's a product of the IETF, which means it represents the consensus of the IETF community. It got public review and was approved for publication by the IESG (Internet Engineering Steering Group) 🔥 Not every IESG-approved doc is a candidate for any level of Internet Standard, so check Section 2 of RFC 7841 if you want the deets 🧚

For the latest status, errata, and how to give feedback, go to https://www.rfc-editor.org/info/rfc8478 💅

Copyright Notice

Copyright (c) 2018 IETF Trust and the persons identified as the document authors. All rights reserved. 🌈

This doc 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 publication date. Please read these carefully, bestie, because they explain your rights and restrictions for this doc. Any Code Components pulled out of this doc must include the Simplified BSD License text, as described in Section 4.e of the Trust Legal Provisions, and they come without warranty, as the Simplified BSD License says 💜

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   4
   2.  Definitions . . . . . . . . . . . . . . . . . . . . . . . . .   4
   3.  Compression Algorithm . . . . . . . . . . . . . . . . . . . .   5
     3.1.  Frames  . . . . . . . . . . . . . . . . . . . . . . . . .   6
       3.1.1.  Zstandard Frames  . . . . . . . . . . . . . . . . . .   6
         3.1.1.1.  Frame Header  . . . . . . . . . . . . . . . . . .   7
         3.1.1.2.  Blocks  . . . . . . . . . . . . . . . . . . . . .  12
         3.1.1.3.  Compressed Blocks . . . . . . . . . . . . . . . .  14
         3.1.1.4.  Sequence Execution  . . . . . . . . . . . . . . .  28
         3.1.1.5.  Repeat Offsets  . . . . . . . . . . . . . . . . .  29
       3.1.2.  Skippable Frames  . . . . . . . . . . . . . . . . . .  30
   4.  Entropy Encoding  . . . . . . . . . . . . . . . . . . . . . .  30
     4.1.  FSE . . . . . . . . . . . . . . . . . . . . . . . . . . .  31
       4.1.1.  FSE Table Description . . . . . . . . . . . . . . . .  31
     4.2.  Huffman Coding  . . . . . . . . . . . . . . . . . . . . .  34
       4.2.1.  Huffman Tree Description  . . . . . . . . . . . . . .  35
         4.2.1.1.  Huffman Tree Header . . . . . . . . . . . . . . .  36
         4.2.1.2.  FSE Compression of Huffman Weights  . . . . . . .  37
         4.2.1.3.  Conversion from Weights to Huffman Prefix Codes .  38
       4.2.2.  Huffman-Coded Streams . . . . . . . . . . . . . . . .  39
   5.  Dictionary Format . . . . . . . . . . . . . . . . . . . . . .  40
   6.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  42
     6.1.  The 'application/zstd' Media Type . . . . . . . . . . . .  42
     6.2.  Content Encoding  . . . . . . . . . . . . . . . . . . . .  43
     6.3.  Dictionaries  . . . . . . . . . . . . . . . . . . . . . .  43
   7.  Security Considerations . . . . . . . . . . . . . . . . . . .  43
   8.  Implementation Status . . . . . . . . . . . . . . . . . . . .  44
   9.  References  . . . . . . . . . . . . . . . . . . . . . . . . .  45
     9.1.  Normative References  . . . . . . . . . . . . . . . . . .  45
     9.2.  Informative References  . . . . . . . . . . . . . . . . .  45
   Appendix A.  Decoding Tables for Predefined Codes . . . . . . . .  46
     A.1.  Literal Length Code Table . . . . . . . . . . . . . . . .  46
     A.2.  Match Length Code Table . . . . . . . . . . . . . . . . .  49
     A.3.  Offset Code Table . . . . . . . . . . . . . . . . . . . .  52
   Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . .  53
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  54

1. Introduction ✨

Okay so zstd is a data compression mechanism, kind of like gzip [RFC1952] 🍓

Same as before, the word "standard" is in the name, but readers are advised that this doc is not an Internet Standards Track spec. It's being published for info only 🙈

This doc describes the Zstandard format. It also registers a media type, so that when a data object compressed with Zstandard is sent in a MIME payload, you can identify it as such 📬

2. Definitions 🎀

Some terms used later in the doc are defined here so everyone's on the same page 🧚

uncompressed: Any set of bytes in its original form, before compression is applied 🌸

compress, compression: The act of running a set of bytes through the compression mechanism described here 💜

compressed: What you get after running a set of bytes through this mechanism. The original input has been compressed 🦋

decompress, decompression: Running a set of bytes through the inverse of the compression mechanism described here, trying to get back the original bytes from before compression 🔥

decompressed: What you get when you run a set of bytes through the reverse of this mechanism. If it works, the decompressed payload and the uncompressed payload are indistinguishable 💅

encode: Translating data from one form to another. That can include compression, or other translations this spec does 🌈

decode: The reverse of "encode". It means undoing a prior encoding to recover the original content 🫶

frame: Content compressed by Zstandard gets turned into a Zstandard frame. You can append multiple frames into one file or stream. Each frame is completely independent, has a defined beginning and end, and carries a set of parameters that tells the decoder how to decompress it 🎁

block: A frame holds one or more blocks. Each block has arbitrary content, described by its header, and a guaranteed maximum content size that depends on the frame parameters. Unlike frames, each block depends on the blocks before it to decode properly. But each block can be decompressed without waiting for the next one, which is what makes streaming possible 🌊

natural order: The order of a sequence of objects or values that's typical for that kind 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 this spec is Mixed_Case_With_Underscores 🐍 Identifiers inside square brackets mean the identifier is optional in the context shown.

3. Compression Algorithm 👑

This section describes the Zstandard algorithm ✨

The goal of this doc is to define a lossless compressed data format that is (a) independent of the CPU type, operating system, file system, and character set, and (b) suitable for file compression, pipe compression, and streaming compression, using the Zstandard algorithm. The text assumes you know basic programming at the level of bits and other primitive data representations 💻

The data can be produced or consumed even for an arbitrarily long sequentially presented input stream, using only a bounded amount of intermediate storage set in advance. That's why it works for data communications 📡 The format uses the Zstandard compression method, plus an optional xxHash-64 checksum method [XXHASH] for catching data corruption 🛡️

The data format in this spec does not try to allow random access to compressed data 🙅‍♀️

Unless noted otherwise, a compliant compressor must produce data sets that conform to the specifications here. It doesn't have 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 a non-ambiguous error code and an associated error message that explains which parameter is unsupported 🚨

This spec is for implementers who write software that compresses data into Zstandard format, decompresses data from it, or both 🧑‍💻 The Zstandard format is supported by an open source reference implementation, written in portable C, 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 without 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 contain compressed data, while skippable frames contain custom user metadata 🎀

3.1.1. Zstandard Frames 💜

Here's the structure of a single Zstandard frame 👀

  +--------------------+------------+
  |    Magic_Number    | 4 bytes    |
  +--------------------+------------+
  |    Frame_Header    | 2-14 bytes |
  +--------------------+------------+
  |     Data_Block     | n bytes    |
  +--------------------+------------+
  | [More Data_Blocks] |            |
  +--------------------+------------+
  | [Content_Checksum] | 0-4 bytes  |
  +--------------------+------------+

Magic_Number: 4 bytes, 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 actually 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 to show up at the start of a random file 🎯 It avoids trivial patterns (0x00, 0xFF, repeated bytes, increasing bytes, and so on), it includes 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 ✨

okay so the frame header is a variable-size thing 🎀 it's at least 2 bytes and can go all the way up to 14 bytes, depending on which optional bits show up. here's the layout:

+-------------------------+-----------+
| Frame_Header_Descriptor | 1 byte    |
+-------------------------+-----------+
|   [Window_Descriptor]   | 0-1 byte  |
+-------------------------+-----------+
|     [Dictionary_ID]     | 0-4 bytes |
+-------------------------+-----------+
|  [Frame_Content_Size]   | 0-8 bytes |
+-------------------------+-----------+

3.1.1.1.1. Frame_Header_Descriptor 💖

the first byte of the header is the Frame_Header_Descriptor, and it's basically the gatekeeper. it tells you which of the other fields are actually there, and decoding just this one byte is enough to figure out how big the whole 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      |
+------------+-------------------------+

in this table, bit 7 is the highest bit and bit 0 is the lowest one 💅

3.1.1.1.1.1. Frame_Content_Size_Flag 🌸

this is a 2-bit flag (basically Frame_Header_Descriptor shifted right by 6 bits) that says whether the Frame_Content_Size, which is the decompressed data size, is written into the header. the Flag_Value tells you the FCS_Field_Size, meaning how many bytes that size takes up:

+----------------+--------+---+---+---+
| Flag_Value     |   0    | 1 | 2 | 3 |
+----------------+--------+---+---+---+
| FCS_Field_Size | 0 or 1 | 2 | 4 | 8 |
+----------------+--------+---+---+---+

when Flag_Value is 0, the FCS_Field_Size depends on Single_Segment_Flag. if Single_Segment_Flag is set, FCS_Field_Size is 1. otherwise it's 0, and the Frame_Content_Size just isn't provided 🙈

3.1.1.1.1.2. Single_Segment_Flag 🔥

if this flag is set, the data MUST be regenerated within a single continuous memory segment.

in that case the Window_Descriptor byte gets skipped, but the Frame_Content_Size is definitely there. so the decoder MUST allocate a memory segment that's equal to or bigger than Frame_Content_Size.

to protect the decoder from unreasonable memory demands, a decoder is allowed to reject a compressed frame that asks for a memory size beyond its authorized range. boundaries are iconic 👑

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 that complies with this version of the specification SHALL NOT interpret this bit. it might get used in a future version to signal a property that isn't mandatory for decoding the frame properly. an encoder that complies 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, and a decoder that complies with this 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. it's giving "future proof" 🔮

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) that says whether a dictionary ID is provided within the header. it also sets the size of that field, called DID_Field_Size:

+----------------+---+---+---+---+
| Flag_Value     | 0 | 1 | 2 | 3 |
+----------------+---+---+---+---+
| DID_Field_Size | 0 | 1 | 2 | 4 |
+----------------+---+---+---+---+

3.1.1.1.2. Window Descriptor 🦋

this one gives you guarantees about the minimum memory buffer you need to decompress a frame, which is super important so decoders can allocate enough memory 💅

the Window_Descriptor byte is optional. when Single_Segment_Flag is set, the Window_Descriptor is not present, and then Window_Size is just the Frame_Content_Size. that can be any value from 0 to 2^64-1 bytes, which is 16 ExaBytes. wild 😭

+------------+----------+----------+
| Bit Number |   7-3    |   2-0    |
+------------+----------+----------+
| Field Name | Exponent | Mantissa |
+------------+----------+----------+

the minimum memory buffer size is called Window_Size, and it comes from these formulae:

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 works out to 3.75 TB. big brain numbers 🧠

generally speaking, bigger Window_Size values tend to improve the compression ratio, but they cost more memory 🌸

to properly decode compressed data, a decoder needs to allocate a buffer of at least Window_Size bytes.

to protect decoders from unreasonable memory requirements, a decoder is allowed to reject a compressed frame that requests a memory size beyond its 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 that need a Window_Size larger than 8 MB. it's merely a recommendation though, and decoders are free to support larger or lower limits, depending on local limitations 🎀

3.1.1.1.3. Dictionary_ID 🧚

this is a variable-size field that holds the ID of the dictionary you need to decode the frame properly. the field is optional. when it isn't present, it's up to the decoder to know which dictionary to use 🔍

the Dictionary_ID field size comes from DID_Field_Size, which is derived straight from Dictionary_ID_Flag. one byte can hold an ID from 0-255, two bytes can hold 0-65535, and four bytes can hold 0-4294967295. the format is little-endian 💖

it's allowed to represent a small ID (for example, 13) with a large 4-byte dictionary ID, even if that's less efficient 🙃

within private environments, any dictionary ID can be used. but for frames and dictionaries that get 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 6.3):

low range:  <= 32767
high 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, and it's optional info 💅 the Frame_Content_Size uses a variable number of bytes, set by FCS_Field_Size. and FCS_Field_Size comes from the value of Frame_Content_Size_Flag. it can be 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 |
+----------------+--------------+

the Frame_Content_Size format is little-endian. when FCS_Field_Size is 1, 4, or 8 bytes, the value gets read directly. when FCS_Field_Size is 2, an offset of 256 gets added. it's allowed to represent a small size (for example 18) using any compatible variant 🌸

3.1.1.2. Blocks 🧱

after the Magic_Number and Frame_Header, there are some number of blocks. each frame MUST have at least 1 block, but there's no upper limit on how many blocks a frame can have 🍓

the structure of a block looks like this:

+--------------+---------------+
| Block_Header | Block_Content |
+--------------+---------------+
|    3 bytes   |    n bytes    |
+--------------+---------------+

the Block_Header uses 3 bytes, written in little-endian convention. it has three fields:

+------------+------------+------------+
| Last_Block | Block_Type | Block_Size |
+------------+------------+------------+
|    bit 0   |   bits 1-2 |  bits 3-23 |
+------------+------------+------------+

3.1.1.2.1. Last_Block 🏁

the lowest bit, Last_Block, signals whether this block is the last one. the frame ends 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 are the Block_Type. there are four block types:

+-----------+------------------+
|   Value   |    Block_Type    |
+-----------+------------------+
|     0     |     Raw_Block    |
+-----------+------------------+
|     1     |     RLE_Block    |
+-----------+------------------+
|     2     | Compressed_Block |
+-----------+------------------+
|     3     |     Reserved     |
+-----------+------------------+

• Raw_Block: this is an uncompressed block. the Block_Content holds Block_Size bytes.
• RLE_Block: this is a single byte repeated Block_Size times. the Block_Content is one single byte. on the decompression side, this byte MUST be repeated Block_Size times 🔁
• Compressed_Block: this is a compressed block as described in Section 3.1.1.3. Block_Size is the length of the Block_Content, which is the compressed data. the decompressed size isn't known, but its maximum possible value is guaranteed (see below) 📦
• Reserved: this is not a block. this value can't be used with the current specification. if it shows up, it's considered to be corrupt data 💀

3.1.1.2.3. Block_Size 📏

the upper 21 bits of Block_Header represent the Block_Size. the Block_Size is the size of the block without the header. a block can contain any number of bytes (even zero), up to the Block_Maximum_Decompressed_Size, which is the smallest of:

• Window_Size
• 128 KB

a Compressed_Block has the extra restriction that Block_Size is always strictly less than the decompressed size. if that condition can't be respected, the block MUST be sent uncompressed instead (that is, treated as a Raw_Block) 🫧

3.1.1.3. Compressed Blocks ✨

Okay bestie, compressed blocks are where the magic happens 🪄 To decompress one, 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 into the decompressed data during Sequence Execution (Section 3.1.1.4) 🦋

To decode a compressed block, you need these ingredients 🍓

• Previous decoded data, up to a distance of Window_Size, or the beginning of the Frame, whichever is smaller. Single_Segment_Flag will be set in the latter case.
• A list of "recent offsets" from the previous Compressed_Block.
• The previous Huffman tree, required by Treeless_Literals_Block type.
• Previous Finite State Entropy (FSE) decoding tables, required by Repeat_Mode, for each symbol type (literals lengths, match lengths, offsets).

Note that decoding tables are not always from the previous Compressed_Block 👀

• 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 literals are regrouped in 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. So flexible, I'm obsessed 😭

Literals can be stored uncompressed or compressed using Huffman prefix codes. When compressed, an optional tree description can be present, followed by 1 or 4 streams.

  +----------------------------+
  |   Literals_Section_Header  |
  +----------------------------+
  | [Huffman_Tree_Description] |
  +----------------------------+
  |        [Jump_Table]        |
  +----------------------------+
  |          Stream_1          |
  +----------------------------+
  |         [Stream_2]         |
  +----------------------------+
  |         [Stream_3]         |
  +----------------------------+
  |         [Stream_4]         |
  +----------------------------+

---

3.1.1.3.1.1. Literals_Section_Header 💅

This field describes how literals are packed. It's a byte-aligned, variable-size bit field, ranging from 1 to 5 bytes, using little-endian convention. Bit fields are literally my love language 🫶

  +---------------------+-----------+
  | Literals_Block_Type |  2 bits   |
  +---------------------+-----------+
  |     Size_Format     | 1-2 bits  |
  +---------------------+-----------+
  |   Regenerated_Size  | 5-20 bits |
  +---------------------+-----------+
  |  [Compressed_Size]  | 0-18 bits |
  +---------------------+-----------+

In this representation, bits at the top are the lowest bits. Wild, but it works 🙃

The Literals_Block_Type field uses the two lowest bits of the first byte, describing four different block types:

  +---------------------------+-------+
  |    Literals_Block_Type    | Value |
  +---------------------------+-------+
  |     Raw_Literals_Block    |   0   |
  +---------------------------+-------+
  |     RLE_Literals_Block    |   1   |
  +---------------------------+-------+
  | Compressed_Literals_Block |   2   |
  +---------------------------+-------+
  |  Treeless_Literals_Block  |   3   |
  +---------------------------+-------+

• Raw_Literals_Block: Literals are stored uncompressed. Literals_Section_Content is Regenerated_Size.
• RLE_Literals_Block: Literals consist of a single-byte value repeated Regenerated_Size times. Literals_Section_Content is 1.
• Compressed_Literals_Block: This is a standard Huffman-compressed block, starting with a Huffman tree description. See details below. Literals_Section_Content is Compressed_Size.
• Treeless_Literals_Block: This is a Huffman-compressed block, using the Huffman tree from the previous Compressed_Literals_Block, or a dictionary if there is no previous Huffman-compressed literals block. Huffman_Tree_Description will be 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_Content is Compressed_Size.

The Size_Format is divided into two families:

• For Raw_Literals_Block and RLE_Literals_Block, it's only necessary to decode Regenerated_Size. There is no Compressed_Size field.
• For Compressed_Block and Treeless_Literals_Block, it's required to decode both Compressed_Size and Regenerated_Size (the decompressed size). It's also necessary 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_Format uses 1 bit. Regenerated_Size uses 5 bits (value 0-31). Literals_Section_Header uses 1 byte. Regenerated_Size = Literal_Section_Header[0]>>3.
• Size_Format == 01: Size_Format uses 2 bits. Regenerated_Size uses 12 bits (values 0-4095). Literals_Section_Header uses 2 bytes. Regenerated_Size = (Literals_Section_Header[0]>>4) + (Literals_Section_Header[1]<<4).
• Size_Format == 11: Size_Format uses 2 bits. Regenerated_Size uses 20 bits (values 0-1048575). Literals_Section_Header uses 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. Note that it is permitted to represent a short value (for example, 13) using a long format, even if it's less efficient. Extra bytes, extra vibes 🌸

Size_Format for Compressed_Literals_Block and Treeless_Literals_Block always uses 2 bits.

• Size_Format == 00: A single stream. Both Regenerated_Size and Compressed_Size use 10 bits (values 0-1023). Literals_Section_Header uses 3 bytes.
• Size_Format == 01: 4 streams. Both Regenerated_Size and Compressed_Size use 10 bits (values 0-1023). Literals_Section_Header uses 3 bytes.
• Size_Format == 10: 4 streams. Both Regenerated_Size and Compressed_Size use 14 bits (values 0-16383). Literals_Section_Header uses 4 bytes.
• Size_Format == 11: 4 streams. Both Regenerated_Size and Compressed_Size use 18 bits (values 0-262143). Literals_Section_Header uses 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 is present. Remember this one, it's a sneaky detail 👀

---

3.1.1.3.1.2. Raw_Literals_Block 🌷

The data in Stream_1 is Regenerated_Size bytes long. It contains the raw literals data to be used during Sequence Execution (Section 3.1.1.3.2). Simple, honest, iconic 🫧

3.1.1.3.1.3. RLE_Literals_Block 🍭

Stream_1 consists of a single byte that should be repeated Regenerated_Size times to generate the decoded literals. One byte, on repeat, no notes 🔁

3.1.1.3.1.4. Compressed_Literals_Block and Treeless_Literals_Block 🌈

Both of these modes contain Huffman-encoded data. For Treeless_Literals_Block, the Huffman table comes from the previously compressed literals block, or from a dictionary; see Section 5. Borrowing the table, no shame 🧚

3.1.1.3.1.5. Huffman_Tree_Description 🌳

This section is only present when the Literals_Block_Type type is Compressed_Literals_Block (2). The format of Huffman_Tree_Description can be found in Section 4.2.1. The size of Huffman_Tree_Description is determined during the decoding process. It must be used to determine where streams begin. Yes, this matters, bestie 🙈

  Total_Streams_Size = Compressed_Size
                       - Huffman_Tree_Description_Size

3.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.)

If only 1 stream is present, it is a single bitstream occupying the entire remaining portion of the literals block, encoded as described within Section 4.2.2.

If there are 4 streams, Literals_Section_Header only provides enough information to know 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, to reach a total decompressed size as specified in Regenerated_Size.

The compressed size of each stream is provided explicitly in the Jump_Table. The Jump_Table is 6 bytes long and consists of three 2-byte little-endian fields, describing the compressed sizes of the first 3 streams. Stream4_Size is computed from Total_Streams_Size minus sizes of other streams.

  Stream4_Size = Total_Streams_Size - 6
                 - Stream1_Size - Stream2_Size
                 - Stream3_Size

Heads up: if Stream1_Size + Stream2_Size + Stream3_Size exceeds Total_Streams_Size, the data are considered corrupted. Yikes 💀

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 🎬

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

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

This is described in more detail in Section 3.1.1.4.

The Sequences_Section regroups all symbols required to decode commands. There are three symbol types: literals lengths, offsets, and match lengths. They are encoded together, interleaved, in a single "bitstream". Very tidy, very chic 💅

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

  Sequences_Section_Header
    [Literals_Length_Table]
    [Offset_Table]
    [Match_Length_Table]
    bitStream

To decode the Sequences_Section, it's necessary to know its size. This size is 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 ✨

okay so this header is made of two items 💅:

• Number_of_Sequences
• Symbol_Compression_Modes

Number_of_Sequences is a variable size field that can take up between 1 and 3 bytes 🧚. You check the first byte, called "byte0", and it tells you how big the field is:

• if (byte0 == 0): there are no sequences 💀. The sequence section stops right here, and the decompressed content is made up entirely of Literals Section content. The FSE tables used in Repeat_Mode are not updated.
• if (byte0 < 128): Number_of_Sequences = byte0. This uses 1 byte.
• if (byte0 < 255): Number_of_Sequences = ((byte0 - 128) << 8) + byte1. This uses 2 bytes.
• if (byte0 == 255): Number_of_Sequences = byte1 + (byte2 << 8) + 0x7F00. This uses 3 bytes.

Symbol_Compression_Modes is a single byte that sets the compression mode for each symbol type 🦋. Here's how the bits are laid out:

+-------------+----------------------+
| Bit Number  |      Field Name      |
+-------------+----------------------+
|     7-6     | Literal_Lengths_Mode |
+-------------+----------------------+
|     5-4     |     Offsets_Mode     |
+-------------+----------------------+
|     3-2     |  Match_Lengths_Mode  |
+-------------+----------------------+
|     1-0     |       Reserved       |
+-------------+----------------------+

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

Literals_Lengths_Mode, Offsets_Mode, and Match_Lengths_Mode define the Compression_Mode of literals lengths, offsets, and match lengths symbols, respectively. They all follow the same enumeration, so this is the one to memorise 🌸:

+-------+---------------------+
| Value |  Compression_Mode   |
+-------+---------------------+
|   0   |   Predefined_Mode   |
+-------+---------------------+
|   1   |      RLE_Mode       |
+-------+---------------------+
|   2   | FSE_Compressed_Mode |
+-------+---------------------+
|   3   |     Repeat_Mode     |
+-------+---------------------+

Predefined_Mode: a predefined FSE distribution table (see Section 4.1) is used, as defined in Section 3.1.1.3.2.2. No distribution table will be present 🎀.

RLE_Mode: the table description is a single byte that holds the symbol's value. That symbol gets used for all sequences 🍓.

FSE_Compressed_Mode: this is standard FSE compression, and a distribution table will be present. The format of that table is described in Section 4.1.1. Note that the maximum allowed accuracy log for the literals length and match length tables is 9, and the maximum accuracy log for the offsets 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 gets used again. If this is the first block, the table in the dictionary gets used instead. 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 has 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 🌈

each symbol is a code in its own context, and it specifies the Baseline and Number_of_Bits to add ⭐. The codes are FSE compressed and interleaved with raw additional bits in the same bitstream, which is a lot of going on at once, bestie 🧚.

Literals length codes are values from 0 to 35 inclusive 💜. They define lengths from 0 to 131071 bytes. The literals length is equal to the decoded Baseline plus the result of reading Number_of_Bits bits from the bitstream, 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       |
+----------------------+----------+----------------+

Match length codes are values from 0 to 52 inclusive 🎀. They define lengths from 3 to 131074 bytes. The match length is equal to the decoded Baseline plus the result of reading Number_of_Bits bits from the bitstream, read 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       |
+-------------------+-----------------------+----------------+

Offset 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 this writing, the reference decoder supports a maximum N value of 31 ✨.

An offset code is also the number of additional bits to read in little-endian fashion, and 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;

This means the maximum Offset_Value is (2^(N+1))-1, which supports back-reference distances 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 are special. They define "repeat codes", and this is described in more detail in Section 3.1.1.5 🔥.

3.1.1.3.2.1.2. Decoding Sequences 💅

okay bestie, FSE bitstreams are read in the reverse of the direction they were written 🔄. The compressor writes bits forward into a block, so the decompressor has to read that bitstream backwards. honestly, the whole vibe is backwards 💀

To find the start of the bitstream, you need the offset of the last byte of the block. You get it by counting Block_Size bytes after the block header 📏.

After the compressor writes the last bit that holds information, it writes a single 1 bit and then fills the byte with 0-7 zero bits of padding ✨. The last byte of the compressed bitstream can't be zero for that reason, so it's a little sign that the padding is there 🫶.

When you decompress, the last byte with the padding is the first byte you read 👀. You skip 0-7 initial zero bits until the first 1 bit shows up, and then the useful part of the bitstream begins 🌸.

FSE decoding needs a 'state' that gets carried from symbol to symbol 🧚. If you want more on FSE decoding, check out Section 4.1 📚.

For sequence decoding, a separate state keeps track of each literal lengths, offsets, and match lengths symbol 🎀. A few FSE primitives get used too, and you can read about how those work in Section 4.1 💜.

The bitstream starts with initial FSE state values. Each one uses the required number of bits in its own accuracy, and you decode them earlier from their normalized distribution 🦋. It starts with Literals_Length_State, then Offset_State, and finally Match_Length_State 👑.

Note that all values get read backward. So the 'start' of the bitstream is at the highest position in memory, right before the last 1 bit for padding 🙈.

After you decode the starting states, you decode a single sequence Number_Of_Sequences times 🔥. Sequences get decoded in order, from first to last. The compressor writes the bitstream forward, so it has to encode the sequences starting with the last one and ending with the first 😭.

For each symbol type, the FSE state tells you the right code. The code then defines the Baseline and Number_of_Bits to read for each type 💖. You can find out how to work out these values in Section 3.1.1.3.2.1 ✨.

Decoding starts by reading the Number_of_Bits needed to decode the offset 🌈. You do the same for Match_Length, and then for Literals_Length 🍓. This sequence then gets used for Sequence Execution (see Section 3.1.1.4) 🦋.

If it's not the last sequence in the block, the next step is to update the states 💅. Using the rules you worked out ahead of time in the decoding tables, you update Literals_Length_State first, then Match_Length_State, and then Offset_State 🔄. See Section 4.1 for how to update states from the bitstream 📖.

You repeat this operation Number_of_Sequences times. At the end, the bitstream shall be entirely consumed. If it isn't, the bitstream is considered corrupted 💀🫠.

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. Those tables are defined here 📋. For details on turning this distribution into a decoding table, see Section 4.1 💜.

3.1.1.3.2.2.1. Literals Length 🍓

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

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

3.1.1.3.2.2.2. Match Length 🦋

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

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

3.1.1.3.2.2.3. Offset Codes 🌸

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

If any sequence in the compressed block needs a bigger offset than this, you can't use the default distribution to represent it 😬.

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

3.1.1.4. Sequence Execution 🚀

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

Each sequence is a tuple of (literals_length, offset_value, match_length), decoded the way the Sequences_Section describes (Section 3.1.1.3.2) 🎀. To execute a sequence, you first copy literals_length bytes from the decoded literals to the output 📤.

Then you copy match_length bytes from previously decoded data. The offset to copy from is set by offset_value 🎯:

• if Offset_Value > 3, then the offset is Offset_Value - 3;
• if Offset_Value is from 1-3, the offset is a special repeat offset value. See Section 3.1.1.5 for how the offset gets determined in this case 🔁.

The offset is measured from the current position (after copying the literals). So an offset of 6 and a match length of 3 means 3 bytes get copied from 6 bytes back 👈. Note that all offsets leading to previously decoded data must be smaller than Window_Size, which is defined in Frame_Header_Descriptor (Section 3.1.1.1.1) 🪟.

3.1.1.5. Repeat Offsets 🔁

As seen above, the first three values define a repeated offset. We'll call them Repeated_Offset1, Repeated_Offset2, and Repeated_Offset3 💖. They're sorted in recency order, with Repeated_Offset1 meaning "most recent one" 👑.

If offset_value is 1, then the offset used is Repeated_Offset1, and so on 🦋.

There's one exception 😤. 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 🙃.

For the first block, the starting offset history is filled with these values: Repeated_Offset1 (1), Repeated_Offset2 (4), and Repeated_Offset3 (8). The exception is when a dictionary is used, because then they come from the dictionary 📖.

After that, each block gets its starting offset history from the ending values of the most recent Compressed_Block. Blocks that aren't Compressed_Block are skipped, so they don't contribute to offset history 🙅‍♀️.

The newest offset takes the lead in offset history and shifts the others back. (If it was already in the history, it goes up to its previous place.) So when Repeated_Offset1 (the most recent) gets used, the history stays unmodified 🧘‍♀️. When Repeated_Offset2 is used, it swaps places with Repeated_Offset1 🔀. If any other offset is used, it becomes Repeated_Offset1, and the rest get shifted back by 1 🎬.

3.1.2. Skippable Frames 🦋

+--------------+------------+-----------+
| Magic_Number | Frame_Size | User_Data |
+--------------+------------+-----------+
|    4 bytes   |   4 bytes  |  n bytes  |
+--------------+------------+-----------+

Skippable frames let you slip user-defined metadata into a flow of concatenated frames 🎁.

Skippable frames defined in this specification are compatible with skippable frames in [LZ4] 🤝.

From a compliant decoder's perspective, skippable frames just need to be skipped. Their content gets ignored, and decoding resumes after the skippable frame 🏃‍♀️.

It should be noted that a skippable frame can be used to watermark a stream of concatenated frames. It can embed any kind of tracking information, even just a Universally Unique Identifier (UUID) 👀. Users who are wary of that possibility should scan the stream of concatenated frames to try to detect such frames, for analysis or removal 🕵️‍♀️.

The fields are:

• Magic_Number: 4 bytes, little-endian format. Value: 0x184D2A5?, which means any value from 0x184D2A50 to 0x184D2A5F. All 16 values are valid to identify a skippable frame. This specification does not 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 nor the size field itself). This field is represented using 4 bytes, little-endian format, unsigned 32 bits. This means User_Data can't be bigger than (2^32-1) bytes 📐.
• User_Data: This field can be anything. Data will just be skipped by the decoder 🫧.

4. Entropy Encoding 🧠

Two types of entropy encoding are used by the Zstandard format: FSE and Huffman coding 💜. Huffman is used to compress literals. FSE is used for all other symbols (Literals_Length_Code, Match_Length_Code, and offset codes), and it's also used to compress Huffman headers ✨.

4.1. FSE 🌈

FSE, short for Finite State Entropy, is an entropy codec based on [ANS] 🧮. FSE encoding and decoding involve a state that gets carried over between symbols. So decoding has to happen in the opposite direction from encoding 🔙. That means all FSE bitstreams are read from end to beginning. The order of the bits in the stream isn't reversed, though. They're just read in the reverse order from the one they were written in 🫶.

For more details on FSE, see Finite State Entropy [FSE] 📚.

FSE decoding uses a decoding table that has a power of 2 size and contains three elements: Symbol, Num_Bits, and Baseline 🎀. The base 2 logarithm of the table size is its Accuracy_Log. An FSE state value represents an index in 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 indicated 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, then add it to Baseline 💖.

4.1.1. FSE Table Description 💖

okay so, to decode FSE streams you need to build the decoding table first 🎀 The Zstandard format describes FSE tables in the way explained here.

An FSE distribution table tells you the probability of every symbol from 0 up to the last present one (included), on a normalized scale of (1 << Accuracy_Log). Note that there must be two or more symbols with non-zero 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 finds it out and reports it. The bitstream starts by saying which scale it's working 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 to the last present one. The number of bits each field uses is variable, and it depends on two things:

• Remaining probabilities + 1: For example, say Accuracy_Log is 8 and 100 probability points have already been handed out. The decoder may read any value from 0 to (256 - 100 + 1) == 157, inclusive. So it must read log2sup(157) == 8 bits. 🧁
• Value decoded: Small values use 1 fewer bit. For example, say values from 0 to 157 (inclusive) are possible. That leaves 255 - 157 = 98 values 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 works through the scheme below 💅

+------------+---------------+-----------+
| 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     |
+------------+---------------+-----------+

Symbol probabilities get read one at a time, in order. You get each probability from the Value decoded using P = Value - 1. So the value 0 turns into the negative probability -1. That's a special one that means "less than 1" 🙈 It changes the distribution table in a way explained below. When you're totalling up allocated probability points, it counts as 1.

When a symbol has a probability of zero, a 2-bit repeat flag comes right after it. That flag says how many zero-probability symbols follow the current one. It gives a number from 0 to 3. If the flag is a 3, another 2-bit repeat flag follows, and so on. It's giving chain of flags 🔗

When the last symbol brings the running total up to (1 << Accuracy_Log), decoding is finished. If the last symbol pushes the total above (1 << Accuracy_Log), the distribution is considered corrupted. > Yikes, that's a dealbreaker 😭

At the end, the decoder can work out how many bytes were used in this process and how many symbols are present. The bitstream uses a round number of bytes. Any leftover bit in the last byte just goes unused 🌸

The normalized probabilities are enough to build one unique decoding table. The table has a size of (1 << Accuracy_Log). Each cell says which symbol gets decoded and how to find the next state ✨

Symbols are checked in their natural order for those "less than 1" probabilities, as described 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, which reads Accuracy_Log bits.

All the 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 next position follows this rule:

position += (tableSize >> 1) + (tableSize >> 3) + 3;
position &= tableSize - 1;

A position gets skipped if a "less than 1" probability symbol is already sitting in it. The position doesn't reset between symbols. It just keeps moving through each position in the table, and it switches to the next symbol once enough states have been given to the current one 🦋

The result is a list of state values. Each state decodes the current symbol.

To figure out the Number_of_Bits and Baseline 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. It gets five state values, and those states are sorted in natural order. The next power of 2 is 8, so the space of probabilities gets split into 8 equal parts. If Accuracy_Log is 7, that means 128 states, and each share (divided by 8) is 16 in size. To reach 8, the 8 - 5 = 3 lowest states count "double". That doubles their number of shares (to 32 in width), and they need 1 more bit as a result 🎀

Baseline is handed out starting from the higher states that use fewer bits. It goes along naturally, then starts again at the first state. Each state 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 |
+----------------+-------+-------+--------+------+-------+

The next state comes from the current state. You read the required Number_of_Bits and add 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 get read backwards, a bit like 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 the compressor writes the last bit that holds information, it writes a single 1 bit. Then it fills out the byte with 0-7 0 bits of padding. 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 0-7 initial 0 bits, plus the first 1 bit that shows up. After that, the useful part of the bitstream starts 💖

The bitstream holds 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). There's one codeword for each symbol. Different symbols can have bit sequences of different lengths, but a parser can always parse an encoded string unambiguously, one symbol at a time ✨

Given an alphabet with known symbol frequencies, the Huffman algorithm lets you build an optimal prefix code. It uses 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 also 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. The transformation 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 - Weight

The last symbol's Weight is deduced from the ones decoded before it, by completing to the nearest power of 2. That power of 2 gives Max_Number_of_Bits, which is the depth of the current tree 🌳

For example, say the following Huffman tree needs to be described:

+---------------+----------------+
| Literal Value | Number_of_Bits |
+---------------+----------------+
|       0       |        1       |
+---------------+----------------+
|       1       |        2       |
+---------------+----------------+
|       2       |        3       |
+---------------+----------------+
|       3       |        0       |
+---------------+----------------+
|       4       |        4       |
+---------------+----------------+
|       5       |        4       |
+---------------+----------------+

The tree depth is 4, since its longest element uses 4 bits. (The longest elements are the ones with the smallest frequencies.) Value 5 won't be listed, because it can be worked 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 find Weight is:

if Number_of_Bits == 0
  Weight = 0
else
  Weight = Max_Number_of_Bits + 1 - Number_of_Bits

That gives the following series of weights:

+---------------+--------+
| Literal Value | Weight |
+---------------+--------+
|       0       |   4    |
+---------------+--------+
|       1       |   3    |
+---------------+--------+
|       2       |   2    |
+---------------+--------+
|       3       |   0    |
+---------------+--------+
|       4       |   1    |
+---------------+--------+

The decoder does the inverse operation. Once it has collected the weights of literals 0 to 4, it knows the last literal, 5, is present with a non-zero Weight. The Weight of 5 comes from moving up to the next power of 2. The sum of 2^(Weight-1) (leaving out the 0's) is 15, and 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 🎀

This is a single byte value (0-255) that says 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 to headerByte (0-127). 💅
• headerByte >= 128: This is a direct representation, where each Weight is written directly as a 4-bit field (0-15). They're encoded forward, 2 weights to a byte. The first weight takes the top 4 bits, and the second takes the bottom 4. For example, these operations could be used to read the weights:

Weight[0] = (Byte[0] >> 4)
Weight[1] = (Byte[0] & 0xf),
etc.

The full representation takes up ceiling(Number_of_Symbols/2) bytes. That means it uses only full bytes, even when Number_of_Symbols is odd. Number_of_Symbols = headerByte - 127. Note that the maximum Number_of_Symbols is 255 - 127 = 128. If any literal has a value over 128, raw header mode isn't possible, and it's necessary to use FSE compression. Keep an eye on this one, bestie, it's a dealbreaker 😭🔥

4.2.1.2. FSE Compression of Huffman Weights ✨

okay so here the Huffman weights get squished down with FSE compression 🫧 It's one single bitstream with two interleaved states, and they both share one distribution table. so cute, right? 🎀

To decode an FSE bitstream, you need to know its compressed size. That size comes from headerByte. You also need its maximum possible decompressed size, which is 255, because literal values run from 0 to 255 and the last symbol's Weight never gets stored. 💅

An FSE bitstream starts with a header that describes the probability distribution, and that header is what builds the decoding table. For a list of Huffman weights, the maximum accuracy log is 6 bits. If you want the full scoop, check out Section 4.1.1. 🦋

The Huffman header compression uses two states that share the same FSE distribution table. State1 handles the even-numbered index symbols, and State2 handles the odd-numbered index symbols. State1 gets initialized first, then State2, and they take turns decoding one symbol each and updating their state. The whole dance is explained in Section 4.1. 💖

The number of symbols to decode is decided by watching for the bitStream overflow condition. If updating the state after decoding a symbol would need more bits than the stream has left, then the missing bits are assumed to be zero. Then the symbols for each of the final states get decoded and boom, done. 🏁

4.2.1.3. Conversion from Weights to Huffman Prefix Codes 🌈

All the present symbols now have a Weight value. Next we turn those weights into Number_of_Bits with this formula:

  if Weight > 0
      Number_of_Bits = Max_Number_of_Bits + 1 - Weight
  else
      Number_of_Bits = 0

Symbols get sorted by Weight. Within the same Weight, they keep their natural sequential order. Symbols with a Weight of zero get removed. Then, starting from the lowest Weight, the prefix codes get handed out in sequential order. 🍓

Let's look at an example where this list of weights has been decoded:

  +---------+--------+
  | Literal | Weight |
  +---------+--------+
  |    0    |   4    |
  +---------+--------+
  |    1    |   3    |
  +---------+--------+
  |    2    |   2    |
  +---------+--------+
  |    3    |   0    |
  +---------+--------+
  |    4    |   1    |
  +---------+--------+
  |    5    |   1    |
  +---------+--------+

Sort by weight, then by natural sequential order, and you get 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     |
  +---------+--------+----------------|--------------+

4.2.2. Huffman-Coded Streams 🧜

Once you've got a Huffman decoding table, you can decode a Huffman-coded stream. It's giving precision. 💅

Each bitstream has to be read backward, starting from the end and heading toward the beginning. That means you need to know the size of each bitstream up front. 🫶

You also need to know exactly which bit is the last one. That's caught by a final bit flag: the highest bit of the last byte is the final-bit-flag. So a last byte of 0 is not possible, and the final-bit-flag itself isn't part of the useful bitstream. That leaves the last byte with between 0 and 7 useful bits. ✨

Start from the end and read the bitstream in a little-endian fashion, keeping track of the bits you've already used. Since the bitstream was encoded in reverse order, starting from the end, you read the symbols in forward order. Wild, but it works 🙈

For example, say the literal sequence "0145" was encoded with the prefix code above. In reverse order, it would be encoded like this:

  +---------+----------+
  | Symbol  | Encoding |
  +---------+----------+
  |    5    |   0000   |
  +---------+----------+
  |    4    |   0001   |
  +---------+----------+
  |    1    |    01    |
  +---------+----------+
  |    0    |    1     |
  +---------+----------+
  | Padding |   00001  |
  +---------+----------+

This gives the following 2-byte bitstream:

  00010000 00001101

Here's the same thing with the symbol codes split up by underscores:

  0001_0000 00001_1_01

Read the highest Max_Number_of_Bits bits, then compare the extracted value to the decoding table. That tells you which symbol to decode and how many bits to discard. 🔍

Keep going until you've read the required number of symbols per stream. If a bitstream isn't entirely and exactly consumed (meaning you don't land exactly on its beginning position with every bit used up), then the decoding process is considered faulty. Yikes, no notes. 💀

5. Dictionary Format 📚

Zstandard is compatible with "raw content" dictionaries. They're free of any format restriction, except they must be at least 8 bytes. These dictionaries work as if they were just the content part of a formatted dictionary. 🌸

However, dictionaries created by "zstd --train" in the reference implementation follow a specific format, which is described right here. 🎀

Dictionaries aren't included in the compressed content. They're provided out of band. So the Dictionary_ID tells you which one to use, but this specification doesn't describe how you actually get the dictionary before compressing or decompressing. Mystery vibes 🔮

A dictionary has a size, defined either by a buffer limit or a file size. The general format looks like this:

+--------------+---------------+----------------+---------+
| Magic_Number | Dictionary_ID | Entropy_Tables | Content |
+--------------+---------------+----------------+---------+

• 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. Check 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, which 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 to be compressed or decompressed, so it can be referenced in sequence commands. 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 to the dictionary, even parts of the dictionary with offsets larger than Window_Size. After the total output has surpassed Window_Size, however, this is no longer allowed, and the dictionary is no longer accessible. Plot twist 😭

6. IANA Considerations 🏛️

IANA has made two registrations, as described below. Official paperwork moment 📝

6.1. The 'application/zstd' Media Type 🍰

The 'application/zstd' media type identifies a block of data that's compressed using zstd compression. The data is a stream of bytes as described in this document. IANA has added the following to the "Media Types" registry:

Type name:  application
Subtype name:  zstd
Required parameters:  N/A
Optional parameters:  N/A
Encoding considerations:  binary
Security considerations:  See Section 7 of RFC 8478
Interoperability considerations:  N/A
Published specification:  RFC 8478
Applications that use this media type:  anywhere data size is an
   issue
Additional information:
   Magic number(s):  4 bytes, little-endian format.
      Value: 0xFD2FB528
   File extension(s):  zst
   Macintosh file type code(s):  N/A
For further information:  See [ZSTD]
Intended usage:  common
Restrictions on usage:  N/A
Author:  Murray S.  Kucherawy
Change Controller:  IETF
Provisional registration:  no

6.2. Content Encoding 🫧

IANA has added the following entry to the "HTTP Content Coding Registry" within the "Hypertext Transfer Protocol (HTTP) Parameters" registry:

Name:  zstd
Description:  A stream of bytes compressed using the Zstandard
   protocol
Pointer to specification text:  RFC 8478

6.3. Dictionaries 🔐

Work in progress includes development of dictionaries that will optimize compression and decompression of particular types of data. Specifying such dictionaries for public use will require registering a code point from the reserved range described in Section 3.1.1.1.3, along with its association with a specific dictionary. 🌟

However, there are at present no such dictionaries published for public use, so this document makes no immediate request of IANA to create such a registry. Nothing to register yet, bestie 🥹

7. Security Considerations 🔐

okay bestie, compression is literally all about squishing out the repetition in your data, so any compression method has this vibe where it reveals patterns. Zstandard is no exception, so the usual precautions apply 💅

One should never compress a message whose content must remain secret with a message generated by a third party 🙅‍♀️ Like, that combo can be used to guess the secret message just by watching how much the entropy goes down. The Compression Ratio Info-leak Made Easy (CRIME) attack [CRIME] is the classic example of this, and it's giving "don't do this" 😭

A decoder has to be able to detect and prevent any kind of data tampering in the compressed frame, so it doesn't trigger system faults like reading or writing beyond allowed memory ranges 🛡️ This can be guaranteed by either the implementation language or careful bound checkings. Of particular note is the encoding of Number_of_Sequences values that make the decoder read into the block header (and beyond) 👀 Same goes for a Frame_Content_Size that's smaller than the actual decompressed data, which is an attempt to trigger a buffer overflow 💀 It is highly recommended to fuzz-test decoder implementations (that means throwing invalid, unexpected, or random input at them and checking that they stay safe) so they can detect bad frames and deal with them without any adverse system side effects 🧪 This is literally how you harden your code, iykyk ✨

An attacker may send correctly formed compressed frames with unreasonable memory requirements 🫠 A decoder must always control its memory requirements and enforce some (system-specific) limits so that memory usage is protected from scenarios like this 👑

Compression can be optimized by training a dictionary on a variety of related content payloads 📚 That dictionary must then be available at the decoder for the payload to be decompressible at all. This document does not specify how to acquire a dictionary for a given compressed payload, but it's worth noting that third-party dictionaries may interact unexpectedly with a decoder, which could lead to memory or other resource exhaustion attacks 🚨 We expect these topics to be discussed in more detail in the Security Considerations section of a forthcoming RFC for dictionary acquisition and transmission, but we're flagging the issue now out of an abundance of caution 🫶

As discussed in Section 3.1.2, it is possible to store arbitrary user metadata 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 👀 not me side-eyeing that one 🙈

---

8. Implementation Status 🎀

the source code for a C language implementation of a Zstandard-compliant library lives at [ZSTD-GITHUB] 💖 This implementation is considered the reference implementation and it's production ready 🔥 It implements the full range of the specification, it's routinely tested against security hazards, and it's widely deployed within Facebook infrastructure 🌸

The reference version is optimized for speed and is highly portable 🦋 It has been proven to run safely on multiple architectures (e.g., x86, x64, ARM, MIPS, PowerPC, IA64) with 32- or 64-bit addressing schemes, and with a little- or big-endian storage scheme 🧚 It also runs on a bunch of operating systems (e.g., UNIX, including Linux, BSD, OS-X, and Solaris, plus Windows) and with a number of compilers (e.g., gcc, clang, visual, and icc) 💅✨

---

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.
• [FSE] "FiniteStateEntropy", commit 6efa78a, June 2018, https://github.com/Cyan4973/FiniteStateEntropy/.
• [LZ4] "LZ4 Frame Format Description", commit d03224b, January 2018, 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 Algorithm", http://www.xxhash.org.
• [ZSTD-GITHUB] "zstd", commit 8514bd8, August 2018, https://github.com/facebook/zstd.

---

Appendix A. Decoding Tables for Predefined Codes 🧁

this appendix has the FSE decoding tables for the predefined literal length, match length, and offset codes 💜 The tables were built using the algorithm given above in Section 4.1.1, so they're perfect examples you can use to crosscheck that your implementation built its decoding tables correctly 🔍

A.1. Literal Length Code Table

  +-------+--------+----------------+------+
  | 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  |
  +-------+--------+----------------+------+

A.2. Match Length Code Table ✨

okay bestie, this one is the match length table 💅 It's the lookup that maps each state to a symbol, a number of bits, and a base, so a decoder can work out match lengths. Here it is, every row exactly as written 🫶

     +-------+--------+----------------+------+
     | 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  |
     +-------+--------+----------------+------+

A.3. Offset Code Table 🎀

and now the offset code table 🦋 same deal: state, symbol, number of bits, base, all copied exactly so nothing gets lost in the vibes 🌈

     +-------+--------+----------------+------+
     | 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  |
     +-------+--------+----------------+------+

---

Acknowledgments 🫶

okay the thank-you section 🥹 zstd was developed by Yann Collet, the main queen behind it 👑

Bobo Bose-Kolanu, Felix Handte, Kyle Nekritz, Nick Terrell, and David Schleimer gave really helpful feedback while this document was being written 💜 literal legends, all of them 🌸

---

Authors' Addresses 💖

the people behind it, with their addresses exactly as they're written 🧚

   Yann Collet
   Facebook
   1 Hacker Way
   Menlo Park, CA  94025
   United States of America

   Email: cyan@fb.com


   Murray S. Kucherawy (editor)
   Facebook
   1 Hacker Way
   Menlo Park, CA  94025
   United States of America

   Email: msk@fb.com