FastLZ
1.0.0
Fastlz (Lisensi MIT) adalah implementasi ANSI C/C90 dari Algoritma Lempel-ZIV 77 (LZ77) kompresi data lossless. Sangat cocok untuk mengompres serangkaian teks/paragraf, urutan data piksel mentah, atau blok data lainnya dengan banyak pengulangan. Ini tidak dimaksudkan untuk digunakan pada gambar, video, dan format data lain yang biasanya sudah dalam bentuk terkompresi optimal.
Fokus untuk Fastlz adalah kompresi dan dekompresi yang sangat cepat, melakukan itu dengan biaya rasio kompresi. Sebagai ilustrasi, perbandingan dengan zlib saat mengompresi enwik8 (juga lebih detail):
| Perbandingan | Kompresi | Dekompresi | |
|---|---|---|---|
| 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 digunakan oleh banyak produk perangkat lunak, dari sejumlah game (seperti Death Stranding) hingga berbagai proyek open-source (Godot Engine, Facebook HHVM, Apache Traffic Server, Calligra Office, OSV, Netty, dll). Bahkan berfungsi sebagai dasar untuk proyek kompresi lainnya seperti Blosc.
Untuk implementasi lain dari LZ77 yang selaras dengan byte, lihat LZ4, Snappy, Density, LZO, LZF, LZJB, LZRW, dll.
Fastlz dapat digunakan secara langsung di aplikasi C/C ++ apa pun. Untuk bahasa/lingkungan pemrograman lainnya, gunakan ikatan yang sesuai:
cargo install fastlzpip install fastlznpm install fastlzgem install fastlz Fastlz hanya terdiri dari dua file: fastlz.h dan fastlz.c . Cukup tambahkan file -file ini ke proyek Anda untuk menggunakan Fastlz. Untuk informasi terperinci tentang API untuk melakukan kompresi dan dekompresi, lihat fastlz.h .
Untuk pengguna VCPKG, Fastlz sudah tersedia: vcpkg install fastlz .
Kompresor file sederhana yang disebut 6pack disertakan sebagai contoh tentang cara menggunakan fastlz. Dekompresor yang sesuai adalah 6unpack .
Fastlz mendukung kompiler ANSI C/C90 yang sesuai dengan standar, termasuk yang populer seperti GCC, dentang, Visual Studio, dan bahkan CC kecil. Fastlz bekerja dengan baik pada sejumlah arsitektur (32-bit dan 64-bit, endian besar dan endian kecil), dari Intel/AMD, PowerPC, System Z, ARM, MIPS, dan RISC-V.
Sistem integrasi kontinu menjalankan serangkaian perjalanan putaran kompresi-dekompresi yang luas pada sistem berikut:
Untuk detail lebih lanjut, periksa Log Bangun Tindakan GitHub yang sesuai.
| AMD64 | Linux | Windows | MacOS |
| GCC | |||
| Dentang | |||
| Tinycc | |||
| Vs 2019 | |||
| I686 | Linux | Windows | MacOS |
| GCC | |||
| Dentang | |||
| 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 |
Mari kita asumsikan bahwa Fastlz mengompres array byte, yang disebut blok yang tidak terkompresi , ke dalam array byte lain, yang disebut blok terkompresi . Untuk memahami apa yang akan disimpan di blok terkompresi, ini adalah ilustratif untuk menunjukkan bagaimana Fastlz akan mendekompresi blok untuk mengambil blok asli yang tidak terkompresi.
3-bit pertama dari blok, yaitu 3 bit yang paling signifikan dari byte pertama, adalah tag blok . Saat ini tag blok menentukan tingkat kompresi yang digunakan untuk menghasilkan blok terkompresi.
| Tag blok | Tingkat kompresi |
|---|---|
| 0 | Level 1 |
| 1 | Level 2 |
Konten blok akan bervariasi tergantung pada tingkat kompresi.
Fastlz Level 1 mengimplementasikan algoritma kompresi LZ77 dengan jendela geser 8 kb dan hingga 264 byte dengan panjang pertandingan.
Blok terkompresi terdiri dari satu atau lebih instruksi . Setiap instruksi dimulai dengan opcode 1-byte, 2-byte opcode, atau 3-byte opcode.
| Jenis instruksi | Opcode [0] | Opcode [1] | Opcode [2] |
|---|---|---|---|
| Lari literal | 000 , l₄-l₀ | - | - |
| Pertandingan singkat | M₂-M₀, R₁₂-R₈ | R₇-r₀ | - |
| Pertandingan panjang | 111 , r₁₂-r₈ | M₇-m₀ | R₇-r₀ |
Perhatikan bahwa instruksi pertama dalam blok terkompresi selalu merupakan menjalankan literal.
Untuk instruksi yang dijalankan secara literal, ada satu atau lebih byte mengikuti kode. Ini disebut literal run.
5 bit opcode[0] , L , menentukan jumlah literal yang mengikuti opcode. Nilai 0 menunjukkan menjalankan literal 1-byte, 1 menunjukkan menjalankan literal 2-byte, dan sebagainya. Jalan literal minimum adalah 1 dan menjalankan literal maksimum adalah 32.
Salinan dekompresor ( L + 1 ) byte literal run, mulai dari yang pertama tepat setelah opcode.
Contoh : Jika blok terkompresi adalah array 4-byte [0x02, 0x41, 0x42, 0x43] , maka opcode adalah 0x02 dan itu berarti menjalankan literal 3 byte. Dekompresor kemudian akan menyalin 3 byte berikutnya, [0x41, 0x42, 0x43] , ke buffer output. Buffer output sekarang mewakili blok (asli) yang tidak terkompresi, [0x41, 0x42, 0x43] .
3 bit opcode[0] , m , menentukan panjang pertandingan . Nilai 1 menunjukkan kecocokan 3-byte, 2 menunjukkan kecocokan 4-byte dan seterusnya. Panjang pertandingan minimum adalah 3 dan panjang pertandingan maksimum adalah 8.
5 bit opcode[0] dikombinasikan dengan 8 bit opcode[1] , R , menentukan offset referensi . Karena offset dikodekan dalam 13 bit, minimum adalah 0 dan maksimum adalah 8191.
Kode C berikut mengambil panjang pertandingan dan offset referensi:
M = opcode [ 0 ] >> 5 ;
R = 256 * ( opcode [ 0 ] << 5 ) + opcode [ 1 ];Byte Decompresres Salinan (M+2) , mulai dari lokasi yang diimbangi oleh R dalam buffer output. Perhatikan bahwa R adalah referensi kembali , yaitu nilai 0 sesuai dengan byte terakhir dalam buffer output, 1 adalah byte kedua dari terakhir, dan sebagainya.
Contoh 1 : Jika blok terkompresi adalah array 7-byte [0x03, 0x41, 0x42, 0x43, 0x44, 0x20, 0x02] , maka ada dua instruksi di sana. Instruksi pertama adalah menjalankan literal 4 byte (karena L = 3 ). Dengan demikian, dekompresor menyalin 4 byte ke buffer output, menghasilkan [0x41, 0x42, 0x43, 0x44] . Instruksi kedua adalah kecocokan pendek dari 3 byte (dari M = 1 , yaitu 0x20 >> 5 ) dan offset 2. Oleh karena itu, kompresor kembali 2 byte dari posisi terakhir, menyalin 3 byte ( [0x42, 0x43, 0x44] ), dan menambahkannya ke buffer output. Buffer output sekarang mewakili data yang tidak terkompresi lengkap, [0x41, 0x42, 0x43, 0x44, 0x42, 0x43, 0x44] .
Contoh 2 : Jika blok terkompresi adalah array 4-byte [0x00, 0x61, 0x40, 0x00] , maka ada dua instruksi di sana. Instruksi pertama adalah menjalankan literal hanya 1 byte ( l = 0 ). Dengan demikian, dekompresor menyalin byte ( 0x61 ) ke buffer output. Buffer output sekarang menjadi [0x61] . Instruksi kedua adalah kecocokan pendek dari 4 byte (dari M = 2 , yaitu 0x40 >> 5 ) dan offset 0. Oleh karena itu, dekompresor salinan 4 byte mulai menggunakan referensi belakang 0 (yaitu posisi 0x61 ). Buffer output sekarang mewakili data yang tidak terkompresi lengkap, [0x61, 0x61, 0x61, 0x61, 0x61] .
Nilai opcode[1] , m , menentukan panjang pertandingan . Nilai 0 menunjukkan kecocokan 9-byte, 1 menunjukkan kecocokan 10-byte dan seterusnya. Panjang pertandingan minimum adalah 9 dan panjang pertandingan maksimum adalah 264.
5 bit opcode[0] dikombinasikan dengan 8 bit opcode[2] , R , menentukan offset referensi . Karena offset dikodekan dalam 13 bit, minimum adalah 0 dan maksimum adalah 8191.
Kode C berikut mengambil panjang pertandingan dan offset referensi:
M = opcode [ 1 ];
R = 256 * ( opcode [ 0 ] << 5 ) + opcode [ 2 ];Byte Decompresres Salinan (M+9) , mulai dari lokasi yang diimbangi oleh R dalam buffer output. Perhatikan bahwa R adalah referensi kembali , yaitu nilai 0 sesuai dengan byte terakhir dalam buffer output, 1 adalah untuk byte kedua ke terakhir, dan sebagainya.
Contoh : Jika blok terkompresi adalah array 4-byte [0x01, 0x44, 0x45, 0xE0, 0x01, 0x01] , maka ada dua instruksi di sana. Instruksi pertama adalah menjalankan literal dengan panjang 2 (karena L = 1 ). Dengan demikian, dekompresor menyalin run literal 2-byte ( [0x44, 0x45] ) ke buffer output. Instruksi kedua adalah pertandingan panjang dengan panjang pertandingan 10 (dari M = 1 ) dan offset 1. Oleh karena itu, dekompresor menyalin 10 byte mulai menggunakan referensi belakang 1 (yaitu posisi 0x44 ). Buffer output sekarang mewakili data yang tidak terkompresi lengkap, [0x44, 0x45, 0x44, 0x45, 0x44, 0x45, 0x44, 0x45, 0x44, 0x45, 0x44, 0x45] .
Fungsi C 40-line berikut mengimplementasikan dekompresor fungsional sepenuhnya untuk format blok di atas. Perhatikan bahwa ini dimaksudkan untuk dididik, misalnya tidak ada cek yang diimplementasikan, dan oleh karena itu benar -benar tidak aman untuk diproduksi.
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 ;
}
}
}
}(Ditulis)
