码长修复与规范编码

合并树给出了初步码长，但有些码可能过长，而且解码器还不知道这些长度。本章先把过长码修复成可用编码，再分配双方一致的码字，最后按接收顺序发送码长描述。三个阶段必须连接起来，解码器才能使用编码器选择的那套编码。

输入是构造器得到的树及符号频率。输出是满足格式上限的码长、每个使用符号的规范码字，以及让解码器恢复这些码长的描述。解码器看不到编码器的父链接，因此描述必须足以重建相同的编码。

先让四个符号往返一次

前一章得到初步码长 A:1、B:2、C:3、D:3。双方按“短码在前、同长度按符号编号排列”的规则分配码字，不必知道原树的左右方向。长度一从 0 开始；跳过它占用的分支，长度二从 10 开始；再跳过它占用的分支，长度三从 110 开始。得到：

取一条短消息 ABCD，拼接得到 0 | 10 | 110 | 111，共九位。解码器已知码长和符号顺序，便能重建同一张表：读到 0 认出 A，读到 10 认出 B，随后 110、111 分别认出 C、D。每次只消费当前码字，后面的位留给下一个符号。

最后一列同时需要数值和位宽，不能只看十六进制数字。C 存 0x3，码长为 3，因此对应的三位整数写成 011；从最低位依次取出就是 1,1,0，也就是接收者看到的规范码字 110。若忽略码长，把整数 3 只当成两位 11，就会少发送一个属于 C 的位。位写入器在完整固定编码块中继续跟踪这个约定。

这次往返只演示符号码字，不是完整 DEFLATE 块。真实块还需要格式允许的符号字母表、结束标记 END_BLOCK、块头和码长描述。下面先解决可能让编码表根本不存在的问题，再回到实际 C 如何实现和发送它。

深度与码长上限

DEFLATE 给字面量／长度和距离码的上限是 15，给描述码长所用的小树上限是 7。未使用符号的长度为零。

一棵较深的 Huffman 树可能超过格式限制。直接截断每个深叶子，会制造过多的短码字。为了用小数字看清楚，取一个教学上限 3，而不是 DEFLATE 的实际上限，并使用抽象频率 A:8, B:4, C:2, D:1, E:1。Huffman 合并给出深度 1,2,3,4,4。怎样判断这些长度能不能共存？一个长度 b 的码字占用全部二进制路径的 2^-b：例如 0 已占第一位是零的那一半，别的码字就不能以它为开头。这些份额的总和称为 Kraft 和；大于一就一定放不下，等于一表示完整占满。原来的长度恰好满足：

1/2 + 1/4 + 1/8 + 1/16 + 1/16 = 1

截成 1,2,3,3,3 后，和变成 9/8。叶子仍然有五片，但这组码长需要的空间已经超过一棵二进制前缀树能提供的空间。只满足最大长度限制，不代表编码已经可用。

码长计数的修复

先把“某个长度有几个符号”列成计数表，也称直方图。用 bl_count[b] 表示长度 b 的符号数；L 表示上限。源码还用 overflow 统计遍历中“根据父码长再加一后超过上限”的节点数，用它决定还要修复几轮。五符号例子中，两个深度四叶子使 overflow=2；更深的树还可能把内部节点计入。修复先改变这张表，再把长度分回具体叶子。它找到上限 L 以下最大的非空长度 b，移除一个该长度编码，在 b+1 处增加两个编码，再移除一个长度为 L 的编码：

下面是教学版记账，不是原样 C 节选：

bl_count[b]     -= 1
bl_count[b + 1] += 2
bl_count[L]     -= 1
overflow       -= 2

把一个长度为 b 的叶子拆成两个孩子，Kraft 权重不变，叶子数增加一。再移除一个长度为 L 的叶子，就恢复了叶子数，并移除了 2^-L 的权重。例子中，截断后的计数是一片长度一、一片长度二和三片长度三。取 b=2 后，计数变成一片长度一和四片长度三，Kraft 和回到 1/2 + 4/8 = 1。

随后，源码从后向前扫描保留节点，先分配最长的码长类别，跳过内部节点，重新填写每片叶子的长度。例子中，A 保留长度一，其余四片叶子取得长度三。载荷成本变为 8×1 + 4×3 + 2×3 + 1×3 + 1×3 = 32 位；原来不受限的树需要 30 位。满足格式限制可能增加成本。

修复后按 A、B、C、D、E 顺序分配的规范码字是 0、100、101、110、111。例如消息 ABCDE 编成 0 | 100 | 101 | 110 | 111，解码得到原消息；相应存储整数是 0、1、5、3、7。这五个符号的例子完成了“合并深度 → 受限长度 → 码字 → 解码”的全过程，使用的上限 3 仍只是教学条件。

把例子对回实际码长计算

gen_bitlen 先把根的码长设为零，再按父节点到后代的顺序遍历保留节点，读取 Len(parent)+1，并把它限制在描述符给出的最大值内。字面量／长度码和距离码的上限是 15，小型码长字母表的上限是 7。未使用符号保持零码长。

只有叶子的码长进入 bl_count：bl_count[b] 统计被分配到长度 b 的符号数。同一遍还估算两种编码要花多少载荷位。opt_len 保存采用新动态编码的累计位数；存在对应固定树时，static_len 保存采用预定义固定编码的位数。每次符号出现的成本包含码长，以及指定精确匹配长度或距离所需的额外数值位。例如长度符号先选出一个长度范围，额外位再选定范围内的具体长度。所以计算码长与估计载荷成本相互连接，但匹配的成本不只包含码长。

源码对每个“根据父码长再加一后超过上限”的遍历节点增加 overflow，其中也包括内部节点。它不只是过长叶子编码的数量。这个小例子里，两个深度为四的叶子贡献超限计数 2；若子树更深，内部节点的贡献也会影响修复次数。

下面的循环中，s 指向压缩器状态，max_length 是以位计的选定上限；局部变量 bits 从较长码长向下寻找前文的非空长度 b；s->bl_count 就是刚刚得到的计数表。实际修复循环逐字见固定源码 trees.c:583–593：

    do {
        bits = max_length - 1;
        while (s->bl_count[bits] == 0) bits--;
        s->bl_count[bits]--;        /* move one leaf down the tree */
        s->bl_count[bits + 1] += 2; /* move one overflow item as its brother */
        s->bl_count[max_length]--;
        /* The brother of the overflow item also moves one step up,
         * but this does not affect bl_count[max_length]
         */
        overflow -= 2;
    } while (overflow > 0);

代入例子的上限 3：首行赋值让 bits=2，非空检查立即成功；三个计数写入依次把 (1,1,3) 变成 (1,0,3)、(1,0,5)、(1,0,4)。最后把超限计数从 2 减到 0，循环结束。随后 600–610 行按保留顺序反向扫描，跳过内部节点，把四个长度三和一个长度一真正写回叶子，同时修正成本。

这些运算要成立，搜索 b 必须能遇到非空类别，最终类别的减法不能下溢，反向扫描也必须有足够的叶子可取。这些事实要从实际构造的完整树和保留顺序推出。如果把任意一组截断码长当成已经具有这些性质，就隐藏了修复中最关键的一段。

规范码字与反转存储

前面的两个往返例子使用了规范分配。码长确定后，这种分配不再需要合并树的左右方向。gen_codes 根据直方图计算每种长度的第一个码字。这里 bits 是正在分配的码长，单位为位；code 保存正在计算的起始码字整数；next_code[bits] 保存该长度下一个尚未使用的码字。左移一位（<< 1）就是在进入下一种长度时补一个零位。下面两行逐字来自固定源码 trees.c:213–214：

        code = (code + bl_count[bits - 1]) << 1;
        next_code[bits] = (ush)code;

对四符号例子，长度一的起点是 0；长度二的起点是 (0+1)×2=2，即 10；长度三的起点是 (2+1)×2=6，即 110。这里的计数必须恰好来自实际码长，且 bl_count[0]=0。

随后按符号编号顺序访问。循环变量 n 是符号编号，max_code 是准备阶段纳入的最大符号编号；节点字段 Len 保存已分配的位长度，Code 保存交给低位先行写入器的整数。实际赋值逐字见 223–227 行：

    for (n = 0;  n <= max_code; n++) {
        int len = tree[n].Len;
        if (len == 0) continue;
        /* Now reverse the bits */
        tree[n].Code = (ush)bi_reverse(next_code[len]++, len);

len 读出当前符号的长度；零长度直接跳过。C 读到长度三，取 next_code[3]=6 再递增为 7，反转三位后存 3；D 接着取 7，反转后仍为 7。这里的后缀 ++ 必须先取旧值，bi_reverse 必须恰好反转 len 位。低位先行写入器才能依次发出规范码字，而不是把 C 发成 011。

规范分配让编码器只需发送码长，而不用传递指针形式的树。双方使用相同的符号顺序和计数规则。精确规则见规范 Huffman 编码规格。接下来的问题，是怎样经济地发送数百个码长。

码长游程的编码

字面量／长度与距离码长形成两个序列，其中也包括未使用符号的零。把每个长度直接写成固定宽度数值，可能耗掉动态编码块省下的大部分空间。因此，DEFLATE 使用一个含 19 个符号的码长字母表。符号 0 到 15 直接给出码长；另外三个符号描述重复：

指令 16 需要此前已经有一个码长，17 和 18 不需要。考虑连续四个 3、十个零、一个 2，再接十一个零。这是码长序列的教学片段，不单独构成完整的 DEFLATE 数据树。与源码相容的一种分解是：

3, 16(extra=0), 17(extra=7), 2, 18(extra=0)

展开后的第 1–4 项都是 3，第 5–14 项是零，第 15 项是 2，第 16–26 项是零，正好恢复全部 26 项。第一个直接给出的 3 建立了前一码长，符号 16 再加三个；符号 17 加十个零，直接给出的 2 改变码长，符号 18 再加十一个零。括号中的数值按表中位宽写入，不是额外的码长符号。超过单条指令上限的长游程要分开处理。源码用 count 记录当前游程包含多少个码长项，不是多少位或多少输入字节；max_count 表示收集到多少项就必须发射，min_count 表示多少项起值得使用重复指令。这些阈值取决于当前是零游程、继续相同的非零码长，还是遇到了新码长。

为什么还需要另一棵 Huffman 树？刚才压短的是载荷符号，而现在要发送的是一长串码长；重复的零和相同长度让它们也值得编码。

scan_tree 先执行这套游程逻辑，统计码长符号频率；build_bl_tree 构造它们的 Huffman 树；之后 send_tree 沿对应的游程分解真正发出编码和额外位。两遍扫描省掉了额外的指令序列缓冲，但要求前后两次决策一致。max_code+1 处的保护码长 0xffff 用来结束最后一个游程；它只作为哨兵比较，不能成为码长字母表的索引。

在下面的片段中，curlen 是当前重复的码长，prevlen 是上次已经描述过的码长，count 是当前游程尚待描述的项数；s->bl_tree 保存 19 个描述符号的编码。REP_3_6 是符号 16 的源码名，send_code 写入它的 Huffman 码字，send_bits 写入随后的定宽数值。固定源码 trees.c:772–783逐字包含以下非零游程分支：

        } else if (curlen != 0) {
            if (curlen != prevlen) {
                send_code(s, curlen, s->bl_tree); count--;
            }
            Assert(count >= 3 && count <= 6, " 3_6?");
            send_code(s, REP_3_6, s->bl_tree); send_bits(s, count - 3, 2);

在四个 3 的游程中，curlen=3 与前一码长不同，所以先发一个 3 并把 count 从 4 减到 3；再发符号 16（REP_3_6）与两位数值 3−3=0。后面的零游程分支把十个零编码为 17 加三位数值 7，把十一个零编码为 18 加七位数值 0。Assert 是源码检查位置，不可充当对正式调用者的证明。

线路上的动态描述

最后还要明确一层：要解开重复指令，接收者需要先知道小型码长树。它自己的码长至多为 7，所以可以按规定顺序直接用三位数值发送：

16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15

动态编码规格定义这层描述。编码器省略这个顺序中未使用的尾部，但至少宣布四项。三个计数分别回答“这次描述包含多少项”：lcodes 是字面量／长度表按符号编号发送的码长项数，dcodes 是距离表的码长项数，blcodes 是上述规定顺序中宣布的小树码长项数。它们都包括发送范围内的零码长项，不是非零编码的个数。

固定源码 trees.c:841–843逐字发射这三个计数字段：

    send_bits(s, lcodes - 257, 5);  /* not +255 as stated in appnote.txt */
    send_bits(s, dcodes - 1,   5);
    send_bits(s, blcodes - 4,  4);  /* not -3 as stated in appnote.txt */

线路上对应这三个计数的字段叫 HLIT、HDIST、HCLEN。它们保存“项数减去允许的最小项数”，因为无需表示更小的计数，这样可以节省位数。例如 lcodes=257、dcodes=1、blcodes=4 时，三个字段的数值依次是 257−257=0、1−1=0、4−4=0，位宽分别为 5、5、4。接收者加回偏移，知道接下来先读四项三位原始码长，对应符号 16、17、18、0；用这棵小树解开后续指令后，必须恢复 257 项字面量／长度码长和一项距离码长。这里仅演示计数字段的换算，没有指定各项码长，也没有构造或声称一个合法整块。

这也解释了为何不需要无限多层“小树描述另一棵树”：最外层直接发送三位数值，接收者已经知道怎样读取它们。完整依赖关系现在收束起来：原始码长描述小树；小树解码重复指令；指令恢复数据树码长；数据树码长确定载荷编码。build_bl_tree 把指令成本、原始描述和计数字段都纳入动态编码候选的记账，块选择随后才可把它与固定编码、原样存储比较。

完整块的实现到格式证明尚未完成：树论证还要求建立实际调用者的前提，让修复后的码长、两遍描述扫描和最终写出的同一组比特连接起来。下一篇证明思路解释怎样把保留森林、修复记账、规范分配和描述的两遍扫描，连接成可以组合的论证。