快速解码与回引用复制

查表 之后，解码器得到直接输出的字节、结束标记，或一个匹配：“从这么远的过去复制这么多个字节”。它要把指令变成字节，并在输入或输出空间耗尽后仍保留同一个含义。

输入是解码出的指令、可读历史字节和调用者可写的输出范围。结果是扩展后的输出；若空间不足，还要保存下次继续的工作。若请求的历史根本不存在，则应进入对应错误路径。先跟踪六字节匹配，再看 zlib 为什么用普通和快速两条路线实现同一操作。

新写出的字节也能成为复制来源

从已有输出 AB 开始。长度六、距离二的匹配要求再写六个字节，每个字节都来自目标位置之前两格。匹配追加 ABABAB，完整输出成为 ABABABAB。

这是教学指令，不是完整 DEFLATE 流。来源逐字节读取，所以后面的步骤可以读到本匹配刚写出的字节。在 C 中，out 指向下一个目标，dist 是距离，来源 from 从 out - dist 开始。

距离为二时，前两次复制使用原来的 A 和 B；第三次读取第一次刚写出的 A。对初始源区间拍一个快照，不能表达这种行为。不相交的 memcpy 不足以替代重复规则，一般的快照式移动也不行。

尚待复制的字节数叫 len，本例初值为六。inflate_fast 的真实直接输出分支见固定版本 inffast.c 第 250–256 行：

from = out - dist;
do {
    *out++ = *from++;
    *out++ = *from++;
    *out++ = *from++;
    len -= 3;
} while (len > 2);

len 是尚待复制的长度。本例第一轮执行步骤 1–3，把六减到三；第二轮执行步骤 4–6，把三减到零。关键是第三条赋值已经读取第一条刚写出的 A。真实循环把三次赋值展开写在一起，但执行顺序仍保持逐字节重复规则。

逐阶段解码与暂停

普通解码器用模式字段记住当前在做什么。模式是恢复执行的位置，不是输出字节。慢速路径进入 LEN（读字面量或长度），查找字面量/长度表项，需要时跟随子表，再消费表项的编码位。字面量把模式改为 LIT（写出该字节）；结束标记改为 TYPE（读下一块类型）；无效表项选择 BAD（报告坏数据）。长度基值则经过 LENEXT 补上长度额外位，在 DIST 查距离，在 DISTEXT 补上距离额外位，最后进入 MATCH 复制。基值是表中给出的固定部分，额外位选定该范围内的具体值。

flowchart TD
    L["LEN：读字面量或长度"] -->|字面量| B["LIT：写一个字节"]
    L -->|匹配长度| E["LENEXT：补全长度"]
    E --> D["DIST / DISTEXT：读出距离"]
    D --> M["MATCH：从历史复制"]
    B --> L
    M -->|匹配复制完毕| L
    M -->|输出空间耗尽| P["保存剩余长度和距离"]
    P -->|下一次调用提供空间| M

这些模式明确保存未完成工作。LIT 在写入前检查输出空间。MATCH 按剩余匹配长度、可用输出空间和源中连续部分的长度，限制每次复制。例如，本例只有两个输出槽时，先写出 AB，再保存尚待复制的四个字节。下一次调用继续同一个匹配，不重新解码指令。因此，缓冲区耗尽时可以把正的剩余长度留到下一次调用。其他状态处理存储块、动态表描述和封装字段。

翻译后的 inflate_LEN 也包含快速分支。默认配置不表示每次调用都走快路：缓冲区大小、已缓冲位数和当前模式会在运行时选择路线。

保存的窗口与当前输出

匹配可能要读到本次调用已写字节之前的历史。zlib 用保存的窗口提供这些字节，它是保留最近历史的环形缓冲区。wsize 是以字节计的容量，whave 是有效历史字节数，wnext 是下一个将被覆盖的槽的数组下标，从零开始计数。这是解码器保存历史的环，压缩器使用的较大滑动字节数组则是另一种布局。容量和有效历史是两个量。

要判断来源在当前输出还是保存的历史中，先比较距离与本次已经产生的字节数。beg 指向外层调用的输出起点，done = out - beg 是本次已写出的字节数。若 dist > done，按该距离回退就会越过 beg；超出的距离叫 op = dist - done，单位仍是字节。这个临时 op 不是表项操作。正常的严格距离检查（sane）拒绝 op > whave。仅仅分配窗口不能提供缺失历史。

考虑一个大小八、已满且 wnext = 3 的教学环。物理单元保存 ABCDEFGH，所以按时间排序的历史是 DEFGHABC。当前调用已经产生 DE，现在要求长度六、距离六的匹配。于是 done = 2、op = 4，第一个窗口索引为：

wsize + wnext - op = 8 + 3 - 4 = 7

先从单元 7 读取 H，回绕后再从单元 0 到 2 读取 ABC。四个窗口历史字节已经用完。匹配剩下的两个字节改从本次调用的输出读取，即 DE。匹配贡献 HABCDE，当前输出变为 DEHABCDE。

八个单元用来解释环形索引，不是允许的 windowBits 初始化大小。实际分支区分 wnext = 0、0 < wnext < op 和 wnext ≥ op。尚未填满的环还满足 wnext = whave；只能读取有效的保留历史。预设字典也可以提供历史，而不成为产生的输出。

快速路径余量

快速路线先确认足够完成下一条指令的空间，再省去各小步重复的空间检查。最长匹配产生 258 字节，因此预留这些可写字节便能容纳任意一条匹配。辅助函数还需要六个未读输入字节来覆盖最坏补充量，具体记账在下文展开。这里 have 是尚未取入的可用字节数，left 是可写输出字节数，bits 是整数位缓冲 hold 中已保存的输入位数。入口保留不足八位，也让退出时能够精确退回未使用的完整字节。主解码器在 LEN 中满足 have ≥ 6、left ≥ 258、bits < 8 时选择 inflate_fast。调用前把局部量恢复到流中，返回后再加载状态。真实调用处见固定版本 inflate.c 第 923–927 行：

case LEN:
    if (have >= 6 && left >= 258 && bits < 8) {
        RESTORE();
        inflate_fast(strm, out);
        LOAD();

RESTORE 把局部游标和位写回流，LOAD 在辅助函数返回后重新加载。节选在真实分支内部结束。刚才只有两个输出槽的例子无法进入这里；准备读取新指令时，若输入足够且有 258 个输出槽，就可以进入。

在这个调用处，主解码器的 out 是保存的可用输出数量，作为辅助函数的 start 参数传入。不同函数中的同名变量含义会变。辅助函数中，in、out 是当前指针，avail_in、avail_out 是剩余字节数，start 是外层调用开始时的输出容量。last、end 是继续处理完整指令所需输入或输出余量的界。下面是重述其指针设置的教学等式，不是 C 引文：

last = in  + (avail_in  - 5)
end  = out + (avail_out - 257)
beg  = out - (start - avail_out)

这两个看似奇怪的减数，是把字节余量换成严格指针比较：last 比输入末尾早五字节，所以 in < last 恰好要求至少剩六字节；out < end 同理要求至少剩 258 个可写字节。start - avail_out 是外层调用已经产生的字节数，从当前输出指针减去它，便找回输出起点 beg，也覆盖进入本辅助函数之前已产生输出的情况。第一个循环体由 do 循环直接执行，所以入口余量必须已经成立。后续迭代使用 in < last && out < end。

一个匹配至多写出 258 字节。一个完整长度/距离指令（称为解码指令）至多读取六个输入字节。若把各补充位置的最大值独立相加，会得到七，但这些最大值不可能同时出现：前面的补充留下足够的位，阻止最后一处也达到最大读取量。快速解码参考 展开这份账目。

每轮复制多个字节

快速辅助函数每轮复制多个字节，并处理最后一个或两个字节的余量。直接输出分支的 do 循环依赖最小匹配长度三。窗口前缀有各自的正计数器。源与目标重叠时，读写顺序尤其重要。

表链接同样通过向后的跳转回到 dolen 或 dodist。有效的已安装表把这种链接查找限制在一个子表级。无效长度或距离符号、不可用历史都经错误状态退出；块结束经规定模式退出。快路省去重复检查，不减少错误义务。

字节回退与写回

返回前，辅助函数退回未使用的完整字节。下面是 inflate_fast 的真实收尾，见固定版本 inffast.c 第 291–294 行。此时 len 改用于整字节数，不再表示匹配长度：

len = bits >> 3;
in -= len;
bits -= len << 3;
hold &= (1U << bits) - 1;

缓冲 19 位时，退回两个字节并保留三位。入口时已缓冲位数小于八，保证退回的是本辅助函数取入的字节，而不是进入之前取入的字节。最终收尾即使在错误退出时，也更新精确的游标、可用量、已缓冲位和模式。

快慢路径的完整组合还未完成。小缓冲区必须由慢速分派覆盖，每个实际快速调用都必须建立快路前提。下一章把两条路线连接到 同一个解码器论证。完整的调用者影响和有定义的错误返回属于 inflate 契约，不能从成功路径动画推出。