zlib 的算法与接口

从八个字节开始，搭起压缩与解压的过程。

字面量与回引用

看一眼这个字符串：ABABABAB。

直接发送它，需要八个字节。另一种做法是先发送 A 和 B，然后附上一条指令：从当前输出末尾回退两个字节，逐字节复制，直到新增六个字节。

这里有两个量：距离是 2，长度是 6。距离说明从哪里读，长度说明产生多少个字节。它们合在一起，就是一个匹配（match）。没有用匹配表示的单个字节，叫作字面量（literal）。

先不要急着算节省了多少空间。现在我们只是把字节串换成了符号序列；符号还要编码，数据还要放进有头部的容器。对这么短的输入，最后的结果完全可能比原文更长。

不过，我们已经把最重要的问题变小了：只要接收者知道怎样执行这三个符号，就能恢复原文。试着一次只复制一个字节。

第一次复制读取最前面的 A。第二次读取 B。第三次读取的 A，已经是这次匹配刚刚写出来的字节了。

所以，这条指令不是“从原有的两个字节里截取六个字节”。它每次从当前输出末尾回退两个位置，读一个字节，再把这个字节加入历史。历史会增长，读取位置也会前进。匹配长度因此可以大于距离。

把距离改成 1，就能观察到另一个熟悉的模式：一个 A 不断产生新的 A。

这就是 DEFLATE 使用的 LZ77 思想：已经出现的内容，可以通过指向历史的描述来重新产生。这里展示的是合法符号的含义，不是实际 zlib 对这个短输入必然采用的编码。

相关接口与格式：inflate

库与数据格式

现在可以把名字放回来了。

zlib 是一个 C 库。 它提供压缩、解压、校验，以及面向缓冲区和流的接口。核心流式压缩接口叫 deflate，解压接口叫 inflate。

DEFLATE 是一种数据格式。 它规定怎样把字面量、匹配和块编码成比特，以及怎样从比特恢复这些符号。它没有规定压缩器必须怎样找匹配。两个压缩器可以为相同输入选择不同的符号序列，只要都能解出原文。

zlib 和 gzip 也都是封装格式。 它们在 DEFLATE 载荷外面添加不同的头部和尾部。无封装 DEFLATE（raw DEFLATE）则只有载荷。

因此，解出最后一个数据字节，不一定就完成了整个流。解压器还可能需要读取块结束码、检查校验值，或者完成 gzip 的长度检查。后面的流式章节会重新遇到这个区别。

格式的原始定义分别见 DEFLATE / RFC 1951、zlib / RFC 1950 和 gzip / RFC 1952。

保存近期字节，再寻找重复

前面说，压缩器可以用“距离 2、长度 6”代替重复的 ABABAB。现在要解决的是：压缩器读到新内容时，怎样找到以前出现过的相同片段？

先设想一个没有窗口的做法：把整个文件读进内存，每到一个新位置，就向前寻找重复。这个办法需要保留越来越多的数据。若文件还在持续到达，我们甚至不知道最终要准备多大的内存。

zlib 采用有界的历史：保留近期字节，在这段内容里寻找重复。较老的字节离开范围后，就不再被后续匹配引用。文件可以继续增长，保留历史所需的内存则有上限。

“滑动窗口”首先是在解决历史该保留多少、怎样复用内存的问题。 它不是一种单独的编码。最后写入压缩流的仍然是字面量和长度／距离对。

随处理位置前进的保留范围

为了看清变化，先用一个只保留最近八字节的示意窗口。已经处理的内容是 0123ABCD，接下来是 ABCDwxyz。压缩器在保留历史里找到 ABCD，于是可以用“回退 4 字节，复制 4 字节”表示接下来的四字节。

接受这条匹配后，已经处理的内容变成 0123ABCDABCD。最近八字节是 ABCDABCD，最早的 0123 可以离开保留范围。继续处理 wxyz 后，最近八字节又变成 ABCDwxyz。

图里的位置属于整条输入流。真实实现还要把这些字节放进有限的数组。deflate 使用一块连续字节区，先向后填充；接近末端时，把仍需保留的部分搬向数组开头，再使用腾出的空间。因而，“逻辑上保留最近的内容”与“每次前进都搬一次数组”是两回事。

实际 C 中的搬移

读搬移代码之前，先说清它必须同步调整的几个位置。压缩器状态指针叫 s，s->window 表示其中的字节数组。字段 strstart、match_start、block_start 分别保存当前输入、暂存匹配和当前块起点在数组中的位置。局部量 wsize 是本次搬移要减去的字节数，more 是数组末端的空闲字节数。注释中的 MAX_DIST 是实现允许的最远回退搜索距离，在窗口精读中展开。这些位置和距离都以字节为单位。

下面四条语句取自项目固定版本的 fill_window，位于需要搬移的分支内部：

zmemcpy(s->window, s->window + wsize, (unsigned)wsize - more);
s->match_start -= wsize;
s->strstart    -= wsize; /* we now have strstart >= MAX_DIST */
s->block_start -= (long) wsize;

第一行用 zmemcpy 把仍有用的字节复制到较小下标。后三行从暂存匹配、当前处理点和当前块起点中，减去同一个搬移量。

可以用一个简单的算式理解：当前位置从 800 变成 288，候选位置从 700 变成 188，两者都减去 512，距离仍是 100。数组下标改变了，匹配指向的字节没有改变。

八字节窗口仅用于图示；真实 zlib 不接受这样的窗口配置。实际数组布局、搬移条件、最远搜索距离，以及位置表怎样同步更新，放在滑动窗口精读中逐项展开。

在保留范围里加快查找

有了字节窗口，仍然可以在其中逐个尝试历史位置。但每次都从头找，会反复比较许多不可能匹配的字节。哈希链解决的是第二个问题：怎样少检查一些候选。

zlib 用片段开头的三个字节计算哈希，把可能匹配的位置归到同一个桶。head 记录桶里最近的位置，prev 把它接到更早的位置。它们保存的是查找线索，字节本身仍在窗口中。哈希相同只表示“值得检查”，真正的匹配长度还要逐字节比较。

看下面的历史和输入。最近的候选位置 4 开始于 ABCR，更早的位置 0 开始于 ABCQ。待处理输入是 ABCQABCX。

位置   0    4    8
       ABCQ ABCR ABCQABCX
       ↑    ↑    ↑
       更早 最近 当前位置

只检查最近候选，会找到 ABC，长度为 3。再沿链检查一次，则可以找到 ABCQABC，长度为 7。两个候选都以相同的三个字节开始，后面的差异才决定最终匹配长度。

如果链很长，继续搜索也有成本。zlib 的搜索设置包括最多检查多少候选，以及找到多长的匹配就可以提前停止。更高的压缩级别可以花更多时间寻找匹配，但它仍然是有边界的搜索，不保证找到全局最优的压缩表示。

窗口保存近期字节，哈希链帮助找到候选，字节比较确定长度，搜索预算限制所花的时间。这四件事合起来，才得到可以提交给编码器的匹配。下一节再说明：找到一个匹配后，为什么有时还值得等一步。

相关接口与格式：deflate · deflateTune

延迟匹配

假设现在已经找到一个长度为 3 的匹配。立刻采用它，看起来很自然。但如果下一个位置能开始一个很长的匹配呢？

让历史里已经有这两段内容：XABZ 和 ABCDEFGH。当前输入是 XABCDEFGQ。

历史：!XABZ!ABCDEFGH!
当前： XABCDEFGQ
       ↑ 当前位置

当前位置以 X 开始，可以匹配历史中的 XAB，然后在 Z 和 C 处停止，长度是 3。

向前看一个位置，当前后缀变成 ABCDEFGQ。它可以匹配历史中的 ABCDEFG，直到 H 与 Q 不同，长度是 7。

因此，我们可以先输出一个字面量 X，再采用从下一个位置开始的长匹配。这就是“延迟匹配”：暂缓对当前位置的决定，先看下一处有没有更长的匹配。

zlib 的慢速策略保存上一个位置的匹配。若新位置找不到更长的匹配，就使用之前保存的那个；若新匹配更长，就把之前的首字节作为字面量输出，继续考虑新匹配。搜索条件还会限制何时值得做这一步。

这个例子比较的是可用匹配，并不声称第二条路径在所有编码条件下都有更小的最终比特数。长度、距离和字面量的编码成本不同；局部匹配选择与完整块的最小成本不是同一个问题。

相关接口与格式：deflate.c

Huffman 树

我们已经减少了重复发送的字节，但符号本身仍要编码。如果每个符号都占相同的位数，常见的符号就没有得到任何优待。

先用四个抽象符号做一个实验。假设一个块中，A 出现 8 次，B 出现 4 次，C 和 D 各出现 2 次。固定用两个比特表示每个符号，总计需要 32 位。

我们希望常见的 A 更短，但还要能连续解码，不能依赖符号之间的分隔符。一种办法是使用前缀码：任何完整符号的编码，都不是另一个编码的开头。

Huffman 构造从出现次数最少的两个结点开始合并。这里先把 C:2 和 D:2 合并成权重 4 的结点，再把它与 B:4 合并成 8，最后与 A:8 合并成根。

2 + 2 → 4
4 + 4 → 8
8 + 8 → 16

合并时形成的每一层，最终都对应一位编码。于是 A 深度为 1，B 为 2，C、D 为 3。数据部分的成本变成：

8 × 1 + 4 × 2 + 2 × 3 + 2 × 3 = 28 位

这里的固定两位对照仅用于解释四符号编码，不是 DEFLATE 的固定编码表。DEFLATE 实际使用的字母表和码长规则更大，也更具体。

规范 Huffman 编码

树还可以左右翻转，得到另一组同样长度的编码。如果压缩器和解压器各自选一棵树，它们怎么保证得到相同的比特模式？

DEFLATE 使用规范 Huffman 编码，也就是按码长和符号顺序确定码字的约定。双方约定：先按码长，再按符号顺序，连续分配编码。这样就不必发送整棵树，只要让解压器知道每个符号的码长。

对于 A:1, B:2, C:3, D:3，分配过程是：

A →   0
B →  10
C → 110
D → 111

从 0 跳到 10，可以理解为先越过上一长度已经使用的码，再把编号左移一位，为更长的码腾出位置。相同长度的符号则直接使用连续编号。

树上长度为 1 的叶子占据一半空间，长度为 2 的占四分之一。把各符号的 2⁻码长 相加，得到 Kraft 和。等于 1 时空间恰好填满；大于 1 时，有些编码必然冲突。

这个条件也给解码器一个早期检查：长度描述不合理时，不必等到解数据才发现矛盾。实际 zlib 的接受规则还区分完整表、空表和某些单符号情况。它们会在解码章节中继续展开。

相关接口与格式：DEFLATE

块类型与编码成本

刚才的四符号例子把数据成本从 32 位降到了 28 位。如果为了告诉接收者这套新编码，又额外发送超过四位的信息，最终就没有省下空间。

动态表不是免费的。它适合有足够数据来分摊描述成本的块；很小的块可能更适合使用双方已经知道的编码，或直接存放原始字节。

DEFLATE 因此提供三种块：

zlib 在刷新块时计算固定编码和动态编码的成本，再考虑能否采用原样存储形式。原始字节必须仍然可用，原样存储分支才有内容可以复制。策略参数也会影响选择。

因此，从输入到压缩流其实经过两次不同的选择：先决定用哪些字面量和匹配表示原文，再决定怎样编码这一块符号。下一章沿着相反方向走：接收者怎样把这些比特还原成原文。

位序与位缓冲

现在站到解压器这一侧。它连续接收字节，取出其中的位，再把它们还原成符号。

字节中的位按从低到高的位置依次使用。普通数值字段按最低有效位先行；Huffman 码则按码字的最高有效位先行。于是，同一串位用“到达顺序”和“整数写法”展示时，看起来会反过来。

以 C 的码 110 为例。先到达的 1 放在缓冲区第 0 位，第二个 1 放在第 1 位，最后的 0 放在第 2 位。若按通常的高位在左写出缓冲区数值，它就是 011。

理解这个区别后，位缓冲就没有那么神秘了。zlib 把缓冲区数值保存在 hold 中，用 bits 记录其中有多少位有效。补入字节时放在现有有效位之后；解释某个字段或码字时，从低位取走它需要的数量。

解码表

每次读取一位、沿编码树走一条边，就能完成解码。但真实实现可以把前几步合并为一次数组访问：查看若干低位，直接查表。

仍然使用 A=0、B=10、C=110、D=111，并让根表查看两位。表只有四个槽：

为什么 A 占了两个槽？它的码只有一位。只要最低位是 0，第二位是 0 还是 1 都不影响 A 的含义。根表查看了两位，却只会消耗一位。

试着解码消息 AD。按码字顺序拼接，得到 0 | 111；按缓冲区整数的写法，则是 1110。此时根索引是 10，我们仍然得到 A。丢掉一位后，缓冲区剩下 111：根索引 11 指向子表，再用剩下的一位 1 得到 D。

这个过程把三个概念分开了：查看多少位、实际消耗多少位、最终产生哪个符号。 如果查到 A 后也丢掉两位，就会吞掉属于 D 的第一位，后面的解码自然错位。

C 和 D 需要子表，是因为根表的两位还不够区分它们。把根表加宽，可以减少子表访问，却会增加表空间。真实 inflate_table 会按码长分布构造根表和子表，而不是固定展开一棵完整的十五层树。

相关接口与格式：inflate

用小缓冲区分批解压

前面的解码过程回答了“压缩字节怎样恢复原文”。应用还要解决一个很实际的问题：原文可能很大，我们希望只准备一小块输出内存，取回一批结果就把它写入文件或交给下一步处理。

这就是这里“流式”的意思：同一个解压任务可以分成多次调用。一次调用从当前输入位置继续解码，向提供的输出空间写入结果；空间用完时，函数返回，应用取走结果，再给它一块可写空间继续。无需先把全部解压结果放进一大块内存。

先只看解压方向：inflate 的输入是压缩字节，输出是恢复后的原文字节。输出缓冲区是应用提供的一块内存，不是压缩块，也不是整个解压结果。

一块五字节内存，两次取回结果

第一轮输出 ABABA，把五个位置写满。应用先取走这五个字节，然后可以复用同一块内存，让第二轮写入 BAB。最终保存的结果是 ABABA 接上 BAB，也就是 ABABABAB。

图中先把压缩比特的解析省略，直接执行我们已经认识的指令：输出 A、输出 B，再回退两个字节、复制六次。第一轮中，前两个位置给了 A、B，只剩三个位置可供复制，因此还有三次复制要等下一轮完成。

应用实际写出的 C 调用

程序只初始化一次 z_stream。下面这段代码在循环中反复执行，output 是五字节数组：

stream.next_out = output;             /* writable destination */
stream.avail_out = sizeof output;     /* five bytes of room */

int result = inflate(&stream, Z_NO_FLUSH);
unsigned produced = sizeof output - stream.avail_out;

先看两个输出字段：next_out 指向这次可以写的位置，avail_out 表示还可以写多少字节。返回后它们已被推进和扣减，所以“提供的容量减去剩余空间”就是本次得到的字节数。Z_NO_FLUSH 是这次普通解压调用使用的参数，不会要求函数在返回前还原完整原文。

应用先取走从 output 开始的 produced 个字节（为零时没有字节可取），再把 next_out 和 avail_out 设置回这块数组的起点和容量。保留同一个 stream，不再次调用初始化。 未读的输入指针和数量也保留在这个对象中，不能从输入开头重送一遍。

完整可编译程序包含初始化、错误处理、循环和资源释放。它使用图中的五个压缩字节；对项目固定的 zlib 源码编译运行，结果是：

call 1: input=4, output=5, bytes=ABABA, result=Z_OK
call 2: input=1, output=3, bytes=BAB, result=Z_STREAM_END

input、output 分别是本轮消耗和产生的字节数。第一轮还有一个压缩字节没读完，第二轮从它继续。Z_OK 表示这次有进展，但流未结束；Z_STREAM_END 才报告完成。只有“输出缓冲区写满”或“最后一个原文字节已产生”，都不足以代替完成信号。

继续执行需要保留的两类信息

第一类是工作进度。例如“这条复制指令还差三个字节，距离仍是 2”。实现把这样的阶段叫作 MATCH。下一轮从剩下的工作继续，不再重新解释同一条指令。

第二类是仍会被引用的字节。第一轮结果被取走后，第二轮的输出数组可以被覆盖，但回引用还需要其中的 B、A。解压器把必要的后缀保存在自己的历史窗口里：先从保存的历史读出 B、A，再从本轮新输出读出第一个 B，得到 BAB。

这里的解压历史窗口与前面的压缩窗口分工不同：压缩窗口帮助找到重复，解压窗口帮助执行已经收到的回引用。它们都保留近期字节，却不是同一块内存。

实际调用也可能因为缺少输入而暂停，例如一个字段只到了半截。遇到这种情况要补充输入；输出空间用完则要提供空间。若输入没有增加、空间也没改变，反复调用不会凭空带来进展。完整输入、输出、错误返回和结束协议见暂停与调用接续精读。

相关接口与格式：inflate · 流与缓冲区规则