deflate 格式，尤其是动态霍夫曼编码

Question

我目前正在实现一个 png 阅读器，但我对数据的位顺序和一般格式感到困惑。

我无法访问 libpng、zlib 或类似软件。
请注意，我写的任何位串都是最高有效位在前。

根据 RFC1951 , "数据元素被打包 [...] 从最低有效位开始"

我的示例图像的第一个字节是:11101101
为了读取 header ，我颠倒了位顺序并得到:10110111

第一位是说这是最后一个区 block ，这是有道理的。接下来的 2 位是“01”，这是静态霍夫曼编码还是动态霍夫曼编码？ RFC 只提到它们是位，但没有提到它们的顺序或它们的数值。

假设动态霍夫曼编码， header 后面是 2 个霍夫曼字母表。然而，这些也是编码的。 0-15作为字面量，16重复前面的代码(3+后面的2位)次。我假设 17 和 18 重复文字 0 是否正确？

进一步的问题是:

• 我的理解是否正确？
• 我怎么知道字母编码结束和下一个开始？
• 与 header 位相比，字母表和实际压缩数据的位顺序是什么？

我想我不明白第 3.2.7 章的大部分内容...

Answer 1

除了霍夫曼代码外，不要反转位，只有在您的解码方法需要时才反转。 zlib 的膨胀从不反转这些位。 puff 保留位仅用于解码霍夫曼码。如果您尝试解释所有反转的位，您会感到困惑，并且您将不得不取消反转偏移位。

只需从底部读取位即可。

在您的示例中，11101101，底部位是 1，表示第一个 block 也是最后一个 block 。接下来的两位(未反转)10 表示这是一个动态 block 。

您可以使用 puff.c , 在 contrib/puff 目录中 zlib分发，作为 RFC 1951 的补充。puff.c 被编写为简单明了的 inflate 实现，以提供 deflate 格式的明确定义。