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

deflatePrime

在裸流的压缩输出前添加调用者提供的位片段。

完整章节与共同规则 ↗
int ZEXPORT deflatePrime(z_streamp strm, int bits, int value);

在裸流的压缩输出前添加调用者提供的位片段。

返回值与后续调用

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

返回值说明位片段是否加入待输出数据。因缓冲空间不足而拒绝时,片段的任何部分都不会插入。

deflatePrime()
返回值 含义与出现条件 调用者接下来
Z_OK
位片段已加入
流检查通过,bits 为 0..16,且待输出空间足够;追加 value 的低 bits 位,最低有效位优先,完整字节进入待输出缓冲。 在前置条件之内,仅在裸流的第一次 deflate 之前插入,并在解释输出时计入前缀;没有字节交付至 next_out。
Z_BUF_ERROR
位数超范围
bits 不在 0..16;在待输出字节紧缩之前拒绝,不插入位。 修正位数,并满足位预置调用的前置条件后再调用。
Z_BUF_ERROR
待输出空间不足
bits 为 0..16,但待输出缓冲没有容纳片段所需的空间;不插入位,但已有待输出字节可能已被紧缩。 原样重复调用不会腾出空间;先按所选位拼接协议合法处理待输出数据,再决定是否重试。
Z_STREAM_ERROR
流检查未通过
流检查失败;正常操作尚未开始,流和结果单元均未写入。 先建立存活流并满足调用的前置条件;这个结果不表示操作已完成。

判读要点。

  • 实现不检查封装或首次调用时机;接受位片段本身不保证任意插入后的普通流格式有效。

调用条件与效果

定义域 受限定义域。效果: 将位追加到待输出数据。

前置条件 存活的裸流,在初始化或 deflateReset 后第一次 deflate 之前;bits 为 0..16,value 为任意 int。调用者解释后续压缩流时需计入这些前缀位。

证明目标。

  • 目标。 Goal.deflatePrime_safety(Safety/Streams.lean);必需。定理:ZlibF.Spec.Public.StreamCallSafetyProof.deflatePrime_safety(public-stream-call-safety.lean)。这个目标有两个子句:对被拒绝的流的拒绝;对可达流的一次调用。
  • 适用条件。 拒绝子句要求 strm 是被拒绝的流(RefusedDeflate)。对可达流的调用要求(StreamCallDomain):
    1. strm 是可达流(StreamReachable);
    2. 平台大小上界成立(ByteObjectsFit);
    3. 自初始化或 deflateReset 以来,还没有 deflate 调用让流开始工作:流状态仍是 INIT_STATE 或 GZIP_STATE(DeflateNotStarted)。
  • 无条件覆盖。 每一个 bits 和 value;每一种封装。调用顺序的要求与前置条件相同。拒绝子句中:每一个被拒绝的流,以及其他参数的每个取值。
  • 保证(对可达流的调用是 StreamCallSafe)。
    • 返回。 对被拒绝的流,调用返回 Z_STREAM_ERROR。对可达流调用时,调用返回。
    • 状态。 对可达流调用时,流保持其不变量(StreamInvariant)。
    • 写入。 对被拒绝的流不写任何内容:堆不变。对可达流调用时,只写流记录和流自己的块。
    • 分配。 对可达流调用时,精确的分配账本(LiveChange)。
  • 不在本目标内。 在 deflate 已经让流开始工作之后调用:在所有安全目标之外(见偏离记录中“其他流参数”一行)。zalloc 和 zfree 已设置、而 state 是垃圾指针、指向已释放的状态或指向 inflate 状态的流记录:没有目标覆盖对这种记录的这个调用(见偏离记录)。返回哪个状态码,以及调用之后的待输出位:功能目标 Goal.deflatePrime(不在计划内;未完成)。
完整返回条件与边界

返回与保证 Z_OK 将 value 的低 bits 位按最低有效位优先的顺序,追加到逻辑待输出位序列。完整字节加入待输出数据,缓冲中剩余少于 8 位。不向 next_out 交付字节;不分配。待输出缓冲区空间不足时,Z_BUF_ERROR 不插入任何位。在该拒绝之前,已有的待输出字节可能已在其所属缓冲区内被紧缩。

聚焦范围之外: 计数不在 0..16 时,在紧缩前返回 Z_BUF_ERROR;流检查失败返回 Z_STREAM_ERROR。功能目标覆盖每一种封装、每一种调用顺序下对待输出位的精确效果。

本组共同前提与范围

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

状态:完成 · 结论的状态

/-- `int deflatePrime(z_streamp strm, int bits, int value)`.
**Safety of `deflatePrime`**: 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.deflatePrime_safety : Prop :=
  (∀ h p bits value, RefusedDeflate h p →
    C.run (Zlib.Deflate.deflatePrime p bits value) h = .ok (Z_STREAM_ERROR, h)) ∧
  (∀ h r bits value,
     StreamCallDomain .deflate h r (.deflatePrime (some r) bits value) →
     StreamCallSafe .deflate h r (.deflatePrime (some r) bits value))
相关定义与源码 ↗

功能契约(安全之外)

ZlibF.Spec.Public.Goal.deflatePrime

状态:未完成,不在计划内 · 结论的状态

/-- `int deflatePrime(z_streamp strm, int bits, int value)`.
Append the requested low bits in transmission order. Compaction can occur before a buffer
error; invalid bit counts are refused before compaction. No allocation occurs. -/
def Goal.deflatePrime : Prop :=
  ∀ h r i z s count value old,
    Zlib.Deflate.Spec.DGood h r i z s → PendingBits h s old →
    ∃ rc after s', C.run (Zlib.Deflate.deflatePrime (some r) count value) h = .ok (rc, after) ∧
      Zlib.Deflate.Spec.DGood after r i z s' ∧
      (count.toInt < 0 ∨ 16 < count.toInt → rc = Z_BUF_ERROR ∧ after = h) ∧
      (0 ≤ count.toInt → count.toInt ≤ 16 →
        s'.pending_out = s'.pending_buf ∧
        if s.pending_buf_size.toNat - s.pending.toNat < (s.bi_valid.toInt.toNat + count.toInt.toNat) / 8 then
          rc = Z_BUF_ERROR ∧ PendingBits after s' old
        else rc = Z_OK ∧ PendingBits after s'
          (old ++ (List.range count.toInt.toNat).map (fun j => decide (value.toUInt32.toNat / 2 ^ j % 2 = 1)))) ∧
      Frame h after (DeflateOwned i s) ∧ LiveChange h after (fun _ => False) (fun _ => False) ∧
      after.nalloc = h.nalloc
相关定义与源码 ↗
ZLIB × LEAN

目录

正在阅读deflatePrime