用于嵌入式使用的紧凑型解压缩库

Question

我们目前正在为客户创建一个设备,它将从PC应用程序中获取一块数据(例如,5-10KB).这有点简化,因此假设数据必须经过多次传递和解压缩,而不是每年一次.通信通道非常非常慢,因此我们希望事先压缩数据,传递给设备并让数据解压缩到内部闪存.然而,设备本身在微控制器上运行,该控制器不是很快并且没有大量内存.它有足够的闪存来存储结果,并且可以在接收时解压缩数据块,但它可能没有足够的RAM来存储整个压缩或未压缩(甚至两个!)数据块.当然,它没有操作系统或其他奢侈品.

这意味着我们需要一个足够快速的无压缩算法,它不会占用大量内存.压缩可能是缓慢而丑陋的,因为我们在PC端进行压缩.C或.NET代码首选,但压缩,以使事情更容易.解压缩代码应该在C中,因为某人不太可能为我们的控制器提供ASM优化版本.

我们发现LZO对我们来说几乎是完美的,但它默认有一个所谓的"免费"许可证(GPL),这使得它对我们的客户来说完全无法使用.作者说,商业许可证可以根据要求提供,但不幸的是他目前无法访问(出于非技术原因,如他网站上的新闻所说).

我找到了一些其他的库,包括zlib的puff.c,我们还在调查,但我想我会问你的经验:

鉴于解压缩设备的资源非常有限,需要源代码和商业许可证,您建议将哪种压缩算法和/或库用于嵌入式目的？

Answer 1

您可能想要查看其中一个不是GPL并且是相当紧凑的实现:

• fastlz - MIT许可证,相当简单的代码
• lzjb - sun CDDL,在zfs中用于压缩,简单而且非常短
• liblzf - BSD风格的许可证,小巧,快速
• lzfx - BSD风格,基于liblzf,小巧,快速

这些算法都基于Lempel-Ziv-Welch的原始算法(它们共有所有LZ) https://en.wikipedia.org/wiki/Lempel-Ziv-Welch

Answer 2

我用过LZSS.我使用了Haruhiko Okumura的代码作为基础.它使用未压缩数据的最后部分(2K)作为字典.如果没有内存,可以修改此代码以不需要临时环形缓冲区.许可证在他的网站上并不清楚,但是一些版本发布了"免费使用,分发和修改此程序"行,并且代码由商业供应商使用.

这是一个基于相同代码的实现,它构成了Allegro游戏库的一部分.Allegro许可是礼品或zlib.

另一种选择可能是实现LZF 的lzfx lib.我还没用过,但看起来不错.还使用以前的结果,因此它具有较低的内存要求,并在BSD许可下发布.

Answer 3

一种替代方案是基本压缩库中的 LZ77 编码器/解码器。

由于它的字典使用未压缩的数据历史记录，因此除了压缩和未压缩的数据缓冲区之外，它不使用额外的 RAM。它应该非常适合您的用例（zlib 许可证、可移植 C）。整个解码器只有 70 行代码（包括注释），而且速度非常快。

编辑：另一种选择是liblzg库，它是上述 LZ77 编码器/解码器的改进版本。它压缩效果更好，通常速度更快，并且不需要内存来解压缩。它非常非常免费（zlib 许可证）。