Kompresní algoritmus nenáročný na paměť

[TrSek32]

Dobrý
Hľadám program pod nejakou slobodnou licenciou, ktorý by mal minimálne pamatové nároky pri dekompresii. Kompresia može byť náročna jak časovo tak pamaťovo. Skúšal som adaptoval bz2. Našiel som toto http://www.landley.net/code/. Podarilo sa mi to zminimalizovať tak, že štruktúra bunzip_data potrebuje len 8840 Byte, ale program ešte používa "Intermediate buffer" (ten má 400KB!!!) a nejde optimalizovat. Škoda.

Ak niečo viete čo by šlo použiť na microcontroleroch a má to schopnú kompresiu (má zmysel to robiť) napíšte.

Vopred ďakujem

[Reklama]

[gzip]

gzip

[RDa]

Zvazte pouziti jineho mikrokontroleru, kde neni problem pridat napr. 8MB sdram. V jake aplikaci potrebujete v mikrokontroleru dekompresi?

[PJ]

Co tak skusit LZ77? To ma vyzadovat max ~32kB pamati. Slobodna implementacia je v libucw.

[Mirek Prýmek]

Pokud jde o běžný MCU, který má třeba 2kb SRAM a kód by neměl být delší než jednotky kB, tak to asi bude chtít nějaký jednoúčelový algoritmus pro konkrétní typ dat - něco jako RLE, DPCM apod. V obecný algoritmus bych moc nedoufal.

Jinak google "microcontroller compression algorithm" nedává nula výsledků...

[Reklama]

[petrnach]

Jaký typ dat potřebuješ komprimovat?

Texty, foto, zvuk, video?

Koukni se na too:
http://www.stanford.edu/class/cs240e/papers/sensys06_compress.pdf

http://www.programminglogic.com/implementing-huffman-coding-in-c/

[Viktor]

Což třeba LZO? NASA to používá v těch marsovských roverech.

[Xjmeno363-megatroll]

vůbec nepíšete o jaká data jde, nic o entropii, skladbě..., jsou to obrázky, vzorky z AD převodníků, nebo jména pacientů...
co je pro vás nenáročné? Může to být malá spotřeba paměti, nebo malý procesorový výkon...
Potřebujete pracovat proudově, blokově? Může to být slovníková metoda?


to se pak špatně radí...

[Xjmeno363-megatroll]

srry, za tu paměť se omlouvám

[katuma]

Jak uz tu zaznelo, pokud tvoje MCU ma alespon par desitek/stovek kb ram, LZO (potazmo NRV2D/E) je urcite nejlepsi volba.

Existuji jeste mensi/rychlejsi algoritmy kde kompresor/dekompresor je pouze nekolik stovek instrukci a naroky na ram jsou nulove, za zminku stoji treba WKDM, obvzlaste pokud pakujes RISC kod muze byt ratio lepsi nez u LZO.

Konkretni popis:
http://www.lst.inf.ethz.ch/research/publications/WMPI_2004/WMPI_2004.pdf
http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/iokit/Kernel/WKdmCompress.c
http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/iokit/Kernel/WKdmDecompress.c

[Mirek Prýmek]

kde kompresor/dekompresor je pouze nekolik stovek instrukci a naroky na ram jsou nulove, za zminku stoji treba WKDM

Jenom jestli to dobře chápu - nulové jsou nároky na _persistentní_ paměť, ne? Nějakou tu operační pamět to tak jako tak potřebuje  (u WKDM podle http://terpconnect.umd.edu/~barua/matt-compress-tr.pdf minimálně těch 16 slov na slovník).

[TrSek32]

a) ide o prenos FW do zariadenia
b) procesor je Cortex http://en.wikipedia.org/wiki/EFM32
c) k dispozicii je max 128Kb pamate ale realne 20KB SRAM

Dakujem za rady. Zacinam testovat LZO.

[ez]

kde kompresor/dekompresor je pouze nekolik stovek instrukci a naroky na ram jsou nulove, za zminku stoji treba WKDM

Jenom jestli to dobře chápu - nulové jsou nároky na _persistentní_ paměť, ne? Nějakou tu operační pamět to tak jako tak potřebuje  (u WKDM podle http://terpconnect.umd.edu/~barua/matt-compress-tr.pdf minimálně těch 16 slov na slovník).

Chapete to spravne, nejdrive je nutne se seznamit s tim jak algoritmus funguje. Tato konkretni implementace potrebuje daleko vice jak 16 slov, viz wkdmcompres - protoze je optimalizovana predevsim na rychlost.

Na opravdu malych mikrocipech jako 8051 bez externi RAM je nutne tento (ci odvozeny) algoritmus implementovat z gruntu. Vstupem pro kompresi byva DMA, vzdy jednosmerna sbernice, read-only.

Pri kompresi 1kb bloku teoreticky staci pouha 4 32bit slova + 20bitu na pocitani offsetu ktere posilame nakonec. Komprese probiha na 3 passy (tagy, fullwords, varwords) v kterych data posilame progresivne - nemame je kam ulozit - gpio)

Dekomprese je jeste jednodussi a hlavne na jeden pass, jako treba rozbaleni 512k boot loader z 128k externi flash, a to prosim i bez pametoveho radice (Opet slova podle taktu ciloveho MCU/DSP tukame do gpio ci dokonce jtagu(!). Na CPU se tato technika nepouziva protoze si umi samo o sobe kod rozbalit - to ale na harward/jine obskurni architekture nebyva vzdy tak trivialni.

[Mirek Prýmek]

Díky moc, ez, za popis. Zkoumat zdroják se mi nechtělo

Jenom tak pro zajímavost: existuje nějaký algoritmus, který by opravdu nepotřeboval ani žádnou operační paměť? (in-situ ala Bubble sort) To asi ne, co?

[gzip]

Jenom tak pro zajímavost: existuje nějaký algoritmus, který by opravdu nepotřeboval ani žádnou operační paměť? (in-situ ala Bubble sort) To asi ne, co?

Takový algoritmus určitě existuje, ale nejspíš bude mít velmi omezenou účinnost pokud jde o komprimování dat. :-(

Jeden vzorový příklad za všechny: identita