AtomGit Flutter 鸿蒙客户端： Zlib 压缩算法的手写实现

心中有国也有家

367人浏览 · 2026-07-14 11:50:05

心中有国也有家 · 2026-07-14 11:50:05 发布

在这里插入图片描述

PNG 需要 zlib 压缩图像数据。不想依赖 dart:io 的 zlib ？自己手写一个"零压缩"版本。

一、为什么选择"零压缩"？

真正的 Deflate 压缩需要 LZ77 + Huffman 编码，实现复杂度极高（数千行代码）。对于 E-Brufen 的 512x512 图标（原始约 1MB），零压缩的 PNG 文件约 1MB——完全可以接受。

// 零压缩 = 数据直接存储，不压缩
// 文件略大，但编码器极简（~30 行）

★ Insight ─────────────────────────────────────
工程中的"最优解"不总是"压缩率最高"。零压缩方案用 1MB（而非 300KB）的文件大小换来了 30 行（而非 3000 行）的代码——这是典型的"够用就好"决策。当 PNG 只用一次（应用图标），1MB 完全可以接受。
─────────────────────────────────────────────────

二、Deflate 算法的前世今生

Deflate 这个名字来源于"压缩"（deflate = 放气），由 Phil Katz 在 1993 年为 PKZIP 2.0 设计。它的核心思想是将两个经典算法组合在一起，形成一个"两阶段"压缩流水线：

第一阶段 —— LZ77（Lempel-Ziv 1977）： 由 Abraham Lempel 和 Jacob Ziv 在 1977 年提出。核心思路是：数据中经常出现重复的字节序列，与其原样存储，不如用一个"指针"（距离 + 长度）来表示"往前看，找到之前出现过的那段内容"。比如 "hello hello" 可以编码为 "hello <后退5个字节, 长度5>"。Deflate 使用了一个 32KB 的滑动窗口作为 LZ77 的搜索范围。

第二阶段 —— Huffman 编码： 由 David Huffman 在 1952 年提出。统计 LZ77 输出的每个符号（字面量字节、长度码、距离码）的出现频率，高频符号分配短编码，低频符号分配长编码，从而在比特层面进一步压缩。

Deflate 的设计非常成功。它后来成为互联网时代最重要的压缩格式体系：

1992 年：Jean-loup Gailly 实现 gzip，在 Deflate 数据外层包裹了 gzip 头部（含文件名、时间戳）和 CRC32 尾部。
1995 年：Jean-loup Gailly 和 Mark Adler 设计 zlib，包裹了更紧凑的 2 字节头部和 Adler-32 尾部。
1996 年：PNG 格式诞生，选择 zlib 作为其图像数据的压缩层——这就是为什么我们写 PNG 编码器时需要实现 zlib。
至今：Deflate 家族几乎统治了无损压缩领域。HTTP 的 Content-Encoding: gzip / deflate、ZIP 文件、PDF、HTTP/2 头部压缩（HPACK）、Apache Parquet 列存格式……处处可见其身影。

RFC 1950（zlib）、RFC 1951（Deflate）、RFC 1952（gzip）三份文档共同定义了这一压缩标准家族。Phil Katz 本人于 2000 年不幸早逝，年仅 37 岁，但他留下的 Deflate 算法影响了此后三十年的互联网数据传输。

★ Insight ─────────────────────────────────────
Deflate 的优雅之处在于"组合优于发明"：LZ77 消除行级/块级冗余，Huffman 消除符号级冗余。两者各自解决不同层面的问题，组合后效果远超单独使用。这不是发明了一个全新的压缩算法，而是找到了两种已有算法的最佳协作方式。
─────────────────────────────────────────────────

三、Zlib 格式结构

┌─ CMF ────┐  1 byte: 0x78 (deflate, 32K window)
├─ FLG ────┤  1 byte: 0x01 (no dict, level 0)
├─ DATA ───┤  N bytes: deflate 压缩数据
├─ ADLER32 ┘  4 bytes: Adler-32 校验和

四、CMF + FLG

final out = <int>[0x78, 0x01];

字节	值	含义
CMF (0x78)	bits 0-3 = 8	Compression Method: deflate
	bits 4-7 = 7	Window size: 2^(7+8) = 32K
FLG (0x01)	bits 0-4 = 1	Check bits
	bit 5 = 0	No dictionary preset

五、Deflate 块（零压缩模式）

out.add(1);  // BFINAL=1, BTYPE=00
// BFINAL=1: 这是最后（也是唯一）一个块
// BTYPE=00: 无压缩存储

Deflate 支持三种块类型：

BTYPE	模式	压缩率
00	无压缩	0%
01	固定 Huffman	中等
10	动态 Huffman	最高

六、Huffman 编码简介——为什么"固定"和"动态"模式那么复杂

要理解为什么 BTYPE=01 和 BTYPE=10 各自需要上千行代码，我们需要先了解 Huffman 编码的工作原理。

Huffman 编码的核心思想： 给每个"符号"分配一个变长的二进制编码。出现频率高的符号用短的编码，出现频率低的符号用长的编码。关键约束是"前缀性"——没有任何编码是另一个编码的前缀，这样才能保证解码器从左到右读比特流时不会产生歧义。

构建 Huffman 树的过程：

统计所有符号的出现频率。
将每个符号放入一个优先队列（最小堆），频率越低优先级越高。
重复取出两个最低频率的节点，合并为一个新节点（频率 = 两者频率之和），放回队列。
最终形成一棵二叉树：从根节点出发，向左走记 0，向右走记 1，到达每个叶子节点的路径就是该符号的 Huffman 编码。

举个例子：假设数据中有三个字节，A（频率 50%）、B（频率 30%）、C（频率 20%）。构建过程是：先合并 C 和 B 得到一个频率 50% 的中间节点，再把这个中间节点和 A 合并成根节点。最终 A 的编码是 0（1 位），B 的编码是 10（2 位），C 的编码是 11（2 位）。

为什么 BTYPE=01（固定 Huffman）对编码端仍然复杂：

固定 Huffman 使用 RFC 1951 预定义的码表——你不需要传输 Huffman 树，省下了描述码表的开销。但对于编码端来说，你仍然需要：

实现完整的 Huffman 编码逻辑：查表将每个符号替换为对应的变长编码。
位级别的打包（bit packing）：因为你输出的不是字节，而是变长的比特流。需要维护一个"位缓冲区"，逐位写入，满 8 位才输出一个字节。
正确映射 LZ77 输出的 256 个字面量字节、长度码（29 个）和距离码（30 个）到固定码表。

换句话说，BTYPE=01 省去了传输码表的成本，但编码和解码逻辑一行都省不了。仅位缓冲区管理就需要近百行精心调试的代码。

为什么 BTYPE=10（动态 Huffman）更复杂：

动态 Huffman 是三种模式中最复杂的：

频率统计：扫描输入数据，统计每个符号的实际出现次数。
构建两棵 Huffman 树：一棵给字面量 + 长度（最多 288 个符号），一棵给距离（最多 32 个符号）。
码表本身的压缩：Deflate 对码表做了二次压缩——用游程编码（Run-Length Encoding）压缩 Huffman 树的描述（哪些符号用了多长的编码），再对游程编码的结果再做一次 Huffman 编码。这是"元压缩"——用 Huffman 压缩 Huffman 树的描述。
位精确输出：最终将压缩后的码表 + LZ77 + Huffman 编码的数据流按位精确输出。

一整套实现下来，一个生产质量的 Deflate 压缩器通常需要 2000-4000 行 C 代码。zlib 库的 deflate.c 文件——只实现了压缩端，不包括解压端——就有 2000+ 行。更不用说还要处理好内存分配、滑动窗口管理、匹配查找优化等工程细节。

// 零压缩 vs 真正 Deflate 的代码量对比
// 零压缩：一个函数，30 行
// BTYPE=01：需要 Huffman 编码器 + 位缓冲区，~500 行
// BTYPE=10：需要 LZ77 匹配器 + Huffman 树构建 + 码表压缩，~3000 行

七、LEN + NLEN

final len = data.length;
out.add(len & 0xFF);         // LEN 低字节
out.add((len >> 8) & 0xFF);  // LEN 高字节

final nlen = len ^ 0xFFFF;
out.add(nlen & 0xFF);         // NLEN 低字节
out.add((nlen >> 8) & 0xFF);  // NLEN 高字节

NLEN = LEN 的 1 补码（ones’ complement = len ^ 0xFFFF 或 ~len & 0xFFFF）。这是 Deflate 的完整性检查——如果 LEN != ~NLEN，数据已损坏。

然后直接写入原始数据：

out.addAll(data);

八、Adler-32 校验和

var s1 = 1, s2 = 0;
for (final b in data) {
  s1 = (s1 + b) % 65521;     // 字节累加，模 65521
  s2 = (s2 + s1) % 65521;    // 累加器的累加，模 65521
}

// 输出：s2 高字节, s2 低字节, s1 高字节, s1 低字节
out.add((s2 >> 8) & 0xFF);
out.add(s2 & 0xFF);
out.add((s1 >> 8) & 0xFF);
out.add(s1 & 0xFF);

Adler-32 = (s2 << 16) | s1，其中：

s1 = 所有字节的和（模 65521）
s2 = 所有 s1 的和（模 65521）

在 zlib 中，Adler-32 以大端字节序存储（s2 在前，s1 在后）。

⚠️ 65521 是 Adler-32 的关键——它是小于 2^16 的最大质数。使用质数模运算可以减少哈希碰撞。

九、质数 65521 的数学性质

Adler-32 选择了 65521 作为模数，而不是看起来更"整"的 65536（即 2^16）。这不是随意之举——65521 是小于 2^16 的最大质数，这个选择背后有着精妙的数学考量。

为什么必须用质数？

在模运算校验和中，模数的选择直接影响碰撞率。考虑一个简单的例子：如果我们用 65536 作为模数（即直接取低 16 位），那么高位的所有信息都会被直接丢弃。这意味着：如果数据中有两个字节同时增加了相同的值，这两个变化可能互相抵消——校验和完全检测不到错误。

而质数模数具有更好的代数结构：在模质数 p 下，非零元素构成一个循环群（cyclic group）。这意味着随着数据不断累加，s1 和 s2 的值能均匀地覆盖 0 到 p-1 的整个范围，不会"卡"在某些特定的值上，也不会产生周期性重复。

65521 = 2^16 - 15 的优化性质：

65521 不仅是质数，还因为接近 2^16 而可以绕过昂贵的除法指令。注意这个关系：

2^16 ≡ 15 (mod 65521)

因此，对于任意整数 v，可以用位移和乘法代替模运算：

// 快速模 65521（不需要除法，利用 2^16 ≡ 15 mod 65521）
int mod65521(int v) {
  // 等效于 v % 65521，但更快
  v = (v & 0xFFFF) + (v >> 16) * 15;
  // 最多再做一次减法即可
  return v >= 65521 ? v - 65521 : v;
}

推导：v = v_hi * 2^16 + v_lo，而 2^16 ≡ 15 mod 65521，所以 v ≡ v_hi * 15 + v_lo mod 65521。这个技巧在 Mark Adler 的原始实现中被广泛使用。

★ Insight ─────────────────────────────────────
65521 是一个"工程数学"的经典案例。纯粹从数学角度看，"小于 2^16 的最大质数"只是一个巧合；但从工程角度看，它同时满足了三个约束：(1) 是质数（降低碰撞率），(2) 小于 2^16（校验和只占 4 字节），(3) 接近 2^16（可以优化除法）。这就是优秀的工程设计——不是单一维度最优，而是多维约束下最"平衡"的解。
─────────────────────────────────────────────────

十、与 CRC32 的对比

特性	CRC32	Adler-32
位置	PNG 每个块末尾	zlib 末尾
目的	检测块数据损坏	检测解压后数据完整性
速度	较慢（逐位处理）	较快（逐字节加法）
碰撞概率	极低	较低

十一、zlib、gzip 与原始 Deflate 的区别

很多开发者在使用这三者时感到困惑——它们共享同一个核心压缩算法（Deflate），但有着不同的"包装"和适用场景。

	zlib	gzip	原始 Deflate
RFC	1950	1952	1951
头部	2 字节（CMF+FLG）	10+ 字节（ID1/ID2、压缩方法、时间戳、可选文件名等）	无
尾部	4 字节 Adler-32	4 字节 CRC32	无
典型用途	PNG、PDF 内部流、HTTP 响应	`.gz` 文件、HTTP `Content-Encoding: gzip` 响应	ZIP 存档条目内部
元信息支持	否	是（文件名、修改时间、操作系统）	否
多流拼接	是（连续多个 zlib 流）	是（`cat a.gz b.gz > c.gz` 有效）	否

如何选择：

选 zlib：当你在一个已有容器格式（如 PNG）内部使用压缩时。zlib 头部最紧凑（仅 2 字节），Adler-32 计算比 CRC32 快。PNG 规范明确要求使用 zlib 包裹的 Deflate。
选 gzip：当你需要压缩独立文件，并希望保留原始文件名、时间戳等元信息时。gzip 的头部包含了原始文件名和修改时间，解压后可以恢复。
选原始 Deflate：当你在 ZIP 文件内部或实现 HTTP Content-Encoding: deflate 时使用。注意：HTTP 的 deflate 历史上存在歧义——有些实现使用原始 Deflate，有些使用 zlib 包裹的 Deflate。实践中，HTTP gzip 比 HTTP deflate 更可靠。

在我们的 PNG 编码场景中，PNG 规范明确要求使用 zlib 格式——所以我们必须输出 CMF、FLG 头部（2 字节）和 Adler-32 尾部（4 字节），将原始 Deflate 数据块包裹在中间。这也是为什么本章从 zlib 头部开始，而不是直接写 Deflate 块。

十二、什么时候从零压缩切换到真正的 Deflate？

零压缩方案工作得很好——前提是数据量小且只压缩一次。但有些场景下，零压缩就力不从心了。以下是可以用来判断的切换信号：

1. 数据超过 50KB 时考虑切换

当 zlib 负载（如图像原始像素）超过约 50KB 时，零压缩的代价开始显现。一个 100KB 的原始数据经过真正的 Deflate 压缩后通常可以缩小到 30-40KB——省下 60% 的空间。

2. 图像有大量重复区域

图标、截图中的大面积纯色或渐变区域是 LZ77 的最爱。比如一个 512x512 的纯蓝色图标——零压缩存储了 262144 个相同的蓝色像素（每个 4 字节 RGBA），而 LZ77 只需几个字节就能描述"重复上一行"。压缩率可能达到 99% 以上。

3. 批量生成场景

如果一次生成 100 张不同尺寸的图标，总零压缩大小可能超过 100MB。换成真正的 Deflate，总体积轻松降到 30MB 以下——对存储和传输的影响是显著的。

4. 网络传输瓶颈

在移动网络环境中，尤其是在 HarmonyOS 的 IoT 设备场景中，每 KB 都影响加载速度。零压缩的 1MB 图标在弱网环境下可能需要 3-5 秒传输，而 300KB 的压缩版本只需 1 秒。

不想手写的替代方案：

如果确实需要真正的压缩但不想手写 2000 行代码，有几种选择：

dart:io 的 ZLibEncoder：一行代码搞定，但依赖 dart:io（Flutter Web 不可用）。
第三方纯 Dart 库：如 archive 包，提供了纯 Dart 的 GZipEncoder，跨平台可用。
FFI 调用系统 zlib：通过 dart:ffi 调用系统的 libz.so 或 zlib1.dll，最快速但需要处理平台差异。

在 E-Brufen 项目中，我们选择了零压缩——512x512 的图标约 1MB，仅在本地构建时使用一次，完全不是问题。等到未来需要生成大尺寸分享图片或批量导出时，再引入真正的 Deflate 也不迟。先上线，后优化——这种渐进式工程策略，在个人项目和早期产品中尤其高效。

十三、如何验证你的 zlib 输出

写完 zlib 编码器后，你肯定想知道生成的数据是否正确。以下是从简单到完整的四种验证方法：

方法 1：用 Python 一行验证

Python 标准库自带了 zlib 支持：

import zlib

# 读取你的 zlib 输出（去掉 PNG chunk 头部后）
with open('output_deflate.bin', 'rb') as f:
    compressed = f.read()

try:
    decompressed = zlib.decompress(compressed)
    print(f"验证通过！解压后 {len(decompressed)} 字节")
except Exception as e:
    print(f"解压失败：{e}")
    # 常见错误：
    # "Error -3 while decompressing" → 头部或 Adler-32 错误
    # "invalid block type" → BTYPE 字段值异常

如果 zlib 头部（CMF/FLG）、Deflate 块结构或 Adler-32 校验和有任何问题，Python 会抛出明确的异常信息，直接定位问题区域。

方法 2：用 OpenSSL 命令行

大多数系统都预装了 OpenSSL，它内置了 zlib 解压功能：

# 将 zlib 数据写入文件
echo -n -e '\x78\x01...' > test.zl

# OpenSSL 解压
openssl zlib -d < test.zl > decompressed.bin

# 检查结果
xxd decompressed.bin | head

方法 3：用十六进制编辑器手动检查

对于零压缩模式，输出的结构非常规律，可以用 xxd 逐字节验证：

xxd output.zlib | head -10
# 你应该看到类似这样的输出：
# 00000000: 7801 0100 0500 faff 4865 6c6c 6f00 0000  x.......Hello...
#          ^^ ^^ ^^ ^^^^ ^^^^
#          |  |  |  |    |
#          78=CMF  |  |    NLEN=0xFFFA (~5)
#            01=FLG  |    
#               01=BFINAL(1)+BTYPE(00)
#                   LEN=5 (0x0005, little-endian)

对于零压缩，LEN 之后紧跟着原始数据，最后 4 字节是 Adler-32。这种逐字节验证能帮你发现位级错误。

方法 4：单元测试（强烈推荐）

将 zlib 编码器用单元测试覆盖起来，确保未来的修改不会引入回归：

import 'package:test/test.dart';

void test_zlibCompress() {
  final input = [0x48, 0x65, 0x6C, 0x6C, 0x6F]; // "Hello"
  final output = zlibCompress(input);
  
  // 1. 检查头部
  expect(output[0], equals(0x78));            // CMF
  expect(output[1], equals(0x01));            // FLG
  
  // 2. 检查 BFINAL + BTYPE
  expect(output[2] & 0x01, equals(1));        // BFINAL=1
  expect((output[2] >> 1) & 0x03, equals(0)); // BTYPE=00
  
  // 3. 用已知的参考输出做完整比对
  // 这个参考值可以提前用 Python zlib.compress(b"Hello") 生成
  final expected = [
    0x78, 0x01,                         // zlib header
    0x01,                               // BFINAL=1, BTYPE=00
    0x05, 0x00,                         // LEN = 5
    0xFA, 0xFF,                         // NLEN = ~5
    0x48, 0x65, 0x6C, 0x6C, 0x6F,      // "Hello"
    0x02, 0x86, 0x01, 0x26              // Adler-32
  ];
  expect(output, equals(expected));
}

void test_zlibCompress_emptyData() {
  // 空数据边界测试
  final output = zlibCompress([]);
  expect(output[0], equals(0x78));
  expect(output[1], equals(0x01));
  // 空数据的 Adler-32 = (s2<<16)|s1 = (0<<16)|1 = 1
  expect(output[output.length - 4], equals(0x00));
  expect(output[output.length - 3], equals(0x00));
  expect(output[output.length - 2], equals(0x00));
  expect(output[output.length - 1], equals(0x01));
}

有了这些验证手段，你就可以放心地使用手写的 zlib 编码器了。建议在 CI 中跑单元测试，每次提交都确保 zlib 输出的正确性。

十四、完整的数据流

PNG IDAT 块数据流：
  Raw pixels (RGBA, filter byte 0)
    → _zlibCompress()
      → [0x78, 0x01]           // zlib header
      → [1]                     // BFINAL=1, BTYPE=00
      → [LEN_LO, LEN_HI]        // 块长度
      → [NLEN_LO, NLEN_HI]      // 1补码
      → [raw pixel data...]     // 原始数据
      → [ADLER32 bytes...]      // 校验和
    → 写入 IDAT chunk

小结

手写 zlib 压缩听起来吓人，但"零压缩模式"将其简化为 ~30 行代码。这再次验证了 E-Brufen 的工程哲学：理解本质后，选择最简单的实现。真正的 Deflate 压缩可以等需要时再引入。

从 LZ77 + Huffman 的经典组合，到 Adler-32 中 65521 这个精妙的质数选择，到 zlib/gzip/Deflate 三者的定位差异——当我们打开了 zlib 这个"黑盒"，里面处处是计算机科学和工程实践交织的智慧。希望这篇文章不仅帮你在鸿蒙 Flutter 中写出正确的 PNG 编码器，也能让你对这一整套压缩技术体系有更深的理解。