AVR-Huffman

         

AVR-Huffman Release status: stable [box doku]
Description	Dekompression von Huffman komprimierten Daten zur Laufzeit
Author(s)	Daniel (Bg)
Last Version	0.1.0 ()
Platform	AVR
License	GPLv3+
Download	SVN browse

About

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)

API

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

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

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

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

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.

Lese-Funktion

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.

Dateiformat

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

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: