zlib × Lean
用 Lean 4 对 zlib 的逐语句翻译作机器检查的证明:默认 x86_64 Linux 构建中每个有文档的公开函数都是安全的,即没有未定义行为、没有内存错误、没有泄漏,并且终止;每条定理都写明自己的前提。
结论
前三项是安全结论;第四项是一项功能结论。每一项的状态是完成或未完成。
- 1完成
inflate对每个输入都安全:没有未定义行为、内存错误、泄漏,并且终止;对一个流上的每个调用序列和缓冲区的任何切分都成立。 - 2完成
deflate对每个输入都安全,对一个流上的每个调用序列都成立。 - 3完成
其余每个有文档的公开函数都安全:
compress*与uncompress*、其他流函数、校验和函数、gzip 文件接口和回调解码器inflateBack。命题:
compress_safety·uncompress_safe·gz_sequence_safety·gz_refusal·inflate_back_sequence_safety· 每个函数的目标 - 4完成
默认 zlib 流的往返:
uncompress(compress(x)) = x;用默认级别的deflateInit和任意刷新值的deflate调用压缩,以deflate(Z_FINISH)调用结束,再用inflateInit解压,对缓冲区的任何切分都得到原输入。
完成:存在一条 Lean 定理,它的命题恰好就是这个目标,并且通过了本项目的每一项检查。未完成:没有这样的定理。
翻译和运行时模型与 C 相符,这一点靠审阅和测试,不是靠证明:见 可信基础;调用必须满足的条件见 偏离记录;一项完成的结论依靠什么,见 这一页。
先读 zlib 本身
- 基础压缩:LZ77 与 Huffman
一个完整的小编解码器:重复片段、Huffman 编码、规则的传递与终止。从
ABABABAB开始,逐步重建 DEFLATE 的核心。 - zlib 的实现与优化
zlib 如何真正实现并优化压缩与解压:窗口、哈希链、匹配搜索、查表和复制。这是最深入的一篇。
- zlib 的功能扩展:流式处理与校验
流式调用、字典、封装、Adler-32 与 CRC-32,以及应用接口:为什么完整缓冲区不够用。