Adler-32 的递推与分块

假设一个流本应恢复出 AB，但某处字节损坏，让它恢复出 AC。两者都是普通字节串，仅仅解码成功还不能分辨发送者原本要传哪一个。因此，zlib 封装附带 Adler-32 校验和：发送者把原始字节算成一个 32 位摘要；接收者对恢复的字节重新计算，再比较两个数。不同就检测到了损坏；相同是完整性检查通过，不保证没有别的字节串恰好得到同一校验和。

一次更新接收已有校验和、可读字节区间及其长度，返回计入这段字节后的校验和。新序列从 1 开始。输入是未压缩数据，不是 Huffman 码。如果解压器第一次交付 A，第二次交付 B，第二次更新必须接着第一次算：尾部字段对应整个 AB。

下面先看校验和保留了什么信息，再逐字节计算 ABABABAB。实际 C 为了减少工作，会把一部分算术延后。最后区分继续处理下个缓冲区与组合两个独立校验和。这两种操作都不需要保留先前的字节。

两个累加器

一个累加器记录字节值之和，另一个记录历次累加结果之和。因此，较早的字节会影响更多项。把这两个和称为 a、s。为了让每个和都能放进结果的一半，计算时取模 M = 65521；“取模”就是保留除以 M 后的余数。从 a = 1、s = 0 开始，对下一个字节值 b 计算：

a := (a + b) mod M
s := (s + a) mod M

第二行使用更新后的 a：第一个 A 让两个和都变成 66，接着 B 让它们变成 132 和 198。若 B 损坏成 C，两个和则会变成 133 和 199，校验和随之改变。若 A、B 交换位置，字节和不变，前缀和却会改变。推广到任意输入，把长度记作 n，字节值依次记作 b₁ 到 bₙ。取余之前：

a = 1 + b₁ + b₂ + ... + bₙ
s = n + n·b₁ + (n−1)·b₂ + ... + bₙ

取余后，两侧模 M 的余数仍然相同。第二个式子的权重说明顺序为什么有影响：第一个字节参与全部 n 个前缀，最后一个字节只参与一个。

返回的校验和把约简后的 a 放在低 16 位，把 s 放在高 16 位，即 a | (s << 16)。<< 16 把 s 移到高半，按位或运算 | 把这两个不重叠的半部拼起来。这种数值布局与封装中的字节顺序是两件事。zlib 尾部按最高有效字节在前的顺序发送四个校验和字节。

八个字节

ASCII A 为 65，B 为 66。这个短例子不需要约简：

第二个字节使 a 变成 66 + 66 = 132，使 s 变成 66 + 132 = 198。第二个累加器不是只加上新字节。因此，这八个字节对应的最终 zlib 校验字段是 09 3c 02 0d。

这些数值已通过独立的逐字节递推和固定版本 C 校验和函数核对。这是对该例子的有限检查，不是覆盖全部输入的正确性结论。

批次与约简

上表逐字节执行数学规则。对于长缓冲区，每次加法后都取余会反复付出额外开销。先累加、稍后再取余，余数仍然相同，条件是中途机器和不能溢出。因此，zlib 把有界数量的字节步骤放进一个批次。

C 既要保存校验和，也要记录读到缓冲区的哪里。两个累加和分别叫 adler（对应 a）和 sum2（对应 s）；buf 指向接下来要读的字节，len 计数还剩多少字节。数学模数 M 在源码中叫 BASE。每批至多处理 NMAX = 5552 个字节，再对两个和取余；下面会推导这个上限。批次内部的 C 计数器 n 计数十六字节组，不是单个字节。宏参数 i 是相对 buf 的字节偏移；十六步展开依次使用偏移 0 到 15。

下面是单字节宏和完整批次循环的主体，来自固定版本 adler32.c 的 14–18 行及 97–106 行。空行隔开两个节选：

#define DO1(buf,i)  {adler += (buf)[i]; sum2 += adler;}

    while (len >= NMAX) {
        len -= NMAX;
        n = NMAX / 16;
        do {
            DO16(buf);
            buf += 16;
        } while (--n);
        MOD(adler);
        MOD(sum2);
    }

DO1 读一个字节，先加进第一个和，再把更新后的第一个和加进第二个和。DO16 按顺序展开十六次。while 条件确认还有完整一批，才减少 len。n 计数该批的十六字节组；每组处理后，buf 前进 16。--n 在这些组完成后结束内循环。最后两行 MOD 对和取余；所选默认分支中，两者都展开为 % BASE。证明必须把这些指针前进、延迟取余与逐字节规则联系起来，不能直接用简单规则代替 C。

为什么 NMAX 选择 5552 字节？把上次取余后处理的字节数记为 m，与 C 中计数组数的 n 区分。从已约简、各自至多为 M−1 的分量开始，每个字节最多为 255，第二个和满足：

s ≤ (m + 1)(M − 1) + 255·m(m + 1)/2

第一项涵盖起始第二个和，以及起始第一个和的 m 次贡献。末项涵盖按 m,m−1,…,1 加权的最坏字节贡献。当 m = 5552 时，右侧为 4294690200，小于 2^32 − 1。当 m = 5553 时，它变成 4296171735，超过该上限。这就是源码选择 NMAX = 5552 的原因。

每个完整批次执行 347 组，每组 16 个字节步骤。展开分组减少循环开销，同时保留每个新 a 到 s 的依赖。余下的数据先按 16 个字节分组，再逐字节处理。独立的短输入和单字节路径避免不必要的准备工作。

所选 LP64 构建中，指针和 unsigned long 都是 64 位，因此累加和比上面的 32 位界有更大余量，但实现保留相同的批次大小。另一个可选源码分支利用 2^16 ≡ 15 (mod 65521) 替代除法。该恒等式解释了为何可以把高位折回低位，却不表示那个分支属于这里描述的默认执行。

缓冲区边界

回到先交付 A、再交付 B 的解压器。第一次从 1 开始更新，返回 00420042。把这个返回值作为第二次种子，函数就把它拆回 a=66,s=66。读入 B 后返回 00c60084，恰好是 AB 的普通校验和。若第二次重新从 1 开始，得到的只是 B 的 00430043，A 的贡献就丢失了。

因此，应用输入的拆分点不必与批次边界一致。一次调用可以在一个字节后结束，下一次继续使用打包、约简后的两个和。校验和状态描述已接收的字节，不描述它们由多少次调用提供。

校验和函数自身不分配、不保留调用者指针，也不写入输入。外层压缩器或解压器另外决定哪些新处理的字节应计入封装校验和。

独立分块

假设两个工作单元已各自从 1 开始算出 A、B 的校验和，只留下这两个数。这里的工作单元可以是两个线程，也可以是分别处理两个文件分块的程序。把 B 的校验和传作更新种子，并不能连接两者：更新函数接收的是字节，不是第二个校验和。组合函数则利用两个摘要和第二段长度，算出连接后的校验和，不必重读任何一段。

推广到先 X 后 Y，把独立计算的分量记作 (aX,sX)、(aY,sY)。用 n 表示 Y 的字节长度，(aXY,sXY) 表示要得到的连接结果。则模 M 有：

aXY = aX + aY − 1
sXY = sX + sY + n·(aX − 1)

减一去掉 Y 多带的一份初始值。长度项表示：X 的字节和会对 Y 中每一个新前缀作出贡献。这里需要的是 Y 的长度，不是 X 或两者之和。

当 X=A、Y=B 时，分量分别为 (66,66)、(67,67)。取 n=1，结果为 (132,198)，仍是 00c60084。Y 很大时，实现先把它的非负长度模 65521 约简，不需要扫描 Y。Adler 组合使用这种带长度权重的算术，而不是 CRC-32 使用的多项式幂。

校验和入口

adler32_z 使用 z_size_t 字节计数，在所选构建中为 64 位；adler32 使用 32 位计数。大计数应使用多个更新调用或更宽的入口，不应先截断。

adler32_combine 和 adler32_combine64 使用 Y 的有符号长度，组合独立开始的校验和。负长度返回 0xffffffff。真正的空 Y 校验和为 1，会保持 X 的校验和。

这里的“种子”是更新之前传入的校验和值。正常的接续种子来自先前的计算结果；任意种子则是调用者提供的整数，未必对应真实前缀。NULL 表示没有提供输入指针。精确的 NULL 和任意种子情况很重要：本项目的 Adler 初始化查询要求 NULL 配合零长度。伪造种子不一定遵循规范的单字节递推。校验和证明章节 解释这些定义域，以及上述等式怎样连接到实际内存和机器算术。