FastLZ
1.0.0
FASTLZ (MIT License)-это реализация ANSI C/C90 алгоритма Lempel-ZIV 77 (LZ77) сжатия данных без потерь. Он подходит для сжатия серии текстовых/параграфов, последовательностей необработанных данных пикселей или любых других блоков данных с большим количеством повторения. Он не предназначен для использования на изображениях, видео и других форматах данных, обычно уже в оптимальной сжатой форме.
Основное внимание для FastLZ - очень быстрое сжатие и декомпрессия, делая это за счет коэффициента сжатия. В качестве иллюстрации сравнение с Zlib при сжатии enwik8 (также более подробно):
| Соотношение | Сжатие | Декомпрессия | |
|---|---|---|---|
| Fastlz | 54,2% | 159 МБ/с | 305 МБ/с |
| Zlib -1 | 42,3% | 50 МБ/с | 184 МБ/с |
| Zlib -9 | 36,5% | 11 МБ/с | 185 МБ/с |
Fastlz используется многими программными продуктами, от ряда игр (таких как Death Stranding) до различных проектов с открытым исходным кодом (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 поддерживает любой стандартный компилятор ANSI C/C90, в том числе популярные, такие как GCC, Clang, Visual Studio и даже Tiny CC. Fastlz хорошо работает на нескольких архитектурах (32-разрядная и 64-битная, большая эндийская и маленькая эндиан), от Intel/AMD, PowerPC, System Z, ARM, MIPS и RISC-V.
Система непрерывной интеграции запускает обширный набор круглых поездок с устранением сжатия в следующих системах:
Для получения более подробной информации проверьте соответствующие журналы строительства действий GitHub.
| AMD64 | Linux | Окна | macOS |
| GCC | |||
| Герметичный | |||
| Tinycc | |||
| Против 2019 года | |||
| I686 | Linux | Окна | macOS |
| GCC | |||
| Герметичный | |||
| Tinycc | |||
| Против 2019 года | |||
| i586 | Linux | Дос | |
| GCC | |||
| Linux | |||
| PowerPC | |||
| GCC | |||
| PPC64 (LE) | |||
| GCC | |||
| GCC | |||
| S390x | |||
| GCC | |||
| Армф | |||
| GCC | |||
| ARM64 | |||
| GCC | |||
| MIPS (EL) | |||
| GCC | |||
| GCC | |||
| MIPS64 (EL) | |||
| GCC | |||
| GCC | |||
| RISCV | |||
| GCC | |||
| RISCV64 | |||
| GCC |
Давайте предположим, что Fastlz сжимает массив байтов, называемый несжатым блоком , в другой массив байтов, называемый сжатым блоком . Чтобы понять, что будет сохранено в сжатом блоке, иллюстрирует, как Fastlz распадет блок, чтобы получить исходный несущественный блок.
Первым 3-битным блоком, т.е. 3 наиболее значимыми битами первого байта, является блок-тегом . В настоящее время блок -тег определяет уровень сжатия, используемый для получения сжатого блока.
| Блок тег | Уровень сжатия |
|---|---|
| 0 | Уровень 1 |
| 1 | Уровень 2 |
Содержание блока будет варьироваться в зависимости от уровня сжатия.
Fastlz Level 1 реализует алгоритм сжатия LZ77 с раздвижным окном 8 КБ и до 264 байт длины совпадения.
Сжатый блок состоит из одной или нескольких инструкций . Каждая инструкция начинается с 1-байтового оптового кода, 2-байтового OpCode или 3-байтового OpCode.
| Тип инструкции | 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.
Декомпрессорные копии ( L + 1 ) байты буквального прогона, начиная с первого сразу после OpCode.
Пример : если сжатый блок представляет собой 4-байтовый массив [0x02, 0x41, 0x42, 0x43] , то опкомда составляет 0x02 , что означает буквальный прогон из 3 байтов. Затем декомпрессор скопирует последующие 3 байта, [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 ];Декомпрессовые копии (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] в сочетании с 8 битами opcode[2] , R определяет опорное смещение . Поскольку смещение кодируется в 13 битах, минимум равен 0, а максимум - 8191.
Следующий код C получает длину совпадения и справочное смещение:
M = opcode [ 1 ];
R = 256 * ( opcode [ 0 ] << 5 ) + opcode [ 2 ];Декомпрессоры копий (M+9) байты, начиная с местоположения, компенсируемого R в выходном буфере. Обратите внимание, что R является обратной ссылкой , то есть значение 0 соответствует последнему байту в выходном буфере, 1 для второго -последнего байта и так далее.
Пример : если сжатый блок представляет собой 4-байтовый массив [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] .
Следующая функция C 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 ;
}
}
}
}(Чтобы быть написанным)
