Микроконтролери и електроника
http://mcu-bg.com/mcu_site/

Компресия за ембедед
http://mcu-bg.com/mcu_site/viewtopic.php?f=16&t=14725		 Страница 1 от 1
Автор:  gicho [ Чет Авг 04, 2016 9:22 am ]
Заглавие:  Компресия за ембедед
Гледам че IAR например ползват имплементация на LZ77 да си архивират инициализационните масиви в тяхната runtime библиотека. Зачетох се и гледам че не е толкова тежка, има и доста варианти:
- lzss
- ucl
Оглеждайки ги им измислих приложение и се чудя дали ще намеря подходяща имплементация. Условията са:
- ANSI C или gcc extensions
- входните данни са масив в паметта (memory mapped)
- мога да ги дам целите като пойнтър и размер (не държа имплементацията да поддържа подаване "на парче")
- изхода също ще отива в паметта на пойнтър
- не искам да минава през файлови хендъли и т.н.
- по възможност без ползване динамична памет
- бърз декомпресор

Засега се насочих към lzss - тестовете показаха че за моя тип данни успява да го намали на 47% от оригинала, така че ме устройва. ucl се справя по-добре но странното е че има само asm имплементация (което е и предимство, няма спор - има го за арм).
Автор:  woody [ Чет Авг 04, 2016 1:23 pm ]
Заглавие:  Re: Компресия за ембедед
gicho, бях понаписал няколко абзаца, ама ми умря нета.

В резюме - давай с LZSS и производните му, за случая да инициализираш .data и подобните е оптималното.
Автор:  gicho [ Чет Авг 04, 2016 1:44 pm ]
Заглавие:  Re: Компресия за ембедед
Да, изглежда работещо. Не ми харесва че голямо обикаляне по битове става и е бавничко. Сигурно ще може малко да се оптимизира, но като гледам алгоритъма му не е подходящ за бързо декомпресиране.
Автор:  woody [ Чет Авг 04, 2016 2:10 pm ]
Заглавие:  Re: Компресия за ембедед
Може би гледаш нещо неправилно като отправна точка. LZSS може да се реализира доста просто срещу малко по-ниска компресия. Реално имаш двойки (отместване, дължина) и само копираш. Самото разкомпресиране е едно от най-бързите. На днешните MCU-та дори няма да го усетиш при стартиране.
Автор:  gicho [ Чет Авг 04, 2016 3:41 pm ]
Заглавие:  Re: Компресия за ембедед
Тръгнах от тази имплементация:
https://oku.edu.mie-u.ac.jp/~okumura/compression/lzss.c
Не е за ембедед. Пробвах две други но и двете изкараха безсмислен резултат (спрямо компресирано с тази отгоре).
Ако имаш референция към нещо което да работи ще съм благодарен.
Като цяло с оптимизациите не е (видимо) по-бавно от неоптимизирано мемкопи.
Автор:  woody [ Чет Авг 04, 2016 4:06 pm ]
Заглавие:  Re: Компресия за ембедед
Хм, LZSS е просто клас и всеки компресор си решава за формата - примерно колко назад в речника да може да се гледа, самото кодиране на дистанцията дали да е директно или не и т.н. Според нуждите. Срещу малък компромис със степента на компресия може почти да не се занимаваш с битове, ами да работиш на ниво 8/16 бита (т.е. много бързо), примерно.
Погледни произволен компресор за изпълними файлове, като игнорираш по-сложните подходи вътре. Навремето имаше EXEPACK, LZEXE и т.н., от модерните се сещам UPX. Ако се огледаш има разни LZ-подобни декомпресори дори за 6502 (pucrunch, примерно). Конкретно трудно ще ти посоча нещо, защото не съм се занимавал от доста години.

Като цяло ако си изясниш теорията можеш да пригодиш нещо или направо да си направиш свое.
Автор:  gicho [ Пет Авг 05, 2016 8:03 am ]
Заглавие:  Re: Компресия за ембедед
За момента портирах това от японския линк да работи достатъчно бързо. Тестовете точно с него като компресор показаха 47% да остава от оригинала. Струва ми се че ако изляза от битове и мина на байтове/думи ще влоша достатъчно че да няма смисъл. Имаш ли идея как мога да тествам (бързо) компресор в този вид (8/16)?
От другите гледах UPX който ползва UCL (и други сигурно, но ucl е който ми трябва). Та там нещата са розови откъм ТТ данни, но както казах не е портируемо - има го за x86 и за arm на асемблер, но примерно за mips го няма. Не намерих "референтна" имплементация на C - да е бавна но да е четима.
Няма време/ресурс да вниквам в алгоритми и да имплементирам - не и за момента.
Автор:  woody [ Пет Авг 05, 2016 1:37 pm ]
Заглавие:  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, което естествено на теб не ти трябва.
Автор:  gicho [ Съб Авг 06, 2016 2:38 am ]
Заглавие:  Re: Компресия за ембедед
Heatshrink-а го гледах, дава по-лоша компресия от lzss-а (в моя случай).
Иначе това с определени инстуркшън сет-ове не ми пречи - един от use case-овете е за ARM изпълним код.
Ще разгледам линковете, благодаря.
Автор:  palavrov [ Съб Авг 06, 2016 7:28 am ]
Заглавие:  Re: Компресия за ембедед
LZO трябва да е ОК за ембеддед.
Навремето си бях правил какви ли не компресори но с годините сорсовете се затриха. Помня, че компресорите на изпълними файлове имаха една особенност - можеше да се дезархивира във същия буфер в който е и компресирания файл - просто го започваше отзад напред :) Т.е. съвсем без междинен буфер минаваш :D
Според изискванията за време и степен на компресия можеш да минеш от bitstream с някаква статична компресия (Huffman, Arithmetic и т.н.) комбиниран с LZ до нещо съвсем просто работещо само с байтове и LZ. Ако го напишеш на асемблер кода ще е супер сбит.
Автор:  gicho [ Чет Авг 11, 2016 1:34 am ]
Заглавие:  Re: Компресия за ембедед
Това с обръщането на посоката е хитро - за момента нямам нужда от него (от флаш се декомпресира и слага в рам), но някъде може да хване дикиш.
Страница 1 от 1 Часовете са според зоната UTC + 1 час [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/