本页说明每项结论、zlib 的每个公开函数是否已经完成。只有本页说明状态。要点是:三项安全结论都已完成,组成它们的 99 个目标全部完成;默认 zlib 流的往返也已完成,它有 14 个目标。
一项结论、一个目标或一个函数只有两种状态。
- 完成:存在一条 Lean 定理,它的命题恰好就是这个目标,并且通过了本项目的每一项检查。这意味着什么,见完成的结论依靠什么。
- 未完成:没有这样的定理。如果也不打算给出定理,会另外写明“不在计划内”。
这些结论是什么意思,请读总览。每个函数对应哪条定理、定理覆盖哪些调用,请读按函数查覆盖情况和偏离记录。
结论
安全指没有未定义行为、没有内存错误、没有泄漏,并且终止。这些结论针对 zlib 1.4 加七个补丁的默认 x86_64 Linux 构建。每项结论都在其目标的前提下成立;前提的简述见总览,按函数列出的见偏离记录。调用序列指一个流、一个 gzip 文件句柄或一个回调解码器的历史。
| # |
结论 |
目标 |
状态 |
| 1 |
inflate 对每个输入、缓冲区的每种切分都安全,对它的调用序列也是如此。 |
Goal.inflate_safety、Goal.inflate_sequence_safety |
完成 |
| 2 |
deflate 对每个输入、缓冲区的每种切分都安全,对它的调用序列也是如此。 |
Goal.deflate_safety、Goal.deflate_sequence_safety |
完成 |
| 3 |
其余每个有文档的公开函数都安全:compress* 与 uncompress*、其他流函数、校验和函数、gzip 文件接口和回调解码器 inflateBack。 |
下文各表中的其余全部目标 |
完成 |
| 4 |
默认 zlib 流的往返:给 compress 留出 compressBound 的空间时,uncompress(compress(x)) = x;用默认级别的 deflateInit 和任意刷新值的 deflate 调用压缩,以 deflate(Z_FINISH) 调用结束,再用 inflateInit 解压,对缓冲区的每种切分都得到原输入。 |
Goal.compress_uncompress_roundtrip、Goal.compress_uncompress_roundtrip_witness、Goal.compress_completes、Goal.compress_z_completes、Goal.uncompress_completes、Goal.stream_roundtrip_total、Goal.deflate_finish_ends、Goal.inflate_chain_ends、Goal.stream_roundtrip、Goal.deflate_completes_default、Goal.deflate_bound_default、Goal.inflate_completes_default、Goal.default_inflate_progress、Goal.default_inflate_completes |
完成 |
第 4 项是一项功能结论。它说的是默认级别的 deflateInit 产生、inflateInit 读取的流,不用预设字典,并且每次分配都成功。它的编码器历史是 deflateInit,然后是 deflate 调用和对缓冲区字段的改动;含有 deflateParams、重置或其他级别的历史不在其中。结束流的那些调用和各次 inflate 调用都有输出空间。往返一页给出每个目标及其前提,下文它的表说明每个目标是什么。
每个公开函数
默认构建中每个有文档的函数都有自己的安全目标。API 参考中每个函数的页面给出它的目标的命题。
解压流
| 函数 |
目标 |
状态 |
inflate |
Goal.inflate_safety |
完成 |
inflateCopy |
Goal.inflateCopy_safety |
完成 |
inflateEnd |
Goal.inflateEnd_safety |
完成 |
inflateGetDictionary |
Goal.inflateGetDictionary_safety |
完成 |
inflateGetHeader |
Goal.inflateGetHeader_safety |
完成 |
inflateInit2_ |
Goal.inflateInit2__safety |
完成 |
inflateInit_ |
Goal.inflateInit__safety |
完成 |
inflateMark |
Goal.inflateMark_safety |
完成 |
inflatePrime |
Goal.inflatePrime_safety |
完成 |
inflateReset |
Goal.inflateReset_safety |
完成 |
inflateReset2 |
Goal.inflateReset2_safety |
完成 |
inflateSetDictionary |
Goal.inflateSetDictionary_safety |
完成 |
inflateSync |
Goal.inflateSync_safety |
完成 |
压缩流
| 函数 |
目标 |
状态 |
deflate |
Goal.deflate_safety |
完成 |
deflateBound |
Goal.deflateBound_safety |
完成 |
deflateBound_z |
Goal.deflateBound_z_safety |
完成 |
deflateCopy |
Goal.deflateCopy_safety |
完成 |
deflateEnd |
Goal.deflateEnd_safety |
完成 |
deflateGetDictionary |
Goal.deflateGetDictionary_safety |
完成 |
deflateInit2_ |
Goal.deflateInit2__safety |
完成 |
deflateInit_ |
Goal.deflateInit__safety |
完成 |
deflateParams |
Goal.deflateParams_safety |
完成 |
deflatePending |
Goal.deflatePending_safety |
完成 |
deflatePrime |
Goal.deflatePrime_safety |
完成 |
deflateReset |
Goal.deflateReset_safety |
完成 |
deflateSetDictionary |
Goal.deflateSetDictionary_safety |
完成 |
deflateSetHeader |
Goal.deflateSetHeader_safety |
完成 |
deflateTune |
Goal.deflateTune_safety |
完成 |
deflateUsed |
Goal.deflateUsed_safety |
完成 |
完整缓冲区与库信息
| 函数 |
目标 |
状态 |
compress |
Goal.compress_safety |
完成 |
compress2 |
Goal.compress2_safety |
完成 |
compress2_z |
Goal.compress2_z_safety |
完成 |
compressBound |
Goal.compressBound |
完成 |
compressBound_z |
Goal.compressBound_z |
完成 |
compress_z |
Goal.compress_z_safety |
完成 |
uncompress |
Goal.uncompress_safe |
完成 |
uncompress2 |
Goal.uncompress2_safe |
完成 |
uncompress2_z |
Goal.uncompress2_z_safe |
完成 |
uncompress_z |
Goal.uncompress_z_safe |
完成 |
zlibCompileFlags |
Goal.zlibCompileFlags_safety |
完成 |
zlibVersion |
Goal.zlibVersion_safety |
完成 |
校验和
| 函数 |
目标 |
状态 |
adler32 |
Goal.adler32_safety |
完成 |
adler32_combine |
Goal.adler32_combine_safety |
完成 |
adler32_combine64 |
Goal.adler32_combine64_safety |
完成 |
adler32_z |
Goal.adler32_z_safety |
完成 |
crc32 |
Goal.crc32_safety |
完成 |
crc32_combine |
Goal.crc32_combine_safety |
完成 |
crc32_combine64 |
Goal.crc32_combine64_safety |
完成 |
crc32_combine_gen |
Goal.crc32_combine_gen_safety |
完成 |
crc32_combine_gen64 |
Goal.crc32_combine_gen64_safety |
完成 |
crc32_combine_op |
Goal.crc32_combine_op_safety |
完成 |
crc32_z |
Goal.crc32_z_safety |
完成 |
回调解码
| 函数 |
目标 |
状态 |
inflateBack |
Goal.inflateBack_safety |
完成 |
inflateBackEnd |
Goal.inflateBackEnd_safety |
完成 |
inflateBackInit_ |
Goal.inflateBackInit__safety |
完成 |
gzip 文件
| 函数 |
目标 |
状态 |
gzbuffer |
Goal.gzbuffer_safety |
完成 |
gzclearerr |
Goal.gzclearerr_safety |
完成 |
gzclose |
Goal.gzclose_safety |
完成 |
gzclose_r |
Goal.gzclose_r_safety |
完成 |
gzclose_w |
Goal.gzclose_w_safety |
完成 |
gzdirect |
Goal.gzdirect_safety |
完成 |
gzdopen |
Goal.gzdopen_safety |
完成 |
gzeof |
Goal.gzeof_safety |
完成 |
gzerror |
Goal.gzerror_safety |
完成 |
gzflush |
Goal.gzflush_safety |
完成 |
gzfread |
Goal.gzfread_safety |
完成 |
gzfwrite |
Goal.gzfwrite_safety |
完成 |
gzgetc |
Goal.gzgetc_safety |
完成 |
gzgetc_ |
Goal.gzgetc__safety |
完成 |
gzgets |
Goal.gzgets_safety |
完成 |
gzoffset |
Goal.gzoffset_safety |
完成 |
gzoffset64 |
Goal.gzoffset64_safety |
完成 |
gzopen |
Goal.gzopen_safety |
完成 |
gzopen64 |
Goal.gzopen64_safety |
完成 |
gzprintf |
Goal.gzprintf_safety |
完成 |
gzputc |
Goal.gzputc_safety |
完成 |
gzputs |
Goal.gzputs_safety |
完成 |
gzread |
Goal.gzread_safety |
完成 |
gzrewind |
Goal.gzrewind_safety |
完成 |
gzseek |
Goal.gzseek_safety |
完成 |
gzseek64 |
Goal.gzseek64_safety |
完成 |
gzsetparams |
Goal.gzsetparams_safety |
完成 |
gztell |
Goal.gztell_safety |
完成 |
gztell64 |
Goal.gztell64_safety |
完成 |
gzungetc |
Goal.gzungetc_safety |
完成 |
gzvprintf |
Goal.gzvprintf_safety |
完成 |
gzwrite |
Goal.gzwrite_safety |
完成 |
gzvprintf 在 zlib.h 中是未文档化函数。它有安全目标,因为 gzprintf 要经过它。Goal.compressBound 和 Goal.compressBound_z 是两个纯函数的完整契约,这两个函数不涉及堆,也不会出故障;这两个契约代替它们的安全目标。
涉及多个函数的目标
| 命题 |
目标 |
状态 |
| inflate 流的每个调用序列都安全。 |
Goal.inflate_sequence_safety |
完成 |
| deflate 流的每个调用序列都安全。 |
Goal.deflate_sequence_safety |
完成 |
| 回调解码器的每个调用序列都安全,对每种调用者协议都成立。 |
Goal.inflate_back_sequence_safety |
完成 |
| gzip 文件句柄的每段历史都安全,对每个文件系统世界都成立。 |
Goal.gz_sequence_safety |
完成 |
inflate 的各个函数拒绝 NULL 流或不一致的流,不出故障。 |
Goal.inflate_refusal |
完成 |
deflate 的各个函数拒绝 NULL 流或不一致的流,不出故障。 |
Goal.deflate_refusal |
完成 |
gzip 文件函数拒绝 NULL 句柄,不出故障,也不改变任何东西。 |
Goal.gz_refusal |
完成 |
| inflate 各目标的前提可以满足:在一个具体的堆上初始化成功。 |
Goal.inflate_initialisation_domain |
完成 |
| deflate 各目标的前提可以满足:在一个具体的堆上初始化成功。 |
Goal.deflate_initialisation_domain |
完成 |
| 回调解码器各目标的前提可以满足:在一个具体的堆上初始化成功。 |
Goal.inflate_back_initialisation_domain |
完成 |
一次 inflateBack 调用的各项前提可以同时满足,用的是具体的回调和具体的调用者协议。 |
Goal.inflateBack_call_domain |
完成 |
| gzip 文件各目标的前提可以满足:存在一个句柄的两段具体历史,一段读、一段写。 |
Goal.gz_sequence_nonvacuity |
完成 |
默认 zlib 流的往返
| 命题 |
目标 |
状态 |
uncompress(compress(x)) = x:给 compress 留出 compressBound 的空间,它返回 Z_OK;把它写出的字节交给 uncompress,空间容得下源数据时,uncompress 返回 Z_OK,并交回源数据及其长度。 |
Goal.compress_uncompress_roundtrip |
完成 |
Goal.compress_uncompress_roundtrip 的前提可以满足:在具体的堆上,源数据非空。 |
Goal.compress_uncompress_roundtrip_witness |
完成 |
给 compress 留出 compressBound 的空间,它返回 Z_OK,写出的是一个 zlib 流,解码得到源数据,并且不要求预设字典。 |
Goal.compress_completes |
完成 |
compress_z 同样如此。 |
Goal.compress_z_completes |
完成 |
对一个不要求预设字典的 zlib 流调用 uncompress,空间容得下解码结果时,它返回 Z_OK,写出解码结果并存入其长度。 |
Goal.uncompress_completes |
完成 |
流的往返,连同两边的完成性:Goal.deflate_finish_ends 与 Goal.inflate_chain_ends 合在一起。 |
Goal.stream_roundtrip_total |
完成 |
在默认流上做过任意 deflate 调用之后,只要每次都有输出空间,接下去的每一串 deflate(Z_FINISH) 调用都在有界次数内结束:全部输入被接受,输出解码得到输入。 |
Goal.deflate_finish_ends |
完成 |
把一个完整的默认流按任意分块交给默认解码器,只要有输出空间,它在有界次数的 inflate 调用内结束,写出的恰好是编码器的输入。 |
Goal.inflate_chain_ends |
完成 |
默认流上的一个 deflate 调用序列和一个 inflate 调用序列都到达 Z_STREAM_END,并且解码器读入的是编码器输出的前缀时,解码器写出的恰好是编码器的输入。 |
Goal.stream_roundtrip |
完成 |
在只用 Z_NO_FLUSH 或 Z_FINISH 的 deflate 调用之后,一次 deflate(Z_FINISH) 调用拿到全部剩余输入,并且空间多于整个输入的上界扣除已有输出后的余量时,返回 Z_STREAM_END,全部输出解码得到全部输入。 |
Goal.deflate_completes_default |
完成 |
在新建的默认流上,一次 deflate(Z_FINISH) 调用拿到全部输入和至少 deflateBound 字节的空间时,返回 Z_STREAM_END,写出的流解码得到输入。 |
Goal.deflate_bound_default |
完成 |
默认解码器已经读了一个完整默认流的一部分,再拿到其余部分和容得下其余解码结果的空间时,返回 Z_STREAM_END,写出编码器输入的其余部分。 |
Goal.inflate_completes_default |
完成 |
默认解码器面对格式接受的任意 zlib 流:每次 inflate 调用拿到流的后续部分和输出空间时,要么以恰好的解码结果结束这个流,要么消耗了输入或写出了输出;要求预设字典的流得到 Z_NEED_DICT。 |
Goal.default_inflate_progress |
完成 |
默认解码器拿到格式接受的 zlib 流的全部剩余部分,以及容得下其余解码结果的空间时,一次调用就结束这个流;要求预设字典的流则返回 Z_NEED_DICT。 |
Goal.default_inflate_completes |
完成 |
不在计划内
这些不打算给出定理。
| 组 |
包含什么 |
理由 |
| 功能正确性(第 4 项除外) |
函数在安全之外算出了什么:其他配置(其他压缩级别、策略、窗口大小和封装,预设字典)下的往返,以及 inflate 把格式接受的流读到结尾;经由 gzip 文件接口或 inflateBack 的往返;inflate 对格式拒绝的流做什么;gzip 文件函数读出或写入的字节;inflateBack 交付的内容;四类调用序列的完整契约(Goal.inflate_sequence、Goal.deflate_sequence、Goal.inflate_back_sequence、Goal.gz_sequence);只谈抽象模型的命题。 |
安全结论不需要它们。关于 gzip 文件接口的命题还要依靠一个手工建立的文件系统和描述符模型,以及格式化输出:模型按 vsnprintf 的 C 契约取得它,并不计算它。安全证明所依赖的功能性事实,在那个证明里一并证明。 |
| 其他构建配置 |
默认 x86_64 Linux 构建之外的每一种配置。 |
每一种配置都要针对不同的平台模型把整个证明重做一遍。 |
| 未文档化函数 |
zError、inflateSyncPoint、get_crc_table、inflateUndermine、inflateValidate、inflateCodesUsed、inflateResetKeep、deflateResetKeep、gzopen_w:zlib.h 在 undocumented functions (not part of the zlib API)(未文档化函数,不属于 zlib API)之下声明了十个函数,这是其中九个。第十个是上文的 gzvprintf。 |
它们不属于 zlib API。没有为它们写出安全目标:未完成,不在计划内。 |
尽管如此,许多函数的功能契约已有定理,九个未文档化函数中的八个也在其中(只有 gzopen_w 例外,它不在默认构建中)。API 参考中每个函数的页面说明它的功能契约是否完成。未完成的功能契约都不在计划内:功能结论只有第 4 项,而它不是某一个函数的契约。