AVR-Huffman

Aus LaborWiki
Wechseln zu: Navigation, Suche
           
AVR-Huffman

Release status: stable [box doku]

Avr-huffman-logo.png
Description Dekompression von Huffman komprimierten Daten zur Laufzeit
Author(s)  Daniel (Bg)
Last Version  0.1.9
Platform  AVR
License  GPLv3+
Download  SVN browse

An english version of this article is available on AVR-Huffman/en.

About[Bearbeiten]

AVR-Huffman ist eine Implementierung der Huffman-Kompression bestehend aus 3 Teilen

  • Tool zum komprimieren binärer Daten (huffman-encode; Host; geschrieben in portablen C)
  • Tool zum dekomprimieren der von huffman-encode erzeugten Daten (huffman-decode; Host; geschrieben in portablen C)
  • Implementierung der Dekompression für AVR-Microcontroller (verfügbar in C und optimiertem Assembler)

Facts[Bearbeiten]

  • 468 Bytes in Assembler
  • C-Interface (avr-gcc)

API[Bearbeiten]

typedef ... huffman_dec_ctx_t;
void huffman_dec_init(huffman_dec_ctx_t* ctx, uint16_t(*rb_func)(uint16_t));
void huffman_dec_set_addr(huffman_dec_ctx_t* ctx,uint16_t addr);
uint16_t huffman_dec_byte(huffman_dec_ctx_t* ctx);

huffman_dec_ctx_t[Bearbeiten]

Der Kontext-Typ definiert die Speicherstruktur für die Daten einer Huffman-Dekompressionsinstanz. D.h. eine Variable von diesem Typ kann die Informationen Speichern die für die Dekompression benötigt werden (u.a. den Baum, bit buffer zum lesen der Daten, funktion zum Lesen der Daten).

huffman_dec_init[Bearbeiten]

Diese Funktion initialsiert eine Variable vom Typ huffman_dec_ctx_t zu der ein Pointer übergeben wird. Das zweite Argument ist ein Pointer auf eine Funktion welche aufgerufen wird wenn komprimierte Daten gelesen werden sollen.

huffman_dec_set_addr[Bearbeiten]

Diese Funktion setzt die Adresse welche der Lese-Funktion übergeben wird und nach dem Aufruf der Lese-Funktion automatisch um eins inkrementiert wird.

huffman_dec_byte[Bearbeiten]

Diese Funktion initialisiert beim ersten Aufruf mit einem neuen Kontext den Huffman-Baum und gibt das nächste dekomprimierte Byte zurück. Dies Funktion ruft bei Bedarf die Lese-Funktion auf um weitere komprimierte Daten zu lesen. Am Ende des streams wird EOF (0xFFFF) zurück gegeben.

Lese-Funktion[Bearbeiten]

Ein Pointer auf diese Funktion wird der Initialisierungsfunktion übergeben. Die Funktion soll die Komprimierten Daten lesen und bei jedem Aufruf entweder ein Byte aus dem komprimierten Datenstrom zurückgeben oder EOF (0xFFFF). Durch die Verwendung eines Funktionszeigers ermöglicht es Huffman-komprimierte Daten auf verschiedenen Medien zu speichern. So kann z.B. ein Kontext Daten aus dem Flash entpacken und ein anderer Daten aus dem EEPROM.

Dynamischer Speicher[Bearbeiten]

avr-huffman-decode alloziert dynamisch beim ersten Aufruf Speicher für den intern verwendeten Huffman-Baum. Es wird via calloc() automatisch der notwendige Speicher alloziert und bei erreichen des END-OF-FILE Markers automatisch via free() wieder frei gegeben. Der Benötigte Speicher hängt ausschließlich von der Menge der verschiedenen Symbole (Bytes) in der Ausgangsdatei ab. Es wird für jedes verschiedene Symbol 3 Byte benötigt, also im schlimmsten Fall (alle 256 Bytewerte treten auf) 768 Bytes.

Konzept[Bearbeiten]

Dateiformat[Bearbeiten]

Bemerkung: Das verwendete Format komprimiert den Huffman-Baum nicht optimal. Dies rechtfertigt sich dadurch, dass eine optimale Darstellung des Baums den Decoder komplizierter gemacht hätte. Der Overhead dürfte jedoch nur einige Bytes betragen.

Die Datei beginnt mit einem 15 bit Magic Value 0xC0 0xDE. Das letzte Bit kann 1 oder 0 sein, so kann es sein dass die ersten beide bytes auch als 0xC0 0xDF gelesen werden. die nächsten 9 Bit codieren die Anzahl der Blätter im Baum. Das letzte Blatt steht für EOF und nicht für ein Daten Byte. Es folgen anschließend immer ein Byte welches die Anzahl der Blätter der jeweiligen Ebene darstellt (beginnend bei einer Tiefe von 1) und dann die Werte der Blätter.

An die Darstellung des Baumes schließt sich unmittelbar die Binären Daten an wobei das höchstwertigste Bit das erste und das niederwertigste das letzte Bit darstellen.

Beispiel[Bearbeiten]

Der Klartext ist:

abcaaab\n

Bzw.

00000000  61 62 63 61 61 61 62 0a                           |abcaaab.|
00000008

Komprimiert sieht das dann so aus:

00000000  c0 de 05 01 61 00 04 63  0a 62 ff 68 35 e0        |....a..c.b.h5.|
0000000e

Der Baum lässt sich wie folgt graphisch darstellen: Huffman graph.png