跳到正文
参考文档 / ZLIB × LEAN

adler32

用 32 位字节计数更新 Adler-32。

完整章节与共同规则 ↗
uLong ZEXPORT adler32(uLong adler, const Bytef *buf, uInt len);

用 32 位字节计数更新 Adler-32。

返回值与后续调用

返回值类型。 uLong — 32 位校验和值

返回本次更新后的 Adler-32,或新校验和的初始值。

adler32()
返回值 含义与出现条件 调用者接下来
1
初始值
buf == NULL 且 len == 0,任意传入校验和值;不读取字节。 以 1 开始处理新序列。
reduce(adler)
空范围约化种子
buf 非 NULL 且 len == 0;空范围也允许尾后指针。reduce 取低 32 位,并把其中两个 16 位的半部各自对 65521 取模。adler 是真实的 Adler-32 时,结果等于 low32(adler),因为真实 Adler-32 的两个半部都小于 65521。 保留该值,继续下一段更新。
Adler-32(A || buf)
追加后的校验和
buf 指向 len 个可读字节,len > 0,且 adler 的低 32 位是 A 的 Adler-32。 将此值用于后续更新或与预期校验和比较。

判读要点。

  • len 是 uInt,最多 2^32 - 1 字节;更大的计数转换为 uInt 时,在调用之前就丢失了高位。更大的计数须用 _z 形式或多次更新。

调用条件与效果

定义域 受限定义域。当 buf 非 NULL 时,效果为只读。

前置条件 buf 为 NULL 且 len == 0,或它指向 len 个可读字节。 要满足校验和后置条件,adler 的低 32 位须为 A 的 Adler-32。

内存与状态效果 保持全部内存与所有权。只读取给定范围。

adler32_z 关于伪造种子的范围在这里同样适用。

证明目标。

  • 目标。 Goal.adler32_safety(Safety/Checksums.lean);必需。定理:ZlibF.Spec.Public.StatelessSafetyProof.adler32_safety(public-stateless-safety.lean)。
  • 适用条件。 buf 为 NULL 且 len == 0;或者 buf 指向 len 个可读字节(AdlerBufferBytes)。len == 0 时,允许指向对象末尾之后一个位置的指针。
  • 无条件覆盖。 每一个 adler,包括不是校验和的值;字节的每一种内容;每一个堆,无论其中有没有库的表。
  • 保证。
    • 返回。 调用返回。
    • 状态、写入、分配。 都没有:调用之后的堆就是调用之前的堆。
  • 不在本目标内。 buf 为 NULL 而 len 非零:在所有目标之外;这比 zlib.h 窄(见偏离记录中“Adler 初始化查询”一行)。返回的值:功能目标 Goal.adler32(不在计划内;已有定理证明它)。
完整返回条件与边界

返回与保证 返回值与 adler32_z(adler, buf, len) 完全相同。 NULL、零长度查询返回 1。非 NULL 的空范围返回 adler 的低 32 位, 其中两个 16 位的半部各自对 65521 取模;真实的校验和因此保持不变。

本组共同前提与范围

逐块计算缓冲区的校验和,或组合各自独立处理的字节序列的校验和,而不重新读取数据。 下文的字节序列 A 和 B 是普通数据;契约使用这些序列的 Adler-32 或 CRC-32。例如先处理 A,再处理 B,可以把 A 的校验和作为下一次更新的起始值;若 A、B 是各自独立处理的,组合函数给出 A 后接 B 的校验和。

更新函数里的 buf 指向这一批输入,len 是这一批的字节数,传入的 adler 或 crc 是继续计算的起始值。组合函数里的 len2 则只表示后一段 B 的字节数,不是两段总长度。

任务 条目
更新 Adler-32 长度为大小类型、32 位长度
组合 Adler-32 普通偏移类型、显式 64 位偏移类型
更新 CRC-32 长度为大小类型、32 位长度
组合 CRC-32 普通偏移类型、显式 64 位偏移类型
复用 CRC 组合算子 生成、用 64 位长度生成、应用
查看字节表 get_crc_table

这些契约遵循固定版本的 adler32.c、crc32.c 和 zlib.h,采用默认 LP64 Linux 静态构建。 没有补丁改动这两个 C 文件(见补丁说明)。 动态建表、硬件 CRC 钩子和生成表的可执行程序不在覆盖范围内 (见构建与平台)。 任何校验和条目都不写入状态、不分配或释放内存,也不执行 I/O。 特殊数值结果是普通值,而不是错误码。定义域和效果互相独立,见契约约定。 这些是聚焦契约:前置条件描述通常的正确用法,有意比函数实际接受的范围窄。 超出前置条件的调用并不因此就是未定义行为,也不一定返回错误码。

已证明的内容。 只证明安全性(见安全性):每个安全目标(Safety/Checksums.lean)说的是调用返回,并且调用之后的堆就是调用之前的堆。它对返回的数值什么也没说。各条目在“证明目标”下给出自己的目标,所用的五项和固定用语由阅读证明目标段落定义。证明所假设的是那里列出的条件,而不是文档中的前置条件。后置条件、返回值表和各项说明描述的是功能行为:它们读自 C 源码,凡是没有定理陈述的,都尚未由证明确认;安全结论不需要它们。进度说明哪些目标已完成。

CRC 目标对模型的堆有一条前提:堆中的两张 CRC 常量表 crc_table 和 x2n_table 等于翻译后的 crc32.h 中的表(CrcGlobals)。这条前提是对调用开始时的堆所作的假设; 没有定理对任意的堆推出它。它是对模型的条件,不是调用者的义务 (见模型的限制)。 关于它证明了两件事。库堆(流目标的起点) 满足它(crc_globals_of_library)。每个校验和目标都返回未改变的堆,所以调用之后这条前提仍然成立。

实用校验和契约使用真实字节序列 A 和 B。各校验和独立计算:Adler-32 从 1 开始, CRC-32 从 0 开始。这些契约有意不对伪造校验和值作功能保证。 Functional/Checksums.lean 中的功能目标还描述任意种子及精确标量结果。 Adler 条目及其 Lean 目标(安全目标和功能目标)都要求 NULL 初始化查询的长度为零 (Common/Checksums.lean 中的 AdlerBufferBytes)。 见偏离记录。

此构建中,uLong 和 z_size_t 是无符号 64 位类型;uInt 是无符号 32 位类型。 z_off_t 和 z_off64_t 是有符号 64 位类型。输入校验和值中高于第 31 位的位被忽略; 返回校验和值可用 32 位表示。显式 *64 声明取决于头文件的大文件特性宏。

安全目标

ZlibF.Spec.Public.Goal.adler32_safety

状态:完成 · 结论的状态

/-- `uLong adler32(uLong adler, const Bytef *buf, uInt len)`.
**Safety of `adler32`**: on a readable buffer of `len` bytes, or `NULL` with `len = 0`
(`AdlerBufferBytes`; narrower than zlib.h, `docs/en/deviations.md`), the call returns and the heap
is unchanged. -/
def Goal.adler32_safety : Prop :=
  ∀ (h : Heap) (seed : UInt64) (pointer : BPtr) (length : UInt32) (bytes : List UInt8),
    AdlerBufferBytes h pointer length.toNat bytes →
    ∃ value, C.run (Zlib.Adler32.adler32 seed pointer length) h = .ok (value, h)
相关定义与源码 ↗

功能契约(安全之外)

ZlibF.Spec.Public.Goal.adler32

状态:完成 · 结论的状态

/-- `uLong adler32(uLong adler, const Bytef *buf, uInt len)`.
The public 32-bit length entry has the same buffer domain and exact result as `_z`.
NULL queries require zero length, as recorded in `docs/en/deviations.md`. -/
def Goal.adler32 : Prop :=
  ∀ (h : Heap) (seed : UInt64) (pointer : BPtr) (length : UInt32) (bytes : List UInt8),
    AdlerBufferBytes h pointer length.toNat bytes →
    C.run (Zlib.Adler32.adler32 seed pointer length) h =
      .ok ((if pointer = .null then 1 else adlerValue seed bytes), h)
相关定义与源码 ↗
ZLIB × LEAN

目录

正在阅读adler32