本文深入探讨deflate压缩数据格式的手动解析过程，重点纠正了rfc1951规范中关于位序的常见误解。我们将通过一个实际案例，详细演示如何根据规范，以最低有效位优先的原则正确解读deflate数据流的头部信息，并初步了解动态霍夫曼编码块的结构，从而帮助读者避免在低级别数据解析中常犯的错误，提升对deflate机制的理解。
DEFLATE压缩数据格式概述
DEFLATE是一种广泛使用的无损数据压缩算法，其核心思想是结合LZ77算法和霍夫曼编码。DEFLATE数据流由一系列独立的块（block）组成，每个块可以采用不同的压缩方式。理解这些块的结构和解析规则是实现DEFLATE解码器的基础。
根据RFC1951规范，每个压缩数据块都以3个头部比特开始，包含以下信息：
- BFINAL (1 bit): 如果这是数据集中最后一个块，则设置为1；否则为0。
-
BTYPE (2 bits): 指定数据压缩类型。
- 00 - 不压缩（stored）
- 01 - 使用固定霍夫曼码压缩
- 10 - 使用动态霍夫曼码压缩
- 11 - 保留（错误）
关键：DEFLATE中的位序规则
在解析DEFLATE数据流时，最容易出错但又至关重要的一点是其位序（bit order）规则。RFC1951 § 3.2.1 明确指出：
Data elements are packed into bytes in order of increasing bit number within the byte, i.e., starting with the least-significant bit of the byte. (数据元素按字节内位号递增的顺序打包，即从字节的最低有效位开始。)
这意味着在读取一个字节时，我们应该首先读取最低有效位（LSB），然后依次是次低有效位，直到最高有效位（MSB）。这与许多人直观上习惯的从MSB开始读取的顺序是相反的。
实际案例分析：DEFLATE头部解析
让我们以一个具体的DEFLATE编码字符串 1589c1... 为例，来演示正确的头部解析过程。
原始的十六进制数据为 1589c11100000cc166a3cc61ff2dca237709880c45e52c2b08eb043dedb78db8851e。 第一个字节是 0x15。将其转换为二进制表示为 0b00010101。
根据RFC1951的位序规则，我们应该从最低有效位开始读取：
- 第一个比特 (BFINAL): 0b0001010**1** -> 1。这表示 BFINAL = 1，即这是数据流中的最后一个块。
- 接下来的两个比特 (BTYPE): 0b00010**10**1 -> 10 (读取顺序是 Bit 1 -> Bit 2，即 0 然后 1)。这表示 BTYPE = 10，即该块使用动态霍夫曼码进行压缩。
因此，正确的头部解析结果是：
- BFINAL = 1 (最后一个块)
- BTYPE = 10 (动态霍夫曼编码)
这与最初假设的 BFINAL=0, BTYPE=00 (不压缩) 完全不同，也解释了为何后续按“不压缩”块解析会遇到LEN/NLEN不匹配的问题。
动态霍夫曼编码块的后续结构
由于我们的示例块类型是 BTYPE=10 (动态霍夫曼编码)，它不会像 BTYPE=00 (不压缩) 块那样直接跟着LEN/NLEN和原始数据。动态霍夫曼编码块的结构更为复杂，它首先包含用于构建霍夫曼码表的元数据，然后才是实际的压缩数据。
一个动态霍夫曼编码块的结构大致如下：
- 头部 (BFINAL, BTYPE)
-
动态霍夫曼码表描述:
- HLIT (5 bits): 字面量/长度码的码长数量 - 257 (257-286)
- HDIST (5 bits): 距离码的码长数量 - 1 (1-32)
- HCLEN (4 bits): 码长码的码长数量 - 4 (4-19)
- 码长码的码长序列: 按照特定顺序 (16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15) 读取 HCLEN 个码长，用于构建码长码的霍夫曼树。
- 字面量/长度码的码长序列: 使用上述码长码的霍夫曼树解码，得到 HLIT 个字面量/长度码的码长。
- 距离码的码长序列: 使用上述码长码的霍夫曼树解码，得到 HDIST 个距离码的码长。
-
压缩数据: 使用上述构建的字面量/长度霍夫曼树和距离霍夫曼树来解码实际的压缩数据，包括：
- 字面量 (Literal): 直接输出原始字节。
- 长度/距离对 (Length/Distance Pair): 表示从输出历史中复制一段数据。长度码指示要复制的字节数，距离码指示从当前位置回溯多少字节。
以提供的 infgen 输出为例，它确认了我们的解析：
- last 对应 BFINAL=1。
- dynamic 对应 BTYPE=10。
- count 259 10 16 对应 HLIT=259-257=2, HDIST=10-1=9, HCLEN=16-4=12。这表明该块定义了259个字面量/长度码，10个距离码，以及16个码长码。
- 后续的 code 和 lens 定义了这些霍夫曼树的结构。
- 最后的 literal 和 match 指令则展示了实际的解压缩操作：
- literal 'A_DEAD_D：直接输出字面量。
- match 3 4：表示从当前输出位置向前回溯4个字节，复制3个字节。
注意事项与总结
- 严格遵守规范： 在处理低级别数据格式（如DEFLATE）时，务必严格遵循其官方规范（RFC1951）。任何对位序、字节序或数据结构的误解都可能导致解码失败。
- 位序优先： DEFLATE的位序规则是“最低有效位优先”。这是理解其头部和后续数据结构的关键。
- 调试工具： 当手动解析遇到困难时，使用如 infgen 这样的专业工具来验证中间步骤和最终结果是极其有用的。它们可以帮助你发现解析逻辑中的错误。
- 逐步验证： 在实现解码器时，建议分阶段进行：先正确解析头部，然后是码表元数据，最后才是实际压缩数据。每一步都进行验证，确保正确性。
通过理解并正确应用DEFLATE的位序规则，我们能够准确地解析压缩数据流的头部信息，并为后续的霍夫曼解码奠定坚实的基础。这是掌握DEFLATE解压缩技术的关键一步。
