1 Zstandard Compression Format
2 ============================
6 Copyright (c) Meta Platforms, Inc. and affiliates.
8 Permission is granted to copy and distribute this document
9 for any purpose and without charge,
10 including translations into other languages
11 and incorporation into compilations,
12 provided that the copyright notice and this notice are preserved,
13 and that any substantive changes or deletions from the original
15 Distribution of this document is unlimited.
25 The purpose of this document is to define a lossless compressed data format,
26 that is independent of CPU type, operating system,
27 file system and character set, suitable for
28 file compression, pipe and streaming compression,
29 using the [Zstandard algorithm](https://facebook.github.io/zstd/).
30 The text of the specification assumes a basic background in programming
31 at the level of bits and other primitive data representations.
33 The data can be produced or consumed,
34 even for an arbitrarily long sequentially presented input data stream,
35 using only an a priori bounded amount of intermediate storage,
36 and hence can be used in data communications.
37 The format uses the Zstandard compression method,
38 and optional [xxHash-64 checksum method](https://cyan4973.github.io/xxHash/),
39 for detection of data corruption.
41 The data format defined by this specification
42 does not attempt to allow random access to compressed data.
44 Unless otherwise indicated below,
45 a compliant compressor must produce data sets
46 that conform to the specifications presented here.
47 It doesn’t need to support all options though.
49 A compliant decompressor must be able to decompress
50 at least one working set of parameters
51 that conforms to the specifications presented here.
52 It may also ignore informative fields, such as checksum.
53 Whenever it does not support a parameter defined in the compressed stream,
54 it must produce a non-ambiguous error code and associated error message
55 explaining which parameter is unsupported.
57 This specification is intended for use by implementers of software
58 to compress data into Zstandard format and/or decompress data from Zstandard format.
59 The Zstandard format is supported by an open source reference implementation,
60 written in portable C, and available at : https://github.com/facebook/zstd .
63 ### Overall conventions
65 - square brackets i.e. `[` and `]` are used to indicate optional fields or parameters.
66 - the naming convention for identifiers is `Mixed_Case_With_Underscores`
69 Content compressed by Zstandard is transformed into a Zstandard __frame__.
70 Multiple frames can be appended into a single file or stream.
71 A frame is completely independent, has a defined beginning and end,
72 and a set of parameters which tells the decoder how to decompress it.
74 A frame encapsulates one or multiple __blocks__.
75 Each block contains arbitrary content, which is described by its header,
76 and has a guaranteed maximum content size, which depends on frame parameters.
77 Unlike frames, each block depends on previous blocks for proper decoding.
78 However, each block can be decompressed without waiting for its successor,
79 allowing streaming operations.
84 - [Zstandard frames](#zstandard-frames)
86 - [Literals Section](#literals-section)
87 - [Sequences Section](#sequences-section)
88 - [Sequence Execution](#sequence-execution)
89 - [Skippable frames](#skippable-frames)
90 - [Entropy Encoding](#entropy-encoding)
92 - [Huffman Coding](#huffman-coding)
93 - [Dictionary Format](#dictionary-format)
97 Zstandard compressed data is made of one or more __frames__.
98 Each frame is independent and can be decompressed independently of other frames.
99 The decompressed content of multiple concatenated frames is the concatenation of
100 each frame decompressed content.
102 There are two frame formats defined by Zstandard:
103 Zstandard frames and Skippable frames.
104 Zstandard frames contain compressed data, while
105 skippable frames contain custom user metadata.
108 The structure of a single Zstandard frame is following:
110 | `Magic_Number` | `Frame_Header` |`Data_Block`| [More data blocks] | [`Content_Checksum`] |
111 |:--------------:|:--------------:|:----------:| ------------------ |:--------------------:|
112 | 4 bytes | 2-14 bytes | n bytes | | 0-4 bytes |
116 4 Bytes, __little-endian__ format.
118 Note: This value was selected to be less probable to find at the beginning of some random file.
119 It avoids trivial patterns (0x00, 0xFF, repeated bytes, increasing bytes, etc.),
120 contains byte values outside of ASCII range,
121 and doesn't map into UTF8 space.
122 It reduces the chances that a text file represent this value by accident.
126 2 to 14 Bytes, detailed in [`Frame_Header`](#frame_header).
130 Detailed in [`Blocks`](#blocks).
131 That’s where compressed data is stored.
133 __`Content_Checksum`__
135 An optional 32-bit checksum, only present if `Content_Checksum_flag` is set.
136 The content checksum is the result
137 of [xxh64() hash function](https://cyan4973.github.io/xxHash/)
138 digesting the original (decoded) data as input, and a seed of zero.
139 The low 4 bytes of the checksum are stored in __little-endian__ format.
143 The `Frame_Header` has a variable size, with a minimum of 2 bytes,
144 and up to 14 bytes depending on optional parameters.
145 The structure of `Frame_Header` is following:
147 | `Frame_Header_Descriptor` | [`Window_Descriptor`] | [`Dictionary_ID`] | [`Frame_Content_Size`] |
148 | ------------------------- | --------------------- | ----------------- | ---------------------- |
149 | 1 byte | 0-1 byte | 0-4 bytes | 0-8 bytes |
151 #### `Frame_Header_Descriptor`
153 The first header's byte is called the `Frame_Header_Descriptor`.
154 It describes which other fields are present.
155 Decoding this byte is enough to tell the size of `Frame_Header`.
157 | Bit number | Field name |
158 | ---------- | ---------- |
159 | 7-6 | `Frame_Content_Size_flag` |
160 | 5 | `Single_Segment_flag` |
162 | 3 | `Reserved_bit` |
163 | 2 | `Content_Checksum_flag` |
164 | 1-0 | `Dictionary_ID_flag` |
166 In this table, bit 7 is the highest bit, while bit 0 is the lowest one.
168 __`Frame_Content_Size_flag`__
170 This is a 2-bits flag (`= Frame_Header_Descriptor >> 6`),
171 specifying if `Frame_Content_Size` (the decompressed data size)
172 is provided within the header.
173 `Flag_Value` provides `FCS_Field_Size`,
174 which is the number of bytes used by `Frame_Content_Size`
175 according to the following table:
177 | `Flag_Value` | 0 | 1 | 2 | 3 |
178 | -------------- | ------ | --- | --- | --- |
179 |`FCS_Field_Size`| 0 or 1 | 2 | 4 | 8 |
181 When `Flag_Value` is `0`, `FCS_Field_Size` depends on `Single_Segment_flag` :
182 if `Single_Segment_flag` is set, `FCS_Field_Size` is 1.
183 Otherwise, `FCS_Field_Size` is 0 : `Frame_Content_Size` is not provided.
185 __`Single_Segment_flag`__
188 data must be regenerated within a single continuous memory segment.
190 In this case, `Window_Descriptor` byte is skipped,
191 but `Frame_Content_Size` is necessarily present.
192 As a consequence, the decoder must allocate a memory segment
193 of size equal or larger than `Frame_Content_Size`.
195 In order to preserve the decoder from unreasonable memory requirements,
196 a decoder is allowed to reject a compressed frame
197 which requests a memory size beyond decoder's authorized range.
199 For broader compatibility, decoders are recommended to support
200 memory sizes of at least 8 MB.
201 This is only a recommendation,
202 each decoder is free to support higher or lower limits,
203 depending on local limitations.
207 A decoder compliant with this specification version shall not interpret this bit.
208 It might be used in any future version,
209 to signal a property which is transparent to properly decode the frame.
210 An encoder compliant with this specification version must set this bit to zero.
214 This bit is reserved for some future feature.
215 Its value _must be zero_.
216 A decoder compliant with this specification version must ensure it is not set.
217 This bit may be used in a future revision,
218 to signal a feature that must be interpreted to decode the frame correctly.
220 __`Content_Checksum_flag`__
222 If this flag is set, a 32-bits `Content_Checksum` will be present at frame's end.
223 See `Content_Checksum` paragraph.
225 __`Dictionary_ID_flag`__
227 This is a 2-bits flag (`= FHD & 3`),
228 telling if a dictionary ID is provided within the header.
229 It also specifies the size of this field as `DID_Field_Size`.
231 |`Flag_Value` | 0 | 1 | 2 | 3 |
232 | -------------- | --- | --- | --- | --- |
233 |`DID_Field_Size`| 0 | 1 | 2 | 4 |
235 #### `Window_Descriptor`
237 Provides guarantees on minimum memory buffer required to decompress a frame.
238 This information is important for decoders to allocate enough memory.
240 The `Window_Descriptor` byte is optional.
241 When `Single_Segment_flag` is set, `Window_Descriptor` is not present.
242 In this case, `Window_Size` is `Frame_Content_Size`,
243 which can be any value from 0 to 2^64-1 bytes (16 ExaBytes).
245 | Bit numbers | 7-3 | 2-0 |
246 | ----------- | ---------- | ---------- |
247 | Field name | `Exponent` | `Mantissa` |
249 The minimum memory buffer size is called `Window_Size`.
250 It is described by the following formulas :
252 windowLog = 10 + Exponent;
253 windowBase = 1 << windowLog;
254 windowAdd = (windowBase / 8) * Mantissa;
255 Window_Size = windowBase + windowAdd;
257 The minimum `Window_Size` is 1 KB.
258 The maximum `Window_Size` is `(1<<41) + 7*(1<<38)` bytes, which is 3.75 TB.
260 In general, larger `Window_Size` tend to improve compression ratio,
261 but at the cost of memory usage.
263 To properly decode compressed data,
264 a decoder will need to allocate a buffer of at least `Window_Size` bytes.
266 In order to preserve decoder from unreasonable memory requirements,
267 a decoder is allowed to reject a compressed frame
268 which requests a memory size beyond decoder's authorized range.
270 For improved interoperability,
271 it's recommended for decoders to support `Window_Size` of up to 8 MB,
272 and it's recommended for encoders to not generate frame requiring `Window_Size` larger than 8 MB.
273 It's merely a recommendation though,
274 decoders are free to support larger or lower limits,
275 depending on local limitations.
279 This is a variable size field, which contains
280 the ID of the dictionary required to properly decode the frame.
281 `Dictionary_ID` field is optional. When it's not present,
282 it's up to the decoder to know which dictionary to use.
284 `Dictionary_ID` field size is provided by `DID_Field_Size`.
285 `DID_Field_Size` is directly derived from value of `Dictionary_ID_flag`.
286 1 byte can represent an ID 0-255.
287 2 bytes can represent an ID 0-65535.
288 4 bytes can represent an ID 0-4294967295.
289 Format is __little-endian__.
291 It's allowed to represent a small ID (for example `13`)
292 with a large 4-bytes dictionary ID, even if it is less efficient.
294 A value of `0` has same meaning as no `Dictionary_ID`,
295 in which case the frame may or may not need a dictionary to be decoded,
296 and the ID of such a dictionary is not specified.
297 The decoder must know this information by other means.
299 #### `Frame_Content_Size`
301 This is the original (uncompressed) size. This information is optional.
302 `Frame_Content_Size` uses a variable number of bytes, provided by `FCS_Field_Size`.
303 `FCS_Field_Size` is provided by the value of `Frame_Content_Size_flag`.
304 `FCS_Field_Size` can be equal to 0 (not present), 1, 2, 4 or 8 bytes.
306 | `FCS_Field_Size` | Range |
307 | ---------------- | ---------- |
314 `Frame_Content_Size` format is __little-endian__.
315 When `FCS_Field_Size` is 1, 4 or 8 bytes, the value is read directly.
316 When `FCS_Field_Size` is 2, _the offset of 256 is added_.
317 It's allowed to represent a small size (for example `18`) using any compatible variant.
323 After `Magic_Number` and `Frame_Header`, there are some number of blocks.
324 Each frame must have at least one block,
325 but there is no upper limit on the number of blocks per frame.
327 The structure of a block is as follows:
329 | `Block_Header` | `Block_Content` |
330 |:--------------:|:---------------:|
331 | 3 bytes | n bytes |
335 `Block_Header` uses 3 bytes, written using __little-endian__ convention.
336 It contains 3 fields :
338 | `Last_Block` | `Block_Type` | `Block_Size` |
339 |:------------:|:------------:|:------------:|
340 | bit 0 | bits 1-2 | bits 3-23 |
344 The lowest bit signals if this block is the last one.
345 The frame will end after this last block.
346 It may be followed by an optional `Content_Checksum`
347 (see [Zstandard Frames](#zstandard-frames)).
351 The next 2 bits represent the `Block_Type`.
352 `Block_Type` influences the meaning of `Block_Size`.
353 There are 4 block types :
355 | Value | 0 | 1 | 2 | 3 |
356 | ------------ | ----------- | ----------- | ------------------ | --------- |
357 | `Block_Type` | `Raw_Block` | `RLE_Block` | `Compressed_Block` | `Reserved`|
359 - `Raw_Block` - this is an uncompressed block.
360 `Block_Content` contains `Block_Size` bytes.
362 - `RLE_Block` - this is a single byte, repeated `Block_Size` times.
363 `Block_Content` consists of a single byte.
364 On the decompression side, this byte must be repeated `Block_Size` times.
366 - `Compressed_Block` - this is a [Zstandard compressed block](#compressed-blocks),
368 `Block_Size` is the length of `Block_Content`, the compressed data.
369 The decompressed size is not known,
370 but its maximum possible value is guaranteed (see below)
372 - `Reserved` - this is not a block.
373 This value cannot be used with current version of this specification.
374 If such a value is present, it is considered corrupted data.
378 The upper 21 bits of `Block_Header` represent the `Block_Size`.
380 When `Block_Type` is `Compressed_Block` or `Raw_Block`,
381 `Block_Size` is the size of `Block_Content` (hence excluding `Block_Header`).
383 When `Block_Type` is `RLE_Block`, since `Block_Content`’s size is always 1,
384 `Block_Size` represents the number of times this byte must be repeated.
386 `Block_Size` is limited by `Block_Maximum_Size` (see below).
388 __`Block_Content`__ and __`Block_Maximum_Size`__
390 The size of `Block_Content` is limited by `Block_Maximum_Size`,
391 which is the smallest of:
395 `Block_Maximum_Size` is constant for a given frame.
396 This maximum is applicable to both the decompressed size
397 and the compressed size of any block in the frame.
399 The reasoning for this limit is that a decoder can read this information
400 at the beginning of a frame and use it to allocate buffers.
401 The guarantees on the size of blocks ensure that
402 the buffers will be large enough for any following block of the valid frame.
407 To decompress a compressed block, the compressed size must be provided
408 from `Block_Size` field within `Block_Header`.
410 A compressed block consists of 2 sections :
411 - [Literals Section](#literals-section)
412 - [Sequences Section](#sequences-section)
414 The results of the two sections are then combined to produce the decompressed
415 data in [Sequence Execution](#sequence-execution)
418 To decode a compressed block, the following elements are necessary :
419 - Previous decoded data, up to a distance of `Window_Size`,
420 or beginning of the Frame, whichever is smaller.
421 - List of "recent offsets" from previous `Compressed_Block`.
422 - The previous Huffman tree, required by `Treeless_Literals_Block` type
423 - Previous FSE decoding tables, required by `Repeat_Mode`
424 for each symbol type (literals lengths, match lengths, offsets)
426 Note that decoding tables aren't always from the previous `Compressed_Block`.
428 - Every decoding table can come from a dictionary.
429 - The Huffman tree comes from the previous `Compressed_Literals_Block`.
433 All literals are regrouped in the first part of the block.
434 They can be decoded first, and then copied during [Sequence Execution],
435 or they can be decoded on the flow during [Sequence Execution].
437 Literals can be stored uncompressed or compressed using Huffman prefix codes.
438 When compressed, a tree description may optionally be present,
439 followed by 1 or 4 streams.
441 | `Literals_Section_Header` | [`Huffman_Tree_Description`] | [jumpTable] | Stream1 | [Stream2] | [Stream3] | [Stream4] |
442 | ------------------------- | ---------------------------- | ----------- | ------- | --------- | --------- | --------- |
445 ### `Literals_Section_Header`
447 Header is in charge of describing how literals are packed.
448 It's a byte-aligned variable-size bitfield, ranging from 1 to 5 bytes,
449 using __little-endian__ convention.
451 | `Literals_Block_Type` | `Size_Format` | `Regenerated_Size` | [`Compressed_Size`] |
452 | --------------------- | ------------- | ------------------ | ------------------- |
453 | 2 bits | 1 - 2 bits | 5 - 20 bits | 0 - 18 bits |
455 In this representation, bits on the left are the lowest bits.
457 __`Literals_Block_Type`__
459 This field uses 2 lowest bits of first byte, describing 4 different block types :
461 | `Literals_Block_Type` | Value |
462 | --------------------------- | ----- |
463 | `Raw_Literals_Block` | 0 |
464 | `RLE_Literals_Block` | 1 |
465 | `Compressed_Literals_Block` | 2 |
466 | `Treeless_Literals_Block` | 3 |
468 - `Raw_Literals_Block` - Literals are stored uncompressed.
469 - `RLE_Literals_Block` - Literals consist of a single byte value
470 repeated `Regenerated_Size` times.
471 - `Compressed_Literals_Block` - This is a standard Huffman-compressed block,
472 starting with a Huffman tree description.
473 In this mode, there are at least 2 different literals represented in the Huffman tree description.
475 - `Treeless_Literals_Block` - This is a Huffman-compressed block,
476 using Huffman tree _from previous Huffman-compressed literals block_.
477 `Huffman_Tree_Description` will be skipped.
478 Note: If this mode is triggered without any previous Huffman-table in the frame
479 (or [dictionary](#dictionary-format)), this should be treated as data corruption.
483 `Size_Format` is divided into 2 families :
485 - For `Raw_Literals_Block` and `RLE_Literals_Block`,
486 it's only necessary to decode `Regenerated_Size`.
487 There is no `Compressed_Size` field.
488 - For `Compressed_Block` and `Treeless_Literals_Block`,
489 it's required to decode both `Compressed_Size`
490 and `Regenerated_Size` (the decompressed size).
491 It's also necessary to decode the number of streams (1 or 4).
493 For values spanning several bytes, convention is __little-endian__.
495 __`Size_Format` for `Raw_Literals_Block` and `RLE_Literals_Block`__ :
497 `Size_Format` uses 1 _or_ 2 bits.
498 Its value is : `Size_Format = (Literals_Section_Header[0]>>2) & 3`
500 - `Size_Format` == 00 or 10 : `Size_Format` uses 1 bit.
501 `Regenerated_Size` uses 5 bits (0-31).
502 `Literals_Section_Header` uses 1 byte.
503 `Regenerated_Size = Literals_Section_Header[0]>>3`
504 - `Size_Format` == 01 : `Size_Format` uses 2 bits.
505 `Regenerated_Size` uses 12 bits (0-4095).
506 `Literals_Section_Header` uses 2 bytes.
507 `Regenerated_Size = (Literals_Section_Header[0]>>4) + (Literals_Section_Header[1]<<4)`
508 - `Size_Format` == 11 : `Size_Format` uses 2 bits.
509 `Regenerated_Size` uses 20 bits (0-1048575).
510 `Literals_Section_Header` uses 3 bytes.
511 `Regenerated_Size = (Literals_Section_Header[0]>>4) + (Literals_Section_Header[1]<<4) + (Literals_Section_Header[2]<<12)`
513 Only Stream1 is present for these cases.
514 Note : it's allowed to represent a short value (for example `27`)
515 using a long format, even if it's less efficient.
517 __`Size_Format` for `Compressed_Literals_Block` and `Treeless_Literals_Block`__ :
519 `Size_Format` always uses 2 bits.
521 - `Size_Format` == 00 : _A single stream_.
522 Both `Regenerated_Size` and `Compressed_Size` use 10 bits (0-1023).
523 `Literals_Section_Header` uses 3 bytes.
524 - `Size_Format` == 01 : 4 streams.
525 Both `Regenerated_Size` and `Compressed_Size` use 10 bits (6-1023).
526 `Literals_Section_Header` uses 3 bytes.
527 - `Size_Format` == 10 : 4 streams.
528 Both `Regenerated_Size` and `Compressed_Size` use 14 bits (6-16383).
529 `Literals_Section_Header` uses 4 bytes.
530 - `Size_Format` == 11 : 4 streams.
531 Both `Regenerated_Size` and `Compressed_Size` use 18 bits (6-262143).
532 `Literals_Section_Header` uses 5 bytes.
534 Both `Compressed_Size` and `Regenerated_Size` fields follow __little-endian__ convention.
535 Note: `Compressed_Size` __includes__ the size of the Huffman Tree description
536 _when_ it is present.
537 Note 2: `Compressed_Size` can never be `==0`.
538 Even in single-stream scenario, assuming an empty content, it must be `>=1`,
539 since it contains at least the final end bit flag.
540 In 4-streams scenario, a valid `Compressed_Size` is necessarily `>= 10`
541 (6 bytes for the jump table, + 4x1 bytes for the 4 streams).
543 4 streams is faster than 1 stream in decompression speed,
544 by exploiting instruction level parallelism.
545 But it's also more expensive,
546 costing on average ~7.3 bytes more than the 1 stream mode, mostly from the jump table.
548 In general, use the 4 streams mode when there are more literals to decode,
549 to favor higher decompression speeds.
550 Note that beyond >1KB of literals, the 4 streams mode is compulsory.
552 Note that a minimum of 6 bytes is required for the 4 streams mode.
553 That's a technical minimum, but it's not recommended to employ the 4 streams mode
554 for such a small quantity, that would be wasteful.
555 A more practical lower bound would be around ~256 bytes.
557 #### Raw Literals Block
558 The data in Stream1 is `Regenerated_Size` bytes long,
559 it contains the raw literals data to be used during [Sequence Execution].
561 #### RLE Literals Block
562 Stream1 consists of a single byte which should be repeated `Regenerated_Size` times
563 to generate the decoded literals.
565 #### Compressed Literals Block and Treeless Literals Block
566 Both of these modes contain Huffman encoded data.
568 For `Treeless_Literals_Block`,
569 the Huffman table comes from previously compressed literals block,
570 or from a dictionary.
573 ### `Huffman_Tree_Description`
574 This section is only present when `Literals_Block_Type` type is `Compressed_Literals_Block` (`2`).
575 The tree describes the weights of all literals symbols that can be present in the literals block, at least 2 and up to 256.
576 The format of the Huffman tree description can be found at [Huffman Tree description](#huffman-tree-description).
577 The size of `Huffman_Tree_Description` is determined during decoding process,
578 it must be used to determine where streams begin.
579 `Total_Streams_Size = Compressed_Size - Huffman_Tree_Description_Size`.
583 The Jump Table is only present when there are 4 Huffman-coded streams.
585 Reminder : Huffman compressed data consists of either 1 or 4 streams.
587 If only one stream is present, it is a single bitstream occupying the entire
588 remaining portion of the literals block, encoded as described in
589 [Huffman-Coded Streams](#huffman-coded-streams).
591 If there are four streams, `Literals_Section_Header` only provided
592 enough information to know the decompressed and compressed sizes
593 of all four streams _combined_.
594 The decompressed size of _each_ stream is equal to `(Regenerated_Size+3)/4`,
595 except for the last stream which may be up to 3 bytes smaller,
596 to reach a total decompressed size as specified in `Regenerated_Size`.
598 The compressed size of each stream is provided explicitly in the Jump Table.
599 Jump Table is 6 bytes long, and consists of three 2-byte __little-endian__ fields,
600 describing the compressed sizes of the first three streams.
601 `Stream4_Size` is computed from `Total_Streams_Size` minus sizes of other streams:
603 `Stream4_Size = Total_Streams_Size - 6 - Stream1_Size - Stream2_Size - Stream3_Size`.
605 `Stream4_Size` is necessarily `>= 1`. Therefore,
606 if `Total_Streams_Size < Stream1_Size + Stream2_Size + Stream3_Size + 6 + 1`,
607 data is considered corrupted.
609 Each of these 4 bitstreams is then decoded independently as a Huffman-Coded stream,
610 as described in [Huffman-Coded Streams](#huffman-coded-streams)
615 A compressed block is a succession of _sequences_ .
616 A sequence is a literal copy command, followed by a match copy command.
617 A literal copy command specifies a length.
618 It is the number of bytes to be copied (or extracted) from the Literals Section.
619 A match copy command specifies an offset and a length.
621 When all _sequences_ are decoded,
622 if there are literals left in the _literals section_,
623 these bytes are added at the end of the block.
625 This is described in more detail in [Sequence Execution](#sequence-execution).
627 The `Sequences_Section` regroup all symbols required to decode commands.
628 There are 3 symbol types : literals lengths, offsets and match lengths.
629 They are encoded together, interleaved, in a single _bitstream_.
631 The `Sequences_Section` starts by a header,
632 followed by optional probability tables for each symbol type,
633 followed by the bitstream.
635 | `Sequences_Section_Header` | [`Literals_Length_Table`] | [`Offset_Table`] | [`Match_Length_Table`] | bitStream |
636 | -------------------------- | ------------------------- | ---------------- | ---------------------- | --------- |
638 To decode the `Sequences_Section`, it's required to know its size.
639 Its size is deduced from the size of `Literals_Section`:
640 `Sequences_Section_Size = Block_Size - Literals_Section_Size`.
643 #### `Sequences_Section_Header`
646 - `Number_of_Sequences`
647 - Symbol compression modes
649 __`Number_of_Sequences`__
651 This is a variable size field using between 1 and 3 bytes.
652 Let's call its first byte `byte0`.
653 - `if (byte0 < 128)` : `Number_of_Sequences = byte0` . Uses 1 byte.
654 - `if (byte0 < 255)` : `Number_of_Sequences = ((byte0 - 0x80) << 8) + byte1`. Uses 2 bytes.
655 Note that the 2 bytes format fully overlaps the 1 byte format.
656 - `if (byte0 == 255)`: `Number_of_Sequences = byte1 + (byte2<<8) + 0x7F00`. Uses 3 bytes.
658 `if (Number_of_Sequences == 0)` : there are no sequences.
659 The sequence section stops immediately,
660 FSE tables used in `Repeat_Mode` aren't updated.
661 Block's decompressed content is defined solely by the Literals Section content.
663 __Symbol compression modes__
665 This is a single byte, defining the compression mode of each symbol type.
667 |Bit number| 7-6 | 5-4 | 3-2 | 1-0 |
668 | -------- | ----------------------- | -------------- | -------------------- | ---------- |
669 |Field name| `Literals_Lengths_Mode` | `Offsets_Mode` | `Match_Lengths_Mode` | `Reserved` |
671 The last field, `Reserved`, must be all-zeroes.
673 `Literals_Lengths_Mode`, `Offsets_Mode` and `Match_Lengths_Mode` define the `Compression_Mode` of
674 literals lengths, offsets, and match lengths symbols respectively.
676 They follow the same enumeration :
678 | Value | 0 | 1 | 2 | 3 |
679 | ------------------ | ----------------- | ---------- | --------------------- | ------------- |
680 | `Compression_Mode` | `Predefined_Mode` | `RLE_Mode` | `FSE_Compressed_Mode` | `Repeat_Mode` |
682 - `Predefined_Mode` : A predefined FSE distribution table is used, defined in
683 [default distributions](#default-distributions).
684 No distribution table will be present.
685 - `RLE_Mode` : The table description consists of a single byte, which contains the symbol's value.
686 This symbol will be used for all sequences.
687 - `FSE_Compressed_Mode` : standard FSE compression.
688 A distribution table will be present.
689 The format of this distribution table is described in [FSE Table Description](#fse-table-description).
690 Note that the maximum allowed accuracy log for literals length and match length tables is 9,
691 and the maximum accuracy log for the offsets table is 8.
692 `FSE_Compressed_Mode` must not be used when only one symbol is present,
693 `RLE_Mode` should be used instead (although any other mode will work).
694 - `Repeat_Mode` : The table used in the previous `Compressed_Block` with `Number_of_Sequences > 0` will be used again,
695 or if this is the first block, table in the dictionary will be used.
696 Note that this includes `RLE_mode`, so if `Repeat_Mode` follows `RLE_Mode`, the same symbol will be repeated.
697 It also includes `Predefined_Mode`, in which case `Repeat_Mode` will have same outcome as `Predefined_Mode`.
698 No distribution table will be present.
699 If this mode is used without any previous sequence table in the frame
700 (nor [dictionary](#dictionary-format)) to repeat, this should be treated as corruption.
702 #### The codes for literals lengths, match lengths, and offsets.
704 Each symbol is a _code_ in its own context,
705 which specifies `Baseline` and `Number_of_Bits` to add.
706 _Codes_ are FSE compressed,
707 and interleaved with raw additional bits in the same bitstream.
709 ##### Literals length codes
711 Literals length codes are values ranging from `0` to `35` included.
712 They define lengths from 0 to 131071 bytes.
713 The literals length is equal to the decoded `Baseline` plus
714 the result of reading `Number_of_Bits` bits from the bitstream,
715 as a __little-endian__ value.
717 | `Literals_Length_Code` | 0-15 |
718 | ---------------------- | ---------------------- |
719 | length | `Literals_Length_Code` |
720 | `Number_of_Bits` | 0 |
722 | `Literals_Length_Code` | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
723 | ---------------------- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
724 | `Baseline` | 16 | 18 | 20 | 22 | 24 | 28 | 32 | 40 |
725 | `Number_of_Bits` | 1 | 1 | 1 | 1 | 2 | 2 | 3 | 3 |
727 | `Literals_Length_Code` | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
728 | ---------------------- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
729 | `Baseline` | 48 | 64 | 128 | 256 | 512 | 1024 | 2048 | 4096 |
730 | `Number_of_Bits` | 4 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
732 | `Literals_Length_Code` | 32 | 33 | 34 | 35 |
733 | ---------------------- | ---- | ---- | ---- | ---- |
734 | `Baseline` | 8192 |16384 |32768 |65536 |
735 | `Number_of_Bits` | 13 | 14 | 15 | 16 |
738 ##### Match length codes
740 Match length codes are values ranging from `0` to `52` included.
741 They define lengths from 3 to 131074 bytes.
742 The match length is equal to the decoded `Baseline` plus
743 the result of reading `Number_of_Bits` bits from the bitstream,
744 as a __little-endian__ value.
746 | `Match_Length_Code` | 0-31 |
747 | ------------------- | ----------------------- |
748 | value | `Match_Length_Code` + 3 |
749 | `Number_of_Bits` | 0 |
751 | `Match_Length_Code` | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 |
752 | ------------------- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
753 | `Baseline` | 35 | 37 | 39 | 41 | 43 | 47 | 51 | 59 |
754 | `Number_of_Bits` | 1 | 1 | 1 | 1 | 2 | 2 | 3 | 3 |
756 | `Match_Length_Code` | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 |
757 | ------------------- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
758 | `Baseline` | 67 | 83 | 99 | 131 | 259 | 515 | 1027 | 2051 |
759 | `Number_of_Bits` | 4 | 4 | 5 | 7 | 8 | 9 | 10 | 11 |
761 | `Match_Length_Code` | 48 | 49 | 50 | 51 | 52 |
762 | ------------------- | ---- | ---- | ---- | ---- | ---- |
763 | `Baseline` | 4099 | 8195 |16387 |32771 |65539 |
764 | `Number_of_Bits` | 12 | 13 | 14 | 15 | 16 |
768 Offset codes are values ranging from `0` to `N`.
770 A decoder is free to limit its maximum `N` supported.
771 Recommendation is to support at least up to `22`.
772 For information, at the time of this writing.
773 the reference decoder supports a maximum `N` value of `31`.
775 An offset code is also the number of additional bits to read in __little-endian__ fashion,
776 and can be translated into an `Offset_Value` using the following formulas :
779 Offset_Value = (1 << offsetCode) + readNBits(offsetCode);
780 if (Offset_Value > 3) offset = Offset_Value - 3;
782 It means that maximum `Offset_Value` is `(2^(N+1))-1`
783 supporting back-reference distances up to `(2^(N+1))-4`,
784 but is limited by [maximum back-reference distance](#window_descriptor).
786 `Offset_Value` from 1 to 3 are special : they define "repeat codes".
787 This is described in more detail in [Repeat Offsets](#repeat-offsets).
789 #### Decoding Sequences
790 FSE bitstreams are read in reverse direction than written. In zstd,
791 the compressor writes bits forward into a block and the decompressor
792 must read the bitstream _backwards_.
794 To find the start of the bitstream it is therefore necessary to
795 know the offset of the last byte of the block which can be found
796 by counting `Block_Size` bytes after the block header.
798 After writing the last bit containing information, the compressor
799 writes a single `1`-bit and then fills the byte with 0-7 `0` bits of
800 padding. The last byte of the compressed bitstream cannot be `0` for
803 When decompressing, the last byte containing the padding is the first
804 byte to read. The decompressor needs to skip 0-7 initial `0`-bits and
805 the first `1`-bit it occurs. Afterwards, the useful part of the bitstream
808 FSE decoding requires a 'state' to be carried from symbol to symbol.
809 For more explanation on FSE decoding, see the [FSE section](#fse).
811 For sequence decoding, a separate state keeps track of each
812 literal lengths, offsets, and match lengths symbols.
813 Some FSE primitives are also used.
814 For more details on the operation of these primitives, see the [FSE section](#fse).
816 ##### Starting states
817 The bitstream starts with initial FSE state values,
818 each using the required number of bits in their respective _accuracy_,
819 decoded previously from their normalized distribution.
821 It starts by `Literals_Length_State`,
822 followed by `Offset_State`,
823 and finally `Match_Length_State`.
825 Reminder : always keep in mind that all values are read _backward_,
826 so the 'start' of the bitstream is at the highest position in memory,
827 immediately before the last `1`-bit for padding.
829 After decoding the starting states, a single sequence is decoded
830 `Number_Of_Sequences` times.
831 These sequences are decoded in order from first to last.
832 Since the compressor writes the bitstream in the forward direction,
833 this means the compressor must encode the sequences starting with the last
834 one and ending with the first.
836 ##### Decoding a sequence
837 For each of the symbol types, the FSE state can be used to determine the appropriate code.
838 The code then defines the `Baseline` and `Number_of_Bits` to read for each type.
839 See the [description of the codes] for how to determine these values.
841 [description of the codes]: #the-codes-for-literals-lengths-match-lengths-and-offsets
843 Decoding starts by reading the `Number_of_Bits` required to decode `Offset`.
844 It then does the same for `Match_Length`, and then for `Literals_Length`.
845 This sequence is then used for [sequence execution](#sequence-execution).
847 If it is not the last sequence in the block,
848 the next operation is to update states.
849 Using the rules pre-calculated in the decoding tables,
850 `Literals_Length_State` is updated,
851 followed by `Match_Length_State`,
852 and then `Offset_State`.
853 See the [FSE section](#fse) for details on how to update states from the bitstream.
855 This operation will be repeated `Number_of_Sequences` times.
856 At the end, the bitstream shall be entirely consumed,
857 otherwise the bitstream is considered corrupted.
859 #### Default Distributions
860 If `Predefined_Mode` is selected for a symbol type,
861 its FSE decoding table is generated from a predefined distribution table defined here.
862 For details on how to convert this distribution into a decoding table, see the [FSE section].
864 [FSE section]: #from-normalized-distribution-to-decoding-tables
866 ##### Literals Length
867 The decoding table uses an accuracy log of 6 bits (64 states).
869 short literalsLength_defaultDistribution[36] =
870 { 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
871 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
876 The decoding table uses an accuracy log of 6 bits (64 states).
878 short matchLengths_defaultDistribution[53] =
879 { 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
880 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
881 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,
886 The decoding table uses an accuracy log of 5 bits (32 states),
887 and supports a maximum `N` value of 28, allowing offset values up to 536,870,908 .
889 If any sequence in the compressed block requires a larger offset than this,
890 it's not possible to use the default distribution to represent it.
892 short offsetCodes_defaultDistribution[29] =
893 { 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
894 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1 };
900 Once literals and sequences have been decoded,
901 they are combined to produce the decoded content of a block.
903 Each sequence consists of a tuple of (`literals_length`, `offset_value`, `match_length`),
904 decoded as described in the [Sequences Section](#sequences-section).
905 To execute a sequence, first copy `literals_length` bytes
906 from the decoded literals to the output.
908 Then `match_length` bytes are copied from previous decoded data.
909 The offset to copy from is determined by `offset_value`:
910 if `offset_value > 3`, then the offset is `offset_value - 3`.
911 If `offset_value` is from 1-3, the offset is a special repeat offset value.
912 See the [repeat offset](#repeat-offsets) section for how the offset is determined
915 The offset is defined as from the current position, so an offset of 6
916 and a match length of 3 means that 3 bytes should be copied from 6 bytes back.
917 Note that all offsets leading to previously decoded data
918 must be smaller than `Window_Size` defined in `Frame_Header_Descriptor`.
921 As seen in [Sequence Execution](#sequence-execution),
922 the first 3 values define a repeated offset and we will call them
923 `Repeated_Offset1`, `Repeated_Offset2`, and `Repeated_Offset3`.
924 They are sorted in recency order, with `Repeated_Offset1` meaning "most recent one".
926 If `offset_value == 1`, then the offset used is `Repeated_Offset1`, etc.
928 There is an exception though, when current sequence's `literals_length = 0`.
929 In this case, repeated offsets are shifted by one,
930 so an `offset_value` of 1 means `Repeated_Offset2`,
931 an `offset_value` of 2 means `Repeated_Offset3`,
932 and an `offset_value` of 3 means `Repeated_Offset1 - 1`.
934 In the final case, if `Repeated_Offset1 - 1` evaluates to 0, then the
935 data is considered corrupted.
937 For the first block, the starting offset history is populated with following values :
938 `Repeated_Offset1`=1, `Repeated_Offset2`=4, `Repeated_Offset3`=8,
939 unless a dictionary is used, in which case they come from the dictionary.
941 Then each block gets its starting offset history from the ending values of the most recent `Compressed_Block`.
942 Note that blocks which are not `Compressed_Block` are skipped, they do not contribute to offset history.
944 [Offset Codes]: #offset-codes
946 ###### Offset updates rules
948 During the execution of the sequences of a `Compressed_Block`, the
949 `Repeated_Offsets`' values are kept up to date, so that they always represent
950 the three most-recently used offsets. In order to achieve that, they are
951 updated after executing each sequence in the following way:
953 When the sequence's `offset_value` does not refer to one of the
954 `Repeated_Offsets`--when it has value greater than 3, or when it has value 3
955 and the sequence's `literals_length` is zero--the `Repeated_Offsets`' values
956 are shifted back one, and `Repeated_Offset1` takes on the value of the
959 Otherwise, when the sequence's `offset_value` refers to one of the
960 `Repeated_Offsets`--when it has value 1 or 2, or when it has value 3 and the
961 sequence's `literals_length` is non-zero--the `Repeated_Offsets` are re-ordered
962 so that `Repeated_Offset1` takes on the value of the used Repeated_Offset, and
963 the existing values are pushed back from the first `Repeated_Offset` through to
964 the `Repeated_Offset` selected by the `offset_value`. This effectively performs
965 a single-stepped wrapping rotation of the values of these offsets, so that
966 their order again reflects the recency of their use.
968 The following table shows the values of the `Repeated_Offsets` as a series of
969 sequences are applied to them:
971 | `offset_value` | `literals_length` | `Repeated_Offset1` | `Repeated_Offset2` | `Repeated_Offset3` | Comment |
972 |:--------------:|:-----------------:|:------------------:|:------------------:|:------------------:|:-----------------------:|
973 | | | 1 | 4 | 8 | starting values |
974 | 1114 | 11 | 1111 | 1 | 4 | non-repeat |
975 | 1 | 22 | 1111 | 1 | 4 | repeat 1: no change |
976 | 2225 | 22 | 2222 | 1111 | 1 | non-repeat |
977 | 1114 | 111 | 1111 | 2222 | 1111 | non-repeat |
978 | 3336 | 33 | 3333 | 1111 | 2222 | non-repeat |
979 | 2 | 22 | 1111 | 3333 | 2222 | repeat 2: swap 1 & 2 |
980 | 3 | 33 | 2222 | 1111 | 3333 | repeat 3: rotate 3 to 1 |
981 | 3 | 0 | 2221 | 2222 | 1111 | special case : insert `repeat1 - 1` |
982 | 1 | 0 | 2222 | 2221 | 1111 | == repeat 2 |
988 | `Magic_Number` | `Frame_Size` | `User_Data` |
989 |:--------------:|:------------:|:-----------:|
990 | 4 bytes | 4 bytes | n bytes |
992 Skippable frames allow the insertion of user-defined metadata
993 into a flow of concatenated frames.
995 Skippable frames defined in this specification are compatible with [LZ4] ones.
997 [LZ4]:https://lz4.github.io/lz4/
999 From a compliant decoder perspective, skippable frames need just be skipped,
1000 and their content ignored, resuming decoding after the skippable frame.
1002 It can be noted that a skippable frame
1003 can be used to watermark a stream of concatenated frames
1004 embedding any kind of tracking information (even just a UUID).
1005 Users wary of such possibility should scan the stream of concatenated frames
1006 in an attempt to detect such frame for analysis or removal.
1010 4 Bytes, __little-endian__ format.
1011 Value : 0x184D2A5?, which means any value from 0x184D2A50 to 0x184D2A5F.
1012 All 16 values are valid to identify a skippable frame.
1013 This specification doesn't detail any specific tagging for skippable frames.
1017 This is the size, in bytes, of the following `User_Data`
1018 (without including the magic number nor the size field itself).
1019 This field is represented using 4 Bytes, __little-endian__ format, unsigned 32-bits.
1020 This means `User_Data` can’t be bigger than (2^32-1) bytes.
1024 The `User_Data` can be anything. Data will just be skipped by the decoder.
1030 Two types of entropy encoding are used by the Zstandard format:
1031 FSE, and Huffman coding.
1032 Huffman is used to compress literals,
1033 while FSE is used for all other symbols
1034 (`Literals_Length_Code`, `Match_Length_Code`, offset codes)
1035 and to compress Huffman headers.
1040 FSE, short for Finite State Entropy, is an entropy codec based on [ANS].
1041 FSE encoding/decoding involves a state that is carried over between symbols,
1042 so decoding must be done in the opposite direction as encoding.
1043 Therefore, all FSE bitstreams are read from end to beginning.
1044 Note that the order of the bits in the stream is not reversed,
1045 we just read the elements in the reverse order they are written.
1047 For additional details on FSE, see [Finite State Entropy].
1049 [Finite State Entropy]:https://github.com/Cyan4973/FiniteStateEntropy/
1051 FSE decoding involves a decoding table which has a power of 2 size, and contain three elements:
1052 `Symbol`, `Num_Bits`, and `Baseline`.
1053 The `log2` of the table size is its `Accuracy_Log`.
1054 An FSE state value represents an index in this table.
1056 To obtain the initial state value, consume `Accuracy_Log` bits from the stream as a __little-endian__ value.
1057 The next symbol in the stream is the `Symbol` indicated in the table for that state.
1058 To obtain the next state value,
1059 the decoder should consume `Num_Bits` bits from the stream as a __little-endian__ value and add it to `Baseline`.
1061 [ANS]: https://en.wikipedia.org/wiki/Asymmetric_Numeral_Systems
1063 ### FSE Table Description
1064 To decode FSE streams, it is necessary to construct the decoding table.
1065 The Zstandard format encodes FSE table descriptions as follows:
1067 An FSE distribution table describes the probabilities of all symbols
1068 from `0` to the last present one (included)
1069 on a normalized scale of `1 << Accuracy_Log` .
1070 Note that there must be two or more symbols with nonzero probability.
1072 It's a bitstream which is read forward, in __little-endian__ fashion.
1073 It's not necessary to know bitstream exact size,
1074 it will be discovered and reported by the decoding process.
1076 The bitstream starts by reporting on which scale it operates.
1077 Let's `low4Bits` designate the lowest 4 bits of the first byte :
1078 `Accuracy_Log = low4bits + 5`.
1080 Then follows each symbol value, from `0` to last present one.
1081 The number of bits used by each field is variable.
1084 - Remaining probabilities + 1 :
1086 Presuming an `Accuracy_Log` of 8,
1087 and presuming 100 probabilities points have already been distributed,
1088 the decoder may read any value from `0` to `256 - 100 + 1 == 157` (inclusive).
1089 Therefore, it may read up to `log2sup(157) == 8` bits, where `log2sup(N)`
1090 is the smallest integer `T` that satisfies `(1 << T) > N`.
1092 - Value decoded : small values use 1 less bit :
1094 Presuming values from 0 to 157 (inclusive) are possible,
1095 255-157 = 98 values are remaining in an 8-bits field.
1096 They are used this way :
1097 first 98 values (hence from 0 to 97) use only 7 bits,
1098 values from 98 to 157 use 8 bits.
1099 This is achieved through this scheme :
1101 | Value read | Value decoded | Number of bits used |
1102 | ---------- | ------------- | ------------------- |
1103 | 0 - 97 | 0 - 97 | 7 |
1104 | 98 - 127 | 98 - 127 | 8 |
1105 | 128 - 225 | 0 - 97 | 7 |
1106 | 226 - 255 | 128 - 157 | 8 |
1108 Symbols probabilities are read one by one, in order.
1110 Probability is obtained from Value decoded by following formula :
1113 It means value `0` becomes negative probability `-1`.
1114 `-1` is a special probability, which means "less than 1".
1115 Its effect on distribution table is described in the [next section].
1116 For the purpose of calculating total allocated probability points, it counts as one.
1118 [next section]:#from-normalized-distribution-to-decoding-tables
1120 When a symbol has a __probability__ of `zero`,
1121 it is followed by a 2-bits repeat flag.
1122 This repeat flag tells how many probabilities of zeroes follow the current one.
1123 It provides a number ranging from 0 to 3.
1124 If it is a 3, another 2-bits repeat flag follows, and so on.
1126 When last symbol reaches cumulated total of `1 << Accuracy_Log`,
1127 decoding is complete.
1128 If the last symbol makes cumulated total go above `1 << Accuracy_Log`,
1129 distribution is considered corrupted.
1130 If this process results in a non-zero probability for a value outside of the
1131 valid range of values that the FSE table is defined for, even if that value is
1132 not used, then the data is considered corrupted.
1134 Then the decoder can tell how many bytes were used in this process,
1135 and how many symbols are present.
1136 The bitstream consumes a round number of bytes.
1137 Any remaining bit within the last byte is just unused.
1139 #### From normalized distribution to decoding tables
1141 The distribution of normalized probabilities is enough
1142 to create a unique decoding table.
1144 It follows the following build rule :
1146 The table has a size of `Table_Size = 1 << Accuracy_Log`.
1147 Each cell describes the symbol decoded,
1148 and instructions to get the next state (`Number_of_Bits` and `Baseline`).
1150 Symbols are scanned in their natural order for "less than 1" probabilities.
1151 Symbols with this probability are being attributed a single cell,
1152 starting from the end of the table and retreating.
1153 These symbols define a full state reset, reading `Accuracy_Log` bits.
1155 Then, all remaining symbols, sorted in natural order, are allocated cells.
1156 Starting from symbol `0` (if it exists), and table position `0`,
1157 each symbol gets allocated as many cells as its probability.
1158 Cell allocation is spread, not linear :
1159 each successor position follows this rule :
1162 position += (tableSize>>1) + (tableSize>>3) + 3;
1163 position &= tableSize-1;
1166 A position is skipped if already occupied by a "less than 1" probability symbol.
1167 `position` does not reset between symbols, it simply iterates through
1168 each position in the table, switching to the next symbol when enough
1169 states have been allocated to the current one.
1171 The process guarantees that the table is entirely filled.
1172 Each cell corresponds to a state value, which contains the symbol being decoded.
1174 To add the `Number_of_Bits` and `Baseline` required to retrieve next state,
1175 it's first necessary to sort all occurrences of each symbol in state order.
1176 Lower states will need 1 more bit than higher ones.
1177 The process is repeated for each symbol.
1180 Presuming a symbol has a probability of 5,
1181 it receives 5 cells, corresponding to 5 state values.
1182 These state values are then sorted in natural order.
1184 Next power of 2 after 5 is 8.
1185 Space of probabilities must be divided into 8 equal parts.
1186 Presuming the `Accuracy_Log` is 7, it defines a space of 128 states.
1187 Divided by 8, each share is 16 large.
1189 In order to reach 8 shares, 8-5=3 lowest states will count "double",
1190 doubling their shares (32 in width), hence requiring one more bit.
1192 Baseline is assigned starting from the higher states using fewer bits,
1193 increasing at each state, then resuming at the first state,
1194 each state takes its allocated width from Baseline.
1196 | state order | 0 | 1 | 2 | 3 | 4 |
1197 | ---------------- | ----- | ----- | ------ | ---- | ------ |
1198 | state value | 1 | 39 | 77 | 84 | 122 |
1199 | width | 32 | 32 | 32 | 16 | 16 |
1200 | `Number_of_Bits` | 5 | 5 | 5 | 4 | 4 |
1201 | range number | 2 | 4 | 6 | 0 | 1 |
1202 | `Baseline` | 32 | 64 | 96 | 0 | 16 |
1203 | range | 32-63 | 64-95 | 96-127 | 0-15 | 16-31 |
1205 During decoding, the next state value is determined from current state value,
1206 by reading the required `Number_of_Bits`, and adding the specified `Baseline`.
1208 See [Appendix A] for the results of this process applied to the default distributions.
1210 [Appendix A]: #appendix-a---decoding-tables-for-predefined-codes
1215 Zstandard Huffman-coded streams are read backwards,
1216 similar to the FSE bitstreams.
1217 Therefore, to find the start of the bitstream, it is required to
1218 know the offset of the last byte of the Huffman-coded stream.
1220 After writing the last bit containing information, the compressor
1221 writes a single `1`-bit and then fills the byte with 0-7 `0` bits of
1222 padding. The last byte of the compressed bitstream cannot be `0` for
1225 When decompressing, the last byte containing the padding is the first
1226 byte to read. The decompressor needs to skip 0-7 initial `0`-bits and
1227 the first `1`-bit it occurs. Afterwards, the useful part of the bitstream
1230 The bitstream contains Huffman-coded symbols in __little-endian__ order,
1231 with the codes defined by the method below.
1233 ### Huffman Tree Description
1235 Prefix coding represents symbols from an a priori known alphabet
1236 by bit sequences (codewords), one codeword for each symbol,
1237 in a manner such that different symbols may be represented
1238 by bit sequences of different lengths,
1239 but a parser can always parse an encoded string
1240 unambiguously symbol-by-symbol.
1242 Given an alphabet with known symbol frequencies,
1243 the Huffman algorithm allows the construction of an optimal prefix code
1244 using the fewest bits of any possible prefix codes for that alphabet.
1246 Prefix code must not exceed a maximum code length.
1247 More bits improve accuracy but cost more header size,
1248 and require more memory or more complex decoding operations.
1249 This specification limits maximum code length to 11 bits.
1253 All literal values from zero (included) to last present one (excluded)
1254 are represented by `Weight` with values from `0` to `Max_Number_of_Bits`.
1255 Transformation from `Weight` to `Number_of_Bits` follows this formula :
1257 Number_of_Bits = Weight ? (Max_Number_of_Bits + 1 - Weight) : 0
1259 When a literal value is not present, it receives a `Weight` of 0.
1260 The least frequent symbol receives a `Weight` of 1.
1261 If no literal has a `Weight` of 1, then the data is considered corrupted.
1262 If there are not at least two literals with non-zero `Weight`, then the data
1263 is considered corrupted.
1264 The most frequent symbol receives a `Weight` anywhere between 1 and 11 (max).
1265 The last symbol's `Weight` is deduced from previously retrieved Weights,
1266 by completing to the nearest power of 2. It's necessarily non 0.
1267 If it's not possible to reach a clean power of 2 with a single `Weight` value,
1268 the Huffman Tree Description is considered invalid.
1269 This final power of 2 gives `Max_Number_of_Bits`, the depth of the current tree.
1270 `Max_Number_of_Bits` must be <= 11,
1271 otherwise the representation is considered corrupted.
1274 Let's presume the following Huffman tree must be described :
1276 | literal value | 0 | 1 | 2 | 3 | 4 | 5 |
1277 | ---------------- | --- | --- | --- | --- | --- | --- |
1278 | `Number_of_Bits` | 1 | 2 | 3 | 0 | 4 | 4 |
1280 The tree depth is 4, since its longest elements uses 4 bits
1281 (longest elements are the one with smallest frequency).
1282 Literal value `5` will not be listed, as it can be determined from previous values 0-4,
1283 nor will values above `5` as they are all 0.
1284 Values from `0` to `4` will be listed using `Weight` instead of `Number_of_Bits`.
1287 Weight = Number_of_Bits ? (Max_Number_of_Bits + 1 - Number_of_Bits) : 0
1289 It gives the following series of weights :
1291 | literal value | 0 | 1 | 2 | 3 | 4 |
1292 | ------------- | --- | --- | --- | --- | --- |
1293 | `Weight` | 4 | 3 | 2 | 0 | 1 |
1295 The decoder will do the inverse operation :
1296 having collected weights of literal symbols from `0` to `4`,
1297 it knows the last literal, `5`, is present with a non-zero `Weight`.
1298 The `Weight` of `5` can be determined by advancing to the next power of 2.
1299 The sum of `2^(Weight-1)` (excluding 0's) is :
1300 `8 + 4 + 2 + 0 + 1 = 15`.
1301 Nearest larger power of 2 value is 16.
1302 Therefore, `Max_Number_of_Bits = 4` and `Weight[5] = log_2(16 - 15) + 1 = 1`.
1304 #### Huffman Tree header
1306 This is a single byte value (0-255),
1307 which describes how the series of weights is encoded.
1309 - if `headerByte` < 128 :
1310 the series of weights is compressed using FSE (see below).
1311 The length of the FSE-compressed series is equal to `headerByte` (0-127).
1313 - if `headerByte` >= 128 :
1314 + the series of weights uses a direct representation,
1315 where each `Weight` is encoded directly as a 4 bits field (0-15).
1316 + They are encoded forward, 2 weights to a byte,
1317 first weight taking the top four bits and second one taking the bottom four.
1318 * e.g. the following operations could be used to read the weights:
1319 `Weight[0] = (Byte[0] >> 4), Weight[1] = (Byte[0] & 0xf)`, etc.
1320 + The full representation occupies `Ceiling(Number_of_Weights/2)` bytes,
1321 meaning it uses only full bytes even if `Number_of_Weights` is odd.
1322 + `Number_of_Weights = headerByte - 127`.
1323 * Note that maximum `Number_of_Weights` is 255-127 = 128,
1324 therefore, only up to 128 `Weight` can be encoded using direct representation.
1325 * Since the last non-zero `Weight` is _not_ encoded,
1326 this scheme is compatible with alphabet sizes of up to 129 symbols,
1327 hence including literal symbol 128.
1328 * If any literal symbol > 128 has a non-zero `Weight`,
1329 direct representation is not possible.
1330 In such case, it's necessary to use FSE compression.
1333 #### Finite State Entropy (FSE) compression of Huffman weights
1335 In this case, the series of Huffman weights is compressed using FSE compression.
1336 It's a single bitstream with 2 interleaved states,
1337 sharing a single distribution table.
1339 To decode an FSE bitstream, it is necessary to know its compressed size.
1340 Compressed size is provided by `headerByte`.
1341 It's also necessary to know its _maximum possible_ decompressed size,
1342 which is `255`, since literal values span from `0` to `255`,
1343 and last symbol's `Weight` is not represented.
1345 An FSE bitstream starts by a header, describing probabilities distribution.
1346 It will create a Decoding Table.
1347 For a list of Huffman weights, the maximum accuracy log is 6 bits.
1348 For more description see the [FSE header description](#fse-table-description)
1350 The Huffman header compression uses 2 states,
1351 which share the same FSE distribution table.
1352 The first state (`State1`) encodes the even indexed symbols,
1353 and the second (`State2`) encodes the odd indexed symbols.
1354 `State1` is initialized first, and then `State2`, and they take turns
1355 decoding a single symbol and updating their state.
1356 For more details on these FSE operations, see the [FSE section](#fse).
1358 The number of symbols to decode is determined
1359 by tracking bitStream overflow condition:
1360 If updating state after decoding a symbol would require more bits than
1361 remain in the stream, it is assumed that extra bits are 0. Then,
1362 symbols for each of the final states are decoded and the process is complete.
1364 If this process would produce more weights than the maximum number of decoded
1365 weights (255), then the data is considered corrupted.
1367 #### Conversion from weights to Huffman prefix codes
1369 All present symbols shall now have a `Weight` value.
1370 It is possible to transform weights into `Number_of_Bits`, using this formula:
1372 Number_of_Bits = (Weight>0) ? Max_Number_of_Bits + 1 - Weight : 0
1374 Symbols are sorted by `Weight`.
1375 Within same `Weight`, symbols keep natural sequential order.
1376 Symbols with a `Weight` of zero are removed.
1377 Then, starting from lowest `Weight`, prefix codes are distributed in sequential order.
1380 Let's presume the following list of weights has been decoded :
1382 | Literal | 0 | 1 | 2 | 3 | 4 | 5 |
1383 | -------- | --- | --- | --- | --- | --- | --- |
1384 | `Weight` | 4 | 3 | 2 | 0 | 1 | 1 |
1386 Sorted by weight and then natural sequential order,
1387 it gives the following distribution :
1389 | Literal | 3 | 4 | 5 | 2 | 1 | 0 |
1390 | ---------------- | --- | --- | --- | --- | --- | ---- |
1391 | `Weight` | 0 | 1 | 1 | 2 | 3 | 4 |
1392 | `Number_of_Bits` | 0 | 4 | 4 | 3 | 2 | 1 |
1393 | prefix codes | N/A | 0000| 0001| 001 | 01 | 1 |
1395 ### Huffman-coded Streams
1397 Given a Huffman decoding table,
1398 it's possible to decode a Huffman-coded stream.
1400 Each bitstream must be read _backward_,
1401 that is starting from the end down to the beginning.
1402 Therefore it's necessary to know the size of each bitstream.
1404 It's also necessary to know exactly which _bit_ is the last one.
1405 This is detected by a final bit flag :
1406 the highest bit of latest byte is a final-bit-flag.
1407 Consequently, a last byte of `0` is not possible.
1408 And the final-bit-flag itself is not part of the useful bitstream.
1409 Hence, the last byte contains between 0 and 7 useful bits.
1411 Starting from the end,
1412 it's possible to read the bitstream in a __little-endian__ fashion,
1413 keeping track of already used bits. Since the bitstream is encoded in reverse
1414 order, starting from the end read symbols in forward order.
1416 For example, if the literal sequence "0145" was encoded using above prefix code,
1417 it would be encoded (in reverse order) as:
1419 |Symbol | 5 | 4 | 1 | 0 | Padding |
1420 |--------|------|------|----|---|---------|
1421 |Encoding|`0000`|`0001`|`01`|`1`| `00001` |
1423 Resulting in following 2-bytes bitstream :
1428 Here is an alternative representation with the symbol codes separated by underscore:
1430 0001_0000 00001_1_01
1433 Reading highest `Max_Number_of_Bits` bits,
1434 it's possible to compare extracted value to decoding table,
1435 determining the symbol to decode and number of bits to discard.
1437 The process continues up to reading the required number of symbols per stream.
1438 If a bitstream is not entirely and exactly consumed,
1439 hence reaching exactly its beginning position with _all_ bits consumed,
1440 the decoding process is considered faulty.
1446 Zstandard is compatible with "raw content" dictionaries,
1447 free of any format restriction, except that they must be at least 8 bytes.
1448 These dictionaries function as if they were just the `Content` part
1449 of a formatted dictionary.
1451 But dictionaries created by `zstd --train` follow a format, described here.
1453 __Pre-requisites__ : a dictionary has a size,
1454 defined either by a buffer limit, or a file size.
1456 | `Magic_Number` | `Dictionary_ID` | `Entropy_Tables` | `Content` |
1457 | -------------- | --------------- | ---------------- | --------- |
1459 __`Magic_Number`__ : 4 bytes ID, value 0xEC30A437, __little-endian__ format
1461 __`Dictionary_ID`__ : 4 bytes, stored in __little-endian__ format.
1462 `Dictionary_ID` can be any value, except 0 (which means no `Dictionary_ID`).
1463 It's used by decoders to check if they use the correct dictionary.
1466 If the dictionary is going to be distributed in a public environment,
1467 the following ranges of `Dictionary_ID` are reserved for some future registrar
1468 and shall not be used :
1470 - low range : <= 32767
1471 - high range : >= (2^31)
1473 Outside of these ranges, any value of `Dictionary_ID`
1474 which is both `>= 32768` and `< (1<<31)` can be used freely,
1475 even in public environment.
1478 __`Entropy_Tables`__ : follow the same format as tables in [compressed blocks].
1479 See the relevant [FSE](#fse-table-description)
1480 and [Huffman](#huffman-tree-description) sections for how to decode these tables.
1481 They are stored in following order :
1482 Huffman tables for literals, FSE table for offsets,
1483 FSE table for match lengths, and FSE table for literals lengths.
1484 These tables populate the Repeat Stats literals mode and
1485 Repeat distribution mode for sequence decoding.
1486 It's finally followed by 3 offset values, populating recent offsets (instead of using `{1,4,8}`),
1487 stored in order, 4-bytes __little-endian__ each, for a total of 12 bytes.
1488 Each recent offset must have a value <= dictionary content size, and cannot equal 0.
1490 __`Content`__ : The rest of the dictionary is its content.
1491 The content act as a "past" in front of data to compress or decompress,
1492 so it can be referenced in sequence commands.
1493 As long as the amount of data decoded from this frame is less than or
1494 equal to `Window_Size`, sequence commands may specify offsets longer
1495 than the total length of decoded output so far to reference back to the
1496 dictionary, even parts of the dictionary with offsets larger than `Window_Size`.
1497 After the total output has surpassed `Window_Size` however,
1498 this is no longer allowed and the dictionary is no longer accessible.
1500 [compressed blocks]: #the-format-of-compressed_block
1502 If a dictionary is provided by an external source,
1503 it should be loaded with great care, its content considered untrusted.
1507 Appendix A - Decoding tables for predefined codes
1508 -------------------------------------------------
1510 This appendix contains FSE decoding tables
1511 for the predefined literal length, match length, and offset codes.
1512 The tables have been constructed using the algorithm as given above in chapter
1513 "from normalized distribution to decoding tables".
1514 The tables here can be used as examples
1515 to crosscheck that an implementation build its decoding tables correctly.
1517 #### Literal Length Code:
1519 | State | Symbol | Number_Of_Bits | Base |
1520 | ----- | ------ | -------------- | ---- |
1538 | 17 | 25 | 5 | 32 |
1550 | 29 | 10 | 5 | 32 |
1553 | 32 | 16 | 5 | 32 |
1555 | 34 | 19 | 5 | 32 |
1557 | 36 | 22 | 5 | 32 |
1560 | 39 | 25 | 4 | 16 |
1561 | 40 | 26 | 5 | 32 |
1572 | 51 | 11 | 5 | 32 |
1573 | 52 | 12 | 5 | 32 |
1575 | 54 | 17 | 5 | 32 |
1576 | 55 | 18 | 5 | 32 |
1577 | 56 | 20 | 5 | 32 |
1578 | 57 | 21 | 5 | 32 |
1579 | 58 | 23 | 5 | 32 |
1580 | 59 | 24 | 5 | 32 |
1586 #### Match Length Code:
1588 | State | Symbol | Number_Of_Bits | Base |
1589 | ----- | ------ | -------------- | ---- |
1657 | State | Symbol | Number_Of_Bits | Base |
1658 | ----- | ------ | -------------- | ---- |
1694 Appendix B - Resources for implementers
1695 -------------------------------------------------
1697 An open source reference implementation is available on :
1698 https://github.com/facebook/zstd
1700 The project contains a frame generator, called [decodeCorpus],
1701 which can be used by any 3rd-party implementation
1702 to verify that a tested decoder is compliant with the specification.
1704 [decodeCorpus]: https://github.com/facebook/zstd/tree/v1.3.4/tests#decodecorpus---tool-to-generate-zstandard-frames-for-decoder-testing
1706 `decodeCorpus` generates random valid frames.
1707 A compliant decoder should be able to decode them all,
1708 or at least provide a meaningful error code explaining for which reason it cannot
1709 (memory limit restrictions for example).
1714 - 0.4.0 : fixed imprecise behavior for nbSeq==0, detected by Igor Pavlov
1715 - 0.3.9 : clarifications for Huffman-compressed literal sizes.
1716 - 0.3.8 : clarifications for Huffman Blocks and Huffman Tree descriptions.
1717 - 0.3.7 : clarifications for Repeat_Offsets, matching RFC8878
1718 - 0.3.6 : clarifications for Dictionary_ID
1719 - 0.3.5 : clarifications for Block_Maximum_Size
1720 - 0.3.4 : clarifications for FSE decoding table
1721 - 0.3.3 : clarifications for field Block_Size
1722 - 0.3.2 : remove additional block size restriction on compressed blocks
1723 - 0.3.1 : minor clarification regarding offset history update rules
1724 - 0.3.0 : minor edits to match RFC8478
1725 - 0.2.9 : clarifications for huffman weights direct representation, by Ulrich Kunitz
1726 - 0.2.8 : clarifications for IETF RFC discuss
1727 - 0.2.7 : clarifications from IETF RFC review, by Vijay Gurbani and Nick Terrell
1728 - 0.2.6 : fixed an error in huffman example, by Ulrich Kunitz
1729 - 0.2.5 : minor typos and clarifications
1730 - 0.2.4 : section restructuring, by Sean Purcell
1731 - 0.2.3 : clarified several details, by Sean Purcell
1732 - 0.2.2 : added predefined codes, by Johannes Rudolph
1733 - 0.2.1 : clarify field names, by Przemyslaw Skibinski
1734 - 0.2.0 : numerous format adjustments for zstd v0.8+
1735 - 0.1.2 : limit Huffman tree depth to 11 bits
1736 - 0.1.1 : reserved dictID ranges
1737 - 0.1.0 : initial release