Zstandard压缩格式规范分析文档-夜雨聆风

Zstandard压缩格式规范分析文档

Zstandard (zstd) 是一种快速无损压缩算法，其压缩格式规范定义了一种独立于CPU类型、操作系统、文件系统和字符集的压缩数据格式，适用于文件压缩、管道和流压缩。

格式特性

1. 格式设计原则

•跨平台兼容：独立于CPU类型、操作系统、文件系统和字符集

•流式处理：支持任意长的顺序输入数据流处理

•内存效率：使用预先限定的中间存储空间

•数据完整性：可选的xxHash-64校验和用于检测数据损坏

2. 基本结构

Zstandard格式由一个或多个帧组成，每个帧独立且可单独解压缩：

Zstandard帧结构：[魔数] [帧头] [数据块…] [内容校验和(可选)]

帧格式详解

1. Zstandard帧结构

魔数(Magic Number)

•4字节，小端格式

•值：0xFD2FB528

•设计目的是减少与随机文件开头冲突的概率

帧头(Frame Header)

可变大小（2-14字节），包含：

•帧头描述符(1字节)

•窗口描述符(0-1字节)

•字典ID (0-4字节)

•帧内容大小(0-8字节)

2. 帧头字段解析

帧头描述符字段

位7-6: Frame_Content_Size_flag (内容大小标志)位5: Single_Segment_flag (单段标志)位4: Unused_bit (未使用位)位3: Reserved_bit (保留位)位2: Content_Checksum_flag (内容校验和标志)位1-0: Dictionary_ID_flag (字典ID标志)

窗口描述符(Window Descriptor)

提供解压缩所需的最小内存缓冲区保证：

windowLog = 10 + Exponent;windowBase = 1 << windowLog;windowAdd = (windowBase / 8) * Mantissa;Window_Size = windowBase + windowAdd;

块格式详解

1. 块结构

|块头(3字节) | 块内容(n字节) |

块头字段

位0: Last_Block (最后块标志)位1-2: Block_Type (块类型)位3-23: Block_Size (块大小)

块类型

•Raw_Block (0)：未压缩块

•RLE_Block (1)：行程长度编码块

•Compressed_Block (2)：压缩块

•Reserved (3)：保留类型

2. 压缩块结构

压缩块包含两个部分：

•字面量部分(Literals Section)：存储原始数据

•序列部分(Sequences Section)：存储压缩指令

字面量部分详解

1. 字面量部分头部

字面量块类型

•Raw_Literals_Block (0)：未压缩字面量

•RLE_Literals_Block (1)：行程编码字面量

•Compressed_Literals_Block (2)：压缩字面量（含树描述）

•Treeless_Literals_Block (3)：压缩字面量（复用前一棵树）

2. 压缩字面量处理

•使用霍夫曼前缀编码

•支持1个或4个流

•包含霍夫曼树描述（仅Compressed_Literals_Block）

序列部分详解

1. 序列部分结构

序列部分头部

包含：

•序列数量(1-3字节)

•符号压缩模式(1字节)

压缩模式

•Predefined_Mode (0)：预定义FSE分布表

•RLE_Mode (1)：行程编码模式

•FSE_Compressed_Mode (2)：标准FSE压缩

•Repeat_Mode (3)：重复前一个表

2. 代码系统

字面量长度代码(0-35)

支持0到131071字节的长度编码，使用基线值+额外位数的方式。

匹配长度代码(0-52)

支持3到131074字节的长度编码。

偏移代码(0-N)

支持回溯引用距离，最大可达(2^(N+1))-4字节。

序列执行

1. 序列解码过程

每个序列包含三元组(literals_length, offset_value, match_length)：

1.复制字面量长度字节到输出

2.从前文复制匹配长度字节

3.更新重复偏移历史

2. 重复偏移机制

•Repeated_Offset1：最近的偏移

•Repeated_Offset2：第二近的偏移

•Repeated_Offset3：第三近的偏移

特殊的偏移值1-3表示重复偏移：

•偏移值1 → Repeated_Offset1

•偏移值2 → Repeated_Offset2

•偏移值3 → Repeated_Offset3

词典格式

1. 词典结构

|魔数 | 词典ID | 熵表 | 内容 |

熵表顺序

•字面量霍夫曼表

•偏移FSE表

•匹配长度FSE表

•字面量长度FSE表

•3个偏移值（最近偏移）

2. 词典使用

•词典ID用于验证正确词典

•词典内容作为“过去”数据供引用

•支持预训练的分布表

跳过帧(Skippable Frames)

1. 跳过帧结构

|魔数(4字节) | 帧大小(4字节) | 用户数据(n字节) |

魔数值范围

0x184D2A50 到 0x184D2A5F，共16个有效值。

熵编码技术

1. FSE (有限状态熵)

•基于ANS (非对称数值系统)

•支持自适应概率模型

•高效的状态转移机制

2. 霍夫曼编码

•用于压缩字面量

•支持权重描述

•限制最大代码长度为11位

实现考虑

1. 内存管理

•窗口大小限制解压缩内存需求

•建议支持至少8MB内存分配

•防止不合理内存需求

2. 兼容性

•向后兼容性保证

•版本间格式稳定性

•RFC8878标准化

3. 性能优化

•流式处理支持

•随机访问限制（设计决定）

•高效的解压缩算法

安全特性

1. 数据完整性

•可选的内容校验和

•基于xxHash-64的哈希函数

•错误检测和报告机制

2. 错误处理

•非歧义错误代码

•详细的错误消息

•参数验证机制

总结

Zstandard格式规范定义了一个功能丰富、高效且安全的压缩格式，支持多种压缩模式、词典压缩、流式处理等高级特性。其精心设计的格式结构平衡了压缩效率、解压缩速度和实现复杂度，使其成为现代压缩算法的理想选择。规范的详细描述为不同平台和语言的实现提供了清晰的指导，确保了跨实现的兼容性。