1Zstandard Compression Format 2============================ 3 4### Notices 5 6Copyright (c) 2016-present Yann Collet, Facebook, Inc. 7 8Permission is granted to copy and distribute this document 9for any purpose and without charge, 10including translations into other languages 11and incorporation into compilations, 12provided that the copyright notice and this notice are preserved, 13and that any substantive changes or deletions from the original 14are clearly marked. 15Distribution of this document is unlimited. 16 17### Version 18 190.2.6 (19/08/17) 20 21 22Introduction 23------------ 24 25The purpose of this document is to define a lossless compressed data format, 26that is independent of CPU type, operating system, 27file system and character set, suitable for 28file compression, pipe and streaming compression, 29using the [Zstandard algorithm](http://www.zstandard.org). 30 31The data can be produced or consumed, 32even for an arbitrarily long sequentially presented input data stream, 33using only an a priori bounded amount of intermediate storage, 34and hence can be used in data communications. 35The format uses the Zstandard compression method, 36and optional [xxHash-64 checksum method](http://www.xxhash.org), 37for detection of data corruption. 38 39The data format defined by this specification 40does not attempt to allow random access to compressed data. 41 42This specification is intended for use by implementers of software 43to compress data into Zstandard format and/or decompress data from Zstandard format. 44The text of the specification assumes a basic background in programming 45at the level of bits and other primitive data representations. 46 47Unless otherwise indicated below, 48a compliant compressor must produce data sets 49that conform to the specifications presented here. 50It doesn’t need to support all options though. 51 52A compliant decompressor must be able to decompress 53at least one working set of parameters 54that conforms to the specifications presented here. 55It may also ignore informative fields, such as checksum. 56Whenever it does not support a parameter defined in the compressed stream, 57it must produce a non-ambiguous error code and associated error message 58explaining which parameter is unsupported. 59 60### Overall conventions 61In this document: 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` 64 65### Definitions 66Content compressed by Zstandard is transformed into a Zstandard __frame__. 67Multiple frames can be appended into a single file or stream. 68A frame is completely independent, has a defined beginning and end, 69and a set of parameters which tells the decoder how to decompress it. 70 71A frame encapsulates one or multiple __blocks__. 72Each block can be compressed or not, 73and has a guaranteed maximum content size, which depends on frame parameters. 74Unlike frames, each block depends on previous blocks for proper decoding. 75However, each block can be decompressed without waiting for its successor, 76allowing streaming operations. 77 78Overview 79--------- 80- [Frames](#frames) 81 - [Zstandard frames](#zstandard-frames) 82 - [Blocks](#blocks) 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) 88 - [FSE](#fse) 89 - [Huffman Coding](#huffman-coding) 90- [Dictionary Format](#dictionary-format) 91 92Frames 93------ 94Zstandard compressed data is made of one or more __frames__. 95Each frame is independent and can be decompressed indepedently of other frames. 96The decompressed content of multiple concatenated frames is the concatenation of 97each frame decompressed content. 98 99There are two frame formats defined by Zstandard: 100 Zstandard frames and Skippable frames. 101Zstandard frames contain compressed data, while 102skippable frames contain no data and can be used for metadata. 103 104## Zstandard frames 105The structure of a single Zstandard frame is following: 106 107| `Magic_Number` | `Frame_Header` |`Data_Block`| [More data blocks] | [`Content_Checksum`] | 108|:--------------:|:--------------:|:----------:| ------------------ |:--------------------:| 109| 4 bytes | 2-14 bytes | n bytes | | 0-4 bytes | 110 111__`Magic_Number`__ 112 1134 Bytes, __little-endian__ format. 114Value : 0xFD2FB528 115 116__`Frame_Header`__ 117 1182 to 14 Bytes, detailed in [`Frame_Header`](#frame_header). 119 120__`Data_Block`__ 121 122Detailed in [`Blocks`](#blocks). 123That’s where compressed data is stored. 124 125__`Content_Checksum`__ 126 127An optional 32-bit checksum, only present if `Content_Checksum_flag` is set. 128The content checksum is the result 129of [xxh64() hash function](http://www.xxhash.org) 130digesting the original (decoded) data as input, and a seed of zero. 131The low 4 bytes of the checksum are stored in __little-endian__ format. 132 133### `Frame_Header` 134 135The `Frame_Header` has a variable size, with a minimum of 2 bytes, 136and up to 14 bytes depending on optional parameters. 137The structure of `Frame_Header` is following: 138 139| `Frame_Header_Descriptor` | [`Window_Descriptor`] | [`Dictionary_ID`] | [`Frame_Content_Size`] | 140| ------------------------- | --------------------- | ----------------- | ---------------------- | 141| 1 byte | 0-1 byte | 0-4 bytes | 0-8 bytes | 142 143#### `Frame_Header_Descriptor` 144 145The first header's byte is called the `Frame_Header_Descriptor`. 146It describes which other fields are present. 147Decoding this byte is enough to tell the size of `Frame_Header`. 148 149| Bit number | Field name | 150| ---------- | ---------- | 151| 7-6 | `Frame_Content_Size_flag` | 152| 5 | `Single_Segment_flag` | 153| 4 | `Unused_bit` | 154| 3 | `Reserved_bit` | 155| 2 | `Content_Checksum_flag` | 156| 1-0 | `Dictionary_ID_flag` | 157 158In this table, bit 7 is the highest bit, while bit 0 is the lowest one. 159 160__`Frame_Content_Size_flag`__ 161 162This is a 2-bits flag (`= Frame_Header_Descriptor >> 6`), 163specifying if `Frame_Content_Size` (the decompressed data size) 164is provided within the header. 165`Flag_Value` provides `FCS_Field_Size`, 166which is the number of bytes used by `Frame_Content_Size` 167according to the following table: 168 169| `Flag_Value` | 0 | 1 | 2 | 3 | 170| -------------- | ------ | --- | --- | --- | 171|`FCS_Field_Size`| 0 or 1 | 2 | 4 | 8 | 172 173When `Flag_Value` is `0`, `FCS_Field_Size` depends on `Single_Segment_flag` : 174if `Single_Segment_flag` is set, `Field_Size` is 1. 175Otherwise, `Field_Size` is 0 : `Frame_Content_Size` is not provided. 176 177__`Single_Segment_flag`__ 178 179If this flag is set, 180data must be regenerated within a single continuous memory segment. 181 182In this case, `Window_Descriptor` byte is skipped, 183but `Frame_Content_Size` is necessarily present. 184As a consequence, the decoder must allocate a memory segment 185of size equal or larger than `Frame_Content_Size`. 186 187In order to preserve the decoder from unreasonable memory requirements, 188a decoder is allowed to reject a compressed frame 189which requests a memory size beyond decoder's authorized range. 190 191For broader compatibility, decoders are recommended to support 192memory sizes of at least 8 MB. 193This is only a recommendation, 194each decoder is free to support higher or lower limits, 195depending on local limitations. 196 197__`Unused_bit`__ 198 199The value of this bit should be set to zero. 200A decoder compliant with this specification version shall not interpret it. 201It might be used in a future version, 202to signal a property which is not mandatory to properly decode the frame. 203 204__`Reserved_bit`__ 205 206This bit is reserved for some future feature. 207Its value _must be zero_. 208A decoder compliant with this specification version must ensure it is not set. 209This bit may be used in a future revision, 210to signal a feature that must be interpreted to decode the frame correctly. 211 212__`Content_Checksum_flag`__ 213 214If this flag is set, a 32-bits `Content_Checksum` will be present at frame's end. 215See `Content_Checksum` paragraph. 216 217__`Dictionary_ID_flag`__ 218 219This is a 2-bits flag (`= FHD & 3`), 220telling if a dictionary ID is provided within the header. 221It also specifies the size of this field as `Field_Size`. 222 223|`Flag_Value`| 0 | 1 | 2 | 3 | 224| ---------- | --- | --- | --- | --- | 225|`Field_Size`| 0 | 1 | 2 | 4 | 226 227#### `Window_Descriptor` 228 229Provides guarantees on minimum memory buffer required to decompress a frame. 230This information is important for decoders to allocate enough memory. 231 232The `Window_Descriptor` byte is optional. 233When `Single_Segment_flag` is set, `Window_Descriptor` is not present. 234In this case, `Window_Size` is `Frame_Content_Size`, 235which can be any value from 0 to 2^64-1 bytes (16 ExaBytes). 236 237| Bit numbers | 7-3 | 2-0 | 238| ----------- | ---------- | ---------- | 239| Field name | `Exponent` | `Mantissa` | 240 241The minimum memory buffer size is called `Window_Size`. 242It is described by the following formulas : 243``` 244windowLog = 10 + Exponent; 245windowBase = 1 << windowLog; 246windowAdd = (windowBase / 8) * Mantissa; 247Window_Size = windowBase + windowAdd; 248``` 249The minimum `Window_Size` is 1 KB. 250The maximum `Window_Size` is `(1<<41) + 7*(1<<38)` bytes, which is 3.75 TB. 251 252To properly decode compressed data, 253a decoder will need to allocate a buffer of at least `Window_Size` bytes. 254 255In order to preserve decoder from unreasonable memory requirements, 256a decoder is allowed to reject a compressed frame 257which requests a memory size beyond decoder's authorized range. 258 259For improved interoperability, 260decoders are recommended to be compatible with `Window_Size <= 8 MB`, 261and encoders are recommended to not request more than 8 MB. 262It's merely a recommendation though, 263decoders are free to support larger or lower limits, 264depending on local limitations. 265 266#### `Dictionary_ID` 267 268This is a variable size field, which contains 269the ID of the dictionary required to properly decode the frame. 270`Dictionary_ID` field is optional. When it's not present, 271it's up to the decoder to make sure it uses the correct dictionary. 272 273Field size depends on `Dictionary_ID_flag`. 2741 byte can represent an ID 0-255. 2752 bytes can represent an ID 0-65535. 2764 bytes can represent an ID 0-4294967295. 277Format is __little-endian__. 278 279It's allowed to represent a small ID (for example `13`) 280with a large 4-bytes dictionary ID, even if it is less efficient. 281 282_Reserved ranges :_ 283If the frame is going to be distributed in a private environment, 284any dictionary ID can be used. 285However, for public distribution of compressed frames using a dictionary, 286the following ranges are reserved and shall not be used : 287- low range : `<= 32767` 288- high range : `>= (1 << 31)` 289 290#### `Frame_Content_Size` 291 292This 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. 296 297| `FCS_Field_Size` | Range | 298| ---------------- | ---------- | 299| 0 | unknown | 300| 1 | 0 - 255 | 301| 2 | 256 - 65791| 302| 4 | 0 - 2^32-1 | 303| 8 | 0 - 2^64-1 | 304 305`Frame_Content_Size` format is __little-endian__. 306When `FCS_Field_Size` is 1, 4 or 8 bytes, the value is read directly. 307When `FCS_Field_Size` is 2, _the offset of 256 is added_. 308It's allowed to represent a small size (for example `18`) using any compatible variant. 309 310 311Blocks 312------- 313 314After `Magic_Number` and `Frame_Header`, there are some number of blocks. 315Each frame must have at least one block, 316but there is no upper limit on the number of blocks per frame. 317 318The structure of a block is as follows: 319 320| `Block_Header` | `Block_Content` | 321|:--------------:|:---------------:| 322| 3 bytes | n bytes | 323 324`Block_Header` uses 3 bytes, written using __little-endian__ convention. 325It contains 3 fields : 326 327| `Last_Block` | `Block_Type` | `Block_Size` | 328|:------------:|:------------:|:------------:| 329| bit 0 | bits 1-2 | bits 3-23 | 330 331__`Last_Block`__ 332 333The lowest bit signals if this block is the last one. 334The frame will end after this last block. 335It may be followed by an optional `Content_Checksum` 336(see [Zstandard Frames](#zstandard-frames)). 337 338__`Block_Type`__ 339 340The next 2 bits represent the `Block_Type`. 341There are 4 block types : 342 343| Value | 0 | 1 | 2 | 3 | 344| ------------ | ----------- | ----------- | ------------------ | --------- | 345| `Block_Type` | `Raw_Block` | `RLE_Block` | `Compressed_Block` | `Reserved`| 346 347- `Raw_Block` - this is an uncompressed block. 348 `Block_Content` contains `Block_Size` bytes. 349 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. 353 354- `Compressed_Block` - this is a [Zstandard compressed block](#compressed-blocks), 355 explained later on. 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) 359 360- `Reserved` - this is not a block. 361 This value cannot be used with current version of this specification. 362 363__`Block_Size`__ 364 365The upper 21 bits of `Block_Header` represent the `Block_Size`. 366 367Block 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. 371 372A block can contain any number of bytes (even empty), 373up to `Block_Maximum_Decompressed_Size`, which is the smallest of : 374- `Window_Size` 375- 128 KB 376 377 378Compressed Blocks 379----------------- 380To decompress a compressed block, the compressed size must be provided 381from `Block_Size` field within `Block_Header`. 382 383A compressed block consists of 2 sections : 384- [Literals Section](#literals-section) 385- [Sequences Section](#sequences-section) 386 387The results of the two sections are then combined to produce the decompressed 388data in [Sequence Execution](#sequence-execution) 389 390#### Prerequisites 391To 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). 397 398Literals Section 399---------------- 400All literals are regrouped in the first part of the block. 401They can be decoded first, and then copied during [Sequence Execution], 402or they can be decoded on the flow during [Sequence Execution]. 403 404Literals can be stored uncompressed or compressed using Huffman prefix codes. 405When compressed, an optional tree description can be present, 406followed by 1 or 4 streams. 407 408| `Literals_Section_Header` | [`Huffman_Tree_Description`] | Stream1 | [Stream2] | [Stream3] | [Stream4] | 409| ------------------------- | ---------------------------- | ------- | --------- | --------- | --------- | 410 411 412#### `Literals_Section_Header` 413 414Header is in charge of describing how literals are packed. 415It's a byte-aligned variable-size bitfield, ranging from 1 to 5 bytes, 416using __little-endian__ convention. 417 418| `Literals_Block_Type` | `Size_Format` | `Regenerated_Size` | [`Compressed_Size`] | 419| --------------------- | ------------- | ------------------ | ------------------- | 420| 2 bits | 1 - 2 bits | 5 - 20 bits | 0 - 18 bits | 421 422In this representation, bits on the left are the lowest bits. 423 424__`Literals_Block_Type`__ 425 426This field uses 2 lowest bits of first byte, describing 4 different block types : 427 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 | 434 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. 440 See details below. 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. 446 447__`Size_Format`__ 448 449`Size_Format` is divided into 2 families : 450 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). 458 459For values spanning several bytes, convention is __little-endian__. 460 461__`Size_Format` for `Raw_Literals_Block` and `RLE_Literals_Block`__ : 462 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)` 475 476Only Stream1 is present for these cases. 477Note : it's allowed to represent a short value (for example `13`) 478using a long format, even if it's less efficient. 479 480__`Size_Format` for `Compressed_Literals_Block` and `Treeless_Literals_Block`__ : 481 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. 494 495Both `Compressed_Size` and `Regenerated_Size` fields follow __little-endian__ convention. 496Note: `Compressed_Size` __includes__ the size of the Huffman Tree description 497_when_ it is present. 498 499### Raw Literals Block 500The data in Stream1 is `Regenerated_Size` bytes long, 501it contains the raw literals data to be used during [Sequence Execution]. 502 503### RLE Literals Block 504Stream1 consists of a single byte which should be repeated `Regenerated_Size` times 505to generate the decoded literals. 506 507### Compressed Literals Block and Treeless Literals Block 508Both of these modes contain Huffman encoded data. 509`Treeless_Literals_Block` does not have a `Huffman_Tree_Description`. 510 511#### `Huffman_Tree_Description` 512This section is only present when `Literals_Block_Type` type is `Compressed_Literals_Block` (`2`). 513The format of the Huffman tree description can be found at [Huffman Tree description](#huffman-tree-description). 514The size of `Huffman_Tree_Description` is determined during decoding process, 515it must be used to determine where streams begin. 516`Total_Streams_Size = Compressed_Size - Huffman_Tree_Description_Size`. 517 518For `Treeless_Literals_Block`, 519the Huffman table comes from previously compressed literals block. 520 521Huffman compressed data consists of either 1 or 4 Huffman-coded streams. 522 523If only one stream is present, it is a single bitstream occupying the entire 524remaining portion of the literals block, encoded as described within 525[Huffman-Coded Streams](#huffman-coded-streams). 526 527If there are four streams, the literals section header only provides enough 528information to know the decompressed and compressed sizes of all four streams _combined_. 529The decompressed size of each stream is equal to `(Regenerated_Size+3)/4`, 530except for the last stream which may be up to 3 bytes smaller, 531to reach a total decompressed size as specified in `Regenerated_Size`. 532 533The compressed size of each stream is provided explicitly: 534the first 6 bytes of the compressed data consist of three 2-byte __little-endian__ fields, 535describing the compressed sizes of the first three streams. 536`Stream4_Size` is computed from total `Total_Streams_Size` minus sizes of other streams. 537 538`Stream4_Size = Total_Streams_Size - 6 - Stream1_Size - Stream2_Size - Stream3_Size`. 539 540Note: remember that `Total_Streams_Size` can be smaller than `Compressed_Size` in header, 541because `Compressed_Size` also contains `Huffman_Tree_Description_Size` when it is present. 542 543Each of these 4 bitstreams is then decoded independently as a Huffman-Coded stream, 544as described at [Huffman-Coded Streams](#huffman-coded-streams) 545 546 547Sequences Section 548----------------- 549A compressed block is a succession of _sequences_ . 550A sequence is a literal copy command, followed by a match copy command. 551A literal copy command specifies a length. 552It is the number of bytes to be copied (or extracted) from the Literals Section. 553A match copy command specifies an offset and a length. 554 555When all _sequences_ are decoded, 556if there are literals left in the _literal section_, 557these bytes are added at the end of the block. 558 559This is described in more detail in [Sequence Execution](#sequence-execution) 560 561The `Sequences_Section` regroup all symbols required to decode commands. 562There are 3 symbol types : literals lengths, offsets and match lengths. 563They are encoded together, interleaved, in a single _bitstream_. 564 565The `Sequences_Section` starts by a header, 566followed by optional probability tables for each symbol type, 567followed by the bitstream. 568 569| `Sequences_Section_Header` | [`Literals_Length_Table`] | [`Offset_Table`] | [`Match_Length_Table`] | bitStream | 570| -------------------------- | ------------------------- | ---------------- | ---------------------- | --------- | 571 572To decode the `Sequences_Section`, it's required to know its size. 573This size is deduced from `Block_Size - Literals_Section_Size`. 574 575 576#### `Sequences_Section_Header` 577 578Consists of 2 items: 579- `Number_of_Sequences` 580- Symbol compression modes 581 582__`Number_of_Sequences`__ 583 584This is a variable size field using between 1 and 3 bytes. 585Let'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. 592 593__Symbol compression modes__ 594 595This is a single byte, defining the compression mode of each symbol type. 596 597|Bit number| 7-6 | 5-4 | 3-2 | 1-0 | 598| -------- | ----------------------- | -------------- | -------------------- | ---------- | 599|Field name| `Literals_Lengths_Mode` | `Offsets_Mode` | `Match_Lengths_Mode` | `Reserved` | 600 601The last field, `Reserved`, must be all-zeroes. 602 603`Literals_Lengths_Mode`, `Offsets_Mode` and `Match_Lengths_Mode` define the `Compression_Mode` of 604literals lengths, offsets, and match lengths symbols respectively. 605 606They follow the same enumeration : 607 608| Value | 0 | 1 | 2 | 3 | 609| ------------------ | ----------------- | ---------- | --------------------- | ------------- | 610| `Compression_Mode` | `Predefined_Mode` | `RLE_Mode` | `FSE_Compressed_Mode` | `Repeat_Mode` | 611 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. 627 628#### The codes for literals lengths, match lengths, and offsets. 629 630Each symbol is a _code_ in its own context, 631which specifies `Baseline` and `Number_of_Bits` to add. 632_Codes_ are FSE compressed, 633and interleaved with raw additional bits in the same bitstream. 634 635##### Literals length codes 636 637Literals length codes are values ranging from `0` to `35` included. 638They define lengths from 0 to 131071 bytes. 639The literals length is equal to the decoded `Baseline` plus 640the result of reading `Number_of_Bits` bits from the bitstream, 641as a __little-endian__ value. 642 643| `Literals_Length_Code` | 0-15 | 644| ---------------------- | ---------------------- | 645| length | `Literals_Length_Code` | 646| `Number_of_Bits` | 0 | 647 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 | 652 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 | 657 658| `Literals_Length_Code` | 32 | 33 | 34 | 35 | 659| ---------------------- | ---- | ---- | ---- | ---- | 660| `Baseline` | 8192 |16384 |32768 |65536 | 661| `Number_of_Bits` | 13 | 14 | 15 | 16 | 662 663 664##### Match length codes 665 666Match length codes are values ranging from `0` to `52` included. 667They define lengths from 3 to 131074 bytes. 668The match length is equal to the decoded `Baseline` plus 669the result of reading `Number_of_Bits` bits from the bitstream, 670as a __little-endian__ value. 671 672| `Match_Length_Code` | 0-31 | 673| ------------------- | ----------------------- | 674| value | `Match_Length_Code` + 3 | 675| `Number_of_Bits` | 0 | 676 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 | 681 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 | 686 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 | 691 692##### Offset codes 693 694Offset codes are values ranging from `0` to `N`. 695 696A decoder is free to limit its maximum `N` supported. 697Recommendation is to support at least up to `22`. 698For information, at the time of this writing. 699the reference decoder supports a maximum `N` value of `28` in 64-bits mode. 700 701An offset code is also the number of additional bits to read in __little-endian__ fashion, 702and can be translated into an `Offset_Value` using the following formulas : 703 704``` 705Offset_Value = (1 << offsetCode) + readNBits(offsetCode); 706if (Offset_Value > 3) offset = Offset_Value - 3; 707``` 708It means that maximum `Offset_Value` is `(2^(N+1))-1` and it supports back-reference distance up to `(2^(N+1))-4` 709but is limited by [maximum back-reference distance](#window_descriptor). 710 711`Offset_Value` from 1 to 3 are special : they define "repeat codes". 712This is described in more detail in [Repeat Offsets](#repeat-offsets). 713 714#### Decoding Sequences 715FSE bitstreams are read in reverse direction than written. In zstd, 716the compressor writes bits forward into a block and the decompressor 717must read the bitstream _backwards_. 718 719To find the start of the bitstream it is therefore necessary to 720know the offset of the last byte of the block which can be found 721by counting `Block_Size` bytes after the block header. 722 723After writing the last bit containing information, the compressor 724writes a single `1`-bit and then fills the byte with 0-7 `0` bits of 725padding. The last byte of the compressed bitstream cannot be `0` for 726that reason. 727 728When decompressing, the last byte containing the padding is the first 729byte to read. The decompressor needs to skip 0-7 initial `0`-bits and 730the first `1`-bit it occurs. Afterwards, the useful part of the bitstream 731begins. 732 733FSE decoding requires a 'state' to be carried from symbol to symbol. 734For more explanation on FSE decoding, see the [FSE section](#fse). 735 736For sequence decoding, a separate state keeps track of each 737literal lengths, offsets, and match lengths symbols. 738Some FSE primitives are also used. 739For more details on the operation of these primitives, see the [FSE section](#fse). 740 741##### Starting states 742The bitstream starts with initial FSE state values, 743each using the required number of bits in their respective _accuracy_, 744decoded previously from their normalized distribution. 745 746It starts by `Literals_Length_State`, 747followed by `Offset_State`, 748and finally `Match_Length_State`. 749 750Reminder : always keep in mind that all values are read _backward_, 751so the 'start' of the bitstream is at the highest position in memory, 752immediately before the last `1`-bit for padding. 753 754After decoding the starting states, a single sequence is decoded 755`Number_Of_Sequences` times. 756These sequences are decoded in order from first to last. 757Since the compressor writes the bitstream in the forward direction, 758this means the compressor must encode the sequences starting with the last 759one and ending with the first. 760 761##### Decoding a sequence 762For each of the symbol types, the FSE state can be used to determine the appropriate code. 763The code then defines the baseline and number of bits to read for each type. 764See the [description of the codes] for how to determine these values. 765 766[description of the codes]: #the-codes-for-literals-lengths-match-lengths-and-offsets 767 768Decoding starts by reading the `Number_of_Bits` required to decode `Offset`. 769It then does the same for `Match_Length`, and then for `Literals_Length`. 770This sequence is then used for [sequence execution](#sequence-execution). 771 772If it is not the last sequence in the block, 773the next operation is to update states. 774Using the rules pre-calculated in the decoding tables, 775`Literals_Length_State` is updated, 776followed by `Match_Length_State`, 777and then `Offset_State`. 778See the [FSE section](#fse) for details on how to update states from the bitstream. 779 780This operation will be repeated `Number_of_Sequences` times. 781At the end, the bitstream shall be entirely consumed, 782otherwise the bitstream is considered corrupted. 783 784#### Default Distributions 785If `Predefined_Mode` is selected for a symbol type, 786its FSE decoding table is generated from a predefined distribution table defined here. 787For details on how to convert this distribution into a decoding table, see the [FSE section]. 788 789[FSE section]: #from-normalized-distribution-to-decoding-tables 790 791##### Literals Length 792The decoding table uses an accuracy log of 6 bits (64 states). 793``` 794short 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, 797 -1,-1,-1,-1 }; 798``` 799 800##### Match Length 801The decoding table uses an accuracy log of 6 bits (64 states). 802``` 803short 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, 807 -1,-1,-1,-1,-1 }; 808``` 809 810##### Offset Codes 811The decoding table uses an accuracy log of 5 bits (32 states), 812and supports a maximum `N` value of 28, allowing offset values up to 536,870,908 . 813 814If any sequence in the compressed block requires a larger offset than this, 815it's not possible to use the default distribution to represent it. 816``` 817short 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 }; 820``` 821 822 823Sequence Execution 824------------------ 825Once literals and sequences have been decoded, 826they are combined to produce the decoded content of a block. 827 828Each sequence consists of a tuple of (`literals_length`, `offset_value`, `match_length`), 829decoded as described in the [Sequences Section](#sequences-section). 830To execute a sequence, first copy `literals_length` bytes from the literals section 831to the output. 832 833Then `match_length` bytes are copied from previous decoded data. 834The offset to copy from is determined by `offset_value`: 835if `offset_value > 3`, then the offset is `offset_value - 3`. 836If `offset_value` is from 1-3, the offset is a special repeat offset value. 837See the [repeat offset](#repeat-offsets) section for how the offset is determined 838in this case. 839 840The offset is defined as from the current position, so an offset of 6 841and a match length of 3 means that 3 bytes should be copied from 6 bytes back. 842Note that all offsets leading to previously decoded data 843must be smaller than `Window_Size` defined in `Frame_Header_Descriptor`. 844 845#### Repeat offsets 846As seen in [Sequence Execution](#sequence-execution), 847the first 3 values define a repeated offset and we will call them 848`Repeated_Offset1`, `Repeated_Offset2`, and `Repeated_Offset3`. 849They are sorted in recency order, with `Repeated_Offset1` meaning "most recent one". 850 851If `offset_value == 1`, then the offset used is `Repeated_Offset1`, etc. 852 853There is an exception though, when current sequence's `literals_length = 0`. 854In this case, repeated offsets are shifted by one, 855so an `offset_value` of 1 means `Repeated_Offset2`, 856an `offset_value` of 2 means `Repeated_Offset3`, 857and an `offset_value` of 3 means `Repeated_Offset1 - 1_byte`. 858 859For the first block, the starting offset history is populated with the following values : 1, 4 and 8 (in order). 860 861Then each block gets its starting offset history from the ending values of the most recent `Compressed_Block`. 862Note that blocks which are not `Compressed_Block` are skipped, they do not contribute to offset history. 863 864[Offset Codes]: #offset-codes 865 866###### Offset updates rules 867 868The newest offset takes the lead in offset history, 869shifting others back (up to its previous place if it was already present). 870 871This means that when `Repeated_Offset1` (most recent) is used, history is unmodified. 872When `Repeated_Offset2` is used, it's swapped with `Repeated_Offset1`. 873If any other offset is used, it becomes `Repeated_Offset1` and the rest are shift back by one. 874 875 876Skippable Frames 877---------------- 878 879| `Magic_Number` | `Frame_Size` | `User_Data` | 880|:--------------:|:------------:|:-----------:| 881| 4 bytes | 4 bytes | n bytes | 882 883Skippable frames allow the insertion of user-defined data 884into a flow of concatenated frames. 885Its design is pretty straightforward, 886with the sole objective to allow the decoder to quickly skip 887over user-defined data and continue decoding. 888 889Skippable frames defined in this specification are compatible with [LZ4] ones. 890 891[LZ4]:http://www.lz4.org 892 893__`Magic_Number`__ 894 8954 Bytes, __little-endian__ format. 896Value : 0x184D2A5?, which means any value from 0x184D2A50 to 0x184D2A5F. 897All 16 values are valid to identify a skippable frame. 898 899__`Frame_Size`__ 900 901This is the size, in bytes, of the following `User_Data` 902(without including the magic number nor the size field itself). 903This field is represented using 4 Bytes, __little-endian__ format, unsigned 32-bits. 904This means `User_Data` can’t be bigger than (2^32-1) bytes. 905 906__`User_Data`__ 907 908The `User_Data` can be anything. Data will just be skipped by the decoder. 909 910 911Entropy Encoding 912---------------- 913Two types of entropy encoding are used by the Zstandard format: 914FSE, and Huffman coding. 915 916FSE 917--- 918FSE, short for Finite State Entropy, is an entropy codec based on [ANS]. 919FSE encoding/decoding involves a state that is carried over between symbols, 920so decoding must be done in the opposite direction as encoding. 921Therefore, all FSE bitstreams are read from end to beginning. 922 923For additional details on FSE, see [Finite State Entropy]. 924 925[Finite State Entropy]:https://github.com/Cyan4973/FiniteStateEntropy/ 926 927FSE decoding involves a decoding table which has a power of 2 size, and contain three elements: 928`Symbol`, `Num_Bits`, and `Baseline`. 929The `log2` of the table size is its `Accuracy_Log`. 930The FSE state represents an index in this table. 931 932To obtain the initial state value, consume `Accuracy_Log` bits from the stream as a __little-endian__ value. 933The next symbol in the stream is the `Symbol` indicated in the table for that state. 934To obtain the next state value, 935the decoder should consume `Num_Bits` bits from the stream as a __little-endian__ value and add it to `Baseline`. 936 937[ANS]: https://en.wikipedia.org/wiki/Asymmetric_Numeral_Systems 938 939### FSE Table Description 940To decode FSE streams, it is necessary to construct the decoding table. 941The Zstandard format encodes FSE table descriptions as follows: 942 943An FSE distribution table describes the probabilities of all symbols 944from `0` to the last present one (included) 945on a normalized scale of `1 << Accuracy_Log` . 946 947It's a bitstream which is read forward, in __little-endian__ fashion. 948It's not necessary to know its exact size, 949since it will be discovered and reported by the decoding process. 950 951The bitstream starts by reporting on which scale it operates. 952`Accuracy_Log = low4bits + 5`. 953 954Then follows each symbol value, from `0` to last present one. 955The number of bits used by each field is variable. 956It depends on : 957 958- Remaining probabilities + 1 : 959 __example__ : 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. 964 965- Value decoded : small values use 1 less bit : 966 __example__ : 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 : 973 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 | 980 981Symbols probabilities are read one by one, in order. 982 983Probability is obtained from Value decoded by following formula : 984`Proba = value - 1` 985 986It means value `0` becomes negative probability `-1`. 987`-1` is a special probability, which means "less than 1". 988Its effect on distribution table is described in the [next section]. 989For the purpose of calculating total allocated probability points, it counts as one. 990 991[next section]:#from-normalized-distribution-to-decoding-tables 992 993When a symbol has a __probability__ of `zero`, 994it is followed by a 2-bits repeat flag. 995This repeat flag tells how many probabilities of zeroes follow the current one. 996It provides a number ranging from 0 to 3. 997If it is a 3, another 2-bits repeat flag follows, and so on. 998 999When last symbol reaches cumulated total of `1 << Accuracy_Log`, 1000decoding is complete. 1001If the last symbol makes cumulated total go above `1 << Accuracy_Log`, 1002distribution is considered corrupted. 1003 1004Then the decoder can tell how many bytes were used in this process, 1005and how many symbols are present. 1006The bitstream consumes a round number of bytes. 1007Any remaining bit within the last byte is just unused. 1008 1009##### From normalized distribution to decoding tables 1010 1011The distribution of normalized probabilities is enough 1012to create a unique decoding table. 1013 1014It follows the following build rule : 1015 1016The table has a size of `Table_Size = 1 << Accuracy_Log`. 1017Each cell describes the symbol decoded, 1018and instructions to get the next state. 1019 1020Symbols are scanned in their natural order for "less than 1" probabilities. 1021Symbols with this probability are being attributed a single cell, 1022starting from the end of the table. 1023These symbols define a full state reset, reading `Accuracy_Log` bits. 1024 1025All remaining symbols are sorted in their natural order. 1026Starting from symbol `0` and table position `0`, 1027each symbol gets attributed as many cells as its probability. 1028Cell allocation is spreaded, not linear : 1029each successor position follow this rule : 1030 1031``` 1032position += (tableSize>>1) + (tableSize>>3) + 3; 1033position &= tableSize-1; 1034``` 1035 1036A position is skipped if already occupied by a "less than 1" probability symbol. 1037`position` does not reset between symbols, it simply iterates through 1038each position in the table, switching to the next symbol when enough 1039states have been allocated to the current one. 1040 1041The result is a list of state values. 1042Each state will decode the current symbol. 1043 1044To get the `Number_of_Bits` and `Baseline` required for next state, 1045it's first necessary to sort all states in their natural order. 1046The lower states will need 1 more bit than higher ones. 1047 1048__Example__ : 1049Presuming a symbol has a probability of 5. 1050It receives 5 state values. States are sorted in natural order. 1051 1052Next power of 2 is 8. 1053Space of probabilities is divided into 8 equal parts. 1054Presuming the `Accuracy_Log` is 7, it defines 128 states. 1055Divided by 8, each share is 16 large. 1056 1057In order to reach 8, 8-5=3 lowest states will count "double", 1058taking shares twice larger, 1059requiring one more bit in the process. 1060 1061Numbering starts from higher states using less bits. 1062 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 | 1070 1071The next state is determined from current state 1072by reading the required `Number_of_Bits`, and adding the specified `Baseline`. 1073 1074See [Appendix A] for the results of this process applied to the default distributions. 1075 1076[Appendix A]: #appendix-a---decoding-tables-for-predefined-codes 1077 1078Huffman Coding 1079-------------- 1080Zstandard Huffman-coded streams are read backwards, 1081similar to the FSE bitstreams. 1082Therefore, to find the start of the bitstream, it is therefore to 1083know the offset of the last byte of the Huffman-coded stream. 1084 1085After writing the last bit containing information, the compressor 1086writes a single `1`-bit and then fills the byte with 0-7 `0` bits of 1087padding. The last byte of the compressed bitstream cannot be `0` for 1088that reason. 1089 1090When decompressing, the last byte containing the padding is the first 1091byte to read. The decompressor needs to skip 0-7 initial `0`-bits and 1092the first `1`-bit it occurs. Afterwards, the useful part of the bitstream 1093begins. 1094 1095The bitstream contains Huffman-coded symbols in __little-endian__ order, 1096with the codes defined by the method below. 1097 1098### Huffman Tree Description 1099Prefix coding represents symbols from an a priori known alphabet 1100by bit sequences (codewords), one codeword for each symbol, 1101in a manner such that different symbols may be represented 1102by bit sequences of different lengths, 1103but a parser can always parse an encoded string 1104unambiguously symbol-by-symbol. 1105 1106Given an alphabet with known symbol frequencies, 1107the Huffman algorithm allows the construction of an optimal prefix code 1108using the fewest bits of any possible prefix codes for that alphabet. 1109 1110Prefix code must not exceed a maximum code length. 1111More bits improve accuracy but cost more header size, 1112and require more memory or more complex decoding operations. 1113This specification limits maximum code length to 11 bits. 1114 1115 1116##### Representation 1117 1118All literal values from zero (included) to last present one (excluded) 1119are represented by `Weight` with values from `0` to `Max_Number_of_Bits`. 1120Transformation from `Weight` to `Number_of_Bits` follows this formula : 1121``` 1122Number_of_Bits = Weight ? (Max_Number_of_Bits + 1 - Weight) : 0 1123``` 1124The last symbol's `Weight` is deduced from previously decoded ones, 1125by completing to the nearest power of 2. 1126This power of 2 gives `Max_Number_of_Bits`, the depth of the current tree. 1127 1128__Example__ : 1129Let's presume the following Huffman tree must be described : 1130 1131| literal | 0 | 1 | 2 | 3 | 4 | 5 | 1132| ---------------- | --- | --- | --- | --- | --- | --- | 1133| `Number_of_Bits` | 1 | 2 | 3 | 0 | 4 | 4 | 1134 1135The tree depth is 4, since its smallest element uses 4 bits. 1136Value `5` will not be listed as it can be determined from the values for 0-4, 1137nor will values above `5` as they are all 0. 1138Values from `0` to `4` will be listed using `Weight` instead of `Number_of_Bits`. 1139Weight formula is : 1140``` 1141Weight = Number_of_Bits ? (Max_Number_of_Bits + 1 - Number_of_Bits) : 0 1142``` 1143It gives the following series of weights : 1144 1145| literal | 0 | 1 | 2 | 3 | 4 | 1146| -------- | --- | --- | --- | --- | --- | 1147| `Weight` | 4 | 3 | 2 | 0 | 1 | 1148 1149The decoder will do the inverse operation : 1150having collected weights of literals from `0` to `4`, 1151it knows the last literal, `5`, is present with a non-zero weight. 1152The weight of `5` can be determined by advancing to the next power of 2. 1153The sum of `2^(Weight-1)` (excluding 0's) is : 1154`8 + 4 + 2 + 0 + 1 = 15`. 1155Nearest power of 2 is 16. 1156Therefore, `Max_Number_of_Bits = 4` and `Weight[5] = 1`. 1157 1158##### Huffman Tree header 1159 1160This is a single byte value (0-255), 1161which describes how to decode the list of weights. 1162 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. 1174 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). 1178 1179##### Finite State Entropy (FSE) compression of Huffman weights 1180 1181In this case, the series of Huffman weights is compressed using FSE compression. 1182It's a single bitstream with 2 interleaved states, 1183sharing a single distribution table. 1184 1185To decode an FSE bitstream, it is necessary to know its compressed size. 1186Compressed size is provided by `headerByte`. 1187It's also necessary to know its _maximum possible_ decompressed size, 1188which is `255`, since literal values span from `0` to `255`, 1189and last symbol's weight is not represented. 1190 1191An FSE bitstream starts by a header, describing probabilities distribution. 1192It will create a Decoding Table. 1193For a list of Huffman weights, the maximum accuracy log is 7 bits. 1194For more description see the [FSE header description](#fse-table-description) 1195 1196The Huffman header compression uses 2 states, 1197which share the same FSE distribution table. 1198The first state (`State1`) encodes the even indexed symbols, 1199and the second (`State2`) encodes the odd indexes. 1200`State1` is initialized first, and then `State2`, and they take turns 1201decoding a single symbol and updating their state. 1202For more details on these FSE operations, see the [FSE section](#fse). 1203 1204The number of symbols to decode is determined 1205by tracking bitStream overflow condition: 1206If updating state after decoding a symbol would require more bits than 1207remain in the stream, it is assumed that extra bits are 0. Then, 1208the symbols for each of the final states are decoded and the process is complete. 1209 1210##### Conversion from weights to Huffman prefix codes 1211 1212All present symbols shall now have a `Weight` value. 1213It is possible to transform weights into Number_of_Bits, using this formula: 1214``` 1215Number_of_Bits = Number_of_Bits ? Max_Number_of_Bits + 1 - Weight : 0 1216``` 1217Symbols are sorted by `Weight`. Within same `Weight`, symbols keep natural order. 1218Symbols with a `Weight` of zero are removed. 1219Then, starting from lowest weight, prefix codes are distributed in order. 1220 1221__Example__ : 1222Let's presume the following list of weights has been decoded : 1223 1224| Literal | 0 | 1 | 2 | 3 | 4 | 5 | 1225| -------- | --- | --- | --- | --- | --- | --- | 1226| `Weight` | 4 | 3 | 2 | 0 | 1 | 1 | 1227 1228Sorted by weight and then natural order, 1229it gives the following distribution : 1230 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 | 1236 1237### Huffman-coded Streams 1238Given a Huffman decoding table, 1239it's possible to decode a Huffman-coded stream. 1240 1241Each bitstream must be read _backward_, 1242that is starting from the end down to the beginning. 1243Therefore it's necessary to know the size of each bitstream. 1244 1245It's also necessary to know exactly which _bit_ is the latest. 1246This is detected by a final bit flag : 1247the highest bit of latest byte is a final-bit-flag. 1248Consequently, a last byte of `0` is not possible. 1249And the final-bit-flag itself is not part of the useful bitstream. 1250Hence, the last byte contains between 0 and 7 useful bits. 1251 1252Starting from the end, 1253it's possible to read the bitstream in a __little-endian__ fashion, 1254keeping track of already used bits. Since the bitstream is encoded in reverse 1255order, starting from the end read symbols in forward order. 1256 1257For example, if the literal sequence "0145" was encoded using above prefix code, 1258it would be encoded (in reverse order) as: 1259 1260|Symbol | 5 | 4 | 1 | 0 | Padding | 1261|--------|------|------|----|---|---------| 1262|Encoding|`0000`|`0001`|`01`|`1`| `00001` | 1263 1264Resulting in following 2-bytes bitstream : 1265``` 126600010000 00001101 1267``` 1268 1269Here is an alternative representation with the symbol codes separated by underscore: 1270``` 12710001_0000 00001_1_01 1272``` 1273 1274Reading highest `Max_Number_of_Bits` bits, 1275it's possible to compare extracted value to decoding table, 1276determining the symbol to decode and number of bits to discard. 1277 1278The process continues up to reading the required number of symbols per stream. 1279If a bitstream is not entirely and exactly consumed, 1280hence reaching exactly its beginning position with _all_ bits consumed, 1281the decoding process is considered faulty. 1282 1283 1284Dictionary Format 1285----------------- 1286 1287Zstandard is compatible with "raw content" dictionaries, 1288free of any format restriction, except that they must be at least 8 bytes. 1289These dictionaries function as if they were just the `Content` part 1290of a formatted dictionary. 1291 1292But dictionaries created by `zstd --train` follow a format, described here. 1293 1294__Pre-requisites__ : a dictionary has a size, 1295 defined either by a buffer limit, or a file size. 1296 1297| `Magic_Number` | `Dictionary_ID` | `Entropy_Tables` | `Content` | 1298| -------------- | --------------- | ---------------- | --------- | 1299 1300__`Magic_Number`__ : 4 bytes ID, value 0xEC30A437, __little-endian__ format 1301 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. 1305 1306_Reserved ranges :_ 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 : 1311 1312 - low range : <= 32767 1313 - high range : >= (2^31) 1314 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. 1326 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. 1335 1336[compressed blocks]: #the-format-of-compressed_block 1337 1338 1339Appendix A - Decoding tables for predefined codes 1340------------------------------------------------- 1341 1342This appendix contains FSE decoding tables 1343for the predefined literal length, match length, and offset codes. 1344The tables have been constructed using the algorithm as given above in chapter 1345"from normalized distribution to decoding tables". 1346The tables here can be used as examples 1347to crosscheck that an implementation build its decoding tables correctly. 1348 1349#### Literal Length Code: 1350 1351| State | Symbol | Number_Of_Bits | Base | 1352| ----- | ------ | -------------- | ---- | 1353| 0 | 0 | 4 | 0 | 1354| 1 | 0 | 4 | 16 | 1355| 2 | 1 | 5 | 32 | 1356| 3 | 3 | 5 | 0 | 1357| 4 | 4 | 5 | 0 | 1358| 5 | 6 | 5 | 0 | 1359| 6 | 7 | 5 | 0 | 1360| 7 | 9 | 5 | 0 | 1361| 8 | 10 | 5 | 0 | 1362| 9 | 12 | 5 | 0 | 1363| 10 | 14 | 6 | 0 | 1364| 11 | 16 | 5 | 0 | 1365| 12 | 18 | 5 | 0 | 1366| 13 | 19 | 5 | 0 | 1367| 14 | 21 | 5 | 0 | 1368| 15 | 22 | 5 | 0 | 1369| 16 | 24 | 5 | 0 | 1370| 17 | 25 | 5 | 32 | 1371| 18 | 26 | 5 | 0 | 1372| 19 | 27 | 6 | 0 | 1373| 20 | 29 | 6 | 0 | 1374| 21 | 31 | 6 | 0 | 1375| 22 | 0 | 4 | 32 | 1376| 23 | 1 | 4 | 0 | 1377| 24 | 2 | 5 | 0 | 1378| 25 | 4 | 5 | 32 | 1379| 26 | 5 | 5 | 0 | 1380| 27 | 7 | 5 | 32 | 1381| 28 | 8 | 5 | 0 | 1382| 29 | 10 | 5 | 32 | 1383| 30 | 11 | 5 | 0 | 1384| 31 | 13 | 6 | 0 | 1385| 32 | 16 | 5 | 32 | 1386| 33 | 17 | 5 | 0 | 1387| 34 | 19 | 5 | 32 | 1388| 35 | 20 | 5 | 0 | 1389| 36 | 22 | 5 | 32 | 1390| 37 | 23 | 5 | 0 | 1391| 38 | 25 | 4 | 0 | 1392| 39 | 25 | 4 | 16 | 1393| 40 | 26 | 5 | 32 | 1394| 41 | 28 | 6 | 0 | 1395| 42 | 30 | 6 | 0 | 1396| 43 | 0 | 4 | 48 | 1397| 44 | 1 | 4 | 16 | 1398| 45 | 2 | 5 | 32 | 1399| 46 | 3 | 5 | 32 | 1400| 47 | 5 | 5 | 32 | 1401| 48 | 6 | 5 | 32 | 1402| 49 | 8 | 5 | 32 | 1403| 50 | 9 | 5 | 32 | 1404| 51 | 11 | 5 | 32 | 1405| 52 | 12 | 5 | 32 | 1406| 53 | 15 | 6 | 0 | 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 | 1413| 60 | 35 | 6 | 0 | 1414| 61 | 34 | 6 | 0 | 1415| 62 | 33 | 6 | 0 | 1416| 63 | 32 | 6 | 0 | 1417 1418#### Match Length Code: 1419 1420| State | Symbol | Number_Of_Bits | Base | 1421| ----- | ------ | -------------- | ---- | 1422| 0 | 0 | 6 | 0 | 1423| 1 | 1 | 4 | 0 | 1424| 2 | 2 | 5 | 32 | 1425| 3 | 3 | 5 | 0 | 1426| 4 | 5 | 5 | 0 | 1427| 5 | 6 | 5 | 0 | 1428| 6 | 8 | 5 | 0 | 1429| 7 | 10 | 6 | 0 | 1430| 8 | 13 | 6 | 0 | 1431| 9 | 16 | 6 | 0 | 1432| 10 | 19 | 6 | 0 | 1433| 11 | 22 | 6 | 0 | 1434| 12 | 25 | 6 | 0 | 1435| 13 | 28 | 6 | 0 | 1436| 14 | 31 | 6 | 0 | 1437| 15 | 33 | 6 | 0 | 1438| 16 | 35 | 6 | 0 | 1439| 17 | 37 | 6 | 0 | 1440| 18 | 39 | 6 | 0 | 1441| 19 | 41 | 6 | 0 | 1442| 20 | 43 | 6 | 0 | 1443| 21 | 45 | 6 | 0 | 1444| 22 | 1 | 4 | 16 | 1445| 23 | 2 | 4 | 0 | 1446| 24 | 3 | 5 | 32 | 1447| 25 | 4 | 5 | 0 | 1448| 26 | 6 | 5 | 32 | 1449| 27 | 7 | 5 | 0 | 1450| 28 | 9 | 6 | 0 | 1451| 29 | 12 | 6 | 0 | 1452| 30 | 15 | 6 | 0 | 1453| 31 | 18 | 6 | 0 | 1454| 32 | 21 | 6 | 0 | 1455| 33 | 24 | 6 | 0 | 1456| 34 | 27 | 6 | 0 | 1457| 35 | 30 | 6 | 0 | 1458| 36 | 32 | 6 | 0 | 1459| 37 | 34 | 6 | 0 | 1460| 38 | 36 | 6 | 0 | 1461| 39 | 38 | 6 | 0 | 1462| 40 | 40 | 6 | 0 | 1463| 41 | 42 | 6 | 0 | 1464| 42 | 44 | 6 | 0 | 1465| 43 | 1 | 4 | 32 | 1466| 44 | 1 | 4 | 48 | 1467| 45 | 2 | 4 | 16 | 1468| 46 | 4 | 5 | 32 | 1469| 47 | 5 | 5 | 32 | 1470| 48 | 7 | 5 | 32 | 1471| 49 | 8 | 5 | 32 | 1472| 50 | 11 | 6 | 0 | 1473| 51 | 14 | 6 | 0 | 1474| 52 | 17 | 6 | 0 | 1475| 53 | 20 | 6 | 0 | 1476| 54 | 23 | 6 | 0 | 1477| 55 | 26 | 6 | 0 | 1478| 56 | 29 | 6 | 0 | 1479| 57 | 52 | 6 | 0 | 1480| 58 | 51 | 6 | 0 | 1481| 59 | 50 | 6 | 0 | 1482| 60 | 49 | 6 | 0 | 1483| 61 | 48 | 6 | 0 | 1484| 62 | 47 | 6 | 0 | 1485| 63 | 46 | 6 | 0 | 1486 1487#### Offset Code: 1488 1489| State | Symbol | Number_Of_Bits | Base | 1490| ----- | ------ | -------------- | ---- | 1491| 0 | 0 | 5 | 0 | 1492| 1 | 6 | 4 | 0 | 1493| 2 | 9 | 5 | 0 | 1494| 3 | 15 | 5 | 0 | 1495| 4 | 21 | 5 | 0 | 1496| 5 | 3 | 5 | 0 | 1497| 6 | 7 | 4 | 0 | 1498| 7 | 12 | 5 | 0 | 1499| 8 | 18 | 5 | 0 | 1500| 9 | 23 | 5 | 0 | 1501| 10 | 5 | 5 | 0 | 1502| 11 | 8 | 4 | 0 | 1503| 12 | 14 | 5 | 0 | 1504| 13 | 20 | 5 | 0 | 1505| 14 | 2 | 5 | 0 | 1506| 15 | 7 | 4 | 16 | 1507| 16 | 11 | 5 | 0 | 1508| 17 | 17 | 5 | 0 | 1509| 18 | 22 | 5 | 0 | 1510| 19 | 4 | 5 | 0 | 1511| 20 | 8 | 4 | 16 | 1512| 21 | 13 | 5 | 0 | 1513| 22 | 19 | 5 | 0 | 1514| 23 | 1 | 5 | 0 | 1515| 24 | 6 | 4 | 16 | 1516| 25 | 10 | 5 | 0 | 1517| 26 | 16 | 5 | 0 | 1518| 27 | 28 | 5 | 0 | 1519| 28 | 27 | 5 | 0 | 1520| 29 | 26 | 5 | 0 | 1521| 30 | 25 | 5 | 0 | 1522| 31 | 24 | 5 | 0 | 1523 1524Version changes 1525--------------- 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 1536