В предыдущем материале на nk9.ru мы разобрали, почему физический объем Flash-памяти 8-битных микроконтроллеров AVR застыл на отметке 128–256 Килобайт и почему появление чипов на 512 КБ экономически и архитектурно невозможно. Но что делать инженеру, если проект требует внедрения сложного графического интерфейса с десятками монохромных иконок, вывода локализованных текстовых меню на пяти языках и хранения таблиц калибровки датчиков? И нужно сделать так, что бы сжатие без потерь было полностью.
Обычный веб-разработчик скажет: «Купите чип помощнее, память стоит копейки». Настоящий системный инженер лишь усмехнется в усы, достанет блокнот и начнет писать алгоритм компрессии.
Главное правило встраиваемых систем: нам не нужно сжимать данные на самом микроконтроллере. Наша задача — сжать тяжелые статические ресурсы один раз на мощном персональном компьютере (этап компиляции), а на микроконтроллер записать лишь плотный, упакованный байт-код и сверхбыстрый, микроскопический декомпрессор на чистом Си.
Сегодня мы препарируем два фундаментальных алгоритма сжатия без потерь (Lossless Compression), идеально подходящих для жестких рамок 8-битных МК: Run-Length Encoding (RLE) и Кодирование Хаффмана.
Часть 1. Почему стандартные ZIP и GZIP неприменимы в микроконтроллерах?
Новичок, пришедший из «большого IT», первым делом пытается портировать в проект популярные библиотеки типа zlib (алгоритм Deflate). И тут же сталкивается с суровым аппаратным дефолтом.
Алгоритмы класса Deflate (основа форматов .zip, .gz, .png) используют скользящее окно поиска совпадений LZ77 и словари.
- Проблема: Для эффективного восстановления данных алгоритму требуется держать в оперативной памяти (SRAM) буфер декодирования размером от 2 до 32 Килобайт.
- Реальность: У классического контроллера ATmega328P всей оперативной памяти — 2 Килобайта. Попытка выделить буфер под LZ77 мгновенно переполнит ОЗУ и приведет к зависанию системы.
Нам нужны алгоритмы, которые:
- Требуют нулевого (или околонулевого) расхода SRAM для декодирования.
- Работают по принципу потокового чтения: прочитали байт из Flash-памяти программ (
PROGMEM), мгновенно декодировали, сразу отправили в периферию (например, в дисплей по шине SPI). - Имеют простую математику, не загружающую 8-битное ядро сложными операциями деления или вычислениями с плавающей запятой.
Этим критериям идеально соответствуют RLE и алгоритм Хаффмана.
Часть 2. Run-Length Encoding (RLE): Простое оружие против монотонности
Алгоритм RLE (кодирование длин серий) — это самый простой в реализации алгоритм сжатия. Его суть заключается в замене повторяющихся последовательностей байт на пару: [Количество повторов, Значение байта].
Где RLE эффективен на 100%:
- Монохромная графики (битовые карты дисплеев): Иконки, шрифты, заставки. На экранах всегда много сплошных черных или белых полей.
- Логи датчиков: Если физическая величина долго не меняется, в памяти пишется длинная череда одинаковых значений.
Где RLE превращается в катастрофу:
- Если данные постоянно меняются (например, зашумленный аналоговый сигнал:
21, 22, 21, 23, 22...), RLE не просто не сожмет их, а увеличит объем данных ровно в два раза, так как запишет каждую точку как[1, 21], [1, 22], [1, 21]....
Профессиональный вариант RLE: Алгоритм PackBits
Чтобы избежать раздувания данных на неповторяющихся байтах, в АРК используют улучшенную модификацию RLE — аналог классического стандарта Apple PackBits.
Каждый управляющий байт (маркер) разделяет данные на два типа:
- Серия повторов (Run): Старший бит равен 1. Остальные 7 бит указывают количество повторов (от 1 до 127). Следующий за маркером байт нужно повторить раз.
- Литералы (Literal): Старший бит равен 0. Остальные 7 бит указывают количество уникальных байт, которые идут следом и должны быть скопированы без изменений.
Реализация PackBits-декомпрессора на Си для AVR (nk9.ru):
Этот код оптимизирован для работы на 8-битных контроллерах. Он читает сжатые данные напрямую из Flash-памяти программ (PROGMEM) и не расходует драгоценную оперативную память.
c
#include <avr/pgmspace.h>
// Сжатый массив графики (иконка) во Flash-памяти
const uint8_t compressed_icon[] PROGMEM = {
0x85, 0xAA, // Повторить 0xAA 5 раз
0x04, 0x11, 0x22, 0x33, 0x44, // Скопировать 4 литерала
0x83, 0x55 // Повторить 0x55 3 раза
};
/**
* Декомпрессия потока RLE (PackBits) напрямую в периферию
* @param src - указатель на сжатые данные в PROGMEM
* @param src_len - размер сжатого массива
* @param dest_callback - функция-колбэк для отправки восстановленного байта (например, в SPI дисплея)
*/
void rle_decompress_p(const uint8_t* src, uint16_t src_len, void (*dest_callback)(uint8_t)) {
uint16_t i = 0;
while (i < src_len) {
// Читаем управляющий байт-маркер из Flash
uint8_t marker = pgm_read_byte(&src[i++]);
if (marker & 0x80) { // Если старший бит равен 1 — это серия повторов
uint8_t count = (marker & 0x7F); // Выделяем количество повторов
uint8_t value = pgm_read_byte(&src[i++]); // Читаем значение для повтора
while (count--) {
dest_callback(value); // Отправляем данные в порт/дисплей
}
} else { // Если старший бит равен 0 — это блок литералов
uint8_t count = marker; // Количество литералов
while (count--) {
uint8_t value = pgm_read_byte(&src[i++]);
dest_callback(value); // Копируем напрямую
}
}
}
}
Часть 3. Кодирование Хаффмана: Статистическое изящество
Если простой алгоритм RLE (Run-Length Encoding) прямолинеен, как кувалда, и работает только на длинных монотонных повторениях, то алгоритм Хаффмана — это тонкий математический инструмент. Он апеллирует к понятию информационной энтропии Клода Шеннона и выжимает максимум пользы из статистической структуры ваших данных.
Этот метод был предложен Дэвидом Хаффманом в 1951 году во время обучения в MIT в качестве альтернативы курсовой работе. С тех пор кодирование Хаффмана признано оптимальным префиксным кодом, позволяющим сжимать стационарные источники без потерь с максимально возможной теоретической эффективностью.
Для инженеров на этот алгоритм представляет колоссальный интерес: он позволяет упаковать текстовые строки локализации интерфейса, таблицы калибровки или файлы конфигурации, уменьшив их физический размер во Flash-памяти программ на 40–70%, не расходуя при этом ни одного байта SRAM на декодирование.
А. Идея: Длина кода пропорциональна вероятности
А. Теоретический базис: Префиксное свойство и избыточность
Стандартные текстовые кодировки (ASCII, UTF-8 для латиницы) используют фиксированную разрядность — ровно 8 бит на один символ. Это крайне расточительно. В любом осмысленном тексте частота появления разных символов неодинакова.
Например, в русском тексте буква «О» встречается в среднем в 11% случаев, тогда как буква «Ф» — всего в 0.2%. Заставляя микроконтроллер хранить обе эти буквы в виде 8-битных кодов, мы нерационально расходуем память.
Идея Хаффмана проста: сделать длину кода символа обратно пропорциональной частоте его появления.
[Символ 'О'] (Частый) ───► Код: 0b0 (Всего 1 бит!)
[Символ 'А'] (Средний) ───► Код: 0b10 (Всего 2 бита!)
[Символ 'Ф'] (Редкий) ───► Код: 0b1101 (Аж 4 бита!)
Проблема неоднозначности (Почему важен префиксный код)
Если буквы имеют разную длину (например, ‘О’ = 0, ‘А’ = 1, ‘Ф’ = 01), то при получении битовой последовательности 010 декодер зайдет в тупик. Что это?
- Это «О» (
0), затем «А» (1), затем снова «О(0`)? - Или это «Ф» (
01) и «О» (0)?
Чтобы избежать этой коллизии, коды Хаффмана обладают префиксным свойством: ни один из полученных кодов символов не является префиксом (началом) другого кода. Это позволяет декодировать непрерывный поток бит однозначно, двигаясь по битам слева направо без всяких разделителей.
Б. Математика на пальцах: Построение дерева Хаффмана
Давайте наглядным примером разберем, как создается это сжатие. Допустим, нам нужно упаковать слово «КОЛОКОЛ» (7 символов).
- Считаем частоту появления каждого символа:
- «О»: 3 раза
- «К»: 2 раза
- «Л»: 2 раза
- Создаем список свободных узлов (листьев) и сортируем их по возрастанию частоты:
[К: 2],[Л: 2],[О: 3]
- Строим дерево (снизу вверх):
- Берем два узла с наименьшей частотой:
К(2)иЛ(2). - Объединяем их в родительский узел
Ветка_1с суммарной частотой . - Узлу
Кприсваиваем левую ветвь (бит0), узлуЛ— правую (бит1).
- Берем два узла с наименьшей частотой:
* Наш список узлов теперь выглядит так: `[О: 3]`, `[Ветка_1: 4]`.
* Снова берем два наименьших узла и объединяем их в `Корень` с частотой 3 + 4 = 7.
* Ветви к `О` присваиваем `0`, к `Ветка_1` — `1`.
- Считываем полученные префиксные коды от корня к листьям:
- «О» =
0(1 бит) - «К» =
10(2 бита) - «Л» =
11(2 бита)
- «О» =
Оценка эффективности сжатия:
- Исходный размер (ASCII): .
- Сжатый битовый поток («КОЛОКОЛ»):
К(10) +О(0) +Л(11) +О(0) +К(10) +О(0) +Л(11) =10011010011.- Размер сжатого потока: 11 бит!
- Степень сжатия: 80.3% экономии места во Flash-памяти!
В. Аппаратная реальность: Обходим ограничения 8-битного ядра
В учебниках по Computer Science алгоритм декодирования дерева Хаффмана обычно реализуется через рекурсивный обход динамического дерева с использованием указателей:
c
// Типичный пример "школьного" кода, который убьет ваш AVR
struct Node {
struct Node* left;
struct Node* right;
char symbol;
};
Почему этот подход — самоубийство для микроконтроллера?
- Дребезг стека (Stack Overflow): Рекурсивный вызов функции забивает стек адресами возврата. При глубине дерева более 10–12 уровней стек 8-битного контроллера встретится с кучей, вызвав немедленный крах системы (Hard Fault).
- Память под указатели: На 8-битном AVR указатель (
void*) занимает 2 байта. Если в дереве 256 символов, то нам потребуется только под хранение адресов переходов! Это вся ОЗУ базовой ATmega328P.
Решение АРК: Плоское индексированное дерево (Flat Tree)
Мы отказываемся от рекурсии и указателей. Дерево Хаффмана сериализуется в плоский массив структур, хранящийся строго во Flash-памяти (PROGMEM).
Каждый узел дерева описывается парой знаковых 8-битных целых чисел (int8_t). Если размер алфавита превышает 127 уникальных символов, мы переходим на 16-битные индексы (int16_t).
c
// Каждый узел дерева Хаффмана — это пара индексов
typedef struct {
int8_t left; // Если индекс >= 0: это номер следующего узла. Если < 0: это лист (символ = ~left)
int8_t right; // Аналогично для правой ветки
} HuffmanNode_t;
Магия знакового бита:
- Если индекс положительный (или равен 0) — это ссылка на другой узел в нашем массиве. Например,
left = 5означает, что при получении бита0мы должны перейти к элементуtree[5]. - Если индекс отрицательный — мы достигли «листа» дерева (конечного символа). Физический ASCII-код символа извлекается с помощью простой и быстрой побитовой инверсии (оператор
~в Си).
Пример: Мы получили отрицательный индекс -66 (в шестнадцатеричном виде для знакового int8_t это 0xBE). Выполняем побитовое отрицание: ~(-66) (инвертируем все биты значения). Получаем 65 — это чистый ASCII-код буквы ‘A’. Операция выполняется процессором AVR за 1 такт!
Г. AVR-оптимизированный Си-декодер Хаффмана (nk9.ru):
Этот алгоритм декодирует поток сжатых бит, читая их по одному. Ему требуется всего 4 байта SRAM для отслеживания текущего состояния! Для примера возьмем ОАФ.
#<strong>include</strong> <avr/pgmspace.h>
#<strong>include</strong> <stdbool.h>
<em>// Пример компактного дерева Хаффмана во Flash-памяти (для символов 'О', 'А', 'Ф')</em>
const HuffmanNode_t huffman_tree[] PROGMEM = {
{ -112, 1 }, <em>// Узел 0: левый потомок - лист (~(-112)) = 'O', правый - Узел 1</em>
{ -98, -103 } <em>// Узел 1: левый потомок - лист (~(-98)) = 'A', правый - лист (~(-103)) = 'Ф'</em>
};
<em>// Сжатый битовый поток: строка "ОАФ" -> биты: 0 (O), 10 (A), 11 (Ф) -> 0b01011000 (упаковано в байт)</em>
const uint8_t compressed_data[] PROGMEM = { 0x58 };
<em>/**
* Декодирование битового потока Хаффмана
* @param tree - указатель на дерево в PROGMEM
* @param src - указатель на сжатые байты в PROGMEM
* @param total_symbols - сколько символов нужно извлечь
* @param dest_callback - функция отправки символа в интерфейс
*/</em>
void <strong>huffman_decompress_p</strong>(const HuffmanNode_t* tree, const uint8_t* src, uint16_t total_symbols, void (*dest_callback)(char)) {
uint16_t src_byte_index = 0;
uint8_t current_byte = 0;
uint8_t bit_mask = 0; <em>// Маска для чтения бит (0 означает, что нужно прочитать новый байт)</em>
uint16_t decoded_count = 0;
<strong>while</strong> (decoded_count < total_symbols) {
int8_t current_node_index = 0; <em>// Начинаем всегда с корня (узел 0)</em>
<em>// Спускаемся по дереву, пока не достигнем листа (символа)</em>
<strong>while</strong> (current_node_index >= 0) {
<em>// Если маска пуста — читаем следующий байт из Flash</em>
<strong>if</strong> (bit_mask == 0) {
current_byte = pgm_read_byte(&src[src_byte_index++]);
bit_mask = 0x80; <em>// Начинаем со старшего бита</em>
}
<em>// Выделяем текущий бит</em>
bool bit = (current_byte & bit_mask) != 0;
bit_mask >>= 1; <em>// Сдвигаем маску на следующий бит</em>
<em>// Читаем текущий узел дерева из Flash</em>
int8_t left_child = (int8_t)pgm_read_byte(&(tree[current_node_index].left));
int8_t right_child = (int8_t)pgm_read_byte(&(tree[current_node_index].right));
<em>// Переходим по ветке в зависимости от бита</em>
<strong>if</strong> (bit == 0) {
current_node_index = left_child;
} <strong>else</strong> {
current_node_index = right_child;
}
}
<em>// Мы достигли листа (значение отрицательное). Восстанавливаем символ</em>
char symbol = (char)(~current_node_index);
dest_callback(symbol); <em>// Отправляем символ получателю</em>
decoded_count++;
}
}
Д. Канонические коды Хаффмана: Экономим Flash на 100%
Для системных архитекторов на nk9.ru, ведущих борьбу за каждый свободный байт Flash-памяти, существует еще более изящное решение — Канонические коды Хаффмана (Canonical Huffman Codes).
В классическом кодировании нам необходимо передавать и хранить структуру дерева (массив связей). В каноническом кодировании мы используем жесткое математическое правило: коды одинаковой длины распределяются строго последовательно в лексикографическом (алфавитном) порядке.
Как это работает:
Вместо хранения сложной структуры дерева на МК записывается всего две небольшие таблицы:
- Список символов, отсортированных по длине их кода.
- Таблица первого числового значения кода для каждой длины (обычно массив из 16 элементов, если максимальная глубина кода равна 16 битам).
[Битовый поток] ──► Считываем биты ──► Сравниваем значение с диапазоном для длины N
│
▼
Вычисляем индекс в плоском массиве символов
(0 байт на структуру дерева!)
При декодировании канонического кода нам не нужно блуждать по узлам дерева в памяти. Мы просто считываем биты в числовой буфер, пока его значение не попадет в диапазон кодов соответствующей длины, а затем вычисляем индекс символа по формуле смещения. Это экономит до 100% памяти, выделяемой под структуру дерева.
И. Битовый стриминг: Выжимаем скорость из 8 бит
При написании декомпрессора Хаффмана критически важно оптимизировать чтение отдельных бит из байтового потока.
8-битный микроконтроллер AVR не имеет аппаратного модуля сдвига на произвольное количество бит за один такт (barrel shifter). Команда data >>= shift на ассемблере AVR разворачивается в цикл из инструкций LSR (Logical Shift Right).
Поэтому классический код чтения произвольного бита по индексу:
c
// Ужасный код: медленный сдвиг на произвольную величину
bool bit = (compressed_bytes[index / 8] >> (7 - (index % 8))) & 0x01;
…будет нещадно тормозить процессор.
Оптимальный битовый стример от АРК:
Мы используем скользящую маску bit_mask, которая на каждом шаге сдвигается строго на 1 бит вправо. Сдвиг на единицу выполняется процессором за 1 такт.
c
// Максимально быстрый разбор бит на AVR
if (bit_mask == 0) {
current_byte = pgm_read_byte(&src[src_byte_index++]); // Читаем байт из Flash
bit_mask = 0x80; // Сбрасываем маску на старший бит (0b10000000)
}
bool bit = (current_byte & bit_mask) != 0; // Наложение маски — 1 такт
bit_mask >>= 1; // Сдвиг маски на 1 бит вправо — 1 такт
Этот подход обеспечивает максимально возможную скорость потоковой декомпрессии данных. Процессор успевает разбирать биты со скоростью, достаточной для того, чтобы на лету скармливать декодированные символы в UART или SPI-дисплей без просадки частоты кадров.
Итог: Кодирование Хаффмана — это демонстрация превосходства интеллекта над грубой вычислительной силой. Понимая эти принципы, вы сможете создавать интерфейсы и системы локализации устройств на nk9.ru, превосходящие по эффективности любые стандартные решения.
Часть 4. Наставления АРК по сжатию данных в микроконтроллерах
Упаковка ресурсов — это мощный инструмент, но он требует от инженера безупречного понимания архитектуры микроконтроллера. Члены Ассоциации АРК рекомендуют придерживаться следующих правил при проектировании систем компрессии:
1. Заповедь «Борьбы с медленными сдвигами»
8-битные процессоры AVR (типа ATmega328P или ATmega2560) не имеют аппаратного barrel-shifter’а (блока сдвига на произвольное количество бит за один такт). Инструкция сдвига >> или << на бит на AVR выполняется в цикле и занимает ровно тактов процессора.
- Инженерный вывод: В декомпрессоре Хаффмана старайтесь избегать сложных математических манипуляций с битовыми масками. Конструкция
bit_mask >>= 1— это самый быстрый способ последовательного обхода бит, так как сдвиг происходит ровно на 1 бит за такт.
2. Заповедь «Гибридного подхода»
Не пытайтесь использовать один алгоритм для всех типов данных.
- Для шрифтов и иконок интерфейса используйте связку: сначала битовая карта упаковывается в RLE, а затем полученный поток байт сжимается Хаффманом. Это дает ультимативное сжатие до 75–80% от исходного объема.
- Для текстовых меню и локализаций (где нет повторяющихся байт, но частоты букв различны) используйте исключительно чистый алгоритм Хаффмана.
3. Заповедь «Проверки на переполнение буфера»
Поскольку декомпрессия происходит «на лету», у вас часто нет возможности проверить целостность всего массива перед началом вывода.
- Если во время передачи данных (например, из-за помехи на шине внешней Flash-памяти) битовый поток Хаффмана исказится, декомпрессор «потеряет» префиксные коды и начнет выдавать бесконечный поток мусора.
- Решение: Всегда жестко ограничивайте цикл декодирования счетчиком количества ожидаемых символов (
total_symbolsв нашем коде) или внедряйте маркер конца потока (EOF) в дерево Хаффмана.
4. Заповедь «Отказа от динамики»
Категорически запрещено использовать malloc для динамического построения дерева Хаффмана в ОЗУ во время работы устройства. Дерево должно быть жестко просчитано на этапе компиляции вашей прошивки и записано во Flash-память в виде статического массива структур констант.
Заключение
Использование сжатия данных — это качественный маркер профессионального разработчика встраиваемых систем. Понимание того, как с помощью RLE или алгоритма Хаффмана упаковать тяжелую графику и многоязычные меню в скромную память дешевого 8-битного контроллера, избавляет вас от необходимости усложнять плату, ставить дорогие микросхемы внешней памяти или переходить на избыточные 32-битные платформы.
Учитесь уважать память вашего контроллера, используйте изящные математические решения на nk9.ru и пусть ваши проекты будут безупречно оптимизированы!
Статья подготовлена инженерным отделом портала nk9.ru. А какие методы сжатия используете вы в своих проектах на микроконтроллерах? Приходилось ли вам вручную писать парсеры битовых потоков? Делитесь своим опытом в комментариях!
Об авторе
