[AVR ASM] Huffman (de)kompression

[Läubi .. (laeubi)]

Ein dekompressions Algorithmus für Daten, benuzt wird ein Huffmanbaum.
Nützlich z.B. für die komprimierung von statischen Bildern bei 
Grafikdisplays. (bis zu 70% Kompression je nach Eingangsdaten)

Die Funktion benötigt im Y-Pointer einen Zeiger auf den SRAM wohin die 
Daten entpackt werden sollen, und im Z-Pointer auf den Flash wo die 
komprimierten Daten liegen.
Dies kann aber durch #defines angepaßt werden, sodass theoretisch gleich 
auf das DisplayRam geschrieben wird, oder aus dem EEProm/externem 
Speicher gelesen wird.
Beispiel:

.include "m32def.inc"

.dseg
  buffer:
  .org 0x60
  .byte 12
.cseg

//Feldpointer initialisieren für Huffman
ldi YL, LOW(buffer)
ldi YH, HIGH(buffer)
//Datenpointer initialisieren
ldi ZL, LOW(daten*2)
ldi ZH, HIGH(daten*2)
call huffman
call <FlushSRAM2Display>

loop:
rjmp loop
.include "Huffman.asm"
daten:
.include "daten.txt"

Einstellmöglichkeiten: (jeweil über #defines)
- Von wo gelesen werden soll
- Wohin soll geschriben werden
- Sollen die verwendeten Register gerettet werden
- soll der 4bit Modus unterstüzt werden

Komprimiert werden können Daten mittels des Javaprogramms im Anhang 
(nächstes Posting), gelesen werden Binärdaten (Ich erzeuge die mit 
meinem GrafikKonverter bspw: Beitrag "Grafikkonverter Tool für AVR/Mikrocontroller (BMP2C, BMP2ASM, BMP2BASCOM)" 
), geschrieben wird eine TXT Datei im AVR Studio ASM Format die einfach 
per include eingebunden werden kann.

Wenn Interese besteht kann ich natürlich noch ne kleine Doku zum 
Dateiformat veröffentlichen, z.B. wenn jemand Lust hat einen 
(kompatiblen) dekompressor in C oder Basic zu verfassen.

Zur Geschwindigkeit:
bei 16MHZ dauert es eine 240x64 Pixel Grafik zu dekodieren mit 24% 
kompressionsrate im 8bit Modus etwa 15ms
bei 4bit (30% gleiche Datei) etwa 19,5ms

[Läubi .. (laeubi)]

Wenn Java installiert ist kann das JAR File meist per Doppelklick direkt 
ausgeführ werden, oder aus der Konsole heraus mittels:
java -jar Huffman_Kompressor_V1.jar
Zusätzlich kann der 4-BitModu mittels:
java -jar Huffman_Kompressor_V1.jar 4
gewählt werden, dies bringt manchmal höhhere Kompressionsraten durch den 
kleineren Huffmanbaum der entsteht.

[avr (Gast)]

Hallo Läubi

Ich habe versucht eine Binärdatei mit dem Kompressor zu komprimieren. Er 
zeigt eine Kompression von 22KB zu 16KB an, aber erzeugt eine 100KB 
Datei? Die Test-Datei habe ich angehängt.

[Läubi .. (laeubi)]

avr schrieb:
> Er zeigt eine Kompression von 22KB zu 16KB an, aber erzeugt eine 100KB
Die Datei welche erzeugt wird ist eine für den AVR Assembler gedachte 
Textdatei, enthält also sehr viel redundanz durch die ASCII Codierung 
(in HEX) sowie ein paar Kommentare.
Nach dem assemblieren werden daraus aber wieder die "binären" 16KB.