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

compressBound_z

计算为默认 zlib 压缩缓冲区确定容量所用的数值上界。

完整章节与共同规则 ↗
z_size_t ZEXPORT compressBound_z(z_size_t sourceLen);

计算为默认 zlib 压缩缓冲区确定容量所用的数值上界。

返回值与后续调用

返回值类型。 z_size_t — 饱和的压缩容量数值

计算默认压缩设置使用的容量数值,不分配缓冲区。

compressBound_z()
返回值 含义与出现条件 调用者接下来
min(2^64 - 1, n + (n >> 12) + (n >> 14) + (n >> 25) + 13)
容量数值
n = sourceLen,可取任意 64 位无符号值;按数学整数求和,再饱和至最大值。n == 0 时返回 13。 将数值用于规划有效目的缓冲区容量。

调用条件与效果

定义域 完整类型定义域。

前置条件 完整类型定义域:每个 64 位 sourceLen,包括零和最大值。

内存与状态效果 纯计算。没有指针访问、分配、状态变化或错误返回。

范围。 本契约规定数值。这个上界是为使用默认封装、窗口和内存设置的压缩而设的, compress 正是这样使用的。它不为任意裸流或 gzip 流的设置给出上界。

证明目标。

  • 目标。 Goal.compressBound_z(Functional/Queries.lean);必需。它是这个函数的完整契约,同时充当它的安全目标;安全目标没有另行陈述。定理:ZlibF.Spec.Public.Proofs.compressBound_z(public-compress-bound.lean)。
  • 适用条件。 始终适用:命题没有前提。
  • 无条件覆盖。 每一个 sourceLen。
  • 保证。
    • 返回。 翻译是一个从参数到结果的全函数。它不接受堆,也没有故障分支,所以调用对每个参数都返回;本目标另外说明结果是后置条件中给出的饱和公式。
    • 状态、写入、分配。 都没有:这个函数不访问内存。
  • 不在本目标内。 压缩器的输出能放进这么大的目的缓冲区。对翻译后的 compress 和 compress_z,在每次分配都成功时,Goal.compress_completes 和 Goal.compress_z_completes 陈述了这一点(见往返)。对 compress2 的其他级别,定理 compress_bound_adequate 陈述了这一点,但只针对不涉及堆的 API 模型;没有定理说翻译后的 compress2 遵循这个模型。
完整返回条件与边界

返回与保证 对 n = sourceLen,返回 min(2^64 - 1, n + (n >> 12) + (n >> 14) + (n >> 25) + 13),其中和按数学整数解释。 零得到 13;和溢出时得到最大值。

本组共同前提与范围

调用时若已知完整的输入和输出容量,可使用缓冲区工具。它们在内部管理临时流。 需要增量 I/O、其他封装、字典或显式刷新边界时,应使用流式接口页面。

任务 条目
压缩缓冲区 选择级别、默认级别、确定目的缓冲区容量
解压缓冲区 报告已消费输入、仅报告输出
查询库信息 版本、编译标志、错误文本

这些契约遵循固定版本的 compress.c、uncompr.c、zutil.c 和 zlib.h,采用默认 LP64 Linux 构建。 没有补丁改动这三个 C 文件(见补丁说明)。 _z 形式使用 z_size_t;普通形式使用 uLong。这里两者均为 64 位。 定义域和效果标签见契约约定。 这些是聚焦契约:前置条件描述通常的正确用法,有意比函数实际接受的范围窄。 超出前置条件的调用并不因此就是未定义行为,也不一定返回错误码。

已证明的内容。 只证明安全性:每次调用都返回,没有未定义行为和内存错误,只写其目标指明的内容,并且不泄漏(见安全性)。各条目在“证明目标”下给出自己的目标,所用的五项和固定用语由阅读证明目标段落定义:目标及其定理;目标适用的条件,按 Lean 命题中的顺序列出;对每一个取值都覆盖的内容;保证的内容(返回、状态、写入、分配);以及留给其他目标的内容。证明所假设的是那里列出的条件,而不是文档中的前置条件。后置条件、返回值表和各项说明描述的是功能行为:它们读自 C 源码,凡是没有定理陈述的,都尚未由证明确认;安全结论不需要它们。哪些目标已完成,见进度。

缓冲区工具的安全目标实例化三个命题 (Common/Utilities.lean):四个压缩函数用 CompressorSafety,uncompress2 和 uncompress2_z 用 UncompressCountedSafe, uncompress 和 uncompress_z 用 UncompressSingleSafe。

缓冲区工具使用 zlib 封装和默认设置,创建并释放一个局部流。流记录是自动变量,不是堆块,所以它不占用任何一次分配尝试。一次调用的分配尝试都来自编解码器。compress* 调用至多尝试五次分配,全部在 deflateInit 中:状态、窗口、prev、head 和待输出缓冲区;当它拒绝参数或级别时,一次也不尝试。uncompress* 调用在 inflateInit 中尝试分配解码器状态,并在解码需要时于 inflate 内尝试分配窗口。

先说明长度的约定:sourceLen 指定可读输入的字节数;*destLen 在调用前是目的数组的可写容量,调用后改为实际写入量。例如目的缓冲区有 1000 字节容量、最终写入 120 字节,调用前应设置 *destLen = 1000,成功返回后读取到 120。这个长度单元自身也是需要保持存活、可读写的调用者存储。uncompress2_z 的 *sourceLen 同样在调用前给出可用的输入字节数,返回后报告已消费的字节数。

上界函数只计算一个数,并不分配目的数组。

flowchart LR
    B["compressBound"] --> C["compress / compress2"]
    C --> Z["zlib 流"] --> U["uncompress / uncompress2"]
    U --> D["解码字节"]

通用约定

缓冲区调用的定义域限于有效内存:非 NULL 源覆盖指定的可读输入; 非 NULL 目的缓冲区覆盖指定的可写容量。非 NULL 长度指针指向可读写的标量单元。 输入、输出和长度单元互相分离,包括同时出现的两个长度单元。 调用期间,调用者保持这些对象存活且不修改它们。 各条目分别说明允许的 NULL 情形。其他无效指针不在此范围内。 处理解压错误不要求压缩数据有效。

通用效果。 范围内的每次调用都终止,且不产生故障。 缓冲区调用保持输入以及输出、长度单元以外的内存不变,写入不超过原始容量。 返回前释放所有内部分配,包括分配失败路径;调用不给调用者留下局部流,也不留下它自己做的分配。 返回指针的查询,返回的是借用的不可变存储。 “证明目标”下列出的安全目标陈述了这些效果,借用存储那一条除外;输出的内容属于功能行为。

模型中的长度单元。 对 compress、compress2 及它们的 _z 形式,翻译把 *destLen 作为值传递:函数接收容量(或者 destLen 为 NULL 这一事实),并返回要存入的长度。这个单元在模型中不是内存,所以这四个函数的安全目标无法谈论与源或目的缓冲区重叠的长度单元(见偏离记录中“整缓冲区压缩”一行)。对 uncompress 系列,长度单元是内存,每个为 8 个可读可写的字节,它们与缓冲区的分离是目标中写明的条件。

形式化契约

ZlibF.Spec.Public.Goal.compressBound_z

状态:完成 · 结论的状态

/-- `z_size_t compressBound_z(z_size_t sourceLen)`.
Every LP64 input returns the saturated public bound formula. No heap is accessed. -/
def Goal.compressBound_z : Prop :=
  ∀ n : UInt64, (Zlib.Compress.compressBound_z n).toNat = Api.compressBound n.toNat
相关定义与源码 ↗
ZLIB × LEAN

目录

正在阅读compressBound_z