unix - Deflate压缩 block 的结构

Question

我在理解 Deflate 算法时遇到困难 ( RFC 1951 )。

TL; DR如何解析Deflate压缩 block 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 )。这两个对我来说没有任何麻烦。

但是我如何解释压缩 block 本身(中间线)？

这是它的十六进制和二进制表示:

4be4 0200

0100 1011
1110 0100
0000 0010
0000 0000

据我了解，不知何故这些:

Each block of compressed data begins with 3 header bits containing the following data:

• first bit BFINAL
• next 2 bits BTYPE

...实际上结束于第一个字节的末尾:0100 1011。 (我将跳过这个问题，为什么有人将实际上位于其他内容尾部的东西称为“标题”。)

据我所知，RFC 包含一些内容，应该是对此的解释:

• Data elements are packed into bytes in order ofincreasing bit number within the byte, i.e., startingwith the least-significant bit of the byte.
• Data elements other than Huffman codes are packedstarting with the least-significant bit of the dataelement.
• Huffman codes are packed starting with the most-significant bit of the code.

In other words, if one were to print out the compressed data asa sequence of bytes, starting with the first byte at theright margin and proceeding to the left, with the most-significant bit of each byte on the left as usual, one would beable to parse the result from right to left, with fixed-widthelements in the correct MSB-to-LSB order and Huffman codes inbit-reversed order (i.e., with the first bit of the code in therelative LSB position).

但遗憾的是我不明白这个解释。

返回我的数据。 OK，那么BFINAL就设置好了，那么BTYPE又是什么呢？ 10 还是 01？

如何解释该压缩 block 中的其余数据？

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

最后一位，即三十秒位，是这样的:

01001011 11100100 00000010 000000000
                           ^
                           last bit

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

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

这就是最容易完成的部分。解码压缩 block 的其余部分更加困难(并且对于更现实的示例，更加困难)。正确解释如何做到这一点将使这个答案对于本网站来说太长(并且您的问题太宽泛)。不过，我会给你一个提示，数据中接下来的三个元素是霍夫曼代码 10010001('a')、00111010('\n')和 0000000(流结束)。剩余的 6 位未使用，并且不是压缩数据的一部分。

请注意，要了解如何解码 deflate 压缩数据，您必须了解什么 Huffman codes是。您正在遵循的 RFC 假设您这样做。您还应该知道如何LZ77 compression有效，尽管该文档或多或少解释了您需要了解的内容。