FastLZ
1.0.0
FastLZ (licence MIT) est une implémentation ANSI C / C90 de l'algorithme Lempel-Ziv 77 (LZ77) de la compression de données sans perte. Il convient à compresser des séries de texte / paragraphes, de séquences de données de pixels brutes ou de tout autre bloc de données avec beaucoup de répétition. Il n'est pas destiné à être utilisé sur des images, des vidéos et d'autres formats de données généralement déjà sous une forme compressée optimale.
L'objectif de FastLZ est une compression et une décompression très rapides, ce qui le faisait au prix du rapport de compression. Comme illustration, la comparaison avec ZLIB lors de la compression d'Enwik8 (également plus de détails):
| Rapport | Compression | Décompression | |
|---|---|---|---|
| Fastlz | 54,2% | 159 Mb / s | 305 Mb / s |
| zlib -1 | 42,3% | 50 Mo / s | 184 Mb / s |
| ZLIB -9 | 36,5% | 11 Mo / s | 185 Mb / s |
Fastlz est utilisé par de nombreux produits logiciels, de plusieurs jeux (tels que Death Stranding) à divers projets open-source (Godot Engine, Facebook HHVM, Apache Traffic Server, Calligra Office, OSV, Netty, etc.). Il sert même de base à d'autres projets de compression comme BLOSC.
Pour d'autres implémentations de LZ77 aligné par les octets, jetez un œil à LZ4, Snappy, Density, LZO, LZF, LZJB, LZRW, etc.
FastLZ peut être utilisé directement dans toutes les applications C / C ++. Pour d'autres langages / environnements de programmation, utilisez la liaison correspondante:
cargo install fastlzpip install fastlznpm install fastlzgem install fastlz Fastlz ne se compose que de deux fichiers: fastlz.h et fastlz.c . Ajoutez simplement ces fichiers à votre projet afin d'utiliser Fastlz. Pour les informations détaillées sur l'API pour effectuer la compression et la décompression, voir fastlz.h .
Pour les utilisateurs de VCPKG, FastLZ est déjà disponible: vcpkg install fastlz .
Un compresseur de fichiers simple appelé 6pack est inclus comme exemple sur la façon d'utiliser Fastlz. Le décompresseur correspondant est 6unpack .
FastLZ prend en charge tout compilateur ANSI C / C90 conforme standard, y compris ceux populaires tels que GCC, Clang, Visual Studio et même Tiny CC. Fastlz fonctionne bien sur un certain nombre d'architectures (32 bits et 64 bits, Big Endian et Little Endian), d'Intel / AMD, PowerPC, System Z, ARM, MIPS et RISC-V.
Le système d'intégration continue exécute un vaste ensemble d'aller-retour en décompression de compression sur les systèmes suivants:
Pour plus de détails, vérifiez les journaux de construction de GitHub Actions correspondants.
| AMD64 | Linux | Fenêtre | macos |
| GCC | |||
| Bruit | |||
| Tinycc | |||
| Vs 2019 | |||
| i686 | Linux | Fenêtre | macos |
| GCC | |||
| Bruit | |||
| Tinycc | |||
| Vs 2019 | |||
| i586 | Linux | Dos | |
| GCC | |||
| Linux | |||
| powerpc | |||
| GCC | |||
| PPC64 (LE) | |||
| GCC | |||
| GCC | |||
| S390X | |||
| GCC | |||
| armer | |||
| GCC | |||
| arm64 | |||
| GCC | |||
| MIPS (EL) | |||
| GCC | |||
| GCC | |||
| MIPS64 (EL) | |||
| GCC | |||
| GCC | |||
| riscv | |||
| GCC | |||
| RISCV64 | |||
| GCC |
Supposons que Fastlz comprime un tableau d'octets, appelé bloc non compressé , dans un autre tableau d'octets, appelé bloc comprimé . Pour comprendre ce qui sera stocké dans le bloc comprimé, il est illustratif de démontrer à quelle vitesse le bloc décompressera le bloc pour récupérer le bloc d'origine non compressé.
Le premier 3 bits du bloc, c'est-à-dire les 3 bits les plus significatifs du premier octet, est l' étiquette de bloc . Actuellement, l'étiquette de bloc détermine le niveau de compression utilisé pour produire le bloc comprimé.
| Étiquette de blocage | Niveau de compression |
|---|---|
| 0 | Niveau 1 |
| 1 | Niveau 2 |
Le contenu du bloc variera en fonction du niveau de compression.
FastLZ Level 1 implémente l'algorithme de compression LZ77 avec une fenêtre coulissante de 8 kb et jusqu'à 264 octets de longueur de correspondance.
Le bloc comprimé se compose d'une ou plusieurs instructions . Chaque instruction commence par un OPCode OPCOT 1 octet, un opcode Opcode 2 octets ou 3 octets.
| Type d'instruction | OPCODE [0] | OPCODE [1] | OPCODE [2] |
|---|---|---|---|
| Course littérale | 000 , l₄-l₀ | - | - |
| Match court | M₂-m₀, r₁₂-r₈ | R₇-r₀ | - |
| Match long | 111 , R₁₂-R₈ | M₇-m₀ | R₇-r₀ |
Notez que la toute première instruction dans un bloc comprimé est toujours une course littérale.
Pour l'instruction de l'exécution littérale, il y a un ou plusieurs octets suivant le code. C'est ce qu'on appelle la course littérale.
Les 5 bits moins significatifs d' opcode[0] , L , détermine le nombre de littéraux suivant l'opcode. La valeur de 0 indique une course littérale de 1 octet, 1 indique une course littérale de 2 octets, etc. Le cycle littéral minimum est 1 et le cycle littéral maximum est de 32.
Le décompresseur copie ( L + 1 ) octets de course littérale, à partir du premier juste après Opcode.
Exemple : Si le bloc compressé est un tableau de 4 octets de [0x02, 0x41, 0x42, 0x43] , alors l'opcode est 0x02 et cela signifie un exécution littéral de 3 octets. Le décompresseur copiera ensuite les 3 octets suivants, [0x41, 0x42, 0x43] , dans le tampon de sortie. Le tampon de sortie représente désormais le bloc (original) non compressé, [0x41, 0x42, 0x43] .
Les 3 bits les plus significatifs d' opcode[0] , M , déterminent la longueur de correspondance . La valeur de 1 indique une correspondance de 3 octets, 2 indique une correspondance de 4 octets et ainsi de suite. La longueur de correspondance minimale est de 3 et la longueur maximale de correspondance est de 8.
Les 5 bits moins significatifs d' opcode[0] combinés avec les 8 bits de l' opcode[1] , R , détermine le décalage de référence . Étant donné que le décalage est codé en 13 bits, le minimum est 0 et le maximum est 8191.
Le code C suivant récupère la longueur de correspondance et le décalage de référence:
M = opcode [ 0 ] >> 5 ;
R = 256 * ( opcode [ 0 ] << 5 ) + opcode [ 1 ];Le décompresseur copie (m + 2) octets, à partir de l'emplacement compensé par R dans le tampon de sortie. Notez que R est une référence arrière , c'est-à-dire que la valeur de 0 correspond au dernier octet dans le tampon de sortie, 1 est le deuxième pour durer des octets, etc.
Exemple 1 : Si le bloc compressé est un tableau de 7 octets de [0x03, 0x41, 0x42, 0x43, 0x44, 0x20, 0x02] , alors il y a deux instructions dans le là. La première instruction est la série littérale de 4 octets (en raison de L = 3 ). Ainsi, le décompresseur copie 4 octets au tampon de sortie, résultant en [0x41, 0x42, 0x43, 0x44] . La deuxième instruction est la correspondance courte de 3 octets (de m = 1 , c'est-à-dire 0x20 >> 5 ) et le décalage de 2. Par conséquent, le compresseur remonte à 2 octets de la dernière position, copie 3 octets ( [0x42, 0x43, 0x44] ), et les considère au buffer de sortie. Le tampon de sortie représente désormais les données complètes non compressées, [0x41, 0x42, 0x43, 0x44, 0x42, 0x43, 0x44] .
Exemple 2 : Si le bloc compressé est un tableau de 4 octets de [0x00, 0x61, 0x40, 0x00] , il y a deux instructions là-dedans. La première instruction est la série littérale de seulement 1 octet ( l = 0 ). Ainsi, le décompresseur copie l'octet ( 0x61 ) au tampon de sortie. Le tampon de sortie devient désormais [0x61] . La deuxième instruction est la correspondance courte de 4 octets (de m = 2 , c'est-à-dire 0x40 >> 5 ) et le décalage de 0. Par conséquent, le décompresseur copie 4 octets commençant à utiliser la référence arrière de 0 (c'est-à-dire la position de 0x61 ). Le tampon de sortie représente désormais les données complètes non compressées, [0x61, 0x61, 0x61, 0x61, 0x61] .
La valeur d' opcode[1] , M , détermine la longueur de correspondance . La valeur de 0 indique une correspondance de 9 octets, 1 indique une correspondance de 10 octets et ainsi de suite. La longueur de correspondance minimale est de 9 et la longueur maximale de correspondance est de 264.
Les 5 bits moins significatifs d' opcode[0] combinés avec les 8 bits d' opcode[2] , R , détermine le décalage de référence . Étant donné que le décalage est codé en 13 bits, le minimum est 0 et le maximum est 8191.
Le code C suivant récupère la longueur de correspondance et le décalage de référence:
M = opcode [ 1 ];
R = 256 * ( opcode [ 0 ] << 5 ) + opcode [ 2 ];Le décompresseur copie (m + 9) octets, à partir de l'emplacement compensé par R dans le tampon de sortie. Notez que R est une référence arrière , c'est-à-dire que la valeur de 0 correspond au dernier octet dans le tampon de sortie, 1 est pour le second au dernier octet, etc.
Exemple : Si le bloc compressé est un tableau de 4 octets de [0x01, 0x44, 0x45, 0xE0, 0x01, 0x01] , il y a deux instructions là-dedans. La première instruction est la course littérale avec la longueur de 2 (en raison de L = 1 ). Ainsi, le décompresseur copie l'exécution littérale de 2 octets ( [0x44, 0x45] ) au tampon de sortie. La deuxième instruction est la longue correspondance avec la longueur de correspondance de 10 (à partir de m = 1 ) et le décalage de 1. Par conséquent, le décompresseur copie 10 octets commençant à utiliser la référence arrière de 1 (c'est-à-dire la position de 0x44 ). Le tampon de sortie représente désormais les données complètes non compressées, [0x44, 0x45, 0x44, 0x45, 0x44, 0x45, 0x44, 0x45, 0x44, 0x45, 0x44, 0x45] .
La fonction C suivante à 40 lignes implémente un décompresseur entièrement fonctionnel pour le format de bloc ci-dessus. Notez qu'il est destiné à être éducatif, par exemple, aucun contrôle lié n'est mis en œuvre, et donc il est absolument dangereux pour la production.
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 ;
}
}
}
}(À écrire)
