块选择与符号成本

匹配搜索把重复输入变成了简短的指令，但解码器不能直接读取内存中的“匹配”对象。块编码的任务，是为这些指令选择一种双方都理解的表示，并在前面写清楚采用哪一种编码。它的输入是已经选好的字面量／匹配序列，输出是包含块头、载荷和结束码的 DEFLATE 比特。

这一章从头到尾使用 ABABABAB：先发字面量 A、B，再发“向后距离 2，复制 6 字节”。前两字节建立历史，匹配逐字节复制后得到 ABABABAB。如果选择最终固定编码块，这三个指令会变成六个字段，共 38 个有效位；最终对齐后是五个字节 73 74 82 40 00。下面先说明为什么有不同块形式，再把这个结果逐项算出来，最后回看源码怎样比较成本。

这是为讲解选定的符号序列，不代表某次实际 zlib 调用必然选择它。匹配选择与块编码是相邻的两个任务；本章从已经选好的三个符号出发。

三种块形式

DEFLATE 块从“是否最后一块”的标志和两位块类型开始。块体可以使用三种形式。

原样存储块直接携带原始字节。它先对齐到字节边界，写入 16 位长度和它的 16 位反码，再复制数据。这样不必支付编码描述的成本，但原始字节区间必须仍然可用。已经整理好的长度／距离记录，不能直接当成原样存储数据复制。

固定编码块使用 DEFLATE 预先规定的码长。解码器已经知道这些编码，因此不需要发送树描述。但数据依然要经过长度／距离编码；固定编码并不表示不压缩。

动态编码块先描述这一个块自己的编码，再发送数据。zlib 构造字面量／长度树和距离树，确定码长，然后分配规范编码。解码器必须先重建相同的码长与码字，才能解释第一个载荷符号。

对于小块，这段描述可能比它省下的位还多。对于较大、频率分布偏斜的块，常见符号的短码则可能把成本赚回来。因此，比较必须覆盖整个块，也包括元数据。

等待发射的符号

字面量直接表示一个字节；匹配用复制长度和回退距离表示一段内容。压缩器先保存这些选择，等块准备好后再编码。在不启用另一种存储布局 LIT_MEM 的默认构建中，zlib 为每个待处理符号保存三个字节。前两个字节保存距离，低字节在前。距离为零表示字面量，此时第三个字节就是字面量值。距离非零表示匹配，第三个字节保存 length - MIN_MATCH，其中 MIN_MATCH = 3 是格式能表示的最短匹配长度。减去这个最小值后，允许的 3 到 258 字节长度变成 0 到 255 的偏移，恰好能放进一个字节。

这里还需要一种便于稍后重新读取的内部表示。三个指令在内存中占九个字节；它们不是最终压缩输出：

源码中，s 指向压缩器状态，sym_buf 是符号字节区，sym_next 是其中下一个空闲字节的偏移。dist 是以字节计的复制距离，字面量时为零；lc 保存字面量字节，或前面定义的长度偏移。这三个字节直接来自 _tr_tally 的普通布局分支，trees.c:1100–1102：

s->sym_buf[s->sym_next++] = (uch)dist;
s->sym_buf[s->sym_next++] = (uch)(dist >> 8);
s->sym_buf[s->sym_next++] = (uch)lc;

第一行保存距离的低八位，然后推进索引。第二行右移八位，保存高字节，并再次推进。第三行保存字面量或长度偏移，再推进一次。对匹配 (dist, lc) = (2, 3)，三行依次写出 02、00、03。非调试构建还使用内联符号记录宏；这里用保留相同打包方式的函数体看清每一次写入。

匹配记录没有保存那六个输出字节，解码器以后会从历史中逐字节产生它们。把本例的三种数量摆在一起，可以看出它们为什么不能混用：

“读完一条记录”可能接受六个原文字节，却只追加一个匹配的编码。后面计算存储边界和比特成本时，必须保留这些单位的区别。

记录符号时，zlib 还会更新字面量／长度树和距离树的频率。一个匹配增加的是长度编码的频率，而不是六个字面量的频率。选中的长度可能还需要额外位，距离也是一样。块结束符号也有自己的频率。等到块准备输出时，这些统计才交给树构造。

这里的交接很重要：compress_block 之后还会重新读取这些记录。输出过程必须把每条记录保留到它被读完为止。共享存储会继续追踪它们实际位于哪里。

固定块的逐字段展开

对已经选好的符号序列，假定从空位缓冲开始，写一个最终的固定编码块。先从匹配记录保存的两个字段推导编码符号。下面各编码表的数值均为十进制。

字面量／长度字母表用符号 0 到 255 表示 256 种字节值，用符号 256 表示块结束，所以匹配长度组从 257 开始编号。源码用 LITERALS = 256 命名字节值的数量，用 _length_code 把保存的长度偏移映射成组号。长度为 6 时，lc 为 3；_length_code[3] 的值是 3，再加上 LITERALS + 1 = 257，得到符号 257 + 3 = 260。更大的长度组需要用额外位在组内选择具体长度；这一组只有一个可能的长度。

选中的字面量／长度表 ltree 为每个符号保存码字和位宽，send_code 负责写出这两个量。这一步对应 compress_block，trees.c:922–923：

code = _length_code[lc];
send_code(s, code + LITERALS + 1, ltree);

第一行把保存的长度偏移 3 查成长度编码组 3。第二行把组号加到 257 后，发射字面量／长度字母表中的符号 260。send_code 再从 ltree 取出这个符号的码字和码长。这样，从记录 02 00 03 到符号 260 的每一步都有明确对象。

对于距离，编码器先把记录中的距离减一。距离 2 变成 1，而 d_code(1) 为 1。最初几个距离组能直接说明这个映射：

接下来，根据固定编码字面量／长度字母表确定码宽：

最后一个固定编码范围中的 286 和 287 是保留符号，不能表示合法匹配长度。合法距离符号的固定码宽都是五位。本例用 ASCII 编码表示字母，A 和 B 的字节值分别为 65 和 66，因此各用八位；符号 260 和块结束符号 256 各用七位。距离符号 1 使用五位，选中的长度组和距离组都不需要额外位。因此完整字段如下：

合计是 3 + 8 + 8 + 7 + 5 + 7 = 38 个有意义的位。最终对齐再补两个零，得到五个无封装 DEFLATE 字节。若同样从字节边界开始，以原样存储形式保存这八个原始字节，则需要十三个字节：块头与对齐、四个长度字节、八个数据字节。zlib 或 gzip 封装还会在无封装块之外添加自己的字段。

成本计算与选择

在正压缩级别下，_tr_flush_block 先构造字面量／长度树和距离树，同时累计动态载荷成本，以及用固定树编码同一组符号的成本。构造了动态候选，并不意味着最后一定使用它。

动态描述本身又分两层。字面量／长度和距离的码长组成一个序列；scan_tree 识别其中重复的码长和连续的零；build_bl_tree 构造用来编码这个序列的较小码长字母表。最后，send_all_trees 写出计数字段、码长字母表自身的码长，以及编码后的序列，其中也包括重复指令的额外位。这项优化缩短的是描述，不改变原来的数据符号。

比较前必须统一单位。s->opt_len 以位计数，包含动态编码的载荷与树描述；s->static_len 以位计数，记录固定编码的载荷。两者都计入结束码，但尚未计入三位块头。按字节向上取整后的候选分别叫 opt_lenb 和 static_lenb：

opt_lenb = (s->opt_len + 3 + 7) >> 3;
static_lenb = (s->static_len + 3 + 7) >> 3;

两行出自 _tr_flush_block，trees.c:1027–1028。第一行转换动态编码的位成本；第二行对固定编码做相同转换。对我们的三符号例子，固定编码的载荷与结束码共 8+8+7+5+7 = 35 位，第二行因此算出 (35+3+7)>>3 = 5 字节，正是前面推导的结果。动态编码的树描述仍要单独算进它的候选，不能从这个例子直接断言实际选择结果。

这里的三计入块头，七用来实现向上取整。在固定编码与动态编码两个压缩候选之间，成本相同的时候固定编码优先；调用者选择 Z_FIXED 策略时，也会让固定候选压过动态候选。对原样存储分支，stored_len 表示这块原始数据的字节数。随后，只有当 stored_len + 4 不大于选中的压缩候选，且原始字节指针非空时，原样存储分支才可用。四对应两个 16 位长度字段。实际原样存储写入器会另行执行位对齐和块头写入。

这些是具体的源码选择规则，并不是对所有可能压缩流求全局最短解。前面的匹配决策和块边界已经限制了候选。强制原样存储输出和其他构建配置，也有各自需要分析的路径。

至此，我们已经确定要发射哪些字段。下一篇沿着位写入器的实际过程继续追踪它们，特别观察一个新字段跨过 16 位寄存器边界时会发生什么。

覆盖全部允许调用的块选择证明尚未完成：它需要在实际返回堆上连接符号频率、候选成本、选中分支与发射结果。树与块输出的详细论证记录各组件的义务；deflate 契约规定公开调用的行为。