Компактная библиотека распаковки для встроенного использования

Question

В настоящее время мы создаем устройство для клиента, которое получит блок данных (например, 5-10 КБ) из приложения для ПК.Это немного упрощено, поэтому предположим, что данные должны передаваться и распаковываться много раз, а не только раз в год.Канал связи очень, очень медленный, поэтому мы хотели бы заранее сжать данные, передать их на устройство и позволить ему распаковать данные во внутреннюю флэш-память.Само устройство, однако, работает на микроконтроллере, который не очень быстрый и не имеет много памяти.Он имеет достаточно флэш-памяти для хранения результата и может распаковывать блок данных по мере его получения, но может не иметь достаточно оперативной памяти для хранения всех сжатых или несжатых (или даже обоих!) Блоков данных.И, конечно, у него нет операционной системы или другой роскоши.

Это означает, что нам нужен достаточно быстрый алгоритм распаковки, который не использует много памяти.Сжатие может быть медленным и уродливым, поскольку мы делаем это на стороне ПК.Код C или .NET предпочтительнее для сжатия, чтобы упростить процесс.Код распаковки должен быть на C, поскольку маловероятно, что кто-то имеет оптимизированную для ASM версию для нашего контроллера.

Мы нашли LZO, который был бы почти идеален для нас, но у него есть так называемое «бесплатное»лицензия (GPL) по умолчанию, что делает ее полностью непригодной для нашего клиента.Автор говорит, что коммерческие лицензии доступны по запросу, но, к сожалению, в настоящее время он недоступен (по нетехническим причинам, как говорят новости на его сайте).

Я нашел несколько других библиотек, включая puff.cот zlib, и мы все еще исследуем, но я подумал, что я бы попросил вашего опыта:

Какой алгоритм и / или библиотеку сжатия вы рекомендуете для встраиваемых целей, учитывая, что устройство декомпрессии действительно ограничило ресурсыа исходный код и коммерческая лицензия требуются?

Answer 1

Возможно, вы захотите проверить один из них, который не является GPL и является довольно компактной реализацией:

• fastlz - лицензия MIT, довольно простой код
• lzjb - sun CDDL, используемый в zfs для сжатия, простой и очень короткий
• liblzf - лицензия в стиле BSD, маленькая, быстрая
• lzfx - стиль BSD, на основе liblzf, маленький, быстрый

Все эти алгоритмы основаны на оригинальном алгоритме Лемпеля – Зива – Уэлча (все они имеют общий LZ) https://en.wikipedia.org/wiki/Lempel–Ziv–Welch

Answer 2

Я использовал LZSS .Я использовал код из Харухико Окумура в качестве базы.Он использует последнюю часть несжатых данных (2K) в качестве словаря.Этот код можно изменить, чтобы он не требовал временного кольцевого буфера, если у вас нет памяти.Лицензирование неясно с его сайта, но некоторые версии были выпущены с включенной строкой «Использовать, распространять и модифицировать эту программу свободно», а код используется коммерческими поставщиками.1011 *

Здесь - это реализация, основанная на том же коде, который является частью игровой библиотеки Allegro.Лицензирование Allegro - это подарочные или zlib.

Другим вариантом может быть lzfx lib, который реализует LZF.Я еще не использовал это, но это кажется хорошим.Также использует предыдущие результаты, поэтому имеет низкие требования к памяти и выпускается под лицензией BSD.

Answer 3

Одной альтернативой может быть кодер / декодер LZ77 в Basic Compression Library .

Поскольку он использует историю распакованных данных для своего словаря, он не использует никакой дополнительной оперативной памяти, кроме сжатойи несжатые буферы данных.Это должно быть идеально для вашего случая использования (лицензия zlib, переносимая версия C).Весь декодер занимает всего 70 строк кода (включая комментарии) и действительно быстрый.

РЕДАКТИРОВАТЬ: еще одна альтернатива - библиотека liblzg , которая является усовершенствованной версией вышеупомянутого кодера LZ77/ декодер.Он сжимает лучше, обычно быстрее и не требует памяти для распаковки.Это очень, очень бесплатно (лицензия zlib).

Answer 4

Многое зависит от характера данных.Если это достаточно просто, вам может не понадобиться что-то очень причудливое.Например, если загруженные данные были простым изображением (например, что-то вроде линейного графика), простое кодирование длины прогона могло бы сократить данные в десять раз, и вам потребовалось бы тривиальное количество кода и оперативной памяти для его декодирования.

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

Answer 5

Я бы порекомендовал ZLIB .Из вики:

В библиотеке предусмотрены средства для управления использованием процессора и памяти Есть также средства для сохранения памяти .Они, вероятно, полезны только в ограниченных средах памяти, таких как некоторые встроенные системы.zlib также используется во многих встраиваемых устройствах, потому что код является переносимым, свободно лицензируется и имеет относительно небольшой объем памяти .

Answer 6

Я видел, как люди используют 7zip во встроенной системе с объемом памяти в десятки мегабайт.

Answer 7

Возможно, вы захотите попробовать Jørgen Ibsen's aPlib - пару выдержек со страницы продукта:

Коэффициент сжатия, достигаемый с помощью aPLib, в сочетании со скоростью и малой занимаемой площадью депакеров (всего 169 байт!) Делает его идеальным выбором для многих продуктов.

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

Библиотека сжатия с закрытым исходным кодом (да, я знаю, что это может быть проблемой), но имеет предварительно скомпилированные библиотеки для различных компиляторов и операционных систем, включая как 32-, так и 64-битные версии. Существует исходный код сборки C и x86 для декомпрессора.

EDIT:

Jørgen также имеет бесплатную библиотеку BrifLZ (лицензия zlib), которую вы можете проверить, если отсутствие источника компрессора является большой проблемой.