deflateBound_z
根据流当前的配置和封装计算大小上界。
完整章节与共同规则 ↗z_size_t ZEXPORT deflateBound_z(z_streamp strm, z_size_t sourceLen);
根据流当前的配置和封装计算大小上界。
这个查询回答“为整份输入准备多少输出字节才足够”。sourceLen 是输入字节数,下面记作 n;w 是头部、尾部及可选字段合计的封装字节数。floor(x) 表示向下取整。SIZE_MAX 是返回类型 z_size_t 能表示的最大值;“饱和”表示数学结果再大也只返回这个最大值,而不回绕成较小数。
返回值与后续调用
返回值类型。 z_size_t — 输出容量上界(字节)
返回值是以字节计的输出容量上界数值,不是 zlib 状态码。结果可能在 SIZE_MAX 处饱和。
deflateBound_z()| 返回值 | 含义与出现条件 | 调用者接下来 |
|---|---|---|
bound输出字节数上界 |
存活流按当前窗口、内存级别、压缩级别、策略和完整封装大小选择公式;NULL 或可安全检查的无效流采用固定/存储公式较大者加 18。结果均在 SIZE_MAX 处饱和,堆不变。 | 所述容量保证只在以下条件下适用:在初始化和各项设置之后、压缩之前调用;配置、字典和头部保持不变;使用标准调优;没有预置位。还须满足缓冲区可表示以及 avail_in/avail_out 的容量条件。 |
调用条件与效果
定义域 受限定义域(存活流和可读的保留头部);包括每个 z_size_t sourceLen。效果: 查询。
前置条件 存活流,满足共享头部条件。对于下述输出容量保证,应在初始化及任何字典/头部设置后、压缩前调用。保持配置、头部和字典不变;使用标准调优,不插入预置位。
证明目标。
- 目标。
Goal.deflateBound_z_safety(Safety/Streams.lean);必需。定理:ZlibF.Spec.Public.StreamCallSafetyProof.deflateBound_z_safety(public-stream-call-safety.lean)。这个目标有两个子句:对被拒绝的流的拒绝;对可达流的一次调用。 - 适用条件。 拒绝子句要求
strm是被拒绝的流(RefusedDeflate)。对可达流的调用要求(StreamCallDomain):strm是可达流(StreamReachable);- 平台大小上界成立(
ByteObjectsFit); - deflate 的条件 4 到 6,即对 gzip 头的要求(
ActiveHeader); - 已交给
deflateSetHeader的头部记录在本次调用时存活且可读,而不只是在写出头部期间:该记录存活,且不是流自己的块;非 NULL 的extra指向extra_len个可读字节,且在流自己的块之外;非 NULL 的name或comment是以 NUL 结尾的字符串(DeflateHeaderLive)。
- 无条件覆盖。 每一个
sourceLen。每一个可达流,无论处于哪个阶段:第一次deflate之前、流的中途、收尾期间,以及Z_STREAM_END之后。拒绝子句中:每一个被拒绝的流,以及其他参数的每个取值。 - 保证(对可达流的调用是
StreamCallSafe)。- 返回。 对被拒绝的流,调用返回的值与
strm为 NULL、sourceLen相同时返回的值相同:这是保守的上界,不是错误码。对可达流调用时,调用返回。 - 状态。 对可达流调用时,流保持其不变量(
StreamInvariant)。 - 写入。 对被拒绝的流不写任何内容:堆不变。对可达流调用时,只写流记录和流自己的块。
- 分配。 对可达流调用时,精确的分配账本(
LiveChange)。
- 返回。 对被拒绝的流,调用返回的值与
- 不在本目标内。
zalloc和zfree已设置、而state是垃圾指针、指向已释放的状态或指向 inflate 状态的流记录:没有目标覆盖对这种记录的这个调用(见偏离记录)。返回的值:功能目标Goal.deflateBound_z(不在计划内;未完成)。这么多输出空间确实足够:功能目标Goal.deflate_sequence的子句DeflateCompletes(不在计划内;未完成)。
完整返回条件与边界
返回与保证 堆不变。要得到的数值是下述数学值,在 SIZE_MAX 处饱和,其中 n = sourceLen,w 为完整封装大小:
- 窗口 15、内存级别 8 且策略不是
Z_FIXED:n + floor(n/4096) + floor(n/16384) + floor(n/33554432) + 7 + w。 - 否则,若窗口位数不超过哈希位数且级别非零:
n + floor(n/8) + floor(n/256) + floor(n/512) + 4 + w。 - 否则:
n + floor(n/32) + floor(n/128) + floor(n/2048) + 7 + w。
哈希位数等于内存级别加 7。第一种情况里“且策略不是 Z_FIXED”这几个字就是补丁 0006 的改动:未打补丁的 C 对每一种策略都使用第一个公式。策略为 Z_FIXED、窗口 15、内存级别 8 时,打过补丁的函数在级别 1 到 9 使用第二个公式,在级别 0 使用第三个公式。对于级别 1 到 3 的 Z_FIXED,第一个公式偏小:在未打补丁的 C 上,一次 deflate(Z_FINISH) 调用即使得到这么多输出空间,也可能返回 Z_OK(见发现,已用真实的 C 复现)。
裸流的 w 为 0;zlib 为 6,存在预置历史时再加 4;gzip 为 18,再加可选的 extra 字段(两个长度字节,加上 extra_len 的低 16 位,即头部写入函数输出的长度)、以零终止的名称/注释和头部 CRC。取低 16 位就是补丁 0007 的改动:未打补丁的 C 以 32 位无符号运算计算 2 + extra_len,当 extra_len 为 2^32 - 2 和 2^32 - 1 时会回绕,得到的上界大约小了 64 KiB(发现,已用真实的 C 复现)。
输出容量: 与数值公式分开,对于大小可表示且足够的缓冲区,如果输入和输出大小能放入 avail_in 和 avail_out,向一次 deflate(Z_FINISH) 提供全部 n 个字节及至少为上界的输出空间,必须返回 Z_STREAM_END。在 Z_FINISH 前仅使用 Z_NO_FLUSH 的干净调用安排具有总输出上界。其他刷新安排可能超出此上界。饱和结果不承诺存在这样大小的可寻址缓冲区。
聚焦范围之外: NULL 或可安全检查的无效流,得到上述固定/存储公式中的较大值,再加 18,并进行饱和。没有错误码。功能目标覆盖每一种可读的 gzip 头部长度,包括大于 65535 的 extra_len;本页的契约不涉及这种长度。
本组共同前提与范围
输入分批到达、输出空间有限,或需要选择封装、字典、刷新边界时,使用 z_stream 压缩器。封装是在 DEFLATE 压缩数据之外增加的头部、尾部和完整性信息;裸 DEFLATE 则不带这些封装。初始化一次,使用连续的缓冲区调用 deflate,即使放弃压缩也要结束流。单个缓冲区的操作见 compress 和 compress2。
| 任务 | 条目 |
|---|---|
| 开始或复用 | 初始化、配置初始化、重置、保留历史的重置 |
| 提供元数据或历史 | 字典、读取历史、gzip 头 |
| 压缩与输出大小 | 压缩、上界、待输出数据、最近刷新位数 |
| 调整或分支 | 参数、调优、位预置、复制 |
| 释放存储 | 结束 |
这些契约遵循固定版本的 zlib 在应用各补丁之后的 zlib.h 和 deflate.c,采用默认 LP64 Linux 构建。七个补丁中只有补丁 0006 和 0007 改动 deflate.c。两者都修改 deflateBound_z,deflateBound 调用 deflateBound_z,其结果也随之改变:0006 修改一个条件,0007 修改封装大小中 gzip extra 字段的长度。两处改动见条目 deflateBound_z。这些补丁不改动其他函数。这些是聚焦契约:前置条件描述通常的正确用法,有意比函数实际接受的范围窄。前置条件之外、C 仍会处理的情况,写在“错误”或聚焦范围之外下。超出前置条件的调用并不因此就是未定义行为,也不一定返回错误码。定义域和效果标签的含义见契约约定。
已证明的内容。 只证明安全性:每次调用都返回,没有未定义行为和内存错误,只写其目标指明的内容,并且不泄漏(见安全性)。各条目在“证明目标”下给出自己的目标,所用的五项和固定用语由阅读证明目标段落定义:目标及其定理;目标适用的条件,按 Lean 命题中的顺序列出;对每一个取值都覆盖的内容;保证的内容(返回、状态、写入、分配);以及留给其他目标的内容。证明所假设的是那里列出的条件,而不是文档中的前置条件。后置条件、返回值表和各项说明描述的是功能行为:它们读自 C 源码,凡是没有定理陈述的,都尚未由证明确认;安全结论不需要它们。哪些目标已完成,见进度。
共享约定
在每条所述前置条件下,文档描述的行为是:调用终止且不产生运行时故障,并且后置条件成立。调用之后流仍然存活时,它的表示不变量保持成立。其中已被证明的部分,就是该条目的安全目标。
先看一次调用的数据交接。next_in 指向尚未读取的输入的起点,avail_in 是从这里开始可读的字节数;next_out 指向下一个可写位置,avail_out 是剩余输出容量,也以字节计。一次调用可以只消耗部分输入、只交付部分输出。调用者应读取更新后的指针和计数,接走已交付字节,再为同一个流补充输入或输出空间。
- 存活流: 可写的
z_stream,其压缩器状态由成功初始化或复制建立,经过合法调用保持,且尚未结束。调用者不改变其内部状态或分配器字段。同一个流的调用按顺序执行。 - 缓冲区: 输入覆盖
avail_in个可读字节;输出覆盖avail_out个可写字节。它们彼此不重叠,也不与流或流拥有的状态重叠。非 NULL 标量结果指向可写单元,与其他结果及流内存分离。这些分离条件是契约的假设。安全目标也假设其中某一条时,该条目的“证明目标”会写明,偏离记录中也有对应的一行。 - 分配器: 使用默认分配/释放函数对,或在初始化前将两个字段都置为 NULL。任意一次分配尝试都可能失败。自定义分配器回调不在本页范围内。
- 帧性质与所有权: 调用只改变自己的流、其拥有的状态和所述输出区域。调用者输入只读。调用者缓冲区和头部记录仍归调用者所有。只有初始化和复制会分配;只有它们失败时的清理与
deflateEnd会释放内存。其他调用保持流的分配集合。 - 头部生命周期: 保留的 gzip 头及其可选字段在使用期间保持可读且不变。非 NULL 的
name和comment以零终止;extra覆盖所述长度。本页的契约取extra_len <= 65535。 - 检查后的拒绝: 除初始化和上界查询外,流检查失败会在正常操作之前返回
Z_STREAM_ERROR,不发生写入。deflateCopy还会清空非 NULL 目的流的状态。这种拒绝不修改查询输出单元。 - 受限定义域指这些显式内存、生命周期和调用顺序条件,加上条目自身的前置条件。它不意味着接受每个可表示的指针或整数。错误概述覆盖各项检查读得到的流记录和状态,不覆盖任意无效地址。
- 可达流: 证明目标里说的是可达流,契约里说的是存活流(见契约约定)。目标所覆盖的调用会延长流的历史:调用返回后,无论返回哪个状态码,流仍然是可达流,下一次调用的目标随之适用。
deflateEnd结束这段历史。 - 结果单元作为值:
deflateGetDictionary、deflatePending和deflateUsed通过指针报告结果(uInt *dictLength、unsigned *pending、int *bits)。翻译没有把这些单元建模为内存:各函数只接收“指针是否为 NULL”这一事实,并把结果作为值返回。因此目标不涉及结果单元的地址,也无法表达结果单元与其他对象重叠的情况。
安全目标
ZlibF.Spec.Public.Goal.deflateBound_z_safety
状态:完成 · 结论的状态
/-- `z_size_t deflateBound_z(z_streamp strm, z_size_t sourceLen)`.
**Safety of `deflateBound_z`**: a `NULL` or inconsistent stream (`RefusedDeflate`) gets the
conservative bound of a `NULL` stream (not an error, as in the C) and nothing changes; and on every
reachable deflate stream, with the caller's arguments as `zlib.h` asks, the call is safe
(`StreamCallSafe`). -/
def Goal.deflateBound_z_safety : Prop :=
(∀ h p n, RefusedDeflate h p → ∃ v, C.run (Zlib.Deflate.deflateBound_z p n) h = .ok (v, h) ∧
C.run (Zlib.Deflate.deflateBound_z none n) h = .ok (v, h)) ∧
(∀ h r sourceLen,
StreamCallDomain .deflate h r (.deflateBound_z (some r) sourceLen) →
StreamCallSafe .deflate h r (.deflateBound_z (some r) sourceLen))相关定义与源码 ↗功能契约(安全之外)
ZlibF.Spec.Public.Goal.deflateBound_z
状态:未完成,不在计划内 · 结论的状态
/-- `z_size_t deflateBound_z(z_streamp strm, z_size_t sourceLen)`.
The mathematical bound includes the entire gzip header, with saturation instead of overflow.
The known extra-length arithmetic issue remains an implementation proof blocker. -/
def Goal.deflateBound_z : Prop := DeflateBoundContract Zlib.Deflate.deflateBound_z相关定义与源码 ↗