本文深入探讨DEFLATE压缩数据格式的手动解析过程，重点纠正了初学者常犯的位序解读错误。通过详尽分析RFC1951规范，阐明了DEFLATE数据流中位和字节的正确读取顺序（LSB优先），并结合实际`gzdeflate`输出示例，演示如何准确识别数据块的BFINAL和BTYPE字段，从而为后续的块内容解析奠定基础。
深入理解DEFLATE数据格式
DEFLATE是一种广泛应用于ZLIB、GZIP和PNG等文件格式的无损数据压缩算法。理解其底层数据格式对于实现自定义解压缩器或进行调试至关重要。RFC1951是DEFLATE格式的官方规范，任何手动解析都必须严格遵循其规定。
一个常见的误区在于对数据流中位的读取顺序。许多人在处理字节时习惯于从最高有效位（MSB）开始读取，但在DEFLATE规范中，数据元素是按照“位号递增”的顺序打包到字节中的，即从最低有效位（LSB）开始。
位序规则：RFC1951的关键细节
RFC1951 § 3.2.1明确指出：“数据元素按照字节内位号递增的顺序打包到字节中，即从字节的最低有效位开始。”这意味着，当你读取一个字节时，首先遇到的是其最低位（bit 0），然后是bit 1，bit 2，依此类推。
例如，如果有一个字节 0x15，其二进制表示为 00010101。 我们通常将其视为 B7 B6 B5 B4 B3 B2 B1 B0，其中 B0 是最低有效位。 0x15 -> 00010101 即：B7=0, B6=0, B5=0, B4=1, B3=0, B2=1, B1=0, B0=1
根据RFC1951的规则，在读取DEFLATE数据流时，我们应按 B0, B1, B2, ... 的顺序提取位。
DEFLATE数据块头部解析
每个DEFLATE数据块都以一个3位的头部开始，这3位包含以下信息：
- 第一位 (BFINAL): 表示当前块是否是数据流的最后一个块。1 表示是最后一个块，0 表示后面还有更多块。
-
接下来的两位 (BTYPE): 指定数据块的压缩方式。
- 00 - 不压缩 (Stored block)
- 01 - 使用固定霍夫曼码压缩 (Fixed Huffman codes)
- 10 - 使用动态霍夫曼码压缩 (Dynamic Huffman codes)
- 11 - 保留 (错误)
让我们以一个实际的gzdeflate输出为例进行解析。
输出的十六进制字符串是 1589c11100000cc166a3cc61ff2dca237709880c45e52c2b08eb043dedb78db8851e。
我们关注第一个字节 0x15。
- 二进制表示: 0x15 转换为二进制是 00010101。
- 提取BFINAL: 按照LSB优先的规则，第一个位是 B0，即 1。 所以，BFINAL = 1。这表示这是数据流的最后一个块。
- 提取BTYPE: 接下来两位是 B1 和 B2。 B1 = 0B2 = 1 将它们组合起来（B2 B1）得到 10。 所以，BTYPE = 10。这表示该块使用动态霍夫曼码进行压缩。
因此，这个DEFLATE数据流的第一个（也是最后一个）块是一个使用动态霍夫曼码压缩的块。
非压缩块的解析误区与正确流程
原始问题中，用户假设 BTYPE=00（非压缩块），并尝试从接下来的字节中读取 LEN 和 NLEN。然而，基于正确的位序解析，我们已经确定 BTYPE 实际上是 10。
如果 BTYPE 确实为 00，解析流程如下：
- 忽略剩余位: 跳过当前部分处理字节中所有剩余的位，直到下一个字节边界。
- 读取LEN和NLEN: 接下来的两个字节是 LEN，再接下来的两个字节是 NLEN。LEN 是块中数据字节的数量，NLEN 是 LEN 的按位取反（一补数）。
- 复制数据: 紧随 NLEN 之后的是 LEN 字节的原始数据。
在用户原先的错误解读中，将 LEN 和 NLEN 视为两个 位，而非两个 字节，这是对规范的又一个误解。LEN 和 NLEN 都是16位无符号整数，占据两个字节。
总结与注意事项
- 严格遵循RFC1951: 在解析DEFLATE数据时，必须严格遵守RFC1951规范中的每一个细节，尤其是关于位和字节的读取顺序。
- LSB优先原则: DEFLATE中所有多位数据元素（如BFINAL、BTYPE、长度/距离码等）都是从最低有效位开始读取的。
- 工具辅助验证: 对于复杂的DEFLATE流，可以使用工具（如infgen，一个DEFLATE流反汇编器）来验证手动解析的结果。这些工具可以帮助你理解数据流的结构，并快速定位解析错误。
- 动态霍夫曼码的复杂性: 如果块类型是动态霍夫曼码，接下来的解析将涉及读取动态霍夫曼码表的定义，这比固定霍夫曼码或非压缩块要复杂得多。
理解并正确应用DEFLATE的位序规则是成功解析DEFLATE数据流的基础。任何对这一规则的误解都将导致后续解析的彻底失败。通过细致地对照规范并进行逐步分析，可以有效地避免此类错误。
