共享存储与输出前缀

块编码还有一个容易漏掉的任务：产生正确输出的同时，不能改坏还没读完的输入。这里每条“输入”记录保存一个字面量字节，或一组复制长度和回退距离。“输出”是位写入器产生的 待交付字节：已经编码完整、但尚未交付给调用者的压缩字节。默认布局让两者共用同一块内存，以节省一份符号数组；安全性取决于读写发生的先后顺序。

先用已经算完的 ABABABAB 看一次完整过程，再引入一般的边界公式。目标不只是“五个输出字节装得下”，还要让每条记录活到被读取的那一刻。

三条记录怎样交出空间

默认内存级别下，符号从分配块的偏移 16384 开始，输出从偏移 0 开始。三条记录分别占 [16384,16387)、[16387,16390)、[16390,16393)。区间左端包含，右端不包含。

读出 B 之前，其三个记录字节必须保持原值；读入局部变量后，这三个字节便可以复用。匹配记录同样如此。因此写入只要始终落在尚未读取的记录之前，就能够沿着这条执行线继续。这个短例子的间隔很宽，后面还要处理记录很多、每条输出也很长的情况。

同一分配的两个视图

这套布局由一个尺度控制：B，在状态中叫 lit_bufsize。它同时决定记录上限和记录前面的初始字节间隔，不是整个分配的容量。初始化参数 memLevel 选择内存预算，并设置 B = 1 << (memLevel + 6)，即 2^(memLevel+6)。实现为输出视图 pending_buf 分配 4B 个字节，让符号视图 sym_buf 指向字节偏移 B。普通打包布局为每个符号保存三个字节，在符号字节数达到 (B-1)*3 时停止记录。因此一个块最多容纳 B-1 条记录。

分配区间：[0 ........................................... 4B)
输出：    [待交付字节从起点向后增长 ....................)
符号：             [B, B+3) [B+3, B+6) ... [4B-6, 4B-3)
                   记录 0   记录 1         最后一条记录

这些视图由初始化函数 deflateInit2_ 建立。下面是 deflate.c:504–505，ZALLOC 通过流的分配器申请 B 个元素，每个元素的大小由 LIT_BUFS 指定，普通布局为 4 字节；s 指向压缩器状态：

s->pending_buf = (uchf *) ZALLOC(strm, s->lit_bufsize, LIT_BUFS);
s->pending_buf_size = (ulg)s->lit_bufsize * 4;

第一行以 B 个、每个四字节的元素申请内存；第二行把待交付使用的容量记成 4B 字节。在分配失败检查之后，普通分支继续执行 deflate.c:519–520：

s->sym_buf = s->pending_buf + s->lit_bufsize;
s->sym_end = (s->lit_bufsize - 1) * 3;

第一行让符号指针指向同一分配中偏移 B 的位置，没有再次分配。第二行把可用记录字节数设成 (B−1)×3。对当前例子，B 为 16384，符号记录因此恰好落在上表的位置。

默认 memLevel = 8 时，B 为 16384。待交付分配有 65536 个字节，第一条记录从偏移 16384 开始，最多 16383 条记录占用 49149 个字节。这些记录已经位于同一分配中，无须再单独分配一个 49149 字节的符号数组。

源码通过 sym_end = (B-1)*3 预留最后一个记录槽位；注释把这个选择与 16 位回绕和原样存储块的大小限制联系起来。LIT_MEM 使用另一种数组和边界，当前图示讲的是普通的打包符号分支。

输出开始前，前面的 B 个字节提供初始余量。随后，每读完一条记录，又腾出三个字节。这解释了共享为什么有机会成立，但还没有说明输出会以多快的速度增长。这里有两条同时移动的边界：读完记录后，允许复用的区域向右扩展；编码产生完整字节后，写入位置也向右推进。安全性要求后者始终不要追上仍待使用的记录。下一节把两条边界都换算成同一分配中的字节偏移，才可以直接比较。

移动的读取边界

为了不覆盖下一条记录，编码器需要记住已经读完多少符号字节。compress_block 把这个字节偏移叫作 sx，初值为零；sx = 6 表示已经读完两条三字节记录。每次迭代先读距离的两个字节和字面量／长度字节，把 sx 增加三，再调用输出辅助函数。字面量发射一个编码；匹配依次发射长度编码、可能的长度额外位、距离编码和可能的距离额外位。

先读后写的顺序可以直接在 compress_block，trees.c:913–915 中看到：

dist = s->sym_buf[sx++] & 0xff;
dist += (unsigned)(s->sym_buf[sx++] & 0xff) << 8;
lc = s->sym_buf[sx++];

第一行读距离低字节并推进 sx；第二行读高字节，左移后加进距离；第三行读字面量／长度偏移，并完成第三次推进。读取匹配记录 02 00 03 后，局部值为 dist = 2、lc = 3，sx 已从 6 变成 9。源码到这之后才选择字面量或匹配分支并发射编码。所以它可以复用当前记录，却仍必须保住下一条记录。

设 q 为已经读完的完整记录数，单位是条，因此它们占 3q 字节。把下一条未读记录的字节偏移记成 R(q)，便有：

R(q) = B + 3q

对前面三条记录的例子，这些边界依次为 B、B+3、B+6 和 B+9。写入器只产生前面推导的五个字节，在默认尺寸下，连第一条边界都远没有接近。证明需要覆盖的是其他符号序列，包括编码长得多的情况。

在一次新的发射阶段，假设尚未交付的字节从分配基址开始，令 P(q) 表示第 q 条记录发射结束后，从起点写出的字节数。实际写入占据半开区间 [0, P(q))。还有未读记录时，写入应当最迟在 R(q) 结束。ZLIB_DEBUG 构建在每条记录结束时断言更强的严格条件 pending < B + sx，为边界留出余量。发布构建中的 Assert 展开为空，不会在运行时检查这个条件，也不会阻止写入。论证必须先建立这个界，才能使用它。

严格界是方便的充分条件，不是“发生覆盖”的定义。如果写入恰好结束在未读边界，两个半开区间依然不相交。证明必须说明自己建立了哪一种不等式，并把计数器连接到真实存储。部分交付之后的待交付计数，也不能自动当成从基址开始的偏移：pending_out 游标和入口状态同样需要交代。

输出增长与前缀成本

为什么写入可能追上读取？一条打包记录占三个字节，但固定编码匹配最多可能产生 31 个编码位：八个长度码位、五个长度额外位、五个距离码位和十三个距离额外位。三个字节只有 24 位，初始间隔因此起着实质作用。

固定编码块可以把逐符号的最坏成本累计起来，再计入三位块头、入口暂存位，以及寄存器转成字节时的取整。得到的是对符号序列每个前缀的界。结合允许的记录个数和最初 B 字节的间隔，才可以论证写入边界始终落在未读输入之前。全部符号读完后，结束码和最终对齐还需要最后的容量论证。

动态编码块增加了两项困难。第一，树描述在记录 0 被读取之前就要写出，因此这整个前缀必须先放在偏移 B 之前。第二，码长来自这个块的实际频率：前面的符号可能很贵，后面的符号可能很便宜。知道它的整块成本胜过固定编码候选，并不能限制早期前缀的成本。

因此，动态编码的论证需要连接实际构造的树、实际频率和实际发射前缀。Kraft 条件检查这些码长能否放进二叉树，且不会让一个码成为另一个码的前缀，却不能单独说明昂贵符号怎样分布在这个块中。树构造的分析正是在这里进入了内存复用问题。

只看总量的反例

下面的教学分配使用 B = 8、容量 32，小于实际允许的 B。两种人为构造的计划，最终输出都能放进分配区。一种一开始就写很多字节，另一种把输出分散到各条记录上。只前进一条记录，对照写入位置和未读边界。

一旦某次写入改坏了一条未读记录，后面的廉价输出就不能把原值变回来。即使后续边界看起来重新安全，也不能抹掉早先发生的覆盖。被破坏的距离还可能在以后触发错误的表索引，所以保留符号既服务于输出写入安全，也服务于编码器后续的读取安全。

原样存储块则有另一种生命周期。选中原样存储形式后，实现复制原始字节，不再消费这些符号记录。记录的保留义务在这个选择点结束；此后，输出可以复用它们的区域，但仍要满足原样存储分支自己的源区间、复制和容量条件。

现在我们可以直接说出需要证明的事，而不必突然引入一种陌生数据结构：每个辅助函数都要保住下一个辅助函数仍然需要的输入。证明思路将把这条执行线索整理成位序列关系、存储不变量和组合步骤。

共享存储的完整组合证明尚未完成：发射入口记账、动态编码的每个前缀成本和允许的调用历史仍需要连接起来。共享缓冲区论证记录精确义务及历史结果的范围；当前进度记录接受结果与开放工作。人为构造的教学计划，不是上游漏洞的证据。