Forum: Mikrocontroller und Digitale Elektronik Datenkomprimierung mit Sonderwünschen


von Thomas B. (thomasbr)


Lesenswert?

Hallo Zusammen,

folgendes Problem:
Ich suche ein Komprimierungsverfahren um eine etwa 5 MB große Datei zu 
komprimieren und diese anschließend Blockweiße über eine serielle 
Leitung an einen MUC zu übertragen. Dort müsste diese dann Blockweise 
dekomprimiert werden, da nicht genügend RAM vorhanden ist um diese 
komplette zwischen zu puffern und anschließend zu entpacken bevor sie in 
den Flash geschrieben wird. Kennt ihr ein Kompressionsverfahren das dazu 
fähig ist?

Ich hab mir das LZMA SDK angeschaut bin mir aber nicht sicher ob das 
dazu in der Lage ist. Dort wird zwar in der Spec immer von Stream 
Kompression geredet und nach Wikipedia ist das genau das was sich suchen 
würde. Aber in einem Forenbeitrag dazu wurde geschrieben, dass dies 
nicht möglich ist und die Spec beschreibt auch keinen Fall dazu. Kennt 
sich jemand mit diesem Kompressionsverfahren aus bzw. hatte jemand schon 
ein ähnliches Problem bzw. kennt ihr einen Verfahren dass genau das 
kann. Bevorzugte Programmiersprache wäre C.

Danke Schon mal
Grüße

von Peter II (Gast)


Lesenswert?

es kommst auf den Inhalt der Datei an, nicht jeden lässt sich 
Datenkomprimieren.

du kannst jeden jedes Verfahren verwenden (ZIP, LZW, GZIP, RAR) mit 
jedem kann man einen Block komprimieren und dann versenden. Du musst dir 
nur ein kleines Protokoll für die Übertragung einfallen lasse.

Je kleiner die Böcke werden, desto weniger gut lässt es sich 
komprimieren.

von G. H. (schufti)


Lesenswert?

ach, wozu das Rad neu erfinden:

Xmodem, Ymodem, Zmodem + deren Derivate ... u.a.m.

http://web.cecs.pdx.edu/~rootd/catdoc/guide/TheGuide_226.html

Implementierungen sind zu 100% im Netz zu finden.

: Bearbeitet durch User
Beitrag #5013222 wurde vom Autor gelöscht.
von Thomas B. (thomasbr)


Lesenswert?

Ich suche ein Komprimierungsverfahren kein Transportprotokoll :-). Das 
Übertragungsprotokoll so wie das Übertragungsmedium sind mir vorgegeben.

von Peter II (Gast)


Lesenswert?

Thomas B. schrieb:
> Ich suche ein Komprimierungsverfahren kein Transportprotokoll

es gibt für so ziemlich jedes Komprimierungsverfahren eine C 
Implementierung - versteht dein Problem nicht.

von c.m. (Gast)


Lesenswert?

ich hab nur mal das LZW verfahren nachprogrammiert, denke aber das für 
alle kompressionsverfahren (außer RLE) die gleiche problematik entsteht: 
es werden on the fly speicherplatzverbrauchende dictionarys erstellt, 
und die kompression funktioniert erst, wenn genügend repetitive daten 
vorhanden sind.
kleine blöcke einzeln zu dekomrimieren wird also nicht viel bringen, und 
bei größeren blöcken brauchst du immernoch speicherplatz fürs 
dictionary.

von Thomas B. (thomasbr)


Lesenswert?

Ja es gibt für so gut wie jede eine C Implementierung. Die sind auch 
alle schön und gut solange die Anforderung ist komplette Datei 
komprimieren und anschließend eine komplette Datei dekomprimieren, dann 
ist die ganze Sache kein Problem.

Hat man nun aber die Anforderung, wegen zu wenig Speicher, dass 
dekomprimieren partial zu machen, also wenn man nicht die komplett 
komprimierte Datei zu Verfügung steht dann sieht die Sache anders aus.

Wie gesagt ich hab mir das LZMA SDK schon angeschaut komprimieren und 
dekomprimieren einer kompletten Datei kein Problem. Wo bei mir aber 
gerade das Verständnis aufhört wie mach ich das blockweise also bei 
streams. Die Spec ist da verwirrend es wird von Streams geredet aber 
alle Beispiele die man findet beziehen sich immer auf komplette Dateien.

von Peter II (Gast)


Lesenswert?

Thomas B. schrieb:
> Ja es gibt für so gut wie jede eine C Implementierung. Die sind auch
> alle schön und gut solange die Anforderung ist komplette Datei
> komprimieren und anschließend eine komplette Datei dekomprimieren, dann
> ist die ganze Sache kein Problem.

das ist doch Unsinn, Du kannst die Funktion einfach sagen die "Datei" 
ist nur 100byte groß (obwohl sie in Wahrheit 5Mbyte) groß ist und dann 
packt er die 100byte.

Die Funktionen müssen ja nicht die echte Datei kennen.

von Torsten R. (Firma: Torrox.de) (torstenrobitzki)


Lesenswert?

Hallo Thomas

Thomas B. schrieb:
> Ich hab mir das LZMA SDK angeschaut bin mir aber nicht sicher ob das
> dazu in der Lage ist. Dort wird zwar in der Spec immer von Stream
> Kompression geredet und nach Wikipedia ist das genau das was sich suchen
> würde.

Warum sollte das nicht nicht möglich sein? In der Regel werden nicht die 
kompletten Daten benötigt, um mit dem Entpacken anzufangen. Ich habe mal 
einen CAN Bootloader geschrieben, der die zlib verwendet hat und bin 
dabei auf keine unlösbaren Probleme gestoßen.

Hast Du Deine Daten den schon mal dahin gehend untersucht, ob die sich 
überhaupt sinnvoll komprimieren lassen? Einfach mal zippen und die 
Größen miteinander vergleichen?

Ich arbeite gerade an einem Bluetooth SWD Adapter und habe mal 
untersucht, wie sich binaries für ARM Cortex komprimieren lassen. Wir 
sind da nur auf ca. 20% (Reduktion) gekommen.

von Thomas B. (thomasbr)


Lesenswert?

Hallo Torsten,

die Komprimierungsrate ist ziemlich gut wenn ich die komplette Datei 
packe komme ich von 5 MB runter auf kleiner 1 MB. Mir ist klar das das 
irgendwie gehen muss, das wie ist gerade mein Problem. Ich hab die 
letzten beiden Tage so viel widersprüchliche Informationen gelesen, dass 
ich im Moment einfach nur verwirrt bin.

Mein erster Plan war jedes Packet das übertragen werden soll einzeln zu 
packen und dann dieses wieder zu entpacken. Das hab ich aber schnell 
wieder verworfen, da das nicht den gewünschten Erfolg hatte.

Aktueller Plan ist komplettes File zu packen dieses dann packetweise zu 
entpacken und in den Flash zu speichern. Und bei der Dekompression 
hapert's gerade am allgemeinen Verständnis dafür.

Die Aussage, dass das eigentlich gehen müsste hilft aber schon mal 
weiter. Danke!

von Horst (Gast)


Lesenswert?

Thomas B. schrieb:
> Aktueller Plan ist komplettes File zu packen dieses dann packetweise zu
> entpacken und in den Flash zu speichern. Und bei der Dekompression
> hapert's gerade am allgemeinen Verständnis dafür.

Du suchst also ein Komprimierungsverfahren, bei dem Du die komprimierte 
Datei zerstückeln und diese Stücke dann einzeln entpacken kannst?
Wo soll da der Unterschied zu

Thomas B. schrieb:
> jedes Packet das übertragen werden soll einzeln zu
> packen und dann dieses wieder zu entpacken.

sein?

Du brauchst ja in jedem Teilpaket alle Informationen zum entpacken, das 
kann aber nur funktionieren, wenn beim Packen schon die Paketgröße 
festgelegt wird und jedes Paket einzeln verarbeitet wird. Womit Du 
wieder beim 'zerstückeln und dann packen' bist.

von Torsten R. (Firma: Torrox.de) (torstenrobitzki)


Lesenswert?

Thomas B. schrieb:

> Aktueller Plan ist komplettes File zu packen dieses dann packetweise zu
> entpacken und in den Flash zu speichern. Und bei der Dekompression
> hapert's gerade am allgemeinen Verständnis dafür.

Das klingt vernünftig. Guck Dir doch einfach mal die API, der von Dir 
ausgesuchten Library, an und guck, ob das passt (auch wenn Du blockweise 
schreiben möchtest, sind die Daten über die serielle Schnittstelle ein 
stream).

Versuch mal, dass von Hinten zu denken: Das Flash braucht Inhalt und 
dekomprimiert solange aus den über die serielle Schnittstelle kommende 
Daten, bis ein Flash-Bock voll ist und schreibt den dann.

mfg Torsten

von Christian M. (Gast)


Lesenswert?

G. H. schrieb:
> Zmodem

Thomas B. schrieb:
> Ich suche ein Komprimierungsverfahren kein Transportprotokoll

ZModem ist Beides!

Gruss Chregu

von Bitwurschtler (Gast)


Lesenswert?

Thomas B. schrieb:
> Hat man nun aber die Anforderung, wegen zu wenig Speicher, dass
> dekomprimieren partial zu machen, also wenn man nicht die komplett
> komprimierte Datei zu Verfügung steht dann sieht die Sache anders aus.

Zum dekomprimieren braucht es keine komplette Datei, du verwechselst das 
mit Komprimieren. Siehe Videostreaming

von Frank M. (ukw) (Moderator) Benutzerseite


Lesenswert?

Thomas B. schrieb:
> Die sind auch alle schön und gut solange die Anforderung ist komplette
> Datei komprimieren und anschließend eine komplette Datei dekomprimieren,

Fast alle Komprimierungsverfahren arbeiten blockweise. Bei einigen ist 
die Blockgröße sogar einstellbar.

Meinst Du, dass gängige Komprimierungsprogramme eine 4 GB große Datei 
erst komplett ins RAM laden, bevor sie anfangen, diese zu komprimieren? 
Da bist Du im Irrtum.

Vielmehr ist es so, dass Daten nur in festen Blöcken komprimiert werden. 
Einige Komprimierungsprogramme wechseln je nach Block-Inhalt sogar ihre 
Taktik, wie sie den Block komprimieren.

Genauso kann das Dekomprimierungsprogramm die Daten blockweise 
entpacken. Das ging mit den oben erwähnten [xyz]modem-Verfahren vor 
vielen Jahren schon mit lächerlich wenig RAM.

: Bearbeitet durch Moderator
von Bitwurschtler (Gast)


Lesenswert?

c.m. schrieb:
> kleine blöcke einzeln zu dekomrimieren wird also nicht viel bringen, und
> bei größeren blöcken brauchst du immernoch speicherplatz fürs
> dictionary.

Die Größe des dictionaries aka symboltabelle sollte nicht besonders von 
der blocklänge abhängen.

von Tom (Gast)


Lesenswert?

Wie gross sind denn die Häppchen die übertragen werden sollen? Und 
wieviel Platz für die ZUsatzinformationen (Dictionary) hast Du auf dem 
uP?
Wenn die Komprimierung nicht nur run length codierung oder ähnliches 
ist, muss ja eine Art Dictionary mit übertragen werden und auf dem uP 
permanet gespeichert werden. Wieviel Platz hast Du dafür?

Da Du schon versucht hast die Daten häppchenweise zu komprimieren, und 
der Erfolg nicht so dolle war, wird das wohl schwierig.
Viel Erfolg!

von Silvio G. (technofreak)


Lesenswert?

Also ich würde nach folgendem Schema vorgehen:

Komprimierung:
1 gesamte Datei untersuchen und Dictionary erstellen
2 Datei komprimieren und in Teildateien abspeichern
3 Dictionary übertragen
4 Teildateien übertragen
5 Schritt 4 bis alles übertragen

Dekomprimierung:
1 Dictionary empfangen
2 Teildatei empfangen
3 Teildatei dekomprimieren
4 Daten abspeichern
5 Schritt 2 bis alles empfangen

Die Größe der Teildateien muss sich danach richten, wie viele Daten der 
µC in einem Durchgang dekomprimieren und abspeichern kann. Das erfordert 
eine Übertragungsfunktion die mit unterschiedlich großen Datenmengen 
klar kommt.

von Thomas B. (thomasbr)


Lesenswert?

Silvio G. schrieb:
> Also ich würde nach folgendem Schema vorgehen:
>
> Komprimierung:
> ....
>
> Dekomprimierung:
> .....
>

das ist der plan :)

von Frank M. (ukw) (Moderator) Benutzerseite


Lesenswert?

Thomas B. schrieb:
> das ist der plan :)

Dann verrate doch mal, wieviel RAM Dein System zur Verfügung hat, also 
wie groß die Summe von (Dict + Datenblock) werden darf.

Oder möchtest Du hier eine Universallösung präsentiert bekommen, die von 
2 Byte bis 2 GB RAM funtioniert?

Und warum möchtest Du die Übertragung überhaupt komprimieren? 
Zeitersparnis? Oder gibt es noch andere Gründe?

: Bearbeitet durch Moderator
von Lutz H. (luhe)


Lesenswert?


von Peter II (Gast)


Lesenswert?

wenn ich das hier lese:

> die Komprimierungsrate ist ziemlich gut wenn ich die komplette Datei
> packe komme ich von 5 MB runter auf kleiner 1 MB.
kommt mir fast der Verdacht, das es sich um eine Intel-HEX Datei 
handelt. Bei normalen BIN-Files für µC würde ich nicht so eine 
komprimierbarkeit erwarten.

von Frank M. (ukw) (Moderator) Benutzerseite


Lesenswert?

Peter II schrieb:
> kommt mir fast der Verdacht, das es sich um eine Intel-HEX Datei
> handelt.

Kann gut sein. Ein Verhältnis von 4:1 ist bei Hex-Dateien immer drin.

Hier würde es ja bereits reichen, die HEX-Datei auf dem Host-System zu 
interpretieren und dann in mehreren Blöcken als Binärdatei zu versenden. 
Bei 16 Nutzbytes pro 45 Byte langer Hex-Dateizeile käme man bereits auf 
einen Faktor 2,85.

Aber das ist alles Spekulation.

von Nosnibor (Gast)


Lesenswert?

Kompressionsverfahren, die beim Auspacken unbedingt die ganze Datei auf 
einmal brauchen, sind sehr selten. Es gibt moderne Verfahren, die mit 
Blöcken von mindestens 100kB arbeiten, aber die meisten Auspacker sind 
einfache Zustandsmaschinen, in die man der Reihe nach Bytes füttert (aus 
einer Datei oder eben von einer Übertragungsstrecke), und die 
gelegentlich Bytes ausgeben, meist durchschnittlich mehr als man 
reingesteckt hat. Demoprogramme zu den Algorithmen zeigen natürlich 
meist den Umgang mit Dateien, aber im Quelltext sollte der Zugang zum 
Streambetrieb leicht zu finden sein.

Zwei Ansprüche haben die meisten Auspacker aber:
1. genug Speicher fürs Dictionary. Da sollte es beim Komprimieren einen 
Parameter geben, um die Größe zu begrenzen.
2. Beliebigen Lesezugriff auf die bereits ausgepackten Daten. Wenigstens 
für ein bestimmtes "Fenster", also die letzten x kB, wobei die 
Fenstergröße auch beim Komprimieren festgelegt wird.

Das zweite sollte ja kein großes Problem sein, wenn die ausgepackten 
Daten sowieso im Flash landen.

von Thomas B. (thomasbr)


Lesenswert?

Hallo Zusammen,

ich hab es hinbekommen und wollte ein kurzes update geben. Ich bin von 
der eigentlichen Liblzma auf Xzutils umgestiegen. Beruht zwar auch auf 
der Liblzma und macht das gleiche die API bzw. die Dokumentation ist 
aber um Welten besser.

Wie es Funktioniert kann man in diesem Foreneintrag nachlesen:

https://stackoverflow.com/questions/6486745/c-lzma-compression-and-decompression-of-large-stream-by-parts


Was mich so verwirrt hat war die Sache mit dem Wörterbuch. Es gibt aber 
bei diesem Verfahren kein Wörterbuch im eigentlichen Sinne mehr das 
komplett im Voraus übertragen könnte und daraus dann die einzelnen Teile 
decodieren kann. Die Wörterbuchgröße gibt eigentlich nur die Größe des 
Sliding Windows vor und die eigentlichen Wörterbucheinträge sind der 
Codierte Text.

https://de.wikipedia.org/wiki/LZ77#Beispiel

Danke noch mal für die hilfreichen Beiträge

von (prx) A. K. (prx)


Lesenswert?

Bei manchen Komprimierungsverfahren gibt es ein Fenster in die zu 
komprimierenden bzw. dekomprimierten Daten, auf das verwiesen wird. 
Dieses Fenster muss also ins RAM passen. Zusätzlich gibt es dann noch 
Datenstrukturen, die darauf verweisen. Auch das muss in diesem Fall ins 
RAM.

Mit einem recht kleinen Speicherumfang kommt beispielsweise die LZRW 
Familie aus. Die Komprimierungsrate ist nicht die beste, aber umso 
besser ist das Tempo: http://www.ross.net/compression/lzrw1.html

von Pandur S. (jetztnicht)


Lesenswert?

Und weshalb flasht man die Daten nicht gleich wenn sie ankommen ? Dann 
koennt man sich die ganze Komprimiererei sparen ?
Falls doch Komprimierung wegen dem Uebertragungsweg .. wuerd ich 
empfehlen Entropie Komprimierung anzuschauen. Die arbeitet ohne 
Dictionary.

: Bearbeitet durch User
von Markus M. (Firma: EleLa - www.elela.de) (mmvisual)


Lesenswert?

UCL könnte das:

http://www.oberhumer.com/opensource/ucl/

Ich hatte das mal vor vielen Jahren mit Delphi eingesetzt:
https://www.yunqa.de/delphi/index

Ich konnte da einen Datenstream komrimieren und dekomprimieren.

von Christopher J. (christopher_j23)


Lesenswert?

Auch wenn der TO schon eine Lösung für sein Problem gefunden hat wollte 
ich hier noch auf LZ4 hinweisen. Das Verfahren ist extrem schnell in der 
Dekompression und auch sehr schlank in der Implementierung. Hier gibts 
einen schönen Artikel von Jens Bauer inklusive Dekompressionsalgorithmus 
in Cortex-M0 Assembler (in 84 Bytes !):
https://community.arm.com/processors/b/blog/posts/lz4-decompression-routine-for-cortex-m0-and-later

Weitere Infos findet man auf der Homepage http://lz4.github.io/lz4/

Hier gibt es noch eine etwas ältere aber mMn ordentliche Referenz zu dem 
Verfahren:
http://fastcompression.blogspot.de/2011/05/lz4-explained.html

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.