Автор |
Съобщение |
gicho
Ранг: Форумен бог
Регистриран на: Пон Мар 13, 2006 12:59 pm Мнения: 3855 Местоположение: Габрово
|
Компресия за ембедед
Гледам че IAR например ползват имплементация на LZ77 да си архивират инициализационните масиви в тяхната runtime библиотека. Зачетох се и гледам че не е толкова тежка, има и доста варианти: - lzss - ucl Оглеждайки ги им измислих приложение и се чудя дали ще намеря подходяща имплементация. Условията са: - ANSI C или gcc extensions - входните данни са масив в паметта (memory mapped) - мога да ги дам целите като пойнтър и размер (не държа имплементацията да поддържа подаване "на парче") - изхода също ще отива в паметта на пойнтър - не искам да минава през файлови хендъли и т.н. - по възможност без ползване динамична памет - бърз декомпресор
Засега се насочих към lzss - тестовете показаха че за моя тип данни успява да го намали на 47% от оригинала, така че ме устройва. ucl се справя по-добре но странното е че има само asm имплементация (което е и предимство, няма спор - има го за арм).
|
Чет Авг 04, 2016 9:22 am |
|
|
woody
Ранг: Форумен бог
Регистриран на: Вто Юли 31, 2007 1:55 pm Мнения: 1792 Местоположение: София
|
Re: Компресия за ембедед
gicho, бях понаписал няколко абзаца, ама ми умря нета.
В резюме - давай с LZSS и производните му, за случая да инициализираш .data и подобните е оптималното.
|
Чет Авг 04, 2016 1:23 pm |
|
|
gicho
Ранг: Форумен бог
Регистриран на: Пон Мар 13, 2006 12:59 pm Мнения: 3855 Местоположение: Габрово
|
Re: Компресия за ембедед
Да, изглежда работещо. Не ми харесва че голямо обикаляне по битове става и е бавничко. Сигурно ще може малко да се оптимизира, но като гледам алгоритъма му не е подходящ за бързо декомпресиране.
|
Чет Авг 04, 2016 1:44 pm |
|
|
woody
Ранг: Форумен бог
Регистриран на: Вто Юли 31, 2007 1:55 pm Мнения: 1792 Местоположение: София
|
Re: Компресия за ембедед
Може би гледаш нещо неправилно като отправна точка. LZSS може да се реализира доста просто срещу малко по-ниска компресия. Реално имаш двойки (отместване, дължина) и само копираш. Самото разкомпресиране е едно от най-бързите. На днешните MCU-та дори няма да го усетиш при стартиране.
|
Чет Авг 04, 2016 2:10 pm |
|
|
gicho
Ранг: Форумен бог
Регистриран на: Пон Мар 13, 2006 12:59 pm Мнения: 3855 Местоположение: Габрово
|
Re: Компресия за ембедед
Тръгнах от тази имплементация: https://oku.edu.mie-u.ac.jp/~okumura/compression/lzss.cНе е за ембедед. Пробвах две други но и двете изкараха безсмислен резултат (спрямо компресирано с тази отгоре). Ако имаш референция към нещо което да работи ще съм благодарен. Като цяло с оптимизациите не е (видимо) по-бавно от неоптимизирано мемкопи.
|
Чет Авг 04, 2016 3:41 pm |
|
|
woody
Ранг: Форумен бог
Регистриран на: Вто Юли 31, 2007 1:55 pm Мнения: 1792 Местоположение: София
|
Re: Компресия за ембедед
Хм, LZSS е просто клас и всеки компресор си решава за формата - примерно колко назад в речника да може да се гледа, самото кодиране на дистанцията дали да е директно или не и т.н. Според нуждите. Срещу малък компромис със степента на компресия може почти да не се занимаваш с битове, ами да работиш на ниво 8/16 бита (т.е. много бързо), примерно. Погледни произволен компресор за изпълними файлове, като игнорираш по-сложните подходи вътре. Навремето имаше EXEPACK, LZEXE и т.н., от модерните се сещам UPX. Ако се огледаш има разни LZ-подобни декомпресори дори за 6502 (pucrunch, примерно). Конкретно трудно ще ти посоча нещо, защото не съм се занимавал от доста години.
Като цяло ако си изясниш теорията можеш да пригодиш нещо или направо да си направиш свое.
|
Чет Авг 04, 2016 4:06 pm |
|
|
gicho
Ранг: Форумен бог
Регистриран на: Пон Мар 13, 2006 12:59 pm Мнения: 3855 Местоположение: Габрово
|
Re: Компресия за ембедед
За момента портирах това от японския линк да работи достатъчно бързо. Тестовете точно с него като компресор показаха 47% да остава от оригинала. Струва ми се че ако изляза от битове и мина на байтове/думи ще влоша достатъчно че да няма смисъл. Имаш ли идея как мога да тествам (бързо) компресор в този вид (8/16)? От другите гледах UPX който ползва UCL (и други сигурно, но ucl е който ми трябва). Та там нещата са розови откъм ТТ данни, но както казах не е портируемо - има го за x86 и за arm на асемблер, но примерно за mips го няма. Не намерих "референтна" имплементация на C - да е бавна но да е четима. Няма време/ресурс да вниквам в алгоритми и да имплементирам - не и за момента.
|
Пет Авг 05, 2016 8:03 am |
|
|
woody
Ранг: Форумен бог
Регистриран на: Вто Юли 31, 2007 1:55 pm Мнения: 1792 Местоположение: София
|
Re: Компресия за ембедед
Твърде отдавна се занимавах с това за да ти дам конкретни (модерни) насоки/сорсове, а ако нямаш време/желание да вникваш то наистина просто ти трябва нещо готово да го пришиеш. Виж дали нещо от тези не е твоето: http://www.oberhumer.com/opensource/lzo/https://github.com/atomicobject/heatshrinkhttp://cyan4973.github.io/lz4/Най-малкото покрай тях може да попаднеш на нещо, тъй като всеки се опитва да комбинира различни подходи за намаляне на ентропията и се получават много пермутации Ако имаш малко над 32KB RAM за ползване по време на декомпресията, например парче което после ще бъде .bss/heap/stack, можеш да отидеш на DEFLATE (gzip). Сега се сещам че може да погледнеш и linux кернелът какво ползва при boot и дали няма нещо дребно. Доста често се ползват трансформации (филтри) които намалят ентропията за конкретен instruction set, което естествено на теб не ти трябва.
|
Пет Авг 05, 2016 1:37 pm |
|
|
gicho
Ранг: Форумен бог
Регистриран на: Пон Мар 13, 2006 12:59 pm Мнения: 3855 Местоположение: Габрово
|
Re: Компресия за ембедед
Heatshrink-а го гледах, дава по-лоша компресия от lzss-а (в моя случай). Иначе това с определени инстуркшън сет-ове не ми пречи - един от use case-овете е за ARM изпълним код. Ще разгледам линковете, благодаря.
|
Съб Авг 06, 2016 2:38 am |
|
|
palavrov
Ранг: Форумен бог
Регистриран на: Вто Окт 11, 2011 10:53 pm Мнения: 4197 Местоположение: Brussels / Пловдив
|
Re: Компресия за ембедед
LZO трябва да е ОК за ембеддед. Навремето си бях правил какви ли не компресори но с годините сорсовете се затриха. Помня, че компресорите на изпълними файлове имаха една особенност - можеше да се дезархивира във същия буфер в който е и компресирания файл - просто го започваше отзад напред Т.е. съвсем без междинен буфер минаваш Според изискванията за време и степен на компресия можеш да минеш от bitstream с някаква статична компресия (Huffman, Arithmetic и т.н.) комбиниран с LZ до нещо съвсем просто работещо само с байтове и LZ. Ако го напишеш на асемблер кода ще е супер сбит.
_________________ Мразя да мразя ...
|
Съб Авг 06, 2016 7:28 am |
|
|
gicho
Ранг: Форумен бог
Регистриран на: Пон Мар 13, 2006 12:59 pm Мнения: 3855 Местоположение: Габрово
|
Re: Компресия за ембедед
Това с обръщането на посоката е хитро - за момента нямам нужда от него (от флаш се декомпресира и слага в рам), но някъде може да хване дикиш.
|
Чет Авг 11, 2016 1:34 am |
|
|