跳到正文
阅读地图

zlib × Lean

沿着数据读算法,沿着实现读证明。

这套文章解释 zlib 怎样压缩和恢复数据,应用怎样使用它,以及这些实现需要证明什么。先用下面的地图认识各个组件,再选择算法概览、实现精读或具体函数的完整约定。

第一部分建立算法与接口的全局认识;第二部分按主题深入,先拆解算法和优化,再连接证明思路。各章都有前置背景和下一步,旁边的全局目录可随时展开。

ZLIB / 全局机制图

压缩与解压的全局地图

先看每个组件负责什么,再进入算法或证明。悬停、聚焦或点选节点,查看它的输入、输出和阅读入口。

原始字节符号编码压缩流恢复的字节
编码块的主要数据流共同机制的支持与约束stored 块直接存放原文字节
01

算法与接口

从重复字节到压缩流,再回到调用者手中的字节。先建立全局认识,再查具体接口。

阅读算法概览 →查看调用与接口地图 ↗
02

算法精读与形式化验证

沿一条实现路径深入:数据怎样布局,优化怎样工作,最后需要证明哪些事实。

选择一个精读主题 →查阅其他组件的完整论证 ↗
沿着同一份数据深入

从三个符号到五个字节

本组精读从 A、B 和一个长度 6、距离 2 的匹配开始。先选择块的表示,再写出比特,接着追踪共用内存的读写,最后把这些算法事实连接成证明。

  1. 01
    算法精读

    块选择与符号成本

    比较同一份输入的三种块表示,解释何时值得发送新编码。

    ↗
  2. 02
    算法精读

    位输出与字节缓冲

    把长短不齐的码字接成字节,再交给调用者。

    ↗
  3. 03
    算法精读

    共享存储与输出前缀

    理解共用一块内存时,怎样保护尚未读取的符号。

    ↗
  4. 04
    证明思路

    压缩输出的证明思路

    说明从符号到输出的每次写入怎样保留正确含义。

    ↗

全部精读主题

01 / 3 章

窗口与匹配 ↗

重复片段的长度与距离从哪里来,以及为什么只需保留近期字节。

02 / 3 章

Huffman 编码构造 ↗

让常见符号占更少比特,并让解码端重建同一套编码。

03 / 4 章

块与压缩输出 ↗

把选好的符号写成压缩块,并安全交给调用者。

04 / 4 章

位输入、解码表与复制 ↗

读取压缩字节、识别符号,并恢复出原来的数据。

05 / 3 章

流式状态与封装 ↗

理解同一任务为什么需要多次调用,以及暂停后怎样继续。

06 / 3 章

状态操作与资源生命周期 ↗

开始、复用、复制和结束任务,同时处理分配失败。

07 / 3 章

校验和与组合 ↗

在分批处理时核对数据,并保留支持序列合并的信息。

08 / 4 章

应用接口与外部交互 ↗

为完整缓冲区、回调和 gzip 文件选择合适的调用方式。

概览与精读的连接

概览中的主题深入实现对应论证
块类型与成本符号账目与三种块的成本符号与格式的含义
位序与位缓冲位寄存器、有效位数与待交付字节写入前后的位串关系
流式调用共享存储与输出交付前缀界与跨调用连接

完整参考

接口定义域、返回值和错误路径在函数页完整保留;引擎论证和 Lean 正文可以沿章节继续查阅。

全部公开 API ↗inflate / deflate ↗文档索引 ↗
ZLIB × LEAN

全局目录

当前位置zlib × Lean