Blaris：面向受限微控制器的无窗口随机访问LZSS压缩算法

大家好，HN的朋友们！我想分享一下我过去几个月一直在做的项目。在仅有几千字节内存（Flash和SRAM都算上）的微控制器上，heatshrink [1] 和 tamp [2] 是目前解压静态资源时的主流选择。它们体积小、可配置，而且压缩率不错。然而，当涉及随机访问工作流时（比如从配置文件中提取单个参数），这两个压缩器都需要分配完全相同的窗口。这意味着，要解压一小块（4-32字节）数据，内存消耗与解压整个负载时一样。blaris 是一种无窗口 LZSS 算法，也就是说它是 LZSS，但不分配窗口。这让它可以达到与 heatshrink 和 tamp 相同的压缩率（有时甚至更好），同时内存占用极低（大约 100 字节 SRAM）。典型的 LZ77/LZSS 在解析匹配时，会从窗口缓冲区复制一个字节。无窗口版本则利用压缩负载本身来解析这个匹配——沿着匹配链一直追溯到字面量游程 token。为了实现这一点，token 被拆分成 3 个流：1. 控制流（每个值 1 字节）——编码字面量游程长度（1 到 16）或 240 种不同的对（match_len, match_distance_log2）。2. 字面量流（每个值 1 字节）——原始字面量。3. 距离位流（位打包）——包含位打包的匹配偏移量。因为控制流是 1 字节，并且决定了 token 的大小，我们可以双向遍历全部 3 个流，这就实现了无窗口 LZSS！还有一些额外的优化用来加速：1. 检查点包含每个 2^SPREAD_LOG 位置的解码器状态，这让解码器能在常数时间内跳转到最近的检查点。2. 匹配的偏移量可以强制对齐到 2 的幂，以牺牲非对齐匹配为代价来增加匹配范围。3. 压缩端的最优解析器会给出输入的最佳可能表示。4. 链扁平化可以显著减少平均的匹配到匹配跳转次数，而只牺牲 1-2% 的压缩率。在解压小块数据（4-32字节）时，blaris 显著优于 heatshrink 和 tamp（1 字节读取快 500 倍）。对于更大的块，由于其解压时间与数据量线性相关，blaris 表现较差，但它本来就不是为此设计的。最棒的是，它在内存方面极其轻量。针对 RV32IMC 架构编译时，它只占用 548-784 字节的 Flash 内存，而无论文件大小如何，只使用 104-112 字节的 SRAM。作为对比，heatshrink 是 1300-1464 字节 Flash，根据窗口大小使用 206-16594 字节 SRAM，而 tamp 是 2238-3238 字节 Flash，同时使用 520-16672 字节 SRAM。[1] https://github.com/atomicobject/heatshrink[2] https://github.com/BrianPugh/tamp评论 URL：https://news.ycombinator.com/item?id=50499357 points: 1 # 评论：0