解码表的实际构造

变长编码很容易画成树：每读一位就选择一条分支，走到符号就停。解码器希望每个符号少做几步，所以先建一张数组表，一次看几位，就知道“已经找到答案”还是“转到较小的表继续查”。本章解释怎样建表，同时保持原编码的含义。

本例需要的结果可以先说清楚：输入给出每个符号有多少编码位，建表后，解码器只凭接下来的几位就能找到符号，并知道应当消费几位。规范编码让码长唯一决定这些码字的分配顺序：先按码长从短到长，同码长按符号数值排列。

先把小例子的表建出来

按数值顺序取符号 A、B、C、D，码长为 [1,2,3,3]。规范分配得到 A=0、B=10、C=110、D=111。这是教学符号，不是完整 DEFLATE 块。请求首次查两位，这一级叫作根表；更长的码转到子表继续查。

依次做这些事：

1. 统计出一个一位符号、一个两位符号和两个三位符号。它们恰好填满一棵二叉编码树。
2. 按码长顺序访问 A、B、C、D，依次分配规范编码。
3. 把 A 放到下一个输入位为 0 的两个根槽。多查看的一位属于后续输入，无论是 0 还是 1，都必须返回 A，且只消费一位。
4. 把 B 放到它的根槽。C、D 共用一个根槽，再用第三位在两项子表中区分。

输入章节 把下一位放在整数最低位置。因此下表索引采用整数写法，下一个输入位在右边：

子表索引 0 得到 C、1 得到 D，各再消费一位。于是 AD 先经根槽 10 得到 A，再经根槽 11 和子表 1 得到 D。下面跟踪 C 怎样构造这个结果，不能预先假定它已经成立。

回到实际接口，inflate_table 接收每个符号的码长、字母表类型、请求的首次查表宽度，以及调用者提供的表空间和临时空间。输出是填好的表、实际首次查表宽度、推进后的表指针和返回码。码长零表示符号不使用。字母表是某一张表允许返回的符号集合。源码把“描述码长的符号”这一组叫 CODES，把字面量／长度符号这一组叫 LENS，把距离符号这一组叫 DISTS。动态块先用第一组描述后两张表的码长。字面量就是直接输出的字节，长度和距离则描述从历史中复制。

码长计数与已占空间

inflate_table 用 lens 保存输入码长，用 count 记录每种码长有多少个符号。它先清零计数，再为每个符号下标 sym 递增 count[lens[sym]]。零码长表示未使用。最短和最长的非零码长以位为单位，分别保存为 min 和 max；首次查表需要的位数叫 root。本例中 min = 1、max = 3，请求的 root = 2 已在其中。若请求超出这个范围，就改成最近的端点。根宽度为两位表示四个表项，不是两个表项。

构造器随后检查这些码长能否放下。从一个可用根槽开始，每向下一层，把空闲槽翻倍，再减去放在该层的符号数。下面是检查过程的教学伪代码，不是 C 节选。其中 l 是以位计的候选码长，count[l] 是使用该码长的符号数，left 记录该深度还有多少空位置。遍历到 15，是因为 DEFLATE 的字面量／长度码和距离码最长为 15 位。

left = 1
对码长 l 从 1 遍历到 15：
    left = 2 * left - count[l]

本例的剩余量依次为 2 - 1 = 1、2 - 1 = 1、2 - 2 = 0，更深处保持零。若有三个一位符号，第一层就得到 2 - 3 = -1：二叉前缀编码放不下。

结果为负表示过度订阅，返回 -1。最终有正剩余量，表示编码不完整。源码不会接受所有不完整编码：除单独处理的空表外，仅在类型不是 CODES、且最大码长为一时允许正剩余量。被接受的非空不完整情形，恰有一个一位符号。

偏移与稳定符号顺序

码长决定每层应有多少个码，但同层符号还需要确定顺序。临时数组 work 保存这个顺序；offs 记录每种码长的下一个可用位置。offs[1] = 0，offs[l+1] = offs[l] + count[l] 给出每种码长在临时数组 work 中的起始槽位。

对码长 [1,2,3,3]，相关计数为 [1,1,2]，起始偏移为 0,1,2。按符号数值顺序扫描，把 A 写到 0、B 写到 1、C 写到 2，再把 D 写到 3。每次存储后递增该码长的偏移。C 和 D 保持符号顺序，因为扫描是稳定的；这里不需要比较排序。

换一个原本没有排好序的输入 [3,1,3,2]，得到 B 在前、D 次之，然后 A、C，即 work = [B,D,A,C]。同一过程仍按码长分组，保持组内符号数值顺序。随后主循环遍历这个已经初始化的 work 前缀。若把已递增的偏移与原来的起始值混同，就会丢掉这层连接。

表项字段与含义

写入的每个单元都要告诉读表器做什么、移除几位。先跟踪根表中的 A：它的编码是 0，完整码长为一位，本次查表查看两位，而且尚未移除根位。主循环分别把这四个量叫作 huff = 0、len = 1、curr = 2、drop = 0。huff 把下一个输入位放在整数最低位置；其余三个量都以位计数。进入子表后，drop 记录已经计入的根位数，因此剩余码宽是 len - drop。对每个符号，它构造一个具有三个字段的 code 表项：

对字面量，op = 0，val 是对应字节。长度和距离编码可能表示一个范围，val 是其最小值，称为基值，额外输入位选定其上的偏移。例如，基值 11 加一个值为 1 的额外位，得到长度 12。表项的 op 保存标志 16 加额外位数；块结束用 op = 96。无效项设置标志 64，但没有结束标志 32；保留符号的其他位可以不同。空表的无效标记恰好是 64。表项的 bits 表示本级编码消费量，与位缓冲的总有效位数不同。CODES 表中的直接项则用 val 返回码长符号。链接用 op 表示子表索引宽度，用 val 表示相对原表基址的偏移。

所以，表项不只是一个符号编号。其字段同时控制解析器的控制流和位消费量。查表即使完全在界内，字段错误仍可能解出错误的流。

根表重复填充

根宽度为二时，A 的一位码必须占据低位索引 00 和 10 两个槽。B 占据 01。C 和 D 共享 11，该槽会成为链接。虽然查表查看两位，每个 A 表项仍只消费一位。

为了填满所有等价索引，构造器先求以表项计的步长。固定低 len - drop 位后，相邻等价索引相差 2^(len-drop)，源码把这个步长叫 incr。当前表共有 2^curr 项；fill 从这个大小开始，按步长向前倒着走。here 是准备好的表项，next 指向当前表的第一项。下面是 inflate_table 的真实填表循环，来自固定版本 inftrees.c 第 238–244 行：

incr = 1U << (len - drop);
fill = 1U << curr;
min = fill;
do {
    fill -= incr;
    next[(huff >> drop) + fill] = here;
} while (fill != 0);

here 是已经准备好的表项，next 指向当前表。填 A 时，len=1、drop=0、curr=2、huff=0，所以 incr=2、fill=4。两轮分别写索引 2（10）和索引 0（00），都使用同一个只消费一位的表项。min 在这里暂存当前表大小，供随后推进到下一张表；它已经不再表示最小码长。之后直接推进反转编码，不必反复反转输入。

子表构造

先看本例还没有区分的 C 和 D。两者都有三位编码，前两位相同；根表已经看过这两位，所以只差最后一位。只要建立一张两项子表，就能用 0 与 1 区分它们。没有必要为这个前缀建立一张查满 15 位的大表。

一般情形下，完整码长 len 超过根宽度时，构造器才需要子表。它沿剩余码长的计数向前查看：每加一位，空闲分支翻倍；再扣除这一深度已有的编码，直到当前前缀的编码能够放下。这个过程选择足够的子表宽度，而不是对每个前缀都预留最大深度。

这里 used 统计此前已经预留的全部表项，包括根表，不是输入位数或符号数。构造器把 next 推进到先前各表之后，为新表把 used 增加 2^curr 项，再安装含有新宽度与偏移的根链接。子表内的重复填充先丢弃根位。对本例，额外的一位就能区分 C 和 D。

把四符号例子的地址也算出来。两位根表占 2^2 = 4 项，即相对原表基址的偏移 0 到 3。一位子表需要 2^1 = 2 项，所以从偏移 4 开始，占偏移 4 和 5。预留后，总量为 used = 4 + 2 = 6。

链接要安装在根位选中的槽。mask = (1U << root) - 1 是只保留 huff 低 root 位的掩码，得到的根索引叫 low。root = 2 时，掩码的二进制写法为 11。构造器用下面的真实语句安装根链接，见 inflate_table 的固定版本 inftrees.c 第 290–293 行：

low = huff & mask;
(*table)[low].op = (unsigned char)curr;
(*table)[low].bits = (unsigned char)root;
(*table)[low].val = (unsigned short)(next - *table);

这里 *table 仍指向原表基址，next 指向子表。C、D 共用的前缀得到 low = 3（二进制 11），所以这些赋值写入根表第 3 项。它的 op = 1 表示再取一位作为子表索引，bits = 2 表示消费根表的两位，val = 4 表示子表位于原基址之后四项。消费根位后，索引 0 选择总偏移 4 + 0 = 4 的 C；索引 1 选择总偏移 4 + 1 = 5 的 D。两个叶项各消费最后一位。

根表和子表属于同一段连续预留空间。指针、偏移、已初始化单元与返回的根宽度必须彼此一致。接下来的调用者使用本次实际返回的宽度，不能使用最初请求的宽度。

空输入、错误与预留空间

全零码长进入提前返回分支：写出两个一位无效表项，返回根宽度一，并把表指针推进两个槽。这里的成功表示表已经构造；尝试通过它解码仍会得到无效编码结果。被接受的单符号情形同样要求在有效槽之外明确写入一个无效槽。

默认配置下，LENS 和 DISTS 的容量检查保护 852 项和 592 项的预留量。inflate 状态在 codes 中预留两者之和 1444 项。这些是表项数量，不是字节数，也不是字母表大小。固定版本的 PKZIP_BUG_WORKAROUND 配置另用 854 和 594，不能把默认常量推广到该配置，见固定版本 inftrees.h 第 37–57 行。若要说明每种合法格式编码都会被接受，还需要另一个界；安全地拒绝容量不足，只说明构造器能够安全拒绝。

CODES 调用对码长和根宽度具有更强的前提：码长至多七，请求的根宽度至少七，因此不需要子表，至多使用 128 项。其他类型的容量检查不能代替这些前提。实际辅助函数定义域还包括保留符号；它们必须获得正确的无效解释。

完整构造器到解码器的组合还未完成。一个具体义务是：辅助函数在索引 count 前假设输入码长都在 0..15，但自身不检查这个界，必须由调用者建立。畸形压缩描述仍在公开安全定义域内；被拒绝的码长集合、容量失败和部分写入则需要各自精确的辅助函数结果。接下来阅读 慢速与快速解码，再阅读 证明连接。完整表参考 给出更细的定义域和义务。