跳到正文
ZLIB × LEAN / 算法精读与验证

位输入、解码表与复制

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

这一环节的任务

解压器识别块和编码表,把比特还原成字面量与匹配。字面量直接成为字节;匹配则从历史逐字节复制,重新产生原来的内容。

在全局图中定位 ↗

前 3 章先展开算法、数据布局与优化,最后一章连接证明思路。可以按顺序读,也可以从已经熟悉的阶段进入。

  1. 01
    算法精读

    位输入与预读

    暂存分批到达的字节,只取走当前字段需要的位。

    ↗
  2. 02
    算法精读

    解码表的实际构造

    把码长描述变成一张能直接查出符号的表。

    ↗
  3. 03
    算法精读

    快速解码与回引用复制

    把长度和距离恢复成原文,并理解批量解码怎样加速。

    ↗
  4. 04
    证明思路

    解码器的证明思路

    把读位、查表和复制连接成同一份解码承诺。

    ↗
ZLIB × LEAN

全局目录

当前位置位输入、解码表与复制