doc: Add RFC documents

1 files changed, 3027 insertions, 0 deletions

diff --git a/doc/rfc/rfc8478.txt b/doc/rfc/rfc8478.txt
new file mode 100644
index 0000000..e4ac22a
--- /dev/null
+++ b/doc/rfc/rfc8478.txt
@@ -0,0 +1,3027 @@
+
+
+
+
+
+
+Internet Engineering Task Force (IETF)                         Y. Collet
+Request for Comments: 8478                             M. Kucherawy, Ed.
+Category: Informational                                         Facebook
+ISSN: 2070-1721                                             October 2018
+
+
+       Zstandard Compression and the application/zstd Media Type
+
+Abstract
+
+   Zstandard, or "zstd" (pronounced "zee standard"), is a data
+   compression mechanism.  This document describes the mechanism and
+   registers a media type and content encoding to be used when
+   transporting zstd-compressed content via Multipurpose Internet Mail
+   Extensions (MIME).
+
+   Despite use of the word "standard" as part of its name, readers are
+   advised that this document is not an Internet Standards Track
+   specification; it is being published for informational purposes only.
+
+Status of This Memo
+
+   This document is not an Internet Standards Track specification; it is
+   published for informational purposes.
+
+   This document is a product of the Internet Engineering Task Force
+   (IETF).  It represents the consensus of the IETF community.  It has
+   received public review and has been approved for publication by the
+   Internet Engineering Steering Group (IESG).  Not all documents
+   approved by the IESG are candidates for any level of Internet
+   Standard; see Section 2 of RFC 7841.
+
+   Information about the current status of this document, any errata,
+   and how to provide feedback on it may be obtained at
+   https://www.rfc-editor.org/info/rfc8478.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                     [Page 1]
+
+RFC 8478                    application/zstd                October 2018
+
+
+Copyright Notice
+
+   Copyright (c) 2018 IETF Trust and the persons identified as the
+   document authors.  All rights reserved.
+
+   This document is subject to BCP 78 and the IETF Trust's Legal
+   Provisions Relating to IETF Documents
+   (https://trustee.ietf.org/license-info) in effect on the date of
+   publication of this document.  Please review these documents
+   carefully, as they describe your rights and restrictions with respect
+   to this document.  Code Components extracted from this document must
+   include Simplified BSD License text as described in Section 4.e of
+   the Trust Legal Provisions and are provided without warranty as
+   described in the Simplified BSD License.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                     [Page 2]
+
+RFC 8478                    application/zstd                October 2018
+
+
+Table of Contents
+
+   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   4
+   2.  Definitions . . . . . . . . . . . . . . . . . . . . . . . . .   4
+   3.  Compression Algorithm . . . . . . . . . . . . . . . . . . . .   5
+     3.1.  Frames  . . . . . . . . . . . . . . . . . . . . . . . . .   6
+       3.1.1.  Zstandard Frames  . . . . . . . . . . . . . . . . . .   6
+         3.1.1.1.  Frame Header  . . . . . . . . . . . . . . . . . .   7
+         3.1.1.2.  Blocks  . . . . . . . . . . . . . . . . . . . . .  12
+         3.1.1.3.  Compressed Blocks . . . . . . . . . . . . . . . .  14
+         3.1.1.4.  Sequence Execution  . . . . . . . . . . . . . . .  28
+         3.1.1.5.  Repeat Offsets  . . . . . . . . . . . . . . . . .  29
+       3.1.2.  Skippable Frames  . . . . . . . . . . . . . . . . . .  30
+   4.  Entropy Encoding  . . . . . . . . . . . . . . . . . . . . . .  30
+     4.1.  FSE . . . . . . . . . . . . . . . . . . . . . . . . . . .  31
+       4.1.1.  FSE Table Description . . . . . . . . . . . . . . . .  31
+     4.2.  Huffman Coding  . . . . . . . . . . . . . . . . . . . . .  34
+       4.2.1.  Huffman Tree Description  . . . . . . . . . . . . . .  35
+         4.2.1.1.  Huffman Tree Header . . . . . . . . . . . . . . .  36
+         4.2.1.2.  FSE Compression of Huffman Weights  . . . . . . .  37
+         4.2.1.3.  Conversion from Weights to Huffman Prefix Codes .  38
+       4.2.2.  Huffman-Coded Streams . . . . . . . . . . . . . . . .  39
+   5.  Dictionary Format . . . . . . . . . . . . . . . . . . . . . .  40
+   6.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  42
+     6.1.  The 'application/zstd' Media Type . . . . . . . . . . . .  42
+     6.2.  Content Encoding  . . . . . . . . . . . . . . . . . . . .  43
+     6.3.  Dictionaries  . . . . . . . . . . . . . . . . . . . . . .  43
+   7.  Security Considerations . . . . . . . . . . . . . . . . . . .  43
+   8.  Implementation Status . . . . . . . . . . . . . . . . . . . .  44
+   9.  References  . . . . . . . . . . . . . . . . . . . . . . . . .  45
+     9.1.  Normative References  . . . . . . . . . . . . . . . . . .  45
+     9.2.  Informative References  . . . . . . . . . . . . . . . . .  45
+   Appendix A.  Decoding Tables for Predefined Codes . . . . . . . .  46
+     A.1.  Literal Length Code Table . . . . . . . . . . . . . . . .  46
+     A.2.  Match Length Code Table . . . . . . . . . . . . . . . . .  49
+     A.3.  Offset Code Table . . . . . . . . . . . . . . . . . . . .  52
+   Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . .  53
+   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  54
+
+
+
+
+
+
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                     [Page 3]
+
+RFC 8478                    application/zstd                October 2018
+
+
+1.  Introduction
+
+   Zstandard, or "zstd" (pronounced "zee standard"), is a data
+   compression mechanism, akin to gzip [RFC1952].
+
+   Despite use of the word "standard" as part of its name, readers are
+   advised that this document is not an Internet Standards Track
+   specification; it is being published for informational purposes only.
+
+   This document describes the Zstandard format.  Also, to enable the
+   transport of a data object compressed with Zstandard, this document
+   registers a media type that can be used to identify such content when
+   it is used in a payload encoded using Multipurpose Internet Mail
+   Extensions (MIME).
+
+2.  Definitions
+
+   Some terms used elsewhere in this document are defined here for
+   clarity.
+
+   uncompressed:  Describes an arbitrary set of bytes in their original
+      form, prior to being subjected to compression.
+
+   compress, compression:  The act of processing a set of bytes via the
+      compression mechanism described here.
+
+   compressed:  Describes the result of passing a set of bytes through
+      this mechanism.  The original input has thus been compressed.
+
+   decompress, decompression:  The act of processing a set of bytes
+      through the inverse of the compression mechanism described here,
+      in an attempt to recover the original set of bytes prior to
+      compression.
+
+   decompressed:  Describes the result of passing a set of bytes through
+      the reverse of this mechanism.  When this is successful, the
+      decompressed payload and the uncompressed payload are
+      indistinguishable.
+
+   encode:  The process of translating data from one form to another;
+      this may include compression or it may refer to other translations
+      done as part of this specification.
+
+   decode:  The reverse of "encode"; describes a process of reversing a
+      prior encoding to recover the original content.
+
+
+
+
+
+
+Collet & Kucherawy            Informational                     [Page 4]
+
+RFC 8478                    application/zstd                October 2018
+
+
+   frame:  Content compressed by Zstandard is transformed into a
+      Zstandard frame.  Multiple frames can be appended into a single
+      file or stream.  A frame is completely independent, has a defined
+      beginning and end, and has a set of parameters that tells the
+      decoder how to decompress it.
+
+   block:  A frame encapsulates one or multiple blocks.  Each block
+      contains arbitrary content, which is described by its header, and
+      has a guaranteed maximum content size that depends upon frame
+      parameters.  Unlike frames, each block depends on previous blocks
+      for proper decoding.  However, each block can be decompressed
+      without waiting for its successor, allowing streaming operations.
+
+   natural order:  A sequence or ordering of objects or values that is
+      typical of that type of object or value.  A set of unique
+      integers, for example, is in "natural order" if when progressing
+      from one element in the set or sequence to the next, there is
+      never a decrease in value.
+
+   The naming convention for identifiers within the specification is
+   Mixed_Case_With_Underscores.  Identifiers inside square brackets
+   indicate that the identifier is optional in the presented context.
+
+3.  Compression Algorithm
+
+   This section describes the Zstandard algorithm.
+
+   The purpose of this document is to define a lossless compressed data
+   format that is a) independent of the CPU type, operating system, file
+   system, and character set and b) is suitable for file compression and
+   pipe and streaming compression, using the Zstandard algorithm.  The
+   text of the specification assumes a basic background in programming
+   at the level of bits and other primitive data representations.
+
+   The data can be produced or consumed, even for an arbitrarily long
+   sequentially presented input data stream, using only an a priori
+   bounded amount of intermediate storage, and hence can be used in data
+   communications.  The format uses the Zstandard compression method,
+   and an optional xxHash-64 checksum method [XXHASH], for detection of
+   data corruption.
+
+   The data format defined by this specification does not attempt to
+   allow random access to compressed data.
+
+   Unless otherwise indicated below, a compliant compressor must produce
+   data sets that conform to the specifications presented here.
+   However, it does not need to support all options.
+
+
+
+
+Collet & Kucherawy            Informational                     [Page 5]
+
+RFC 8478                    application/zstd                October 2018
+
+
+   A compliant decompressor must be able to decompress at least one
+   working set of parameters that conforms to the specifications
+   presented here.  It may also ignore informative fields, such as the
+   checksum.  Whenever it does not support a parameter defined in the
+   compressed stream, it must produce a non-ambiguous error code and
+   associated error message explaining which parameter is unsupported.
+
+   This specification is intended for use by implementers of software to
+   compress data into Zstandard format and/or decompress data from
+   Zstandard format.  The Zstandard format is supported by an open
+   source reference implementation, written in portable C, and available
+   at [ZSTD].
+
+3.1.  Frames
+
+   Zstandard compressed data is made up of one or more frames.  Each
+   frame is independent and can be decompressed independently of other
+   frames.  The decompressed content of multiple concatenated frames is
+   the concatenation of each frame's decompressed content.
+
+   There are two frame formats defined for Zstandard: Zstandard frames
+   and skippable frames.  Zstandard frames contain compressed data,
+   while skippable frames contain custom user metadata.
+
+3.1.1.  Zstandard Frames
+
+   The structure of a single Zstandard frame is as follows:
+
+     +--------------------+------------+
+     |    Magic_Number    | 4 bytes    |
+     +--------------------+------------+
+     |    Frame_Header    | 2-14 bytes |
+     +--------------------+------------+
+     |     Data_Block     | n bytes    |
+     +--------------------+------------+
+     | [More Data_Blocks] |            |
+     +--------------------+------------+
+     | [Content_Checksum] | 0-4 bytes  |
+     +--------------------+------------+
+
+   Magic_Number:  4 bytes, little-endian format.  Value: 0xFD2FB528.
+
+   Frame_Header:  2 to 14 bytes, detailed in Section 3.1.1.1.
+
+   Data_Block:  Detailed in Section 3.1.1.2.  This is where data
+      appears.
+
+
+
+
+
+Collet & Kucherawy            Informational                     [Page 6]
+
+RFC 8478                    application/zstd                October 2018
+
+
+   Content_Checksum:  An optional 32-bit checksum, only present if
+      Content_Checksum_Flag is set.  The content checksum is the result
+      of the XXH64() hash function [XXHASH] digesting the original
+      (decoded) data as input, and a seed of zero.  The low 4 bytes of
+      the checksum are stored in little-endian format.
+
+   The magic number was selected to be less probable to find at the
+   beginning of an arbitrary file.  It avoids trivial patterns (0x00,
+   0xFF, repeated bytes, increasing bytes, etc.), contains byte values
+   outside of ASCII range, and doesn't map into UTF-8 space, all of
+   which reduce the likelihood of its appearance at the top of a text
+   file.
+
+3.1.1.1.  Frame Header
+
+   The frame header has a variable size, with a minimum of 2 bytes and
+   up to 14 bytes depending on optional parameters.  The structure of
+   Frame_Header is as follows:
+
+     +-------------------------+-----------+
+     | Frame_Header_Descriptor | 1 byte    |
+     +-------------------------+-----------+
+     |   [Window_Descriptor]   | 0-1 byte  |
+     +-------------------------+-----------+
+     |     [Dictionary_ID]     | 0-4 bytes |
+     +-------------------------+-----------+
+     |  [Frame_Content_Size]   | 0-8 bytes |
+     +-------------------------+-----------+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                     [Page 7]
+
+RFC 8478                    application/zstd                October 2018
+
+
+3.1.1.1.1.  Frame_Header_Descriptor
+
+   The first header's byte is called the Frame_Header_Descriptor.  It
+   describes which other fields are present.  Decoding this byte is
+   enough to tell the size of Frame_Header.
+
+     +------------+-------------------------+
+     | Bit Number | Field Name              |
+     +------------+-------------------------+
+     |    7-6     | Frame_Content_Size_Flag |
+     +------------+-------------------------+
+     |     5      | Single_Segment_Flag     |
+     +------------+-------------------------+
+     |     4      | (unused)                |
+     +------------+-------------------------+
+     |     3      | (reserved)              |
+     +------------+-------------------------+
+     |     2      | Content_Checksum_Flag   |
+     +------------+-------------------------+
+     |    1-0     | Dictionary_ID_Flag      |
+     +------------+-------------------------+
+
+   In this table, bit 7 is the highest bit, while bit 0 is the lowest
+   one.
+
+3.1.1.1.1.1.  Frame_Content_Size_Flag
+
+   This is a 2-bit flag (equivalent to Frame_Header_Descriptor right-
+   shifted 6 bits) specifying whether Frame_Content_Size (the
+   decompressed data size) is provided within the header.  Flag_Value
+   provides FCS_Field_Size, which is the number of bytes used by
+   Frame_Content_Size according to the following table:
+
+     +----------------+--------+---+---+---+
+     | Flag_Value     |   0    | 1 | 2 | 3 |
+     +----------------+--------+---+---+---+
+     | FCS_Field_Size | 0 or 1 | 2 | 4 | 8 |
+     +----------------+--------+---+---+---+
+
+   When Flag_Value is 0, FCS_Field_Size depends on Single_Segment_Flag:
+   If Single_Segment_Flag is set, FCS_Field_Size is 1.  Otherwise,
+   FCS_Field_Size is 0; Frame_Content_Size is not provided.
+
+
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                     [Page 8]
+
+RFC 8478                    application/zstd                October 2018
+
+
+3.1.1.1.1.2.  Single_Segment_Flag
+
+   If this flag is set, data must be regenerated within a single
+   continuous memory segment.
+
+   In this case, Window_Descriptor byte is skipped, but
+   Frame_Content_Size is necessarily present.  As a consequence, the
+   decoder must allocate a memory segment of size equal or larger than
+   Frame_Content_Size.
+
+   In order to protect the decoder from unreasonable memory
+   requirements, a decoder is allowed to reject a compressed frame that
+   requests a memory size beyond the decoder's authorized range.
+
+   For broader compatibility, decoders are recommended to support memory
+   sizes of at least 8 MB.  This is only a recommendation; each decoder
+   is free to support higher or lower limits, depending on local
+   limitations.
+
+3.1.1.1.1.3.  Unused Bit
+
+   A decoder compliant with this specification version shall not
+   interpret this bit.  It might be used in a future version, to signal
+   a property that is not mandatory to properly decode the frame.  An
+   encoder compliant with this specification must set this bit to zero.
+
+3.1.1.1.1.4.  Reserved Bit
+
+   This bit is reserved for some future feature.  Its value must be
+   zero.  A decoder compliant with this specification version must
+   ensure it is not set.  This bit may be used in a future revision, to
+   signal a feature that must be interpreted to decode the frame
+   correctly.
+
+3.1.1.1.1.5.  Content_Checksum_Flag
+
+   If this flag is set, a 32-bit Content_Checksum will be present at the
+   frame's end.  See the description of Content_Checksum above.
+
+
+
+
+
+
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                     [Page 9]
+
+RFC 8478                    application/zstd                October 2018
+
+
+3.1.1.1.1.6.  Dictionary_ID_Flag
+
+   This is a 2-bit flag (= Frame_Header_Descriptor & 0x3) indicating
+   whether a dictionary ID is provided within the header.  It also
+   specifies the size of this field as DID_Field_Size:
+
+     +----------------+---+---+---+---+
+     | Flag_Value     | 0 | 1 | 2 | 3 |
+     +----------------+---+---+---+---+
+     | DID_Field_Size | 0 | 1 | 2 | 4 |
+     +----------------+---+---+---+---+
+
+3.1.1.1.2.  Window Descriptor
+
+   This provides guarantees about the minimum memory buffer required to
+   decompress a frame.  This information is important for decoders to
+   allocate enough memory.
+
+   The Window_Descriptor byte is optional.  When Single_Segment_Flag is
+   set, Window_Descriptor is not present.  In this case, Window_Size is
+   Frame_Content_Size, which can be any value from 0 to 2^64-1 bytes (16
+   ExaBytes).
+
+     +------------+----------+----------+
+     | Bit Number |   7-3    |   2-0    |
+     +------------+----------+----------+
+     | Field Name | Exponent | Mantissa |
+     +------------+----------+----------+
+
+   The minimum memory buffer size is called Window_Size.  It is
+   described by the following formulae:
+
+     windowLog = 10 + Exponent;
+     windowBase = 1 << windowLog;
+     windowAdd = (windowBase / 8) * Mantissa;
+     Window_Size = windowBase + windowAdd;
+
+   The minimum Window_Size is 1 KB.  The maximum Window_Size is (1<<41)
+   + 7*(1<<38) bytes, which is 3.75 TB.
+
+   In general, larger Window_Size values tend to improve the compression
+   ratio, but at the cost of increased memory usage.
+
+   To properly decode compressed data, a decoder will need to allocate a
+   buffer of at least Window_Size bytes.
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 10]
+
+RFC 8478                    application/zstd                October 2018
+
+
+   In order to protect decoders from unreasonable memory requirements, a
+   decoder is allowed to reject a compressed frame that requests a
+   memory size beyond decoder's authorized range.
+
+   For improved interoperability, it's recommended for decoders to
+   support values of Window_Size up to 8 MB and for encoders not to
+   generate frames requiring a Window_Size larger than 8 MB.  It's
+   merely a recommendation though, and decoders are free to support
+   larger or lower limits, depending on local limitations.
+
+3.1.1.1.3.  Dictionary_ID
+
+   This is a variable size field, which contains the ID of the
+   dictionary required to properly decode the frame.  This field is
+   optional.  When it's not present, it's up to the decoder to know
+   which dictionary to use.
+
+   Dictionary_ID field size is provided by DID_Field_Size.
+   DID_Field_Size is directly derived from the value of
+   Dictionary_ID_Flag.  One byte can represent an ID 0-255; 2 bytes can
+   represent an ID 0-65535; 4 bytes can represent an ID 0-4294967295.
+   Format is little-endian.
+
+   It is permitted to represent a small ID (for example, 13) with a
+   large 4-byte dictionary ID, even if it is less efficient.
+
+   Within private environments, any dictionary ID can be used.  However,
+   for frames and dictionaries distributed in public space,
+   Dictionary_ID must be attributed carefully.  The following ranges are
+   reserved for use only with dictionaries that have been registered
+   with IANA (see Section 6.3):
+
+   low range:  <= 32767
+   high range:  >= (1 << 31)
+
+   Any other value for Dictionary_ID can be used by private arrangement
+   between participants.
+
+   Any payload presented for decompression that references an
+   unregistered reserved dictionary ID results in an error.
+
+
+
+
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 11]
+
+RFC 8478                    application/zstd                October 2018
+
+
+3.1.1.1.4.  Frame Content Size
+
+   This is the original (uncompressed) size.  This information is
+   optional.  Frame_Content_Size uses a variable number of bytes,
+   provided by FCS_Field_Size.  FCS_Field_Size is provided by the value
+   of Frame_Content_Size_Flag.  FCS_Field_Size can be equal to 0 (not
+   present), 1, 2, 4, or 8 bytes.
+
+     +----------------+--------------+
+     | FCS Field Size | Range        |
+     +----------------+--------------+
+     |        0       | unknown      |
+     +----------------+--------------+
+     |        1       | 0 - 255      |
+     +----------------+--------------+
+     |        2       | 256 - 65791  |
+     +----------------+--------------+
+     |        4       | 0 - 2^32 - 1 |
+     +----------------+--------------+
+     |        8       | 0 - 2^64 - 1 |
+     +----------------+--------------+
+
+   Frame_Content_Size format is little-endian.  When FCS_Field_Size is
+   1, 4, or 8 bytes, the value is read directly.  When FCS_Field_Size is
+   2, the offset of 256 is added.  It's allowed to represent a small
+   size (for example 18) using any compatible variant.
+
+3.1.1.2.  Blocks
+
+   After Magic_Number and Frame_Header, there are some number of blocks.
+   Each frame must have at least 1 block, but there is no upper limit on
+   the number of blocks per frame.
+
+   The structure of a block is as follows:
+
+     +--------------+---------------+
+     | Block_Header | Block_Content |
+     +--------------+---------------+
+     |    3 bytes   |    n bytes    |
+     +--------------+---------------+
+
+
+
+
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 12]
+
+RFC 8478                    application/zstd                October 2018
+
+
+   Block_Header uses 3 bytes, written using little-endian convention.
+   It contains three fields:
+
+     +------------+------------+------------+
+     | Last_Block | Block_Type | Block_Size |
+     +------------+------------+------------+
+     |    bit 0   |   bits 1-2 |  bits 3-23 |
+     +------------+------------+------------+
+
+3.1.1.2.1.  Last_Block
+
+   The lowest bit (Last_Block) signals whether this block is the last
+   one.  The frame will end after this last block.  It may be followed
+   by an optional Content_Checksum (see Section 3.1.1).
+
+3.1.1.2.2.  Block_Type
+
+   The next 2 bits represent the Block_Type.  There are four block
+   types:
+
+     +-----------+------------------+
+     |   Value   |    Block_Type    |
+     +-----------+------------------+
+     |     0     |     Raw_Block    |
+     +-----------+------------------+
+     |     1     |     RLE_Block    |
+     +-----------+------------------+
+     |     2     | Compressed_Block |
+     +-----------+------------------+
+     |     3     |     Reserved     |
+     +-----------+------------------+
+
+   Raw_Block:  This is an uncompressed block.  Block_Content contains
+      Block_Size bytes.
+
+   RLE_Block:  This is a single byte, repeated Block_Size times.
+      Block_Content consists of a single byte.  On the decompression
+      side, this byte must be repeated Block_Size times.
+
+   Compressed_Block:  This is a compressed block as described in
+      Section 3.1.1.3.  Block_Size is the length of Block_Content,
+      namely the compressed data.  The decompressed size is not known,
+      but its maximum possible value is guaranteed (see below).
+
+   Reserved:  This is not a block.  This value cannot be used with the
+      current specification.  If such a value is present, it is
+      considered to be corrupt data.
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 13]
+
+RFC 8478                    application/zstd                October 2018
+
+
+3.1.1.2.3.  Block_Size
+
+   The upper 21 bits of Block_Header represent the Block_Size.
+   Block_Size is the size of the block excluding the header.  A block
+   can contain any number of bytes (even zero), up to
+   Block_Maximum_Decompressed_Size, which is the smallest of:
+
+   o  Window_Size
+
+   o  128 KB
+
+   A Compressed_Block has the extra restriction that Block_Size is
+   always strictly less than the decompressed size.  If this condition
+   cannot be respected, the block must be sent uncompressed instead
+   (i.e., treated as a Raw_Block).
+
+3.1.1.3.  Compressed Blocks
+
+   To decompress a compressed block, the compressed size must be
+   provided from the Block_Size field within Block_Header.
+
+   A compressed block consists of two sections: a Literals
+   Section (Section 3.1.1.3.1) and a
+   Sequences_Section (Section 3.1.1.3.2).  The results of the two
+   sections are then combined to produce the decompressed data in
+   Sequence Execution (Section 3.1.1.4).
+
+   To decode a compressed block, the following elements are necessary:
+
+   o  Previous decoded data, up to a distance of Window_Size, or the
+      beginning of the Frame, whichever is smaller.  Single_Segment_Flag
+      will be set in the latter case.
+
+   o  List of "recent offsets" from the previous Compressed_Block.
+
+   o  The previous Huffman tree, required by Treeless_Literals_Block
+      type.
+
+   o  Previous Finite State Entropy (FSE) decoding tables, required by
+      Repeat_Mode, for each symbol type (literals lengths, match
+      lengths, offsets).
+
+   Note that decoding tables are not always from the previous
+   Compressed_Block:
+
+   o  Every decoding table can come from a dictionary.
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 14]
+
+RFC 8478                    application/zstd                October 2018
+
+
+   o  The Huffman tree comes from the previous
+      Compressed_Literals_Block.
+
+3.1.1.3.1.  Literals_Section_Header
+
+   All literals are regrouped in the first part of the block.  They can
+   be decoded first and then copied during Sequence Execution (see
+   Section 3.1.1.4), or they can be decoded on the flow during Sequence
+   Execution.
+
+   Literals can be stored uncompressed or compressed using Huffman
+   prefix codes.  When compressed, an optional tree description can be
+   present, followed by 1 or 4 streams.
+
+     +----------------------------+
+     |   Literals_Section_Header  |
+     +----------------------------+
+     | [Huffman_Tree_Description] |
+     +----------------------------+
+     |        [Jump_Table]        |
+     +----------------------------+
+     |          Stream_1          |
+     +----------------------------+
+     |         [Stream_2]         |
+     +----------------------------+
+     |         [Stream_3]         |
+     +----------------------------+
+     |         [Stream_4]         |
+     +----------------------------+
+
+3.1.1.3.1.1.  Literals_Section_Header
+
+   This field describes how literals are packed.  It's a byte-aligned
+   variable-size bit field, ranging from 1 to 5 bytes, using little-
+   endian convention.
+
+     +---------------------+-----------+
+     | Literals_Block_Type |  2 bits   |
+     +---------------------+-----------+
+     |     Size_Format     | 1-2 bits  |
+     +---------------------+-----------+
+     |   Regenerated_Size  | 5-20 bits |
+     +---------------------+-----------+
+     |  [Compressed_Size]  | 0-18 bits |
+     +---------------------+-----------+
+
+   In this representation, bits at the top are the lowest bits.
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 15]
+
+RFC 8478                    application/zstd                October 2018
+
+
+   The Literals_Block_Type field uses the two lowest bits of the first
+   byte, describing four different block types:
+
+     +---------------------------+-------+
+     |    Literals_Block_Type    | Value |
+     +---------------------------+-------+
+     |     Raw_Literals_Block    |   0   |
+     +---------------------------+-------+
+     |     RLE_Literals_Block    |   1   |
+     +---------------------------+-------+
+     | Compressed_Literals_Block |   2   |
+     +---------------------------+-------+
+     |  Treeless_Literals_Block  |   3   |
+     +---------------------------+-------+
+
+   Raw_Literals_Block:  Literals are stored uncompressed.
+      Literals_Section_Content is Regenerated_Size.
+
+   RLE_Literals_Block:  Literals consist of a single-byte value repeated
+      Regenerated_Size times.  Literals_Section_Content is 1.
+
+   Compressed_Literals_Block:  This is a standard Huffman-compressed
+      block, starting with a Huffman tree description.  See details
+      below.  Literals_Section_Content is Compressed_Size.
+
+   Treeless_Literals_Block:  This is a Huffman-compressed block, using
+      the Huffman tree from the previous Compressed_Literals_Block, or a
+      dictionary if there is no previous Huffman-compressed literals
+      block.  Huffman_Tree_Description will be skipped.  Note that if
+      this mode is triggered without any previous Huffman-table in the
+      frame (or dictionary, per Section 5), it should be treated as data
+      corruption.  Literals_Section_Content is Compressed_Size.
+
+   The Size_Format is divided into two families:
+
+   o  For Raw_Literals_Block and RLE_Literals_Block, it's only necessary
+      to decode Regenerated_Size.  There is no Compressed_Size field.
+
+   o  For Compressed_Block and Treeless_Literals_Block, it's required to
+      decode both Compressed_Size and Regenerated_Size (the decompressed
+      size).  It's also necessary to decode the number of streams (1 or
+      4).
+
+   For values spanning several bytes, the convention is little endian.
+
+   Size_Format for Raw_Literals_Block and RLE_Literals_Block uses 1 or 2
+   bits.  Its value is (Literals_Section_Header[0]>>2) & 0x3.
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 16]
+
+RFC 8478                    application/zstd                October 2018
+
+
+   Size_Format == 00 or 10:  Size_Format uses 1 bit.  Regenerated_Size
+      uses 5 bits (value 0-31).  Literals_Section_Header uses 1 byte.
+      Regenerated_Size = Literal_Section_Header[0]>>3.
+
+   Size_Format == 01:  Size_Format uses 2 bits.  Regenerated_Size uses
+      12 bits (values 0-4095).  Literals_Section_Header uses 2 bytes.
+      Regenerated_Size = (Literals_Section_Header[0]>>4) +
+      (Literals_Section_Header[1]<<4).
+
+   Size_Format == 11:  Size_Format uses 2 bits.  Regenerated_Size uses
+      20 bits (values 0-1048575).  Literals_Section_Header uses 3 bytes.
+      Regenerated_Size = (Literals_Section_Header[0]>>4) +
+      (Literals_Section_Header[1]<<4) + (Literals_Section_Header[2]<<12)
+
+   Only Stream_1 is present for these cases.  Note that it is permitted
+   to represent a short value (for example, 13) using a long format,
+   even if it's less efficient.
+
+   Size_Format for Compressed_Literals_Block and Treeless_Literals_Block
+   always uses 2 bits.
+
+   Size_Format == 00:  A single stream.  Both Regenerated_Size and
+      Compressed_Size use 10 bits (values 0-1023).
+      Literals_Section_Header uses 3 bytes.
+
+   Size_Format == 01:  4 streams.  Both Regenerated_Size and
+      Compressed_Size use 10 bits (values 0-1023).
+      Literals_Section_Header uses 3 bytes.
+
+   Size_Format == 10:  4 streams.  Both Regenerated_Size and
+      Compressed_Size use 14 bits (values 0-16383).
+      Literals_Section_Header uses 4 bytes.
+
+   Size_Format == 11:  4 streams.  Both Regenerated_Size and
+      Compressed_Size use 18 bits (values 0-262143).
+      Literals_Section_Header uses 5 bytes.
+
+   Both the Compressed_Size and Regenerated_Size fields follow little-
+   endian convention.  Note that Compressed_Size includes the size of
+   the Huffman_Tree_Description when it is present.
+
+3.1.1.3.1.2.  Raw_Literals_Block
+
+   The data in Stream_1 is Regenerated_Size bytes long.  It contains the
+   raw literals data to be used during Sequence Execution
+   (Section 3.1.1.3.2).
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 17]
+
+RFC 8478                    application/zstd                October 2018
+
+
+3.1.1.3.1.3.  RLE_Literals_Block
+
+   Stream_1 consists of a single byte that should be repeated
+   Regenerated_Size times to generate the decoded literals.
+
+3.1.1.3.1.4.  Compressed_Literals_Block and Treeless_Literals_Block
+
+   Both of these modes contain Huffman-encoded data.  For
+   Treeless_Literals_Block, the Huffman table comes from the previously
+   compressed literals block, or from a dictionary; see Section 5.
+
+3.1.1.3.1.5.  Huffman_Tree_Description
+
+   This section is only present when the Literals_Block_Type type is
+   Compressed_Literals_Block (2).  The format of
+   Huffman_Tree_Description can be found in Section 4.2.1.  The size of
+   Huffman_Tree_Description is determined during the decoding process.
+   It must be used to determine where streams begin.
+
+     Total_Streams_Size = Compressed_Size
+                          - Huffman_Tree_Description_Size
+
+3.1.1.3.1.6.  Jump_Table
+
+   The Jump_Table is only present when there are 4 Huffman-coded
+   streams.
+
+   (Reminder: Huffman-compressed data consists of either 1 or 4 Huffman-
+   coded streams.)
+
+   If only 1 stream is present, it is a single bitstream occupying the
+   entire remaining portion of the literals block, encoded as described
+   within Section 4.2.2.
+
+   If there are 4 streams, Literals_Section_Header only provides enough
+   information to know the decompressed and compressed sizes of all 4
+   streams combined.  The decompressed size of each stream is equal to
+   (Regenerated_Size+3)/4, except for the last stream, which may be up
+   to 3 bytes smaller, to reach a total decompressed size as specified
+   in Regenerated_Size.
+
+   The compressed size of each stream is provided explicitly in the
+   Jump_Table.  The Jump_Table is 6 bytes long and consists of three
+   2-byte little-endian fields, describing the compressed sizes of the
+   first 3 streams.  Stream4_Size is computed from Total_Streams_Size
+   minus sizes of other streams.
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 18]
+
+RFC 8478                    application/zstd                October 2018
+
+
+     Stream4_Size = Total_Streams_Size - 6
+                    - Stream1_Size - Stream2_Size
+                    - Stream3_Size
+
+   Note that if Stream1_Size + Stream2_Size + Stream3_Size exceeds
+   Total_Streams_Size, the data are considered corrupted.
+
+   Each of these 4 bitstreams is then decoded independently as a
+   Huffman-Coded stream, as described in Section 4.2.2.
+
+3.1.1.3.2.  Sequences_Section
+
+   A compressed block is a succession of sequences.  A sequence is a
+   literal copy command, followed by a match copy command.  A literal
+   copy command specifies a length.  It is the number of bytes to be
+   copied (or extracted) from the Literals Section.  A match copy
+   command specifies an offset and a length.
+
+   When all sequences are decoded, if there are literals left in the
+   literals section, these bytes are added at the end of the block.
+
+   This is described in more detail in Section 3.1.1.4.
+
+   The Sequences_Section regroups all symbols required to decode
+   commands.  There are three symbol types: literals lengths, offsets,
+   and match lengths.  They are encoded together, interleaved, in a
+   single "bitstream".
+
+   The Sequences_Section starts by a header, followed by optional
+   probability tables for each symbol type, followed by the bitstream.
+
+     Sequences_Section_Header
+       [Literals_Length_Table]
+       [Offset_Table]
+       [Match_Length_Table]
+       bitStream
+
+   To decode the Sequences_Section, it's necessary to know its size.
+   This size is deduced from the size of the Literals_Section:
+   Sequences_Section_Size = Block_Size - Literals_Section_Header -
+   Literals_Section_Content
+
+
+
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 19]
+
+RFC 8478                    application/zstd                October 2018
+
+
+3.1.1.3.2.1.  Sequences_Section_Header
+
+   This header consists of two items:
+
+   o  Number_of_Sequences
+
+   o  Symbol_Compression_Modes
+
+   Number_of_Sequences is a variable size field using between 1 and 3
+   bytes.  If the first byte is "byte0":
+
+   o  if (byte0 == 0): there are no sequences.  The sequence section
+      stops here.  Decompressed content is defined entirely as Literals
+      Section content.  The FSE tables used in Repeat_Mode are not
+      updated.
+
+   o  if (byte0 < 128): Number_of_Sequences = byte0.  Uses 1 byte.
+
+   o  if (byte0 < 255): Number_of_Sequences = ((byte0 - 128) << 8) +
+      byte1.  Uses 2 bytes.
+
+   o  if (byte0 == 255): Number_of_Sequences = byte1 + (byte2 << 8) +
+      0x7F00.  Uses 3 bytes.
+
+   Symbol_Compression_Modes is a single byte, defining the compression
+   mode of each symbol type.
+
+     +-------------+----------------------+
+     | Bit Number  |      Field Name      |
+     +-------------+----------------------+
+     |     7-6     | Literal_Lengths_Mode |
+     +-------------+----------------------+
+     |     5-4     |     Offsets_Mode     |
+     +-------------+----------------------+
+     |     3-2     |  Match_Lengths_Mode  |
+     +-------------+----------------------+
+     |     1-0     |       Reserved       |
+     +-------------+----------------------+
+
+   The last field, Reserved, must be all zeroes.
+
+
+
+
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 20]
+
+RFC 8478                    application/zstd                October 2018
+
+
+   Literals_Lengths_Mode, Offsets_Mode, and Match_Lengths_Mode define
+   the Compression_Mode of literals lengths, offsets, and match lengths
+   symbols, respectively.  They follow the same enumeration:
+
+     +-------+---------------------+
+     | Value |  Compression_Mode   |
+     +-------+---------------------+
+     |   0   |   Predefined_Mode   |
+     +-------+---------------------+
+     |   1   |      RLE_Mode       |
+     +-------+---------------------+
+     |   2   | FSE_Compressed_Mode |
+     +-------+---------------------+
+     |   3   |     Repeat_Mode     |
+     +-------+---------------------+
+
+   Predefined_Mode:  A predefined FSE (see Section 4.1) distribution
+      table is used, as defined in Section 3.1.1.3.2.2.  No distribution
+      table will be present.
+
+   RLE_Mode:  The table description consists of a single byte, which
+      contains the symbol's value.  This symbol will be used for all
+      sequences.
+
+   FSE_Compressed_Mode:  Standard FSE compression.  A distribution table
+      will be present.  The format of this distribution table is
+      described in Section 4.1.1.  Note that the maximum allowed
+      accuracy log for literals length and match length tables is 9, and
+      the maximum accuracy log for the offsets table is 8.  This mode
+      must not be used when only one symbol is present; RLE_Mode should
+      be used instead (although any other mode will work).
+
+   Repeat_Mode:  The table used in the previous Compressed_Block with
+      Number_Of_Sequences > 0 will be used again, or if this is the
+      first block, the table in the dictionary will be used.  Note that
+      this includes RLE_Mode, so if Repeat_Mode follows RLE_Mode, the
+      same symbol will be repeated.  It also includes Predefined_Mode,
+      in which case Repeat_Mode will have the same outcome as
+      Predefined_Mode.  No distribution table will be present.  If this
+      mode is used without any previous sequence table in the frame (or
+      dictionary; see Section 5) to repeat, this should be treated as
+      corruption.
+
+
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 21]
+
+RFC 8478                    application/zstd                October 2018
+
+
+3.1.1.3.2.1.1.  Sequence Codes for Lengths and Offsets
+
+   Each symbol is a code in its own context, which specifies Baseline
+   and Number_of_Bits to add.  Codes are FSE compressed and interleaved
+   with raw additional bits in the same bitstream.
+
+   Literals length codes are values ranging from 0 to 35 inclusive.
+   They define lengths from 0 to 131071 bytes.  The literals length is
+   equal to the decoded Baseline plus the result of reading
+   Number_of_Bits bits from the bitstream, as a little-endian value.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 22]
+
+RFC 8478                    application/zstd                October 2018
+
+
+     +----------------------+----------+----------------+
+     | Literals_Length_Code | Baseline | Number_of_Bits |
+     +----------------------+----------+----------------+
+     |         0-15         |  length  |       0        |
+     +----------------------+----------+----------------+
+     |          16          |    16    |       1        |
+     +----------------------+----------+----------------+
+     |          17          |    18    |       1        |
+     +----------------------+----------+----------------+
+     |          18          |    20    |       1        |
+     +----------------------+----------+----------------+
+     |          19          |    22    |       1        |
+     +----------------------+----------+----------------+
+     |          20          |    24    |       2        |
+     +----------------------+----------+----------------+
+     |          21          |    28    |       2        |
+     +----------------------+----------+----------------+
+     |          22          |    32    |       3        |
+     +----------------------+----------+----------------+
+     |          23          |    40    |       3        |
+     +----------------------+----------+----------------+
+     |          24          |    48    |       4        |
+     +----------------------+----------+----------------+
+     |          25          |    64    |       6        |
+     +----------------------+----------+----------------+
+     |          26          |    128   |       7        |
+     +----------------------+----------+----------------+
+     |          27          |    256   |       8        |
+     +----------------------+----------+----------------+
+     |          28          |    512   |       9        |
+     +----------------------+----------+----------------+
+     |          29          |   1024   |       10       |
+     +----------------------+----------+----------------+
+     |          30          |   2048   |       11       |
+     +----------------------+----------+----------------+
+     |          31          |   4096   |       12       |
+     +----------------------+----------+----------------+
+     |          32          |   8192   |       13       |
+     +----------------------+----------+----------------+
+     |          33          |  16384   |       14       |
+     +----------------------+----------+----------------+
+     |          34          |  32768   |       15       |
+     +----------------------+----------+----------------+
+     |          35          |  65536   |       16       |
+     +----------------------+----------+----------------+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 23]
+
+RFC 8478                    application/zstd                October 2018
+
+
+   Match length codes are values ranging from 0 to 52 inclusive.  They
+   define lengths from 3 to 131074 bytes.  The match length is equal to
+   the decoded Baseline plus the result of reading Number_of_Bits bits
+   from the bitstream, as a little-endian value.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 24]
+
+RFC 8478                    application/zstd                October 2018
+
+
+     +-------------------+-----------------------+----------------+
+     | Match_Length_Code |       Baseline        | Number_of_Bits |
+     +-------------------+-----------------------+----------------+
+     |        0-31       | Match_Length_Code + 3 |       0        |
+     +-------------------+-----------------------+----------------+
+     |         32        |          35           |       1        |
+     +-------------------+-----------------------+----------------+
+     |         33        |          37           |       1        |
+     +-------------------+-----------------------+----------------+
+     |         34        |          39           |       1        |
+     +-------------------+-----------------------+----------------+
+     |         35        |          41           |       1        |
+     +-------------------+-----------------------+----------------+
+     |         36        |          43           |       2        |
+     +-------------------+-----------------------+----------------+
+     |         37        |          47           |       2        |
+     +-------------------+-----------------------+----------------+
+     |         38        |          51           |       3        |
+     +-------------------+-----------------------+----------------+
+     |         39        |          59           |       3        |
+     +-------------------+-----------------------+----------------+
+     |         40        |          67           |       4        |
+     +-------------------+-----------------------+----------------+
+     |         41        |          83           |       4        |
+     +-------------------+-----------------------+----------------+
+     |         42        |          99           |       5        |
+     +-------------------+-----------------------+----------------+
+     |         43        |         131           |       7        |
+     +-------------------+-----------------------+----------------+
+     |         44        |         259           |       8        |
+     +-------------------+-----------------------+----------------+
+     |         45        |         515           |       9        |
+     +-------------------+-----------------------+----------------+
+     |         46        |         1027          |       10       |
+     +-------------------+-----------------------+----------------+
+     |         47        |         2051          |       11       |
+     +-------------------+-----------------------+----------------+
+     |         48        |         4099          |       12       |
+     +-------------------+-----------------------+----------------+
+     |         49        |         8195          |       13       |
+     +-------------------+-----------------------+----------------+
+     |         50        |         16387         |       14       |
+     +-------------------+-----------------------+----------------+
+     |         51        |         32771         |       15       |
+     +-------------------+-----------------------+----------------+
+     |         52        |         65539         |       16       |
+     +-------------------+-----------------------+----------------+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 25]
+
+RFC 8478                    application/zstd                October 2018
+
+
+   Offset codes are values ranging from 0 to N.
+
+   A decoder is free to limit its maximum supported value for N.
+   Support for values of at least 22 is recommended.  At the time of
+   this writing, the reference decoder supports a maximum N value of 31.
+
+   An offset code is also the number of additional bits to read in
+   little-endian fashion and can be translated into an Offset_Value
+   using the following formulas:
+
+     Offset_Value = (1 << offsetCode) + readNBits(offsetCode);
+     if (Offset_Value > 3) Offset = Offset_Value - 3;
+
+   This means that maximum Offset_Value is (2^(N+1))-1, supporting back-
+   reference distance up to (2^(N+1))-4, but it is limited by the
+   maximum back-reference distance (see Section 3.1.1.1.2).
+
+   Offset_Value from 1 to 3 are special: they define "repeat codes".
+   This is described in more detail in Section 3.1.1.5.
+
+3.1.1.3.2.1.2.  Decoding Sequences
+
+   FSE bitstreams are read in reverse of the direction they are written.
+   In zstd, the compressor writes bits forward into a block, and the
+   decompressor must read the bitstream backwards.
+
+   To find the start of the bitstream, it is therefore necessary to know
+   the offset of the last byte of the block, which can be found by
+   counting Block_Size bytes after the block header.
+
+   After writing the last bit containing information, the compressor
+   writes a single 1 bit and then fills the byte with 0-7 zero bits of
+   padding.  The last byte of the compressed bitstream cannot be zero
+   for that reason.
+
+   When decompressing, the last byte containing the padding is the first
+   byte to read.  The decompressor needs to skip 0-7 initial zero bits
+   until the first 1 bit occurs.  Afterwards, the useful part of the
+   bitstream begins.
+
+   FSE decoding requires a 'state' to be carried from symbol to symbol.
+   For more explanation on FSE decoding, see Section 4.1.
+
+   For sequence decoding, a separate state keeps track of each literal
+   lengths, offsets, and match lengths symbols.  Some FSE primitives are
+   also used.  For more details on the operation of these primitives,
+   see Section 4.1.
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 26]
+
+RFC 8478                    application/zstd                October 2018
+
+
+   The bitstream starts with initial FSE state values, each using the
+   required number of bits in their respective accuracy, decoded
+   previously from their normalized distribution.  It starts with
+   Literals_Length_State, followed by Offset_State, and finally
+   Match_Length_State.
+
+   Note that all values are read backward, so the 'start' of the
+   bitstream is at the highest position in memory, immediately before
+   the last 1 bit for padding.
+
+   After decoding the starting states, a single sequence is decoded
+   Number_Of_Sequences times.  These sequences are decoded in order from
+   first to last.  Since the compressor writes the bitstream in the
+   forward direction, this means the compressor must encode the
+   sequences starting with the last one and ending with the first.
+
+   For each of the symbol types, the FSE state can be used to determine
+   the appropriate code.  The code then defines the Baseline and
+   Number_of_Bits to read for each type.  The description of the codes
+   for how to determine these values can be found in
+   Section 3.1.1.3.2.1.
+
+   Decoding starts by reading the Number_of_Bits required to decode
+   offset.  It does the same for Match_Length and then for
+   Literals_Length.  This sequence is then used for Sequence Execution
+   (see Section 3.1.1.4).
+
+   If it is not the last sequence in the block, the next operation is to
+   update states.  Using the rules pre-calculated in the decoding
+   tables, Literals_Length_State is updated, followed by
+   Match_Length_State, and then Offset_State.  See Section 4.1 for
+   details on how to update states from the bitstream.
+
+   This operation will be repeated Number_of_Sequences times.  At the
+   end, the bitstream shall be entirely consumed; otherwise, the
+   bitstream is considered corrupted.
+
+3.1.1.3.2.2.  Default Distributions
+
+   If Predefined_Mode is selected for a symbol type, its FSE decoding
+   table is generated from a predefined distribution table defined here.
+   For details on how to convert this distribution into a decoding
+   table, see Section 4.1.
+
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 27]
+
+RFC 8478                    application/zstd                October 2018
+
+
+3.1.1.3.2.2.1.  Literals Length
+
+   The decoding table uses an accuracy log of 6 bits (64 states).
+
+     short literalsLength_defaultDistribution[36] =
+       { 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
+         2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
+         -1,-1,-1,-1
+       };
+
+3.1.1.3.2.2.2.  Match Length
+
+   The decoding table uses an accuracy log of 6 bits (64 states).
+
+     short matchLengths_defaultDistribution[53] =
+       { 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
+         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,
+         -1,-1,-1,-1,-1
+       };
+
+3.1.1.3.2.2.3.  Offset Codes
+
+   The decoding table uses an accuracy log of 5 bits (32 states), and
+   supports a maximum N value of 28, allowing offset values up to
+   536,870,908.
+
+   If any sequence in the compressed block requires a larger offset than
+   this, it's not possible to use the default distribution to represent
+   it.
+
+     short offsetCodes_defaultDistribution[29] =
+       { 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
+         1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1
+       };
+
+3.1.1.4.  Sequence Execution
+
+   Once literals and sequences have been decoded, they are combined to
+   produce the decoded content of a block.
+
+   Each sequence consists of a tuple of (literals_length, offset_value,
+   match_length), decoded as described in the
+   Sequences_Section (Section 3.1.1.3.2).  To execute a sequence, first
+   copy literals_length bytes from the decoded literals to the output.
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 28]
+
+RFC 8478                    application/zstd                October 2018
+
+
+   Then, match_length bytes are copied from previous decoded data.  The
+   offset to copy from is determined by offset_value:
+
+   o  if Offset_Value > 3, then the offset is Offset_Value - 3;
+
+   o  if Offset_Value is from 1-3, the offset is a special repeat offset
+      value.  See Section 3.1.1.5 for how the offset is determined in
+      this case.
+
+   The offset is defined as from the current position (after copying the
+   literals), so an offset of 6 and a match length of 3 means that 3
+   bytes should be copied from 6 bytes back.  Note that all offsets
+   leading to previously decoded data must be smaller than Window_Size
+   defined in Frame_Header_Descriptor (Section 3.1.1.1.1).
+
+3.1.1.5.  Repeat Offsets
+
+   As seen above, the first three values define a repeated offset; we
+   will call them Repeated_Offset1, Repeated_Offset2, and
+   Repeated_Offset3.  They are sorted in recency order, with
+   Repeated_Offset1 meaning "most recent one".
+
+   If offset_value is 1, then the offset used is Repeated_Offset1, etc.
+
+   There is one exception: When the current sequence's literals_length
+   is 0, repeated offsets are shifted by 1, so an offset_value of 1
+   means Repeated_Offset2, an offset_value of 2 means Repeated_Offset3,
+   and an offset_value of 3 means Repeated_Offset1 - 1_byte.
+
+   For the first block, the starting offset history is populated with
+   the following values: Repeated_Offset1 (1), Repeated_Offset2 (4), and
+   Repeated_Offset3 (8), unless a dictionary is used, in which case they
+   come from the dictionary.
+
+   Then each block gets its starting offset history from the ending
+   values of the most recent Compressed_Block.  Note that blocks that
+   are not Compressed_Block are skipped; they do not contribute to
+   offset history.
+
+   The newest offset takes the lead in offset history, shifting others
+   back (up to its previous place if it was already present).  This
+   means that when Repeated_Offset1 (most recent) is used, history is
+   unmodified.  When Repeated_Offset2 is used, it is swapped with
+   Repeated_Offset1.  If any other offset is used, it becomes
+   Repeated_Offset1, and the rest are shifted back by 1.
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 29]
+
+RFC 8478                    application/zstd                October 2018
+
+
+3.1.2.  Skippable Frames
+
+     +--------------+------------+-----------+
+     | Magic_Number | Frame_Size | User_Data |
+     +--------------+------------+-----------+
+     |    4 bytes   |   4 bytes  |  n bytes  |
+     +--------------+------------+-----------+
+
+   Skippable frames allow the insertion of user-defined metadata into a
+   flow of concatenated frames.
+
+   Skippable frames defined in this specification are compatible with
+   skippable frames in [LZ4].
+
+   From a compliant decoder perspective, skippable frames simply need to
+   be skipped, and their content ignored, resuming decoding after the
+   skippable frame.
+
+   It should be noted that a skippable frame can be used to watermark a
+   stream of concatenated frames embedding any kind of tracking
+   information (even just a Universally Unique Identifier (UUID)).
+   Users wary of such possibility should scan the stream of concatenated
+   frames in an attempt to detect such frames for analysis or removal.
+
+   The fields are:
+
+   Magic_Number:  4 bytes, little-endian format.  Value: 0x184D2A5?,
+      which means any value from 0x184D2A50 to 0x184D2A5F.  All 16
+      values are valid to identify a skippable frame.  This
+      specification does not detail any specific tagging methods for
+      skippable frames.
+
+   Frame_Size:  This is the size, in bytes, of the following User_Data
+      (without including the magic number nor the size field itself).
+      This field is represented using 4 bytes, little-endian format,
+      unsigned 32 bits.  This means User_Data can't be bigger than
+      (2^32-1) bytes.
+
+   User_Data:  This field can be anything.  Data will just be skipped by
+      the decoder.
+
+4.  Entropy Encoding
+
+   Two types of entropy encoding are used by the Zstandard format: FSE
+   and Huffman coding.  Huffman is used to compress literals, while FSE
+   is used for all other symbols (Literals_Length_Code,
+   Match_Length_Code, and offset codes) and to compress Huffman headers.
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 30]
+
+RFC 8478                    application/zstd                October 2018
+
+
+4.1.  FSE
+
+   FSE, short for Finite State Entropy, is an entropy codec based on
+   [ANS].  FSE encoding/decoding involves a state that is carried over
+   between symbols, so decoding must be done in the opposite direction
+   as encoding.  Therefore, all FSE bitstreams are read from end to
+   beginning.  Note that the order of the bits in the stream is not
+   reversed; they are simply read in the reverse order from which they
+   were written.
+
+   For additional details on FSE, see Finite State Entropy [FSE].
+
+   FSE decoding involves a decoding table that has a power of 2 size and
+   contains three elements: Symbol, Num_Bits, and Baseline.  The base 2
+   logarithm of the table size is its Accuracy_Log.  An FSE state value
+   represents an index in this table.
+
+   To obtain the initial state value, consume Accuracy_Log bits from the
+   stream as a little-endian value.  The next symbol in the stream is
+   the Symbol indicated in the table for that state.  To obtain the next
+   state value, the decoder should consume Num_Bits bits from the stream
+   as a little-endian value and add it to Baseline.
+
+4.1.1.  FSE Table Description
+
+   To decode FSE streams, it is necessary to construct the decoding
+   table.  The Zstandard format encodes FSE table descriptions as
+   described here.
+
+   An FSE distribution table describes the probabilities of all symbols
+   from 0 to the last present one (included) on a normalized scale of
+   (1 << Accuracy_Log).  Note that there must be two or more symbols
+   with non-zero probability.
+
+   A bitstream is read forward, in little-endian fashion.  It is not
+   necessary to know its exact size, since the size will be discovered
+   and reported by the decoding process.  The bitstream starts by
+   reporting on which scale it operates.  If low4bits designates the
+   lowest 4 bits of the first byte, then Accuracy_Log = low4bits + 5.
+
+
+
+
+
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 31]
+
+RFC 8478                    application/zstd                October 2018
+
+
+   This is followed by each symbol value, from 0 to the last present
+   one.  The number of bits used by each field is variable and depends
+   on:
+
+   Remaining probabilities + 1:  For example, presuming an Accuracy_Log
+      of 8, and presuming 100 probabilities points have already been
+      distributed, the decoder may read any value from 0 to
+      (256 - 100 + 1) == 157, inclusive.  Therefore, it must read
+      log2sup(157) == 8 bits.
+
+   Value decoded:  Small values use 1 fewer bit.  For example, presuming
+      values from 0 to 157 (inclusive) are possible, 255 - 157 = 98
+      values are remaining in an 8-bit field.  The first 98 values
+      (hence from 0 to 97) use only 7 bits, and values from 98 to 157
+      use 8 bits.  This is achieved through this scheme:
+
+     +------------+---------------+-----------+
+     | Value Read | Value Decoded | Bits Used |
+     +------------+---------------+-----------+
+     |   0 - 97   |     0 - 97    |     7     |
+     +------------+---------------+-----------+
+     |  98 - 127  |    98 - 127   |     8     |
+     +------------+---------------+-----------+
+     | 128 - 225  |     0 - 97    |     7     |
+     +------------+---------------+-----------+
+     | 226 - 255  |   128 - 157   |     8     |
+     +------------+---------------+-----------+
+
+   Symbol probabilities are read one by one, in order.  The probability
+   is obtained from Value decoded using the formula P = Value - 1.  This
+   means the value 0 becomes the negative probability -1.  This is a
+   special probability that means "less than 1".  Its effect on the
+   distribution table is described below.  For the purpose of
+   calculating total allocated probability points, it counts as 1.
+
+   When a symbol has a probability of zero, it is followed by a 2-bit
+   repeat flag.  This repeat flag tells how many probabilities of zeroes
+   follow the current one.  It provides a number ranging from 0 to 3.
+   If it is a 3, another 2-bit repeat flag follows, and so on.
+
+   When the last symbol reaches a cumulated total of
+   (1 << Accuracy_Log), decoding is complete.  If the last symbol makes
+   the cumulated total go above (1 << Accuracy_Log), distribution is
+   considered corrupted.
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 32]
+
+RFC 8478                    application/zstd                October 2018
+
+
+   Finally, the decoder can tell how many bytes were used in this
+   process and how many symbols are present.  The bitstream consumes a
+   round number of bytes.  Any remaining bit within the last byte is
+   simply unused.
+
+   The distribution of normalized probabilities is enough to create a
+   unique decoding table.  The table has a size of (1 << Accuracy_Log).
+   Each cell describes the symbol decoded and instructions to get the
+   next state.
+
+   Symbols are scanned in their natural order for "less than 1"
+   probabilities as described above.  Symbols with this probability are
+   being attributed a single cell, starting from the end of the table
+   and retreating.  These symbols define a full state reset, reading
+   Accuracy_Log bits.
+
+   All remaining symbols are allocated in their natural order.  Starting
+   from symbol 0 and table position 0, each symbol gets allocated as
+   many cells as its probability.  Cell allocation is spread, not
+   linear; each successor position follows this rule:
+
+     position += (tableSize >> 1) + (tableSize >> 3) + 3;
+     position &= tableSize - 1;
+
+   A position is skipped if it is already occupied by a "less than 1"
+   probability symbol.  Position does not reset between symbols; it
+   simply iterates through each position in the table, switching to the
+   next symbol when enough states have been allocated to the current
+   one.
+
+   The result is a list of state values.  Each state will decode the
+   current symbol.
+
+   To get the Number_of_Bits and Baseline required for the next state,
+   it is first necessary to sort all states in their natural order.  The
+   lower states will need 1 more bit than higher ones.  The process is
+   repeated for each symbol.
+
+   For example, presuming a symbol has a probability of 5, it receives
+   five state values.  States are sorted in natural order.  The next
+   power of 2 is 8.  The space of probabilities is divided into 8 equal
+   parts.  Presuming the Accuracy_Log is 7, this defines 128 states, and
+   each share (divided by 8) is 16 in size.  In order to reach 8, 8 - 5
+   = 3 lowest states will count "double", doubling the number of shares
+   (32 in width), requiring 1 more bit in the process.
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 33]
+
+RFC 8478                    application/zstd                October 2018
+
+
+   Baseline is assigned starting from the higher states using fewer
+   bits, and proceeding naturally, then resuming at the first state,
+   each taking its allocated width from Baseline.
+
+     +----------------+-------+-------+--------+------+-------+
+     |   state order  |   0   |   1   |   2    |  3   |  4    |
+     +----------------+-------+-------+--------+------+-------+
+     |     width      |   32  |   32  |   32   |  16  |  16   |
+     +----------------+-------+-------+--------+------+-------+
+     | Number_of_Bits |   5   |   5   |   5    |  4   |  4    |
+     +----------------+-------+-------+--------+------+-------+
+     |  range number  |   2   |   4   |   6    |  0   |  1    |
+     +----------------+-------+-------+--------+------+-------+
+     |    Baseline    |   32  |   64  |   96   |  0   |  16   |
+     +----------------+-------+-------+--------+------+-------+
+     |     range      | 32-63 | 64-95 | 96-127 | 0-15 | 16-31 |
+     +----------------+-------+-------+--------+------+-------+
+
+   The next state is determined from the current state by reading the
+   required Number_of_Bits and adding the specified Baseline.
+
+   See Appendix A for the results of this process that are applied to
+   the default distributions.
+
+4.2.  Huffman Coding
+
+   Zstandard Huffman-coded streams are read backwards, similar to the
+   FSE bitstreams.  Therefore, to find the start of the bitstream, it is
+   necessary to know the offset of the last byte of the Huffman-coded
+   stream.
+
+   After writing the last bit containing information, the compressor
+   writes a single 1 bit and then fills the byte with 0-7 0 bits of
+   padding.  The last byte of the compressed bitstream cannot be 0 for
+   that reason.
+
+   When decompressing, the last byte containing the padding is the first
+   byte to read.  The decompressor needs to skip 0-7 initial 0 bits and
+   the first 1 bit that occurs.  Afterwards, the useful part of the
+   bitstream begins.
+
+   The bitstream contains Huffman-coded symbols in little-endian order,
+   with the codes defined by the method below.
+
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 34]
+
+RFC 8478                    application/zstd                October 2018
+
+
+4.2.1.  Huffman Tree Description
+
+   Prefix coding represents symbols from an a priori known alphabet by
+   bit sequences (codewords), one codeword for each symbol, in a manner
+   such that different symbols may be represented by bit sequences of
+   different lengths, but a parser can always parse an encoded string
+   unambiguously symbol by symbol.
+
+   Given an alphabet with known symbol frequencies, the Huffman
+   algorithm allows the construction of an optimal prefix code using the
+   fewest bits of any possible prefix codes for that alphabet.
+
+   The prefix code must not exceed a maximum code length.  More bits
+   improve accuracy but yield a larger header size and require more
+   memory or more complex decoding operations.  This specification
+   limits the maximum code length to 11 bits.
+
+   All literal values from zero (included) to the last present one
+   (excluded) are represented by Weight with values from 0 to
+   Max_Number_of_Bits.  Transformation from Weight to Number_of_Bits
+   follows this pseudocode:
+
+     if Weight == 0
+       Number_of_Bits = 0
+     else
+       Number_of_Bits = Max_Number_of_Bits + 1 - Weight
+
+   The last symbol's Weight is deduced from previously decoded ones, by
+   completing to the nearest power of 2.  This power of 2 gives
+   Max_Number_of_Bits the depth of the current tree.
+
+   For example, presume the following Huffman tree must be described:
+
+     +---------------+----------------+
+     | Literal Value | Number_of_Bits |
+     +---------------+----------------+
+     |       0       |        1       |
+     +---------------+----------------+
+     |       1       |        2       |
+     +---------------+----------------+
+     |       2       |        3       |
+     +---------------+----------------+
+     |       3       |        0       |
+     +---------------+----------------+
+     |       4       |        4       |
+     +---------------+----------------+
+     |       5       |        4       |
+     +---------------+----------------+
+
+
+
+Collet & Kucherawy            Informational                    [Page 35]
+
+RFC 8478                    application/zstd                October 2018
+
+
+   The tree depth is 4, since its longest element uses 4 bits.  (The
+   longest elements are those with the smallest frequencies.)  Value 5
+   will not be listed as it can be determined from the values for 0-4,
+   nor will values above 5 as they are all 0.  Values from 0 to 4 will
+   be listed using Weight instead of Number_of_Bits.  The pseudocode to
+   determine Weight is:
+
+     if Number_of_Bits == 0
+       Weight = 0
+     else
+       Weight = Max_Number_of_Bits + 1 - Number_of_Bits
+
+   It gives the following series of weights:
+
+     +---------------+--------+
+     | Literal Value | Weight |
+     +---------------+--------+
+     |       0       |   4    |
+     +---------------+--------+
+     |       1       |   3    |
+     +---------------+--------+
+     |       2       |   2    |
+     +---------------+--------+
+     |       3       |   0    |
+     +---------------+--------+
+     |       4       |   1    |
+     +---------------+--------+
+
+   The decoder will do the inverse operation: having collected weights
+   of literals from 0 to 4, it knows the last literal, 5, is present
+   with a non-zero Weight.  The Weight of 5 can be determined by
+   advancing to the next power of 2.  The sum of 2^(Weight-1) (excluding
+   0's) is 15.  The nearest power of 2 is 16.  Therefore,
+   Max_Number_of_Bits = 4 and Weight[5] = 16 - 15 = 1.
+
+4.2.1.1.  Huffman Tree Header
+
+   This is a single byte value (0-255), which describes how the series
+   of weights is encoded.
+
+   headerByte < 128:  The series of weights is compressed using FSE (see
+      below).  The length of the FSE-compressed series is equal to
+      headerByte (0-127).
+
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 36]
+
+RFC 8478                    application/zstd                October 2018
+
+
+   headerByte >= 128:  This is a direct representation, where each
+      Weight is written directly as a 4-bit field (0-15).  They are
+      encoded forward, 2 weights to a byte with the first weight taking
+      the top 4 bits and the second taking the bottom 4; for example,
+      the following operations could be used to read the weights:
+
+     Weight[0] = (Byte[0] >> 4)
+     Weight[1] = (Byte[0] & 0xf),
+     etc.
+
+      The full representation occupies ceiling(Number_of_Symbols/2)
+      bytes, meaning it uses only full bytes even if Number_of_Symbols
+      is odd.  Number_of_Symbols = headerByte - 127.  Note that maximum
+      Number_of_Symbols is 255 - 127 = 128.  If any literal has a value
+      over 128, raw header mode is not possible, and it is necessary to
+      use FSE compression.
+
+4.2.1.2.  FSE Compression of Huffman Weights
+
+   In this case, the series of Huffman weights is compressed using FSE
+   compression.  It is a single bitstream with two interleaved states,
+   sharing a single distribution table.
+
+   To decode an FSE bitstream, it is necessary to know its compressed
+   size.  Compressed size is provided by headerByte.  It's also
+   necessary to know its maximum possible decompressed size, which is
+   255, since literal values span from 0 to 255, and the last symbol's
+   Weight is not represented.
+
+   An FSE bitstream starts by a header, describing probabilities
+   distribution.  It will create a decoding table.  For a list of
+   Huffman weights, the maximum accuracy log is 6 bits.  For more
+   details, see Section 4.1.1.
+
+   The Huffman header compression uses two states, which share the same
+   FSE distribution table.  The first state (State1) encodes the even-
+   numbered index symbols, and the second (State2) encodes the odd-
+   numbered index symbols.  State1 is initialized first, and then
+   State2, and they take turns decoding a single symbol and updating
+   their state.  For more details on these FSE operations, see
+   Section 4.1.
+
+   The number of symbols to be decoded is determined by tracking the
+   bitStream overflow condition: If updating state after decoding a
+   symbol would require more bits than remain in the stream, it is
+   assumed that extra bits are zero.  Then, symbols for each of the
+   final states are decoded and the process is complete.
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 37]
+
+RFC 8478                    application/zstd                October 2018
+
+
+4.2.1.3.  Conversion from Weights to Huffman Prefix Codes
+
+   All present symbols will now have a Weight value.  It is possible to
+   transform weights into Number_of_Bits, using this formula:
+
+     if Weight > 0
+         Number_of_Bits = Max_Number_of_Bits + 1 - Weight
+     else
+         Number_of_Bits = 0
+
+   Symbols are sorted by Weight.  Within the same Weight, symbols keep
+   natural sequential order.  Symbols with a Weight of zero are removed.
+   Then, starting from the lowest Weight, prefix codes are distributed
+   in sequential order.
+
+   For example, assume the following list of weights has been decoded:
+
+     +---------+--------+
+     | Literal | Weight |
+     +---------+--------+
+     |    0    |   4    |
+     +---------+--------+
+     |    1    |   3    |
+     +---------+--------+
+     |    2    |   2    |
+     +---------+--------+
+     |    3    |   0    |
+     +---------+--------+
+     |    4    |   1    |
+     +---------+--------+
+     |    5    |   1    |
+     +---------+--------+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 38]
+
+RFC 8478                    application/zstd                October 2018
+
+
+   Sorting by weight and then the natural sequential order yields the
+   following distribution:
+
+     +---------+--------+----------------+--------------+
+     | Literal | Weight | Number_Of_Bits | Prefix Codes |
+     +---------+--------+----------------|--------------+
+     |    3    |   0    |        0       |      N/A     |
+     +---------+--------+----------------|--------------+
+     |    4    |   1    |        4       |     0000     |
+     +---------+--------+----------------|--------------+
+     |    5    |   1    |        4       |     0001     |
+     +---------+--------+----------------|--------------+
+     |    2    |   2    |        3       |      001     |
+     +---------+--------+----------------|--------------+
+     |    1    |   3    |        2       |       01     |
+     +---------+--------+----------------|--------------+
+     |    0    |   4    |        1       |        1     |
+     +---------+--------+----------------|--------------+
+
+4.2.2.  Huffman-Coded Streams
+
+   Given a Huffman decoding table, it is possible to decode a Huffman-
+   coded stream.
+
+   Each bitstream must be read backward, which starts from the end and
+   goes up to the beginning.  Therefore, it is necessary to know the
+   size of each bitstream.
+
+   It is also necessary to know exactly which bit is the last.  This is
+   detected by a final bit flag: the highest bit of the last byte is a
+   final-bit-flag.  Consequently, a last byte of 0 is not possible.  And
+   the final-bit-flag itself is not part of the useful bitstream.
+   Hence, the last byte contains between 0 and 7 useful bits.
+
+   Starting from the end, it is possible to read the bitstream in a
+   little-endian fashion, keeping track of already used bits.  Since the
+   bitstream is encoded in reverse order, starting from the end, read
+   symbols in forward order.
+
+
+
+
+
+
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 39]
+
+RFC 8478                    application/zstd                October 2018
+
+
+   For example, if the literal sequence "0145" was encoded using the
+   above prefix code, it would be encoded (in reverse order) as:
+
+     +---------+----------+
+     | Symbol  | Encoding |
+     +---------+----------+
+     |    5    |   0000   |
+     +---------+----------+
+     |    4    |   0001   |
+     +---------+----------+
+     |    1    |    01    |
+     +---------+----------+
+     |    0    |    1     |
+     +---------+----------+
+     | Padding |   00001  |
+     +---------+----------+
+
+   This results in the following 2-byte bitstream:
+
+     00010000 00001101
+
+   Here is an alternative representation with the symbol codes separated
+   by underscores:
+
+     0001_0000 00001_1_01
+
+   Reading the highest Max_Number_of_Bits bits, it's possible to compare
+   the extracted value to the decoding table, determining the symbol to
+   decode and number of bits to discard.
+
+   The process continues reading up to the required number of symbols
+   per stream.  If a bitstream is not entirely and exactly consumed,
+   hence reaching exactly its beginning position with all bits consumed,
+   the decoding process is considered faulty.
+
+5.  Dictionary Format
+
+   Zstandard is compatible with "raw content" dictionaries, free of any
+   format restriction, except that they must be at least 8 bytes.  These
+   dictionaries function as if they were just the content part of a
+   formatted dictionary.
+
+   However, dictionaries created by "zstd --train" in the reference
+   implementation follow a specific format, described here.
+
+   Dictionaries are not included in the compressed content but rather
+   are provided out of band.  That is, the Dictionary_ID identifies
+   which should be used, but this specification does not describe the
+
+
+
+Collet & Kucherawy            Informational                    [Page 40]
+
+RFC 8478                    application/zstd                October 2018
+
+
+   mechanism by which the dictionary is obtained prior to use during
+   compression or decompression.
+
+   A dictionary has a size, defined either by a buffer limit or a file
+   size.  The general format is:
+
+     +--------------+---------------+----------------+---------+
+     | Magic_Number | Dictionary_ID | Entropy_Tables | Content |
+     +--------------+---------------+----------------+---------+
+
+   Magic_Number:  4 bytes ID, value 0xEC30A437, little-endian format.
+
+   Dictionary_ID:  4 bytes, stored in little-endian format.
+      Dictionary_ID can be any value, except 0 (which means no
+      Dictionary_ID).  It is used by decoders to check if they use the
+      correct dictionary.  If the frame is going to be distributed in a
+      private environment, any Dictionary_ID can be used.  However, for
+      public distribution of compressed frames, the following ranges are
+      reserved and shall not be used:
+
+         low range: <= 32767
+         high range: >= (2^31)
+
+   Entropy_Tables:  Follow the same format as the tables in compressed
+      blocks.  See the relevant FSE and Huffman sections for how to
+      decode these tables.  They are stored in the following order:
+      Huffman table for literals, FSE table for offsets, FSE table for
+      match lengths, and FSE table for literals lengths.  These tables
+      populate the Repeat Stats literals mode and Repeat distribution
+      mode for sequence decoding.  It is finally followed by 3 offset
+      values, populating repeat offsets (instead of using {1,4,8}),
+      stored in order, 4-bytes little-endian each, for a total of 12
+      bytes.  Each repeat offset must have a value less than the
+      dictionary size.
+
+   Content:  The rest of the dictionary is its content.  The content
+      acts as a "past" in front of data to be compressed or
+      decompressed, so it can be referenced in sequence commands.  As
+      long as the amount of data decoded from this frame is less than or
+      equal to Window_Size, sequence commands may specify offsets longer
+      than the total length of decoded output so far to reference back
+      to the dictionary, even parts of the dictionary with offsets
+      larger than Window_Size.  After the total output has surpassed
+      Window_Size, however, this is no longer allowed, and the
+      dictionary is no longer accessible.
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 41]
+
+RFC 8478                    application/zstd                October 2018
+
+
+6.  IANA Considerations
+
+   IANA has made two registrations, as described below.
+
+6.1.  The 'application/zstd' Media Type
+
+   The 'application/zstd' media type identifies a block of data that is
+   compressed using zstd compression.  The data is a stream of bytes as
+   described in this document.  IANA has added the following to the
+   "Media Types" registry:
+
+   Type name:  application
+
+   Subtype name:  zstd
+
+   Required parameters:  N/A
+
+   Optional parameters:  N/A
+
+   Encoding considerations:  binary
+
+   Security considerations:  See Section 7 of RFC 8478
+
+   Interoperability considerations:  N/A
+
+   Published specification:  RFC 8478
+
+   Applications that use this media type:  anywhere data size is an
+      issue
+
+   Additional information:
+
+      Magic number(s):  4 bytes, little-endian format.
+         Value: 0xFD2FB528
+
+      File extension(s):  zst
+
+      Macintosh file type code(s):  N/A
+
+   For further information:  See [ZSTD]
+
+   Intended usage:  common
+
+   Restrictions on usage:  N/A
+
+   Author:  Murray S.  Kucherawy
+
+   Change Controller:  IETF
+
+
+
+Collet & Kucherawy            Informational                    [Page 42]
+
+RFC 8478                    application/zstd                October 2018
+
+
+   Provisional registration:  no
+
+6.2.  Content Encoding
+
+   IANA has added the following entry to the "HTTP Content Coding
+   Registry" within the "Hypertext Transfer Protocol (HTTP) Parameters"
+   registry:
+
+   Name:  zstd
+
+   Description:  A stream of bytes compressed using the Zstandard
+      protocol
+
+   Pointer to specification text:  RFC 8478
+
+6.3.  Dictionaries
+
+   Work in progress includes development of dictionaries that will
+   optimize compression and decompression of particular types of data.
+   Specification of such dictionaries for public use will necessitate
+   registration of a code point from the reserved range described in
+   Section 3.1.1.1.3 and its association with a specific dictionary.
+
+   However, there are at present no such dictionaries published for
+   public use, so this document makes no immediate request of IANA to
+   create such a registry.
+
+7.  Security Considerations
+
+   Any data compression method involves the reduction of redundancy in
+   the data.  Zstandard is no exception, and the usual precautions
+   apply.
+
+   One should never compress a message whose content must remain secret
+   with a message generated by a third party.  Such a compression can be
+   used to guess the content of the secret message through analysis of
+   entropy reduction.  This was demonstrated in the Compression Ratio
+   Info-leak Made Easy (CRIME) attack [CRIME], for example.
+
+   A decoder has to demonstrate capabilities to detect and prevent any
+   kind of data tampering in the compressed frame from triggering system
+   faults, such as reading or writing beyond allowed memory ranges.
+   This can be guaranteed by either the implementation language or
+   careful bound checkings.  Of particular note is the encoding of
+   Number_of_Sequences values that cause the decoder to read into the
+   block header (and beyond), as well as the indication of a
+   Frame_Content_Size that is smaller than the actual decompressed data,
+   in an attempt to trigger a buffer overflow.  It is highly recommended
+
+
+
+Collet & Kucherawy            Informational                    [Page 43]
+
+RFC 8478                    application/zstd                October 2018
+
+
+   to fuzz-test (i.e., provide invalid, unexpected, or random input and
+   verify safe operation of) decoder implementations to test and harden
+   their capability to detect bad frames and deal with them without any
+   adverse system side effect.
+
+   An attacker may provide correctly formed compressed frames with
+   unreasonable memory requirements.  A decoder must always control
+   memory requirements and enforce some (system-specific) limits in
+   order to protect memory usage from such scenarios.
+
+   Compression can be optimized by training a dictionary on a variety of
+   related content payloads.  This dictionary must then be available at
+   the decoder for decompression of the payload to be possible.  While
+   this document does not specify how to acquire a dictionary for a
+   given compressed payload, it is worth noting that third-party
+   dictionaries may interact unexpectedly with a decoder, leading to
+   possible memory or other resource exhaustion attacks.  We expect such
+   topics to be discussed in further detail in the Security
+   Considerations section of a forthcoming RFC for dictionary
+   acquisition and transmission, but highlight this issue now out of an
+   abundance of caution.
+
+   As discussed in Section 3.1.2, it is possible to store arbitrary user
+   metadata in skippable frames.  While such frames are ignored during
+   decompression of the data, they can be used as a watermark to track
+   the path of the compressed payload.
+
+8.  Implementation Status
+
+   Source code for a C language implementation of a Zstandard-compliant
+   library is available at [ZSTD-GITHUB].  This implementation is
+   considered to be the reference implementation and is production
+   ready; it implements the full range of the specification.  It is
+   routinely tested against security hazards and widely deployed within
+   Facebook infrastructure.
+
+   The reference version is optimized for speed and is highly portable.
+   It has been proven to run safely on multiple architectures (e.g.,
+   x86, x64, ARM, MIPS, PowerPC, IA64) featuring 32- or 64-bit
+   addressing schemes, a little- or big-endian storage scheme, a number
+   of different operating systems (e.g., UNIX (including Linux, BSD,
+   OS-X, and Solaris) and Windows), and a number of compilers (e.g.,
+   gcc, clang, visual, and icc).
+
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 44]
+
+RFC 8478                    application/zstd                October 2018
+
+
+9.  References
+
+9.1.  Normative References
+
+   [ZSTD]     "Zstandard", <http://www.zstd.net>.
+
+9.2.  Informative References
+
+   [ANS]      Duda, J., "Asymmetric numeral systems: entropy coding
+              combining speed of Huffman coding with compression rate of
+              arithmetic coding", January 2014,
+              <https://arxiv.org/pdf/1311.2540>.
+
+   [CRIME]    "CRIME", June 2018, <https://en.wikipedia.org/w/
+              index.php?title=CRIME&oldid=844538656>.
+
+   [FSE]      "FiniteStateEntropy", commit 6efa78a, June 2018,
+              <https://github.com/Cyan4973/FiniteStateEntropy/>.
+
+   [LZ4]      "LZ4 Frame Format Description", commit d03224b, January
+              2018, <https://github.com/lz4/lz4/blob/master/doc/
+              lz4_Frame_format.md>.
+
+   [RFC1952]  Deutsch, P., "GZIP file format specification version 4.3",
+              RFC 1952, DOI 10.17487/RFC1952, May 1996,
+              <https://www.rfc-editor.org/info/rfc1952>.
+
+   [XXHASH]   "XXHASH Algorithm", <http://www.xxhash.org>.
+
+   [ZSTD-GITHUB]
+              "zstd", commit 8514bd8, August 2018,
+              <https://github.com/facebook/zstd>.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 45]
+
+RFC 8478                    application/zstd                October 2018
+
+
+Appendix A.  Decoding Tables for Predefined Codes
+
+   This appendix contains FSE decoding tables for the predefined literal
+   length, match length, and offset codes.  The tables have been
+   constructed using the algorithm as given above in Section 4.1.1.  The
+   tables here can be used as examples to crosscheck that an
+   implementation has built its decoding tables correctly.
+
+A.1.  Literal Length Code Table
+
+     +-------+--------+----------------+------+
+     | State | Symbol | Number_Of_Bits | Base |
+     +-------+--------+----------------+------+
+     |    0  |    0   |        0       |   0  |
+     +-------+--------+----------------+------+
+     |    0  |    0   |        4       |   0  |
+     +-------+--------+----------------+------+
+     |    1  |    0   |        4       |  16  |
+     +-------+--------+----------------+------+
+     |    2  |    1   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |    3  |    3   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |    4  |    4   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |    5  |    6   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |    6  |    7   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |    7  |    9   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |    8  |   10   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |    9  |   12   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   10  |   14   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   11  |   16   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   12  |   18   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   13  |   19   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   14  |   21   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   15  |   22   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   16  |   24   |        5       |   0  |
+
+
+
+Collet & Kucherawy            Informational                    [Page 46]
+
+RFC 8478                    application/zstd                October 2018
+
+
+     +-------+--------+----------------+------+
+     |   17  |   25   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   18  |   26   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   19  |   27   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   20  |   29   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   21  |   31   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   22  |    0   |        4       |  32  |
+     +-------+--------+----------------+------+
+     |   23  |    1   |        4       |   0  |
+     +-------+--------+----------------+------+
+     |   24  |    2   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   25  |    4   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   26  |    5   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   27  |    7   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   28  |    8   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   29  |   10   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   30  |   11   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   31  |   13   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   32  |   16   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   33  |   17   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   34  |   19   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   35  |   20   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   36  |   22   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   37  |   23   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   38  |   25   |        4       |   0  |
+     +-------+--------+----------------+------+
+     |   39  |   25   |        4       |  16  |
+     +-------+--------+----------------+------+
+     |   40  |   26   |        5       |  32  |
+
+
+
+Collet & Kucherawy            Informational                    [Page 47]
+
+RFC 8478                    application/zstd                October 2018
+
+
+     +-------+--------+----------------+------+
+     |   41  |   28   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   42  |   30   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   43  |    0   |        4       |  48  |
+     +-------+--------+----------------+------+
+     |   44  |    1   |        4       |  16  |
+     +-------+--------+----------------+------+
+     |   45  |    2   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   46  |    3   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   47  |    5   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   48  |    6   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   49  |    8   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   50  |    9   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   51  |   11   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   52  |   12   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   53  |   15   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   54  |   17   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   55  |   18   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   56  |   20   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   57  |   21   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   58  |   23   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   59  |   24   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   60  |   35   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   61  |   34   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   62  |   33   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   63  |   32   |        6       |   0  |
+     +-------+--------+----------------+------+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 48]
+
+RFC 8478                    application/zstd                October 2018
+
+
+A.2.  Match Length Code Table
+
+     +-------+--------+----------------+------+
+     | State | Symbol | Number_Of_Bits | Base |
+     +-------+--------+----------------+------+
+     |    0  |    0   |        0       |   0  |
+     +-------+--------+----------------+------+
+     |    0  |    0   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |    1  |    1   |        4       |   0  |
+     +-------+--------+----------------+------+
+     |    2  |    2   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |    3  |    3   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |    4  |    5   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |    5  |    6   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |    6  |    8   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |    7  |   10   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |    8  |   13   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |    9  |   16   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   10  |   19   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   11  |   22   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   12  |   25   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   13  |   28   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   14  |   31   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   15  |   33   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   16  |   35   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   17  |   37   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   18  |   39   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   19  |   41   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   20  |   43   |        6       |   0  |
+
+
+
+Collet & Kucherawy            Informational                    [Page 49]
+
+RFC 8478                    application/zstd                October 2018
+
+
+     +-------+--------+----------------+------+
+     |   21  |   45   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   22  |    1   |        4       |  16  |
+     +-------+--------+----------------+------+
+     |   23  |    2   |        4       |   0  |
+     +-------+--------+----------------+------+
+     |   24  |    3   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   25  |    4   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   26  |    6   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   27  |    7   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   28  |    9   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   29  |   12   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   30  |   15   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   31  |   18   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   32  |   21   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   33  |   24   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   34  |   27   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   35  |   30   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   36  |   32   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   37  |   34   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   38  |   36   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   39  |   38   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   40  |   40   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   41  |   42   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   42  |   44   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   43  |    1   |        4       |  32  |
+     +-------+--------+----------------+------+
+     |   44  |    1   |        4       |  48  |
+
+
+
+Collet & Kucherawy            Informational                    [Page 50]
+
+RFC 8478                    application/zstd                October 2018
+
+
+     +-------+--------+----------------+------+
+     |   45  |    2   |        4       |  16  |
+     +-------+--------+----------------+------+
+     |   46  |    4   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   47  |    5   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   48  |    7   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   49  |    8   |        5       |  32  |
+     +-------+--------+----------------+------+
+     |   50  |   11   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   51  |   14   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   52  |   17   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   53  |   20   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   54  |   23   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   55  |   26   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   56  |   29   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   57  |   52   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   58  |   51   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   59  |   50   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   60  |   49   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   61  |   48   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   62  |   47   |        6       |   0  |
+     +-------+--------+----------------+------+
+     |   63  |   46   |        6       |   0  |
+     +-------+--------+----------------+------+
+
+
+
+
+
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 51]
+
+RFC 8478                    application/zstd                October 2018
+
+
+A.3.  Offset Code Table
+
+     +-------+--------+----------------+------+
+     | State | Symbol | Number_Of_Bits | Base |
+     +-------+--------+----------------+------+
+     |    0  |    0   |        0       |   0  |
+     +-------+--------+----------------+------+
+     |    0  |    0   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |    1  |    6   |        4       |   0  |
+     +-------+--------+----------------+------+
+     |    2  |    9   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |    3  |   15   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |    4  |   21   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |    5  |    3   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |    6  |    7   |        4       |   0  |
+     +-------+--------+----------------+------+
+     |    7  |   12   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |    8  |   18   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |    9  |   23   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   10  |    5   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   11  |    8   |        4       |   0  |
+     +-------+--------+----------------+------+
+     |   12  |   14   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   13  |   20   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   14  |    2   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   15  |    7   |        4       |  16  |
+     +-------+--------+----------------+------+
+     |   16  |   11   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   17  |   17   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   18  |   22   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   19  |    4   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   20  |    8   |        4       |  16  |
+
+
+
+Collet & Kucherawy            Informational                    [Page 52]
+
+RFC 8478                    application/zstd                October 2018
+
+
+     +-------+--------+----------------+------+
+     |   21  |   13   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   22  |   19   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   23  |    1   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   24  |    6   |        4       |  16  |
+     +-------+--------+----------------+------+
+     |   25  |   10   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   26  |   16   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   27  |   28   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   28  |   27   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   29  |   26   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   30  |   25   |        5       |   0  |
+     +-------+--------+----------------+------+
+     |   31  |   24   |        5       |   0  |
+     +-------+--------+----------------+------+
+
+Acknowledgments
+
+   zstd was developed by Yann Collet.
+
+   Bobo Bose-Kolanu, Felix Handte, Kyle Nekritz, Nick Terrell, and David
+   Schleimer provided helpful feedback during the development of this
+   document.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 53]
+
+RFC 8478                    application/zstd                October 2018
+
+
+Authors' Addresses
+
+   Yann Collet
+   Facebook
+   1 Hacker Way
+   Menlo Park, CA  94025
+   United States of America
+
+   Email: cyan@fb.com
+
+
+   Murray S. Kucherawy (editor)
+   Facebook
+   1 Hacker Way
+   Menlo Park, CA  94025
+   United States of America
+
+   Email: msk@fb.com
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Collet & Kucherawy            Informational                    [Page 54]
+