1 Zstandard Compression Format
2 ============================
6 Copyright (c) 2016-present Yann Collet, Facebook, Inc.
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](http://www.zstandard.org).
31 The data can be produced or consumed,
32 even for an arbitrarily long sequentially presented input data stream,
33 using only an a priori bounded amount of intermediate storage,
34 and hence can be used in data communications.
35 The format uses the Zstandard compression method,
36 and optional [xxHash-64 checksum method](http://www.xxhash.org),
37 for detection of data corruption.
39 The data format defined by this specification
40 does not attempt to allow random access to compressed data.
42 This specification is intended for use by implementers of software
43 to compress data into Zstandard format and/or decompress data from Zstandard format.
44 The text of the specification assumes a basic background in programming
45 at the level of bits and other primitive data representations.
47 Unless otherwise indicated below,
48 a compliant compressor must produce data sets
49 that conform to the specifications presented here.
50 It doesn’t need to support all options though.
52 A compliant decompressor must be able to decompress
53 at least one working set of parameters
54 that conforms to the specifications presented here.
55 It may also ignore informative fields, such as checksum.
56 Whenever it does not support a parameter defined in the compressed stream,
57 it must produce a non-ambiguous error code and associated error message
58 explaining which parameter is unsupported.
60 ### Overall conventions
62 - square brackets i.e. `[` and `]` are used to indicate optional fields or parameters.
63 - the naming convention for identifiers is `Mixed_Case_With_Underscores`
66 Content compressed by Zstandard is transformed into a Zstandard __frame__.
67 Multiple frames can be appended into a single file or stream.
68 A frame is completely independent, has a defined beginning and end,
69 and a set of parameters which tells the decoder how to decompress it.
71 A frame encapsulates one or multiple __blocks__.
72 Each block can be compressed or not,
73 and has a guaranteed maximum content size, which depends on frame parameters.
74 Unlike frames, each block depends on previous blocks for proper decoding.
75 However, each block can be decompressed without waiting for its successor,
76 allowing streaming operations.
81 - [Zstandard frames](#zstandard-frames)
83 - [Literals Section](#literals-section)
84 - [Sequences Section](#sequences-section)
85 - [Sequence Execution](#sequence-execution)
86 - [Skippable frames](#skippable-frames)
87 - [Entropy Encoding](#entropy-encoding)
89 - [Huffman Coding](#huffman-coding)
90 - [Dictionary Format](#dictionary-format)
94 Zstandard compressed data is made of up one or more __frames__.
95 Each frame is independent and can be decompressed indepedently of other frames.
96 The decompressed content of multiple concatenated frames is the concatenation of
97 each frames decompressed content.
99 There are two frame formats defined by Zstandard:
100 Zstandard frames and Skippable frames.
101 Zstandard frames contain compressed data, while
102 skippable frames contain no data and can be used for metadata.
105 The structure of a single Zstandard frame is following:
107 | `Magic_Number` | `Frame_Header` |`Data_Block`| [More data blocks] | [`Content_Checksum`] |
108 |:--------------:|:--------------:|:----------:| ------------------ |:--------------------:|
109 | 4 bytes | 2-14 bytes | n bytes | | 0-4 bytes |
113 4 Bytes, __little-endian__ format.
118 2 to 14 Bytes, detailed in [`Frame_Header`](#frame_header).
122 Detailed in [`Blocks`](#blocks).
123 That’s where compressed data is stored.
125 __`Content_Checksum`__
127 An optional 32-bit checksum, only present if `Content_Checksum_flag` is set.
128 The content checksum is the result
129 of [xxh64() hash function](http://www.xxhash.org)
130 digesting the original (decoded) data as input, and a seed of zero.
131 The low 4 bytes of the checksum are stored in __little-endian__ format.
135 The `Frame_Header` has a variable size, with a minimum of 2 bytes,
136 and up to 14 bytes depending on optional parameters.
137 The structure of `Frame_Header` is following:
139 | `Frame_Header_Descriptor` | [`Window_Descriptor`] | [`Dictionary_ID`] | [`Frame_Content_Size`] |
140 | ------------------------- | --------------------- | ----------------- | ---------------------- |
141 | 1 byte | 0-1 byte | 0-4 bytes | 0-8 bytes |
143 #### `Frame_Header_Descriptor`
145 The first header's byte is called the `Frame_Header_Descriptor`.
146 It describes which other fields are present.
147 Decoding this byte is enough to tell the size of `Frame_Header`.
149 | Bit number | Field name |
150 | ---------- | ---------- |
151 | 7-6 | `Frame_Content_Size_flag` |
152 | 5 | `Single_Segment_flag` |
154 | 3 | `Reserved_bit` |
155 | 2 | `Content_Checksum_flag` |
156 | 1-0 | `Dictionary_ID_flag` |
158 In this table, bit 7 is the highest bit, while bit 0 is the lowest one.
160 __`Frame_Content_Size_flag`__
162 This is a 2-bits flag (`= Frame_Header_Descriptor >> 6`),
163 specifying if `Frame_Content_Size` (the decompressed data size)
164 is provided within the header.
165 `Flag_Value` provides `FCS_Field_Size`,
166 which is the number of bytes used by `Frame_Content_Size`
167 according to the following table:
169 | `Flag_Value` | 0 | 1 | 2 | 3 |
170 | -------------- | ------ | --- | --- | --- |
171 |`FCS_Field_Size`| 0 or 1 | 2 | 4 | 8 |
173 When `Flag_Value` is `0`, `FCS_Field_Size` depends on `Single_Segment_flag` :
174 if `Single_Segment_flag` is set, `Field_Size` is 1.
175 Otherwise, `Field_Size` is 0 : `Frame_Content_Size` is not provided.
177 __`Single_Segment_flag`__
180 data must be regenerated within a single continuous memory segment.
182 In this case, `Window_Descriptor` byte is skipped,
183 but `Frame_Content_Size` is necessarily present.
184 As a consequence, the decoder must allocate a memory segment
185 of size equal or bigger than `Frame_Content_Size`.
187 In order to preserve the decoder from unreasonable memory requirements,
188 a decoder is allowed to reject a compressed frame
189 which requests a memory size beyond decoder's authorized range.
191 For broader compatibility, decoders are recommended to support
192 memory sizes of at least 8 MB.
193 This is only a recommendation,
194 each decoder is free to support higher or lower limits,
195 depending on local limitations.
199 The value of this bit should be set to zero.
200 A decoder compliant with this specification version shall not interpret it.
201 It might be used in a future version,
202 to signal a property which is not mandatory to properly decode the frame.
206 This bit is reserved for some future feature.
207 Its value _must be zero_.
208 A decoder compliant with this specification version must ensure it is not set.
209 This bit may be used in a future revision,
210 to signal a feature that must be interpreted to decode the frame correctly.
212 __`Content_Checksum_flag`__
214 If this flag is set, a 32-bits `Content_Checksum` will be present at frame's end.
215 See `Content_Checksum` paragraph.
217 __`Dictionary_ID_flag`__
219 This is a 2-bits flag (`= FHD & 3`),
220 telling if a dictionary ID is provided within the header.
221 It also specifies the size of this field as `Field_Size`.
223 |`Flag_Value`| 0 | 1 | 2 | 3 |
224 | ---------- | --- | --- | --- | --- |
225 |`Field_Size`| 0 | 1 | 2 | 4 |
227 #### `Window_Descriptor`
229 Provides guarantees on minimum memory buffer required to decompress a frame.
230 This information is important for decoders to allocate enough memory.
232 The `Window_Descriptor` byte is optional.
233 When `Single_Segment_flag` is set, `Window_Descriptor` is not present.
234 In this case, `Window_Size` is `Frame_Content_Size`,
235 which can be any value from 0 to 2^64-1 bytes (16 ExaBytes).
237 | Bit numbers | 7-3 | 2-0 |
238 | ----------- | ---------- | ---------- |
239 | Field name | `Exponent` | `Mantissa` |
241 The minimum memory buffer size is called `Window_Size`.
242 It is described by the following formulas :
244 windowLog = 10 + Exponent;
245 windowBase = 1 << windowLog;
246 windowAdd = (windowBase / 8) * Mantissa;
247 Window_Size = windowBase + windowAdd;
249 The minimum `Window_Size` is 1 KB.
250 The maximum `Window_Size` is `(1<<41) + 7*(1<<38)` bytes, which is 3.75 TB.
252 To properly decode compressed data,
253 a decoder will need to allocate a buffer of at least `Window_Size` bytes.
255 In order to preserve decoder from unreasonable memory requirements,
256 a decoder is allowed to reject a compressed frame
257 which requests a memory size beyond decoder's authorized range.
259 For improved interoperability,
260 decoders are recommended to be compatible with `Window_Size >= 8 MB`,
261 and encoders are recommended to not request more than 8 MB.
262 It's merely a recommendation though,
263 decoders are free to support larger or lower limits,
264 depending on local limitations.
268 This is a variable size field, which contains
269 the ID of the dictionary required to properly decode the frame.
270 `Dictionary_ID` field is optional. When it's not present,
271 it's up to the decoder to make sure it uses the correct dictionary.
273 Field size depends on `Dictionary_ID_flag`.
274 1 byte can represent an ID 0-255.
275 2 bytes can represent an ID 0-65535.
276 4 bytes can represent an ID 0-4294967295.
277 Format is __little-endian__.
279 It's allowed to represent a small ID (for example `13`)
280 with a large 4-bytes dictionary ID, even if it is less efficient.
283 If the frame is going to be distributed in a private environment,
284 any dictionary ID can be used.
285 However, for public distribution of compressed frames using a dictionary,
286 the following ranges are reserved and shall not be used :
287 - low range : `<= 32767`
288 - high range : `>= (1 << 31)`
290 #### `Frame_Content_Size`
292 This is the original (uncompressed) size. This information is optional.
293 `Frame_Content_Size` uses a variable number of bytes, provided by `FCS_Field_Size`.
294 `FCS_Field_Size` is provided by the value of `Frame_Content_Size_flag`.
295 `FCS_Field_Size` can be equal to 0 (not present), 1, 2, 4 or 8 bytes.
297 | `FCS_Field_Size` | Range |
298 | ---------------- | ---------- |
305 `Frame_Content_Size` format is __little-endian__.
306 When `FCS_Field_Size` is 1, 4 or 8 bytes, the value is read directly.
307 When `FCS_Field_Size` is 2, _the offset of 256 is added_.
308 It's allowed to represent a small size (for example `18`) using any compatible variant.
314 After `Magic_Number` and `Frame_Header`, there are some number of blocks.
315 Each frame must have at least one block,
316 but there is no upper limit on the number of blocks per frame.
318 The structure of a block is as follows:
320 | `Block_Header` | `Block_Content` |
321 |:--------------:|:---------------:|
322 | 3 bytes | n bytes |
324 `Block_Header` uses 3 bytes, written using __little-endian__ convention.
325 It contains 3 fields :
327 | `Last_Block` | `Block_Type` | `Block_Size` |
328 |:------------:|:------------:|:------------:|
329 | bit 0 | bits 1-2 | bits 3-23 |
333 The lowest bit signals if this block is the last one.
334 The frame will end after this last block.
335 It may be followed by an optional `Content_Checksum`
336 (see [Zstandard Frames](#zstandard-frames)).
340 The next 2 bits represent the `Block_Type`.
341 There are 4 block types :
343 | Value | 0 | 1 | 2 | 3 |
344 | ------------ | ----------- | ----------- | ------------------ | --------- |
345 | `Block_Type` | `Raw_Block` | `RLE_Block` | `Compressed_Block` | `Reserved`|
347 - `Raw_Block` - this is an uncompressed block.
348 `Block_Content` contains `Block_Size` bytes.
350 - `RLE_Block` - this is a single byte, repeated `Block_Size` times.
351 `Block_Content` consists of a single byte.
352 On the decompression side, this byte must be repeated `Block_Size` times.
354 - `Compressed_Block` - this is a [Zstandard compressed block](#compressed-blocks),
356 `Block_Size` is the length of `Block_Content`, the compressed data.
357 The decompressed size is not known,
358 but its maximum possible value is guaranteed (see below)
360 - `Reserved` - this is not a block.
361 This value cannot be used with current version of this specification.
365 The upper 21 bits of `Block_Header` represent the `Block_Size`.
367 Block sizes must respect a few rules :
368 - For `Compressed_Block`, `Block_Size` is always strictly less than decompressed size.
369 - Block decompressed size is always <= `Window_Size`
370 - Block decompressed size is always <= 128 KB.
372 A block can contain any number of bytes (even empty),
373 up to `Block_Maximum_Decompressed_Size`, which is the smallest of :
380 To decompress a compressed block, the compressed size must be provided
381 from `Block_Size` field within `Block_Header`.
383 A compressed block consists of 2 sections :
384 - [Literals Section](#literals-section)
385 - [Sequences Section](#sequences-section)
387 The results of the two sections are then combined to produce the decompressed
388 data in [Sequence Execution](#sequence-execution)
391 To decode a compressed block, the following elements are necessary :
392 - Previous decoded data, up to a distance of `Window_Size`,
393 or all previously decoded data when `Single_Segment_flag` is set.
394 - List of "recent offsets" from previous `Compressed_Block`.
395 - Decoding tables of previous `Compressed_Block` for each symbol type
396 (literals, literals lengths, match lengths, offsets).
400 All literals are regrouped in the first part of the block.
401 They can be decoded first, and then copied during [Sequence Execution],
402 or they can be decoded on the flow during [Sequence Execution].
404 Literals can be stored uncompressed or compressed using Huffman prefix codes.
405 When compressed, an optional tree description can be present,
406 followed by 1 or 4 streams.
408 | `Literals_Section_Header` | [`Huffman_Tree_Description`] | Stream1 | [Stream2] | [Stream3] | [Stream4] |
409 | ------------------------- | ---------------------------- | ------- | --------- | --------- | --------- |
412 #### `Literals_Section_Header`
414 Header is in charge of describing how literals are packed.
415 It's a byte-aligned variable-size bitfield, ranging from 1 to 5 bytes,
416 using __little-endian__ convention.
418 | `Literals_Block_Type` | `Size_Format` | `Regenerated_Size` | [`Compressed_Size`] |
419 | --------------------- | ------------- | ------------------ | ------------------- |
420 | 2 bits | 1 - 2 bits | 5 - 20 bits | 0 - 18 bits |
422 In this representation, bits on the left are the lowest bits.
424 __`Literals_Block_Type`__
426 This field uses 2 lowest bits of first byte, describing 4 different block types :
428 | `Literals_Block_Type` | Value |
429 | --------------------------- | ----- |
430 | `Raw_Literals_Block` | 0 |
431 | `RLE_Literals_Block` | 1 |
432 | `Compressed_Literals_Block` | 2 |
433 | `Treeless_Literals_Block` | 3 |
435 - `Raw_Literals_Block` - Literals are stored uncompressed.
436 - `RLE_Literals_Block` - Literals consist of a single byte value
437 repeated `Regenerated_Size` times.
438 - `Compressed_Literals_Block` - This is a standard Huffman-compressed block,
439 starting with a Huffman tree description.
441 - `Treeless_Literals_Block` - This is a Huffman-compressed block,
442 using Huffman tree _from previous Huffman-compressed literals block_.
443 `Huffman_Tree_Description` will be skipped.
444 Note: If this mode is triggered without any previous Huffman-table in the frame
445 (or [dictionary](#dictionary-format)), this should be treated as data corruption.
449 `Size_Format` is divided into 2 families :
451 - For `Raw_Literals_Block` and `RLE_Literals_Block`,
452 it's only necessary to decode `Regenerated_Size`.
453 There is no `Compressed_Size` field.
454 - For `Compressed_Block` and `Treeless_Literals_Block`,
455 it's required to decode both `Compressed_Size`
456 and `Regenerated_Size` (the decompressed size).
457 It's also necessary to decode the number of streams (1 or 4).
459 For values spanning several bytes, convention is __little-endian__.
461 __`Size_Format` for `Raw_Literals_Block` and `RLE_Literals_Block`__ :
463 - Value ?0 : `Size_Format` uses 1 bit.
464 `Regenerated_Size` uses 5 bits (0-31).
465 `Literals_Section_Header` has 1 byte.
466 `Regenerated_Size = Header[0]>>3`
467 - Value 01 : `Size_Format` uses 2 bits.
468 `Regenerated_Size` uses 12 bits (0-4095).
469 `Literals_Section_Header` has 2 bytes.
470 `Regenerated_Size = (Header[0]>>4) + (Header[1]<<4)`
471 - Value 11 : `Size_Format` uses 2 bits.
472 `Regenerated_Size` uses 20 bits (0-1048575).
473 `Literals_Section_Header` has 3 bytes.
474 `Regenerated_Size = (Header[0]>>4) + (Header[1]<<4) + (Header[2]<<12)`
476 Only Stream1 is present for these cases.
477 Note : it's allowed to represent a short value (for example `13`)
478 using a long format, even if it's less efficient.
480 __`Size_Format` for `Compressed_Literals_Block` and `Treeless_Literals_Block`__ :
482 - Value 00 : _A single stream_.
483 Both `Regenerated_Size` and `Compressed_Size` use 10 bits (0-1023).
484 `Literals_Section_Header` has 3 bytes.
485 - Value 01 : 4 streams.
486 Both `Regenerated_Size` and `Compressed_Size` use 10 bits (0-1023).
487 `Literals_Section_Header` has 3 bytes.
488 - Value 10 : 4 streams.
489 Both `Regenerated_Size` and `Compressed_Size` use 14 bits (0-16383).
490 `Literals_Section_Header` has 4 bytes.
491 - Value 11 : 4 streams.
492 Both `Regenerated_Size` and `Compressed_Size` use 18 bits (0-262143).
493 `Literals_Section_Header` has 5 bytes.
495 Both `Compressed_Size` and `Regenerated_Size` fields follow __little-endian__ convention.
496 Note: `Compressed_Size` __includes__ the size of the Huffman Tree description
497 _when_ it is present.
499 ### Raw Literals Block
500 The data in Stream1 is `Regenerated_Size` bytes long,
501 it contains the raw literals data to be used during [Sequence Execution].
503 ### RLE Literals Block
504 Stream1 consists of a single byte which should be repeated `Regenerated_Size` times
505 to generate the decoded literals.
507 ### Compressed Literals Block and Treeless Literals Block
508 Both of these modes contain Huffman encoded data.
509 `Treeless_Literals_Block` does not have a `Huffman_Tree_Description`.
511 #### `Huffman_Tree_Description`
512 This section is only present when `Literals_Block_Type` type is `Compressed_Literals_Block` (`2`).
513 The format of the Huffman tree description can be found at [Huffman Tree description](#huffman-tree-description).
514 The size of `Huffman_Tree_Description` is determined during decoding process,
515 it must be used to determine where streams begin.
516 `Total_Streams_Size = Compressed_Size - Huffman_Tree_Description_Size`.
518 For `Treeless_Literals_Block`,
519 the Huffman table comes from previously compressed literals block.
521 Huffman compressed data consists of either 1 or 4 Huffman-coded streams.
523 If only one stream is present, it is a single bitstream occupying the entire
524 remaining portion of the literals block, encoded as described within
525 [Huffman-Coded Streams](#huffman-coded-streams).
527 If there are four streams, the literals section header only provides enough
528 information to know the decompressed and compressed sizes of all four streams _combined_.
529 The decompressed size of each stream is equal to `(Regenerated_Size+3)/4`,
530 except for the last stream which may be up to 3 bytes smaller,
531 to reach a total decompressed size as specified in `Regenerated_Size`.
533 The compressed size of each stream is provided explicitly:
534 the first 6 bytes of the compressed data consist of three 2-byte __little-endian__ fields,
535 describing the compressed sizes of the first three streams.
536 `Stream4_Size` is computed from total `Total_Streams_Size` minus sizes of other streams.
538 `Stream4_Size = Total_Streams_Size - 6 - Stream1_Size - Stream2_Size - Stream3_Size`.
540 Note: remember that `Total_Streams_Size` can be smaller than `Compressed_Size` in header,
541 because `Compressed_Size` also contains `Huffman_Tree_Description_Size` when it is present.
543 Each of these 4 bitstreams is then decoded independently as a Huffman-Coded stream,
544 as described at [Huffman-Coded Streams](#huffman-coded-streams)
549 A compressed block is a succession of _sequences_ .
550 A sequence is a literal copy command, followed by a match copy command.
551 A literal copy command specifies a length.
552 It is the number of bytes to be copied (or extracted) from the Literals Section.
553 A match copy command specifies an offset and a length.
555 When all _sequences_ are decoded,
556 if there are literals left in the _literal section_,
557 these bytes are added at the end of the block.
559 This is described in more detail in [Sequence Execution](#sequence-execution)
561 The `Sequences_Section` regroup all symbols required to decode commands.
562 There are 3 symbol types : literals lengths, offsets and match lengths.
563 They are encoded together, interleaved, in a single _bitstream_.
565 The `Sequences_Section` starts by a header,
566 followed by optional probability tables for each symbol type,
567 followed by the bitstream.
569 | `Sequences_Section_Header` | [`Literals_Length_Table`] | [`Offset_Table`] | [`Match_Length_Table`] | bitStream |
570 | -------------------------- | ------------------------- | ---------------- | ---------------------- | --------- |
572 To decode the `Sequences_Section`, it's required to know its size.
573 This size is deduced from `Block_Size - Literals_Section_Size`.
576 #### `Sequences_Section_Header`
579 - `Number_of_Sequences`
580 - Symbol compression modes
582 __`Number_of_Sequences`__
584 This is a variable size field using between 1 and 3 bytes.
585 Let's call its first byte `byte0`.
586 - `if (byte0 == 0)` : there are no sequences.
587 The sequence section stops there.
588 Decompressed content is defined entirely as Literals Section content.
589 - `if (byte0 < 128)` : `Number_of_Sequences = byte0` . Uses 1 byte.
590 - `if (byte0 < 255)` : `Number_of_Sequences = ((byte0-128) << 8) + byte1` . Uses 2 bytes.
591 - `if (byte0 == 255)`: `Number_of_Sequences = byte1 + (byte2<<8) + 0x7F00` . Uses 3 bytes.
593 __Symbol compression modes__
595 This is a single byte, defining the compression mode of each symbol type.
597 |Bit number| 7-6 | 5-4 | 3-2 | 1-0 |
598 | -------- | ----------------------- | -------------- | -------------------- | ---------- |
599 |Field name| `Literals_Lengths_Mode` | `Offsets_Mode` | `Match_Lengths_Mode` | `Reserved` |
601 The last field, `Reserved`, must be all-zeroes.
603 `Literals_Lengths_Mode`, `Offsets_Mode` and `Match_Lengths_Mode` define the `Compression_Mode` of
604 literals lengths, offsets, and match lengths symbols respectively.
606 They follow the same enumeration :
608 | Value | 0 | 1 | 2 | 3 |
609 | ------------------ | ----------------- | ---------- | --------------------- | ------------- |
610 | `Compression_Mode` | `Predefined_Mode` | `RLE_Mode` | `FSE_Compressed_Mode` | `Repeat_Mode` |
612 - `Predefined_Mode` : A predefined FSE distribution table is used, defined in
613 [default distributions](#default-distributions).
614 No distribution table will be present.
615 - `RLE_Mode` : The table description consists of a single byte.
616 This code will be repeated for all sequences.
617 - `Repeat_Mode` : The table used in the previous compressed block will be used again.
618 No distribution table will be present.
619 Note: this includes RLE mode, so if `Repeat_Mode` follows `RLE_Mode`, the same symbol will be repeated.
620 If this mode is used without any previous sequence table in the frame
621 (or [dictionary](#dictionary-format)) to repeat, this should be treated as corruption.
622 - `FSE_Compressed_Mode` : standard FSE compression.
623 A distribution table will be present.
624 The format of this distribution table is described in [FSE Table Description](#fse-table-description).
625 Note that the maximum allowed accuracy log for literals length and match length tables is 9,
626 and the maximum accuracy log for the offsets table is 8.
628 #### The codes for literals lengths, match lengths, and offsets.
630 Each symbol is a _code_ in its own context,
631 which specifies `Baseline` and `Number_of_Bits` to add.
632 _Codes_ are FSE compressed,
633 and interleaved with raw additional bits in the same bitstream.
635 ##### Literals length codes
637 Literals length codes are values ranging from `0` to `35` included.
638 They define lengths from 0 to 131071 bytes.
639 The literals length is equal to the decoded `Baseline` plus
640 the result of reading `Number_of_Bits` bits from the bitstream,
641 as a __little-endian__ value.
643 | `Literals_Length_Code` | 0-15 |
644 | ---------------------- | ---------------------- |
645 | length | `Literals_Length_Code` |
646 | `Number_of_Bits` | 0 |
648 | `Literals_Length_Code` | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
649 | ---------------------- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
650 | `Baseline` | 16 | 18 | 20 | 22 | 24 | 28 | 32 | 40 |
651 | `Number_of_Bits` | 1 | 1 | 1 | 1 | 2 | 2 | 3 | 3 |
653 | `Literals_Length_Code` | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
654 | ---------------------- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
655 | `Baseline` | 48 | 64 | 128 | 256 | 512 | 1024 | 2048 | 4096 |
656 | `Number_of_Bits` | 4 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
658 | `Literals_Length_Code` | 32 | 33 | 34 | 35 |
659 | ---------------------- | ---- | ---- | ---- | ---- |
660 | `Baseline` | 8192 |16384 |32768 |65536 |
661 | `Number_of_Bits` | 13 | 14 | 15 | 16 |
664 ##### Match length codes
666 Match length codes are values ranging from `0` to `52` included.
667 They define lengths from 3 to 131074 bytes.
668 The match length is equal to the decoded `Baseline` plus
669 the result of reading `Number_of_Bits` bits from the bitstream,
670 as a __little-endian__ value.
672 | `Match_Length_Code` | 0-31 |
673 | ------------------- | ----------------------- |
674 | value | `Match_Length_Code` + 3 |
675 | `Number_of_Bits` | 0 |
677 | `Match_Length_Code` | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 |
678 | ------------------- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
679 | `Baseline` | 35 | 37 | 39 | 41 | 43 | 47 | 51 | 59 |
680 | `Number_of_Bits` | 1 | 1 | 1 | 1 | 2 | 2 | 3 | 3 |
682 | `Match_Length_Code` | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 |
683 | ------------------- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
684 | `Baseline` | 67 | 83 | 99 | 131 | 259 | 515 | 1027 | 2051 |
685 | `Number_of_Bits` | 4 | 4 | 5 | 7 | 8 | 9 | 10 | 11 |
687 | `Match_Length_Code` | 48 | 49 | 50 | 51 | 52 |
688 | ------------------- | ---- | ---- | ---- | ---- | ---- |
689 | `Baseline` | 4099 | 8195 |16387 |32771 |65539 |
690 | `Number_of_Bits` | 12 | 13 | 14 | 15 | 16 |
694 Offset codes are values ranging from `0` to `N`.
696 A decoder is free to limit its maximum `N` supported.
697 Recommendation is to support at least up to `22`.
698 For information, at the time of this writing.
699 the reference decoder supports a maximum `N` value of `28` in 64-bits mode.
701 An offset code is also the number of additional bits to read in __little-endian__ fashion,
702 and can be translated into an `Offset_Value` using the following formulas :
705 Offset_Value = (1 << offsetCode) + readNBits(offsetCode);
706 if (Offset_Value > 3) offset = Offset_Value - 3;
708 It means that maximum `Offset_Value` is `(2^(N+1))-1` and it supports back-reference distance up to `(2^(N+1))-4`
709 but is limited by [maximum back-reference distance](#window_descriptor).
711 `Offset_Value` from 1 to 3 are special : they define "repeat codes".
712 This is described in more detail in [Repeat Offsets](#repeat-offsets).
714 #### Decoding Sequences
715 FSE bitstreams are read in reverse direction than written. In zstd,
716 the compressor writes bits forward into a block and the decompressor
717 must read the bitstream _backwards_.
719 To find the start of the bitstream it is therefore necessary to
720 know the offset of the last byte of the block which can be found
721 by counting `Block_Size` bytes after the block header.
723 After writing the last bit containing information, the compressor
724 writes a single `1`-bit and then fills the byte with 0-7 `0` bits of
725 padding. The last byte of the compressed bitstream cannot be `0` for
728 When decompressing, the last byte containing the padding is the first
729 byte to read. The decompressor needs to skip 0-7 initial `0`-bits and
730 the first `1`-bit it occurs. Afterwards, the useful part of the bitstream
733 FSE decoding requires a 'state' to be carried from symbol to symbol.
734 For more explanation on FSE decoding, see the [FSE section](#fse).
736 For sequence decoding, a separate state keeps track of each
737 literal lengths, offsets, and match lengths symbols.
738 Some FSE primitives are also used.
739 For more details on the operation of these primitives, see the [FSE section](#fse).
741 ##### Starting states
742 The bitstream starts with initial FSE state values,
743 each using the required number of bits in their respective _accuracy_,
744 decoded previously from their normalized distribution.
746 It starts by `Literals_Length_State`,
747 followed by `Offset_State`,
748 and finally `Match_Length_State`.
750 Reminder : always keep in mind that all values are read _backward_,
751 so the 'start' of the bitstream is at the highest position in memory,
752 immediately before the last `1`-bit for padding.
754 After decoding the starting states, a single sequence is decoded
755 `Number_Of_Sequences` times.
756 These sequences are decoded in order from first to last.
757 Since the compressor writes the bitstream in the forward direction,
758 this means the compressor must encode the sequences starting with the last
759 one and ending with the first.
761 ##### Decoding a sequence
762 For each of the symbol types, the FSE state can be used to determine the appropriate code.
763 The code then defines the baseline and number of bits to read for each type.
764 See the [description of the codes] for how to determine these values.
766 [description of the codes]: #the-codes-for-literals-lengths-match-lengths-and-offsets
768 Decoding starts by reading the `Number_of_Bits` required to decode `Offset`.
769 It then does the same for `Match_Length`, and then for `Literals_Length`.
770 This sequence is then used for [sequence execution](#sequence-execution).
772 If it is not the last sequence in the block,
773 the next operation is to update states.
774 Using the rules pre-calculated in the decoding tables,
775 `Literals_Length_State` is updated,
776 followed by `Match_Length_State`,
777 and then `Offset_State`.
778 See the [FSE section](#fse) for details on how to update states from the bitstream.
780 This operation will be repeated `Number_of_Sequences` times.
781 At the end, the bitstream shall be entirely consumed,
782 otherwise the bitstream is considered corrupted.
784 #### Default Distributions
785 If `Predefined_Mode` is selected for a symbol type,
786 its FSE decoding table is generated from a predefined distribution table defined here.
787 For details on how to convert this distribution into a decoding table, see the [FSE section].
789 [FSE section]: #from-normalized-distribution-to-decoding-tables
791 ##### Literals Length
792 The decoding table uses an accuracy log of 6 bits (64 states).
794 short literalsLength_defaultDistribution[36] =
795 { 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
796 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
801 The decoding table uses an accuracy log of 6 bits (64 states).
803 short matchLengths_defaultDistribution[53] =
804 { 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
805 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
806 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,
811 The decoding table uses an accuracy log of 5 bits (32 states),
812 and supports a maximum `N` value of 28, allowing offset values up to 536,870,908 .
814 If any sequence in the compressed block requires a larger offset than this,
815 it's not possible to use the default distribution to represent it.
817 short offsetCodes_defaultDistribution[29] =
818 { 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
819 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1 };
825 Once literals and sequences have been decoded,
826 they are combined to produce the decoded content of a block.
828 Each sequence consists of a tuple of (`literals_length`, `offset_value`, `match_length`),
829 decoded as described in the [Sequences Section](#sequences-section).
830 To execute a sequence, first copy `literals_length` bytes from the literals section
833 Then `match_length` bytes are copied from previous decoded data.
834 The offset to copy from is determined by `offset_value`:
835 if `offset_value > 3`, then the offset is `offset_value - 3`.
836 If `offset_value` is from 1-3, the offset is a special repeat offset value.
837 See the [repeat offset](#repeat-offsets) section for how the offset is determined
840 The offset is defined as from the current position, so an offset of 6
841 and a match length of 3 means that 3 bytes should be copied from 6 bytes back.
842 Note that all offsets leading to previously decoded data
843 must be smaller than `Window_Size` defined in `Frame_Header_Descriptor`.
846 As seen in [Sequence Execution](#sequence-execution),
847 the first 3 values define a repeated offset and we will call them
848 `Repeated_Offset1`, `Repeated_Offset2`, and `Repeated_Offset3`.
849 They are sorted in recency order, with `Repeated_Offset1` meaning "most recent one".
851 If `offset_value == 1`, then the offset used is `Repeated_Offset1`, etc.
853 There is an exception though, when current sequence's `literals_length = 0`.
854 In this case, repeated offsets are shifted by one,
855 so an `offset_value` of 1 means `Repeated_Offset2`,
856 an `offset_value` of 2 means `Repeated_Offset3`,
857 and an `offset_value` of 3 means `Repeated_Offset1 - 1_byte`.
859 For the first block, the starting offset history is populated with the following values : 1, 4 and 8 (in order).
861 Then each block gets its starting offset history from the ending values of the most recent `Compressed_Block`.
862 Note that blocks which are not `Compressed_Block` are skipped, they do not contribute to offset history.
864 [Offset Codes]: #offset-codes
866 ###### Offset updates rules
868 The newest offset takes the lead in offset history,
869 shifting others back (up to its previous place if it was already present).
871 This means that when `Repeated_Offset1` (most recent) is used, history is unmodified.
872 When `Repeated_Offset2` is used, it's swapped with `Repeated_Offset1`.
873 If any other offset is used, it becomes `Repeated_Offset1` and the rest are shift back by one.
879 | `Magic_Number` | `Frame_Size` | `User_Data` |
880 |:--------------:|:------------:|:-----------:|
881 | 4 bytes | 4 bytes | n bytes |
883 Skippable frames allow the insertion of user-defined data
884 into a flow of concatenated frames.
885 Its design is pretty straightforward,
886 with the sole objective to allow the decoder to quickly skip
887 over user-defined data and continue decoding.
889 Skippable frames defined in this specification are compatible with [LZ4] ones.
891 [LZ4]:http://www.lz4.org
895 4 Bytes, __little-endian__ format.
896 Value : 0x184D2A5?, which means any value from 0x184D2A50 to 0x184D2A5F.
897 All 16 values are valid to identify a skippable frame.
901 This is the size, in bytes, of the following `User_Data`
902 (without including the magic number nor the size field itself).
903 This field is represented using 4 Bytes, __little-endian__ format, unsigned 32-bits.
904 This means `User_Data` can’t be bigger than (2^32-1) bytes.
908 The `User_Data` can be anything. Data will just be skipped by the decoder.
913 Two types of entropy encoding are used by the Zstandard format:
914 FSE, and Huffman coding.
918 FSE, short for Finite State Entropy, is an entropy codec based on [ANS].
919 FSE encoding/decoding involves a state that is carried over between symbols,
920 so decoding must be done in the opposite direction as encoding.
921 Therefore, all FSE bitstreams are read from end to beginning.
923 For additional details on FSE, see [Finite State Entropy].
925 [Finite State Entropy]:https://github.com/Cyan4973/FiniteStateEntropy/
927 FSE decoding involves a decoding table which has a power of 2 size, and contain three elements:
928 `Symbol`, `Num_Bits`, and `Baseline`.
929 The `log2` of the table size is its `Accuracy_Log`.
930 The FSE state represents an index in this table.
932 To obtain the initial state value, consume `Accuracy_Log` bits from the stream as a __little-endian__ value.
933 The next symbol in the stream is the `Symbol` indicated in the table for that state.
934 To obtain the next state value,
935 the decoder should consume `Num_Bits` bits from the stream as a __little-endian__ value and add it to `Baseline`.
937 [ANS]: https://en.wikipedia.org/wiki/Asymmetric_Numeral_Systems
939 ### FSE Table Description
940 To decode FSE streams, it is necessary to construct the decoding table.
941 The Zstandard format encodes FSE table descriptions as follows:
943 An FSE distribution table describes the probabilities of all symbols
944 from `0` to the last present one (included)
945 on a normalized scale of `1 << Accuracy_Log` .
947 It's a bitstream which is read forward, in __little-endian__ fashion.
948 It's not necessary to know its exact size,
949 since it will be discovered and reported by the decoding process.
951 The bitstream starts by reporting on which scale it operates.
952 `Accuracy_Log = low4bits + 5`.
954 Then follows each symbol value, from `0` to last present one.
955 The number of bits used by each field is variable.
958 - Remaining probabilities + 1 :
960 Presuming an `Accuracy_Log` of 8,
961 and presuming 100 probabilities points have already been distributed,
962 the decoder may read any value from `0` to `255 - 100 + 1 == 156` (inclusive).
963 Therefore, it must read `log2sup(156) == 8` bits.
965 - Value decoded : small values use 1 less bit :
967 Presuming values from 0 to 156 (inclusive) are possible,
968 255-156 = 99 values are remaining in an 8-bits field.
969 They are used this way :
970 first 99 values (hence from 0 to 98) use only 7 bits,
971 values from 99 to 156 use 8 bits.
972 This is achieved through this scheme :
974 | Value read | Value decoded | Number of bits used |
975 | ---------- | ------------- | ------------------- |
976 | 0 - 98 | 0 - 98 | 7 |
977 | 99 - 127 | 99 - 127 | 8 |
978 | 128 - 226 | 0 - 98 | 7 |
979 | 227 - 255 | 128 - 156 | 8 |
981 Symbols probabilities are read one by one, in order.
983 Probability is obtained from Value decoded by following formula :
986 It means value `0` becomes negative probability `-1`.
987 `-1` is a special probability, which means "less than 1".
988 Its effect on distribution table is described in the [next section].
989 For the purpose of calculating total allocated probability points, it counts as one.
991 [next section]:#from-normalized-distribution-to-decoding-tables
993 When a symbol has a __probability__ of `zero`,
994 it is followed by a 2-bits repeat flag.
995 This repeat flag tells how many probabilities of zeroes follow the current one.
996 It provides a number ranging from 0 to 3.
997 If it is a 3, another 2-bits repeat flag follows, and so on.
999 When last symbol reaches cumulated total of `1 << Accuracy_Log`,
1000 decoding is complete.
1001 If the last symbol makes cumulated total go above `1 << Accuracy_Log`,
1002 distribution is considered corrupted.
1004 Then the decoder can tell how many bytes were used in this process,
1005 and how many symbols are present.
1006 The bitstream consumes a round number of bytes.
1007 Any remaining bit within the last byte is just unused.
1009 ##### From normalized distribution to decoding tables
1011 The distribution of normalized probabilities is enough
1012 to create a unique decoding table.
1014 It follows the following build rule :
1016 The table has a size of `Table_Size = 1 << Accuracy_Log`.
1017 Each cell describes the symbol decoded,
1018 and instructions to get the next state.
1020 Symbols are scanned in their natural order for "less than 1" probabilities.
1021 Symbols with this probability are being attributed a single cell,
1022 starting from the end of the table.
1023 These symbols define a full state reset, reading `Accuracy_Log` bits.
1025 All remaining symbols are sorted in their natural order.
1026 Starting from symbol `0` and table position `0`,
1027 each symbol gets attributed as many cells as its probability.
1028 Cell allocation is spreaded, not linear :
1029 each successor position follow this rule :
1032 position += (tableSize>>1) + (tableSize>>3) + 3;
1033 position &= tableSize-1;
1036 A position is skipped if already occupied by a "less than 1" probability symbol.
1037 `position` does not reset between symbols, it simply iterates through
1038 each position in the table, switching to the next symbol when enough
1039 states have been allocated to the current one.
1041 The result is a list of state values.
1042 Each state will decode the current symbol.
1044 To get the `Number_of_Bits` and `Baseline` required for next state,
1045 it's first necessary to sort all states in their natural order.
1046 The lower states will need 1 more bit than higher ones.
1049 Presuming a symbol has a probability of 5.
1050 It receives 5 state values. States are sorted in natural order.
1052 Next power of 2 is 8.
1053 Space of probabilities is divided into 8 equal parts.
1054 Presuming the `Accuracy_Log` is 7, it defines 128 states.
1055 Divided by 8, each share is 16 large.
1057 In order to reach 8, 8-5=3 lowest states will count "double",
1058 taking shares twice larger,
1059 requiring one more bit in the process.
1061 Numbering starts from higher states using less bits.
1063 | state order | 0 | 1 | 2 | 3 | 4 |
1064 | ---------------- | ----- | ----- | ------ | ---- | ----- |
1065 | width | 32 | 32 | 32 | 16 | 16 |
1066 | `Number_of_Bits` | 5 | 5 | 5 | 4 | 4 |
1067 | range number | 2 | 4 | 6 | 0 | 1 |
1068 | `Baseline` | 32 | 64 | 96 | 0 | 16 |
1069 | range | 32-63 | 64-95 | 96-127 | 0-15 | 16-31 |
1071 The next state is determined from current state
1072 by reading the required `Number_of_Bits`, and adding the specified `Baseline`.
1074 See [Appendix A] for the results of this process applied to the default distributions.
1076 [Appendix A]: #appendix-a---decoding-tables-for-predefined-codes
1080 Zstandard Huffman-coded streams are read backwards,
1081 similar to the FSE bitstreams.
1082 Therefore, to find the start of the bitstream, it is therefore to
1083 know the offset of the last byte of the Huffman-coded stream.
1085 After writing the last bit containing information, the compressor
1086 writes a single `1`-bit and then fills the byte with 0-7 `0` bits of
1087 padding. The last byte of the compressed bitstream cannot be `0` for
1090 When decompressing, the last byte containing the padding is the first
1091 byte to read. The decompressor needs to skip 0-7 initial `0`-bits and
1092 the first `1`-bit it occurs. Afterwards, the useful part of the bitstream
1095 The bitstream contains Huffman-coded symbols in __little-endian__ order,
1096 with the codes defined by the method below.
1098 ### Huffman Tree Description
1099 Prefix coding represents symbols from an a priori known alphabet
1100 by bit sequences (codewords), one codeword for each symbol,
1101 in a manner such that different symbols may be represented
1102 by bit sequences of different lengths,
1103 but a parser can always parse an encoded string
1104 unambiguously symbol-by-symbol.
1106 Given an alphabet with known symbol frequencies,
1107 the Huffman algorithm allows the construction of an optimal prefix code
1108 using the fewest bits of any possible prefix codes for that alphabet.
1110 Prefix code must not exceed a maximum code length.
1111 More bits improve accuracy but cost more header size,
1112 and require more memory or more complex decoding operations.
1113 This specification limits maximum code length to 11 bits.
1116 ##### Representation
1118 All literal values from zero (included) to last present one (excluded)
1119 are represented by `Weight` with values from `0` to `Max_Number_of_Bits`.
1120 Transformation from `Weight` to `Number_of_Bits` follows this formula :
1122 Number_of_Bits = Weight ? (Max_Number_of_Bits + 1 - Weight) : 0
1124 The last symbol's `Weight` is deduced from previously decoded ones,
1125 by completing to the nearest power of 2.
1126 This power of 2 gives `Max_Number_of_Bits`, the depth of the current tree.
1129 Let's presume the following Huffman tree must be described :
1131 | literal | 0 | 1 | 2 | 3 | 4 | 5 |
1132 | ---------------- | --- | --- | --- | --- | --- | --- |
1133 | `Number_of_Bits` | 1 | 2 | 3 | 0 | 4 | 4 |
1135 The tree depth is 4, since its smallest element uses 4 bits.
1136 Value `5` will not be listed as it can be determined from the values for 0-4,
1137 nor will values above `5` as they are all 0.
1138 Values from `0` to `4` will be listed using `Weight` instead of `Number_of_Bits`.
1141 Weight = Number_of_Bits ? (Max_Number_of_Bits + 1 - Number_of_Bits) : 0
1143 It gives the following series of weights :
1145 | literal | 0 | 1 | 2 | 3 | 4 |
1146 | -------- | --- | --- | --- | --- | --- |
1147 | `Weight` | 4 | 3 | 2 | 0 | 1 |
1149 The decoder will do the inverse operation :
1150 having collected weights of literals from `0` to `4`,
1151 it knows the last literal, `5`, is present with a non-zero weight.
1152 The weight of `5` can be determined by advancing to the next power of 2.
1153 The sum of `2^(Weight-1)` (excluding 0's) is :
1154 `8 + 4 + 2 + 0 + 1 = 15`.
1155 Nearest power of 2 is 16.
1156 Therefore, `Max_Number_of_Bits = 4` and `Weight[5] = 1`.
1158 ##### Huffman Tree header
1160 This is a single byte value (0-255),
1161 which describes how to decode the list of weights.
1163 - if `headerByte` >= 128 : this is a direct representation,
1164 where each `Weight` is written directly as a 4 bits field (0-15).
1165 They are encoded forward, 2 weights to a byte with the first weight taking
1166 the top four bits and the second taking the bottom four (e.g. the following
1167 operations could be used to read the weights:
1168 `Weight[0] = (Byte[0] >> 4), Weight[1] = (Byte[0] & 0xf)`, etc.).
1169 The full representation occupies `((Number_of_Symbols+1)/2)` bytes,
1170 meaning it uses a last full byte even if `Number_of_Symbols` is odd.
1171 `Number_of_Symbols = headerByte - 127`.
1172 Note that maximum `Number_of_Symbols` is 255-127 = 128.
1173 A larger series must necessarily use FSE compression.
1175 - if `headerByte` < 128 :
1176 the series of weights is compressed by FSE.
1177 The length of the FSE-compressed series is equal to `headerByte` (0-127).
1179 ##### Finite State Entropy (FSE) compression of Huffman weights
1181 In this case, the series of Huffman weights is compressed using FSE compression.
1182 It's a single bitstream with 2 interleaved states,
1183 sharing a single distribution table.
1185 To decode an FSE bitstream, it is necessary to know its compressed size.
1186 Compressed size is provided by `headerByte`.
1187 It's also necessary to know its _maximum possible_ decompressed size,
1188 which is `255`, since literal values span from `0` to `255`,
1189 and last symbol's weight is not represented.
1191 An FSE bitstream starts by a header, describing probabilities distribution.
1192 It will create a Decoding Table.
1193 For a list of Huffman weights, the maximum accuracy log is 7 bits.
1194 For more description see the [FSE header description](#fse-table-description)
1196 The Huffman header compression uses 2 states,
1197 which share the same FSE distribution table.
1198 The first state (`State1`) encodes the even indexed symbols,
1199 and the second (`State2`) encodes the odd indexes.
1200 `State1` is initialized first, and then `State2`, and they take turns
1201 decoding a single symbol and updating their state.
1202 For more details on these FSE operations, see the [FSE section](#fse).
1204 The number of symbols to decode is determined
1205 by tracking bitStream overflow condition:
1206 If updating state after decoding a symbol would require more bits than
1207 remain in the stream, it is assumed that extra bits are 0. Then,
1208 the symbols for each of the final states are decoded and the process is complete.
1210 ##### Conversion from weights to Huffman prefix codes
1212 All present symbols shall now have a `Weight` value.
1213 It is possible to transform weights into Number_of_Bits, using this formula:
1215 Number_of_Bits = Number_of_Bits ? Max_Number_of_Bits + 1 - Weight : 0
1217 Symbols are sorted by `Weight`. Within same `Weight`, symbols keep natural order.
1218 Symbols with a `Weight` of zero are removed.
1219 Then, starting from lowest weight, prefix codes are distributed in order.
1222 Let's presume the following list of weights has been decoded :
1224 | Literal | 0 | 1 | 2 | 3 | 4 | 5 |
1225 | -------- | --- | --- | --- | --- | --- | --- |
1226 | `Weight` | 4 | 3 | 2 | 0 | 1 | 1 |
1228 Sorted by weight and then natural order,
1229 it gives the following distribution :
1231 | Literal | 3 | 4 | 5 | 2 | 1 | 0 |
1232 | ---------------- | --- | --- | --- | --- | --- | ---- |
1233 | `Weight` | 0 | 1 | 1 | 2 | 3 | 4 |
1234 | `Number_of_Bits` | 0 | 4 | 4 | 3 | 2 | 1 |
1235 | prefix codes | N/A | 0000| 0001| 001 | 01 | 1 |
1237 ### Huffman-coded Streams
1238 Given a Huffman decoding table,
1239 it's possible to decode a Huffman-coded stream.
1241 Each bitstream must be read _backward_,
1242 that is starting from the end down to the beginning.
1243 Therefore it's necessary to know the size of each bitstream.
1245 It's also necessary to know exactly which _bit_ is the latest.
1246 This is detected by a final bit flag :
1247 the highest bit of latest byte is a final-bit-flag.
1248 Consequently, a last byte of `0` is not possible.
1249 And the final-bit-flag itself is not part of the useful bitstream.
1250 Hence, the last byte contains between 0 and 7 useful bits.
1252 Starting from the end,
1253 it's possible to read the bitstream in a __little-endian__ fashion,
1254 keeping track of already used bits. Since the bitstream is encoded in reverse
1255 order, starting from the end read symbols in forward order.
1257 For example, if the literal sequence "0145" was encoded using above prefix code,
1258 it would be encoded (in reverse order) as:
1260 |Symbol | 5 | 4 | 1 | 0 | Padding |
1261 |--------|------|------|----|---|---------|
1262 |Encoding|`0000`|`0001`|`01`|`1`| `00001` |
1264 Resulting in following 2-bytes bitstream :
1269 Here is an alternative representation with the symbol codes separated by underscore:
1271 0001_0000 00001_1_01
1274 Reading highest `Max_Number_of_Bits` bits,
1275 it's possible to compare extracted value to decoding table,
1276 determining the symbol to decode and number of bits to discard.
1278 The process continues up to reading the required number of symbols per stream.
1279 If a bitstream is not entirely and exactly consumed,
1280 hence reaching exactly its beginning position with _all_ bits consumed,
1281 the decoding process is considered faulty.
1287 Zstandard is compatible with "raw content" dictionaries,
1288 free of any format restriction, except that they must be at least 8 bytes.
1289 These dictionaries function as if they were just the `Content` part
1290 of a formatted dictionary.
1292 But dictionaries created by `zstd --train` follow a format, described here.
1294 __Pre-requisites__ : a dictionary has a size,
1295 defined either by a buffer limit, or a file size.
1297 | `Magic_Number` | `Dictionary_ID` | `Entropy_Tables` | `Content` |
1298 | -------------- | --------------- | ---------------- | --------- |
1300 __`Magic_Number`__ : 4 bytes ID, value 0xEC30A437, __little-endian__ format
1302 __`Dictionary_ID`__ : 4 bytes, stored in __little-endian__ format.
1303 `Dictionary_ID` can be any value, except 0 (which means no `Dictionary_ID`).
1304 It's used by decoders to check if they use the correct dictionary.
1307 If the frame is going to be distributed in a private environment,
1308 any `Dictionary_ID` can be used.
1309 However, for public distribution of compressed frames,
1310 the following ranges are reserved and shall not be used :
1312 - low range : <= 32767
1313 - high range : >= (2^31)
1315 __`Entropy_Tables`__ : following the same format as the tables in compressed blocks.
1316 See the relevant [FSE](#fse-table-description)
1317 and [Huffman](#huffman-tree-description) sections for how to decode these tables.
1318 They are stored in following order :
1319 Huffman tables for literals, FSE table for offsets,
1320 FSE table for match lengths, and FSE table for literals lengths.
1321 These tables populate the Repeat Stats literals mode and
1322 Repeat distribution mode for sequence decoding.
1323 It's finally followed by 3 offset values, populating recent offsets (instead of using `{1,4,8}`),
1324 stored in order, 4-bytes __little-endian__ each, for a total of 12 bytes.
1325 Each recent offset must have a value < dictionary size.
1327 __`Content`__ : The rest of the dictionary is its content.
1328 The content act as a "past" in front of data to compress or decompress,
1329 so it can be referenced in sequence commands.
1330 As long as the amount of data decoded from this frame is less than or
1331 equal to `Window_Size`, sequence commands may specify offsets longer
1332 than the total length of decoded output so far to reference back to the
1333 dictionary. After the total output has surpassed `Window_Size` however,
1334 this is no longer allowed and the dictionary is no longer accessible.
1336 [compressed blocks]: #the-format-of-compressed_block
1339 Appendix A - Decoding tables for predefined codes
1340 -------------------------------------------------
1342 This appendix contains FSE decoding tables
1343 for the predefined literal length, match length, and offset codes.
1344 The tables have been constructed using the algorithm as given above in chapter
1345 "from normalized distribution to decoding tables".
1346 The tables here can be used as examples
1347 to crosscheck that an implementation build its decoding tables correctly.
1349 #### Literal Length Code:
1351 | State | Symbol | Number_Of_Bits | Base |
1352 | ----- | ------ | -------------- | ---- |
1370 | 17 | 25 | 5 | 32 |
1382 | 29 | 10 | 5 | 32 |
1385 | 32 | 16 | 5 | 32 |
1387 | 34 | 19 | 5 | 32 |
1389 | 36 | 22 | 5 | 32 |
1392 | 39 | 25 | 4 | 16 |
1393 | 40 | 26 | 5 | 32 |
1404 | 51 | 11 | 5 | 32 |
1405 | 52 | 12 | 5 | 32 |
1407 | 54 | 17 | 5 | 32 |
1408 | 55 | 18 | 5 | 32 |
1409 | 56 | 20 | 5 | 32 |
1410 | 57 | 21 | 5 | 32 |
1411 | 58 | 23 | 5 | 32 |
1412 | 59 | 24 | 5 | 32 |
1418 #### Match Length Code:
1420 | State | Symbol | Number_Of_Bits | Base |
1421 | ----- | ------ | -------------- | ---- |
1489 | State | Symbol | Number_Of_Bits | Base |
1490 | ----- | ------ | -------------- | ---- |
1526 - 0.2.6 : fixed an error in huffman example, by Ulrich Kunitz
1527 - 0.2.5 : minor typos and clarifications
1528 - 0.2.4 : section restructuring, by Sean Purcell
1529 - 0.2.3 : clarified several details, by Sean Purcell
1530 - 0.2.2 : added predefined codes, by Johannes Rudolph
1531 - 0.2.1 : clarify field names, by Przemyslaw Skibinski
1532 - 0.2.0 : numerous format adjustments for zstd v0.8+
1533 - 0.1.2 : limit Huffman tree depth to 11 bits
1534 - 0.1.1 : reserved dictID ranges
1535 - 0.1.0 : initial release