Daten dekomprimieren für AVR - LHA,GZIP o.ä.

[Uwe S. (de0508)]

Guten Morgen,

hat jemand mal eine Routine für avr gcc gesehen, um komprimierten Text 
im Datensegemnt vor der Ausgabe zu dekomprimieren ?

So etwas wie LHA für Unix Systeme:

http://de.sourceforge.jp/projects/lha/downloads/11617/lha-1.14i-ac20040929.tar.gz/

Ich habe keine Problem eine Binär-Datei in das Datensegment zu legen und 
dann zu Linken, es geht wirklich nur um eine kleine Routine, die einen 
komprimierten Bereich im Flash wieder dekomprimiert.
D.h. natürlich der Text muss in Päckchen im SRAM stehen und wird von 
dort ausgegeben (Software Uart).

Zielsystem atTiny85, 8K Flash, max. 512 Byte Ram

[Peter S. (psavr)]

>es geht wirklich nur um eine kleine Routine, die einen
>komprimierten Bereich im Flash wieder dekomprimiert.
Die Routine wird nicht klein genug sein, um in dein 8kB Zielsystem zu 
passen, zudem wird auch einiges an RAM benötigt.

Ich nehme an, der Controller sollte noch was anderes tun...

Ein sehr simple und machbare Kompression wäre RLE (RunLengthEncoding), 
aber die bewirkt nur was bei Daten mit sehr hoher Redunanz.

Die beste Lösung: Nimm ein Controller der ausreichen FLASH hat, oder ein 
externes FLASH/EEPROM mit seriellem Interface...
Unter 32..64kB wird die Routine mehr Speicherplaz belegen, als dass Du 
einsparen kannnst

[Uwe S. (de0508)]

Danke Peter,

das waren auch meine Vermutung.

Leider kann ich in dieser Anwendung nichts ändern, so dass ich keine mit 
dem restlichen Platz auskommen muß.

Auch mit LZO - Lempel-Ziv-Oberhumer habe ich schon experimentiert:

http://de.wikipedia.org/wiki/Lempel-Ziv-Oberhumer
http://www.oberhumer.com/opensource/lzo/

Solong.

[Uwe S. (de0508)]

Hallo Mitleser,

dieses Projekt habe ich gerade noch gefunden:

*heatshrink: An Embedded Data Compression Library*

http://spin.atomicobject.com/2013/03/14/heatshrink-embedded-data-compression/

und muss es mal testen..

[Falk B. (falk)]

@ Uwe S. (de0508)

>hat jemand mal eine Routine für avr gcc gesehen, um komprimierten Text
>im Datensegemnt vor der Ausgabe zu dekomprimieren ?

Also viele kleine Strings?

>So etwas wie LHA für Unix Systeme:

>http://de.sourceforge.jp/projects/lha/downloads/11...

Die meisten Kompessormethodenfunktionieren nur gut, wenn sie größere 
Datenblöcke bearbeiten können.

>Zielsystem atTiny85, 8K Flash, max. 512 Byte Ram

Ich würde in Richtung Lochstreifenkodierung schauen. Dann reichen 
vielleicht 5 Bit/Char. Oder eine einfache Huffmannkodierung, sowas hab 
ich vor Ewigkeiten mal auf nem 68HC11 gemacht, lief ganz gut, war klein 
und relativ schnell.

Puhhh, noch gefunden, das war Ende 2000 8-0

[Uwe S. (de0508)]

@Falk Brunner,

danke Falk.

Eine einfachste String Zusammenfassung hatte ich schon mal getestet:

Alle Zeichenketten die mind. 2 malig vorkommen und deren Länge länger 
wie 4 Zeichen sind, werden durch ein TOKEN ersetzt.
Dieses TOKEN ist natürlich ein Byte und wird direkt im eigentlichen Text 
eingefügt.
Ich habe TOKEN E{ 255, 254, ... } gewählt.

Somit ergibt sich eine Tabelle/ Array:

{ { TOKENn, STRINGn},
  { TOKENn-1, STRINGn-1},
  // usw.
};

Jetzt ist auch klar was bei der Ausgabe passiert: nach diesen Token wird 
gesucht und dann der ursprüngliche Text ausgegeben.

Da mein ursprünglicher Text KONSTANT ist, ist diese Art der 
Komprimierung nur bei längeren Textstücken effizient.

[Johann L. (gjlayde)]

Allzu kompliziert darf der Algorithmus nicht werden; ansonsten geht dir 
rucki zucki der Platz auf dem µC aus...

Mit einem ad-hoc brute-force Ansatz kommt man auf eine 
Komprimierungsrate von 20%-25% für "normalen" Text; die Decodierung 
verschlingt ca. 40-55 Bytes auf einem AVR — je nachdem, ob man diese in 
Assembler oder C schreibt.

Der Gewinn pro Ersetzung ist dabei

$$\text{len} \cdot \text{num} - (\text{len} + 1 +\text{num})$$

wobei len die Länge einer Ersetzung ist und num deren Anzahl.  Der 
erste Summand ist die Anzahl der Zeichen vor der Ersetzung; der zweite 
(negative) die Anzahl benötigter Zeichen danach.

Mit diesen Randwerten fängt die Komprimierung ab ca. 300 Zeichen an sich 
zu lohnen; wobei die Struktur des Textes natürlich eine Rolle spielt 
(Umlaute, viele kleinere Texte oder 1 großer, etc.)