FastLZ
1.0.0
O FASTLZ (MIT Licença) é uma implementação ANSI C/C90 do algoritmo Lempel-Ziv 77 (LZ77) de compressão de dados sem perdas. É adequado comprimir uma série de texto/parágrafos, sequências de dados brutos de pixels ou quaisquer outros blocos de dados com muita repetição. Não se destina a ser usado em imagens, vídeos e outros formatos de dados normalmente já de forma compactada ideal.
O foco para o Fastlz é uma compressão e descompressão muito rápidas, fazendo isso ao custo da taxa de compressão. Como ilustração, a comparação com o Zlib ao comprimir Enwik8 (também em mais detalhes):
| Razão | Compressão | Descompressão | |
|---|---|---|---|
| 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. |
O Fastlz é usado por muitos produtos de software, desde vários jogos (como Death Stranding) a vários projetos de código aberto (GODOT Engine, Facebook HHVM, Apache Traffic Server, Calligra Office, OSV, Netty, etc.). Até serve como base para outros projetos de compressão como o BLOSC.
Para outras implementações do LZ77 alinhado a byte, dê uma olhada no LZ4, Snappy, Density, LZO, LZF, LZJB, LZRW, etc.
O FASTLZ pode ser usado diretamente em qualquer aplicativo C/C ++. Para outras linguagens/ambientes de programação, use a ligação correspondente:
cargo install fastlzpip install fastlznpm install fastlzgem install fastlz O Fastlz consiste em apenas dois arquivos: fastlz.h e fastlz.c . Basta adicionar esses arquivos ao seu projeto para usar o Fastlz. Para obter informações detalhadas sobre a API para executar compressão e descompressão, consulte fastlz.h .
Para usuários do VCPKG, o Fastlz já está disponível: vcpkg install fastlz .
Um compressor de arquivo simples chamado 6pack está incluído como um exemplo sobre como usar o Fastlz. O descompressor correspondente é 6unpack .
A Fastlz suporta qualquer compilador ANSI C/C90 de conformidade padrão, incluindo os populares como GCC, CLANG, Visual Studio e até Tiny CC. O Fastlz funciona bem em várias arquiteturas (32 bits e 64 bits, Big Endian e Little Endian), da Intel/AMD, PowerPC, System Z, Arm, MIPS e RISC-V.
O sistema de integração contínuo executa um extenso conjunto de viagens redondas de compressão-decompressão nos seguintes sistemas:
Para obter mais detalhes, verifique as ações do GitHub correspondentes criam logs.
| AMD64 | Linux | Windows | macos |
| GCC | |||
| Clang | |||
| Tinycc | |||
| VS 2019 | |||
| I686 | Linux | Windows | macos |
| GCC | |||
| Clang | |||
| 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 |
Vamos supor que o Fastlz comprime uma matriz de bytes, chamada de bloco não compactado , em outra matriz de bytes, chamada de bloco compactado . Para entender o que será armazenado no bloco compactado, é ilustrativo demonstrar como o Fastlz descompactará o bloco para recuperar o bloco não compactado original.
Os primeiros 3 bits do bloco, ou seja, os 3 bits mais significativos do primeiro byte, é a etiqueta do bloco . Atualmente, a tag de bloco determina o nível de compressão usado para produzir o bloco compactado.
| Tag Block | Nível de compressão |
|---|---|
| 0 | Nível 1 |
| 1 | Nível 2 |
O conteúdo do bloco varia dependendo do nível de compressão.
O Fastlz Nível 1 implementa o algoritmo de compressão LZ77 com janela deslizante de 8 kb e até 264 bytes de comprimento da partida.
O bloco compactado consiste em uma ou mais instruções . Cada instrução começa com um código de operação de 1 bytes, código de opções de 2 bytes ou código de opções de 3 bytes.
| Tipo de instrução | OpCode [0] | OpCode [1] | OpCode [2] |
|---|---|---|---|
| Corrida literal | 000 , l₄-l₀ | - | - |
| Corta curta | M₂-m₀, r₁₂-r₈ | R₇-r₀ | - |
| Longa partida | 111 , r₁₂-r₈ | M₇-m₀ | R₇-r₀ |
Observe que a primeira instrução em um bloco compactado é sempre uma corrida literal.
Para a instrução literal de execução, há um ou mais bytes seguindo o código. Isso é chamado de corrida literal.
Os 5 bits menos significativos do opcode[0] , L , determina o número de literais seguindo o código de opção. O valor 0 indica uma corrida literal de 1 byte, 1 indica uma corrida literal de 2 bytes e assim por diante. A corrida literal mínima é 1 e a execução literal máxima é 32.
O descompressor cópia ( L + 1 ) bytes de corrida literal, a partir do primeiro logo após o código de opções.
Exemplo : se o bloco compactado for uma matriz de 4 bytes de [0x02, 0x41, 0x42, 0x43] , o código OPCOD é 0x02 e isso significa uma execução literal de 3 bytes. O descompressor copiará os 3 bytes subsequentes, [0x41, 0x42, 0x43] , para o buffer de saída. O buffer de saída agora representa o bloco não compactado (original), [0x41, 0x42, 0x43] .
Os 3 bits mais significativos do opcode[0] , M , determina o comprimento da correspondência . O valor de 1 indica uma partida de 3 bytes, 2 indica uma partida de 4 bytes e assim por diante. O comprimento mínimo da correspondência é 3 e o comprimento máximo da correspondência é 8.
Os 5 bits menos significativos do opcode[0] combinados com os 8 bits do opcode[1] , R , determinam o deslocamento de referência . Como o deslocamento é codificado em 13 bits, o mínimo é 0 e o máximo é 8191.
O código C a seguir recupera o comprimento da correspondência e o deslocamento de referência:
M = opcode [ 0 ] >> 5 ;
R = 256 * ( opcode [ 0 ] << 5 ) + opcode [ 1 ];O descompressor cópia (M+2) bytes, começando pelo local compensado por r no buffer de saída. Observe que R é uma referência traseira , ou seja, o valor de 0 corresponde ao último byte no buffer de saída, 1 é o segundo a último byte e assim por diante.
Exemplo 1 : Se o bloco compactado for uma matriz de 7 bytes de [0x03, 0x41, 0x42, 0x43, 0x44, 0x20, 0x02] , há duas instruções no local. A primeira instrução é a corrida literal de 4 bytes (devido a L = 3 ). Assim, o descompressor copia 4 bytes para o buffer de saída, resultando em [0x41, 0x42, 0x43, 0x44] . A segunda instrução é a correspondência curta de 3 bytes (de M = 1 , ou seja, 0x20 >> 5 ) e o deslocamento de 2. Portanto, o compressor remonta a 2 bytes da última posição, copia 3 bytes ( [0x42, 0x43, 0x44] ) e os anexam ao buffer de saída. O buffer de saída agora representa os dados completos não confirmados, [0x41, 0x42, 0x43, 0x44, 0x42, 0x43, 0x44] .
Exemplo 2 : Se o bloco compactado for uma matriz de 4 bytes de [0x00, 0x61, 0x40, 0x00] , há duas instruções lá. A primeira instrução é a corrida literal de apenas 1 byte ( L = 0 ). Assim, o descompressor copia o byte ( 0x61 ) para o buffer de saída. O buffer de saída agora se torna [0x61] . A segunda instrução é a correspondência curta de 4 bytes (de M = 2 , ou seja, 0x40 >> 5 ) e o deslocamento de 0. Portanto, o descompressor copia 4 bytes começando usando a referência traseira de 0 (ou seja, a posição de 0x61 ). O buffer de saída agora representa os dados completos não confirmados, [0x61, 0x61, 0x61, 0x61, 0x61] .
O valor do opcode[1] , M , determina o comprimento da correspondência . O valor 0 indica uma partida de 9 bytes, 1 indica uma partida de 10 bytes e assim por diante. O comprimento mínimo da correspondência é 9 e o comprimento máximo da correspondência é 264.
Os 5 bits menos significativos do opcode[0] combinados com os 8 bits de opcode[2] , R , determinam o deslocamento de referência . Como o deslocamento é codificado em 13 bits, o mínimo é 0 e o máximo é 8191.
O código C a seguir recupera o comprimento da correspondência e o deslocamento de referência:
M = opcode [ 1 ];
R = 256 * ( opcode [ 0 ] << 5 ) + opcode [ 2 ];Os bytes descompressores (M+9) , a partir do local, compensado por R no buffer de saída. Observe que R é uma referência traseira , ou seja, o valor de 0 corresponde ao último byte no buffer de saída, 1 é para o segundo a último byte e assim por diante.
Exemplo : se o bloco compactado for uma matriz de 4 bytes de [0x01, 0x44, 0x45, 0xE0, 0x01, 0x01] , há duas instruções lá. A primeira instrução é a corrida literal com o comprimento de 2 (devido a L = 1 ). Assim, o descompressor copia a execução literal de 2 bytes ( [0x44, 0x45] ) para o buffer de saída. A segunda instrução é a longa correspondência com o comprimento da correspondência de 10 (de M = 1 ) e o deslocamento de 1. Portanto, o descompressor copia 10 bytes começando usando a referência traseira de 1 (ou seja, a posição de 0x44 ). O buffer de saída agora representa os dados completos não compactados, [0x44, 0x45, 0x44, 0x45, 0x44, 0x45, 0x44, 0x45, 0x44, 0x45, 0x44, 0x45] .
A função C de 40 linhas a seguir implementa um descompressor totalmente funcional para o formato do bloco acima. Observe que se destina a ser educacional, por exemplo, nenhum cheque encadernado é implementado e, portanto, é absolutamente inseguro para a produção.
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 ;
}
}
}
}(A ser escrito)
