Deflate压缩块的结构

Question

理解Deflate算法(RFC 1951)时遇到了麻烦.

TL; DR如何解析Deflate压缩块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 1 011.(我将跳过这个问题,为什么有人会称之为"标题"的东西实际上是其他东西的尾巴.)

RFC包含的东西,据我所知,应该是对此的解释:

• 数据元素按字节中的位数增加的顺序打包成字节,即从字节的最低有效位开始.
• 除了霍夫曼码之外的数据元素从数据元素的最低有效位开始打包.
• 霍夫曼代码从代码的最高位开始打包.

换句话说,如果要将压缩数据打印出来作为一个字节序列,从右边距的第一个字节开始, 然后向左移动,左边每个字节的最重要位像往常一样,将能够从右到左解析结果,其中固定宽度元素在正确的MSB到LSB顺序中,而霍夫曼代码以位反转顺序(即,相对LSB位置中的代码的第一位) .

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

回到我的数据.好的,所以设置了BFINAL,而BTYPE是什么？10或01？

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

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,表示这是压缩数据中的最后一个块.

BTYPE值存储在数据的后两位中.这些是上面标记为"第二位"和"第三位"的位.唯一的问题是两者中哪一位是最低有效位,哪一位是最重要的位.根据RFC,"除了霍夫曼代码之外的数据元素从数据元素的最低有效位开始打包." 这意味着这两个位中的第一位,即标记为"第二位"的位,是最不重要的位.这意味着BTYPE的值是01二进制的.因此表示使用固定的霍夫曼码压缩块.

这就是容易完成的部分.解码压缩块的其余部分更加困难(并且使用更现实的示例,更加困难).正确地解释这将如何使这个答案太久(并且你的问题太广泛)对于这个网站.我会给你一个提示,数据中接下来的三个元素是霍夫曼代码10010001('a'),00111010('\n')和0000000(流结束).其余6位未使用,不属于压缩数据.

请注意,要了解如何解压缩压缩数据,您必须了解Huffman代码是什么.您所遵循的RFC假设您这样做.您还应该知道LZ77压缩是如何工作的,尽管文档或多或少地解释了您需要知道的内容.