mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik schneller und kostenloser (De-)Komprimierungsalgorithmus


Autor: Werner Maier (wmaier)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,
ich suche einen schnellen und kostenlos verwendbaren 
Komprimierungsalgorithmus in C ähnlich dem LZO oder NRV von 
oberhumer.com, welcher für eingebettete Systeme geeignet ist. Also einen 
Algorithmus der wenig Speicher im Flash und RAM sowie geringe 
Rechenleistung für die Dekomprimierung benötigt. Die Komprimierung hat 
keine Speicher und Rechenleistungsbegrenzungen. Im konkreten 
Anwendungsfall soll eine hex-Datei auf einem Desktop PC komprimiert 
werden und dann über eine Schnittstelle an einen Mikrocontroller 
übertragen werden.Dieser soll die Daten möglichst schnell entpacken 
können. Die o.g. Algorithmen scheinen diese Kriterien zu erfüllen sind 
jedoch nicht kostenlos. Kann mir jemand einen anderen Algorithmus in C 
nennen, bei dem keine Lizenzkosten anfallen? Inwiefern eignen sich 
Algorithmen wie RLE oder Huffman?
Gruß
Werner Maier

Autor: holger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Im konkreten
>Anwendungsfall soll eine hex-Datei auf einem Desktop PC komprimiert
>werden und dann über eine Schnittstelle an einen Mikrocontroller
>übertragen werden.

Übertrage keine HEX Datei sondern eine BIN Datei.
Das ist schon mal ungefähr dreimal schneller.
Dekomprimieren sparst du dir auch.

Autor: Tcf Kat (tcfkat)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Yo, nur sollte man dann das Protokoll mindestens mit CRC absichern...

Autor: Μαtthias W. (matthias) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi

definiere µC. Mit der zlib (http://www.zlib.net/) kommt eine 
Minialmalversin des deflate Algorithmus (IIRC in puff.c) der laut Doku 
so um die 4k Stack und sonst nichts braucht. Für einen Mega8 sicher 
nicht geeignet aber für einen nicht gerade winzingen ARM schon.

Matthias

Autor: Pedobear (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert

Autor: Werner Maier (wmaier)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,
schonmal danke für die Antworten.
zu Holger und Tcf kat:
Die Hex -Datei besteht ja nur aus 0-9 und A-F. Das repräsentiert 0000 - 
1111. Diese Nullen und Einsen werden auch so also quasi binär 
übertragen. Die werden im Kontroller nicht als z.B. ASCII "A" 
dargestellt (also nicht als 0x41 oder 65dez). Somit üertrage ich ja 
binär.

zu Matthias:
zlib hört sich auf den ersten Blick interessant an. Ich werde mal 
genauer recherchieren. Ich hoffe der ist auch schnell genug und 
verbraucht nicht zu viel Speicher zum Dekomprimieren. (ARM ähnlich ist 
der Prozessor ca.100Mhz)

Ist deflate nicht gleich komprimieren und inflate gleich dekomprimieren? 
Ich brauche den schnellen und speicherschonenden Algorithmus bei der 
Dekomprimierung als bei inflate.

zu Pedobear:
Die Algortihmen von oberhummer hatte ich teilweise schon in der Frage 
erwähnt. Leider kann ich diese nicht verwenden, da sie unter eine Lizenz 
stehen und ich einen absolut freien Algorithmus verwenden möchte.

Gruß
Werner Maier

Autor: Tcf Kat (tcfkat)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Also nutzt Du den gesamten Wertebereich eines übertragenen Characters 
aus, oder wie verstehe ich das?
Bei dem Algorithmus ist es wichtig, dass das Dekomprimieren nicht zuviel 
Rechenleistung frisst. Sonst ist der lahme µC langsamer als die 
Übertragung. Ich würde erstmal auf dem PC verschiedene Algorithmen 
testen. Soviel ist bei Binär nicht drin, wenn der Kompressionsfaktor 
nicht hoch ist, lohnt der Aufwand nicht (ich wollte das mal auf einem 
16MHz 386EX implementieren, fallen gelassen, die Kiste war zu lahm). 
Wieviel Daten musst Du denn übertragen, und mit welcher Baudrate?

Autor: Rene (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wo kein Kläger da kein Richter. Mal ehrlich ,selbst wenn das Produkt wo 
der Mikrokontroller drauf ist vermarktet wird ,ist es nahezu unmöglich 
zu beweisen welcher Algorithmus für ein bestimmtes Problem verwendet 
wurde. Man kommt nun nichtmal an den Binärcode heran ,da es 
Auslesesperren bei vielen Controllern gibt. Der Patentinhaber müßte 
einen Millionenschwehren Aufwand betreiben um den Speicher des 
Controllers auszulesen(Lasercutter, Elektronenmikroskop, Nano Equipment 
u.s.w.) . Dann würde er sich womöglich auch noch selber strafbar machen. 
Also rein mit dem LZW und gut isss.

Autor: Andreas K. (a-k)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Rene: Ist dir klar, dass du hier grad dazu aufforderst, gegen die GPL 
zu verstossen?

Autor: Rene (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das verstößt nicht gegen die GPL ,sondern hebelt Softwarepatente aus.LZW 
und RLE dienen nicht dazu der Menschheit freie Informationen zu 
verschaffen, sondern einzig und allein den Patentinhabern fette 
Geldeinnahmen zu ermöglichen. GPL ist für mich was anderes. Wer LZW und 
RLE benutzen möchte wird zur Kasse gebeten. Eine Unverschämtheit finde 
ich. Es gibt eine ganze reihe von Leuten die scheeren sich um solche 
Patente ein Scheißdreck. Oder würdet Ihr in Euren Anwendungen z.B. auf 
den Fortschrittbalken verzichten wollen? Der ist nämlich auch patentiert 
worden und Theoretisch müßtet Ihr Geld bezahlen wenn Ihr einen solchen 
Fortschrittbalken in einer GUI anzeigt.

Autor: karla (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die GPL ist eine Lizenz für ein Stück Software.
Ein Algorithmus an sich wird nicht durch die GPL geschützt sondern "nur" 
die Implementierung.
Der Algorithmus an sich kann durch Kopplung an ein Gerät oder Ähnliches 
mittels Patent geschützt werden (oder neuerdings mittels 
Softwarepatent).
Fast alle effizienten verlustfreien Kompressionsverfahren sind 
inzwischen nicht mehr durch Patente geschützt, da abgelaufen.

Autor: Andreas K. (a-k)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Werner führte an, dass er LZO und UCL aufgrund der Lizenzbedingungen 
nicht verwenden kann. Was er nicht erwähnte: Bei dieser Lizenz handelt 
es sich um die GPL.

Autor: karla (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja Du hast recht. Wenn er fertige Software in einem kommerziellen 
Produkt einsetzen will, geht das natürlich nicht mit GPL Software.
Er könnte aber mit dem Autor Kontakt aufnehmen und von diesem eine 
Lizenz erwerben - trotz GPL.

Autor: Dietmar E (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Die Hex -Datei besteht ja nur aus 0-9 und A-F. Das repräsentiert 0000 -
1111. Diese Nullen und Einsen werden auch so also quasi binär
übertragen

Die Hex-Datei wird, wie alle Daten, zwar binär übertragen, aber um ein 
Byte hexadezimal zu codieren, werden zwei Bytes (z.b. ff für 255) 
benötigt, also fallen doppelt so viele Bytes/Daten an. Es wäre etwas 
unsinnig, die Daten vor dem Packen erst zu verdoppeln, oder? Das gilt 
zumindest dann, wenn man den üblichen 8bit-ASCII-Zeichensatz verwendet.

Autor: opacer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Seit wann ist LZW wieder patentrechtlich geschützt? Die Patente sind 
2004 weltweit ausgelaufen und können demnach frei genutzt werden.

Autor: Tcf Kat (tcfkat)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Dietmar E (Gast): Das war ja eben meine Frage, ob binär oder ASCII 
übertragen wird. In ersterem Fall ist die Angabe .hex-File irreführend.

Autor: Werner Maier (wmaier)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

Zu hex-Datei:
Die Datei liegt zwar in dem, mit einem einfachen Texteditor, leicht 
auslesbaren ASCII Zeichen von 0-F, wird dann aber binär übertragen. D.h. 
ein „A“  wird als 1010 übertragen und nicht als ASCII 0x41=1000001b! 
Also soll also eine Datei mit lauter „0-Fs“ nach der Komprimierung 
kleiner sein aber auch aus „0-Fs“ bestehen. Sorry, für die Verwirrung.

Zu Dietmar E:
Ein Byte sind 8Bit. 4Bits werden mit den Zeichen 0-F gekennzeichnet 
(z.B. 0xF = 1111b). Also ist ein Byte mit genau zwei Zeichen aus 0-F 
festgelegt, also 0x00=00000000b bis 0xFF=11111111b. Diese werden so 
binär übertragen. Ich verstehe das Problem da nicht!

Geschwindigkeit des Rechners:
Die Rechenleistung ist für einen Mikrocontroller recht hoch. Im 
Allgemeinen ist der Prozessor wohl mit einem ARM1020E zu vergleichen: 
100-200MHz. RAM Speicher weiß ich gerade nicht, aber es wird etwas 
besser sein als der ARM1020E.

Zur Lizenz:
Was wäre, wenn ein Mitarbeiter da mal etwas, ob gewollt oder ungewollt, 
verrät? Da möchte ich keine Risiken eingehen. Es sollen keinerlei Kosten 
oder Verpflichtungen geben! (Die GPL ist übrigens auch nicht frei von 
Kosten!).
Laut http://de.wikipedia.org/wiki/LZW sind die Lizenzen für LZW und 
ähnliche abgelaufen, gilt das nun auch oder nur für den implementierten 
Algorithmus bzw. Sourcecode?

Die eigentliche Frage!!!!!!:
Bisher sind einige Algorithmen genannt worden. Zlib, LZW und RLE fand 
ich am interessantesten. Weiß nun jemand, welcher am besten für eine 
Komprimierung für quasi binäre Daten geeignet sind, welche schnell und 
ressourcenschonend sind und wo man evtl. schon c-Code findet?

Autor: opacer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich habe LZW schonmal auf einem ARM implementiert (allerdings ARM9). 
Läuft super, hab da aber auch einiges an speicher und rechenleistung. 
Vorteil für mich ist die möglichkeit einen Stream zu komprimieren / 
dekomprimieren und nicht einiges an Daten vorzuhalten.

Wenn du eine Implementierung von LZW findest - egal in welcher sprache - 
und der quelltext ist unter GPL, dann darfst du das ganze nicht in 
close-source nutzten. Ist der Source unter der LGPL dann schon.
Wenn du den Algorithmus selber in Source packst, was nicht so schwer 
sein sollte, dann darfst du ihn natürlich nutzen.

Autor: Werner Maier (wmaier)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo opacer,
kann man denn beim LZW genau vorhersagen oder bestimmen wie groß der 
Speicherverbrauch beim Entpacken ist. Damit meine ich nicht die 
Entkomprimierten Daten, sondern die temporären Daten die im RAM liegen 
wie z.B. die Diktionaries die angelegt werden.
Gruß
Werner

Autor: Dietmar E (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> D.h. ein „A“  wird als 1010 übertragen

Du erfindest einen eigenen Zeichensatz mit 4 bit pro Zeichen? 
Normalerweise denkt man nicht in der der Kategorie "wie übertrage ich 
ein A", sondern in der Kategorie "wie übertrage ich ein Byte". Am Anfang 
hast Du geschrieben, dass eine Hex-Datei komprimiert und übertragen 
werden soll. Die richtige Lösung wäre, den Schritt von Hexdatei zu 
Binärdatei vor dem Komprimieren vorzunehmen (und damit auch vor dem 
Übertragen).

Autor: Werner Maier (wmaier)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,
am besten wir vergessen den Namen hex-Datei und sprechen nur noch von 
einer binär Datei die komprimiert werden muss! War wohl etwas 
umständlich beschrieben.
Gruß
Werner

Autor: Dietmar E (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Komprimierung für quasi binäre Daten

Gibt es nicht. Meinst Du quasi-zufällig? Entscheidend ist die Struktur 
der Daten. Bilder, Audiodaten, Messwerte usw. haben jeweils Strukturen, 
die man ausnutzen kann. RLE biete sich beispielsweise an, wenn sich im 
Datenstrom ein Byte oft wiederholt - das wird bei Strichgrafiken der 
Fall sein (Hintergrund). Bei Audiodaten und Messwerten könnte man die 
Stetigkeit der Daten ausnutzen und nur die Differenzen komprimieren. 
Aber wenn es in den Daten keine deutliche Struktur gibt, also 
quasi-zufällige Daten vorliegen, dann wird man einen 
nicht-spezialisierten Algorithmus nehmen. Davon gibt es viele:
http://de.wikipedia.org/wiki/Liste_der_Datenkompre...

Autor: opacer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

mit dem Algorithmuss kannst du ja auch was spielen. D.h. du kannst in 
der Implementierung ja die Wörterbuchgrößte beschränken auf z.B. 1KB 
oder weniger. Danach werden keine neuen mehr aufgenommen bzw. ein neues 
Wörterbuch erstellt. Aber klar ist auch wenn das Wörterbuch zu klein 
ist, dann wird nicht mehr viel komprimiert. Zu groß bringt auch nicht 
sonderlich viel.

Am besten du nimmst den LZW als Algorithmus und spielst was rum und 
implementierst den so wie du ihn brauchst. Evtl. kann man vorher noch ne 
Run-Length-Komprimierung machen..

Grüße

Autor: Werner Maier (wmaier)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,
bei den Daten handelt es sich teilweise um kompilierten C-Code. LZW oder 
zlib überhaupt möglich binär-Dateien zu verarbeiten?
Gruß

Autor: Tcf Kat (tcfkat)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Werner Maier: Sorry, das mit den 100MHz hatte ich zu spät gelesen. Wie 
gesagt, ich hatte mal was auf einem 16MHz 386EX (Embedded Version des 
386SX) gemacht, aber wegen Ineffizienz verworfen.
Wie schon von einigen Vorrednern gesagt, der Kompressionsfaktor, und 
damit der Sinn oder Unsinn der Aktion, hängt sehr stark davon ab, 
welcher Art die Daten sind - ausführbarer Code, oder schlecht 
komprimierte Daten wie TIFF-Bilder unterscheiden sich in der 
Komprimierbarkeit um Welten! Wenn Du viele gleiche Bytes hintereinander 
hast, wirst Du mit einer simplen Lauflängenkomprimierung schon sehr gute 
Resultate erzielen, die frisst auch nicht viel Ressourcen. Deswegen 
empfehle ich Dir, erstmal mit den verfügbaren Sourcen auf dem PC 
Kompressionstest zu machen, um den Sinn abschätzen zu können. Was der 
Dekompressor an Ressourcen braucht, lässt sich sicherlich durch einen 
Debugger, oder durch Modifikation der Sourcen (z.B. malloc abfangen) 
heraus bekommen. Ich habe mich mal vor über 15 Jahren mit 
Kompressionsalgorithmen beschäftigt, ich habe noch irgendwo Sourcen zu 
verschiedenen Algorithmen, die liegen aber auf einer alten HDD, die 
müsste ich erstmal heraussuchen. Wenn Du Interesse hast, kann ich das 
mal machen.

Autor: Μαtthias W. (matthias) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi

deflate ist der allgemeine Begriff für den in der zlib verwendeten 
Algorithmus. Und ich meinte nicht die komplette zlib sondern nur die 
simple Implementierung der Entpackroutinen die sich im Source der zlib 
finden. Zum packen verwende ich am PC die zlib und zum entpacken im 
Zielsystem eben die geannnte Implementierung. Diese entpackt die Daten 
mit etwa 10MB/s auf dem von mir verwendeten Prozessor (~500MHz ARM)

Matthias

Autor: Dietmar E (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> [mit] LZW oder zlib überhaupt möglich binär-Dateien zu verarbeiten?

Ja. Diese Packer sehen Textdateien nur als Zahlenfolge und damit 
genauso, wie binäre Dateien (d.h. wie Audio-Datein, Grafiken, 
kompilierter Code usw.). Die packen alles. Am Computer gibt es auf der 
unteresten Ebene der Speicherhardware, der CPU und der Dateien nur 
Zahlen. Dass manche Zahlen tatsächlich nur Zahlen sind und dass andere 
Zahlen für Buchstaben (oder Töne oder Grafiken usw.) stehen, ergibt sich 
nur durch die Art und Weise, wie diese Zahlen von der Software 
verarbeitet werden, d.h. durch das angenommene, dahinterstehende 
Codiersystem. Die erwähnten Packer nehmen kein Codiersystem an, denen 
reicht es, die Zahlen als Zahlen zu sehen. Also können sie alles packen. 
Als "binäre" Dateien bezeichnet man übrigens alle Dateien, die nicht 
Textdateien sind, d.h. eine Abfolge von Zahlen, die sich nicht durch 
eine Zeichentabelle interpretieren lässt. Natürlich folgen auch die 
meisten binäre Dateien irgendeiner Codierung, z.B. könnte jede Zahl für 
einen Farbwert stehen. "Binäre Dateien" ist also nur ein Oberbegriff.

Autor: Werner Maier (wmaier)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,
@ Tcf Kat:
Das mit den Source wäre sehr nett. Ich würde ja gerne einige Algorithmen 
ausprobieren dafür muss ich ja erstmal die Sourcen haben. 
Selbstprogrammieren würde da wohl recht lange dauern.
Zu zlib habe ich aber Source im Netz gefunden (www.zlib.net). Das werde 
ich auch mal ausprobieren.
Gruß
Werner

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.