FastLZ
1.0.0
FASTLZ (MIT-Lizenz) ist eine ANSI C/C90-Implementierung des Lempel-Ziv 77-Algorithmus (LZ77) der verlustfreien Datenkomprimierung. Es ist geeignet, eine Reihe von Text/Absätzen, Sequenzen von Rohpixeldaten oder anderen Datenblöcken mit viel Wiederholung zu komprimieren. Es ist nicht gedacht, in Bildern, Videos und anderen Datenformaten verwendet zu werden, die normalerweise bereits in optimaler komprimierter Form sind.
Der Fokus für Fastlz liegt auf einer sehr schnellen Komprimierung und Dekompression, die dies auf Kosten des Komprimierungsverhältnisses tut. Als Illustration ist der Vergleich mit ZLIB bei der Komprimierung von Enwik8 (auch in Details):
| Verhältnis | Kompression | Dekompression | |
|---|---|---|---|
| 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 wird von vielen Softwareprodukten verwendet, von einer Reihe von Spielen (z. B. Death Stranding) bis hin zu verschiedenen Open-Source-Projekten (Godot Engine, Facebook HHVM, Apache Traffic Server, Calligra Office, OSV, Netty usw.). Es dient sogar als Grundlage für andere Komprimierungsprojekte wie Blosc.
Für andere Implementierungen von Byte-ausgerichteten LZ77 schauen Sie sich LZ4, Snappy, Dichte, LZO, LZF, LZJB, LZRW usw. ans.
FASTLZ kann direkt in C/C ++ - Anwendungen verwendet werden. Verwenden Sie für andere Programmiersprachen/Umgebungen die entsprechende Bindung:
cargo install fastlzpip install fastlznpm install fastlzgem install fastlz Fastlz besteht aus nur zwei Dateien: fastlz.h und fastlz.c . Fügen Sie diese Dateien einfach Ihrem Projekt hinzu, um FASTLZ zu verwenden. Für die detaillierten Informationen zur API zur Durchführung von Komprimierung und Dekompression siehe fastlz.h .
Für VCPKG -Benutzer ist FASTLZ bereits verfügbar: vcpkg install fastlz .
Ein einfacher Dateikompressor namens 6pack ist als Beispiel für die Verwendung von FASTLZ enthalten. Der entsprechende Dekompressor ist 6unpack .
FASTLZ unterstützt alle standardmäßigen konformen ANSI C/C90-Compiler, einschließlich der beliebten wie GCC, Clang, Visual Studio und sogar Tiny CC. Fastlz arbeitet gut an einer Reihe von Architekturen (32-Bit und 64-Bit, Big Endian und Little Endian), von Intel/AMD, Powerpc, System Z, Arm, MIPS und RISC-V.
Das kontinuierliche Integrationssystem führt auf den folgenden Systemen einen umfassenden Satz von Rundreisen der Kompressionsdeko-Dokumente aus:
Weitere Informationen finden Sie in den entsprechenden GitHub -Aktionen Build -Protokollen.
| AMD64 | Linux | Fenster | macos |
| GCC | |||
| Klang | |||
| Tinycc | |||
| Vs 2019 | |||
| I686 | Linux | Fenster | macos |
| GCC | |||
| Klang | |||
| Tinycc | |||
| Vs 2019 | |||
| i586 | Linux | DOS | |
| GCC | |||
| Linux | |||
| Powerpc | |||
| GCC | |||
| PPC64 (LE) | |||
| GCC | |||
| GCC | |||
| S390X | |||
| GCC | |||
| Armhf | |||
| GCC | |||
| ARM64 | |||
| GCC | |||
| MIPS (EL) | |||
| GCC | |||
| GCC | |||
| MIPS64 (el) | |||
| GCC | |||
| GCC | |||
| RISCV | |||
| GCC | |||
| RISCV64 | |||
| GCC |
Nehmen wir an, dass FASTLZ eine Reihe von Bytes, die als unkomprimierter Block bezeichnet wird, in ein anderes Array von Bytes, den als komprimierten Block bezeichnet wird, als komprimierter Block komprimiert. Um zu verstehen, was im komprimierten Block gespeichert wird, ist es veranschaulichend zu demonstrieren, wie schnell der Block dekomprimiert wird, um den ursprünglichen unkomprimierten Block abzurufen.
Der erste 3-Bit des Blocks, dh die drei signifikantesten Bits des ersten Byte, ist das Block-Tag . Derzeit bestimmt das Block -Tag die Komprimierungsebene, die zur Herstellung des komprimierten Blocks verwendet wird.
| Block -Tag | Kompressionsniveau |
|---|---|
| 0 | Stufe 1 |
| 1 | Stufe 2 |
Der Inhalt des Blocks variiert je nach Komprimierungsstufe.
Fastlz Level 1 implementiert den LZ77 -Komprimierungsalgorithmus mit 8 KB -Schiebfenster und bis zu 264 Bytes der Spiellänge.
Der komprimierte Block besteht aus einer oder mehreren Anweisungen . Jeder Befehl beginnt mit einem 1-Byte-Opcode, 2-Byte-Opcode oder 3-Byte-Opcode.
| Anleitungstyp | Opcode [0] | Opcode [1] | Opcode [2] |
|---|---|---|---|
| Wörtlicher Lauf | 000 , l₄-l₀ | - - | - - |
| Kurzes Match | M₂-M₀, r₁₂-r₈ | R₇-r₀ | - - |
| Langes Match | 111 , r₁₂-r₈ | M₇-M₀ | R₇-r₀ |
Beachten Sie, dass die allererste Anweisung in einem komprimierten Block immer ein wörtlicher Lauf ist.
Für den literalischen Anweisungen folgen ein oder mehrere Bytes dem Code. Dies wird als wörtlicher Lauf bezeichnet.
Die 5 am wenigsten signifikanten Bits von opcode[0] , L , bestimmt die Anzahl der Literale nach dem Opcode. Der Wert von 0 zeigt einen 1-Byte-Liter-Lauf an, 1 zeigt einen 2-Byte-Liter-Lauf an und so weiter. Der minimale Liter -Lauf beträgt 1 und der maximale literale Lauf beträgt 32.
Die Dekompressorkopien ( L + 1 ) Bytes des buchstäblichen Laufs, beginnend mit dem ersten direkt nach Opcode.
Beispiel : Wenn der komprimierte Block ein 4-Byte-Array von [0x02, 0x41, 0x42, 0x43] ist, ist der Opcode 0x02 und das bedeutet ein wörtlicher Lauf von 3 Bytes. Der Dekompressor kopiert dann die nachfolgenden 3 Bytes [0x41, 0x42, 0x43] in den Ausgangspuffer. Der Ausgangspuffer repräsentiert nun den (ursprünglichen) unkomprimierten Block [0x41, 0x42, 0x43] .
Die 3 meist signifikantesten Bits von opcode[0] , m , bestimmt die Übereinstimmungslänge . Der Wert von 1 zeigt eine 3-Byte-Übereinstimmung an, 2 zeigt eine 4-Byte-Übereinstimmung an und so weiter. Die minimale Matchlänge beträgt 3 und die maximale Übereinstimmungslänge 8.
Die 5 am wenigsten signifikanten Bits von opcode[0] in Kombination mit den 8 Bit des opcode[1] , r , bestimmt den Referenzversatz . Da der Offset in 13 Bit codiert ist, beträgt das Minimum 0 und das Maximum 8191.
Der folgende C -Code ruft den Übereinstimmung der Übereinstimmung und Referenzversetzt ab:
M = opcode [ 0 ] >> 5 ;
R = 256 * ( opcode [ 0 ] << 5 ) + opcode [ 1 ];Die Dekompressor -Kopien (M+2) Bytes, beginnend mit dem von R im Ausgangspuffer ausgeglichenen Standort. Beachten Sie, dass R eine Back -Referenz ist, dh der Wert von 0 entspricht dem letzten Byte im Ausgangspuffer, 1 ist das zweite zuletztes Byte und so weiter.
Beispiel 1 : Wenn der komprimierte Block ein 7-Byte-Array von [0x03, 0x41, 0x42, 0x43, 0x44, 0x20, 0x02] ist, gibt es in der dort zwei Anweisungen. Die erste Anweisung ist der wörtliche Lauf von 4 Bytes (aufgrund von L = 3 ). Somit kopiert der Dekompressor 4 Bytes in den Ausgangspuffer, was zu [0x41, 0x42, 0x43, 0x44] führt. Die zweite Anweisung ist die kurze Übereinstimmung von 3 Bytes (ab M = 1 , dh 0x20 >> 5 ) und der Versatz von 2. Daher geht der Kompressor 2 Bytes aus der letzten Position zurück, kopiert 3 Bytes ( [0x42, 0x43, 0x44] ) und wenden Sie sie zum Ausgabepuffer an. Der Ausgangspuffer repräsentiert nun die vollständigen unkomprimierten Daten [0x41, 0x42, 0x43, 0x44, 0x42, 0x43, 0x44] .
Beispiel 2 : Wenn der komprimierte Block ein 4-Byte-Array von [0x00, 0x61, 0x40, 0x00] ist, gibt es dort zwei Anweisungen. Die erste Anweisung ist der wörtliche Lauf von nur 1 Byte ( l = 0 ). Somit kopiert der Dekompressor das Byte ( 0x61 ) in den Ausgangspuffer. Der Ausgangspuffer wird nun [0x61] . Die zweite Anweisung ist die kurze Übereinstimmung von 4 Bytes (ab M = 2 , dh 0x40 >> 5 ) und der Versatz von 0. Daher kopiert der Dekompressor 4 Bytes mit der Rückseite von 0 (dh der Position von 0x61 ). Der Ausgangspuffer repräsentiert nun die vollständigen unkomprimierten Daten [0x61, 0x61, 0x61, 0x61, 0x61] .
Der Wert von opcode[1] , m , bestimmt die Übereinstimmungslänge . Der Wert von 0 zeigt eine 9-Byte-Übereinstimmung an, 1 zeigt eine 10-Byte-Übereinstimmung an und so weiter. Die minimale Matchlänge beträgt 9 und die maximale Übereinstimmungslänge 264.
Die 5 am wenigsten signifikanten Bits von opcode[0] in Kombination mit den 8 Bits von opcode[2] , R , bestimmt den Referenzversatz . Da der Offset in 13 Bit codiert ist, beträgt das Minimum 0 und das Maximum 8191.
Der folgende C -Code ruft den Übereinstimmung der Übereinstimmung und Referenzversetzt ab:
M = opcode [ 1 ];
R = 256 * ( opcode [ 0 ] << 5 ) + opcode [ 2 ];Die Dekompressor -Kopien (M+9) -Bytes, beginnend mit dem von R im Ausgangspuffer ausgeglichenen Standort. Beachten Sie, dass R eine Back -Referenz ist, dh der Wert von 0 entspricht dem letzten Byte im Ausgangspuffer, 1 ist für das zweite bis zuletzte Byte und so weiter.
Beispiel : Wenn der komprimierte Block ein 4-Byte-Array von [0x01, 0x44, 0x45, 0xE0, 0x01, 0x01] ist, gibt es dort zwei Anweisungen. Die erste Anweisung ist der wörtliche Lauf mit der Länge von 2 (aufgrund von L = 1 ). Somit kopiert der Dekompressor den 2-Byte-Liter-Lauf ( [0x44, 0x45] ) zum Ausgangspuffer. Die zweite Anweisung ist die lange Übereinstimmung mit der Matchlänge von 10 (ab M = 1 ) und dem Versatz von 1. Daher kopiert der Dekompressor 10 Bytes mit der Rücklage von 1 (dh der Position von 0x44 ). Der Ausgangspuffer repräsentiert nun die vollständigen unkomprimierten Daten [0x44, 0x45, 0x44, 0x45, 0x44, 0x45, 0x44, 0x45, 0x44, 0x45, 0x44, 0x45] .
Die folgende 40-Linie-C-Funktion implementiert einen voll funktionsfähigen Dekompressor für das obige Blockformat. Beachten Sie, dass es beabsichtigt ist, pädagogisch zu sein, z. B. kein gebundener Scheck implementiert und daher für die Produktion absolut unsicher ist.
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 ;
}
}
}
}(Geschrieben werden)
