Сжатие графики при помощи алгоритма LZ4

Содержание

1. Введение

2. Постановка задачи

   • Дисплей

   • Процесс отрисовки изображений

   • Память

3. Выбор алгоритма сжатия

4. Как работает LZ4?

   • LZ4 Block format

   • LZ4 Frame format

5. Так сжимались данные

   • Какой формат выбрать?

   • Разработка протокола хранения данных

6. Результаты

Введение

Привет! Меня зовут Александр Крестинин, я разработчик встроенного ПО в компании Whoosh. Мы в embedded-команде не только переливаем биты из одного регистра в другой, но и решаем разные бизнес-задачи. Иногда попадаются головоломки. 

Однажды мы подумали, что было бы здорово выводить на экраны самокатов анимации и изображения — показывать инструкции, как пользоваться сервисом, как начать и закончить поездку, и чтобы запускать DOOM.

Зачем?

1) Сделать комфортнее. Удобно видеть инструкции на большом и ярком экране перед глазами, а не нырять за ними в приложение на смартфоне. 

2) Сделать безопаснее. Пользователь меньше отвлекается на телефон, крепче держится за самокат и внимательнее смотрит на всё, что вокруг.

3) Почти у всех привычных устройств уже есть экраны, которые выводят пользователям видео и картинки, а почему бы не сделать то же самое на самокате?

Но тут возникает проблема. Микроконтроллер крайне ограничен в памяти и вычислительных ресурсах. Самая простая анимация занимает чрезмерно много места. А если внедрить в отрисовку алгоритмы сжатия, то вычислительная нагрузка увеличится и анимация будет сильно лагать.

Расскажу, как мы нашли решение этой задачи.

Постановка задачи

Итак, что мы имеем:

• Светодиодный дисплей с разрешением 48 х 24;

• Микроконтроллер, который занят множеством других задач;

• 1 Mб внутренней Flash-памяти контроллера.

Разберёмся чуть подробнее в железе, с которым придётся работать.

Дисплей

С лицевой стороны дисплей представляет собой монохромную светодиодную матрицу
48 х 24 и схематично может быть представлен так:

Обычно такие матрицы представляются как двумерный массив (в нашем случае [24, 48]): начало — в левом верхнем углу, нумерация столбцов — слева направо, а нумерация строк — сверху вниз.

NOTE: В левом и правом нижнем углу дисплея отсутствует некоторое количество светодиодов. Это обусловлено конструктивными особенностями и никак не влияет на программную реализацию.

С обратной стороны дисплея расположены 72 последовательно соединённых сдвиговых регистра. Каждая пара микросхем отвечает за соответствующие 32 светодиода. Соединение между ними будем называть сдвиговой парой. Передача данных по такой паре показана на рисунке:

Все сдвиговые пары соединены друг с другом последовательно, начиная со входа шины SPI:

NOTE: Вход SPI на схеме расположен зеркально, потому что сдвиговые регистры находятся на обратной стороне платы.

Изображения передаются от контроллера на дисплей по шине SPI с использованием технологии Direct Memory Access (DMA) — с её помощью можно передавать данные к периферии без участия микроконтроллера.

Как видно из рисунков 2 и 3, индексы массива DMA, которые будут сдвигаться регистрами по дисплею, из-за особенностей конструкции абсолютно не соответствуют индексам светодиодов в контексте светодиодной матрицы как двумерного массива. Следовательно, нельзя просто взять и заполнить массив байтами изображения для отправки по DMA. Нужно сопоставить представление дисплея в коде и железную реальность.

Как устроена отрисовка изображений

Перед тем как продолжить, введём некоторые определения.

Пиксель — наименьшая единица информации об изображении, которой оперирует графическое ядро. Размер — 1 байт.

Светодиод — наименьшая единица светодиодной матрицы дисплея. Кодируется 1 битом информации и может находиться только в одном из двух состояний: включён или выключен.

AppBuff — буфер яркостей пикселей. Размер = 48 * 24 = 1152 байта.

DMABuff — буфер состояний светодиодов. Размер = 48 * 24 = 1152 бита.

GRAY_SCALE — количество оттенков серого, которое может отобразить наш дисплей. Мы приняли его равным 16, но эту величину можно настраивать.

Изначально мы попытались решить проблему сопоставления индексов AppBuff и DMABuff алгоритмически, но это изрядно увеличивало вычислительную нагрузку на отрисовку. Тогда мы создали карту индексов, которая соединяет понимание светодиодного дисплея как двумерного массива с фактической железной реализацией.

Способ создания такой карты покажу на примере.

Как видно из рисунка, порядок передачи данных по 32 светодиодам будет происходить при помощи DMA с элементами [0..31] и показан на рисунке синим цветом. Тогда, если мы хотим установить яркость элемента [0,0] нашей матрицы (показано красным шрифтом), надо записать значение в элемент DMA буфера с индексом 24. Для элемента [0,1] — индекс 25 и так далее.

Карта индексов для этого примера выглядит так:

u8 IdxMap[32] = { 24, 25, 26, 27, 28, 29, 30, 31,
                  23, 22, 21, 20, 19, 18, 17, 16,
                  8,  9,  10, 11, 12, 13, 14, 15,
                  7,  6,  5,  4,  3,  2,  1,  0}

Так можно построить таблицу индексов и для всего дисплея. Всё отлично, кроме одного — памяти. Теперь, помимо IdxMap[1152], необходимо использовать массив DisplayBuffTmp[1152]. Последний нужен для выполнения операции последовательной группировки значений по новым индексам, так, как при их объединении для буфера DMA нужно 8 байт объединить в один, в зависимости от установленного GRAY_SCALE (подробнее об этом позже).

for(u32 pix = 0; pix < DISPLAY_PIXEL_NUM; pix++)
		DisplayBuffTmp[IndexesMap[pix]] = AppBuff[pix];

То есть идём последовательно по AppBuff, а в DisplayBuffTmp меняем значения согласно новым индексам из IdxMap.

И именно DisplayBuffTmp мы загоняем в функцию конвертации GRAY_SCALE, а полученное выводим на дисплей:

Display_BuffConvert((u8*)DisplayBuffTmp, (u8*)DMABuff);
Pl_Display_Send((u8*)DMABuff, DISPLAY_OUT_BUFF_SIZE, 0); 

На подготовку данных, конвертацию и запуск в DMA уходит 731 uS (все измерения тут и далее сделаны на флаге -O0)

for(u32 pix = 0; pix < DISPLAY_PIXEL_NUM; pix++)
    DisplayBuffTmp[IdxMap[pix]] = AppBuff[pix];

Display_BuffConvert((u8*)DisplayBuffTmp, (u8*)DMABuff);
Pl_Display_Send((u8*)DMABuff, DISPLAY_OUT_BUFF_SIZE, 0);

Хотелось бы избавиться от буфера DisplayBuffTmp, так как он служит просто промежуточным звеном.

Для этого мы создали таблицу реверсивных индексов, чтобы получить уже сгруппированные индексы, где 8 пикселей будут соседними для объединения и подготовки к выводу в DMA. Массив создан отдельно и захардкожен во флеш-память по следующему правилу:

u8 IdxMapReversed[DISPLAY_PIXEL_NUM];

for(u32 pix = 0; pix < DISPLAY_PIXEL_NUM; pix++)
		IdxMapReversed[IdxMap[pix]] = pix;

Использование таблицы реверсивных индексов позволяет заменить цикл

for(u32 pix = 0; pix < DISPLAY_PIXEL_NUM; pix++)
		DisplayBuffTmp[IdxMap[pix]] = AppBuff[pix];

на

for(u32 pix = 0; pix < DISPLAY_PIXEL_NUM; pix++)
			DisplayBuffTmp[pix] = AppBuff[IdxMapReversed[pix]]; 

Теперь DisplayBuffTmp заполняется последовательно. Проверяем — да, всё работает.

for(u32 pix = 0; pix < DISPLAY_PIXEL_NUM; pix++)
    DisplayBuffTmp[pix] = AppBuff[IdxMapReversed[pix]];

Display_BuffConvert((u8*)DisplayBuffTmp, (u8*)DMABuff);
Pl_Display_Send((u8*)DMABuff, DISPLAY_OUT_BUFF_SIZE, 0);

А теперь переписываем функцию конвертации GRAY_SCALE с использованием u8 tmpIn[DISPLAY_PIXEL_BITS]:

#define DISPLAY_GRAYSCALE     16
#define DISPLAY_PIXEL_BITS    8
#define DISPLAY_DIGIT_WEIGHT  ((1 << DISPLAY_M_MONO_PIXEL_BITS) / DISPLAY_M_MONO_GRAYSCALE)

static void Display_BuffConvert(u8* pIn, u8* pOut)
{
	for(u32 bytePos = 0, byteOffset = 0;
		bytePos < DISPLAY_OUT_BUFF_SIZE;
		bytePos++, byteOffset += DISPLAY_PIXEL_BITS)
	{
		u8 tmpIn[DISPLAY_PIXEL_BITS];
		for(u32 pixOffset = 0; pixOffset < DISPLAY_PIXEL_BITS; pixOffset++)
			tmpIn[pixOffset] = pIn[IdxMapReversed[byteOffset + pixOffset]];

		pOut[bytePos] = 0x00;
		for(u32 pix = 0; pix < DISPLAY_PIXEL_BITS; pix++)
			if(tmpIn[pix] / DISPLAY_DIGIT_WEIGHT > GrayscaleFrameCnt)
				pOut[bytePos] |= 0x01 << pix;
	}
} 

Проверяем, что получилось:

Display_BuffConvert((u8*)AppBuff, (u8*)DMABuff);
Pl_Display_Send((u8*)DMABuff, DISPLAY_OUT_BUFF_SIZE, 0);

739 uS — это практически тот же самый перформанс, что был в первой попытке оптимизации. Только теперь удалось полностью отказаться от DisplayBuffTmp.

Так, отрисовку кадра можно представить в виде схемы:

1) Графическое ядро заполняет AppBuff данными о яркости пикселей изображения.

2) Так как у светодиодов только два состояния — включены или выключены, то для контроля их яркости имитируем ШИМ-сигнал из кадров. Изображение разбивается на GRAY_SCALE (16), количество подкадров, и сжимается, преобразуя 8 байт яркости пикселей в 1 байт состояния светодиодов, где каждый бит обозначает состояние одного из восьми светодиодов.

3) Подкадр переводится в DMABuff через таблицу индексов.

4) Массив бит DMABuff передаётся через SPI на дисплей и цикл повторяется.

Память

Для тех, кто не связан с разработкой ПО для микроконтроллеров, может быть неочевидна проблема хранения изображений с максимальным разрешением 48 х 24 пикселя.

Так как наш дисплей одноцветный, то яркость каждого пикселя может иметь значение от 0 до 255 и храниться в одном байте. Мы решили кодировать яркость пикселей именно байтом, чтобы использовать больше оттенков в будущем. Максимальный размер изображения составляет 48 х 24 = 1152 байта, что чуть больше 1 Кб. Это только лишь на одно чёрно-белое изображение! Если же мы хотим выводить анимацию (по сути, это куча изображений) в 60 кадрах в секунду (FPS), то для одной секунды потребуется выделить 60 x 1152 = 67,5 Кб. А это почти 20% всей оперативной памяти и около 6,6% всей энергонезависимой Flash-памяти микроконтроллера. Да, и это без учёта буфера в 1152 байта для работы графического ядра и буфера DMA для отправки данных.

NOTE: Теоретически, человеческому глазу достаточно и 24 кадров в секунду. Но мы проверили отображение анимаций на таком FPS и обнаружили, что дисплей очень сильно мерцает. Поэтому решили ориентироваться на 60 кадров в секунду.

Мы сложили размеры всех нужных нам изображений и анимаций. Обнаружили, что они не помещаются в свободное пространство внутренней Flash-памяти контроллера. А ведь мы захотим добавлять ещё...

Можно попробовать взять SD-карту. Она дешёвая, и у неё большой объём памяти. Проблема в том, что нам нужно в runtime считывать изображения для отрисовки их на дисплее. В этом случае критически важна скорость считывания данных из памяти. У нас она составила 0,96 МБ/c. Считывание одного изображения занимало около 1,14 мс. С этим можно жить, но всё же хотелось иметь запас по скорости работы системы, поэтому мы отказались от SD-карты в пользу Serial Flash.

Что же делать? Можно сжимать изображения для экономии пространства. Итак, сформулируем задачу.

1. Внедрить алгоритм сжатия без потерь информации, применение которого не увеличит время отрисовки кадра выше 16 мс (приблизительно 60 FPS);

2. Написать скрипт для сжатия файлов на ПК перед их загрузкой во Flash-память;

3. Разработать протокол хранения сжатых данных в Serial Flash;

4. Написать алгоритм runtime-разархивирования изображений на МК.

Звучит неплохо, но насколько глубока кроличья нора…

Выбор алгоритма сжатия

Есть множество архиваторов и методик, но чтобы выбрать решение, определим требования:

• сжатие без потери информации;

• любая скорость сжатия;

• максимально высокая скорость разжатия.

Почему так? Скорость сжатия для нас не важна, этот процесс будет выполняться редко и на ПК с огромным количеством вычислительных ресурсов. А вот требования к скорости разжатия у нас крайне высокие. Мы внедряем разархивирование изображения в процесс отрисовки — любые задержки приведут к сильному падению FPS и ухудшат опыт пользователей.

Мы рассмотрели несколько популярных алгоритмов сжатия:

• Run-length encoding (RLE) — простейший алгоритм, который часто применяется для компрессии монохромных изображений;

• LZ4 — алгоритм сжатия без потерь, он отличается крайне высокой скоростью декомпрессии данных при удовлетворительной степени сжатия;

• DEFLATE (zlib) — алгоритм, комбинирующий в себе LZ77 и кодирование Хаффмана. Тоже отличается очень высокой степенью сжатия данных;

• Lempel-Ziv_Markov chain algorithm (LZMA) — алгоритм, основанный на использовании словаря последовательных повторений данных для достижения высокой степени сжатия.

Провели бенчмарк-тесты всех вариантов. Результаты:

Несмотря на подходящие условия для применения RLE, он справился хуже LZ4 как по степени сжатия, так и по скорости. Скорее всего, это обусловлено чередованием значений яркости пикселей, что не позволяло сжать данные сильнее. А в случае использования цветных изображений ситуация будет только хуже. LZMA был на втором месте по степени сжатия, но не справился с требованием по скорости декомпрессии данных.

Zlib оказался лучшим решением для экономии памяти, но по скорости декомпрессии данных уступил LZ4 более чем в 2,5 раза.

Наиболее подходящим решением стал LZ4. К тому же он независим от типа CPU, операционной системы, файловой системы и набора символов. А если мы сравним скорости компрессии и декомпрессии, то увидим, что результаты подтверждаются и при сравнении на другом наборе данных:

Подробнее можно почитать тут и тут.

Иногда нам требуется сжатие и других данных на IoT. Например, можно хранить .map-файлы в сжатом виде. Об этом мы упоминали в прошлой статье про IoT-Geofencing. Подойдёт ли LZ4 для этой задачи? Проведём benchmark-тестирование.

Здесь LZ4 тоже уступает в степени сжатия данных, но выигрывает по скорости компрессии и декомпрессии.

Ещё один плюс в том, что сжатие изображений и анимаций позволит нам снизить накладные расходы на OTA-обновление графики.

Судя по всему, LZ4 полностью нам подходит. Разберёмся, что там у него под капотом.

Как работает LZ4?

Очень упрощённо: LZ4 находит повторяющиеся последовательности данных и сжимает их особым образом (под капотом всё, естественно, сильно сложнее). В нём реализовано два интересующих нас формата сжатия данных: Block format и Frame format.

Block format

Все данные, сжатые LZ4, представляют собой блоки определённой структуры. Упрощённый вид LZ4 Block:

• Sequence — последовательность, представляющая собой набор литералов, за которыми следует описание копируемых данных.

• Token — однобайтовое поле с данными о количестве литералов и количестве байт, описывающих длину копируемого сообщения.

• Opt. len. bytes — опциональные байты длины, описывают количество литералов, выходящее за пределы описания в Token;

• Literal 1 ... N — собственно, литералы, где N — количество литералов.

• Match copy — поле с данными о том, какие байты информации считать с предыдущего блока.

Каждый блок состоит из последовательностей. Последовательность — это комбинация токена, литералов и поля для описания данных, которые требуется скопировать из предыдущего буфера.

Токен имеет размер в один байт и по смыслу разделён на два 4-битных поля. Первое поле описывает количество литералов и может принимать значения от 0 до 15. В случае, когда литералов больше чем 15, после токена начинают добавляться опциональные байты длины, которые могут принимать значения от 0 до 255. Эти байты будут добавляться до тех пор, пока сумма их значений не сможет описать количество литералов.

Весьма интересна структура поля Match copy. В нём содержится offset, который показывает откуда нужно скопировать байты относительно текущей позиции. Это поле может принимать значения от 0 до 65535, а расчёт позиции производится как current position — offset.

Чтобы узнать размер копируемого участка, используется второе 4-битное поле байта Token. По аналогии с первым, оно принимает значения от 0 до 15 и, в случае нехватки, дополняется байтами в оставшейся части Match copy.

У нас нет задачи углубиться в тонкости работы LZ4. Если читателю интересна эта тема, то вот подробное описание спецификации Block. Главное, что нужно запомнить про Block format:

• LZ4 сжимает данные в блоки;

• каждый блок ориентируется на информацию из прошлого вывода;

• несжимаемые данные могут увеличиваться в размере после сжатия LZ4.

Frame format

Общая структура LZ4 Frame format выглядит так:

• Magic Number — любое магическое число в формате Little endian;

• Frame Descriptor — блок, описывающий содержание Frame длиной от 3 до 15 байт;

• Data Blocks — блоки сжатых данных в Block format;

• End Mark — последовательность блоков данных считается завершённой, когда после последнего блока идёт 32-битное значение 0x00000000;

• Checksum — контрольная сумма для проверки того, что данные декодированы верно.

Как мы помним, блоки данных при разжатии ориентируются на предыдущую информацию. Frame format описывает единый непрерывный сжатый набор данных. Например, один файл. Если мы захотим добавить данные к файлу, то нужно заново сжать его уже с новым содержимым. Или же отдельно сжать дополнительную информацию и присоединить её к предыдущей в виде отдельного Frame. Советую применять именно эту спецификацию сжатия из-за её кроссплатформенности и удобства. Узнать больше о внутренней работе Frame format можно тут.

Теперь у нас есть теоретическое представление о работе LZ4. Но, как известно, практика — критерий истины.

Так сжимались данные

Какой формат выбрать?

В описании Block-спецификации утверждается, что можно достичь степени сжатия в 250 раз. Эти цифры впечатляют, но нужно понять, насколько алгоритм способен сжать именно наши данные? Достичь такой степени сжатия может помешать размер изображений и метаданные, нужные для работы каждого из форматов.

Проверим формат в деле на наших изображениях и анимациях при различных настройках и спецификациях LZ4. Для этого применим скрипт с использованием python-библиотеки для алгоритма LZ4:

import io
import os
import lz4.block
import lz4.frame
import numpy as np
import pandas as pd
from PIL import Image


DATA_SRC_PATH = 'data/'


def get_data(path: str) -> list:
    images_list = []
    files = os.listdir(os.getcwd() + '/' + path)
    for file in files:
        if '.bmp' in file or '.png' in file:
            images_list.append(file)
        else:
            print('terr: file is not .bmp or .png')
            continue
    return images_list


def compress_data(data: list) -> list:
    compressed_data = []
    for data_file in data:
        image = Image.open(DATA_SRC_PATH + dataFile)

        image = image.convert('RGB')
        image_line_rgb = np.array(image).flatten().tolist()
        image_red_ch = []
        for idx, pix_ch in enumerate(image_line_rgb):
            if idx % 3 == 0:
                image_red_ch.append(pix_ch)

        out_io = io.BytesIO()
        out_io.write(bytes(image_red_ch))

        image_name = data_file.split('.')[0]
        original = len(out_io.getvalue())
        compressed_block = len(lz4.block.compress(out_io.getvalue()))
        compressed_frame = len(lz4.frame.compress(out_io.getvalue()))
        compressed_data.append(
            [image_name, original, compressed_block,
             round(original / compressed_block, 2),
             compressed_frame, round(original / compressed_frame, 2)])
    return compressed_data


if __name__ == '__main__':
    data = get_data(DATA_SRC_PATH)
    compressed_data = compress_data(data)
    df = pd.DataFrame(compressed_data, columns=DATA_LIST)
    df.to_csv('data.csv')

Что в результате? Эти данные дают представление об эффективности различных форматов алгоритма LZ4:

При уменьшении размера сжимаемых данных степень сжатия уменьшается вплоть до того, что результат превышает по размеру исходное изображение. Это связано с тем, что к несжатым данным добавляются метаданные LZ4. Ещё интересный эффект: несмотря на размер в 1152 байта, изображения могут сжиматься с разной эффективностью. Это связано опять же с количеством найденных повторяющихся паттернов.

Итого:

1. на всех анимациях и изображениях спецификация Block показала себя лучше, чем спецификация Frame: степень сжатия была выше;

2. на очень маленьких изображениях применение любой из спецификаций привело к увеличению размера файла. Это произошло из-за добавления метаданных алгоритма к несжатому содержимому.

Разработка протокола хранения данных

Теперь мы понимаем как сжимать данные. А как их хранить? Для успешной декомпрессии изображения, LZ4 необходимо передать полноценный блок или фрейм данных. На этапе разархивации мы должны знать размер блока и то, что в нём зашифровано. А если мы имеем дело с анимацией, то ещё должны понимать, сколько там кадров и где какой кадр находится.

Если мы решим применять спецификацию Frame, то не получим доступ к отдельным изображениям из анимации. Это приведёт к ряду других проблем:

• при каждой отрисовке изображения потребуется динамически разархивировать ВСЮ анимацию;

• высокая вычислительная нагрузка и очень большая трата памяти при динамическом выделении, которая к тому же не всегда успешна.

Придётся разработать свой протокол хранения сжатых изображений и анимаций на основе спецификации Block.

Flash-память — это набор ячеек, куда записывается информация. В целях экономии мы будем хранить ВСЕ данные единым непрерывным блоком. Так как у изображений и анимаций после сжатия разный размер, то нужно сформировать такие метаданные, которые позволят «шагать» по данным и находить нужные объекты вне зависимости от их расположения во Flash.

Пример JSON-метаданных:

{
    "name": "cat",
    "type": "img",
    "comp": true,
    "widt": 32,
    "heig": 18,
    "size": 120
}  

где:

• name — уникальное строковое имя содержимого;

• type — тип содержимого: "anm" или "img";

• comp — флаг для обозначения состояния данных — сжаты или нет;

• widt — ширина исходного изображения или кадра;

• heig — высота исходного изображения или кадра;

• size — размер данных в сжатом виде.

С изображениями разобрались. Но что делать с анимациями? Для хранения анимаций разработали следующий формат, именуемый пакетом:

• Meta Data — метаданные об анимации;

• Magic Word — 4-байтное слово, определяет использование описанного пакета;

• Frame amount — 4-байтное число, описывает количество кадров в анимации;

• Offsets amount — 4-байтное число, описывает количество сдвигов;

• Compressed Data — сжатые кадры анимации;

• Offsets Data — значения сдвигов относительно начала пакета.

Поле Meta Data позволяет определить объект, с которым ведётся работа. Magic word — индикатор используемого протокола хранения и обработки и начальная точка отсчёта для обработки. Frame amount определяет количество кадров анимации в участке Compressed Data. Аналогичную роль выполняет и поле Offsets amount — оно определяет количество сдвигов относительно начала протокола, они хранятся в участке Offsets Data. Эти сдвиги точно определяют, где находится каждый из LZ4 блоков данных. В отличие от сжатых блоков данных, которые различаются друг от друга по размеру, у сдвигов фиксированный размер — 4 байта. Зная количество этих сдвигов, мы можем найти размер поля Offsets Data и сдвиг для нужного кадра.

Схематично обработка пакета выглядит так:

1. Идентификация объекта по полю Meta Data;

2. Идентификация формата пакета проверкой поля Magic Word;

3. Запись значений полей Frame amount и Offsets amount и проверка их равенства;

4. Нахождение начала поля Offsets Data путём отступления 4-х offsets amount байт от конца пакета;

5. Нахождение и считывание значения сдвигов для N-го и N+1 кадра путём отступа 4 x N байт от начала поля Offsets Data;

6. Нахождение начала и конца N-го кадра по значениям сдвигов. Считывание кадра.

Итак, все компоненты подготовлены. Осталось собрать всё воедино и посмотреть на итоговый результат. Внедрение библиотеки LZ4 в наш проект потребовало всего лишь одну обёртку:

 RET_STATE_t LZ4_Wrapper_BlockCompress(u8* pSrcBuff, u32 srcSize, u8* pDstBuff, u32 dstSize) {
	u32 maxDstSize = LZ4_compressBound(srcSize);

	if (pSrcBuff == NULL || pDstBuff == NULL || srcSize == 0 || dstSize < maxDstSize) {
		EXIT(RET_STATE_ERR_PARAM);
	}

	u32 compBytes =
		LZ4_compress_default((const char*)pSrcBuff, (char*)pDstBuff, srcSize, maxDstSize);

	return (compBytes > maxDstSize || compBytes <= 0) ? RET_STATE_ERROR : RET_STATE_SUCCESS;
}

RET_STATE_t LZ4_Wrapper_BlockDecompress(u8* pSrcBuff, u32 srcSize, u8* pDstBuff, u32 dstSize) {
	if (pSrcBuff == NULL || pDstBuff == NULL || srcSize == 0 || dstSize == 0) {
		EXIT(RET_STATE_ERR_PARAM);
	}

	s32 decompBytes =
		(s32)LZ4_decompress_safe((const char*)pSrcBuff, (char*)pDstBuff, srcSize, dstSize);

	return (decompBytes < 0 || decompBytes != dstSize) ? RET_STATE_ERROR : RET_STATE_SUCCESS;
}

А добавление декомпрессии данных в процесс отрисовки и вовсе прошло бесшовно:

	u8 outputBuff[frameSize];
	if (imageObj->Storage.IsCompressed) {
		LZ4_Wrapper_BlockDecompress(inputBuff, imageObj->Storage.Size, outputBuff, frameSize);
		imageObj->Image = (u8*)outputBuff;
	} else
		imageObj->Image = (u8*)inputBuff;

Результаты

Применив реализацию алгоритма LZ4 block, мы приступили к проверке итоговых параметров решения.

Сначала проверили размер изображений и анимаций после сжатия и добавления метаданных нашего протокола хранения.

Несмотря на добавление метаданных, видно, что LZ4 показывает высокую степень сжатия данных.

Результаты benchmark-тестирования каждого этапа отрисовки кадра показаны в таблице:

Операция конвертации и отправки изображения — самая затратная по времени. На каждый кадр надо произвести 16 таких операций. При этом декомпрессия данных при помощи LZ4 в среднем занимает лишь 87 микросекунд. Отрисовка одного изображения или кадра суммарно занимает 1,08 мс. Такой скорости отображения хватает для обеспечения стабильных 60 FPS.

Итого, после RnD и кропотливой разработки мы достигли следующих результатов:

• внедрили в сборку алгоритм сжатия изображений и анимаций LZ4;

• разработали протокол хранения анимаций и изображений во Flash-памяти;

• сделали и внедрили алгоритм runtime-разжатия данных для отрисовки на светодиодном дисплее;

• уместили все наши анимации и изображения во внутреннюю память контроллера. В целом добились сокращения используемой памяти для изображений в 2,7 раза, а для анимаций — в 5,8 раз;

Безусловно, когда у нас станет больше графики, мы не сможем хранить данные только во внутренней памяти. Но благодаря разработанному протоколу, сможем перенести хранение во внешнюю память.

Летом 2023 года в Москве мы протестировали 200 самокатов с большими дашбордами, на которые выводилась анимация с подсказками. За время исследования их взяли в аренду более 7500 пользователей Whoosh. Мы опросили их о впечатлениях от поездки: 65% отметили удобство большого дашборда с анимацией и планировали отдавать предпочтение таким самокатам. Будет ли у нашего будущего самоката именно такой экран — пока коммерческая тайна, но индустрия явно движется в сторону устройств, которые могут использоваться без смартфона. В этом сезоне для той же цели мы запустили функцию WKey — самокат стартует и завершает поездку при зажатии обоих тормозов, пользователю не надо доставать телефон.

Спасибо за внимание! Буду рад ответить на вопросы и почитать о вашем опыте использования алгоритмов сжатия.

• Был ли у вас опыт использования таких алгоритмов в embedded-проектах?

• С какими трудностями столкнулись? Как решили?

• Был ли опыт применения других спецификаций LZ4?