FastLZ
1.0.0
Fastlz (ใบอนุญาต MIT) เป็นการใช้งาน ANSI C/C90 ของอัลกอริทึม LEMPEL-ZIV 77 (LZ77) ของการบีบอัดข้อมูลที่ไม่สูญเสีย มันเหมาะที่จะบีบอัดซีรีส์ของข้อความ/ย่อหน้าลำดับของข้อมูลพิกเซลดิบหรือบล็อกข้อมูลอื่น ๆ ที่มีการทำซ้ำจำนวนมาก มันไม่ได้มีวัตถุประสงค์เพื่อใช้กับรูปภาพวิดีโอและรูปแบบอื่น ๆ ของข้อมูลโดยทั่วไปแล้วในรูปแบบบีบอัดที่ดีที่สุด
การมุ่งเน้นสำหรับ Fastlz เป็นการบีบอัดและการบีบอัดที่รวดเร็วมากโดยทำเช่นนั้นในราคาของอัตราส่วนการบีบอัด เป็นภาพประกอบการเปรียบเทียบกับ zlib เมื่อบีบอัด Enwik8 (ในรายละเอียดเพิ่มเติม):
| อัตราส่วน | การบีบอัด | การบีบอัด | |
|---|---|---|---|
| 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 ถูกใช้โดยผลิตภัณฑ์ซอฟต์แวร์จำนวนมากตั้งแต่เกมจำนวนมาก (เช่น Death Stranding) ไปจนถึงโครงการโอเพนซอร์ซที่หลากหลาย (Godot Engine, Facebook HHVM, Apache Traffic Server, Calligra Office, OSV, Netty, ฯลฯ ) มันยังทำหน้าที่เป็นพื้นฐานสำหรับโครงการบีบอัดอื่น ๆ เช่น Blosc
สำหรับการใช้งานอื่น ๆ ของ LZ77 ที่สอดคล้องกันของไบต์ลองดูที่ LZ4, เร็ว, ความหนาแน่น, LZO, LZF, 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 และแม้แต่ CC ขนาดเล็ก Fastlz ทำงานได้ดีกับสถาปัตยกรรมจำนวนมาก (32 บิตและ 64- บิต, Endian ขนาดใหญ่และ Little Endian) จาก Intel/AMD, PowerPC, System Z, ARM, MIPS และ RISC-V
ระบบการรวมอย่างต่อเนื่องเรียกใช้ชุดการเดินทางรอบการบีบอัดการบีบอัดรอบ ๆ ระบบต่อไปนี้:
สำหรับรายละเอียดเพิ่มเติมให้ตรวจสอบการกระทำของ GitHub ที่เกี่ยวข้อง
| AMD64 | ลินเวกซ์ | หน้าต่าง | แม็กอส |
| GCC | |||
| เสียงดัง | |||
| TinyCC | |||
| VS 2019 | |||
| i686 | ลินเวกซ์ | หน้าต่าง | แม็กอส |
| GCC | |||
| เสียงดัง | |||
| TinyCC | |||
| VS 2019 | |||
| i586 | ลินเวกซ์ | ดอส | |
| GCC | |||
| ลินเวกซ์ | |||
| PowerPC | |||
| GCC | |||
| PPC64 (LE) | |||
| GCC | |||
| GCC | |||
| S390X | |||
| GCC | |||
| armhf | |||
| GCC | |||
| ARM64 | |||
| GCC | |||
| MIPS (EL) | |||
| GCC | |||
| GCC | |||
| MIPS64 (EL) | |||
| GCC | |||
| GCC | |||
| RISCV | |||
| GCC | |||
| RISCV64 | |||
| GCC |
ให้เราสมมติว่า Fastlz บีบอัดอาร์เรย์ของไบต์เรียกว่า บล็อกที่ไม่บีบอัด ลงในอาร์เรย์อื่นของไบต์เรียกว่า บล็อกบีบอัด เพื่อให้เข้าใจถึงสิ่งที่จะเก็บไว้ในบล็อกบีบอัดมันเป็นตัวอย่างที่จะแสดงให้เห็นว่า Fastlz จะ บีบอัด บล็อกเพื่อดึงบล็อกที่ไม่มีการบีบอัดดั้งเดิมอย่างไร
3 บิตแรกของบล็อกคือ 3 บิตที่สำคัญที่สุดของไบต์แรกคือ แท็กบล็อก ปัจจุบันแท็กบล็อกกำหนดระดับการบีบอัดที่ใช้ในการสร้างบล็อกบีบอัด
| บล็อกแท็ก | ระดับการบีบอัด |
|---|---|
| 0 | ระดับ 1 |
| 1 | ระดับ 2 |
เนื้อหาของบล็อกจะแตกต่างกันไปขึ้นอยู่กับระดับการบีบอัด
Fastlz ระดับ 1 ใช้อัลกอริทึมการบีบอัด LZ77 พร้อมหน้าต่างเลื่อน 8 kb และความยาวการจับคู่สูงถึง 264 ไบต์
บล็อกบีบอัดประกอบด้วย คำแนะนำ อย่างน้อยหนึ่งคำ แต่ละคำสั่งเริ่มต้นด้วย opcode 1 ไบต์, opcode 2-byte หรือ opcode 3 ไบต์
| ประเภทคำสั่ง | Opcode [0] | Opcode [1] | Opcode [2] |
|---|---|---|---|
| วิ่งตามตัวอักษร | 000 , l₄-l₀ | - | - |
| การแข่งขันสั้น | m₂-m₀, r₁₂-r₈ | r₇-r₀ | - |
| การแข่งขันที่ยาวนาน | 111 , r₁₂-r₈ | m₇-m₀ | r₇-r₀ |
โปรดทราบว่าคำสั่ง แรก ในบล็อกบีบอัดนั้นเป็นการดำเนินการตามตัวอักษรเสมอ
สำหรับคำแนะนำการรันที่แท้จริงมีหนึ่งไบต์ขึ้นไปตามรหัส สิ่งนี้เรียกว่าการวิ่งตามตัวอักษร
5 บิตที่สำคัญน้อยที่สุดของ opcode[0] , l , กำหนด จำนวนตัวอักษร ตาม opcode ค่า 0 หมายถึงการรันตัวอักษร 1 ไบต์ 1 หมายถึงการวิ่งตามตัวอักษร 2 ไบต์และอื่น ๆ การวิ่งตามตัวอักษรขั้นต่ำคือ 1 และการวิ่งตามตัวอักษรสูงสุดคือ 32
สำเนา decompressor ( l + 1 ) ไบต์ของการรันตัวอักษรเริ่มต้นจากอันแรกทันทีหลังจาก opcode
ตัวอย่าง : หากบล็อกบีบอัดเป็นอาร์เรย์ 4-byte ของ [0x02, 0x41, 0x42, 0x43] ดังนั้น opcode คือ 0x02 และนั่นหมายถึงการวิ่งตามตัวอักษร 3 ไบต์ จากนั้น decompressor จะคัดลอก 3 bytes ที่ตามมา, [0x41, 0x42, 0x43] ไปยังบัฟเฟอร์เอาต์พุต บัฟเฟอร์เอาต์พุตตอนนี้แสดงถึงบล็อกที่ไม่บีบอัด (ต้นฉบับ) [0x41, 0x42, 0x43]
3 บิตที่สำคัญที่สุดของ opcode[0] , m , กำหนด ความยาวการจับคู่ ค่า 1 หมายถึงการจับคู่ 3 ไบต์ 2 หมายถึงการจับคู่ 4 ไบต์และอื่น ๆ ความยาวการจับคู่ขั้นต่ำคือ 3 และความยาวการจับคู่สูงสุดคือ 8
5 บิตที่สำคัญน้อยที่สุดของ opcode[0] รวมกับ 8 บิตของ opcode[1] , r , กำหนด ค่าชดเชยการอ้างอิง เนื่องจากการชดเชยถูกเข้ารหัสใน 13 บิตขั้นต่ำคือ 0 และสูงสุดคือ 8191
รหัส C ต่อไปนี้จะดึงความยาวการจับคู่และชดเชยการอ้างอิง:
M = opcode [ 0 ] >> 5 ;
R = 256 * ( opcode [ 0 ] << 5 ) + opcode [ 1 ];สำเนา decompressor (M+2) ไบต์เริ่มต้นจากตำแหน่งที่ชดเชยโดย R ในบัฟเฟอร์เอาต์พุต โปรดทราบว่า R เป็น ข้อมูลอ้างอิงด้านหลัง เช่นค่า 0 สอดคล้องกับไบต์สุดท้ายในบัฟเฟอร์เอาต์พุต 1 คือไบต์ที่สองถึงสุดท้ายและอื่น ๆ
ตัวอย่างที่ 1 : หากบล็อกบีบอัดเป็นอาร์เรย์ 7 ไบต์ของ [0x03, 0x41, 0x42, 0x43, 0x44, 0x20, 0x02] ดังนั้นมีสองคำแนะนำในนั้น คำสั่งแรกคือการวิ่งตามตัวอักษร 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 : หากบล็อกบีบอัดเป็นอาร์เรย์ 4 ไบต์ของ [0x00, 0x61, 0x40, 0x00] ดังนั้นมีสองคำแนะนำในนั้น คำสั่งแรกคือการดำเนินการตามตัวอักษรเพียง 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
5 บิตที่สำคัญน้อยที่สุดของ opcode[0] รวมกับ opcode[2] , R , กำหนดค่า การชดเชยการอ้างอิง เนื่องจากการชดเชยถูกเข้ารหัสใน 13 บิตขั้นต่ำคือ 0 และสูงสุดคือ 8191
รหัส C ต่อไปนี้จะดึงความยาวการจับคู่และชดเชยการอ้างอิง:
M = opcode [ 1 ];
R = 256 * ( opcode [ 0 ] << 5 ) + opcode [ 2 ];สำเนา decompressor (M+9) ไบต์เริ่มต้นจากตำแหน่งที่ชดเชยโดย R ในบัฟเฟอร์เอาต์พุต โปรดทราบว่า R เป็น ข้อมูลอ้างอิงด้านหลัง เช่นค่า 0 สอดคล้องกับไบต์สุดท้ายในบัฟเฟอร์เอาต์พุต 1 คือครั้งที่สองถึงไบต์สุดท้ายและอื่น ๆ
ตัวอย่าง : หากบล็อกบีบอัดเป็นอาร์เรย์ 4-byte ของ [0x01, 0x44, 0x45, 0xE0, 0x01, 0x01] ดังนั้นมีสองคำแนะนำในนั้น คำสั่งแรกคือการดำเนินการตามตัวอักษรที่มีความยาว 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 บรรทัดต่อไปนี้ใช้ตัวบีบอัดแบบสมบูรณ์แบบสำหรับรูปแบบบล็อกด้านบน โปรดทราบว่ามีจุดประสงค์เพื่อการศึกษาเช่นไม่มีการตรวจสอบที่มีขอบเขตและดังนั้นจึง ไม่ปลอดภัย สำหรับการผลิต
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 ;
}
}
}
}(จะเขียน)
