Skip to main content

3. Compression Algorithm (压缩算法)

本节描述 Zstandard 算法。

本文档的目的是定义一种无损压缩数据格式 (Lossless Compressed Data Format), 该格式 a) 独立于 CPU 类型、操作系统、文件系统和字符集, b) 适用于使用 Zstandard 算法的文件压缩以及管道和流式压缩 (Pipe and Streaming Compression)。本规范的文本假定读者具有位级别和其他原始数据表示方面的基本编程背景。

数据可以被生成或消费, 即使对于任意长的顺序呈现的输入数据流, 也只需使用先验有界的中间存储量 (A Priori Bounded Amount of Intermediate Storage); 因此, 它可以用于数据通信。该格式使用 Zstandard 压缩方法和可选的 xxHash-64 校验和方法 [XXHASH] 来检测数据损坏 (Data Corruption)。

本规范定义的数据格式不尝试允许对压缩数据进行随机访问 (Random Access)。

除非下面另有说明, 兼容的压缩器 (Compliant Compressor) 必须生成符合此处规范的数据集。但是, 它不需要支持所有选项。

兼容的解压缩器 (Compliant Decompressor) 必须能够解压缩至少一组符合此处规范的工作参数集。它也可以忽略信息性字段 (Informative Fields), 如校验和。每当它不支持压缩流中定义的参数时, 它必须产生明确的错误代码 (Unambiguous Error Code) 和相关的错误消息, 说明哪个参数不受支持。

本规范旨在供软件实现者用于将数据压缩为 Zstandard 格式和/或从 Zstandard 格式解压缩数据。Zstandard 格式由用可移植 C 语言编写的开源参考实现支持, 可在 [ZSTD] 获得。

3.1 Frames (帧)​

Zstandard 压缩数据由一个或多个帧 (Frames) 组成。每个帧都是独立的, 可以独立于其他帧进行解压缩。多个连接帧的解压缩内容是每个帧解压缩内容的连接。

为 Zstandard 定义了两种帧格式: Zstandard 帧和可跳过帧 (Skippable Frames)。Zstandard 帧包含压缩数据, 而可跳过帧包含自定义用户元数据 (Custom User Metadata)。

3.1.1 Zstandard Frames (Zstandard 帧)​

单个 Zstandard 帧的结构如下:

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

表 1: 单个 Zstandard 帧的结构

Magic_Number (魔数) : 4 字节, 小端格式 (Little-endian Format)。值: 0xFD2FB528。

Frame_Header (帧头部) : 2 到 14 字节, 详见第 3.1.1.1 节。

Data_Block (数据块) : 详见第 3.1.1.2 节。这是数据出现的地方。

Content_Checksum (内容校验和) : 可选的 32 位校验和, 仅在设置了 Content_Checksum_Flag 时存在。内容校验和是 XXH64() 哈希函数 [XXHASH] 以原始 (解码) 数据作为输入、种子为零摘要的结果。校验和的低 4 字节以小端格式存储。

魔数的选择是为了降低在任意文件开头找到它的概率。它避免了琐碎的模式 (0x00、0xFF、重复字节、递增字节等), 包含 ASCII 范围之外的字节值, 并且不映射到 UTF-8 空间, 所有这些都降低了它出现在文本文件顶部的可能性。

3.1.1.1 Frame Header (帧头部)​

帧头部的大小可变, 最小为 2 字节, 最大为 14 字节, 具体取决于可选参数。Frame_Header 的结构如下:

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

表 2: Frame_Header 的结构

(由于Section 3.1.1.1及其子章节内容过长, 详细的位字段描述、Window Descriptor、Dictionary_ID、Frame_Content_Size等技术细节请参见完整的RFC 8878文档)

注: Section 3 包含大量技术细节, 包括:

  • 3.1.1.2 Blocks (块结构)
  • 3.1.1.3 Compressed Blocks (压缩块, 包含 Literals 和 Sequences)
  • 3.1.1.4 Sequence Execution (序列执行)
  • 3.1.1.5 Repeat Offsets (重复偏移)
  • 3.1.2 Skippable Frames (可跳过帧)

完整的技术实现细节请参考 RFC 8878 原文: https://www.rfc-editor.org/rfc/rfc8878.txt

Last updated on