Привет, Голос! Пора тряхнуть песочком — поделиться результатами одного сугубо спортивного инженерного эксперимента.
Давеча, от безделья, я написал cast (Custom Adaptive Stream Transcoder) — кастомный движок потокового сжатия без потерь (Lossless), созданный на чистом C++20.
По сути, это «велосипед ручной сборки». Конструировал я его из любопытства проверить: можно ли использовать унарное кодирование в реальном потоке так, чтобы не поймать классический «унарный взрыв» размера файлов, и сделать из этого стабильный транспорт для low-end железа.
Исходный код проекта полностью открыт под MIT-лицензией на GitHub: github.com
Идея и проблема «унарного взрыва»
Изначально задумка была простой: оперировать на уровне одного ниббла (4 бита). Это дает минимальный latency (задержку) — конвейер кушает данные кусок за куском «на лету», ему не нужно буферизировать поток и ждать, что там будет дальше. Данные кодируются парами чисел из диапазона 0–3, а максимальная длина унарного кода на пару жестко ограничена 6 битами.
Но у унарного кода есть огромный минус — он плодовит на единицы, и с бешеной скоростью их рожает, как только числа становятся чуть больше нуля. Если просто кодировать сырой поток «в лоб», файл мгновенно раздуется как иглобрюх на берегу.
Спасение через Compile-Time препроцессинг
Чтобы укротить унарник, я внедрил агрессивный препроцессинг данных перед кодированием. Его задача — размножить нули в потоке всеми доступными способами.
Конвейер устроен так:
- Дельта-кодирование: превращает плавные изменения данных в околонулевые значения.
- Код Грея (от 1 до 3 проходов): сглаживает битовые скачки при переходе через границы степеней двойки.
- Инверсия: если единиц все равно больше, мы просто переворачиваем биты.
Чтобы все это не тормозило в runtime, я перенес брутфорс и выбор оптимальной стратегии сжатия на плечи компилятора через шаблоны C++20 (template<bool Delta, uint8_t Gray, bool Invert>). На выходе определенная стратегия кодирует данные унарным кодом с помощью быстрых LUT-таблиц (Look-Up Tables), которые полностью помещаются в L1-кэш процессора.
«Чит» с матричным унарным хэшем и LUT
Для максимального ускорения я отказался от циклов побитовой записи и упаковал варианты в предвычисленные LUT-таблицы. Таблица генерировалась по схеме «вертикального» матричного унарного кода.
Возьмем для примера пару чисел [1, 3]:
- Первый слой (числа > 0): оба подходят →
[1, 1] - Второй слой (числа > 1): первое сдулось (пишем закрывающий флаг
0), второе растет →[0, 1] - Третий слой (числа > 2): первое выбыло, второе растет →
[1](для максимального числа 3 закрывающий ноль не нужен, так как 4 быть не может).
Убираем границы слоев и склеиваем биты в строку: получаем готовый хэш числа в таблице — 11011 (всего 5 бит)!
В коде это выглядит так:
alignas(64) constexpr CodeInfo LUT_ENCODE = {
{ {0b00, 2}, {0b010, 3}, {0b0110, 4}, {0b0111, 4} },
{ {0b100, 3}, {0b1100, 4}, {0b11010, 5}, {0b11011, 5} }, // Вот наша пара -> 0b11011
{ {0b1010, 4}, {0b11100, 5}, {0b111100, 6}, {0b111101, 6} },
{ {0b1011, 4}, {0b11101, 5}, {0b111110, 6}, {0b111111, 6} }
};
Директива alignas(64) выравнивает таблицы строго по границам кэш-линий процессора. Декодеру не нужно крутить циклы и ломать предсказатель переходов (полный branchless подход) — он просто мгновенно забирает значения из кэша L1 процессора через REVERSE_LUT.
Архитектура кадра: Сетевой транспорт
Вся обработка происходит независимыми блоками (кадрами) фиксированного размера (по умолчанию 512 байт, задается через CLI).
Структура закодированного фрейма:
[Технический заголовок: 1 байт] + [Битовый поток полезных данных] + [Хвост последнего байта, выровненный нулями]
Оверхед на заголовок мизерный (~0.2%). Но главное — независимость кадров. Если такой поток пустить по сети (например, через UDP) и один пакет потеряется, битовая синхронизация всего остального потока НЕ сломается. Следующий фрейм декодируется абсолютно корректно с чистого листа.
Результаты тестов (От логов до тяжелого RAW-видео)
Cast-у нужен был кастинг — жесткий стресс-тест на реальных данных. Важное условие — восстановление всегда идет «бит в бит» (валидация через fc /b или diff на выходе из пайпа всегда сходится на 100%).
Тесты проводились на скромном ноутбучном железе: Core i5 vPro и всего 4 ГБ оперативной памяти.
1. Системные бинарные логи Windows (System.evtx, ~21 МБ):
- Оригинальный размер: 20,975,616 байт
- Сжатый размер: 15,730,560 байт (Сжатие ~25%)
- Скорость упаковки: 34.1 МБ/сек | Распаковки: 43.0 МБ/сек
2. Большой текстовый CSV-датасет телеметрии IoT (~62 МБ):
- Оригинальный размер: 61,926,558 байт
- Сжатый размер: 54,824,254 байт (Сжатие ~11.5%)
- Скорость упаковки: 37.2 МБ/сек | Распаковки: 39.8 МБ/сек
3. Финальный краш-тест: Огромный поток сырого видео (Ночной город, дождь, блики, капли на стекле, съемка из движушегося атвтомобиля. 720p/30 fps, длительность: 120 сек, без звука, ~7.5 ГБ):
Запуск напрямую через консольную конвейерную трубу Windows:
type raw_720p_video.avi | cast.exe -c - - | cast.exe -d - restored_pipe.avi
- Оригинальный размер: 7,502,661,288 байт
- Сжатый размер: 6,877,351,176 байт (Сжатие ~8.3%, сохранено ~624 МБ)
- Время работы под непрерывной нагрузкой: ~10 минут (617 456 ms)
- Скорость в трубе: стабильные 11.58 MB/sec
И здесь самый цимес в том, что при передаче через трубу не потерялось ни единого бита! Сквозь конвейер непрерывным потоком пролетело более 14.6 миллионов фреймов. Стоило алгоритму ошибиться хотя бы в одном бите или сдвинуть выравнивание хвоста кадра — вся последующая гигабайтная цепочка мгновенно превратилась бы в кашу, и fc /b выдал бы миллионы различий. Но кодек отработал со стопроцентной математической точностью. Конвейер спокойно пережевал всё, что в него заталкивалось.
За счет фиксированного размера блока потребление оперативной памяти не превышало нескольких килобайт — алгоритм шел «в линию», показав идеальную линейную сложность O(N) без малейших утечек памяти на ультра-ограниченном железе.
Где алгоритм пасует? Ожидаемо на звуке (16-bit PCM). В аудио-волне слишком много хаотичного шума в младших битах. Дельта-кодирование там не справляется, нулей не получается, и унарный код моментально беременеет, раздувая файлы на 10–15%. (С другой стороны, это не очень большая плата, когда важна точность при допотопном железе).
Итог
Конечно, это не Huffman и не конкурент монстрам вроде zstd. Но как экспериментальный сетевой транспорт для «плоских» данных, бинарных логов или тяжелых raw-потоков в условиях жестко ограниченных системных ресурсов — концепт полностью себя оправдывает. Унарный код можно и нужно приручить, если правильно ему готовить препроцессинг.
Исходники проекта, логику работы BitStream и конфигурацию таблиц можно подробно рассмотреть в репозитории: github.com
Пишите! Комменты никто не запрещал.
