FastLZ
1.0.0
FASTLZ (MIT 라이센스)는 무손실 데이터 압축의 LEMPEL-ZIV 77 알고리즘 (LZ77)의 ANSI C/C90 구현입니다. 일련의 텍스트/단락, 원시 픽셀 데이터 시퀀스 또는 많은 반복으로 다른 데이터 블록을 압축하는 것이 적합합니다. 이미지, 비디오 및 기타 형식의 데이터를 일반적으로 이미 최적의 압축 형식으로 사용하는 것이 아닙니다.
Fastlz의 초점은 압축 비율의 비용으로 매우 빠른 압축 및 감압입니다. 예를 들어, enwik8을 압축 할 때 Zlib과의 비교 (자세한 내용) : 자세한 내용은 다음과 같습니다.
| 비율 | 압축 | 감압 | |
|---|---|---|---|
| Fastlz | 54.2% | 159MB/s | 305MB/s |
| Zlib -1 | 42.3% | 50MB/s | 184MB/s |
| Zlib -9 | 36.5% | 11 MB/s | 185MB/s |
Fastlz는 여러 게임 (예 : 데스 스트랜드)에서 다양한 오픈 소스 프로젝트 (Godot Engine, Facebook HHVM, Apache Traffic Server, Calligra Office, OSV, Netty 등)에 이르기까지 많은 소프트웨어 제품에서 사용됩니다. 또한 BLOSC와 같은 다른 압축 프로젝트의 기초 역할을합니다.
바이트 정렬 LZ77의 다른 구현의 경우 LZ4, Snappy, Density, 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는 GCC, Clang, Visual Studio 및 Tiny CC와 같은 인기있는 컴파일러를 포함하여 표준 정보 ANSI C/C90 컴파일러를 지원합니다. Fastlz는 Intel/AMD, PowerPC, System Z, Arm, MIPS 및 RISC-V의 여러 아키텍처 (32 비트 및 64 비트, Big Endian 및 Little Endian)에서 잘 작동합니다.
연속 통합 시스템은 다음 시스템에서 광범위한 압축 탈환 라운드 트립을 실행합니다.
자세한 내용은 해당 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가 압축되지 않은 블록 이라고하는 바이트 배열을 압축 블록 이라고 불리는 다른 바이트 배열로 압축한다고 가정 해 봅시다. 압축 블록에 저장 될 내용을 이해하기 위해, 원래의 압축되지 않은 블록을 검색하기 위해 블록을 압축하는 방법을 보여주는 것이 예시되어 있습니다.
블록의 첫 3 비트, 즉 첫 번째 바이트의 가장 중요하지 않은 비트는 블록 태그 입니다. 현재 블록 태그는 압축 블록을 생성하는 데 사용되는 압축 수준을 결정합니다.
| 블록 태그 | 압축 수준 |
|---|---|
| 0 | 레벨 1 |
| 1 | 레벨 2 |
블록의 내용은 압축 수준에 따라 다릅니다.
Fastlz Level 1은 8kb 슬라이딩 창과 최대 264 바이트의 일치 길이로 LZ77 압축 알고리즘을 구현합니다.
압축 블록은 하나 이상의 지침 으로 구성됩니다. 각 명령어는 1 바이트 오크 코드, 2 바이트 오크 코드 또는 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입니다.
압축 압력기는 Opcode 직후 첫 번째부터 시작하여 리터럴 런의 바이트 ( L + 1 ) 바이트를 복사합니다.
예 : 압축 블록이 [0x02, 0x41, 0x42, 0x43] 의 4 바이트 배열 인 경우 Opcode는 0x02 이고 이는 3 바이트의 리터럴 실행을 의미합니다. 그런 다음 감압제는 후속 3 바이트 인 [0x41, 0x42, 0x43] 을 출력 버퍼에 복사합니다. 출력 버퍼는 이제 (원래) 비 압축 블록, [0x41, 0x42, 0x43] 나타냅니다.
가장 중요하지 않은 opcode[0] , m 은 일치 길이를 결정합니다. 1의 값은 3 바이트 일치, 2는 4 바이트 일치 등을 나타냅니다. 최소 일치 길이는 3이고 최대 일치 길이는 8입니다.
8 비트의 opcode[1] , r 과 결합 된 5 가지 opcode[0] 가 참조 오프셋을 결정합니다. 오프셋은 13 비트로 인코딩되므로 최소값은 0이고 최대 값은 8191입니다.
다음 C 코드는 일치 길이와 참조 오프셋을 검색합니다.
M = opcode [ 0 ] >> 5 ;
R = 256 * ( opcode [ 0 ] << 5 ) + opcode [ 1 ];출력 버퍼에서 R 에 의해 오프셋 된 위치에서 시작하여 감압제 복사 (M+2) 바이트. 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의 오프셋입니다. 따라서, 감압제는 0의 후면 참조를 사용하여 시작하는 4 바이트를 복사합니다 (예 : 0x61 의 위치). 출력 버퍼는 이제 완전한 압축되지 않은 데이터 인 [0x61, 0x61, 0x61, 0x61, 0x61] 을 나타냅니다.
opcode[1] , m 의 값은 일치 길이를 결정합니다. 0의 값은 9 바이트 일치, 1은 10 바이트 일치 등을 나타냅니다. 최소 일치 길이는 9이고 최대 일치 길이는 264입니다.
8 비트의 opcode[2] , r 과 결합 된 5 가지 opcode[0] 가 참조 오프셋을 결정합니다. 오프셋은 13 비트로 인코딩되므로 최소값은 0이고 최대 값은 8191입니다.
다음 C 코드는 일치 길이와 참조 오프셋을 검색합니다.
M = opcode [ 1 ];
R = 256 * ( opcode [ 0 ] << 5 ) + opcode [ 2 ];출력 버퍼에서 R 에 의해 오프셋 된 위치에서 시작하여 감압제 카피 (M+9) 바이트. R 은 백 참조 이며, 즉 0의 값은 출력 버퍼의 마지막 바이트에 해당하고, 1은 두 번째 ~ 마지막 바이트 등에 해당합니다.
예 : 압축 블록이 [0x01, 0x44, 0x45, 0xE0, 0x01, 0x01] 의 4 바이트 배열 인 경우 두 가지 지침이 있습니다. 첫 번째 명령은 길이가 2 인 리터럴 런 ( l = 1 )입니다. 따라서, 감압제는 2 바이트 리터럴 런 ( [0x44, 0x45] )를 출력 버퍼에 복사한다. 두 번째 명령어는 10의 일치 길이 ( m = 1 에서)와 1의 오프셋과의 긴 일치입니다. 따라서 감압제는 1의 후면 참조 (즉, 0x44 의 위치)를 사용하여 10 바이트를 복사합니다. 출력 버퍼는 이제 완전한 압축되지 않은 데이터 인 [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 ;
}
}
}
}(쓰기)
