Отговори на тема  [ 11 мнения ] 
Компресия за ембедед 
Автор Съобщение
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Пон Мар 13, 2006 12:59 pm
Мнения: 2788
Местоположение: Габрово
Мнение Компресия за ембедед
Гледам че IAR например ползват имплементация на LZ77 да си архивират инициализационните масиви в тяхната runtime библиотека. Зачетох се и гледам че не е толкова тежка, има и доста варианти:
- lzss
- ucl
Оглеждайки ги им измислих приложение и се чудя дали ще намеря подходяща имплементация. Условията са:
- ANSI C или gcc extensions
- входните данни са масив в паметта (memory mapped)
- мога да ги дам целите като пойнтър и размер (не държа имплементацията да поддържа подаване "на парче")
- изхода също ще отива в паметта на пойнтър
- не искам да минава през файлови хендъли и т.н.
- по възможност без ползване динамична памет
- бърз декомпресор

Засега се насочих към lzss - тестовете показаха че за моя тип данни успява да го намали на 47% от оригинала, така че ме устройва. ucl се справя по-добре но странното е че има само asm имплементация (което е и предимство, няма спор - има го за арм).


Чет Авг 04, 2016 9:22 am
Профил
Ранг: Форумен бог
Ранг: Форумен бог
Аватар

Регистриран на: Вто Юли 31, 2007 1:55 pm
Мнения: 1792
Местоположение: София
Мнение Re: Компресия за ембедед
gicho, бях понаписал няколко абзаца, ама ми умря нета.

В резюме - давай с LZSS и производните му, за случая да инициализираш .data и подобните е оптималното.


Чет Авг 04, 2016 1:23 pm
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Пон Мар 13, 2006 12:59 pm
Мнения: 2788
Местоположение: Габрово
Мнение Re: Компресия за ембедед
Да, изглежда работещо. Не ми харесва че голямо обикаляне по битове става и е бавничко. Сигурно ще може малко да се оптимизира, но като гледам алгоритъма му не е подходящ за бързо декомпресиране.


Чет Авг 04, 2016 1:44 pm
Профил
Ранг: Форумен бог
Ранг: Форумен бог
Аватар

Регистриран на: Вто Юли 31, 2007 1:55 pm
Мнения: 1792
Местоположение: София
Мнение Re: Компресия за ембедед
Може би гледаш нещо неправилно като отправна точка. LZSS може да се реализира доста просто срещу малко по-ниска компресия. Реално имаш двойки (отместване, дължина) и само копираш. Самото разкомпресиране е едно от най-бързите. На днешните MCU-та дори няма да го усетиш при стартиране.


Чет Авг 04, 2016 2:10 pm
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Пон Мар 13, 2006 12:59 pm
Мнения: 2788
Местоположение: Габрово
Мнение Re: Компресия за ембедед
Тръгнах от тази имплементация:
https://oku.edu.mie-u.ac.jp/~okumura/compression/lzss.c
Не е за ембедед. Пробвах две други но и двете изкараха безсмислен резултат (спрямо компресирано с тази отгоре).
Ако имаш референция към нещо което да работи ще съм благодарен.
Като цяло с оптимизациите не е (видимо) по-бавно от неоптимизирано мемкопи.


Чет Авг 04, 2016 3:41 pm
Профил
Ранг: Форумен бог
Ранг: Форумен бог
Аватар

Регистриран на: Вто Юли 31, 2007 1:55 pm
Мнения: 1792
Местоположение: София
Мнение Re: Компресия за ембедед
Хм, LZSS е просто клас и всеки компресор си решава за формата - примерно колко назад в речника да може да се гледа, самото кодиране на дистанцията дали да е директно или не и т.н. Според нуждите. Срещу малък компромис със степента на компресия може почти да не се занимаваш с битове, ами да работиш на ниво 8/16 бита (т.е. много бързо), примерно.
Погледни произволен компресор за изпълними файлове, като игнорираш по-сложните подходи вътре. Навремето имаше EXEPACK, LZEXE и т.н., от модерните се сещам UPX. Ако се огледаш има разни LZ-подобни декомпресори дори за 6502 (pucrunch, примерно). Конкретно трудно ще ти посоча нещо, защото не съм се занимавал от доста години.

Като цяло ако си изясниш теорията можеш да пригодиш нещо или направо да си направиш свое.


Чет Авг 04, 2016 4:06 pm
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Пон Мар 13, 2006 12:59 pm
Мнения: 2788
Местоположение: Габрово
Мнение Re: Компресия за ембедед
За момента портирах това от японския линк да работи достатъчно бързо. Тестовете точно с него като компресор показаха 47% да остава от оригинала. Струва ми се че ако изляза от битове и мина на байтове/думи ще влоша достатъчно че да няма смисъл. Имаш ли идея как мога да тествам (бързо) компресор в този вид (8/16)?
От другите гледах UPX който ползва UCL (и други сигурно, но ucl е който ми трябва). Та там нещата са розови откъм ТТ данни, но както казах не е портируемо - има го за x86 и за arm на асемблер, но примерно за mips го няма. Не намерих "референтна" имплементация на C - да е бавна но да е четима.
Няма време/ресурс да вниквам в алгоритми и да имплементирам - не и за момента.


Пет Авг 05, 2016 8:03 am
Профил
Ранг: Форумен бог
Ранг: Форумен бог
Аватар

Регистриран на: Вто Юли 31, 2007 1:55 pm
Мнения: 1792
Местоположение: София
Мнение Re: Компресия за ембедед
Твърде отдавна се занимавах с това за да ти дам конкретни (модерни) насоки/сорсове, а ако нямаш време/желание да вникваш то наистина просто ти трябва нещо готово да го пришиеш.
Виж дали нещо от тези не е твоето:

http://www.oberhumer.com/opensource/lzo/
https://github.com/atomicobject/heatshrink
http://cyan4973.github.io/lz4/

Най-малкото покрай тях може да попаднеш на нещо, тъй като всеки се опитва да комбинира различни подходи за намаляне на ентропията и се получават много пермутации

Ако имаш малко над 32KB RAM за ползване по време на декомпресията, например парче което после ще бъде .bss/heap/stack, можеш да отидеш на DEFLATE (gzip). Сега се сещам че може да погледнеш и linux кернелът какво ползва при boot и дали няма нещо дребно. Доста често се ползват трансформации (филтри) които намалят ентропията за конкретен instruction set, което естествено на теб не ти трябва.


Пет Авг 05, 2016 1:37 pm
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Пон Мар 13, 2006 12:59 pm
Мнения: 2788
Местоположение: Габрово
Мнение Re: Компресия за ембедед
Heatshrink-а го гледах, дава по-лоша компресия от lzss-а (в моя случай).
Иначе това с определени инстуркшън сет-ове не ми пречи - един от use case-овете е за ARM изпълним код.
Ще разгледам линковете, благодаря.


Съб Авг 06, 2016 2:38 am
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Вто Окт 11, 2011 10:53 pm
Мнения: 2775
Местоположение: Brussels / Пловдив
Мнение Re: Компресия за ембедед
LZO трябва да е ОК за ембеддед.
Навремето си бях правил какви ли не компресори но с годините сорсовете се затриха. Помня, че компресорите на изпълними файлове имаха една особенност - можеше да се дезархивира във същия буфер в който е и компресирания файл - просто го започваше отзад напред :) Т.е. съвсем без междинен буфер минаваш :D
Според изискванията за време и степен на компресия можеш да минеш от bitstream с някаква статична компресия (Huffman, Arithmetic и т.н.) комбиниран с LZ до нещо съвсем просто работещо само с байтове и LZ. Ако го напишеш на асемблер кода ще е супер сбит.

_________________
Мразя да мразя ...


Съб Авг 06, 2016 7:28 am
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Пон Мар 13, 2006 12:59 pm
Мнения: 2788
Местоположение: Габрово
Мнение Re: Компресия за ембедед
Това с обръщането на посоката е хитро - за момента нямам нужда от него (от флаш се декомпресира и слага в рам), но някъде може да хване дикиш.


Чет Авг 11, 2016 1:34 am
Профил
Покажи мненията от миналия:  Сортирай по  
Отговори на тема   [ 11 мнения ] 

Кой е на линия

Потребители разглеждащи този форум: 0 регистрирани и 1 госта


Вие не можете да пускате нови теми
Вие не можете да отговаряте на теми
Вие не можете да променяте собственото си мнение
Вие не можете да изтривате собствените си мнения
Вие не можете да прикачвате файл

Търсене:
Иди на:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software for PTF.
Хостинг и Домейни