Компактная библиотека декомпрессии для встроенного использования
В настоящее время мы создаем устройство для клиента, которое получит блок данных (например, 5-10 КБ) из приложения ПК. Это немного упрощено, поэтому предположим, что данные должны быть переданы и несжаты много, а не раз в год. Канал связи действительно, очень медленный, поэтому мы хотели бы заранее скомпилировать данные, перейти к устройству и разрешить его распаковать данные во внутреннюю вспышку. Однако само устройство работает на микроконтроллере, который не очень быстр и не имеет большой памяти. У него достаточно флэш-памяти для хранения результата и может распаковать блок данных по мере его получения, но у него может не хватить ОЗУ для хранения всех сжатых или несжатых (или даже обоих!) Блоков данных. И, конечно же, у него нет операционной системы или другой роскоши.
Это означает, что нам нужен достаточно быстрый алгоритм без сжатия, который не использует много памяти. Сжатие может быть медленным и уродливым, поскольку мы делаем это на стороне ПК. C или .NET предпочтительнее, хотя для сжатия, чтобы упростить задачу. Код без сжатия должен быть в C, так как маловероятно, что у кого-то есть оптимизированная версия ASM для нашего контроллера.
Мы нашли LZO, который был бы почти идеальным для нас, но по умолчанию имеет так называемую "свободную" лицензию (GPL), что делает ее совершенно непригодной для наших клиентов. Автор говорит, что коммерческие лицензии доступны по запросу, но, к сожалению, он в настоящее время недоступен (по нетехническим причинам, например, новости на его сайте говорят).
Я нашел несколько других библиотек, в том числе puff.c из zlib, и мы все еще расследуем, но я подумал, что попрошу ваш опыт:
Какой алгоритм сжатия и/или библиотека вы рекомендуете для встроенных целей, учитывая, что устройство декомпрессии действительно ограничено ресурсами и исходным кодом, и требуется коммерческая лицензия?
Ответы
Ответ 1
Возможно, вы захотите проверить один из них, который не является GPL и представляет собой довольно компактную реализацию:
- fastlz - лицензия MIT, довольно простой код
- lzjb - sun CDDL, используемый в zfs для сжатия, простой и очень короткий
- liblzf - лицензия BSD-стиля, маленькая, быстрая
- lzfx - стиль BSD, основанный на liblzf, маленький, быстрый
Все эти алгоритмы основаны на исходном алгоритме Lempel-Ziv-Welch (они имеют все общие LZ)
https://en.wikipedia.org/wiki/Lempel-Ziv-Welch
Ответ 2
Я использовал LZSS. Я использовал код из Haruhiko Okumura в качестве базы. Он использует последнюю часть несжатых данных (2K) в качестве словаря. Этот код можно изменить, чтобы не требовать временного кольцевого буфера, если у вас нет памяти. Лицензирование не ясно из его сайта, но some версии был выпущен с использованием "Использовать, распространять и модифицировать эту программу свободно", и код используется коммерческими поставщиками.
Здесь - это реализация, основанная на том же коде, который является частью игровой библиотеки Allegro. Лицензирование Allegro - подарочная упаковка или zlib.
Другим вариантом может быть lzfx lib, которые реализуют LZF. Я еще не использовал его, но это кажется приятным. Также использует предыдущие результаты, поэтому он имеет низкие требования к памяти и выпускается под лицензией BSD.
Ответ 3
Одной из альтернатив может быть кодировщик/декодер LZ77 в Базовая библиотека сжатия.
Поскольку он использует историю распакованных данных для своего словаря, он не использует лишнюю ОЗУ, кроме сжатых и несжатых буферов данных. Он должен быть идеальным для вашего случая использования (лицензия zlib, переносимая C). Весь декодер составляет всего 70 строк кода (включая комментарии) и очень быстро.
EDIT: Еще одна альтернатива - библиотека liblzg, которая является уточненной версией вышеупомянутого кодера/декодера LZ77. Он сжимается лучше, обычно быстрее и не требует памяти для декомпрессии. Это очень, очень бесплатно (zlib лицензия).
Ответ 4
Многое зависит от характера данных. Если это достаточно просто, вам может не понадобиться ничего необычного. Например, если загруженные данные были простым изображением (например, что-то вроде линейного графика), простая кодировка длины пробега могла сократить данные до десяти раз, и вам понадобилось бы тривиальное количество кода и ОЗУ для его декодирования.
Конечно, если данные более сложны, то это не будет очень полезно. Но я бы начал с изучения отправляемых данных и посмотрел, есть ли конкретные аспекты, которые позволят вам сжать его более эффективно, чем использовать алгоритм общего назначения.
Ответ 5
Я бы рекомендовал ZLIB.
Из вики:
Библиотека предоставляет средства для управления использованием процессора и памяти
Есть также средства для сохранения памяти. Вероятно, они полезны только в средах с ограниченной памятью, таких как некоторые встроенные системы.
zlib также используется во многих встроенных устройствах, потому что код переносимый, лицензированный по лицензии
и имеет относительно небольшой объем памяти.
Ответ 6
Возможно, вы захотите проверить Jørgen Ibsen aPlib - пару выдержек со страницы продукта:
Коэффициенты сжатия, достигнутые aPLib в сочетании со скоростью и крошечным размером депакеры (всего 169 байт!), делают его идеальным выбором для многих продуктов.
aPLib можно использовать даже для коммерческого использования, пожалуйста, ознакомьтесь с включенной лицензией.
Библиотека сжатия является закрытой (да, я знаю, что это может быть проблемой), но имеет предварительно скомпилированные библиотеки для различных компиляторов и операционных систем, включая 32- и 64-разрядные версии. Исходный код сборки C и x86 для декомпрессора.
EDIT:
Jørgen также имеет бесплатную библиотеку BrifLZ (zlib license), которую вы можете проверить, если проблема с источником компрессора не является большой проблемой.
Ответ 7
Я видел, как люди использовали 7zip во встроенной системе с памятью в десятках мегабайт.