位输入与预读

解码器要逐位读取输入，应用程序却只能按字节提供数据。一个字段可能在字节中间结束，下一个字段就从紧接着的一位开始。输入处理的任务是保留这些剩余位，再与后续字节接起来，不能漏位、重复或倒序。

它接收上次保存的位和调用者尚未读取的字节，交出当前字段的值，并留下精确的未消费输入。这个步骤本身还不产生解压字节。算法概览 介绍了字节→符号→输出的全程；本页先跟踪第一步。

按顺序保存接下来的位

假设接下来要读的三位依次是 0、1、1。可以把它们放进一个小整数，下一个要读的位占最低位置：通常的二进制写法就是 110，即十进制 6。从右往左读这个写法，才是输入顺序。只有这三个位置有效。

现在下一个字段需要五位。手上只有三位，所以要先取入一个字节。新字节接在原来三位的后面，不能覆盖它们。这个临时存位的整数称为位缓冲。C 中用 hold 保存它的值，用 bits 记录有效位数。因此起始状态写作 hold = 6、bits = 3。位数不可省略：有效的零位仍然是输入，虽然它对整数数值没有贡献。归一化表示有效部分之上没有置位，可写作 hold < 2^bits；未读字节在逻辑上接在它后面。

用一个具体字节补充

设下一字节为 0xA5 = 165。它提供八位，也从低位置向高位置读取。把它接到已保存的三位之上，得到：

原有位的读取顺序：0、1、1
新字节的读取顺序：1、0、1、0、0、1、0、1
新的 hold = 6 + (165 << 3) = 1326
新的 bits = 3 + 8 = 11

这里的 << 3 表示左移三位：原来的三个位置仍留给 0、1、1，新字节从第 3 位开始占据接下来的八个位置。因此两份内容不会重叠，可以相加。此时还没有解析字段，只是把同一串十一位放进整数。输入游标前进一个字节，但下一个未消费位仍是最初的 0。

源码把“补充一个字节”写成 PULLBYTE 宏：next 指向接下来要读的字节，have 统计调用者尚可提供的字节数，单位是字节而不是位。下面是 inflate 实际使用的宏，取自固定版本 inflate.c 第 366–372 行：

#define PULLBYTE() \
    do { \
        if (have == 0) goto inf_leave; \
        have--; \
        hold += (unsigned long)(*next++) << bits; \
        bits += 8; \
    } while (0)

have 是调用者当前还提供多少可读字节，next 指向下一个字节。本例有字节可取：have-- 扣除一个，*next++ 读取 165 并推进游标，移位把它放到原来三位之上。若没有字节，第一条检查就在读取前离开。翻译后的 PULLBYTE 保持这个源码顺序。

字段需要的位数记作 n，解析器用 NEEDBITS(n) 提出这个请求。宏重复取入，直到缓冲至少有 n 位。它可能已经取入一些字节，却仍在凑齐 n 位前耗尽当前输入。那些位必须留给下一次调用；输入耗尽不能假装字段已经读完，也不能清空位缓冲。

先读字段，再消费它

回到需要五位的字段。怎样从 1326 取出这五位？先用 2^5 - 1 = 31 得到低五位全为 1 的掩码，再做按位与：1326 & 31 = 14。这样高于第 4 位的部分全部被遮掉，留下的五位是 01110，即十进制 14。查看这个值不会改变位缓冲。解析器接受该字段后，才恰好移除五位：hold 变成 1326 >> 5 = 41，bits 变成六。下一个字段从这六位开始。

C 中，BITS(n) 掩码取得低 n 位；DROPBITS(n) 右移，并从有效位数中减去 n，见真实宏第 383–391 行。调用处必须先建立位数足够、移位宽度合法的条件。看到一位和消费一位是不同的事。

这个例子区分了三份账目：从调用者取入的字节、解析器已解释的位，以及已产生的解压字节。头部字段可以消费位而不输出；已经解码的匹配可以输出而不再读输入。一个游标不能同时表示这三个量。

连续解出两个符号

Huffman 编码为每个符号分配长短不一的位串。使用教学编码 A=0、B=10、C=110、D=111。消息 AD 按 0 | 111 到达。只展示这四个有意义的位时，得到 hold = 1110、bits = 4。这不是完整 DEFLATE 块，也不是只取四位的字节读取。

查表可以一次查看两位。首先查的表叫根表；较长的码还可以转到较小的子表，继续解释余下的位。下一章 解释怎样建表，这里先看读表需要什么：

第一次查表看到了 A 的完整编码，还多看了 D 的第一位。若移除两位，就会丢掉 D 的开头。因此，表项必须记录实际消费量，它可能小于查表宽度。

普通数值字段按最低有效位先到达。Huffman 码字则按最高有效的编码位先到达，字节位置仍从低到高读取。于是码字 110 在位缓冲中对应整数 011。建表器按这个顺序安排表项，解码器不必反转每个输入字节。

提前读取，也要保留输入

为了 A 多看的一位叫作预读：看到了稍后才需要的输入。快速解码器还可能提前取入整个字节。一个符号的含义由支撑它的前缀决定；取了一个字节，不表示其中所有位都属于已经产生的输出。

快速路径退出时，把未使用的完整字节退回输入游标，只留下不足八位。若缓冲 19 位，就退回两个字节，留下三位。顺序仍须描述同一条未消费位流。慢速与快速复制 会继续跟踪这份账目。

解析器还使用状态的局部副本。LOAD 从流中取得输入、输出游标和已保存位；RESTORE 在边界写回。函数体运行时，堆字段和局部量不必始终相等。流状态 继续解释跨调用的这些边界。

证明需要保持什么

要论证的保持关系很容易表述：位缓冲接上未读字节，恰好就是未消费输入。已有的 BitInv 和 stream 形式化了这个关系，以及可读存储和归一化条件。解码器证明章节 解释它如何连接到表和输出。

完整解码器的组合证明还未完成：它需要在每次取入处建立存活可读字节和有效指针推进，在每个移位处建立符合所选位宽的界。默认 LP64 翻译使用 64 位的 hold 字，但这个宽度不能代替各处请求量的具体界。

输入耗尽、数据畸形或工作未完成时的精确行为，见 inflate 和流式解码参考。这些情形仍在范围内，不能由很小的成功轨迹排除。