FastLZ
1.0.0
FastLZ (Licencia MIT) es una implementación ANSI C/C90 del algoritmo Lempel-Ziv 77 (LZ77) de la compresión de datos sin pérdidas. Es adecuado para comprimir la serie de texto/párrafos, secuencias de datos de píxeles sin procesar o cualquier otro bloque de datos con mucha repetición. No está destinado a usarse en imágenes, videos y otros formatos de datos generalmente ya en una forma comprimida óptima.
El enfoque para FastLZ es una compresión y descompresión muy rápida, lo que lo hace a costa de la relación de compresión. Como ilustración, la comparación con ZLIB al comprimir ENWIK8 (también en más detalles):
| Relación | Compresión | Descompresión | |
|---|---|---|---|
| Rápido | 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 es utilizado por muchos productos de software, desde varios juegos (como la cadena de la muerte) hasta varios proyectos de código abierto (Godot Engine, Facebook HHVM, Apache Traffic Server, Calligra Office, OSV, Netty, etc.). Incluso sirve como base para otros proyectos de compresión como Blosc.
Para otras implementaciones de LZ77 alineados con bytes, eche un vistazo a LZ4, Snappy, Densidad, LZO, LZF, LZJB, LZRW, etc.
FastLZ se puede usar directamente en cualquier aplicación C/C ++. Para otros lenguajes/entornos de programación, use el enlace correspondiente:
cargo install fastlzpip install fastlznpm install fastlzgem install fastlz Fastlz consta de solo dos archivos: fastlz.h y fastlz.c . Simplemente agregue estos archivos a su proyecto para usar FastLZ. Para la información detallada sobre la API para realizar compresión y descompresión, consulte fastlz.h .
Para los usuarios de VCPKG, FastLZ ya está disponible: vcpkg install fastlz .
Un compresor de archivo simple llamado 6pack se incluye como ejemplo sobre cómo usar FastLZ. El descompresor correspondiente es 6unpack .
FastLZ admite cualquier compilador ANSI C/C90 con conformidad estándar, incluidos los populares como GCC, Clang, Visual Studio e incluso Tiny CC. Fastlz funciona bien en una serie de arquitecturas (32 bits y 64 bits, Big Endian y Little Endian), de Intel/AMD, PowerPC, System Z, Arm, MIPS y RISC-V.
El sistema de integración continua ejecuta un extenso conjunto de viajes redondos de compresión de descompresión en los siguientes sistemas:
Para obtener más detalles, consulte los registros de construcción de acciones de GitHub correspondientes.
| AMD64 | Linux | Windows | macosa |
| GCC | |||
| Sonido metálico | |||
| Tinycc | |||
| VS 2019 | |||
| i686 | Linux | Windows | macosa |
| GCC | |||
| Sonido metálico | |||
| Tinycc | |||
| VS 2019 | |||
| i586 | Linux | Dos | |
| GCC | |||
| Linux | |||
| PowerPC | |||
| GCC | |||
| PPC64 (LE) | |||
| GCC | |||
| GCC | |||
| S390X | |||
| GCC | |||
| armhf | |||
| GCC | |||
| brazo | |||
| GCC | |||
| MIPS (El) | |||
| GCC | |||
| GCC | |||
| MIPS64 (El) | |||
| GCC | |||
| GCC | |||
| riscv | |||
| GCC | |||
| riscv64 | |||
| GCC |
Supongamos que Fastlz comprime una matriz de bytes, llamado bloque sin comprimir , en otra matriz de bytes, llamado bloque comprimido . Para comprender lo que se almacenará en el bloque comprimido, es ilustrativo demostrar qué tan rápido descomprimirá el bloque para recuperar el bloque sin comprimir original.
El primer 3 bits del bloque, es decir, los 3 bits más significativos del primer byte, es la etiqueta de bloque . Actualmente, la etiqueta de bloque determina el nivel de compresión utilizado para producir el bloque comprimido.
| Etiqueta de bloque | Nivel de compresión |
|---|---|
| 0 | Nivel 1 |
| 1 | Nivel 2 |
El contenido del bloque variará según el nivel de compresión.
El nivel 1 de FastLZ implementa el algoritmo de compresión LZ77 con una ventana deslizante de 8 kb y hasta 264 bytes de longitud del partido.
El bloque comprimido consta de una o más instrucciones . Cada instrucción comienza con un código de operación de 1 byte, un código de operación de 2 bytes o un código de operación de 3 bytes.
| Tipo de instrucción | Código de operación [0] | Código de operación [1] | Código de operación [2] |
|---|---|---|---|
| Carrera literal | 000 , L₄-L₀ | - | - |
| Breve | M₂-M₀, R₁₂-R₈ | R₇-r₀ | - |
| Longitud | 111 , R₁₂-R₈ | M₇-m₀ | R₇-r₀ |
Tenga en cuenta que la primera instrucción en un bloque comprimido es siempre una ejecución literal.
Para la instrucción de ejecución literal, hay uno o más bytes siguiendo el código. Esto se llama la carrera literal.
Los 5 bits menos significativos de opcode[0] , L , determinan el número de literales que siguen el código de operación. El valor de 0 indica una ejecución literal de 1 byte, 1 indica una ejecución literal de 2 bytes, y así sucesivamente. La ejecución mínima literal es 1 y la ejecución literal máxima es 32.
El descompresor copia ( l + 1 ) bytes de ejecución literal, comenzando desde el primero justo después del código de operación.
Ejemplo : si el bloque comprimido es una matriz de 4 bytes de [0x02, 0x41, 0x42, 0x43] , entonces el código de operación es 0x02 y eso significa una ejecución literal de 3 bytes. El descompresor copiará los 3 bytes posteriores, [0x41, 0x42, 0x43] , al búfer de salida. El búfer de salida ahora representa el bloque (original) sin comprimir, [0x41, 0x42, 0x43] .
Los 3 bits más significativos de opcode[0] , M , determinan la longitud de la coincidencia . El valor de 1 indica una coincidencia de 3 bytes, 2 indica una coincidencia de 4 bytes, etc. La longitud mínima de coincidencia es 3 y la longitud máxima de coincidencia es 8.
Los 5 bits menos importantes de opcode[0] se combinaron con los 8 bits del opcode[1] , r , determina el desplazamiento de referencia . Dado que el desplazamiento está codificado en 13 bits, el mínimo es 0 y el máximo es 8191.
El siguiente código C recupera la longitud de coincidencia y el desplazamiento de referencia:
M = opcode [ 0 ] >> 5 ;
R = 256 * ( opcode [ 0 ] << 5 ) + opcode [ 1 ];El descompresor copia (m+2) bytes, comenzando desde la ubicación compensada por R en el búfer de salida. Tenga en cuenta que R es una referencia posterior , es decir, el valor de 0 corresponde al último byte en el búfer de salida, 1 es el segundo byte del último, y así sucesivamente.
Ejemplo 1 : Si el bloque comprimido es una matriz de 7 bytes de [0x03, 0x41, 0x42, 0x43, 0x44, 0x20, 0x02] , entonces hay dos instrucciones en el allí. La primera instrucción es la ejecución literal de 4 bytes (debido a L = 3 ). Por lo tanto, el descompresor copia 4 bytes al búfer de salida, lo que resulta en [0x41, 0x42, 0x43, 0x44] . La segunda instrucción es la coincidencia corta de 3 bytes (de M = 1 , es decir 0x20 >> 5 ) y el desplazamiento de 2. Por lo tanto, el compresor se remonta a 2 bytes desde la última posición, copia 3 bytes ( [0x42, 0x43, 0x44] ), y los agrega al búfer de salida. El búfer de salida ahora representa los datos completos sin comprimir, [0x41, 0x42, 0x43, 0x44, 0x42, 0x43, 0x44] .
Ejemplo 2 : Si el bloque comprimido es una matriz de 4 bytes de [0x00, 0x61, 0x40, 0x00] , entonces hay dos instrucciones allí. La primera instrucción es la ejecución literal de solo 1 byte ( l = 0 ). Por lo tanto, el descompresor copia el byte ( 0x61 ) al búfer de salida. El búfer de salida ahora se convierte en [0x61] . La segunda instrucción es la coincidencia corta de 4 bytes (de M = 2 , es decir, 0x40 >> 5 ) y el desplazamiento de 0. Por lo tanto, el descompresor copia 4 bytes que comienzan a usar la referencia posterior de 0 (es decir, la posición de 0x61 ). El búfer de salida ahora representa los datos completos sin comprimir, [0x61, 0x61, 0x61, 0x61, 0x61] .
El valor de opcode[1] , M , determina la longitud de coincidencia . El valor de 0 indica una coincidencia de 9 bytes, 1 indica una coincidencia de 10 bytes, etc. La longitud mínima de coincidencia es 9 y la longitud máxima de coincidencia es 264.
Los 5 bits menos significativos de opcode[0] se combinaron con los 8 bits de opcode[2] , R , determina el desplazamiento de referencia . Dado que el desplazamiento está codificado en 13 bits, el mínimo es 0 y el máximo es 8191.
El siguiente código C recupera la longitud de coincidencia y el desplazamiento de referencia:
M = opcode [ 1 ];
R = 256 * ( opcode [ 0 ] << 5 ) + opcode [ 2 ];El descompresor copia (m+9) bytes, comenzando desde la ubicación compensada por R en el búfer de salida. Tenga en cuenta que R es una referencia posterior , es decir, el valor de 0 corresponde al último byte en el búfer de salida, 1 es para el segundo a último byte, y así sucesivamente.
Ejemplo : si el bloque comprimido es una matriz de 4 bytes de [0x01, 0x44, 0x45, 0xE0, 0x01, 0x01] , entonces hay dos instrucciones allí. La primera instrucción es la ejecución literal con la longitud de 2 (debido a L = 1 ). Por lo tanto, el descompresor copia la ejecución literal de 2 bytes ( [0x44, 0x45] ) al búfer de salida. La segunda instrucción es la pareja larga con la longitud de coincidencia de 10 (de M = 1 ) y el desplazamiento de 1. Por lo tanto, el descompresor copia 10 bytes que comienzan a usar la referencia posterior de 1 (es decir, la posición de 0x44 ). El búfer de salida ahora representa los datos completos sin comprimir, [0x44, 0x45, 0x44, 0x45, 0x44, 0x45, 0x44, 0x45, 0x44, 0x45, 0x44, 0x45] .
La siguiente función C de 40 líneas implementa un descompresor totalmente funcional para el formato de bloque anterior. Tenga en cuenta que está destinado a ser educativo, por ejemplo, no se implementa ningún cheque vinculado y, por lo tanto, es absolutamente inseguro para la producción.
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 ;
}
}
}
}(Para ser escrito)
