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

deflate

接受输入,交付有效压缩流的一部分或全部。

完整章节与共同规则 ↗
int ZEXPORT deflate(z_streamp strm, int flush);

接受输入,交付有效压缩流的一部分或全部。

flush 描述调用者希望推进到哪里:普通调用交给压缩器选择输出时机,刷新请求建立所选边界,Z_FINISH 请求结束整个流。请求不会让有限的输出缓冲区变大:空间用完时,取走输出,再按下述协议继续。

返回值与后续调用

返回值类型。 int — zlib 状态码

返回值区分需要继续、整个压缩流完成,以及拒绝或无法推进。更新后的指针和计数给出本次调用消费和交付的字节数。

deflate()
返回值 含义与出现条件 调用者接下来
Z_OK
尚可能需要继续
调用尚未报告完整流结束。可能已消费输入,或已交付头部、数据、刷新标记或尾部的字节;输出填满时仍可能有未消费输入或待输出数据。 接走输出并使用更新后的计数;输出填满时补空间,刷新期间保持同一个 flush 值。收尾开始后不增加输入,只用 Z_FINISH 继续直到 Z_STREAM_END。
Z_STREAM_END
完整压缩流已交付
仅在 Z_FINISH 下,所有给定输入及全部压缩输出(包括封装尾部)均已交付。 保存最终输出;用 deflateEnd 释放,或 deflateReset 开始新流。此返回本身不释放状态。
Z_BUF_ERROR
没有输出空间
初始检查通过,但 avail_out 为 0;不消费输入、不交付输出,原存活流保留。 提供有效非空输出空间后继续;若正在刷新,保持原来的 flush 值,收尾期间只用 Z_FINISH。
Z_BUF_ERROR
目前无法推进
没有可用输入或待输出数据,且没有比此前更强的刷新请求;当前非 Z_FINISH 调用无法推进。 等待新输入,或在应用确实需要时选择更强的合法刷新;不要原样循环。流仍然存活。
Z_BUF_ERROR
最终处理后又提供输入
最终块处理已开始后仍提供新输入;不接受新输入,但拒绝前可能已交付旧待输出数据。存活流保留。 接走实际交付的输出,把未接受的新输入留给另一任务;不再向此流提供输入,仅用 Z_FINISH 完成,或合法重置/结束。
Z_STREAM_ERROR
流或调用参数被拒绝
流检查失败、flush 无效(包括 Z_TREES)、next_out 为 NULL、输入量非零而 next_in 为 NULL,或收尾开始后使用非 Z_FINISH 的刷新。初始拒绝不消费或交付字节。 先确定流是存活的,并修正缓冲区或 flush;收尾开始后只用 Z_FINISH。流检查失败时,不保证任意状态都可以重试或结束。

判读要点。

  • 非结束性的刷新完成后,返回的仍是 Z_OK,不表示流已结束;应结合输出空间和所用刷新协议判断该边界是否完成。

调用条件与效果

定义域 受限定义域。效果: 消费输入、输出数据并更新进度。

前置条件 存活流,缓冲区和任何正在使用的头部均有效。next_out 非 NULL,avail_out > 0;仅输入为零时 next_in 可为 NULL。flush 为 Z_NO_FLUSH、Z_PARTIAL_FLUSH、Z_SYNC_FLUSH、Z_FULL_FLUSH、Z_FINISH 或 Z_BLOCK。刷新期间输出填满时,以相同刷新请求和更多空间继续。收尾开始后,不提供新输入,只以 Z_FINISH 继续。普通格式有效性要求从初始化/deflateReset(或该历史的副本)开始,使用合法字典/头部设置、标准调优,且不进行任意位预置。

证明目标。

  • 目标。 Goal.deflate_safety(Safety/Streams.lean);必需。定理:ZlibF.Spec.Public.StreamCallSafetyProof.deflate_safety(public-stream-call-safety.lean)。这个目标有两个子句:对被拒绝的流的拒绝;对可达流的一次调用。Goal.deflate_refusal(Safety/Refusals.lean)也是必需目标,它陈述同一个拒绝。
  • 适用条件。 拒绝子句要求 strm 是被拒绝的流(RefusedDeflate)。对可达流的调用要求(StreamCallDomain):
    1. strm 是可达流(StreamReachable);
    2. 平台大小上界成立(ByteObjectsFit);
    3. next_in 为 NULL,或指向 avail_in 个可读字节;next_out 为 NULL,或指向 avail_out 个可写字节;两个范围都不在流自己的块内,且互不重叠(StreamBuffers);
    4. 在写出 gzip 头期间(流状态为 GZIP_STATE 到 HCRC_STATE),如果已有头部记录交给 deflateSetHeader:该记录存活,且不是流自己的块;非 NULL 的 extra 指向 extra_len 个可读字节,且在流自己的块之外;非 NULL 的 name 或 comment 是以 NUL 结尾的字符串(HeaderMemory);
    5. 调用者保留了已经写出的部分:正在写出的字段(extra、name 或 comment)仍然覆盖已写出的那一段,并且没有在写出一部分之后被置为 NULL(DeflateHeaderProgress);
    6. 在写出头部期间:输入范围、输出范围、extra(extra_len mod 2^16 个字节)、name 和 comment(各自直到其 NUL)两两不重叠,并且 extra、name、comment 在流自己的块之外(DeflateHeaderApart)。条件 4 到 6 合起来就是 ActiveHeader。
  • 无条件覆盖。 每一个 flush 值,包括不是刷新码的值;每一种输入字节序列。每一个可达流,无论处于哪个阶段:第一次 deflate 之前、流的中途、收尾期间,以及 Z_STREAM_END 之后。本目标比前置条件宽:next_out 可以为 NULL,avail_out 可以为零,next_in 可以在 avail_in 非零时为 NULL,flush 可以是任意 int。C 会拒绝或报告这些情况(见上面的返回值表)。拒绝子句中:每一个被拒绝的流,以及其他参数的每个取值。
  • 保证(对可达流的调用是 StreamCallSafe)。
    • 返回。 对被拒绝的流,调用返回 Z_STREAM_ERROR。对可达流调用时,调用返回。
    • 状态。 对可达流调用时,流保持其不变量(StreamInvariant)。
    • 写入。 对被拒绝的流不写任何内容:堆不变。对可达流调用时,只写流记录、流自己的块和 next_out 处的 avail_out 个字节。
    • 分配。 对可达流调用时,精确的分配账本(LiveChange)。
  • 不在本目标内。 zalloc 和 zfree 已设置、而 state 是垃圾指针、指向已释放的状态或指向 inflate 状态的流记录:没有目标覆盖对这种记录的这个调用(见偏离记录)。返回哪个状态码、写出哪些字节:功能目标 Goal.deflate(不在计划内;已有定理证明它)。
完整返回条件与边界

返回与保证 记本轮消费的输入字节数为 used,交付的输出字节数为 made;old avail_in 和 old avail_out 是调用前提供的输入量和输出容量。满足 used <= old avail_in、made <= old avail_out。指针按相应数量推进,可用计数按相应数量减少,总计数按相应数量增加并遵循无符号回绕。输入不变;已交付前缀以外的输出不变。输出填满时可能仍有输入未消费。不分配或释放。

跨调用交付的字节构成已接受输入的一种有效编码的前缀,使用所选封装、设置和预置字典。完成的输出可解码为该输入。这里规定有效输出,而非唯一的压缩字节序列。头部写出之后,adler 跟踪已接受的输入:zlib 用 Adler-32,gzip 用 CRC-32;裸流没有输入校验和。

Z_OK 表示可能需要继续。Z_STREAM_END 只在 Z_FINISH 下发生,且所有给定输入及所有压缩输出(包括尾部)都已交付。存活的状态仍被拥有,直到 deflateEnd 释放,或通过 deflateReset 复用。

请求的刷新完全交付后,Z_BLOCK 完成一个块但不填充到字节边界;Z_PARTIAL_FLUSH 添加空固定块;Z_SYNC_FLUSH 使此前全部输入可供解码器解码,并以对齐的空存储块结尾。Z_FULL_FLUSH 还重置匹配历史:后续块不引用该次已完成刷新之前的数据。若要在那里重新启动裸流解码器,需要保留精确边界,并先交付完整刷新标记。Z_FINISH 关闭最终块并写入封装尾部。

错误路径 Z_BUF_ERROR 覆盖输出空间为零、无输入且无更强刷新请求因而无法推进,或最终块处理已开始后又提供输入。它保留存活流;应按需提供空间/输入。Z_STREAM_ERROR 覆盖流检查失败、无效刷新(包括 Z_TREES)、无效 NULL 输入/输出组合,或收尾开始后请求非 Z_FINISH 的刷新。初始参数拒绝不消费输入、不交付输出。收尾开始后,因新输入而产生的较晚 Z_BUF_ERROR,可能先交付旧的待输出数据;不接受新输入。msg 和记录的刷新请求可能改变。安全目标和功能目标都包括所有有符号刷新值及这些拒绝。

本组共同前提与范围

输入分批到达、输出空间有限,或需要选择封装、字典、刷新边界时,使用 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.deflate_safety

状态:完成 · 结论的状态

/-- `int deflate(z_streamp strm, int flush)`.
**Safety of `deflate`**: a `NULL` or inconsistent stream (`RefusedDeflate`) is refused with
`Z_STREAM_ERROR` and nothing changed; and on every reachable deflate stream, with the caller's
arguments as `zlib.h` asks, the call is safe (`StreamCallSafe`). -/
def Goal.deflate_safety : Prop :=
  (∀ h p flush, RefusedDeflate h p →
    C.run (Zlib.Deflate.deflate p flush) h = .ok (Z_STREAM_ERROR, h)) ∧
  (∀ h r flush,
     StreamCallDomain .deflate h r (.deflate (some r) flush) →
     StreamCallSafe .deflate h r (.deflate (some r) flush))
相关定义与源码 ↗

功能契约(安全之外)

ZlibF.Spec.Public.Goal.deflate

状态:完成 · 结论的状态

/-- `int deflate(z_streamp strm, int flush)`.
Preserve the live stream and its five allocations. Account for exactly the bytes accepted
and delivered, including progress on a full output buffer and clean parameter refusals.
`Z_BUF_ERROR` is characterized exactly (`zlib.h`: no progress was possible): no output space;
or no input, nothing pending and a flush that repeats or weakens the previous one, other than
`Z_FINISH`; or new input after the first `Z_FINISH`. Only in the last case can the call still
deliver pending output before it refuses. A `Z_FINISH` call with output space, no new input
after the first `Z_FINISH`, and no refusal, ends the stream or makes progress. Success keeps
`msg`; an error sets it to the error's text. `data_type` changes only from `Z_UNKNOWN` to a guess.
The sequence target states valid encoding, flush points and completion. -/
def Goal.deflate : Prop :=
  ∀ h r i z s flush,
    StreamReachable .deflate h r → Zlib.Deflate.Spec.DGood h r i z s →
    StreamBuffers h r → ActiveHeader h r →
    ∃ rc after z' s' used out,
      C.run (Zlib.Deflate.deflate (some r) flush) h = .ok (rc, after) ∧
      Zlib.Deflate.Spec.DGood after r i z' s' ∧ StreamAccounting z z' used out.length ∧
      Bytes after z.next_out out.length out ∧
      z'.total_in = z.total_in + UInt64.ofNat used ∧
      z'.total_out = z.total_out + UInt64.ofNat out.length ∧
      (rc = Z_OK ∨ rc = Z_STREAM_END ∨ rc = Z_STREAM_ERROR ∨ rc = Z_BUF_ERROR) ∧
      (rc = Z_STREAM_ERROR ↔ DeflateRefuses z s flush) ∧
      (flush.toInt < 0 ∨ 5 < flush.toInt → rc = Z_STREAM_ERROR ∧ after = h) ∧
      (rc = Z_STREAM_END → flush = Z_FINISH ∧ s'.status = FINISH_STATE ∧
        z'.avail_in = 0 ∧ s'.pending = 0 ∧ s'.bi_valid = 0) ∧
      (rc = Z_BUF_ERROR → used = 0 ∧
        (out = [] ∨ (s.status = FINISH_STATE ∧ z.avail_in ≠ 0))) ∧
      (¬ DeflateRefuses z s flush → z.avail_out = 0 → rc = Z_BUF_ERROR) ∧
      (¬ DeflateRefuses z s flush → z.avail_out ≠ 0 →
        ¬ (s.status = FINISH_STATE ∧ z.avail_in ≠ 0) →
        (rc = Z_BUF_ERROR ↔ z.avail_in = 0 ∧ s.pending = 0 ∧ flush ≠ Z_FINISH ∧
          deflateRank flush ≤ deflateRank s.last_flush)) ∧
      (flush = Z_FINISH → ¬ DeflateRefuses z s flush → z.avail_out ≠ 0 →
        ¬ (s.status = FINISH_STATE ∧ z.avail_in ≠ 0) →
        rc = Z_STREAM_END ∨ used ≠ 0 ∨ out ≠ []) ∧
      (rc = Z_OK ∨ rc = Z_STREAM_END → z'.msg = z.msg) ∧
      (rc = Z_BUF_ERROR → StaticString after z'.msg (errorText Z_BUF_ERROR.toInt)) ∧
      (rc = Z_STREAM_ERROR → 0 ≤ flush.toInt → flush.toInt ≤ 5 →
        StaticString after z'.msg (errorText Z_STREAM_ERROR.toInt)) ∧
      (z'.data_type = z.data_type ∨
        (z.data_type = Z_UNKNOWN ∧ (z'.data_type = Z_BINARY ∨ z'.data_type = Z_TEXT))) ∧
      BufferFrame h after (fun b => StreamRoot r b ∨ DeflateOwned i s b) [⟨z.next_out, out.length⟩] ∧
      LiveChange h after (fun _ => False) (fun _ => False) ∧ after.nalloc = h.nalloc
相关定义与源码 ↗
ZLIB × LEAN

目录

正在阅读deflate