Сжатие данных без потерь
Сжатие матрицы без потерь: от Julia к C и embedded
В своей работе я часто сталкиваюсь с проблемой передачи большого объема данных между оборудованием. Мне не нравится, что передача данных становится "бутылочным горлышком" системы. Решение проблемы было неожиданным - я вспомнил, что под капотом у архиватора Zip и решил написать свои портируемые реализации алгоритмов DEFLATE (сжатие данных) и INFLATE (распаковка данных). Они находятся в pure_deflate.c.
В этом проекте мы посмотрим как они работают, какой выигрыш они дают.
Пример: Матрица 400 × 400 Float64 занимает 1 280 000 байт. По UART 115200, 8N1 её передача займёт около 111 секунд. Сократим объём, сохранив все исходные биты.
using Random
if !isdefined(Main, :CDeflateDemoTools)
include(joinpath(@__DIR__, "demo_helpers.jl"))
end
import .CDeflateDemoTools as Demo
n = 400
repeats = 3
seed = 42
(; shape=(n,n), elements=n*n, bytes=n*n*sizeof(Float64))
2. Как работает кодек
В DEFLATE сжатие проходит в два этапа: сначала повторяющиеся байты заменяются ссылками, затем полученная последовательность кодируется по Хаффману. Разберём оба этапа на простом примере, а после проверим их на матрице. Во всех расчётах Julia вызывает наш pure_deflate.c через ccall; для первоначальной сборки библиотеки нужен GCC.
В последовательности ABCABCABC первые три байта записываются как литералы A, B, C. Оставшиеся шесть уже встречались, поэтому вместо них можно записать ссылку «скопировать 6 байт с расстояния 3» (рисунок 1). Чтобы находить такие повторы, наш кодек просматривает предыдущие данные в окне 4096 байт; длина одной ссылки ограничена 258 байтами.
Рисунок 1. Литералы и ссылка LZ77.
import .CDeflateDemoTools as Demo
sample = collect(codeunits("ABCABCABC"))
sample_packed = Demo.deflate(sample)
sample_restored = Demo.inflate(sample_packed, length(sample))
@assert sample_restored == sample
(; input=String(copy(sample)), input_bytes=length(sample),
packed_bytes=length(sample_packed), restored=String(copy(sample_restored)), exact=true)
Перебирать все предыдущие позиции дорого, поэтому поиск начинается с хеша трёх очередных байтов. По нему кодек находит цепочку возможных совпадений, сравнивает до 32 кандидатов и выбирает самое длинное. Если совпадение содержит хотя бы три байта, записывается ссылка; иначе – один исходный байт. Так входные данные превращаются в последовательность литералов и ссылок.
Теперь эту последовательность нужно записать в битовый поток. Для этого используются фиксированные коды Хаффмана из RFC 1951: литералы, длины и расстояния получают свои коды. Поскольку таблицы заранее известны декодеру, передавать их не требуется. При распаковке декодер читает те же коды, возвращает литералы и выполняет команды копирования.
Все операции происходят над байтами, поэтому восстанавливаются и особые представления Float64: NaN, бесконечности и знаковый ноль. Однако сам raw DEFLATE не содержит контрольной суммы: для защиты от повреждений при передаче её нужно добавить в протокол.
3. Проверка сжатия
Применим этот алгоритм к плавной матрице 400 × 400. Сначала представим её как поток байтов: элементы идут по столбцам, байты каждого Float64 – в порядке little endian. Это соглашение понадобится и при обратном преобразовании; вместе с данными сохраним форму массива и выбранный режим.
import .CDeflateDemoTools as Demo
A = [1000.0 + 0.5*(i+j-2)/(n-1) for i in 1:n, j in 1:n]
raw = Demo.matrix_bytes(A)
compressed = Demo.deflate(raw)
restored_bytes = Demo.inflate(compressed, length(raw))
@assert restored_bytes == raw
(; original_bytes=length(raw), compressed_bytes=length(compressed),
ratio=length(raw)/length(compressed), bit_exact=restored_bytes == raw)
После распаковки сравниваем исходные и восстановленные байты: так проверяется сохранность всех битов Float64. Эту последовательность действий объединяют pack_matrix и unpack_matrix. При упаковке дополнительно сравниваются размеры потоков; если сжатие не дало выигрыша, пакет содержит исходные байты.
import .CDeflateDemoTools as Demo
packet = Demo.pack_matrix(A; shuffle=false)
B = Demo.unpack_matrix(packet)
@assert size(B) == size(A)
@assert Demo.matrix_bytes(B) == Demo.matrix_bytes(A)
(; shape=size(B), codec=packet.codec, bit_exact=true,
special_values=Demo.special_values_test())
У близких по величине Float64 часть байтов часто совпадает, но в исходном потоке эти байты разделены остальными. Byte shuffle собирает байты одинаковых позиций вместе (рисунок 2), создавая более длинные повторы для кодека. После распаковки обратная перестановка возвращает исходный порядок. Проверим, оправдывает ли улучшение сжатия затраты на эту обработку.
Рисунок 2. Перестановка байтов.
import .CDeflateDemoTools as Demo
shuffled_payload = Demo.deflate(raw; shuffle=true)
restored_shuffled = Demo.inflate(shuffled_payload, length(raw); shuffle=true)
@assert restored_shuffled == raw
(; original_bytes=length(raw), plain_deflate_bytes=length(compressed),
shuffle_deflate_bytes=length(shuffled_payload), bit_exact=true)
Одной плавной матрицы для оценки недостаточно, поэтому сравним три случая: нули с повторами, плавные значения и случайные числа из [1000, 1001). Для каждого выполним сжатие с shuffle и без него. Таблица 1 пересчитывается при запуске и показывает медиану трёх измерений после прогрева.
import .CDeflateDemoTools as Demo
cases = Demo.examples(n; seed)
measurements = Demo.measure_cases(cases; repeats)
compression_results = Demo.size_table(measurements)
compression_results
4. Передача данных и модель Engee
Чтобы оценить выигрыш на интерфейсе, к времени обработки добавим время передачи сжатых байтов. При последовательном выполнении получаем:
По этой формуле строится таблица 2. Для UART 8N1 учитываем 10 бит на байт, для SPI предполагаем поток без пауз. Заголовки и повторные передачи пока исключены, поэтому результат служит оценкой для заданной скорости.
import .CDeflateDemoTools as Demo
interface_results = Demo.link_table(measurements)
interface_results
Этот расчёт рассматривает массив целиком. Чтобы показать передачу порциями и накопление очереди, собрана модель DeflateLinkChannel (рисунок 3). Byte Pack/Unpack преобразуют матрицу в байты и обратно, а шесть блоков C Function выполняют разбиение, сжатие, передачу, распаковку, сборку и побитную проверку.
Порции по 8 КиБ поступают каждые 0,01 с. В Deflate для каждой выбирается сжатый или исходный поток, после чего пакет попадает в FIFO канала. В сохранённой конфигурации скорость равна 100 000 байт/с, вместимость – 256 пакетов; при заполнении новый пакет теряется. На приёмнике Inflate восстанавливает байты, Assemble собирает все 157 порций, а BitExact сравнивает кадр с оригиналом. Для правильной распаковки значение shuffle_enable должно совпадать в кодере и декодере.
Рисунок 3. Модель DeflateLinkChannel.
При таком разбиении получаются 156 полных порций по 8192 байта и последняя – 2048 байт. Каждая сжимается со своим словарём, поэтому повторы между порциями уже не используются. Таблица 3 позволяет оценить, как это влияет на объём при разных размерах порции; учитываются только полезные байты без заполнения выходного буфера.
import .CDeflateDemoTools as Demo
block_results = Demo.block_table(raw)
block_results
Таблица 4. Расчёт передачи порций 8 КиБ с условным заголовком 16 байт на пакет. Размеры получены вызовами C-кодека; время рассчитано как объём / скорость без симуляции очереди.
using DataFrames
import .CDeflateDemoTools as Demo
pieces = [raw[i:min(i+8191,end)] for i in 1:8192:length(raw)]
payload_bytes = sum(min(length(x),length(Demo.deflate(x;shuffle=true))) for x in pieces)
wire_bytes = payload_bytes + 16length(pieces)
packet_results = DataFrame(
"Скорость, байт/с" => [50000,100000],
"Порций" => fill(length(pieces),2),
"Исходные байты с заголовками" => fill(length(raw)+16length(pieces),2),
"Сжатые байты с заголовками" => fill(wire_bytes,2),
"Без сжатия, с" => [(length(raw)+16length(pieces))/v for v in (50000,100000)],
"Со сжатием, с" => [wire_bytes/v for v in (50000,100000)],
)
packet_results
Таблица 4 оценивает только передачу порций, тогда как таблица 2 учитывает также время кодека. Вместе они показывают, сколько байтов удаётся сэкономить и при какой скорости эта экономия окупает обработку.
Саму модель можно отдельно запустить из /user/DeflateDemoRepo/DeflateLinkChannel.engee, изменив настройки Matrix и Channel. При проверке результата сначала нужен dl_complete: лишь после сборки всего кадра имеет смысл оценивать dl_exact. Таблицы этого скрипта пересчитываются вызовами кодека и результатами симуляции не являются.
import .CDeflateDemoTools as Demo
report_path = joinpath(@__DIR__, "pure_demo_results.md")
Demo.write_report(report_path, [compression_results, interface_results, block_results, packet_results])
(; report=report_path, julia=string(VERSION), implementation=Demo.implementation_label(),
bit_exact=all(r.exact for r in measurements))
5. От демки к устройству
В демке матрица хранится целиком, чтобы удобно сравнить исходные и восстановленные данные. На устройстве такой подход требует слишком много памяти: один кадр занимает 1,28 МБ, а очередь модели – ещё около 2 МиБ. Поэтому в прошивку перенесём обработку одной порции.
Источник набирает 8 КиБ данных, сжимает их нашим C-кодеком и отправляет полученный пакет. Если сжатие увеличило размер, в пакет попадают исходные байты. После завершения передачи буферы можно использовать снова. Приёмник распаковывает очередную порцию и сразу отдаёт её потребителю либо записывает во внешнюю память. Полный кадр тогда не нужно держать во внутренней RAM ни на одной стороне.
Для такой схемы можно заранее посчитать память: рабочие структуры кодека плюс входной, выходной и временный буферы. В таблице 5 источник и приёмник показаны отдельно.
Таблица 5. Расход RAM при обработке порций по 8 КиБ. Стек, DMA, очереди и остальная прошивка не включены.
| Операция | Workspace, байт | Буферы, байт | Всего, байт |
|---|---|---|---|
| Сжатие | 32768 | 8192 + 9218 | 50178 |
| Сжатие с shuffle | 32768 | 8192 + 9218 + 8192 | 58370 |
| Распаковка транспортного пакета | 2144 | 8192 + 8192 | 18528 |
| Распаковка с unshuffle | 2144 | 8192 + 8192 + 8192 | 26720 |
На рисунке 4 видно, какая часть RAM уходит на рабочую структуру и какая – на буферы.
Рисунок 4. RAM на порцию 8 КиБ.
По таблице 5 и рисунку 4 источник со shuffle требует около 57 КиБ RAM, а приёмник с обратной перестановкой – 26 КиБ. Это память одной обрабатываемой порции; стек и остальная прошивка в расчёт не входят. Если получение, обработка и передача идут параллельно, понадобятся дополнительные буферы. Освобождать передаваемый буфер можно только после того, как интерфейс закончил с ним работу.
Кроме памяти нужно согласовать темп поступления данных со скоростью обработки и канала. Когда источник выдаёт порции быстрее, чем они отправляются, даже ограниченная очередь постепенно заполнится. В таком случае потребуется приостанавливать источник или заранее определять, какие данные допустимо потерять.
Выводы
Сжатие сокращает передачу, когда экономия на объёме превышает время работы кодека. Поэтому выбирать режим нужно по полному пути: сжатие, канал и восстановление. Byte shuffle может улучшить результат, но его дополнительные затраты тоже должны окупаться.
В демке все таблицы выигрыша рассчитываются вызовами C-кодека из Julia, а восстановление проверяется побитно. Модель показывает, где в передаче появляются очередь и сборка кадра; для переноса на устройство обработку следует организовать порциями. Окончательное решение о размере порции принимается после замеров времени и памяти на целевом контроллере.