Форум Микро-Чип
Поиск и заказ электронных компонентов
 

Вернуться   Форум Микро-Чип > Своими руками

Своими руками Завершенные и текущие проекты, хард & софт

Ответ
 
Опции темы Опции просмотра
Старый 13.01.2011, 15:54   #1
dimonomid
Member
 
Аватар для dimonomid
 
Регистрация: 17.06.2009
Возраст: 32
Сообщений: 98
Вес репутации: 1112/42
dimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud of
Отправить сообщение для dimonomid с помощью ICQ
Lightbulb Распаковка информации, сжатой методом deflate

Всем здрасьте.

Мне нужно реализовать в PIC24 распаковку инфы, сжатой методом Deflate. Может быть, у кого-то уже есть рабочий модуль?

Если кто не знает, этот алгоритм используется в gzip и в изображениях PNG, использует комбинацию алгоритма LZ77 и алгоритма Хаффмана.

Почему я выбрал именно этот алгоритм - потому, что он свободный и достаточно эффективный, плюс еще вот процитирую Википедию:
Цитата:
The normal intent with an alternative Inflate implementation is highly optimised decoding speed, or extremely predictable RAM usage for micro-controller embedded systems.
Вот и сама статья про него, в конце статьи есть несколько ссылок на оперсорсные проекты. Среди них, по-моему, самый удачный этот: tinf.

Я его по пытаюсь допилить до юзабельного состояния, но пока что все равно остаются проблемы.

Во-первых, сначала он требовал килобайт с лишним стека, я перенес все тяжелые массивы из стека (разместил просто статически), теперь стека требует мало, но ОЗУ потребляет порядочно: 3.3К.

Program memory занимает примерно столько же - 3.2К, это меня полностью устраивает.

Ну и еще он у меня пока работает криво: вроде бы и работает, но иногда где-то байт перепутает, еще при распаковке некоторых последовательностей возникает address error - в общем, нужно допиливать.

Подозреваю, что ошибки возникают из-за того, что писался он для настольных ПК, и, следовательно, размеры типов другие. Я там заменил везде unsigned int на unsigned long, short на int, и т.д., но там еще может где-то предполагается, что указатель 32-битный, или еще что-то.. Нужно еще попробовать собрать его под ПК и посмотреть, как он будет работать в "родной среде".

В общем, если у кого-то есть что посоветовать дельное - буду рад выслушать.

UPD: да, deflate - не самоцель, если есть какой-то другой, более подходящий алгоритм, я буду рад =) Просто исходя из того, что я накопал за последние дни, я сделал вывод, что deflate - это, вроде как, лучший вариант.

Последний раз редактировалось dimonomid; 13.01.2011 в 16:10.
dimonomid вне форума   Ответить с цитированием
Старый 19.01.2011, 12:11   #2
dimonomid
Member
 
Аватар для dimonomid
 
Регистрация: 17.06.2009
Возраст: 32
Сообщений: 98
Вес репутации: 1112/42
dimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud of
Отправить сообщение для dimonomid с помощью ICQ
По умолчанию Re: Распаковка информации, сжатой методом deflate

Все, вроде доработал.
Оптимизировано использование ОЗУ, добавлена расширяемость для работы с внешними устройствами хранения данных, добавлены другие настройки.

Теперь:
Объем используемой ОЗУ: 1.6 Кб (из кучи, стека или статически - это настраивается) + около 50 байт стека;
Размер кода: 3.4 Кб.

Вообще, передо мной стояла следующая задача: на микроконтроллере PIC24 запрашивать по UART сжатые данные, на лету распаковывать и записывать во flash-память, объем распакованных данных может достигать 1 Мб.
Но вообще можно работать с любыми устройствами хранения данных, и объем данных может достигать 4 Гб =)

Если кому нужно, то вот http://dfrank.ru/prog/c/tinf, там же можно скачать.

Последний раз редактировалось tester; 20.01.2011 в 19:47. Причина: 50 Кб стека -> 50 байт стека
dimonomid вне форума   Ответить с цитированием
Старый 19.01.2011, 12:19   #3
tester
Super Moderator
 
Аватар для tester
 
Регистрация: 28.02.2007
Возраст: 40
Сообщений: 3,577
Вес репутации: 4386/118
tester has a reputation beyond reputetester has a reputation beyond reputetester has a reputation beyond reputetester has a reputation beyond reputetester has a reputation beyond reputetester has a reputation beyond reputetester has a reputation beyond reputetester has a reputation beyond reputetester has a reputation beyond reputetester has a reputation beyond reputetester has a reputation beyond repute
По умолчанию Re: Распаковка информации, сжатой методом deflate

Цитата:
Сообщение от dimonomid Посмотреть сообщение
Если кому нужно, то вот http://dfrank.ru/prog/c/tinf, там же можно скачать.
Спасибо, очень полезная библиотека.

(Форум плюсик не дает тебе поставить, видимо, ставил недавно)
tester вне форума   Ответить с цитированием
Старый 20.01.2011, 23:34   #4
Alex B.
Super Moderator
 
Аватар для Alex B.
 
Регистрация: 25.02.2007
Адрес: Russia, SPb
Сообщений: 1,674
Вес репутации: 1729/73
Alex B. has a brilliant futureAlex B. has a brilliant futureAlex B. has a brilliant futureAlex B. has a brilliant futureAlex B. has a brilliant futureAlex B. has a brilliant futureAlex B. has a brilliant futureAlex B. has a brilliant futureAlex B. has a brilliant futureAlex B. has a brilliant futureAlex B. has a brilliant future
Отправить сообщение для Alex B. с помощью Skype™
По умолчанию Re: Распаковка информации, сжатой методом deflate

Цитата:
Сообщение от dimonomid Посмотреть сообщение
Все, вроде доработал.
Оптимизировано использование ОЗУ, добавлена расширяемость для работы с внешними устройствами хранения данных, добавлены другие настройки.
Теперь:
Объем используемой ОЗУ: 1.6 Кб (из кучи, стека или статически - это настраивается) + около 50 байт стека;
Размер кода: 3.4 Кб.
Так а какая степень сжатия достижима? как быстро работает?
__________________
даташит читать до того , а не после
Alex B. вне форума   Ответить с цитированием
Старый 21.01.2011, 13:07   #5
dimonomid
Member
 
Аватар для dimonomid
 
Регистрация: 17.06.2009
Возраст: 32
Сообщений: 98
Вес репутации: 1112/42
dimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud of
Отправить сообщение для dimonomid с помощью ICQ
По умолчанию Re: Распаковка информации, сжатой методом deflate

Цитата:
Сообщение от Alex B. Посмотреть сообщение
Так а какая степень сжатия достижима? как быстро работает?
На всякий случай уточню: этот модуль умеет только распаковывать, сжимать он не умеет. Сжимать нужно, например, gzip'ом.

Степень сжатия, конечно, зависит от типа данных. Результаты тестов:
bin прошивка: 110 Kb -> 86 Kb (сжато на 22%)
windows *.exe: 101 Kb -> 46 Kb (сжато на 55%)
ASCII текст: 506 Kb -> 162 Kb (сжато на 68%)
bmp картинка: 7 Kb -> 1 Kb (сжато на 86%) (вот эта картинка: http://ompldr.org/vNzM3dA)

Работает довольно медленно.
Без учета времени, потраченного на чтение-запись во флеш:
распаковка ASCII текста 10 Kb -> 30 Kb: около 5 500 000 тиков;
распаковка windows exe 46 Kb -> 101 Kb: около 23 000 000 тиков.

---

Вообще, я думаю сделать еще один модуль, который будет распаковывать инфу, сжатую методом LZ77. Суть его просто в том, что повторяющиеся данные копируются из ранее "распакованных". Это более эффективно, чем RLE, но не более ресурсоемко, чем RLE. Никаких 1.6 Кб ОЗУ уже не будет нужно, и работать будет в разы быстрее. С bmp иконками вроде той, что я привел, должен будет работать неплохо, раза в два-то сожмет.
dimonomid вне форума   Ответить с цитированием
Старый 30.01.2012, 13:51   #6
altemir
Junior Member
 
Регистрация: 30.01.2012
Сообщений: 2
Вес репутации: 100/0
altemir will become famous soon enoughaltemir will become famous soon enough
По умолчанию Re: Распаковка информации, сжатой методом deflate

Здравствуйте. Скажите, отладили ли вы алгоритм, приведённый здесь: http://dfrank.ru/prog/c/tinf ?
Известны ли тесты на arm7-платформе (LPC2000)? Как можно увеличить скорость распаковки? Есть проц, работающий на частоте в 58МГц, есть gzip-файл прошивки ПЛИС, весящий около 35КБ. По приведённым у вас расчётам получается время декомпрессии (для PIC24) около 3сек. Хотелось бы сократить. Готов RAM отдать под 2КБ и FLASH под 5КБ
altemir вне форума   Ответить с цитированием
Старый 30.01.2012, 13:59   #7
dimonomid
Member
 
Аватар для dimonomid
 
Регистрация: 17.06.2009
Возраст: 32
Сообщений: 98
Вес репутации: 1112/42
dimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud of
Отправить сообщение для dimonomid с помощью ICQ
По умолчанию Re: Распаковка информации, сжатой методом deflate

Цитата:
Сообщение от altemir Посмотреть сообщение
Здравствуйте. Скажите, отладили ли вы алгоритм, приведённый здесь: http://dfrank.ru/prog/c/tinf ?
Глюков не замечал. Вроде все работает.

Цитата:
Сообщение от altemir Посмотреть сообщение
Известны ли тесты на arm7-платформе (LPC2000)?
Неа
Цитата:
Сообщение от altemir Посмотреть сообщение
Как можно увеличить скорость распаковки? Есть проц, работающий на частоте в 58МГц, есть gzip-файл прошивки ПЛИС, весящий около 35КБ. По приведённым у вас расчётам получается время декомпрессии (для PIC24) около 3сек. Хотелось бы сократить.
Я не знаю, как можно ускорить. Знал бы - написал бы =)

Цитата:
Сообщение от altemir Посмотреть сообщение
Готов RAM отдать под 2КБ и FLASH под 5КБ
Расход памяти я привел: RAM 1.6КБ, Flash 3.6КБ (если компилировать микрочиповским C30. другие компиляторы не тестировал)

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

Можете поискать еще другие реализации, но все те, что я встречал, когда искал, требовали в несколько раз больше ресурсов (и Flash, и RAM). Но, может, вам повезет больше =)
dimonomid вне форума   Ответить с цитированием
Старый 30.01.2012, 14:04   #8
altemir
Junior Member
 
Регистрация: 30.01.2012
Сообщений: 2
Вес репутации: 100/0
altemir will become famous soon enoughaltemir will become famous soon enough
По умолчанию Re: Распаковка информации, сжатой методом deflate

Хорошо. Спасибо. Если доберусь с этим алгоритмом до проекта - отпишусь
altemir вне форума   Ответить с цитированием
Старый 12.12.2012, 19:13   #9
dimonomid
Member
 
Аватар для dimonomid
 
Регистрация: 17.06.2009
Возраст: 32
Сообщений: 98
Вес репутации: 1112/42
dimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud ofdimonomid has much to be proud of
Отправить сообщение для dimonomid с помощью ICQ
По умолчанию Re: Распаковка информации, сжатой методом deflate

Коль скоро у нас тут появился раздел "Своими руками", переместите эту тему туда, пожалуйста.
dimonomid вне форума   Ответить с цитированием
Старый 25.10.2017, 16:03   #10
SERGOSV
Junior Member
 
Регистрация: 31.03.2016
Возраст: 49
Сообщений: 21
Вес репутации: 175/7
SERGOSV has a spectacular aura aboutSERGOSV has a spectacular aura about
По умолчанию Re: Распаковка информации, сжатой методом deflate

Тема не новая, но хотел сказать автору СПАСИБО! Приятно работающая библиотечка. Пробовал на PIC32MZ под ХС32. Файлы, жатые 7-zip, разжимает на ура! (Что интересно - идущая в Harmony zlib - у меня не завелась, пока не разобрался почему).

Вопрос автору - было ли развитие библиотеки? Интересно...
SERGOSV вне форума   Ответить с цитированием
Старый 06.11.2017, 15:09   #11
SERGOSV
Junior Member
 
Регистрация: 31.03.2016
Возраст: 49
Сообщений: 21
Вес репутации: 175/7
SERGOSV has a spectacular aura aboutSERGOSV has a spectacular aura about
По умолчанию Re: Распаковка информации, сжатой методом deflate

В продолжение темы - функции, которые идут в Harmony для сжатия-разжатия - работают. Правда в том виде, как есть, позволяют работать только с буфером в памяти и не с gzip архивами (ну насколько я с ними разобрался).
Библиотека, которая здесь обсуждается - работает с любыми источниками-приемниками данных, единственная особенность, которую мне пришлось под свои задачи скорректировать - автор в качестве словаря для распаковки архива использует ранее распакованные данные. Я упаковывал в архив несколько файлов, для чего предварительно собирал их в tar. Таким образом, чтоб получить распакованные файлы, например во Flash памяти - нужно сначала разжать архив, потом отдельно распаковывать tar. Что приводит к необходимости иметь удвоенный объем флэш для распаковки архива, что не хорошо.
Но если создать временный скользящий буфер размером 32К (PIC32MZ это позволяет, памяти хватает), то можно в потоковом режиме распаковывать архив, сразу раскладывая файлы из tar.
(Если такой задачи нет - несколько файлов в одном архиве, то механизм, изложенный автором - хорошо работает без изменений).
SERGOSV вне форума   Ответить с цитированием
Ответ


Здесь присутствуют: 1 (пользователей: 0 , гостей: 1)
 
Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход


Часовой пояс GMT +3, время: 20:40.


Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd. Перевод: zCarot