hfm

Консольная утилита, умеющая сжимать произвольный файл, а затем разжимать его обратно с помощью алгоритма Хаффмана.

Локальная сборка и запуск

1. Установите необходимые инструменты:
   • CMake (3.14+)
2. Клонируйте репозиторий:

   git clone https://github.com/e4d08/hfm.git

3. Соберите:

   cd hfm
   ./scripts/build.sh

Сжатие

Для сжатия просто укажите сжимаемый файл и через флаг -o передайте выходной файл:

hfm my_file -o my_compressed_file.hfm

Утилита создаст файл my_compressed_file.hfm в формате hfm, описание которого приводится ниже.

Разжатие

Для разжимания файла в формате hfm просто добавьте флаг -d (decompress):

hfm -d my_compressed_file.hfm -o my_decompressed_file

Описание формата hfm

hfm — это минималистичный формат сжатого файла. Он устроен очень просто: исходный файл сжимается блоками по 65535 байтов, в выходной файл записываются результаты сжатия каждого блока, первый блок расположен в самом начале файла hfm.

Базовое устройство блока:

1. Заголовок:
   • байт флагов (1 байт);
   • размер блока в байтах (2 байта);
   • размер исходных данных (2 байта);
2. Таблица частот (256 x 2 = 512 байтов);
3. Собственно сжатые данные (до 65535 байтов).

Итого оверхед на блок составляет 517 байтов.

Если вдруг какой-то из исходных блоков в результате сжатия увеличится (станет больше 65535 байтов), то устройство выходного блока изменится:

1. Аналогичный заголовок, но байт флагов установлен в 0x1;
2. Далее идут исходные данные в неизмененном виде.

Итоговый оверхед в таком случае составит всего 5 байтов.

Замеры производительности

Проект предоставляет набор скриптов для анализа производительности утилиты: scripts/benchmark.sh, scripts/report.py и scripts/plot.py. benchmark.py использует утилиту hyperfine для измерения производительности и сравнения с другими утилитами: bzip2, gzip, xz и zstd. report.py создает сводные таблички в формате Markdown, содержащие измерения таких параметров как скорость сжатия и коэффициент сжатия. Скрипт plot.py с помощью библиотеки matplotlib рисует графики по сделанным замерам.