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。
opcode[0]的5個最不重要的位與opcode[2] ， R的8位確定參考偏移。由於偏移量以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 ;
}
}
}
}（要寫）
