[要約] RFC 8878は、Zstandard圧縮アルゴリズムとapplication/zstdメディアタイプの標準化を目的としています。このRFCは、Zstandard圧縮形式を使用するための標準化された方法を提供し、データの効率的な圧縮と伝送を可能にします。

Internet Engineering Task Force (IETF)                         Y. Collet
Request for Comments: 8878                             M. Kucherawy, Ed.
Obsoletes: 8478                                                 Facebook
Category: Informational                                    February 2021
ISSN: 2070-1721
        

Zstandard Compression and the 'application/zstd' Media Type

zStandard圧縮と「アプリケーション/ ZSTD」メディアタイプ

Abstract

概要

Zstandard, or "zstd" (pronounced "zee standard"), is a lossless data compression mechanism. This document describes the mechanism and registers a media type, content encoding, and a structured syntax suffix to be used when transporting zstd-compressed content via MIME.

zStandard、または "zstd"( "zee標準")は、ロスレスデータ圧縮メカニズムです。この文書はメカニズムを説明し、メディアタイプ、コンテンツエンコーディング、およびMIMEを介してzstd-compressedコンテンツを転送するときに使用される構造化シンタックスサフィックスを記述します。

Despite use of the word "standard" as part of Zstandard, readers are advised that this document is not an Internet Standards Track specification; it is being published for informational purposes only.

ZSTANDARDの一部として「標準」という単語を使用しても、この文書はインターネット標準のトラック仕様ではないことを読者にお勧めします。それは情報提供のためだけに公開されています。

This document replaces and obsoletes RFC 8478.

この文書はRFC 8478に代わって廃止されます。

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.

この文書は、インターネットエンジニアリングタスクフォース(IETF)の製品です。IETFコミュニティのコンセンサスを表します。それは公開レビューを受け、インターネットエンジニアリングステアリンググループ(IESG)による出版の承認を受けました。IESGによって承認されたすべての文書がすべてのレベルのインターネット規格の候補者ではありません。RFC 7841のセクション2を参照してください。

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/rfc8878.

この文書の現在のステータス、任意のエラータ、およびフィードバックを提供する方法は、https://www.rfc-editor.org/info/rfc8878で入手できます。

Copyright Notice

著作権表示

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

著作権(C)2021 IETF信頼と文書著者として識別された人。全著作権所有。

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.

この文書は、この文書の公開日に有効なIETF文書(https://truste.ietf.org/License-info)に関するBCP 78とIETF信頼の法的規定を受けています。この文書に関してあなたの権利と制限を説明するので、これらの文書を慎重に見直してください。この文書から抽出されたコードコンポーネントには、信頼法の法的規定のセクション4。

Table of Contents

目次

   1.  Introduction
   2.  Definitions
   3.  Compression Algorithm
     3.1.  Frames
       3.1.1.  Zstandard Frames
         3.1.1.1.  Frame Header
         3.1.1.2.  Blocks
         3.1.1.3.  Compressed Blocks
         3.1.1.4.  Sequence Execution
         3.1.1.5.  Repeat Offsets
       3.1.2.  Skippable Frames
   4.  Entropy Encoding
     4.1.  FSE
       4.1.1.  FSE Table Description
     4.2.  Huffman Coding
       4.2.1.  Huffman Tree Description
         4.2.1.1.  Huffman Tree Header
         4.2.1.2.  FSE Compression of Huffman Weights
         4.2.1.3.  Conversion from Weights to Huffman Prefix Codes
       4.2.2.  Huffman-Coded Streams
   5.  Dictionary Format
   6.  Use of Dictionaries
   7.  IANA Considerations
     7.1.  The 'application/zstd' Media Type
     7.2.  Content Encoding
     7.3.  Structured Syntax Suffix
     7.4.  Dictionaries
   8.  Security Considerations
   9.  References
     9.1.  Normative References
     9.2.  Informative References
   Appendix A.  Decoding Tables for Predefined Codes
     A.1.  Literals Length Code Table
     A.2.  Match Length Code Table
     A.3.  Offset Code Table
   Appendix B.  Changes since RFC 8478
   Acknowledgments
   Authors' Addresses
        
1. Introduction
1. はじめに

Zstandard, or "zstd" (pronounced "zee standard"), is a data compression mechanism, akin to gzip [RFC1952].

zStandard、または "zstd"( "zee標準")は、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, content encoding, and structured syntax suffix that can be used to identify such content when it is used in a payload.

このドキュメントではzStandardフォーマットについて説明します。また、zStandardで圧縮されたデータオブジェクトのトランスポートを可能にするために、この文書は、ペイロードで使用されたときにそのようなコンテンツを識別するために使用できるメディアタイプ、コンテンツエンコード、および構造化シンタックスサフィックスを登録します。

2. Definitions
2. 定義

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.

非圧縮:圧縮が受ける前に、元の形式で任意のバイトのセットを記述します。

compressed: Describes the result of passing a set of bytes through this mechanism. The original input has thus been compressed.

圧縮:このメカニズムを通して一連のバイトを渡す結果を記述します。元の入力は圧縮されました。

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.

デコード: "エンコード"の逆です。元のコンテンツを回復するために事前のエンコーディングを逆にするプロセスを説明します。

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.

フレーム:zStandardで圧縮されたコンテンツはzStandardフレームに変換されます。複数のフレームを単一のファイルまたはストリームに追加できます。フレームは完全に独立しており、定義された開始と終了を持ち、デコーダにそれを解凍する方法を伝える一連のパラメータを持っています。

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.

ブロック:フレームは1つまたは複数のブロックをカプセル化します。各ブロックは任意のコンテンツを含み、これはそのヘッダによって記述され、フレームパラメータに依存する保証された最大コンテンツサイズを有する。フレームとは異なり、各ブロックは適切な復号化のための前のブロックに依存します。ただし、各ブロックは、その後継者を待たずに解凍でき、ストリーミング操作を可能にします。

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.

自然な順序:そのタイプのオブジェクトまたは値に典型的なオブジェクトまたは値の順序または順序付け。たとえば、セットまたはシーケンスの1つの要素から次の要素へ進むと、値が減少することはない場合、一連の一意の整数が "Natural Order"にあります。

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.

仕様内の識別子の命名規則は混在しています.case_with_underscoresです。角括弧内の識別子は、識別子が現在のコンテキストでオプションであることを示します。

3. Compression Algorithm
3. 圧縮アルゴリズム

This section describes the Zstandard algorithm.

このセクションでは、zStandardアルゴリズムについて説明します。

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

この文書の目的は、zStandardアルゴリズムを使用して、CPUタイプ、オペレーティングシステム、ファイルシステム、および文字セットと文字セットと文字セットとは無関係の可逆圧縮データフォーマットを定義することです。仕様書のテキストは、ビットのレベルおよび他のプリミティブデータ表現でのプログラミングの基本的な背景を想定しています。

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; hence, it 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.

データは、任意に長く長く順次に提示された入力データストリームを使用しても、中間記憶域の先験的な境界量を使用しても、生成または消費され得る。したがって、データ通信に使用できます。このフォーマットは、データ破損を検出するために、zStandard圧縮方式とオプションのXXHASH-64チェックサムメソッド[XXHASH]を使用します。

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.

以下に示さない限り、準拠のコンプレッサーはここに提示された仕様に適合するデータセットを生成しなければならない。ただし、すべてのオプションをサポートする必要はありません。

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 an unambiguous error code and associated error message explaining which parameter is unsupported.

準拠解凍器は、ここに提示された仕様に一致する少なくとも1つのワーキングセットのパラメータを解凍することができなければならない。チェックサムなどの有益な分野も無視することがあります。圧縮ストリームで定義されているパラメータをサポートしていないときはいつでも、どのパラメータがサポートされていないかを説明する、明確なエラーコードと関連エラーメッセージを作成する必要があります。

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].

この仕様は、データをzStandardフォーマットに圧縮するためのソフトウェアの実装者による使用、および/またはzStandardフォーマットからデータを解凍することを目的としています。zStandardフォーマットは、ポータブルCで書かれたオープンソースのリファレンス実装でサポートされ、[zstd]で入手可能です。

3.1. Frames
3.1. 骨折り

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.

zStandard圧縮データは1つ以上のフレームで構成されています。各フレームは独立しており、他のフレームとは無関係に解凍できます。複数の連結フレームの解凍されたコンテンツは、各フレームの解凍コンテンツの連結です。

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.

zStandard:zStandardフレームとスキップ可能なフレームには2つのフレームフォーマットがあります。zStandardフレームには圧縮データが含まれていますが、スキップ可能なフレームにはカスタムユーザーメタデータが含まれています。

3.1.1. Zstandard Frames
3.1.1. zStandardフレーム

The structure of a single Zstandard frame is as follows:

単一のzStandardフレームの構造は次のとおりです。

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

Table 1: The Structure of a Single Zstandard Frame

表1:単一のZSTANDARDフレームの構造

Magic_Number: 4 bytes, little-endian format. Value: 0xFD2FB528.

magic_number:4バイト、リトルエンディアンフォーマット。値:0xFD2FB528。

Frame_Header: 2 to 14 bytes, detailed in Section 3.1.1.1.

Frame_Header:3~14バイト、セクション3.1.1.1に詳述されています。

Data_Block: Detailed in Section 3.1.1.2. This is where data appears.

DATA_BLOCK:3.1.1.2項で詳しく説明します。これはデータが表示されます。

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.

content_checkSum:オプションの32ビットチェックサムは、content_checksum_flagが設定されている場合にのみ存在します。コンテンツチェックサムは、xxh64()ハッシュ関数[xxhash]オリジナル(復号化された)データを入力として消化し、シードゼロの結果です。チェックサムの低い4バイトは、リトルエンディアン形式で保存されています。

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 the 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.

マジックナンバーは、任意のファイルの先頭に見つける可能性が低くなるように選択されました。それは些細なパターン(0x00、0xFF、繰り返しバイト、バイトの増加など)を避け、ASCIIの範囲外のバイト値を含み、UTF-8スペースにマッピングされず、そのすべてがその外観の可能性を低下させます。テキストファイルの上

3.1.1.1. Frame Header
3.1.1.1. フレームヘッダー

The frame header has a variable size, with a minimum of 2 bytes up to a maximum of 14 bytes depending on optional parameters. The structure of Frame_Header is as follows:

フレームヘッダーは可変サイズを持ち、オプションのパラメーターに応じて最大14バイトまで最小2バイトです。Frame_Headerの構造は次のとおりです。

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

Table 2: The Structure of Frame_Header

表2:Frame_Headerの構造

3.1.1.1.1. Frame_Header_Descriptor
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.

最初のヘッダーのバイトはframe_header_descriptorと呼ばれます。それはどのような他のフィールドが存在するかを説明します。このバイトのデコードは、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      |
                 +------------+-------------------------+
        

Table 3: The Frame_Header_Descriptor

表3:frame_header_descriptor

In Table 3, bit 7 is the highest bit, while bit 0 is the lowest one.

表3では、ビット7が最も高いビットであり、ビット0は最も低いものです。

3.1.1.1.1.1. Frame_Content_Size_Flag
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. Frame_Content_Size_Flag provides FCS_Field_Size, which is the number of bytes used by Frame_Content_Size according to Table 4:

これは2ビットのフラグ(Frame_Header_Descriptor右シフト6ビットと同等)を指定します。frame_content_size_flagはfcs_field_sizeを提供します。これは表4に従ってFrame_Content_Sizeによって使用されるバイト数です。

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

Table 4: Frame_Content_Size_Flag Provides FCS_Field_Size

表4:frame_content_size_flagはfcs_field_sizeを提供します

When Frame_Content_Size_Flag 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.

frame_content_size_flagが0のとき、fcs_field_sizeはsignal_segment_flagによって異なります。single_segment_flagが設定されている場合、fcs_field_sizeは1です。そうでなければ、fcs_field_sizeは0です。FRAME_CONTENT_SIZEは提供されていません。

3.1.1.1.1.2. Single_Segment_Flag
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 a size equal to or larger than Frame_Content_Size.

この場合、window_descriptor byteはスキップされますが、frame_content_sizeは必ず存在します。結果として、デコーダは、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.

より広い互換性のために、デコーダは少なくとも8 MBのメモリサイズをサポートするために推奨されます。これは推奨事項です。各デコーダは、局所的な制限に応じて、より高いまたは下限を支えることができます。

3.1.1.1.1.3. Unused Bit
3.1.1.1.1.3. 未使用のビット

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
3.1.1.1.1.4. 予約ビット

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

このフラグが設定されている場合は、フレームの終わりに32ビットのcontent_checksumが存在します。上記のcontent_checksumの説明を参照してください。

3.1.1.1.1.6. Dictionary_ID_Flag
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:

これは、辞書IDがヘッダ内に設けられているかどうかを示す2ビットのフラグ(= resfil_header_descriptor&0x3)です。このフィールドのサイズもdid_field_sizeとして指定します。

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

Table 5: Dictionary_ID_Flag

表5:DICITIONARY_ID_FLAG

3.1.1.1.2. Window Descriptor
3.1.1.1.2. ウィンドウ記述子

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

window_descriptor byteはオプションです。single_segment_flagが設定されていると、window_descriptorは存在しません。この場合、window_sizeはframe_content_sizeです。これは、0から2 ^(64) - 1バイト(16 exabytes)の任意の値です。

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

Table 6: Window_Descriptor

表6:window_descriptor

The minimum memory buffer size is called Window_Size. It is described by the following formulas:

最小メモリバッファのサイズはwindow_sizeと呼ばれます。それは次の式で説明されています。

     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.

最小WINDOW_SIZEは1 KBです。最大window_sizeは(1 << 41)7 *(1 << 41)7 *(1 << 38)バイトです。これは3.75 TBです。

In general, larger Window_Size values tend to improve the compression ratio, but at the cost of increased memory usage.

一般に、より大きなwindow_size値は圧縮比を改善する傾向がありますが、メモリ使用量の増加のコストです。

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

圧縮データを正しくデコードするために、デコーダは少なくともwindow_sizeバイトのバッファを割り当てる必要があります。

In order to protect decoders 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 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 higher or lower limits, depending on local limitations.

相互運用性を向上させるために、デコーダは最大8 MBまでのwindow_sizeの値をサポートすることが推奨され、エンコーダは8 MBを超えるwindow_sizeを必要とするフレームを生成しないようにします。それは単に推奨事項であり、復号器はローカルの制限に応じてより高いまたは下限を支えることができます。

3.1.1.1.3. Dictionary_ID
3.1.1.1.3. Dictionary_ID

This is a field of variable size, 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.

これは可変サイズのフィールドです。これは、フレームを正しく復号するために必要な辞書のIDを含む。このフィールドはオプションです。存在しない場合は、どの辞書を使用するかを知るためにデコーダ次第です。

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.

dictionary_idフィールドサイズはdid_field_sizeによって提供されます。DID_FIELD_SIZEはDICITIOURE_ID_FLAGの値から直接派生しています。1バイトはID 0~255を表すことができます。2バイトはID 0~65535を表すことができます。4バイトはID 0~4294967295を表すことができます。フォーマットはリトルエンディアンです。

It is permitted to represent a small ID (for example, 13) with a large 4-byte dictionary ID, even if it is less efficient.

あまり効率的であっても、4バイトの辞書IDを持つ小さいID(たとえば、13)を表すことが許可されています。

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 7.4):

民間環境内では、辞書IDを使用できます。ただし、パブリック・スペースで配布されているフレームや辞書の場合、DICICTORACE_IDは慎重に属性になっている必要があります。次の範囲は、IANAに登録されている辞書でのみ使用するために予約されています(セクション7.4を参照)。

   low range:  <= 32767
        
   high range:  >= (1 << 31)
        

Any other value for Dictionary_ID can be used by private arrangement between participants.

dictionary_idの他の値は、参加者間のプライベート配置で使用できます。

Any payload presented for decompression that references an unregistered reserved dictionary ID results in an error.

未登録の予約辞書IDを参照する解凍のために提示されたペイロードは、エラーになります。

3.1.1.1.4. Frame_Content_Size
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.

これは元の(非圧縮)サイズです。この情報はオプションです。frame_content_sizeは、fcs_field_sizeによって提供される可変バイト数を使用します。fcs_field_sizeは、frame_content_size_flagの値によって提供されます。FCS_FIELD_SIZEは、0(存在せず)、1,2,4、または8バイトに等しくなります。

                    +================+================+
                    | FCS Field Size | Range          |
                    +================+================+
                    |       0        | unknown        |
                    +----------------+----------------+
                    |       1        | 0 - 255        |
                    +----------------+----------------+
                    |       2        | 256 - 65791    |
                    +----------------+----------------+
                    |       4        | 0 - 2^(32) - 1 |
                    +----------------+----------------+
                    |       8        | 0 - 2^(64) - 1 |
                    +----------------+----------------+
        

Table 7: Frame_Content_Size

表7:frame_content_size

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.

FRAME_CONTENT_SIZEフォーマットはリトルエンディアンです。fcs_field_sizeが1,4、または8バイトの場合、値は直接読み取られます。fcs_field_sizeが2のとき、256のオフセットが追加されます。互換性のあるバリアントを使用して、小さいサイズ(たとえば18)を表すことができます。

3.1.1.2. Blocks
3.1.1.2. ブロック

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.

magic_numberとframe_headerの後、いくつかのブロックがいくつかあります。各フレームは少なくとも1ブロックを持たなければなりませんが、フレームあたりのブロック数に上限はありません。

The structure of a block is as follows:

ブロックの構造は次のとおりです。

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

Table 8: The Structure of a Block

表8:ブロックの構造

Block_Header uses 3 bytes, written using little-endian convention. It contains three fields:

Block_Headerは、リトルエンディアン条約を使用して書かれた3バイトを使用します。3つのフィールドが含まれています。

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

Table 9: Block_Header

表9:Block_Header

3.1.1.2.1. Last_Block
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).

最低ビット(Last_Block)は、このブロックが最後のものかどうかを示します。この最後のブロックの後にフレームが終了します。オプションのContent_CheckSumが続く場合があります(セクション3.1.1を参照)。

3.1.1.2.2. Block_Type
3.1.1.2.2. block_type.

The next 2 bits represent the Block_Type. There are four block types:

次の2ビットはblock_typeを表します。4つのブロックタイプがあります。

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

Table 10: The Four Block Types

表10:4つのブロックタイプ

Raw_Block: This is an uncompressed block. Block_Content contains Block_Size bytes.

RAW_BLOCK:これは非圧縮ブロックです。block_content block_sizeバイトを含みます。

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.

RLE_BLOCK:これは単一のバイト、繰り返しのblock_size時間です。block_contentは1バイトで構成されています。解凍側では、このバイトはBlock_Sizeタイムを繰り返す必要があります。

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

compressed_block:3.1.1.3項で説明されているように圧縮ブロックです。block_sizeは、block_content、すなわち圧縮データの長さです。解凍されたサイズはわかりませんが、最大限の可能な値が保証されています(下記参照)。

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, and a compliant decoder must reject it.

予約済み:これはブロックではありません。この値は現在の指定では使用できません。そのような値が存在する場合は、破損したデータであると考えられ、準拠デコーダはそれを拒否しなければなりません。

3.1.1.2.3. Block_Size
3.1.1.2.3. block_size.

The upper 21 bits of Block_Header represent the Block_Size.

block_headerの上位21ビットはblock_sizeを表します。

When Block_Type is Compressed_Block or Raw_Block, Block_Size is the size of Block_Content (hence excluding Block_Header).

block_typeがcompressed_blockまたはraw_blockの場合、block_sizeはblock_content(したがってblock_headerを除く)のサイズです。

When Block_Type is RLE_Block, since Block_Content's size is always 1, Block_Size represents the number of times this byte must be repeated.

block_typeがrle_blockの場合、block_contentのサイズは常に1ですので、block_sizeはこのバイトを繰り返す必要がある回数を表します。

Block_Size is limited by Block_Maximum_Size (see below).

block_sizeはblock_maximum_sizeによって制限されます(下記参照)。

3.1.1.2.4. Block_Content and Block_Maximum_Size
3.1.1.2.4. block_contentとblock_maximum_size

The size of Block_Content is limited by Block_Maximum_Size, which is the smallest of:

block_contentのサイズはblock_maximum_sizeによって制限されています。これは以下の最小です。

* Window_Size

* window_size

* 128 KB

* 128キロ

Block_Maximum_Size is constant for a given frame. This maximum is applicable to both the decompressed size and the compressed size of any block in the frame.

block_maximum_sizeは特定のフレームに対して定数です。この最大値は、フレーム内の任意のブロックの解凍サイズと圧縮サイズの両方に適用されます。

The reasoning for this limit is that a decoder can read this information at the beginning of a frame and use it to allocate buffers. The guarantees on the size of blocks ensure that the buffers will be large enough for any following block of the valid frame.

この制限の推論は、デコーダがフレームの先頭にこの情報を読み取り、それを使用してバッファを割り当てることができることです。ブロックのサイズの保証は、バッファが次のフレームのいずれかのブロックに対して十分に大きくなることを保証します。

If the compressed block is larger than the uncompressed one, sending the uncompressed block (i.e., a Raw_Block) is recommended instead.

圧縮ブロックが圧縮されていないものより大きい場合は、非圧縮ブロック(すなわちRAW_BLOCK)を送信することを代わりに推奨する。

3.1.1.3. Compressed Blocks
3.1.1.3. 圧縮ブロック

To decompress a compressed block, the compressed size must be provided from the Block_Size field within Block_Header.

圧縮ブロックを解凍するためには、BLOMB_HEADER内のblock_sizeフィールドから圧縮サイズを指定する必要があります。

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

圧縮ブロックは2つのセクションで構成されています.Literals_Section(セクション3.1.1.3.1)とSequences_Section(セクション3.1.1.3.2)。次に、2つのセクションの結果が組み合わされて、順序実行で解凍されたデータが生成されます(セクション3.1.1.4)。

To decode a compressed block, the following elements are necessary:

圧縮ブロックを復号するには、次の要素が必要です。

* 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.

* window_sizeの距離、またはフレームの先頭まで、どちらか小さい方の復号化データ。後者の場合にSINGE_SEGUMENT_FLAGが設定されます。

* List of "recent offsets" from the previous Compressed_Block.

* 前のcompressed_blockからの「最近のオフセット」のリスト。

* The previous Huffman tree, required by Treeless_Literals_Block type.

* Treeless_Literals_Blockタイプに必要な前のハフマンツリー。

* Previous Finite State Entropy (FSE) decoding tables, required by Repeat_Mode, for each symbol type (literals length codes, match length codes, offset codes).

* 以前の有限状態エントロピー(FSE)repeats_modeによって必要な復号化テーブル(リテラル長コード、一致長コード、オフセットコード)ごとに必要です。

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

デコードテーブルは必ずしも前のcompressed_blockからのものではありません。

* Every decoding table can come from a dictionary.

* すべてのデコードテーブルは辞書から来ることができます。

* The Huffman tree comes from the previous Compressed_Literals_Block.

* ハフマンツリーは前のcompressed_literals_blockから来ています。

3.1.1.3.1. Literals_Section_Header
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.

すべてのリテラルはブロックの最初の部分で再グループ化されています。それらは最初に復号化されてからシーケンス実行中にコピーされます(セクション3.1.1.4を参照)、またはシーケンス実行中のフローでデコードできます。

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.

リテラルは、Huffmanプレフィックスコードを使用して非圧縮または圧縮されて保存できます。圧縮されたとき、オプションのツリー記述が存在し、続いて1または4のストリームが続くことができます。

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

Table 11: Compressed Literals

表11:圧縮リテラル

3.1.1.3.1.1. Literals_Section_Header
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.

このフィールドは、リテラルがどのようにパックされるかを説明します。それは、リトルエンディアン条約を使用して、1から5バイトの範囲のバイト整列型可変サイズビットフィールドです。

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

Table 12: Literals_Section_Header

表12:Liters_Section_Header

In this representation, bits at the top are the lowest bits.

この表現では、上部のビットが最も低いビットです。

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

literals_block_typeフィールドは、4つの異なるブロックタイプを記述する最初のバイトの最小ビットを使用します。

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

Table 13: Literals_Block_Type

表13:Literals_Block_Type.

Raw_Literals_Block: Literals are stored uncompressed. Literals_Section_Content is Regenerated_Size.

RAW_LITERALS_BLOCK:リテラルは圧縮されていない保存されています。literals_section_contentはREGENERATED_SIZEです。

RLE_Literals_Block: Literals consist of a single-byte value repeated Regenerated_Size times. Literals_Section_Content is 1.

RLE_LITERALS_BLOCK:リテラルは、regenerated_size時間を繰り返し繰り返します。literals_section_contentは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.

compressed_literals_block:これは、ハフマンツリーの説明から始めて、これは標準のハフマン圧縮ブロックです。下記の詳細を参照してください。literals_section_contentは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.

TreelEses_Literals_Block:これは前のcompressed_literals_blockまたは以前のハフマン圧縮リテラルブロックがない場合、ハフマンツリーを使用して、ハフマン圧縮ブロックです。Huffman_tree_descriptionはスキップされます。このモードがフレーム内の以前のハフマンテーブルなしで(またはセクション5ごとに辞書)のない場合は、データ破損として扱う必要があります。literals_section_contentはcompressed_sizeです。

The Size_Format is divided into two families:

size_formatは2つのファミリに分けられます。

* For Raw_Literals_Block and RLE_Literals_Block, it's only necessary to decode Regenerated_Size. There is no Compressed_Size field.

* RAW_LITERALS_BLOCKとRLE_LITERALS_BLOCKの場合、REGENERATED_SIZEをデコードするためだけに必要です。compressed_sizeフィールドはありません。

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

* compressed_blockおよびtreeless_literals_blockの場合、compressed_sizeとregenerated_size(解凍サイズ)の両方をデコードする必要があります。ストリーム数(1または4)を復号する必要があります。

For values spanning several bytes, the convention is little endian.

数バイトにまたがる値の場合、条約は小さなエンディアンです。

Size_Format for Raw_Literals_Block and RLE_Literals_Block uses 1 or 2 bits. Its value is (Literals_Section_Header[0]>>2) & 0x3.

size_format for raw_literals_blockとrle_literals_blockは1または2ビットを使用します。その値は(Literals_Section_Header [0] >> 2)&0x3です。

Size_Format == 00 or 10: Size_Format uses 1 bit. Regenerated_Size uses 5 bits (value 0-31). Literals_Section_Header uses 1 byte. Regenerated_Size = Literal_Section_Header[0]>>3.

size_format == 00または10:size_formatは1ビットを使用します。REGENERATED_SIZEは5ビット(値0~31)を使用します。literals_section_headerは1バイトを使用します。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.

これらの場合にStream_1だけが存在します。効率的であっても、長い形式を使用して短い値(例えば13)を表すことが許可されていることに注意してください。

Size_Format for Compressed_Literals_Block and Treeless_Literals_Block always uses 2 bits.

compressed_literals_blockおよびtreeless_literals_blockのsize_format_blockは常に2ビットを使用します。

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 == 00:単一のストリーム。REGENERATED_SIZEとCOMPRESSED_SIZEはどちらも10ビット(値0~1023)を使用します。literals_section_headerは3バイトを使用します。

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 == 01:4ストリーム。REGENERATED_SIZEとCOMPRESSED_SIZEはどちらも10ビット(値0~1023)を使用します。literals_section_headerは3バイトを使用します。

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 == 10:4ストリーム。REGENERATED_SIZEとCOMPRESSED_SIZEはどちらも14ビット(値0~16383)を使用します。literals_section_headerは4バイトを使用します。

Size_Format == 11: 4 streams. Both Regenerated_Size and Compressed_Size use 18 bits (values 0-262143). Literals_Section_Header uses 5 bytes.

size_format == 11:4ストリーム。REGENERATED_SIZEとCOMPRESSED_SIZEの両方が18ビット(値0~262143)を使用します。literals_section_headerは5バイトを使用します。

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.

compressed_sizeフィールドとRegenerated_sizeフィールドの両方がリトルエンディアン条約に従います。compressed_sizeには、存在するときにHuffman_tree_descriptionのサイズが含まれています。

3.1.1.3.1.2. Raw_Literals_Block
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).

Stream_1のデータはRegenerated_sizeバイト数です。シーケンス実行中に使用されるRAWリテラルデータが含まれています(セクション3.1.1.3.2)。

3.1.1.3.1.3. RLE_Literals_Block
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.

stream_1は、regenerated_size時間を繰り返す必要がある単一のバイトからなり、デコードされたリテラルを生成します。

3.1.1.3.1.4. Compressed_Literals_Block and Treeless_Literals_Block
3.1.1.3.1.4. compressed_literals_blockとtreeless_literals_block

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

これらのモードの両方にハフマン符号化データが含まれています。Treeless_Literals_Blockの場合、Huffmanテーブルは以前に圧縮されたリテラルブロック、または辞書からのものです。5セクション5を参照してください。

3.1.1.3.1.5. Huffman_Tree_Description
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.

このセクションは、Literals_block_typeタイプがcompressed_literals_block(2)の場合にのみ存在します。Huffman_tree_descriptionの形式はセクション4.2.1にあります。Huffman_Tree_Descriptionのサイズは、復号化プロセス中に決定されます。ストリームがどこから始まるのかを判断するために使用する必要があります。

Total_Streams_Size = Compressed_Size - Huffman_Tree_Description_Size

total_streams_size = compressed_size - Huffman_tree_description_size

3.1.1.3.1.6. Jump_Table
3.1.1.3.1.6. jump_table.

The Jump_Table is only present when there are 4 Huffman-coded streams.

Jump_tableは、4つのハフマン符号化ストリームがあるときにのみ存在します。

(Reminder: Huffman-compressed data consists of either 1 or 4 Huffman-coded streams.)

(注意:ハフマン圧縮データは、1または4つのハフマン符号化ストリームで構成されています。)

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.

1つのストリームのみが存在する場合は、セクション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.

4つのストリームがある場合、Literals_Section_Headerは4つのストリームすべてのすべてのストリームの解凍された圧縮サイズを知るための十分な情報を提供します。各ストリームの伸張されたサイズは、Regenerated_Sizeで指定されているように、最後のストリームを除いて、(Regenerated_Size 3)/ 4に等しくあります。

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 the sizes of other streams.

各ストリームの圧縮サイズは、Jump_tableで明示的に提供されます。JUMP_TABLEは6バイト長さで、最初の3つのストリームの圧縮サイズを記述して3つの2バイトのリトルエンディアンフィールドで構成されています。stream4_sizeはtotal_streams_sizeから他のストリームのサイズを引いたものから計算されます。

     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.

stream1_size stream2_size stream3_sizeがtotal_streams_sizeを超えると、データは破損していると見なされます。

Each of these 4 bitstreams is then decoded independently as a Huffman-coded stream, as described in Section 4.2.2.

セクション4.2.2で説明されているように、これらの4つのビットストリームのそれぞれはハフマン符号化ストリームとして独立して復号化される。

3.1.1.3.2. Sequences_Section
3.1.1.3.2. シーケンス_セクション

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.

圧縮ブロックは一連のシーケンスです。シーケンスはリテラルコピーコマンドであり、その後に一致コピーコマンドが続きます。リテラルコピーコマンドは長さを指定します。リテラル_Sectionからコピー(または抽出)するバイト数です。match copyコマンドは、オフセットと長さを指定します。

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

すべてのシーケンスがデコードされると、Literals_Sectionにリテラルが残っている場合、これらのバイトはブロックの最後に追加されます。

This is described in more detail in Section 3.1.1.4.

これはセクション3.1.1.4でより詳細に説明されています。

The Sequences_Section regroups all symbols required to decode commands. There are three symbol types: literals length codes, offset codes, and match length codes. They are encoded together, interleaved, in a single "bitstream".

sequences_sectionは、コマンドをデコードするのに必要なすべてのシンボルを再グループ化します。3つのシンボルタイプがあります:リテラル長のコード、オフセットコード、および一致する長さのコード。それらは、単一の「ビットストリーム」にインターリーブされた、一緒にエンコードされます。

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

sequences_sectionはヘッダーから始まり、続いて各シンボルタイプのオプションの確率表が続き、その後にビットストリームが続きます。

     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.

シーケンスをデコードするためには、そのサイズを知る必要があります。このサイズは、literals_section_section_size = block_size - literals_section_header - literals_section_contentのサイズから推定されます。

3.1.1.3.2.1. Sequences_Section_Header
3.1.1.3.2.1. Sequences_Section_Header

This header consists of two items:

このヘッダーは2つの項目で構成されています。

* Number_of_Sequences

* number_of_sequences

* Symbol_Compression_Modes

* symbal_compression_mode.

Number_of_Sequences is a variable size field using between 1 and 3 bytes. If the first byte is "byte0":

number_of_sequencesは、1~3バイトを使用して可変サイズフィールドです。最初のバイトが "byte0"の場合:

* 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.

* if(byte0 == 0):シーケンスはありません。シーケンスセクションはここで停止します。解凍されたコンテンツは、完全にリテラル数のコンテンツとして定義されます。repeate_modeで使用されているFSEテーブルは更新されません。

* if (byte0 < 128): Number_of_Sequences = byte0. Uses 1 byte.

* if(byte0 <128):number_of_sequences = byte0。1バイトを使用します。

* if (byte0 < 255): Number_of_Sequences = ((byte0 - 128) << 8) + byte1. Uses 2 bytes.

* if(byte0 <255):number_of_sequences =((byte0 - 128)<< 8)byte1。2バイトを使用します。

* if (byte0 == 255): Number_of_Sequences = byte1 + (byte2 << 8) + 0x7F00. Uses 3 bytes.

* if(byte0 == 255):number_of_sequences = byte1(byte2 << 8)0x7F00。3バイトを使用します。

Symbol_Compression_Modes is a single byte, defining the compression mode of each symbol type.

symbol_compression_modesは単一のバイトで、各シンボルタイプの圧縮モードを定義します。

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

Table 14: Symbol_Compression_Modes

表14:symbol_compression_mode.

The last field, Reserved, must be all zeroes.

予約された最後のフィールドは、すべてのゼロでなければなりません。

Literals_Lengths_Mode, Offsets_Mode, and Match_Lengths_Mode define the Compression_Mode of literals length codes, offset codes, and match length codes, respectively. They follow the same enumeration:

literals_lengths_mode、offsets_mode、およびmatch_lengths_modeリテラル長のコード、オフセットコード、および一致する長さのコードのcompression_modeを定義します。彼らは同じ列挙に従います:

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

Table 15: Literals_Lengths_Mode, Offsets_Mode, and Match_Lengths_Mode

表15:Literals_LengthS_Mode、offsets_mode、およびmatch_lengths_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.

predefined_mode:3.1.1.3.2.2項で定義されているように、定義済みのFSE(セクション4.1を参照)。配布テーブルはありません。

RLE_Mode: The table description consists of a single byte, which contains the symbol's value. This symbol will be used for all sequences.

RLE_MODE:テーブルの説明は、シンボルの値を含む1バイトで構成されています。この記号はすべてのシーケンスに使用されます。

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 code and match length code tables is 9, and the maximum accuracy log for the offset code 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).

fse_compressed_mode:標準のFSE圧縮。配布テーブルが存在するでしょう。この配布テーブルのフォーマットはセクション4.1.1で説明されています。リテラル長符号と一致長さのコード表についての最大許容精度ログは9、オフセットコード表の最大精度ログは8です。代わりにRLE_MODEを使用する必要があります(他のモードは機能しますが)。

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.

REPEAT_MODE:NUMBER_OF_SEQUENCES> 0を持つ前のcompressed_blockで使用されているテーブルが再度使用されます。またはこれが最初のブロックである場合は、辞書内のテーブルが使用されます。これにはrle_modeが含まれているので、repeat_modeがrle_modeに続く場合は、同じシンボルが繰り返されます。PRESEFINDING_MODEも含まれています。その場合、repeat_modeはpredefined_modeと同じ結果を持ちます。配布テーブルはありません。このモードがフレーム(または辞書(またはセクション5を参照)の以前のシーケンステーブルなしで使用される場合、これは破損として扱われるべきです。

3.1.1.3.2.1.1. Sequence Codes for Lengths and Offsets
3.1.1.3.2.1.1. 長さとオフセットのシーケンスコード

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.

各シンボルは、それ自体のコンテキスト内のコードです。これは、追加するベースラインとNUMBER_OF_BITSを指定します。コードはFSE圧縮され、同じビットストリーム内の生の追加ビットでインターリーブされます。

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.

リテラル長コードは、0から35までの値である値です。それらは0から131071バイトの長さを定義します。リテラルの長さは復号化されたベースラインに等しくなり、ビットストリームからのnumber_of_bitsビットをリトルエンディアンの値として読み取る結果です。

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

Table 16: Literals Length Codes

表16:リテラル長符号

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.

一致長さコードは、0から52までの値である。それらは3から131074バイトの長さを定義します。一致する長さは、復号化されたベースラインに等しく、ビットストリームからNumber_of_bitsビットをリトルエンディアン値として読み取る結果です。

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

Table 17: Match Length Codes

表17:マッチレングスコード

Offset codes are values ranging from 0 to N.

オフセットコードは、0から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.

デコーダは、N個のサポート値の最大値を自由に制限することができます。少なくとも22の値のサポートをお勧めします。この書き込み時に、参照デコーダは最大N値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に変換することもできます。

     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が(2 ^(n 1)) - 4までの(2 ^(n 1)) - 4までの(2 ^(n 1))-1であることを意味しますが、最大バックレーバー距離によって制限されています(セクション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.

1から3までのoffset_valueは特別です。それらは「繰り返しコード」を定義します。これについては、3.1.1.5項でさらに詳細に説明されています。

3.1.1.3.2.1.2. Decoding Sequences
3.1.1.3.2.1.2. デコードシーケンス

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.

FSEビットストリームは、書かれている方向の逆に読み取られます。ZSTDでは、コンプレッサーはビットをブロックに転送し、デコンプレッサーは後方にビットストリームを読み取る必要があります。

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.

ビットストリームの開始を見つけるためには、ブロックの最後のバイトのオフセットを知る必要があります。これは、ブロックヘッダーの後にblock_sizeバイトをカウントすることによって見つけることができます。

After writing the last bit containing information, the compressor writes a single 1 bit and then fills the rest of the byte with zero bits. The last byte of the compressed bitstream cannot be zero for that reason.

最後のビットを記録した後、コンプレッサーは単一の1ビットを書き込み、次にバイトの残りのバイトをゼロビットに埋めます。圧縮されたビットストリームの最後のバイトは、その理由でゼロになることはできません。

When decompressing, the last byte containing the padding is the first byte to read. The decompressor needs to skip the up to 7 bits of 0-padding as well as the first 1 bit that occurs. Afterwards, the useful part of the bitstream begins.

解凍すると、パディングを含む最後のバイトは読み取る最初のバイトです。デコンプレッサは、最初の1ビットと同様に、最大7ビットの0パディングと最初の1ビットをスキップする必要があります。その後、ビットストリームの有用な部分が始まります。

FSE decoding requires a 'state' to be carried from symbol to symbol. For more explanation on FSE decoding, see Section 4.1.

FSEデコードでは、シンボルからシンボルに伝送されることが必要です。FSE復号化の詳細については、4.1項を参照してください。

For sequence decoding, a separate state keeps track of each literals length, offset, and match length code. Some FSE primitives are also used. For more details on the operation of these primitives, see Section 4.1.

シーケンスデコードの場合、個別の状態は、リテラルの長さ、オフセット、および一致長さのコードを追跡します。いくつかのFSEプリミティブも使用されています。これらのプリミティブの動作の詳細については、セクション4.1を参照してください。

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.

ビットストリームは、それぞれの正確さのそれぞれの精度で必要なビット数を使用して、それぞれ初期のFSE状態値で始まります。それはliters_length_state、続いてオフセット_Stateを続け、最後に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.

すべての値が後方に読み取られるため、ビットストリームの「開始」は、パディングの最後の1ビットの直前のメモリ内の最高位置にあります。

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.

開始状態を復号した後、単一のシーケンスは復号化されたnumber_of_sequences時間です。これらのシーケンスは、最初から最後まで順番にデコードされます。コンプレッサはビットストリームを順方向に書き込むので、これはコンプレッサが最後のものから始めて最初に終わるシーケンスをエンコードしなければならないことを意味します。

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.

各シンボルタイプについて、FSE状態を使用して適切なコードを決定できます。その後、コードは各タイプに対して読み取るベースラインとnumber_of_bitsを定義します。これらの値を決定する方法のコードの説明は、セクション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).

復号化は、オフセットをデコードするのに必要なnumber_of_bitsを読み取ることから始まります。match_lengthの場合は同じことが同じです。このシーケンスはシーケンス実行に使用されます(3.1.1.4項を参照)。

If it is not the last sequence in the block, the next operation is to update states. Using the rules precalculated 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.

ブロック内の最後のシーケンスではない場合、次の操作は状態を更新することです。復号化テーブルで事前に計算されたルールを使用して、Literals_Length_Stateを更新し、続いてmatch_length_state、そしてオフセット_Stateを実行します。ビットストリームから状態を更新する方法については、セクション4.1を参照してください。

This operation will be repeated Number_of_Sequences times. At the end, the bitstream shall be entirely consumed; otherwise, the bitstream is considered corrupted.

この操作はnumber_of_sequences時間繰り返されます。最後に、ビットストリームは完全に消費されるものとします。それ以外の場合、ビットストリームは破損していると見なされます。

3.1.1.3.2.2. Default Distributions
3.1.1.3.2.2. デフォルトのディストリビューション

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.

PRESEFINDING_MODEがシンボルタイプに対して選択されている場合、そのFSEデコードテーブルはここで定義されている定義済み配布テーブルから生成されます。この分布を復号化テーブルに変換する方法については、セクション4.1を参照してください。

3.1.1.3.2.2.1. Literals Length Codes
3.1.1.3.2.2.1. リテラル長符号

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

復号化テーブルは、6ビット(64状態)の精度ログを使用する。

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 };

短い文字rength_defaultDistribution [36] = {4,3,2,2,2,2,2,2,2,2,2,2,2,2,1,1,2,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 Codes
3.1.1.3.2.2.2. マッチレングスコード

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

復号化テーブルは、6ビット(64状態)の精度ログを使用する。

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 };

短い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,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,1,1,1,1,1、 - 1、-1、-1、-1、-1、-1、-1}。

3.1.1.3.2.2.3. Offset Codes
3.1.1.3.2.2.3. オフセットコード

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.

復号化テーブルは、5ビット(32状態)の精度ログを使用し、最大N値を28個サポートし、最大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 };

短いオフセット符号_DefaultDistribution [29] = {1,1,1,1,1,1,1,2,2,1,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
3.1.1.4. シーケンス実行

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.

各シーケンスは、sequeces_section(セクション3.1.1.3.2)で説明されているように復号化された(Literals_Length、offset_value、match_length)のタプルで構成されています。シーケンスを実行するには、最初にデコードされたリテラルからLiterals_Lengthバイトを出力にコピーします。

Then, match_length bytes are copied from previous decoded data. The offset to copy from is determined by offset_value:

その後、match_lengthバイトを以前の復号化データからコピーします。コピーするオフセットは、OFFSET_VALUEによって決まります。

* if Offset_Value > 3, then the offset is Offset_Value - 3;

* offset_value> 3の場合、オフセットはoffset_value - 3です。

* if Offset_Value is from 1-3, the offset is a special repeat offset value. See Section 3.1.1.5 for how the offset is determined in this case.

* offset_valueが1-3の場合、オフセットは特別な繰り返しオフセット値です。この場合、オフセットがどのように決定されるかについては、セクション3.1.1.5を参照してください。

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

オフセットは、現在位置(リテラルをコピーした後)から定義されているので、6のオフセットと3つの長さ3は、3バイトを6バイトからコピーする必要があります。以前にデコードされたデータをもたらすすべてのオフセットは、frame_header_descriptorで定義されているwindow_sizeより小さくなければなりません(セクション3.1.1.1.1)。

3.1.1.5. Repeat Offsets
3.1.1.5. オフセットを繰り返します

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".

上記のように、最初の3つの値は繰り返しオフセットを定義します。repisted_offset1、repispe_offset2、およびreptial_offset3と呼びます。それらは、repisted_offset1を意味し、「最新のもの」を意味します。

If offset_value is 1, then the offset used is Repeated_Offset1, etc.

offset_valueが1の場合、使用されるオフセットはreplant_offset1などです。

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.

例外が1つあります。現在のシーケンスのリテラルが0の場合、繰り返しのオフセットは1だけシフトされます。

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.

最初のブロックの場合、開始オフセット履歴には、辞書が使用されていない限り、repistion_offset1(1)、repisted_offset2(4)、およびrepents_offset3(8)が入力されます。

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.

それから、各ブロックは、最新のcompressed_blockの終了値から始動オフセット履歴を取得します。compressed_blockではないブロックはスキップされていることに注意してください。彼らはオフセット履歴に貢献しません。

During the execution of the sequences of a Compressed_Block, the Repeated_Offsets' values are kept up to date, so that they always represent the three most recently used offsets. In order to achieve that, they are updated after executing each sequence in the following way:

compressed_blockのシーケンスの実行中に、repisted_offsets 'の値は最新の状態に保たれますので、それらは常に最後に使用されているオフセットを表します。それを達成するために、それらは次のようにして各シーケンスを実行した後に更新される。

When the sequence's offset_value does not refer to one of the Repeated_Offsets -- when it has value greater than 3, or when it has value 3 and the sequence's literals_length is zero -- the Repeated_Offsets' values are shifted back one, and Repeated_Offset1 takes on the value of the offset that was just used.

シーケンスのoffset_valueがrepisted_offsetsの1つを参照しない - それが3より大きい値を持つとき、またはそれが値3とシーケンスのliterals_lengthがゼロのとき - repistion_offsets '値は1つずつずつ取り戻されます。使用されたばかりのオフセットの値。

Otherwise, when the sequence's offset_value refers to one of the Repeated_Offsets -- when it has value 1 or 2, or when it has value 3 and the sequence's literals_length is non-zero -- the Repeated_Offsets are reordered, so that Repeated_Offset1 takes on the value of the used Repeated_Offset, and the existing values are pushed back from the first Repeated_Offset through to the Repeated_Offset selected by the offset_value. This effectively performs a single-stepped wrapping rotation of the values of these offsets, so that their order again reflects the recency of their use.

それ以外の場合、シーケンスのoffset_valueとは、repistion_offsetsのいずれかを参照しています。使用されているrepistion_offsetのうち、既存の値は、offset_valueによって選択された最初のrepistion_offsetからrepistion_offsetから繰り返されます。これにより、これらのオフセットの値の単一階段のラッピング回転を効果的に実行するので、それらの順序はそれらの使用の推論を反映している。

The following table shows the values of the Repeated_Offsets as a series of sequences are applied to them:

次の表は、repistion_offsetsの値をシーケンスに適用したものです。

   +=======+==========+===========+===========+===========+============+
   |offset_|literals_ | Repeated_ | Repeated_ | Repeated_ |Comment     |
   | value |  length  |  Offset1  |  Offset2  |  Offset3  |            |
   +=======+==========+===========+===========+===========+============+
   |       |          |     1     |     4     |     8     |starting    |
   |       |          |           |           |           |values      |
   +-------+----------+-----------+-----------+-----------+------------+
   |   1114|    11    |    1111   |     1     |     4     |non-repeat  |
   +-------+----------+-----------+-----------+-----------+------------+
   |      1|    22    |    1111   |     1     |     4     |repeat 1; no|
   |       |          |           |           |           |change      |
   +-------+----------+-----------+-----------+-----------+------------+
   |   2225|    22    |    2222   |    1111   |     1     |non-repeat  |
   +-------+----------+-----------+-----------+-----------+------------+
   |   1114|   111    |    1111   |    2222   |    1111   |non-repeat  |
   +-------+----------+-----------+-----------+-----------+------------+
   |   3336|    33    |    3333   |    1111   |    2222   |non-repeat  |
   +-------+----------+-----------+-----------+-----------+------------+
   |      2|    22    |    1111   |    3333   |    2222   |repeat 2;   |
   |       |          |           |           |           |swap 1 & 2  |
   +-------+----------+-----------+-----------+-----------+------------+
   |      3|    33    |    2222   |    1111   |    3333   |repeat 3;   |
   |       |          |           |           |           |rotate 3 to |
   |       |          |           |           |           |1           |
   +-------+----------+-----------+-----------+-----------+------------+
   |      1|    0     |    2221   |    2222   |    1111   |insert      |
   |       |          |           |           |           |resolved    |
   |       |          |           |           |           |offset      |
   +-------+----------+-----------+-----------+-----------+------------+
   |      1|    0     |    2222   |    2221   |    3333   |repeat 2    |
   +-------+----------+-----------+-----------+-----------+------------+
        

Table 18: Repeated_Offsets

表18:repistion_offsets.

3.1.2. Skippable Frames
3.1.2. スキップ可能なフレーム
                 +==============+============+===========+
                 | Magic_Number | Frame_Size | User_Data |
                 +==============+============+===========+
                 |   4 bytes    |  4 bytes   |  n bytes  |
                 +--------------+------------+-----------+
        

Table 19: Skippable Frames

表19:スキップ可能なフレーム

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].

本明細書で定義されているスキップ可能なフレームは、[LZ4]のSkippableフレームと互換性があります。

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.

スキップ可能なフレームを使用して、任意の種類の追跡情報を埋め込む連結フレームのストリームを透かして(普遍的に一意の識別子(UUID)でも)。そのような可能性のないユーザーは、分析または削除のためにそのようなフレームを検出するために連結フレームのストリームをスキャンする必要があります。

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.

magic_number:4バイト、リトルエンディアンフォーマット。値:0x184d2a5?、0x184D2A50から0x184D2A5Fまでの任意の値を意味します。16の値はすべてスキップ可能なフレームを識別するために有効です。この仕様では、スキップ可能なフレームの特定のタグ付け方法を詳しく説明していません。

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.

frame_size:これは、次のuser_dataのサイズ(マジックナンバーもサイズフィールド自体を含まず)です。このフィールドは、4バイト、リトルエンディアンフォーマット、符号なし32ビットを使用して表されます。つまり、user_dataは(2 ^(32)-1)バイトより大きくすることはできません。

User_Data: This field can be anything. Data will just be skipped by the decoder.

user_data:このフィールドは何でもすることができます。データはデコーダによってスキップされます。

4. Entropy Encoding
4. エントロピーエンコーディング

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.

2種類のエントロピー符号化は、zStandard形式:FSEとハフマン符号化によって使用されます。Huffmanはリテラルを圧縮するために使用されますが、FSEは他のすべてのシンボル(Literals_Length_code、Match_Length_Code、およびOffset Codes)に使用され、Huffmanヘッダーを圧縮します。

4.1. FSE
4.1. f

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.

FSE、有限状態エントロピーの場合は短い場合は、[ANS]に基づくエントロピーコーデックです。FSEエンコーディング/復号化はシンボル間で伝送される状態を含み、復号化は符号化として反対方向に行わなければならない。したがって、すべてのFSEビットストリームが終了から最初から読み込まれます。ストリーム内のビットの順序は逆ではないことに注意してください。それらは単にそれらが書かれた逆の順序で読む。

For additional details on FSE, see "FiniteStateEntropy" [FSE].

FSEの詳細については、「FENITESTANTEROPY」[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.

FSEデコードは、2つのサイズを有する復号化テーブルを含み、シンボル、num_bits、およびベースライン3つの要素を含む。テーブルサイズの基本2の対数はその字形_logです。FSE状態値はこのテーブルのインデックスを表します。

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.

初期状態値を取得するには、小さなエンディアン値としてストリームからPRECTICE_LOGビットを消費します。ストリーム内の次の記号は、その状態の表に示されているシンボルです。次の状態値を取得するには、デコーダはストリームからNUM_BITSビットをリトルエンディアン値として消費し、それをベースラインに追加する必要があります。

4.1.1. FSE Table Description
4.1.1. FSEテーブルの説明

To decode FSE streams, it is necessary to construct the decoding table. The Zstandard format encodes FSE table descriptions as described here.

FSEストリームをデコードするためには、復号化テーブルを構成する必要がある。zStandardフォーマットは、ここで説明されているようにFSEテーブルの説明をエンコードします。

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 nonzero probability.

FSE分布テーブルは、正規化されたスケール(1 << ecrecty_log)の0から最後の存在の1つ(含まれている)までのすべてのシンボルの確率を表します。ゼロ以外の確率で2つ以上のシンボルがなければならないことに注意してください。

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.

リトルエンディアンファッションでは、ビットストリームが前方に読み込まれます。サイズは復号化プロセスによって発見され報告されるので、その正確なサイズを知る必要はありません。ビットストリームは、どのスケールで動作するかについてのレポートによって開始されます。LOW4BITSが最初のバイトの最下位4ビットを指定した場合、PRECTY_LOG = LOW4BITS 5。

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:

これに続いて、0から最後の現在のものまで、各シンボル値が続きます。各フィールドで使用されるビット数は変数で、次のように依存します。

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 log_(2)sup(157) == 8 bits.

残り確率1:例えば、8の精度を推定し、100個の確率ポイントを推定しており、デコーダは0から(256 - 100 1)== 157までの任意の値を読み取ることができます。したがって、log_(2)sup(157)== 8ビットを読み取る必要があります。

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 the scheme in Table 20:

復号化された値:小さい値は1少ないビットを使用します。たとえば、0から157までの値が可能です.255 - 157 = 98の値が8ビットフィールドに残っています。最初の98の値(したがって、0から97まで)は7ビットしか使用さず、98から157の値は8ビットを使用します。これは表20のスキームを通して達成されます。

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

Table 20: Values Decoded

表20:値をデコードします

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.

シンボル確率は1つずつ読み込まれます。許容値は、式P = value -1を使用して復号された値から得られます。これは、値0が負の確率-1になることを意味します。これは「1未満」を意味する特別な確率です。分布テーブルへの影響については後述する。総割り当て確率点を計算する目的で、それは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.

シンボルがゼロの確率がある場合、それに続いて2ビットの繰り返しフラグが続きます。この繰り返しフラグは、ゼロの確率が現在のものに従うことを示しています。それは0から3の範囲の数値を提供する3であれば、もう1つの2ビットの繰り返しフラグが続きます。

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.

最後の記号が累積合計(1 << ecrectacy_log)に達すると、復号は完了します。最後のシンボルが累積合計を上に累積した場合(1 << ecrectacy_log)、分布は破損していると見なされます。

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 context in which the table is to be used specifies an expected number of symbols. That expected number of symbols never exceeds 256. If the number of symbols decoded is not equal to the expected, the header should be considered corrupt.

テーブルを使用するコンテキストは、予想されるシンボル数を指定します。それが予想されるシンボル数は256を超えない。デコードされたシンボルの数が予想と等しくない場合、ヘッダは破損していると見なされるべきです。

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.

正規化確率の分布は、固有の復号化テーブルを作成するのに十分です。テーブルのサイズは(1 << ecreasce_log)です。各セルは、次の状態を取得するためのシンボル復号化および命令を記述します。

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.

シンボルは、上述のように「1未満の」確率のための自然な順序でスキャンされます。この確率を持つシンボルは、テーブルの最後から始めて、テーブルの終わりから始めて、単一のセルに起因しています。これらのシンボルは、完全な状態リセット、正確さ_logビットを定義します。

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:

残りのすべてのシンボルはそれらの自然な順序で割り当てられています。シンボル0とテーブル位置0から始めて、各シンボルはその確率と同じ数のセルとして割り当てられます。セル割り当ては線形ではなく拡散されます。各後継者の位置はこの規則に従います。

     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.

「1未満の確率シンボル」で既に占められている場合、位置はスキップされます。位置はシンボル間でリセットされません。それは単にテーブル内の各位置を繰り返し、十分な状態が現在のものに割り当てられているときに次の記号に切り替えます。

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.

NUMBER_OF_BITSとベースラインを次の状態に必要な場合は、まずそれらの自然な順序ですべての状態をソートする必要があります。低い状態は、より高いものよりも1ビットが必要です。プロセスは各シンボルに対して繰り返されます。

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.

例えば、シンボルの推定は5の確率を有するので、5つの状態値を受信する。状態は自然な順序でソートされています。2の次の電力は8です。確率のスペースは8等しい部分に分けられます。eccectacy_logの推定は7で、これは128の状態を定義し、各共有(8で割った)は16のサイズです。8,8 - 5 = 3 = 3 = 3最低状態になると、「double」が「幅32の幅の32」を2倍にし、プロセスで1ビットを必要とします。

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

Table 21: Baseline Assignments

表21:ベースライン割り当て

The next state is determined from the current state by reading the required Number_of_Bits and adding the specified Baseline.

次の状態は、必要なnumber_of_bitsを読み取り、指定されたベースラインを追加することによって、現在の状態から決定されます。

See Appendix A for the results of this process that are applied to the default distributions.

デフォルトのディストリビューションに適用されるこのプロセスの結果については、付録Aを参照してください。

4.2. Huffman Coding
4.2. ハフマンコーディング

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.

zStandardハフマン符号化ストリームは、FSEビットストリームと同様に後方に読み取られます。したがって、ビットストリームの開始を見つけるためには、ハフマン符号化ストリームの最後のバイトのオフセットを知る必要がある。

After writing the last bit containing information, the compressor writes a single 1 bit and then fills the rest of the byte with 0 bits. The last byte of the compressed bitstream cannot be 0 for that reason.

最後のビットを記録した後、コンプレッサーは1ビットを1ビットに書き込み、次にバイトの残りのバイトを0ビットに記入します。圧縮ビットストリームの最後のバイトは、その理由で0にすることはできません。

When decompressing, the last byte containing the padding is the first byte to read. The decompressor needs to skip the up to 7 bits of 0-padding as well as the first 1 bit that occurs. Afterwards, the useful part of the bitstream begins.

解凍すると、パディングを含む最後のバイトは読み取る最初のバイトです。デコンプレッサは、最初の1ビットと同様に、最大7ビットの0パディングと最初の1ビットをスキップする必要があります。その後、ビットストリームの有用な部分が始まります。

The bitstream contains Huffman-coded symbols in little-endian order, with the codes defined by the method below.

ビットストリームには、小さい順序でハフマン符号化シンボルが含まれており、以下のメソッドによって定義されたコードが含まれています。

4.2.1. Huffman Tree Description
4.2.1. ハフマンツリーの説明

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.

プレフィックスコードは最大コード長を超えてはいけません。より多くのビットは精度を向上させますが、より大きなヘッダーサイズをもたらし、より多くのメモリまたはより複雑な復号化操作を必要とします。この仕様は最大コード長を11ビットに制限します。

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:

ゼロ(inculd)から最後の存在(除外)までのすべてのリテラル値は、0からmax_number_of_bitsの値で重み付けされます。重みからnumber_of_bitsへの変換は、この疑似コードに従います。

     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.

最後のシンボルの重さは、最近復号化されたものから推定されます.2の最も近い電力に完了することによって、この電力はmax_number_of_bitsの現在のツリーの深さを与えます。

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

Table 22: Huffman Tree

表22:ハフマンツリー

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:

最長要素は4ビットを使用するため、ツリーの深さは4です。(最長の要素は最小の要素は最小の周波数です。)値5は、0から4の値から決定されることも、5以上の値でも0から5を超える値ではありません.0から4の値がリストされます。number_of_bitsの代わりに重みを使用します。重みを決定するための疑似コードは次のとおりです。

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

Table 23: Weights

表23:重みの

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 nonzero 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.

デコーダは逆動作を行います。5の重みは2の次の電力に進むことによって決定することができる.2((重み-1))(0の除外)は15です.2の最も近い電力は16です。したがって、max_number_of_bits = 4と重さ[5] = 16 - 15 = 1。

4.2.1.1. Huffman Tree Header
4.2.1.1. ハフマンツリーヘッダー

This is a single byte value (0-255), which describes how the series of weights is encoded.

これは単一のバイト値(0~255)で、一連の重みがどのように符号化されるかを説明します。

headerByte < 128: The series of weights is compressed using FSE (see below). The length of the FSE-compressed series is equal to headerByte (0-127).

HeaderByte <128:一連の重みはFSEを使用して圧縮されます(下記参照)。FSE圧縮シリーズの長さはヘッダバイト(0~127)に等しい。

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:

HeaderByte> = 128:これは直接表現です。各重みは4ビットフィールドとして直接書き込まれます(0~15)。それらは、上部4ビットをとり、2番目の重みを底部4ビットとし、底部4を撮影する。たとえば、次の操作を使用して重みを読むことができます。

        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.

フル表現は天井(NUMBER_OF_SYMBOLS / 2)バイトを占め、NUMBER_OF_SYMBOLSが奇数であってもフルバイトのみを使用します。number_of_symbols = headerByte - 127.最大数値_of_symbolsは255 - 127 = 128です。リテラルが128を超える値がある場合、RAWヘッダーモードは不可能で、FSE圧縮を使用する必要があります。

4.2.1.2. FSE Compression of Huffman Weights
4.2.1.2. ハフマン重量のFSE圧縮

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.

この場合、一連のハフマン重みはFSE圧縮を使用して圧縮される。それは単一の配信テーブルを共有する2つのインターリーブ状態を持つ単一のビットストリームです。

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.

FSEビットストリームを復号するためには、その圧縮サイズを知る必要があります。圧縮サイズはヘッダーバイトによって提供されます。リテラル値が0から255に及び、最後のシンボルの重みが表されていないため、最大の可能な解凍サイズを255であることも必要です。

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.

FSEビットストリームはヘッダーから始まり、確率の配布を説明します。復号化テーブルを作成します。ハフマン重みのリストについては、最大精度ログは6ビットです。詳細については、セクション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.

ハフマンヘッダ圧縮は2つの状態を使用し、同じFSE分布テーブルを共有します。第1状態(STATE1)は偶数番号のインデックスシンボルを符号化し、2番目(STATE2)は奇数索引シンボルを符号化する。STATE1は最初に初期化され、次にSTATE2を順番に復元すると、単一のシンボルを復号化し、それらの状態を更新します。これらのFSE操作の詳細については、セクション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.

復号するシンボルの数は、ビットストリームオーバーフロー条件を追跡することによって決定される。シンボルを復号した後の更新状態がストリーム内に残っているよりも多くのビットを必要とするならば、それは余分なビットがゼロであると仮定される。次に、最終状態のそれぞれのシンボルがデコードされ、プロセスが完了します。

4.2.1.3. Conversion from Weights to Huffman Prefix Codes
4.2.1.3. 重みからハフマンプレフィックスコードへの変換

All present symbols will now have a Weight value. It is possible to transform weights into Number_of_Bits, using this formula:

現在のシンボルはすべて重み値を持ちます。この式を使用して、重みをnumber_of_bitsに変換することが可能です。

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

ウェイト> 0 number_of_bits = max_number_of_bits 1 - 重み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    |
                           +---------+--------+
        

Table 24: Decoded Weights

表24:復号された重み

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

Table 25: Sorting by Weight

表25:重さによるソート

4.2.2. Huffman-Coded Streams
4.2.2. ハフマン符号化ストリーム

Given a Huffman decoding table, it is possible to decode a Huffman-coded stream.

ハフマン復号化テーブルを考えると、ハフマン符号化ストリームを復号することが可能である。

Each bitstream must be read backward, starting from the end and going 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.

最後のビットが正確にどのビットであるかを知ることも必要です。これは最終ビットフラグによって検出されます。最後のバイトの最高ビットは最後のビットフラグです。その結果、最後のバイトが不可能ではありません。そして最終ビットフラグ自体は有用なビットストリームの一部ではありません。したがって、最後のバイトは0から7の有用なビットを含みます。

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.

最後から始めて、既に使用されているビットを追跡しながら、リトルエンディアンファッションでビットストリームを読み取ることが可能です。ビットストリームは、最後から始めて逆の順序で符号化されているので、順方向にシンボルを読み取る。

For example, if the literal sequence "0145" was encoded using the above prefix code, it would be encoded (in reverse order) as:

たとえば、リテラルシーケンス "0145"が上記の接頭辞コードを使用してエンコードされた場合は、次のようにエンコードされます(逆の順序)。

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

Table 26: Literal Sequence "0145"

表26:リテラルシーケンス「0145」

This results in the following 2-byte bitstream:

これにより、次の2バイトのビットストリームが得られます。

00010000 00001101

00010000 00001101

Here is an alternative representation with the symbol codes separated by underscores:

これは、アンダースコアによって区切られたシンボルコードを持つ代替表現です。

0001_0000 00001_1_01

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.

最高のMAX_NUMBER_OF_BITSビットを読み取ると、抽出された値をデコードテーブルと比較し、デコードするシンボルと廃棄するビット数を決定することができます。

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
5. 辞書フォーマット

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.

zStandardは、それらが少なくとも8バイトでなければならないことを除いて、フォーマットの制限を含まない、 "Raw Content"辞書と互換性があります。これらの辞書は、フォーマットされた辞書のコンテンツ部分だけであるかのように機能します。

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

ただし、参照実装の「zstd --train」によって作成された辞書は、ここで説明されている特定のフォーマットに従います。

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 mechanism by which the dictionary is obtained prior to use during compression or decompression.

辞書は圧縮コンテンツに含まれていませんが、むしろ帯域外に提供されます。つまり、dictionary_idは使用する必要があるが識別されているが、この仕様は、圧縮または解凍中に使用する前に辞書が得られるメカニズムを説明していない。

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

Table 27: Dictionary General Format

表27:辞書一般的なフォーマット

Magic_Number: 4 bytes ID, value 0xEC30A437, little-endian format.

magic_number:4バイトID、値0xec30A437、リトルエンディアンフォーマット。

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:

dictionary_id:4バイト、リトルエンディアン形式で保存されています。dictionary_idは0を除いて任意の値にすることができます(これはdictionary_idを意味しません)。それは彼らが正しい辞書を使用するかどうかをチェックするためにデコーダによって使用されます。フレームがプライベート環境で配布される予定の場合は、yprickary_idを使用できます。しかしながら、圧縮フレームの公衆分配のために、以下の範囲は予約されており、使用されてはならない。

         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.

Entropy_tables:圧縮ブロック内のテーブルと同じ形式に従います。これらのテーブルをデコードする方法については、関連するFSEおよびHuffmanセクションを参照してください。これらは、次の順序で保存されます.Literals用のHuffmanテーブル、オフセットのFSEテーブル、マッチング長のFSEテーブル、およびリテラル長のFSEテーブル。これらのテーブルは、繰り返し統計リテラルモードとシーケンス復号化のために配布モードを繰り返します。それは最後に3つのオフセット値を続け、({1,4,8}を使用する代わりに({1,4,8}を使用するのではなく)、4バイトのリトルエンディアンの合計12バイトの間、繰り返しオフセットを入力します。各繰り返しオフセットには、辞書サイズよりも小さい値が必要です。

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.

コンテンツ:残りの辞書はその内容です。コンテンツは、圧縮または解凍されるべきデータの前の「過去」として機能するので、シーケンスコマンドで参照できます。このフレームから復号されたデータ量がwindow_size以下である限り、シーケンスコマンドはこれまで復号化出力の全長よりも長いオフセットを指定して、オフセットを有する辞書の一部であってもwindow_size。ただし、全出力がwindow_sizeを超えた後は、これは許可されなくなり、辞書にはアクセスできなくなりました。

6. Use of Dictionaries
6. 辞書の使用

Provisioning for use of dictionaries with zstd is being explored. See, for example, [DICT-SEC]. The likely outcome will be a registry of well-tested dictionaries optimized for different use cases and identifiers for each, possibly with a private negotiation mechanism for use of unregistered dictionaries.

ZSTDを使用して辞書を使用するためのプロビジョニングが検討中です。たとえば、[DICT-SEC]を参照してください。可能性の高い成果は、除外されていない辞書の使用のための秘密交渉メカニズムを持つ、それぞれの異なるユースケースと識別子に対して最適化されたよくテストされた辞書のレジストリです。

To ensure compatibility with the future specification of use of dictionaries with zstd payloads, especially with MIME, content encoded with the media type registered here should not use a dictionary. The exception to this requirement might be a private dictionary negotiation, suggested above, which is not part of this specification.

ZSTDペイロードを使用した辞書の使用の将来の互換性との互換性を確保するために、特にMIMEでは、ここに登録されているメディアタイプでエンコードされたコンテンツは辞書を使用しないでください。この要件の例外は、上記で示唆されたプライベート辞書ネゴシエーションであり、これはこの仕様の一部ではありません。

7. IANA Considerations
7. IANAの考慮事項

IANA has updated two previously existing registrations and made one new registration as described below.

IANAは、以前に既存の登録を更新し、以下に説明するように新しい登録を1つ作成しました。

7.1. The 'application/zstd' Media Type
7.1. 「アプリケーション/ ZSTD」メディアタイプ

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:

'application / zstd'メディアタイプは、zstd圧縮を使用して圧縮されているデータブロックを識別します。このドキュメントで説明されているように、データはバイトのストリームです。IANAは「メディアタイプ」レジストリに次のものを追加しました。

Type name: application

タイプ名:アプリケーション

Subtype name: zstd

サブタイプ名:ZSTD

Required parameters: N/A

必要なパラメータ:N / A.

Optional parameters: N/A

オプションのパラメータ:n / A.

Encoding considerations: binary

エンコードに関する考慮事項:バイナリ

Security considerations: See Section 8 of RFC 8878.

セキュリティ上の考慮事項:RFC 8878のセクション8を参照してください。

Interoperability considerations: N/A

相互運用性の考慮事項:N / A.

Published specification: RFC 8878

公開仕様:RFC 8878

Applications which use this media type: anywhere data size is an issue

このメディアタイプを使用するアプリケーション:Anywhereデータサイズは問題です

Fragment identifier considerations: No fragment identifiers are defined for this type.

フラグメント識別子の考慮事項:このタイプにフラグメント識別子は定義されていません。

Additional information:

追加情報:

      Deprecated alias names for this type:  N/A
      Magic number(s):  4 bytes, little-endian format.
         Value: 0xFD2FB528
      File extension(s):  zst
      Macintosh file type code(s):  N/A
        
   Person & email address to contact for further information:  Yann
      Collet <cyan@fb.com>
        

Intended usage: common

意図された使用法:一般的な

Restrictions on usage: N/A

使用制限:N / A.

Author: Murray S. Kucherawy

著者:Murray S. Kucherawy

Change Controller: IETF

変更コントローラ:IETF.

Provisional registration: no

暫定登録:いいえ

For further information: See [ZSTD]

詳細については:[zstd]を参照

7.2. Content Encoding
7.2. コンテンツエンコーディング

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

IANAは、「ハイパーテキスト転送プロトコル(HTTP)パラメータ」レジストリ内の「HTTPコンテンツコーディングレジストリ」に次のエントリを追加しました。

Name: zstd

名前:zstd.

Description: A stream of bytes compressed using the Zstandard protocol

説明:zStandardプロトコルを使用して圧縮されたバイトのストリーム

Reference: RFC 8878

参照:RFC 8878

7.3. Structured Syntax Suffix
7.3. 構造化構文接尾辞

IANA has registered the following into the "Structured Syntax Suffix" registry:

IANAは「構造化構文サフィックス」レジストリに次のものを登録しました。

Name: Zstandard

名前:zStandard.

   +suffix:  +zstd
        

Encoding Considerations: binary

エンコードに関する考慮事項:バイナリ

Interoperability Considerations: N/A

相互運用性の考慮事項:N / A.

Fragment Identifier Considerations: The syntax and semantics of fragment identifiers specified for +zstd should be as specified for 'application/zstd'.

フラグメント識別子の考慮事項:ZSTDに指定されたフラグメント識別子の構文とセマンティクスは、 'application / zstd'に指定されている必要があります。

Security Considerations: See Section 8 of RFC 8878.

セキュリティ上の考慮事項:RFC 8878のセクション8を参照してください。

Contact: Refer to the author for the 'application/zstd' media type.

連絡先:「アプリケーション/ ZSTD」メディアタイプの作成者を参照してください。

Author/Change Controller: IETF

作成者/変更コントローラー:IETF

7.4. Dictionaries
7.4. 辞書

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.

進行中の作業には、特定の種類のデータの圧縮と解凍を最適化する辞書の開発が含まれます。このような公共の辞書の指定は、セクション3.1.1.1.3で説明されている予約範囲からのコードポイントの登録と、特定の辞書との関連付けを必要とします。

At present, there are no such dictionaries published for public use, so this document has made no immediate request of IANA to create such a registry.

現在のところ、公共の使用のために公開されている辞書はありませんので、この文書はそのようなレジストリを作成するためのIANAの即時要求を行っていません。

8. Security Considerations
8. セキュリティに関する考慮事項

Any data-compression method involves the reduction of redundancy in the data. Zstandard is no exception, and the usual precautions apply.

任意のデータ圧縮方法は、データ内の冗長性の低下を含む。zStandardは例外ではなく、通常の予防措置が適用されます。

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

デコーダは、許可されたメモリ範囲を超えて読み書きや書き込みなど、圧縮フレーム内で改ざんされているデータを検出していない種類のデータを検出して防止するための機能を実証する必要があります。これは実装言語または慎重なバインドチェックのいずれかによって保証されます。特に注意事項は、バッファオーバーフローをトリガしようとする試みで、デコーダをブロックヘッダ(およびそれ以降)に読み込むことを要求するNumber_of_Sequences値の符号化である。Fuzz-Test(すなわち、無効で予想外の入力およびランダムな入力および確信の安全な操作を提供する)デコーダの実装を、不良フレームを検出し、不利なシステム副作用なしでそれらに対処するために復活することを強く推奨されます。

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.

圧縮は、さまざまな関連コンテンツペイロードで辞書を訓練することによって最適化できます。この辞書は、ペイロードの解凍のためにデコーダで利用可能でなければならない。この文書では、特定の圧縮ペイロードの辞書を取得する方法は指定されていませんが、サードパーティの辞書がデコーダと対話する可能性があるため、メモリやその他のリソース - 排気攻撃をもたらすことが注目に値します。このようなトピックは、辞書の取得および送信のための次のRFCのセキュリティ上の考慮事項のセクションでさらに詳細に議論されることを期待していますが、この問題を今すぐ存在しなくなりました。

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.

3.1.2項で説明したように、スキップ可能なフレームに任意のユーザーメタデータを格納することが可能です。そのようなフレームはデータの解凍中に無視されますが、それらは圧縮ペイロードの経路を追跡するための透かしとして使用できます。

9. References
9. 参考文献
9.1. Normative References
9.1. 引用文献

[ZSTD] "Zstandard", <http://www.zstd.net>.

[zstd] "zStandard"、<http://www.zstd.net>。

9.2. Informative References
9.2. 参考引用

[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>.

[ANS] DUDA、J.、「非対称数値システム:算術符号化の圧縮率を用いたハフマン符号化のエントロピー符号化」、2014年1月、<https://arxiv.org/pdf/1311.2540>。

[CRIME] "CRIME", June 2018, <https://en.wikipedia.org/w/ index.php?title=CRIME&oldid=844538656>.

[犯罪]「犯罪」、2018年6月、<https://en.wikipedia.org/w/ index.php?title =犯罪&oldid = 844538656>。

[DICT-SEC] Handte, F., "Security Considerations Regarding Compression Dictionaries", Work in Progress, Internet-Draft, draft-handte-httpbis-dict-sec-00, 29 October 2019, <https://tools.ietf.org/html/draft-handte-httpbis-dict-sec-00>.

[DICT-SEC]ハンドテ、F。、「圧縮辞書に関するセキュリティ上の考慮事項」、進行中の作業、インターネットドラフト、ドラフト - HTTPBIS-DICT-SEC-00,2019、<https://tools.ietf.org / html / draft-handte-httpbis-dict-sec-00>。

[Err5786] RFC Errata, "Erratum ID 5786", RFC 8478, <https://www.rfc-editor.org/errata/eid5786>.

[ERR5786] RFCエラータ、「Erratum ID 5786」、RFC 8478、<https://www.rfc-editor.org/errata/eid5786>。

[Err6303] RFC Errata, "Erratum ID 6303", RFC 8478, <https://www.rfc-editor.org/errata/eid6303>.

[ERR6303] RFC正誤表、「Erratum ID 6303」、RFC 8478、<https://www.rfc-editor.org/errata/eid6303>。

[FSE] "FiniteStateEntropy", commit 12a533a, July 2020, <https://github.com/Cyan4973/FiniteStateEntropy/>.

[FSE] "FINITESTANTEROPY"、2020年7月、<https://github.com/cyan4973/FinitestateEntropy/>。

[LZ4] "LZ4 Frame Format Description", commit ec735ac, January 2019, <https://github.com/lz4/lz4/blob/master/doc/ lz4_Frame_format.md>.

[LZ4] "LZ4フレームフォーマットの説明"、2019年1月、<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>.

[RFC1952] Deutsch、P.、 "GZIPファイル形式仕様バージョン4.3"、RFC 1952、DOI 10.17487 / RFC1952、1996年5月、<https://www.rfc-editor.org/info/rfc1952>。

[XXHASH] "xxHash", <http://www.xxhash.org>.

[xxhash] "xxhash"、<http://www.xxhash.org>。

Appendix A. Decoding Tables for Predefined Codes
付録A.定義済みコードの復号化テーブル

This appendix contains FSE decoding tables for the predefined literals 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.

この付録には、事前定義されたリテラル長、一致する長さ、およびオフセットコードのFSEデコードテーブルが含まれています。テーブルは、4.1.1項で上記のようなアルゴリズムを使用して構築されています。ここでのテーブルは、実装がそのデコードテーブルを正しく構築したことをクロスチェックするための例として使用できます。

A.1. Literals Length Code Table
A.1. リテラル長コードテーブル
                +=======+========+================+======+
                | State | Symbol | Number_Of_Bits | Base |
                +=======+========+================+======+
                |   0   |   0    |       0        |  0   |
                +-------+--------+----------------+------+
                |   0   |   0    |       4        |  0   |
                +-------+--------+----------------+------+
                |   1   |   0    |       4        |  16  |
                +-------+--------+----------------+------+
                |   2   |   1    |       5        |  32  |
                +-------+--------+----------------+------+
                |   3   |   3    |       5        |  0   |
                +-------+--------+----------------+------+
                |   4   |   4    |       5        |  0   |
                +-------+--------+----------------+------+
                |   5   |   6    |       5        |  0   |
                +-------+--------+----------------+------+
                |   6   |   7    |       5        |  0   |
                +-------+--------+----------------+------+
                |   7   |   9    |       5        |  0   |
                +-------+--------+----------------+------+
                |   8   |   10   |       5        |  0   |
                +-------+--------+----------------+------+
                |   9   |   12   |       5        |  0   |
                +-------+--------+----------------+------+
                |   10  |   14   |       6        |  0   |
                +-------+--------+----------------+------+
                |   11  |   16   |       5        |  0   |
                +-------+--------+----------------+------+
                |   12  |   18   |       5        |  0   |
                +-------+--------+----------------+------+
                |   13  |   19   |       5        |  0   |
                +-------+--------+----------------+------+
                |   14  |   21   |       5        |  0   |
                +-------+--------+----------------+------+
                |   15  |   22   |       5        |  0   |
                +-------+--------+----------------+------+
                |   16  |   24   |       5        |  0   |
                +-------+--------+----------------+------+
                |   17  |   25   |       5        |  32  |
                +-------+--------+----------------+------+
                |   18  |   26   |       5        |  0   |
                +-------+--------+----------------+------+
                |   19  |   27   |       6        |  0   |
                +-------+--------+----------------+------+
                |   20  |   29   |       6        |  0   |
                +-------+--------+----------------+------+
                |   21  |   31   |       6        |  0   |
                +-------+--------+----------------+------+
                |   22  |   0    |       4        |  32  |
                +-------+--------+----------------+------+
                |   23  |   1    |       4        |  0   |
                +-------+--------+----------------+------+
                |   24  |   2    |       5        |  0   |
                +-------+--------+----------------+------+
                |   25  |   4    |       5        |  32  |
                +-------+--------+----------------+------+
                |   26  |   5    |       5        |  0   |
                +-------+--------+----------------+------+
                |   27  |   7    |       5        |  32  |
                +-------+--------+----------------+------+
                |   28  |   8    |       5        |  0   |
                +-------+--------+----------------+------+
                |   29  |   10   |       5        |  32  |
                +-------+--------+----------------+------+
                |   30  |   11   |       5        |  0   |
                +-------+--------+----------------+------+
                |   31  |   13   |       6        |  0   |
                +-------+--------+----------------+------+
                |   32  |   16   |       5        |  32  |
                +-------+--------+----------------+------+
                |   33  |   17   |       5        |  0   |
                +-------+--------+----------------+------+
                |   34  |   19   |       5        |  32  |
                +-------+--------+----------------+------+
                |   35  |   20   |       5        |  0   |
                +-------+--------+----------------+------+
                |   36  |   22   |       5        |  32  |
                +-------+--------+----------------+------+
                |   37  |   23   |       5        |  0   |
                +-------+--------+----------------+------+
                |   38  |   25   |       4        |  0   |
                +-------+--------+----------------+------+
                |   39  |   25   |       4        |  16  |
                +-------+--------+----------------+------+
                |   40  |   26   |       5        |  32  |
                +-------+--------+----------------+------+
                |   41  |   28   |       6        |  0   |
                +-------+--------+----------------+------+
                |   42  |   30   |       6        |  0   |
                +-------+--------+----------------+------+
                |   43  |   0    |       4        |  48  |
                +-------+--------+----------------+------+
                |   44  |   1    |       4        |  16  |
                +-------+--------+----------------+------+
                |   45  |   2    |       5        |  32  |
                +-------+--------+----------------+------+
                |   46  |   3    |       5        |  32  |
                +-------+--------+----------------+------+
                |   47  |   5    |       5        |  32  |
                +-------+--------+----------------+------+
                |   48  |   6    |       5        |  32  |
                +-------+--------+----------------+------+
                |   49  |   8    |       5        |  32  |
                +-------+--------+----------------+------+
                |   50  |   9    |       5        |  32  |
                +-------+--------+----------------+------+
                |   51  |   11   |       5        |  32  |
                +-------+--------+----------------+------+
                |   52  |   12   |       5        |  32  |
                +-------+--------+----------------+------+
                |   53  |   15   |       6        |  0   |
                +-------+--------+----------------+------+
                |   54  |   17   |       5        |  32  |
                +-------+--------+----------------+------+
                |   55  |   18   |       5        |  32  |
                +-------+--------+----------------+------+
                |   56  |   20   |       5        |  32  |
                +-------+--------+----------------+------+
                |   57  |   21   |       5        |  32  |
                +-------+--------+----------------+------+
                |   58  |   23   |       5        |  32  |
                +-------+--------+----------------+------+
                |   59  |   24   |       5        |  32  |
                +-------+--------+----------------+------+
                |   60  |   35   |       6        |  0   |
                +-------+--------+----------------+------+
                |   61  |   34   |       6        |  0   |
                +-------+--------+----------------+------+
                |   62  |   33   |       6        |  0   |
                +-------+--------+----------------+------+
                |   63  |   32   |       6        |  0   |
                +-------+--------+----------------+------+
        

Table 28: Literals Length Code

表28:リテラル長コード

A.2. Match Length Code Table
A.2. マッチ長コードテーブル
                +=======+========+================+======+
                | State | Symbol | Number_Of_Bits | Base |
                +=======+========+================+======+
                |   0   |   0    |       0        |  0   |
                +-------+--------+----------------+------+
                |   0   |   0    |       6        |  0   |
                +-------+--------+----------------+------+
                |   1   |   1    |       4        |  0   |
                +-------+--------+----------------+------+
                |   2   |   2    |       5        |  32  |
                +-------+--------+----------------+------+
                |   3   |   3    |       5        |  0   |
                +-------+--------+----------------+------+
                |   4   |   5    |       5        |  0   |
                +-------+--------+----------------+------+
                |   5   |   6    |       5        |  0   |
                +-------+--------+----------------+------+
                |   6   |   8    |       5        |  0   |
                +-------+--------+----------------+------+
                |   7   |   10   |       6        |  0   |
                +-------+--------+----------------+------+
                |   8   |   13   |       6        |  0   |
                +-------+--------+----------------+------+
                |   9   |   16   |       6        |  0   |
                +-------+--------+----------------+------+
                |   10  |   19   |       6        |  0   |
                +-------+--------+----------------+------+
                |   11  |   22   |       6        |  0   |
                +-------+--------+----------------+------+
                |   12  |   25   |       6        |  0   |
                +-------+--------+----------------+------+
                |   13  |   28   |       6        |  0   |
                +-------+--------+----------------+------+
                |   14  |   31   |       6        |  0   |
                +-------+--------+----------------+------+
                |   15  |   33   |       6        |  0   |
                +-------+--------+----------------+------+
                |   16  |   35   |       6        |  0   |
                +-------+--------+----------------+------+
                |   17  |   37   |       6        |  0   |
                +-------+--------+----------------+------+
                |   18  |   39   |       6        |  0   |
                +-------+--------+----------------+------+
                |   19  |   41   |       6        |  0   |
                +-------+--------+----------------+------+
                |   20  |   43   |       6        |  0   |
                +-------+--------+----------------+------+
                |   21  |   45   |       6        |  0   |
                +-------+--------+----------------+------+
                |   22  |   1    |       4        |  16  |
                +-------+--------+----------------+------+
                |   23  |   2    |       4        |  0   |
                +-------+--------+----------------+------+
                |   24  |   3    |       5        |  32  |
                +-------+--------+----------------+------+
                |   25  |   4    |       5        |  0   |
                +-------+--------+----------------+------+
                |   26  |   6    |       5        |  32  |
                +-------+--------+----------------+------+
                |   27  |   7    |       5        |  0   |
                +-------+--------+----------------+------+
                |   28  |   9    |       6        |  0   |
                +-------+--------+----------------+------+
                |   29  |   12   |       6        |  0   |
                +-------+--------+----------------+------+
                |   30  |   15   |       6        |  0   |
                +-------+--------+----------------+------+
                |   31  |   18   |       6        |  0   |
                +-------+--------+----------------+------+
                |   32  |   21   |       6        |  0   |
                +-------+--------+----------------+------+
                |   33  |   24   |       6        |  0   |
                +-------+--------+----------------+------+
                |   34  |   27   |       6        |  0   |
                +-------+--------+----------------+------+
                |   35  |   30   |       6        |  0   |
                +-------+--------+----------------+------+
                |   36  |   32   |       6        |  0   |
                +-------+--------+----------------+------+
                |   37  |   34   |       6        |  0   |
                +-------+--------+----------------+------+
                |   38  |   36   |       6        |  0   |
                +-------+--------+----------------+------+
                |   39  |   38   |       6        |  0   |
                +-------+--------+----------------+------+
                |   40  |   40   |       6        |  0   |
                +-------+--------+----------------+------+
                |   41  |   42   |       6        |  0   |
                +-------+--------+----------------+------+
                |   42  |   44   |       6        |  0   |
                +-------+--------+----------------+------+
                |   43  |   1    |       4        |  32  |
                +-------+--------+----------------+------+
                |   44  |   1    |       4        |  48  |
                +-------+--------+----------------+------+
                |   45  |   2    |       4        |  16  |
                +-------+--------+----------------+------+
                |   46  |   4    |       5        |  32  |
                +-------+--------+----------------+------+
                |   47  |   5    |       5        |  32  |
                +-------+--------+----------------+------+
                |   48  |   7    |       5        |  32  |
                +-------+--------+----------------+------+
                |   49  |   8    |       5        |  32  |
                +-------+--------+----------------+------+
                |   50  |   11   |       6        |  0   |
                +-------+--------+----------------+------+
                |   51  |   14   |       6        |  0   |
                +-------+--------+----------------+------+
                |   52  |   17   |       6        |  0   |
                +-------+--------+----------------+------+
                |   53  |   20   |       6        |  0   |
                +-------+--------+----------------+------+
                |   54  |   23   |       6        |  0   |
                +-------+--------+----------------+------+
                |   55  |   26   |       6        |  0   |
                +-------+--------+----------------+------+
                |   56  |   29   |       6        |  0   |
                +-------+--------+----------------+------+
                |   57  |   52   |       6        |  0   |
                +-------+--------+----------------+------+
                |   58  |   51   |       6        |  0   |
                +-------+--------+----------------+------+
                |   59  |   50   |       6        |  0   |
                +-------+--------+----------------+------+
                |   60  |   49   |       6        |  0   |
                +-------+--------+----------------+------+
                |   61  |   48   |       6        |  0   |
                +-------+--------+----------------+------+
                |   62  |   47   |       6        |  0   |
                +-------+--------+----------------+------+
                |   63  |   46   |       6        |  0   |
                +-------+--------+----------------+------+
        

Table 29: Match Length Code Table

表29:整合長コードテーブル

A.3. Offset Code Table
A.3. オフセットコードテーブル
                +=======+========+================+======+
                | State | Symbol | Number_Of_Bits | Base |
                +=======+========+================+======+
                |   0   |   0    |       0        |  0   |
                +-------+--------+----------------+------+
                |   0   |   0    |       5        |  0   |
                +-------+--------+----------------+------+
                |   1   |   6    |       4        |  0   |
                +-------+--------+----------------+------+
                |   2   |   9    |       5        |  0   |
                +-------+--------+----------------+------+
                |   3   |   15   |       5        |  0   |
                +-------+--------+----------------+------+
                |   4   |   21   |       5        |  0   |
                +-------+--------+----------------+------+
                |   5   |   3    |       5        |  0   |
                +-------+--------+----------------+------+
                |   6   |   7    |       4        |  0   |
                +-------+--------+----------------+------+
                |   7   |   12   |       5        |  0   |
                +-------+--------+----------------+------+
                |   8   |   18   |       5        |  0   |
                +-------+--------+----------------+------+
                |   9   |   23   |       5        |  0   |
                +-------+--------+----------------+------+
                |   10  |   5    |       5        |  0   |
                +-------+--------+----------------+------+
                |   11  |   8    |       4        |  0   |
                +-------+--------+----------------+------+
                |   12  |   14   |       5        |  0   |
                +-------+--------+----------------+------+
                |   13  |   20   |       5        |  0   |
                +-------+--------+----------------+------+
                |   14  |   2    |       5        |  0   |
                +-------+--------+----------------+------+
                |   15  |   7    |       4        |  16  |
                +-------+--------+----------------+------+
                |   16  |   11   |       5        |  0   |
                +-------+--------+----------------+------+
                |   17  |   17   |       5        |  0   |
                +-------+--------+----------------+------+
                |   18  |   22   |       5        |  0   |
                +-------+--------+----------------+------+
                |   19  |   4    |       5        |  0   |
                +-------+--------+----------------+------+
                |   20  |   8    |       4        |  16  |
                +-------+--------+----------------+------+
                |   21  |   13   |       5        |  0   |
                +-------+--------+----------------+------+
                |   22  |   19   |       5        |  0   |
                +-------+--------+----------------+------+
                |   23  |   1    |       5        |  0   |
                +-------+--------+----------------+------+
                |   24  |   6    |       4        |  16  |
                +-------+--------+----------------+------+
                |   25  |   10   |       5        |  0   |
                +-------+--------+----------------+------+
                |   26  |   16   |       5        |  0   |
                +-------+--------+----------------+------+
                |   27  |   28   |       5        |  0   |
                +-------+--------+----------------+------+
                |   28  |   27   |       5        |  0   |
                +-------+--------+----------------+------+
                |   29  |   26   |       5        |  0   |
                +-------+--------+----------------+------+
                |   30  |   25   |       5        |  0   |
                +-------+--------+----------------+------+
                |   31  |   24   |       5        |  0   |
                +-------+--------+----------------+------+
        

Table 30: Offset Code

表30:オフセットコード

Appendix B. Changes since RFC 8478
付録B. RFC 8478以降の変更

The following are the changes in this document relative to RFC 8478:

以下は、RFC 8478に対するこのドキュメントの変更です。

* Applied errata [Err5786] and [Err6303].

* 適用されたerrata [err5786]と[ERR6303]。

* Clarified forward compatibility regarding dictionaries.

* 辞書に関する前方互換性を明確にしました。

* Clarified application of Block_Maximum_Size.

* block_maximum_sizeの適用を明確にしました。

* Added structured media type suffix registration.

* 構造化メディアタイプサフィックス登録を追加しました。

* Clarified that the content checksum is always 4 bytes.

* コンテンツチェックサムは常に4バイトであることを明確にしました。

* Clarified handling of reserved and corrupt inputs.

* 予約および破損入力の処理を明確にしました。

* Added fragment identifier considerations to the media type registration.

* メディアタイプの登録にフラグメント識別子の考慮事項を追加しました。

Acknowledgments

謝辞

zstd was developed by Yann Collet.

ZSTDはYann Colletによって開発されました。

Felix Handte and Nick Terrell provided feedback that went into this revision and RFC 8478. RFC 8478 also received contributions from Bobo Bose-Kolanu, Kyle Nekritz, and David Schleimer.

Felix HandteとNick Terrellは、このリビジョンとRFC 8478に入ったフィードバックを提供しました.RFC 8478もBobo Bose-Kolanu、Kyle Nekritz、David Schleimerからの貢献を受けました。

Authors' Addresses

著者の住所

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

Yann Collet Facebook 1ハッカーウェイメンロパーク、CA 94025アメリカ

   Email: cyan@fb.com
        

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

Murray S. Kucherawy(編集)Facebook 1 Hacker Way Menlo Park、CA 94025アメリカ

   Email: msk@fb.com