logo标签列表

压缩规范Deflate的澄清解释

c++binaryzlibhuffman-codedeflate
4
我的希望是在这个问题中（见：底部）尽可能地阐述我对压缩过程的了解，并且我可以在我知识存在偏差的领域接受更正。希望最终，这个问题可以成为一个方便的资源。
Zlib头
前两个字节等同于zlib压缩的头，与格式为（来源：credit）。
---CMF---  ---FLG---
0111.1000  1101.0101
CINF -CM-  +-||
           | |+- FCHECK
           | +-- FDICT
           +---- FLEVEL

根据RFC 1950，从右到左：

  1. FCHECK（1.0101）- 验证CMF和FLG作为16位无符号整数是否为31的倍数

  2. FDICT（0）- 如果设置，则表示FLG后紧接着包含预设字典

  3. FLEVEL（11） - 压缩“强度”[0-3]

  4. CM（1000）- 压缩方法，其中CM=8==“deflate”压缩方法

  5. CINF（0111）- 指示所使用的滑动窗口的大小，其中CINF=7==32K滑动窗口

数据块头

新字节中的下三位相当于Huffman编码块的标头：

---CMF---  ---FLG---  NEW BYTE
0111.1000  1101.0101  11101100
                           |-|
                           | +- BFINAL
                           +--- BTYPE

从右到左，根据RFC 1951：

  1. BFINAL（0）- 如果这是最后一个数据块，则设置为（1）

  2. BTYPE（10）- 哈夫曼编码：（00）无; （01）固定哈夫曼码; （10）动态码; （11）无效

哈夫曼编码

从这里开始，我将假设BTYPE =（10）

以下值立即进行：

NEW BYTE                NXT BYTE                  
(11101)100       ->     101)(11101)   ->   0111111(1
       |-|
       | +- BFINAL
       +--- BTYPE

  1. HLIT (11101) - 257个长度/字面量编码的5位数字（257-286）

  2. HDIST (11101) - 1个距离编码的5位数字（1-32）

  3. HCLEN (1111) - 4个代码长度编码的4位数字（4-19）

在此之后，是HCLEN（不要忘记+4）3位字段，其中的值按顺序分配给此序列：

16 17 18 0 8 7 9 6 10 5 11 4 12 3 13 2 14 1 15

自从HCLEN = 19以来，整个序列都被使用了。
在该序列中，代码长度为0意味着相应的符号未被使用。
作为一个图形示例，在读取19x3位后，我们有六个额外的位（括号内的额外位）：
NXT BYTE 00000000 00000000 00000000 00000000 00000000 00000000 [000000](00

我的问题

上面括号里的最后几位会被忽略吗？

我不会点踩，但我对这个问题的价值有所怀疑。1）它与PNG无关，而是与ZLIB/deflate规范有关（PNG使用ZLIB/deflate在这里是无关紧要的——“解耦层”的概念对于工程至关重要）。2）这不是一个真正具体的问题，而是一种寻求帮助以理解ZLIB/deflate格式细节的呼吁，使用一个特殊的例子（这几乎不会帮助其他人）。3）如果你不了解霍夫曼压缩，那么假装以位为单位理解ZLIB流可能有些奇怪（尽管也许值得赞扬）。 - leonbloy
我认为在这个领域理解某些东西的定义就是能够编写代码，例如编写一个解码器。但我会强调问题的价值，它是一个真正掌握字节级文件 I/O 甚至到单个位的绝佳练习。这也涉及了大小端性。作为一名大学受过教育的计算机科学专业学生，我在所有这些领域都比较薄弱。也许问题标题不正确，能否更改呢？如果可以的话应该改成什么样子呢？至于我包含 PNG 的（可能不好的）逻辑是，搜索 deflate 的大量内容自然会涉及到 PNG。我认为这是很好学习的东西。 - Trés DuBiel
@leonbloy，在我看来，Stack Overflow 最好的特点之一就是那些真正深入的回答，它们能够消除任何困惑并阐述最佳的 X 处理方式。我正在尝试从社区中模仿或引发这样的回答。 - Trés DuBiel
这是一个很好的练习，我完全同意！寻求对于如此好的练习的帮助并不等同于提出一个好问题（或许，我不确定）。"我将按原样发布，去阅读有关哈夫曼编码的资料，然后进行相应更新。" 对于一个技术博客文章来说，这是有用的内容。但这并不完全符合本站的理念：针对具体问题给出具体答案。 - leonbloy
1
@MarcusJ 我最初做这些是因为我在学习PNG文件。 IDAT块的结构与我上面展示的完全相同。从zlib头开始，然后是数据块头，接着是哈夫曼编码，最后是编码数据。你的第一个字节“0x78”与我的示例完全相同（包含CINF和CM的CMF字节）。 - Trés DuBiel
显示剩余3条评论
1个回答
7
不。在压缩流中，只有当遇到存储块（00）或者读取了最后一个块的结束码时才需要跳过位以达到字节边界。在读取完用于编码长度的位后，你需要使用生成的哈夫曼编码来继续读取后续位以获取编码长度。
感谢您的回复，Adler博士。我发现了您的puff.c程序，并从构造函数中借用了一部分内容。即，在测试过度订阅/不完整的长度集的部分，在构建第一个树（代码长度代码）时，在我测试过的五个图像上返回负值。这是为什么呢？我测试的图像来自于gimp（创建）或者互联网（下载）。它们都有BTYPE为2，并且我按照上述描述读取了值。我还与puff.c进行了交叉检查，确保我正在读取正确的位。再次感谢。 - Trés DuBiel
你可能没有读取正确的位，或者你没有正确解释它们。 - Mark Adler
谢谢，我会检查我的实现。 - Trés DuBiel
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接