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

crc32_combine_op

使用预先生成的算子,计算 A 后接 B 的 CRC-32。

完整章节与共同规则 ↗
uLong ZEXPORT crc32_combine_op(uLong crc1, uLong crc2, uLong op);

使用预先生成的算子,计算 A 后接 B 的 CRC-32。

返回值与后续调用

返回值类型。 uLong — CRC-32 校验和值或算子拒绝值

将先前生成的算子应用于两个独立 CRC。零算子有单独拒绝结果。

crc32_combine_op()
返回值 含义与出现条件 调用者接下来
0
零算子被拒绝
op == 0;可传任意校验和值。 用 B 的真实长度重新生成有效算子。
CRC-32(A || B)
拼接 CRC
crc1、crc2 的低 32 位是分别从 0 开始计算的 A、B 的 CRC;op 是为 B 的长度生成且未改动的算子。 将结果作为拼接 CRC;相同 B 长度可复用此算子。

判读要点。

  • 有效 CRC 也可能为 0,返回值本身不能区分拒绝与有效结果。
  • 伪造算子、错误长度的算子不在功能保证内。

调用条件与效果

定义域 受限定义域。效果为纯计算。

前置条件 要得到拼接结果,crc1 和 crc2 的低 32 位须分别为 A 和 B 各自从 0 开始计算的 CRC-32。op 是按 B 的长度调用 crc32_combine_gen 或 crc32_combine_gen64 得到、且未经修改的结果。 独立的拒绝情形允许 op == 0 配合任意校验和参数。

内存与状态效果 保持全部内存与所有权。不读取缓冲区或流状态。

若 LP64 op 非零、但低 32 位全为零,调用不会返回:uLong 有 64 位, multmodp 中的循环只在 op 的第 31 位到第 0 位中寻找置位的位,此外没有别的出口。 crc32_combine_op_diverges 对翻译证明了这一点:运行以模型的燃料耗尽故障结束 (见 CRC-32 证明)。对 C 而言,这是对源码的解读。 这样的 op 不在下面安全目标的前提之内;该前提只涵盖生成函数返回的算子:生成的算子小于 2^32,并且要么为零,要么有置位的位。

证明目标。

  • 目标。 Goal.crc32_combine_op_safety(Safety/Checksums.lean);必需。定理:ZlibF.Spec.Public.StatelessSafetyProof.crc32_combine_op_safety(public-stateless-safety.lean)。
  • 适用条件:
    1. 堆中有库的两张 CRC 常量表(CrcGlobals),即本页开头所述的对模型的条件;
    2. op 是 crc32_combine_gen 或 crc32_combine_gen64 对某个 len2 返回的值。这就是 zlib.h 给出的定义域。
  • 无条件覆盖。 每一个 crc1 和 crc2,包括伪造的校验和;生成算子时所用的每一个 len2,包括负值(此时算子为 0)。
  • 保证。
    • 返回。 调用返回。
    • 状态、写入、分配。 都没有:调用之后的堆就是调用之前的堆。
  • 不在本目标内。 不是由生成函数返回的 op:在所有目标之外(见偏离记录中“CRC 组合算子”一行)。返回的值:功能目标 Goal.crc32_combine_op(不在计划内;已有定理证明它)。
完整返回条件与边界

返回与保证 返回 A 后接 B 的 CRC-32。若 op == 0,返回 0。 用于空 B 的算子保持 A 的校验和不变。

本组共同前提与范围

逐块计算缓冲区的校验和,或组合各自独立处理的字节序列的校验和,而不重新读取数据。 下文的字节序列 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.crc32_combine_op_safety

状态:完成 · 结论的状态

/-- `uLong crc32_combine_op(uLong crc1, uLong crc2, uLong op)`.
**Safety of `crc32_combine_op`**: for an operator `op` that `crc32_combine_gen` or
`crc32_combine_gen64` returned (zlib.h's domain), the call returns and the heap is unchanged. -/
def Goal.crc32_combine_op_safety : Prop :=
  ∀ (h : Heap) (first second : UInt64) (length : Int64) (op : UInt64), CrcGlobals h →
    (C.run (Zlib.Crc32.crc32_combine_gen length) h = .ok (op, h) ∨
     C.run (Zlib.Crc32.crc32_combine_gen64 length) h = .ok (op, h)) →
    ∃ value, C.run (Zlib.Crc32.crc32_combine_op first second op) h = .ok (value, h)
相关定义与源码 ↗

功能契约(安全之外)

ZlibF.Spec.Public.Goal.crc32_combine_op

状态:完成 · 结论的状态

/-- `uLong crc32_combine_op(uLong crc1, uLong crc2, uLong op)`.
`zlib.h` requires an operator generated from a length by `crc32_combine_gen`. The domain here
is exactly those mathematical operators, including its zero rejection result. Arbitrary forged
operators are not promised termination. Every permitted call has the polynomial result and
preserves the whole heap. -/
def Goal.crc32_combine_op : Prop :=
  ∀ (h : Heap) (first second : UInt64) (length : Int64), CrcGlobals h →
    C.run (Zlib.Crc32.crc32_combine_op first second (crcOperator length)) h =
      .ok (crcCombined first second length, h)
相关定义与源码 ↗
ZLIB × LEAN

目录

正在阅读crc32_combine_op