FastLZ
1.0.0
FastLZ（MIT许可证）是无损耗数据压缩的Lempel-Ziv 77算法（LZ77）的ANSI C/C90实现。它适合压缩一系列文本/段落，原始像素数据的序列或具有大量重复的任何其他数据块。它不打算用于图像，视频和其他数据格式，通常以最佳的压缩形式使用。
FastLZ的重点是非常快速的压缩和减压，以压缩比为代价。作为例证，在压缩ENWIK8时与Zlib的比较（也有更多详细信息）：
| 比率 | 压缩 | 减压 | |
|---|---|---|---|
| fastlz | 54.2％ | 159 MB/s | 305 MB/s |
| Zlib -1 | 42.3％ | 50 MB/s | 184 MB/s |
| Zlib -9 | 36.5％ | 11 MB/s | 185 MB/s |
Fastlz被许多软件产品使用，从许多游戏（例如死亡搁浅）到各种开源项目（Godot Engine，Facebook HHVM，Apache Traffic Server，Calligra Office，OSV，Netty等）。它甚至是Blosc等其他压缩项目的基础。
有关字节对准LZ77的其他实现，请查看LZ4，快速，密度，LZO，LZF，LZJB，LZJB，LZRW等。
Fastlz可以直接在任何C/C ++应用中使用。对于其他编程语言/环境，请使用相应的绑定：
cargo install fastlzpip install fastlznpm install fastlzgem install fastlz Fastlz仅由两个文件组成： fastlz.h和fastlz.c 。只需将这些文件添加到您的项目中即可使用fastlz。有关API执行压缩和减压的详细信息，请参见fastlz.h 。
对于VCPKG用户，Fastlz已经可用： vcpkg install fastlz 。
包括一个名为6pack的简单文件压缩机作为如何使用fastlz的示例。相应的解压缩器为6unpack 。
FASTLZ支持任何标准构成的ANSI C/C90编译器，包括受欢迎的编译器，例如GCC，Clang，Visual Studio，甚至是Tiny CC。 Fastlz从Intel/AMD，PowerPC，System Z，ARM，MIPS和RISC-V上使用了许多体系结构（32位和64位，大型Endian和Little Endian）的许多体系结构（32位和64位）。
连续的集成系统在以下系统上运行了一组大量的压缩压缩圆旅程：
有关更多详细信息，请检查相应的GitHub操作构建日志。
| AMD64 | Linux | 视窗 | macos |
| 海湾合作委员会 | |||
| 铛 | |||
| tinycc | |||
| vs 2019 | |||
| I686 | Linux | 视窗 | macos |
| 海湾合作委员会 | |||
| 铛 | |||
| tinycc | |||
| vs 2019 | |||
| i586 | Linux | dos | |
| 海湾合作委员会 | |||
| Linux | |||
| PowerPC | |||
| 海湾合作委员会 | |||
| PPC64（LE） | |||
| 海湾合作委员会 | |||
| 海湾合作委员会 | |||
| S390X | |||
| 海湾合作委员会 | |||
| Armhf | |||
| 海湾合作委员会 | |||
| ARM64 | |||
| 海湾合作委员会 | |||
| mips（el） | |||
| 海湾合作委员会 | |||
| 海湾合作委员会 | |||
| MIPS64（EL） | |||
| 海湾合作委员会 | |||
| 海湾合作委员会 | |||
| Riscv | |||
| 海湾合作委员会 | |||
| Riscv64 | |||
| 海湾合作委员会 |
让我们假设Fastlz压缩一个字节数组，称为未压缩块，将字节数组称为另一个字节，称为压缩块。要了解将存储在压缩块中的内容，可以说明说明Fastlz将如何解压缩块以检索原始未压缩块。
块的第一个3位，即第一个字节的3个最重要的位是块标签。当前，块标签确定用于产生压缩块的压缩水平。
| 块标签 | 压缩水平 |
|---|---|
| 0 | 1级 |
| 1 | 级别2 |
块的内容将根据压缩水平而有所不同。
FastLZ 1级实现LZ77压缩算法，带有8 kb滑动窗口，最多264个字节的匹配长度。
压缩块由一个或多个说明组成。每种说明都以1字节OPCODE，2字节OPCODE或3字节OPCODE开始。
| 指令类型 | opcode [0] | opcode [1] | opcode [2] |
|---|---|---|---|
| 字面跑步 | 000 ，l₄-l₀ | - | - |
| 短比赛 | m₂-m₀，r₁₂-r₈ | r₇-r₀ | - |
| 长比赛 | 111 ，r₁₂-r₈ | m₇-m₀ | R₇-R₀ |
请注意，压缩块中的第一个指令始终是字面运行。
对于文字运行指令，遵循代码有一个或多个字节。这称为字面运行。
opcode[0] ， l的5个最不重要的位确定了opcode之后的文字数量。 0的值表示1字节字面运行，1表示2字节字面运行，依此类推。最小文字运行为1，最大文字运行为32。
解压缩器副本（ L + 1 ）字节的文字运行，从Opcode之后的第一个开始。
示例：如果压缩块是[0x02, 0x41, 0x42, 0x43]的4字节阵列，则OPCODE为0x02 ，这意味着3个字节的字面运行。然后，解压缩器将将后续3个字节[0x41, 0x42, 0x43]复制到输出缓冲区。输出缓冲区现在表示（原始）未压缩块， [0x41, 0x42, 0x43] 。
opcode[0] ， m最重要的位最重要的位确定匹配长度。 1的值表示3字节匹配，2表示4字节匹配等。最小匹配长度为3，最大匹配长度为8。
opcode[0]的5个最不重要的位与opcode[1] R的8位确定参考偏移。由于偏移量以13位编码，最小值为0，最大值为8191。
以下C代码检索匹配长度和参考偏移：
M = opcode [ 0 ] >> 5 ;
R = 256 * ( opcode [ 0 ] << 5 ) + opcode [ 1 ];解压缩器副本（M+2）字节，从输出缓冲区中R偏移的位置开始。请注意， r是返回引用，即0的值对应于输出缓冲区中的最后一个字节，1是第二个字节，依此类推。
示例1 ：如果压缩块是[0x03, 0x41, 0x42, 0x43, 0x44, 0x20, 0x02]的7字节阵列，则其中有两个说明。第一个指令是4个字节的字面运行（由于L = 3 ）。因此，解压缩器将4个字节复制到输出缓冲区，从而导致[0x41, 0x42, 0x43, 0x44] 。第二个指令是3个字节的短匹配（从m = 1 ，即0x20 >> 5 ）和2的偏移。因此，压缩机从最后一个位置返回2个字节，复制3个字节（ [0x42, 0x43, 0x44] ），并将它们附加到输出缓冲区中。输出缓冲区现在表示完整的未压缩数据， [0x41, 0x42, 0x43, 0x44, 0x42, 0x43, 0x44] 。
示例2 ：如果压缩块是[0x00, 0x61, 0x40, 0x00]的4字节阵列，则其中有两个说明。第一个指令是仅1个字节的字面运行（ L = 0 ）。因此，解压缩器将字节（ 0x61 ）复制到输出缓冲区。输出缓冲区现在变为[0x61] 。第二个指令是4个字节的短匹配（从m = 2 ，即0x40 >> 5 ）和0的偏移。因此，解压缩器复制4个字节开始使用0（即0x61的位置）启动。输出缓冲区现在表示完整的未压缩数据， [0x61, 0x61, 0x61, 0x61, 0x61] 。
opcode[1] ， m的值确定匹配长度。 0表示9字节匹配，1表示10字节匹配等。最小匹配长度为9，最大匹配长度为264。
The 5 least-significant bits of opcode[0] combined with the 8 bits of opcode[2] , R , determines the reference offset .由于偏移量以13位编码，最小值为0，最大值为8191。
以下C代码检索匹配长度和参考偏移：
M = opcode [ 1 ];
R = 256 * ( opcode [ 0 ] << 5 ) + opcode [ 2 ];解压缩器副本（M+9）字节，从输出缓冲区中R偏移的位置开始。请注意， r是返回引用，即0的值对应于输出缓冲区中的最后一个字节，1为第二个字节，依此类推。
示例：如果压缩块是[0x01, 0x44, 0x45, 0xE0, 0x01, 0x01]的4字节数组，则其中有两个说明。第一个指令是长度为2的字面运行（由于L = 1 ）。因此，解压缩器将2字节字面运行（ [0x44, 0x45] ）复制到输出缓冲区。第二个指令是匹配长度为10（从m = 1 ）和1的偏移的长匹配。因此，解压缩器复制了10个字节开始使用1（即0x44的位置）开始。输出缓冲区现在表示完整的未压缩数据， [0x44, 0x45, 0x44, 0x45, 0x44, 0x45, 0x44, 0x45, 0x44, 0x45, 0x44, 0x45] 。
以下40行C函数实现了上述块格式的彻底功能解压缩器。请注意，它旨在具有教育性，例如无限制检查，因此绝对不安全。
void fastlz_level1_decompress ( const uint8_t * input , int length , uint8_t * output ) {
int src = 0 ;
int dest = 0 ;
while ( src < length ) {
int type = input [ src ] >> 5 ;
if ( type == 0 ) {
/* literal run */
int run = 1 + input [ src ];
src = src + 1 ;
while ( run > 0 ) {
output [ dest ] = input [ src ];
src = src + 1 ;
dest = dest + 1 ;
run = run - 1 ;
}
} else if ( type < 7 ) {
/* short match */
int ofs = 256 * ( input [ src ] & 31 ) + input [ src + 1 ];
int len = 2 + ( input [ src ] >> 5 );
src = src + 2 ;
int ref = dest - ofs - 1 ;
while ( len > 0 ) {
output [ dest ] = output [ ref ];
ref = ref + 1 ;
dest = dest + 1 ;
len = len - 1 ;
}
} else {
/* long match */
int ofs = 256 * ( input [ src ] & 31 ) + input [ src + 2 ];
int len = 9 + input [ src + 1 ];
src = src + 3 ;
int ref = dest - ofs - 1 ;
while ( len > 0 ) {
output [ dest ] = output [ ref ];
ref = ref + 1 ;
dest = dest + 1 ;
len = len - 1 ;
}
}
}
}（要写）
