本教程深入探讨DEFLATE压缩数据流的手动解析过程，重点揭示了RFC1951规范中关于字节内位序（Least Significant Bit优先）这一常见陷阱。通过具体示例，文章演示了如何正确解读DEFLATE数据块的头部信息，如BFINAL和BTYPE，并强调了严格遵循官方规范的重要性，以避免解析错误。
DEFLATE压缩数据流概述
DEFLATE是一种广泛使用的无损数据压缩算法，其规范定义在RFC1951中。理解DEFLATE数据流的内部结构对于实现自定义解压缩器或进行调试至关重要。DEFLATE数据通常由一系列数据块组成，每个块都有其特定的头部信息，指示该块的类型和是否为数据流的最后一个块。
为了演示DEFLATE的解析过程，我们首先使用PHP的gzdeflate函数生成一个DEFLATE编码的字符串：
<?php
$result = gzdeflate('A_DEAD_DAD_CEDED_A_BAD_BABE_A_BEADED_ABACA_BED');
echo bin2hex($result);
?>上述代码将输出以下十六进制字符串： 1589c11100000cc166a3cc61ff2dca237709880c45e52c2b08eb043dedb78db8851e
我们的目标是手动解析这个字符串的起始部分，理解其结构。
DEFLATE数据块头部解析：位序陷阱
根据RFC1951 § 3.2.3 "Details of block format" 的描述，每个压缩数据块都以3个头部位开始，包含以下信息：
- 第一个位：BFINAL
- 接下来的两个位：BTYPE
其中，BFINAL位指示这是否是数据流的最后一个块，BTYPE则指定了数据块的压缩方式（00为无压缩，01为固定Huffman编码，10为动态Huffman编码，11为保留）。
在尝试解析上述十六进制字符串时，一个常见的错误是对字节内位序的误解。让我们以第一个字节0x15为例。0x15的二进制表示是0b00010101。
如果按照从高位到低位的常规阅读顺序，我们可能会错误地认为前三个位是000。这将导致BFINAL为0，BTYPE为00（无压缩）。然而，这与DEFLATE规范中一个关键但常被忽视的细节相悖。
核心纠正：RFC1951中的位序规则
RFC1951 § 3.1 "General Structure" 明确指出：
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. (数据元素按字节内位号递增的顺序打包，即从字节的最低有效位开始。)
这意味着在解析DEFLATE数据流时，我们应该从每个字节的最低有效位（LSB）开始读取。
正确解析示例
现在，让我们根据正确的位序规则重新解析第一个字节0x15 (0b00010101)：
- BFINAL (第一个位): 字节的最低有效位是1。因此，BFINAL = 1。这表示这是数据流的最后一个块。
- BTYPE (接下来的两个位): 接下来是字节的第1位和第2位。它们分别是0和1。组合起来是10。因此，BTYPE = 10。这表示该数据块使用动态Huffman编码进行压缩。
通过正确的位序解析，我们得出：BFINAL = 1，BTYPE = 10。这与原始问题中尝试的“无压缩块”的假设完全不同，也与实际的DEFLATE实现（如gzdeflate）的行为相符，因为动态Huffman编码是其常用模式。
如果忽略这一位序规则，后续对LEN/NLEN或Huffman编码的解析都将是错误的，导致解压失败。
DEFLATE数据块类型概览与处理流程
一旦正确解析了BFINAL和BTYPE，我们就可以根据BTYPE的值来决定后续的解析策略：
- BTYPE = 00 (无压缩块): 在这种情况下，会跳过当前字节中任何剩余的位，然后直接读取一个16位的LEN字段和其补码NLEN字段。紧接着是LEN字节的原始数据。
- BTYPE = 01 (固定Huffman编码块): 这种块使用RFC1951中预定义的固定Huffman码表进行压缩。解析器可以直接使用这些预定义码表来解码数据。
- BTYPE = 10 (动态Huffman编码块): 这是最复杂的类型。数据块的起始部分会包含用于构建两个Huffman码表（一个用于字面量/长度码，另一个用于距离码）的编码信息。解析器需要首先读取并构建这些码表，然后才能使用它们来解码实际的压缩数据。
我们示例中的数据流属于BTYPE = 10，这意味着接下来的字节将包含构建动态Huffman码表所需的信息。对这些信息的详细解析超出了本文的范围，但其基础仍然是严格遵循RFC1951中关于位序和字段结构的规定。
实践建议与注意事项
- 严格遵循RFC规范： DEFLATE的规范非常详细，任何对其中细节的忽视都可能导致解析错误。特别是位序问题，是初学者常犯的错误。
- 使用现有库进行验证： 在手动解析时，可以使用成熟的DEFLATE库（如zlib）或专门的调试工具（如infgen）来验证你的解析步骤是否正确。例如，infgen可以输出DEFLATE流的详细解析过程，帮助你理解每一步。
- 逐步调试： 对于复杂的动态Huffman块，建议从简单的固定Huffman块或无压缩块开始练习，逐步增加难度。
总结
DEFLATE数据流的手动解析是一项细致的工作，它要求开发者对RFC1951规范有深刻的理解。本文通过一个具体的示例，强调了在解析DEFLATE数据块头部时，严格按照“从字节的最低有效位开始读取”的位序规则的重要性。正确理解和应用这一规则是成功解析DEFLATE数据流的基础，避免了因位序误解而导致的解析错误。在处理DEFLATE数据时，务必牢记规范的每一个细节，并善用工具进行验证。
