Hallo, Ich möchte hier meine Implementierung der Huffman-Kompression für den AVR vorstellen. Der Vorteil gegenüber der früher in diesem Forum geposteten Software ist die Einhaltung der avr-gcc ABI, so dass dieser Code einfach in C-Programmen zu verwenden ist. Im "host"-Verzeichnis liegen die host-tools zum komprimieren und dekomprimieren (geschrieben in portablem C, sollten sich eigentlich überall compiliere lassen). Im "test"-Verzeichnis liegt eine Test-Applikation die auch noch ein paar andere nette Dinge enthält (uart, kommandointerface, dump utility, ...). Das ganze steht unter der GPLv3 Lizenz. Updates gibt es im svn unter http://das-labor.org/svn/microcontroller-2/lib/avr-huffman. Der AVR kann allerdings nur dekomprimieren, der Assembler Code dafür brauch nur 572 Bytes an Flash-Speicher. Ein wenig Doku findet sich im Labor wiki unter http://www.das-labor.org/wiki/AVR-Huffman Viel Spaß damit, nerilex
Gast
#1447484
Nett, nachher mal testen ob das ganze auch am Cevi mit cc65 will. :)
Gast
#1449893
Mal eine Frage ... unkomprimiert: > 00000000 61 62 63 61 61 61 62 0a komprimiert: > 00000000 c0 de 05 01 61 00 04 63 0a 62 ff 68 35 e0 Ist im komprimierten auch gleich schon der Huffmann-Baum gespeichert, oder nur die komprimierten Daten? Normalerweise sollte aus der oben genannten Sequenz sowas rauskommen: Generiertes Alphabet: a: 0 b: 10 c: 110 0x0a: 111 Ergebnis (binär): 0,10,110,0,0,0,111 = 0x587 aber selbst mit gespeichertem Alphabet ... 0x00 0x61 0x02 0x62 0x06 0x63 0x07 0x0a | 0x05 0x87 Aber das ist immer noch weniger als die Sequenz oben ...
Gast
#1449896
Ups, mein Huffman Code ist unsinn ... sorry ;) Trotzdme, wieso ist das komprimierte soviel größer, als das unkomprimierte?
> Trotzdme, wieso ist das komprimierte soviel größer, als das > unkomprimierte? Weil es zu wenig Daten sind. Da ist der Overhead für die Kompression im Verhältnis zu den Nutzdaten "suboptimal".
Gast schrieb: > Trotzdme, wieso ist das komprimierte soviel größer, als das > unkomprimierte? Huffman Kompression funktioniert am besten bei einer unendlichen gedächtnislosen Quellen Folge. 00000000 61 62 63 61 61 61 62 0a ist zumindest schonmal nicht sehr unendlich ;)
In dem gewählten Beispiel werden die komprimierten Daten von dem Baum dominiert. Die Daten lassen sich wie folgt aufteilen: Header: c0 de Baum: 05 01 61 00 04 63 0a 62 ff Daten: 68 35 e0 Es gibt mehrere Möglichkeiten einen entsprechenden Huffmanbaum zu konstruieren. Daher ist es wichtig den Baum so zu speichern, das er exakt wieder hergestellt werden kann. Ich verwende eine spezielle Technik um den Baum zu speichern. Dazu wird der Baum so verändert, dass von links nach rechts der Baum immer tiefer wird. Dann werden die Ebenen aufsteigend gespeichert. D.h. Es muss nur die Anzahl der Blätter je Ebene gespeichert werden gefolgt von den Werten der Blätter. mfg nerilex