滑动窗口与哈希链

压缩器寻找已经出现过的内容，用一条引用描述重复片段。先看完整输入 0123ABCDABCDwxyz：其中 ABCD 连续出现了两次。假设压缩器已经处理完 0123ABCD，现在正准备处理第二个 ABCD。

从当前位置回退 4 字节，正好到达第一个 ABCD 的开头。因此，这次重复可以表示成“距离 4、长度 4”。压缩器记录这两个量；解压器读到它们后，从已恢复内容中回退 4 字节，再按顺序复制 4 字节，就能恢复第二个 ABCD。图中的两组蓝色字节对应同一段内容，连线标出引用的来源。

要找到这样的重复，压缩器需要保留已经处理过的字节。但输入可以一直增长，历史不能无限积累。滑动窗口的作用，是只保留近期历史，供后续匹配使用。 下面把保留上限缩小到 8 字节，逐步观察：先定位两组 ABCD，再查看引用，最后推进处理位置。

接受这次匹配后，已经处理的内容是 0123ABCDABCD，最近 8 字节变为 ABCDABCD，最早的 0123 退出保留范围。再处理 wxyz，窗口保留 ABCDwxyz。处理位置不断前进，保留容量始终是 8 字节；离开范围的旧字节不再参与后续匹配。

这里的八只是解释逻辑保留范围，不是 zlib 的合法窗口配置，也没有画出它的物理搬移时机。DEFLATE 的距离最多为 32768；本实现搜索时还要预留比较空间，实际搜索界稍小。下面会把这两层分开。

窗口这一步接收调用者的新字节和压缩器的旧状态，产物是仍可搜索的历史、连续的待处理字节，以及与它们一致的位置索引。它还没有生成压缩符号。下一篇候选搜索才决定用字面量还是引用；匹配证明解释这些交接如何保持字节含义。

从保留范围到实际数组

一个直观实现可以每来一个字节就删掉最老字节、搬动其余内容。zlib 避免这种频繁搬移：它在更大的连续数组里向前处理，接近末端时才成批搬动。于是同一个字节既有永不改变的逻辑流位置，也有会在搬移后改变的数组下标。近期历史的逻辑范围，并不等于整个物理数组。

位置与保留字节

先区分两种位置。流位置表示一个字节是整条输入中的第几个字节，处理继续时不会改变。数组下标表示它现在放在内存的哪一格，搬动字节后会改变。下面的变量描述数组布局，单位都是字节。

真实实现需要同时存放两批内容：已经处理、可供匹配的历史，以及已经读入、尚未处理的新输入。把配置的窗口尺度记为 W，它对应 C 字段 w_size。普通布局分配一个能容纳 2W 字节的连续数组 window，容量记在 window_size 中。例如 W = 512 时，数组共有 1024 格。分配容量和允许的回退距离是两种不同的限制。

处理位置由 strstart 记录：它是下一个要处理的字节的数组下标。lookahead 是从这里开始已经读入、但还没有处理的真实输入字节数，也就是预读量。例如 strstart = 800、lookahead = 100 时，待处理字节占据 [800, 900)，即包含下标 800、不包含 900；真实数据末尾是 900。

数组下标：0                strstart            strstart + lookahead       2W
          [ 较早的已处理字节 ][ 已读入、尚未处理的输入 ][ 空闲区域 ..........)
                               ← lookahead 字节 →

图中较早的字节不一定都还能参与匹配，允许的最远距离会在下一节定义。先看存储方式：zlib 的字节比较直接沿这个连续数组进行。从一个下标向后读取，就能连续比较一段内容。它不把每次字节访问都变成“下标对 W 取余”；接近数组末端时，才把仍需保留的内容成批搬到低下标，腾出尾部接收新输入。后面哈希链中的前驱表会循环复用槽位，那是另一个数组。

匹配长度、预读需求与搜索距离

找到一段重复，需要回答两个问题：它能复制多少字节，来源离当前位置有多远？ 在开头的 ABCD 例子里，长度和距离恰好都是 4，但它们描述不同的量。长度决定这次能替代多少输入；距离决定要回到历史中的哪里。

DEFLATE 的一个匹配只能表示 3 到 258 字节的复制。因此，只有 1 或 2 字节相同还不够构成这种匹配；更长的重复也需要拆成多个符号。源码把这两个长度端点分别命名为 MIN_MATCH = 3 和 MAX_MATCH = 258，单位都是输入字节。

压缩器还希望在作出选择前，多看到一点后续输入。否则，本轮只读到 AB，并不能说明完整的 ABCD 匹配不存在。在正常补充输入时，zlib 尝试准备 262 字节预读量。源码把这个目标命名为 MIN_LOOKAHEAD，定义为 MAX_MATCH + MIN_MATCH + 1：最长匹配的 258 字节之外，还为后续三字节串的哈希插入等操作预留余量。它是本实现的预读目标；输入末尾或刷新时可以处理不足 262 字节的尾部。

有了这个预留量，才能说明实现的搜索上限。zlib 不把 W 全部用作允许的回退距离，而是取 窗口尺度减去预读目标。这个上限在源码中叫 MAX_DIST(s)，其中 s 是压缩器状态，值为 s->w_size - MIN_LOOKAHEAD。我们用简写 W - 262 表示它。候选离当前位置超过这个距离，就不再进入普通匹配搜索。

普通的 W = 32768 配置给出搜索上限 32768 - 262 = 32506 字节。DEFLATE 格式本身仍允许距离 32768；这里计算的是这个压缩器选择搜索多远。数组中即使还放着更早的字节，也不能因此把它们当成允许的候选。这就是物理存储范围与搜索范围的区别。

窗口参数与字节数

API 参数 windowBits 用指数表达窗口尺度：归一化后的值为 b 时，W = 2^b 字节。例如 b 为 9 对应 512 字节，b 为 15 对应 32768 字节。无封装 DEFLATE 和 gzip 的参数还用符号或附加数值选择封装，初始化函数会先处理这些选择，再得到窗口指数；完整参数规则见 deflateInit2_。

本节所选默认构建中，实际得到 512 ≤ W ≤ 32768。zlib 封装接受的指数 8 会被改为 9；无封装与 gzip 则拒绝指数 8 的情形，所以这里不会得到 256 字节窗口。最小的实际尺度 512 仍能给搜索留下 512 - 262 = 250 字节。若把 256 直接代入同一个公式，就连正的搜索余量也没有了。

补充输入与预读区

当前预读量不足时，负责补充输入的函数 fill_window 先计算真实数据末尾到数组末尾还剩多少空格。这个空闲字节数叫 more；window_size 是数组总容量，普通布局下等于 2W：

more = window_size - lookahead - strstart

在下面的 C 片段中，s 指向压缩器状态，s->strm 指向调用者的公开流结构。read_buf 从这个流读取输入，返回实际复制的字节数 n。片段摘自固定版本 fill_window，311–312 行，不是教学伪代码：

n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more);
s->lookahead += n;

第一行把目的地址放在已有真实数据之后，并把空闲量 more 交给 read_buf 作读取上限。第二行只增加实际读到的 n，而不是增加请求量。这样在输入不足时，计数仍描述真实存在的字节。

调用者本轮还提供了多少可读输入，由公开字段 avail_in 计数。完成必要的滑动后，read_buf 把至多 min(avail_in, more) 个字节复制到 window + strstart + lookahead。它推进调用者输入指针，减少 avail_in，更新输入记账及选定封装的校验和，再把 lookahead 增加相应数量。接收这些字节，并不表示匹配策略已经把它们消费成符号。

只要调用者仍有可用输入，循环就尽量取得 262 个字节的预读区。到了策略层，Z_NO_FLUSH 下预读不足时可以返回 need_more，而不是立刻对一个短前缀作出决定。结束或刷新调用则可以处理不足这个长度的尾部。这些内部结果不是公开 deflate 的返回码，外围协议见调用接口。

比较代码为了加速，有时会扫描到真实输入末尾之后。因此，数组中还需要一小段已经初始化的尾部，避免读取未初始化的内容。high_water 是这个初始化前缀的末尾下标：[0, high_water) 都已写入过。补充输入后，zlib 按需把真实数据末尾之后最多 258 字节清零，且不越过数组边界。源码用 WIN_INIT = MAX_MATCH = 258 表示这个初始化长度。清零只让这些内存可供读取，并没有增加真实输入；一个匹配能消费多少字节，仍由 lookahead 限制。

补充输入还会完成延期的哈希插入。如果上次调用结束时只剩一或两个字节，这些位置还没有完整的三字节字符串可供插入。insert 计数保存这部分工作。新字节到达后，fill_window 重新准备滚动哈希，把现在已经完整的字符串插入，再继续普通搜索。

带具体偏移的滑动

滑动条件是 strstart ≥ W + MAX_DIST，也就是 strstart ≥ 2W - 262。取合法的 W=512，令 strstart = 800、lookahead = 100。真实数据结束于 900，剩余空间 more = 1024 - 900 = 124。滑动阈值为 762，因此进入滑动分支。

它复制 W - more = 388 个字节，把 [512, 900) 搬到 [0, 388)。这里搬的是上半区已经有效的部分，不是无条件复制全部 512 个字节。源、目标区间互不重叠。strstart 减去 512，变成 288；lookahead 仍为 100。空闲空间增加到 636 个字节。若还有 300 个新字节，下一次读取便把它们放进 [388, 688)，令预读量达到 400。

原来位于 700 的保留候选变成 188。它与当前位置的距离仍是 800 - 700 = 288 - 188 = 100。在逻辑层面，窗口偏移 0 代表的输入流基准已经前移 512，所以两组下标仍然指向同一批流字节。

搬移还要更新保存的位置：match_start 是保存的匹配起点，block_start 是当前压缩块的原始输入起点。代码中的 wsize 是窗口尺度 W 的局部变量，zmemcpy 是复制字节的辅助宏。把例子接回实际实现，固定版本 fill_window，287–290 行的连续四行是：

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;

第一行真正搬动字节：目的地是数组开头，来源是偏移 W，长度正是例子的 388。第二行平移保存的匹配位置；这不保证该字段此时一定是有效候选。第三行平移当前处理位置。第四行用有符号运算平移块起点，以容许它落到当前数组之前。后续源码还会限制延期插入量、调用 slide_hash，并把新增的 W 字节加入空闲计数。

元数据也必须完成相同的变换。slide_hash 对每个位置 m 执行：若 m ≥ W，保存 m-W；否则保存零哨兵。头表和前驱表都需要更新。block_start 是有符号量，滑动后可以为负：原始块的开头可能已经离开窗口。因此，原样存储块选择还必须判断原始字节指针是否可用。旧的 match_start 也可能只是暂存的过时值；它的无符号减法需要在真正使用该字段的位置分析，不能把它永久当成有效引用。

滚动哈希与前驱槽位

逐一搜索所有较早位置，会比较许多不可能匹配的内容。zlib 先对每个三字节串计算一个较小的整数，称为哈希值，再按这个整数把位置归入不同的桶。要找 ABC 时，只遍历与它同桶的位置。相同的三字节串一定同桶，不同的串也可能同桶，所以这一步只缩小候选范围，之后仍要比较真实字节。

桶越多，通常越容易把不相关的候选分开，但索引也占更多内存。初始化参数 memLevel 控制这部分内存配置。默认值 8 对应 32768 个桶。源码的几个字段描述同一张索引：

为了从 ABC 前进到 BCD 时不重算所有字节，zlib 递推更新哈希值。下面用 h 表示当前哈希整数，next_byte 表示下一个字节的数值。<< 是左移，XOR 是逐位异或，AND 配合掩码只留下低 15 位：

h := ((h << hash_shift) XOR next_byte) AND hash_mask

从零开始，十进制字节 A=65、B=66、C=67 依次得到哈希状态 65、2146、3075。再加入 D=68，得到 36，恰好等于重新从零对 B、C、D 计算的结果。三次移位会把更早的贡献推出 15 位掩码。因此，递推能够从一个连续三字节串前进到下一个，而不必重算整个键。

一个桶通常包含多个位置。zlib 把同桶位置连成一条由新到旧的链：头表 head 记录每个桶最新的位置，前驱表 prev 让每个位置指向上一个同桶位置。这里“前驱”指上一次插入的同桶候选，不一定是输入中紧挨着的前一个字节。

设桶号为 hash、要插入的位置为 p。head[hash] 是旧桶头；p 的前驱放在 prev[p & (W-1)]。W 是二的幂，所以 & (W-1) 等价于对 W 取余，把位置映射到 W 个槽位之一。例如桶 3075 原来指向位置 60，插入位置 100 后，prev[100] = 60、head[3075] = 100。这次搜索从旧桶头 60 开始，而不是从刚插入的 100 开始。返回的旧桶头在代码中叫 match_head。

下面的宏把这个顺序落实到 C。参数 s 指向状态，str 是要插入的位置，match_head 接收旧桶头；ins_h 是状态中保存的滚动哈希值，w_mask 等于 W-1。UPDATE_HASH 执行上面的哈希递推，Pos 是保存位置的整数类型。固定版本的普通 INSERT_STRING 宏，160–163 行保留了操作顺序：

#define INSERT_STRING(s, str, match_head) \
   (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
    match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \
    s->head[s->ins_h] = (Pos)(str))

第一行命名宏及三个参数。第二行用当前位置的第三字节完成哈希更新。第三行把旧桶头同时存入前驱槽位和返回变量 match_head。第四行才把当前位置发布为新桶头。逗号表达式按这个次序执行；编译选项 FASTEST 启用的简化实现另有不维护前驱链的分支，不能套用这段代码的全部论证。

前驱数组只有 W 个槽位，p 与 p+W 会复用同一槽位。例如 W=512 时，位置 100 和 612 都使用槽位 100。插入位置 612 会改写位置 100 曾经保存的链接；但两位置已相隔 512 字节，超过本配置 250 字节的搜索距离，旧位置本来也不能再作为新匹配的来源。

这节省了内存，但论证必须记住槽位属于哪次插入。只有当 p 对应的槽位尚未被后来的位置复用时，才能把其中数值解释成 p 当时记录的前驱。滑动 W 会保留 p mod W，因此保留链接可以继续使用原来的槽位，只改变其中保存的位置值。零表示 NIL，实际源码不会把位置零作为普通候选提供给搜索。

哈希把位置归入候选桶，真正的内容比较在下一篇候选搜索与延迟决策展开。覆盖全部公开调用的窗口组合证明尚未完成：它还需要把初始化、补充输入、搬移和候选索引的保持性接到同一条调用历史上。压缩实现论证列出了这条连接的具体义务。