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

TrSek32

Kompresní algoritmus nenáročný na paměť
« kdy: 16. 10. 2012, 11:46:06 »
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
« Poslední změna: 16. 10. 2012, 12:02:26 od Petr Krčmář »


gzip

Re:Kompresny algoritmus s minimalnymi narokmi na pamat
« Odpověď #1 kdy: 16. 10. 2012, 11:47:51 »
gzip

RDa

  • *****
  • 2 567
    • Zobrazit profil
    • E-mail
Re:Kompresní algoritmus nenáročný na paměť
« Odpověď #2 kdy: 16. 10. 2012, 12:07:23 »
Zvazte pouziti jineho mikrokontroleru, kde neni problem pridat napr. 8MB sdram. V jake aplikaci potrebujete v mikrokontroleru dekompresi?

PJ

Re:Kompresní algoritmus nenáročný na paměť
« Odpověď #3 kdy: 16. 10. 2012, 12:15:57 »
Co tak skusit LZ77? To ma vyzadovat max ~32kB pamati. Slobodna implementacia je v libucw.

Re:Kompresní algoritmus nenáročný na paměť
« Odpověď #4 kdy: 16. 10. 2012, 12:34:40 »
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ů...


Re:Kompresní algoritmus nenáročný na paměť
« Odpověď #5 kdy: 16. 10. 2012, 13:32:02 »

Viktor

Re:Kompresní algoritmus nenáročný na paměť
« Odpověď #6 kdy: 16. 10. 2012, 14:08:20 »
Což třeba LZO? NASA to používá v těch marsovských roverech.

Xjmeno363-megatroll

Re:Kompresní algoritmus nenáročný na paměť
« Odpověď #7 kdy: 16. 10. 2012, 16:20:56 »
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

Re:Kompresní algoritmus nenáročný na paměť
« Odpověď #8 kdy: 16. 10. 2012, 16:21:31 »
srry, za tu paměť se omlouvám

Re:Kompresní algoritmus nenáročný na paměť
« Odpověď #9 kdy: 16. 10. 2012, 22:53:05 »
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

Re:Kompresní algoritmus nenáročný na paměť
« Odpověď #10 kdy: 16. 10. 2012, 23:22:09 »
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

Re:Kompresní algoritmus nenáročný na paměť
« Odpověď #11 kdy: 17. 10. 2012, 11:26:41 »
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

Re:Kompresní algoritmus nenáročný na paměť
« Odpověď #12 kdy: 17. 10. 2012, 12:29:11 »
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.


Re:Kompresní algoritmus nenáročný na paměť
« Odpověď #13 kdy: 17. 10. 2012, 12:53:21 »
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

Re:Kompresní algoritmus nenáročný na paměť
« Odpověď #14 kdy: 17. 10. 2012, 13:36:54 »
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