尝试理解PNG文件中的zlib/deflate压缩技术

Question

我目前正在为了学习目的编写一个小型PNG图像I/O库。我的问题如下：

我创建了一个仅有2x2像素的小PNG图像，并在十六进制编辑器中打开以研究其内容。这是我使用GIMP创建并用"9"压缩存储的图像。

（请注意，这是原始2x2像素图像的放大图像 ;) ）

我猜测未压缩的话，这在内存中会长成这个样子：

00 00 00 FF 00 00 00 00 FF 00 FF 00

没有 alpha 通道时存储。

（我在这里只是为了清晰起见说明。我知道压缩，并没有期望在文件中看到这个字节模式）。

我提取了 IDAT 块并去掉了块标识符（“IDAT”）和尾部的 CRC 值，得到了这个字节序列：

08 D7 05 C1 01 01 00 00 00 80 10 FF 4F 17 10 48 06 0F FE 02 FE

现在，前两个字节08 D7包含编码块的信息。最后四个字节0F FE 02 FE必须是ADLER32校验和。

这最终让我得到以下字节：

05 C1 01 01 00 00 00 80 10 FF 4F 17 10 48 06

用二进制表示，这些字节是：

0000 0101  1100 0001  0000 0001  0000 0001
0000 0000  0000 0000  0000 0000  1000 0000
0001 0000  1111 1111  0100 1111  0001 0111
0001 0000  0100 1000  0000 0110

为了更好地理解DEFLATE，我试图手动“解压”这个序列，至少在我足够理解它以编写一个小工具之前。但是我很快就卡住了。

RFC 1951（“DEFLATE压缩数据格式规范”）指出，每个编码块都以三位头开始。一位表示这是否是最后一个块，另外两个块表示压缩方法。由于我假设编码器仅使用一个块（意味着第一个块自动是最后一个），并使用非静态Huffmann树，因此我正在寻找位序列“101”，但我找不到它（也没有找到其他可能的标题“100”或“110”）。

此外，RFC还指出，必须有两个两字节值LEN和NLEN存储块的长度，其中NLEN是LEN的一补数，但是我仍然无法找到满足此条件的四个字节。我甚至不会开始寻找任何可能代表两个Huffmann树的东西。

我阅读了RFC 1951和1950（"ZLIB压缩数据格式规范"），以及有关zlib、DEFLATE、LZ77和Huffman编码的维基百科文章，还有一些网上的小而不太有用的文章和一些Stack Overflow上的答案，但都无法帮助我理解。

如果能得到任何帮助或提示，我将非常感激！

- Rafael Pasquay

Answer 1

如果有帮助的话，这里是IDAT块内容的反汇编：

! infgen 2.2 output
!
zlib
!
last
dynamic
count 257 2 18
code 1 1
code 2 2
code 18 2
lens 1
zeros 138
zeros 116
lens 2 2 1 1
! litlen 0 1
! litlen 255 2
! litlen 256 2
! dist 0 1
! dist 1 1
literal 0 0 0 0 255 0 0 0 0 0 255 0 255 0
end
!
adler

你可以在这里获取 infgen 的源代码：http://zlib.net/infgen.c.gz。

- Mark Adler

---

底部是签名还是确认最后两个单词已正确编码？ - Jongware

这不是确认，而只是一个声明，即在Adler-32应该存在的地方有四个字节。 infgen不会计算未压缩数据的校验值以查看其是否正确。 - Mark Adler

Answer 2

我认为您忽略了位如何在字节中打包的问题（请参阅例如RFC的3.1.1节）。

 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.

因此，如果第一个字节为05 = 0000 0101，则第一位为1。

（顺便说一下，这么详细地查看事物肯定很有启发性，但是如果你的目的是理解PNG，我想你可能走得有点太远了。）

此外，当您到达找到未压缩的IDAT流的点时，请记住像素使用每行五个filters之一进行编码，并且每行开头有一个额外的字节，用于信号过滤器类型。因此，您实际上不会找到原始的12个字节00 00 00 FF 00 00 00 00 FF 00 FF 00，而是14个字节。

- leonbloy

---

谢谢你的回答。你说得对，我没有考虑字节内部的位顺序。我知道过滤器，并且只包括这个小例子来展示在解压和去除过滤器后我期望得到什么结果；-）...其实也可以把这段代码省略掉。 - Rafael Pasquay

现在我们已经有了头文件。我对以下的零表示第一个哈夫曼树的理解是正确的吗？（顺便说一下，这非常低级，我肯定不会在另一种图像格式上再做一次，但我至少想要理解在这个层面上发生了什么；-)）。 - Rafael Pasquay

如果您想要详细的解释，我推荐访问http://www.amazon.com/Compressed-Image-File-Formats-JPEG/dp/0201604434/ref=pd_sim_b_1?ie=UTF8&refRID=05VHZ02D8BR9MJCQNK3W。 - user3344003

我不确定，我不是deflate的专家，也许你应该为此提出一个新问题（记住：这不是聊天论坛）。在这里，您可以从真正的专家那里获得答案，例如Adler先生本人 :-) http://stackoverflow.com/users/1180620/mark-adler - leonbloy

对你来说，应该称呼我为阿德勒博士。 - Mark Adler