通用（近似）LZ77 事物

尝试制作一个包含所有以下内容的单个库：

• DEFLATE
• LZ4
• FastLZ
• Nintendo

这个包专门设计用于在 no_std 环境中工作，包括不要求任何运行时分配。然而，截至本文撰写时，它做出了消耗额外内存的权衡，因此它可能或可能不适合微控制器。

该包还设计为以“流式”方式工作，其中输入/输出数据分批次供应/生成，状态在调用之间保存在数据结构中。因此，它也假定输出目的地不可寻址。

算法

此包大致实现了与 gzip 用于 LZ77 压缩相同的精确算法，涉及使用字符串的前几个字节计算键的链式散列表。然而，它不是直接的移植，也不生成位相同的输出。此算法用于 每个 输出格式（这使得它比 FastLZ 等参考实现慢得多，但偶尔产生更好的压缩比率）。

与 gzip 不同，此包使用二进制合并包-收集问题算法生成长度限制的霍夫曼码。

性能

此包尚未针对性能进行优化，但似乎运行速度明显较慢。

关于替代方案的说明

此包最终遇到了 许多 Rust 限制。其中一些最显著的 hack 解决方案在此处记录。

常量泛型

由于 LZ77 引擎在所有格式之间共享，因此它使用常量泛型进行了大量参数化。但是，min_const_generics 不允许任何涉及常量泛型的计算，即使是计算例如数组大小。

解决方案是将所有必需的数字从最外层的非泛型级别传递下来，并在所有相关的 new 函数中编写断言以确保它们确实具有必须具有的值（例如，确保 MAX_LEN_PLUS_ONE 确实等于 MAX_LEN + 1）。

协程

为了显著简化解压缩函数的编写，最好采用简单的“获取输入，处理，写入输出，循环直到完成”模式。然而，这并不支持所需的“流式”用例。理想情况下，最好让编译器自动执行“无栈协程转换”以在两者之间进行转换。

目前，Rust中的协程API尚不稳定，但async是稳定的。实际上，async是建立在不稳定API之上的，并最终转换成它。因此，通过大量滥用async函数，编译器会为我们执行所需的转换。

为此，此crate包含足够的假异步执行器来轮询解压缩函数的future，直到它们阻塞需要更多输入（唤醒器完全被忽略）。此执行器包含与InputPeeker future之间的后通道，因此，当提供更多输入时，它被提供给InputPeeker进行读取。

出于人体工程学原因，这需要一小部分不安全代码，我们向编译器承诺，在解压缩函数耗尽输入时，传入的数据将不再被保留。没有这个，在循环中提供输入数据变得不可能。

创建协程

因为这个库是为no_std用例构建的，没有堆，解压缩状态存储在栈上。然而，唯一将此状态从用户抽象出来的方法是通过某种方式创建一个不卫生的宏（否则，所需的对象将超出作用域并被丢弃）。这是通过进程宏实现的，因为普通宏不能做到这一点。