Сжатие данных в микроконтроллере, DEFLATE и библиотека miniz

Когда речь заходит о передаче больших объёмов информации, особенно текстовой, логично вспомнить о сжатии данных. Существует множество алгоритмов сжатия, многие из которых имеют давнюю историю, некоторые алгоритмы вплотную подбираются к теоретическому пределу степени сжатия — но требуют много времени и памяти, другие работают быстро и скверно, какие-то из них прямо предназначены для определённых типов данных, но стандартом в HTTP давно стал gzip.

Этот формат воплощает метод DEFLATE, который базируется на двух базовых алгоритмах: LZ77 и кодировании Хаффмана.

LZ77 ищет во входном потоке данных повторящиеся последовательности, и заменяет все повторные их вхождения ссылками. В бинарных данных это довольно редкая ситуация, но в тексте это происходит гораздо чаще, и это даёт возможность добиться существенного сжатия уже на этом этапе.

Таким образом, во время прохода по тексту алгоритм LZ77 составляет словарь из повторяющихся фрагментов, и встречая старый фрагмент, заменяет его номером фрагмента из словаря.

Дальше работает алгоритм Хаффмана, который подсчитывает частоту употребления каждого фрагмента из словаря, и назначает частым фрагментам более короткий номер — так мы сокращаем сами номера фрагментов. Доказано, что код Хаффмана очень близок к теоретическому пределу степени сжатия.

Эти алгоритмы можно использовать, к примеру, для сжатия JSON-сообщений — в типичном случае вы получите степень сжатия от 30% (для коротких сообщений) до 2 раз (если сообщение длиннее 500 байт) и больше.

Классическая библиотека zlib, написанная и поддерживаемая авторами самого gzip Жан-Лу Гайи и Марком Адлером, довольно неудобна в использовании — это множество c и h-файлов, зависимость от системных дефайнов, привязка к системным форматам целых чисел. У меня не получилось её завести, и я обратился к другой библиотеке, которую заметил уже очень давно — miniz за авторством Rich Geldreich.

Она предоставляет простые функции compress и uncompress, которые принимают входной поток данных (массив unsigned char) + длину данных в нём, и указатель на выходной буфер + указатель на int, в котором будет записана длина сжатых данных.

На компьютере библиотека запускается очень легко, нужно лишь подключить её через include (странный способ):

#include "stdio.h"
#include "stdlib.h"
#include "miniz.c"

void main()
{
static const char *s_pStr = "{\"event\": 1051, \"counters\": {\"00\": 45312, \"01\": 67543, \"05\": 124, \"0C\": 0, \"1A\": 654677, \"1B\": 6547, \"17\": 1235, \"18\": 4132, \"FA\": 7652, \"FD\": 75462}, \"card_number\": \"04C9DED1D90280\"}";
uLong comp_len = 300, uncomp_len = 300;
int i;
unsigned char pComp[300] = { 0 }, pUncomp[300] = { 0 };
printf("\noriginal - %d,\ndata: %s\n", strlen(s_pStr), s_pStr);

compress(pComp, &comp_len, (const unsigned char *)s_pStr, strlen(s_pStr));
printf("\ncompressed - %d bytes,\ndata: ", comp_len);
for(i = 0; i < comp_len; i++)
printf("%02X ", pComp[i]);

uncompress(pUncomp, &uncomp_len, (const unsigned char *)pComp, comp_len);
printf("\n\nuncompressed - %d bytes,\ndata: %s\n", uncomp_len, pUncomp);

printf("\nCompression ratio: %2.1f%%\n", 100.0*comp_len/uncomp_len);
}

Однако, при попытке перенести этот код на микроконтроллер STM32F217 возникла проблема — выделение памяти под структуру tdefl_compressor заканчивается неудачей. Она требует у malloc кусок памяти размером в 320 килобайт, чего в микроконтроллерах отродясь не бывало. Нехило, разом зохавать 320 кБ. Чо ж делать-то? :)

Посмотрим, из чего состоит эта структура.

typedef struct
{
tdefl_put_buf_func_ptr m_pPut_buf_func; // указатель на функцию, это немного
void *m_pPut_buf_user; // указатель на войд, тоже чуть-чуть
mz_uint m_flags, m_max_probes[2]; // свой typedef на uint
int m_greedy_parsing; // ок, простой int
mz_uint m_adler32, m_lookahead_pos, m_lookahead_size, m_dict_size; // опять инт
mz_uint8 *m_pLZ_code_buf, *m_pLZ_flags, *m_pOutput_buf, *m_pOutput_buf_end; // свой typedef на char, всё это очень маленькое, не может столько занимать
mz_uint m_num_flags_left, m_total_lz_bytes, m_lz_code_buf_dict_pos, m_bits_in, m_bit_buffer; // и опять int
mz_uint m_saved_match_dist, m_saved_match_len, m_saved_lit, m_output_flush_ofs, m_output_flush_remaining, m_finished, m_block_index, m_wants_to_finish; // и опять
tdefl_status m_prev_return_status; // выше определён как enum из четырёх значений
const void *m_pIn_buf; // указатель на войд
void *m_pOut_buf; // и так далее, до сих пор ни одной огромной переменной!
size_t *m_pIn_buf_size, *m_pOut_buf_size; // тоже целое число
tdefl_flush m_flush; // тоже 4-значный enum
const mz_uint8 *m_pSrc; // char
size_t m_src_buf_left, m_out_buf_ofs; // int
mz_uint8 m_dict[TDEFL_LZ_DICT_SIZE + TDEFL_MAX_MATCH_LEN - 1]; // опаньки, вот оно! массив чаров!
mz_uint16 m_huff_count[TDEFL_MAX_HUFF_TABLES][TDEFL_MAX_HUFF_SYMBOLS]; // и двумерный массив long intов!
mz_uint16 m_huff_codes[TDEFL_MAX_HUFF_TABLES][TDEFL_MAX_HUFF_SYMBOLS]; // ещё один!
mz_uint8 m_huff_code_sizes[TDEFL_MAX_HUFF_TABLES][TDEFL_MAX_HUFF_SYMBOLS]; // похоже, дальше сплошные эпические массивы.
mz_uint8 m_lz_code_buf[TDEFL_LZ_CODE_BUF_SIZE]; // да, вот всё это жрёт память.
mz_uint16 m_next[TDEFL_LZ_DICT_SIZE];
mz_uint16 m_hash[TDEFL_LZ_HASH_SIZE];
mz_uint8 m_output_buf[TDEFL_OUT_BUF_SIZE];
} tdefl_compressor;

Чему же равны эти дефайны?

TDEFL_LZ_DICT_SIZE = 32768
TDEFL_LZ_HASH_SIZE = 32768
TDEFL_LZ_CODE_BUF_SIZE = 65536
TDEFL_MAX_MATCH_LEN = 258
TDEFL_MAX_HUFF_TABLES = 3
TDEFL_MAX_HUFF_SYMBOLS = 288
TDEFL_OUT_BUF_SIZE = 85196

Похоже, выделяются массивы отдельно под первый раунд (LZ77) и второй раунд сжатия (код Хаффмана). Уже и так всё понятно, но давайте посмотрим реальные размеры всех этих массивов:

m_dict = 33 кБ

m_huff_count + m_huff_codes + m_huff_code_sizes = 4 кБ

m_lz_code_buf = 25 кБ

m_next = 65 кБ (!)

m_hash = 8 кБ

m_output_buf = 32 кБ

Ну всё ясно, нашли главных виновников. Надо уменьшать размеры этих массивов, поправив дефайны — но я не знаю как библиотека работает «под капотом», наверняка же нельзя просто так наобум кромсать массивы. Директива TDEFL_LESS_MEMORY не особенно помогла, библиотека по-прежнему требовала 168 кБ памяти. В моём STM32F217 всего 128 кБ памяти, да и на другие задачи память тоже нужна.

Я написал автору библиотеки, Rich Geldreich. Первое что он предложил сделать — это уменьшить размер словаря (m_dict), но он в два раза меньше самого большого массива, m_next. Вторая рекомендация была уже более предметной:

  1. Уменьшить TDEFL_LZ_CODE_BUF_SIZE до 4-8 кБ или около того. Уменьшение размера блоков увеличит количество блоков на выходе, уменьшая степень сжатия.
  2. Уменьшить TDEFL_LZ_HASH_BITS до 9-10, но это приведёт к уменьшению производительности. При этом нужно установить TDEFL_LEVEL1_HASH_SIZE_MASK равным меньшему из 4095 или (1 « TDEFL_LZ_HASH_BITS) — 1.
  3. Значительное уменьшения требований по памяти достигается уменьшением TDEFL_LZ_DICT_SIZE до 1-16 кБ, при этом оно должно быть степенью двойки. Rich опасался что это приведёт к глюкам в коде, но забегая вперёд скажу что всё прошло гладко.

В итоге я доигрался с уменьшением массивов до:

TDEFL_LZ_CODE_BUF_SIZE = 1 кБ
TDEFL_OUT_BUF_SIZE = TDEFL_LZ_CODE_BUF_SIZE * 1 (вместо * 1.3)
TDEFL_LZ_HASH_BITS = 8
TDEFL_LZ_DICT_SIZE = 1 кБ

доведя таким образом memory footprint до ровно 10 кБ.

Ещё одна проблема — по умолчанию размер кучи ограничен всего 0x2000 = 8192 байт, больше вы выделить не можете. Это легко поправить, в IAR нужно зайти в свойства проекта -> Linker -> Override default, Edit -> Stack/Heap sizes -> HEAP, я поставил 0x15000. Для STM32F217 этого достаточно, можно чуть больше.

linker heap

Для запуска в окружении МК библиотеке нужно также задать дефайны MINIZ_NO_STDIO и MINIZ_NO_TIME, чтобы она не попыталась использовать системные функции ввода/вывода и времени.

Проверив работу библиотеки на разных наборах данных (я экспериментировал с JSON-строками) — преимущественно текстовых, преимущественно численных, с кусками русскоязычных идентификаторов и так далее, я не заметил никаких проблем. Одна из моих тестовых JSON-строк:

{"event": 1051, "counters": {"00": 45312, "01": 67543, "05": 124, "0C": 0, "1A": 654677, "1B": 6547, "17": 1235, "18": 4132, "FA": 7652, "FD": 75462}, "card_number": "04C9DED1D90280"}

Она имеет длину 183 байта, после сжатия библиотекой miniz она сокращается до 134 байт (-34%), очень хороший результат для такой сравнительно короткой строки: ведь чем длиннее строка, тем больше получается словарь, и сжатие становится эффективнее, потому что для очень многих последовательностей найдётся образец в словаре. На коротких строках словарь мал, и нельзя ожидать сильного сжатия.

miniz

На более длинных строках, таких как пример на официальном сайте json:

{
"glossary": {
"title": "example glossary",
"GlossDiv": {
"title": "S",
"GlossList": {
"GlossEntry": {
"ID": "SGML",
"SortAs": "SGML",
"GlossTerm": "Standard Generalized Markup Language",
"Acronym": "SGML",
"Abbrev": "ISO 8879:1986",
"GlossDef": {
"para": "A meta-markup language, used to create markup languages such as DocBook.",
"GlossSeeAlso": ["GML", "XML"]
},
"GlossSee": "markup"
}
}
}
}
}

кстати, она имеет длину 582 байта; на таких строках можно добиться гораздо большего сжатия, в этом примере 252 байт (степень сжатия 43%) на максимальных настройках. Кстати, степень сжатия в функции compress принята «средней», чтобы управлять ей используйте функцию compress2, которая последним параметром принимает дефайн типа MZ_NO_COMPRESSION, MZ_BEST_SPEED, MZ_BEST_COMPRESSION или даже MZ_UBER_COMPRESSION. Автор модуля явно не лишён юмора :)

Однако нужно помнить что во многих алгоритмах сжатия заданная «сила сжатия» на самом деле влияет именно на размер памяти, требуемой при разжатии, и это косвенно сказывается собственно на степени сжатия.

И ещё один интересный момент, архиватор 7z с алгоритмом gzip и пресетом ultra сжал мою 183-байтовую строчку до 156 байт, а miniz (я напомню) до 134. Получается, miniz в два раза круче ultra 7z gzip!

Справедливости ради стоит сказать что существует алгоритм zopfli, который может достичь на 10% более сильного сжатия, чем стандартная реализация DEFLATE, но ему потребуется в 100 раз больше времени. Делает он это за счёт попыток найти кратчаший путь в графе, короче он пытается по-разному разбить данные для сжатия и ищет самый оптимальный способ это сделать.

Ещё существуют программы deflopt и defluff, которые принимают результат работы DEFLATE и оптимизируют код, вытягивая ещё долю процента сжатия.

Этот алгоритм сжатия можно использовать как для сохранения данных в файл, так и для общения по сети, веб-серверы должны прожёвывать GZIP-трафик сходу и без проблем.

Вырисовывается структура правильного обмена данными с сервером: протокол верхнего уровня HTTP + транспорт JSON + сжатие GZIP. Осталось добавить шифрование — и получится законченный протокол: удобный, текстовый, защищённый и сжатый.