Deflate压缩块的结构

Question

我在理解Deflate算法（RFC 1951）时遇到了困难。

简短概述：如何解析压缩块4be4 0200？

我创建了一个包含字母和换行符a\n的文件，并运行gzip a.txt。生成的文件为a.txt.gz：

1f8b 0808 fe8b eb55 0003 612e 7478 7400

4be4 0200

07a1 eadd 0200 0000

我理解第一行是头部附加信息，最后一行是输入的CRC32和大小（RFC 1951）。这两个对我来说没有问题。

但是我该如何解释压缩块本身（中间那一行）？

以下是它的十六进制和二进制表示：

4be4 0200

0100 1011
1110 0100
0000 0010
0000 0000

据我理解，以下这些部分：

每个压缩数据块都以3位头部比特开始，包含以下数据：

• 第一位 BFINAL
• 接下来的2位 BTYPE

实际上是以以下的方式结束于第一个字节的结尾：0100 1011。（我跳过了为什么把实际上在其他地方结尾的东西称为“头部”的问题。）

RFC文档中包含了一些内容，据我理解应该是对此进行解释的：

• 数据元素按照字节中递增的位序打包，即从字节的最低有效位开始。
• 不是Huffman代码的数据元素，按照数据元素的最低有效位开始打包。
• Huffman代码按照代码的最高有效位开始打包。

换句话说，如果将压缩数据作为字节序列打印出来，则从右边开始，按顺序排列每个固定宽度元素和反转编码顺序的Huffman代码（即代码的第一个比特位于相对LSB位置）。每个字节的最高有效位仍在左侧，因此可以从右向左解析结果。

但是遗憾的是，我无法理解这个解释。

回到我的数据。好的，那么BFINAL已经设置了，BTYPE是什么？10还是01？

我如何解释压缩块中其余的数据？

- EugZol

---

你的数据不仅仅是字母'a'。它是字母'a'后面跟着换行符'\n'或十进制10。所以其中编码了两个字节，而不仅仅是一个字节。 - Mark Adler

@MarkAdler 感谢您指出这一点。 - EugZol

你可以使用infgen，一个deflate流反汇编器，来帮助你理解RFC 1951。流的反汇编成可读的描述以及infgen.c代码本身进一步说明了deflate格式的构建。 - Mark Adler

@MarkAdler 那个程序非常有帮助。你可以将链接添加为答案。虽然从正式意义上讲它并没有直接回答我的问题，但它是相关的且非常有用。我不会更改已接受的答案，但我一定会给你点赞。 - EugZol

Answer 1

首先，让我们将压缩数据的十六进制表示形式作为一系列字节来查看（而不是像您的问题中一样作为一系列16位大端值）：

4b e4 02 00

现在让我们将这些十六进制字节转换为二进制：

01001011 11100100 00000010 000000000

根据RFC，比特被打包“从字节的最低有效位开始”。字节的最低有效位是字节的最右边的位。因此，第一个字节的第一个比特是这个：

01001011 11100100 00000010 000000000
       ^
       first bit

第二个比特是这个：

01001011 11100100 00000010 000000000
      ^
      second bit

第三位：

01001011 11100100 00000010 000000000
     ^
     third bit

接下来的步骤类似。当你处理完第一个字节中的所有位后，就开始处理第二个字节中最低位的位（即第九位）。

01001011 11100100 00000010 000000000
                ^
                ninth bit

最后一位，即第32位，是这个：

01001011 11100100 00000010 000000000
                           ^
                           last bit

BFINAL值是压缩数据中的第一个比特，因此包含在上面标记为“第一位”的单个比特中。它的值为1，表示这是压缩数据中的最后一个块。

BTYPE值存储在数据的接下来两个比特中。这些是上面标记为“第二位”和“第三位”的比特。唯一的问题是哪个比特是最低有效位，哪个是最高有效位。根据RFC，“除Huffman代码以外的数据元素从数据元素的最低有效位开始打包。”这意味着这两个比特中的第一个比特，即标记为“第二位”的比特，是最低有效位。这意味着BTYPE的值是01，以二进制表示，因此指示该块使用固定的Huffman代码进行压缩。

而这只是容易的部分。解码压缩块的其余部分更加困难（并且使用更实际的示例会更加困难）。适当地解释如何做这将使本答案变得太长（并且您的问题也太广泛），不适合在此网站上回答。不过我可以给你一个提示，数据中的下一个三个元素是Huffman代码10010001（'a'），00111010（'\n'）和0000000（流结束）。剩余的6个比特未使用，并且不是压缩数据的一部分。

请注意，要理解如何解码deflate压缩数据，您需要了解什么是Huffman代码。您遵循的RFC假定您已经知道。您还应该了解LZ77压缩是如何工作的，尽管该文档或多或少地解释了您需要知道的内容。

- Ross Ridge

---

非常感谢！这就可以了。但是为什么头部位于最右边的位置？我自己在编程语言中实现的BitStream会有一些麻烦从那里取出它们，如果它们位于最左边的位置，则可以避免这种情况。这对其他工具更方便吗？ - EugZol

@EugZol 这取决于你的观点。头部位从数据的第一个比特开始。数据的第一个比特是第一个字节的第一个比特。字节中的比特按最不重要的比特优先和最重要的比特最后的顺序排序。这与我们通常排序数字的方式相同，最小值数字在前，最大值数字在后。问题在于，我们将数字的数字写反了，我们将数字的最高有效数字放在第一位，最低有效数字放在最后。如果我们尝试从左到右读取它们，这会翻转二进制数字的顺序。 - Ross Ridge

@EugZol 不管你怎么看待这个问题，提取位应该不会更加困难。在 C 中，你可以像这样做：bit = byte & 1; byte >>= 1;。如果位被提取的方式符合你的预期，即从字节的最右边和最高有效位开始，那么你需要做的是 bit = (byte >> 7) & 1; byte <<= 1;。 - Ross Ridge

@EugZol 大多数人都是反向阅读数字。如果你仔细想一下，12 应该是二十一，而 21 应该是十二。12 应该是二十一，因为首先你看到的是一个一，然后应该随着每个后续数字增加位值。每当我们阅读数字时，实际上是跳过数字末尾，反向阅读它们。 - Nick Sotiros

@EugZol：「来回跳跃」的问题基本上与字节序相同。你在问题中引用的RFC解释了如何对字节和位进行排序，以便一切都有意义：换句话说，如果将压缩数据作为字节序列打印出来，从右边界开始，向左移动第一个字节。如果您使用从左到右但每个字节内的位顺序从MSB到LSB的“传统”十六进制转储工具，则会遇到非常类似于混合字节序的问题。如果您使用小端位序转储，则会匹配字节顺序。 - Peter Cordes