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
>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.
Yo, nur sollte man dann das Protokoll mindestens mit CRC absichern...
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
Angehängte Dateien:
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
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?
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.
@Rene: Ist dir klar, dass du hier grad dazu aufforderst, gegen die GPL zu verstossen?
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.
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.
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.
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.
> 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.
Seit wann ist LZW wieder patentrechtlich geschützt? Die Patente sind 2004 weltweit ausgelaufen und können demnach frei genutzt werden.
@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.
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?
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.
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
> 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).
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
> 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_Datenkompressionsprogramme
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
Hallo, bei den Daten handelt es sich teilweise um kompilierten C-Code. LZW oder zlib überhaupt möglich binär-Dateien zu verarbeiten? Gruß
@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.
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
> [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.
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
Thread beobachten
Seitenaufteilung abschaltenBitte 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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.