Compactor

Es gibt 3 Antworten in diesem Thema, welches 1.326 mal aufgerufen wurde. Der letzte Beitrag (10. Juli 2021 um 08:38) ist von Sokrates.

  • Ich habe ein neues Tool veröffentlicht:

    Bitte melde dich an, um diesen Link zu sehen.

    "compactor" ist ein Werkzeug für die Datenkompression von Read-only Arrays. Vorteile gegenüber üblichen Verfahren: es wird keine Zeit und kein zusätzlicher Speicher für das entpacken benötigt.

    Hier ein einfaches Beispiel zur Erläuterung. Eingabe seien zwei Arrays:

    readOnlyArray1 = 1 2

    readOnlyArray2 = 2 3

    "compactor" Ausgabe dazu:

    compressedArray = 1 2 3

    readOnlyArray1 = compressedArray+0

    readOnlyArray2 = compressedArray+1

    In diesem Beispiel wird also 1 Byte gespart. Der Zugriff auf die Daten ist vor und nach der Kompression diesselbe, es wird also keine Zeit für die Dekompression benötigt. Es wird auch kein weiterer Speicher zur Dekompression benötigt, da es eine Dekompression im herkömmlichen Sinne gar nicht gibt.

    Wird der Wert "2" im gepackten Array geändert, so ändert sich dieser Wert sowohl für Array 1 als auch für Array 2. Deshalb sollten nur Read-Only Daten für diese Methode verwendet werden.

    Zusätzlich wird "Data alignment" unterstützt, der Abstand in Relation zum Ausgabearray kann also für Eingabearrays vorgegeben werden. Alignments >1 können sehr schnell zu einem schlechten Kompressionsergebnis führen, der Einsatz von Data alignment sollte also mit Bedacht gewählt sein.

    Die Zeiten für Kompression und Dekompression sind bei dieser Methode extrem asymmetrisch, das gilt besonders für viele und umfangreiche Eingabe-Arrays. Ich habe daher viel Zeit und Mühe in eine schnelle Berechnung gesteckt (das Problem ist NP-hard). Die Geschwindigkeit sollte jetzt für Retro-Computing ausreichend sein, es kann allerdings auch ein Timeout bei der Berechnung gesetzt werden.

    Ich hoffe dieses Werkzeug ist für den einen oder die andere nützlich. Falls Ihr also verzweifelt nach ein paar zusätzlichen Bytes in Eurer Software sucht, solltet Ihr Euch dieses Werkzeug mal ansehen!

  • Version 2.0 ist veröffentlicht:

    Bitte melde dich an, um diesen Link zu sehen.

    Danke an enthusi für's testen!

    Aus den bisherigen Rückmeldungen schließe ich, dass es mitunter Verwirrung darüber gibt, wann und wie das Werkzeug eingesetzt werden soll. Deshalb möchte ich dazu noch etwas schreiben.

    Ganz prinzipiell: "compactor" ist kein Ersatz für bestehende Packer. Falls ihr also bestehende Packer einsetzen könnt, so wird mit diesen SEHR wahrscheinlich eine deutlich bessere Kompressionsrate erziehlt.

    Der Einsatz von "compactor" empfiehlt sich dort, wo KEIN bestehender Packer eingesetzt werden kann: also wenn entweder keine Zeit für das entpacken vorhanden ist oder kein Speicher dafür verfügbar ist oder beides.

    Falls Ihr also ein Programm habt bei dem Euch einfach ein paar zusätzliche Bytes gut tun würden ohne das Zeitverhalten des Programms ändern zu müssen, dann könnte Euch "compactor" möglicherweise weiterhelfen.

    Neu in Version 2:

    Ein- und Ausgabe von Binärdaten und die optionale Angabe von Fülldaten. Bei den Fülldaten kann man für jedes Eingabe-Bit angeben, ob es eine relevante Information enthält oder nicht. Beispiel: bei C64 Color Ram Werten sind nur die unteren 4 Bit relevant, in diesen sind die 16 Farben kodiert. Die oberen 4 Bits werden ignoriert. Die Farbe schwarz z. B. kann durch 0 repräsentiert werden, aber auch durch 16, 32, 64 usw. Durch Angabe der Fülldatenmaske %11110000 kann man dem Werkzeug mitteilen, dass die oberen 4 Bits Fülldaten sind. Diese Verfügbarkeit an gültigen Werte-Varianten erhöht die Chance auf Übereinstimmungen bei der Suche nach Überlappungen der Eingabefelder und damit die Kompressionsrate.

    Mir ist klar, das das ein ziemlicher Spezialfall ist bei einem Kompressionsverfahren, welches selbst schon einen Spezialfall darstellt :smile: Aber naja, ich war halt gerade tief in der Thematik und da ist das Thema halt mit "abgefallen"...

    Es würde mich freuen, wenn das Werkzeug für den einen oder die andere nützlich ist. Falls Ihr das Werkzeug verwendet würde es mich auch freuen, wenn ihr mir ein paar Details dazu nennen könntet!

    P.S.: Wer noch etwas mehr Infos haben will: im Brotkastenfreun.de-Podcast Folge 008 gehe ich ausführlich auf das Verfahren ein, welches "compactor" zu Grunde liegt.

  • Schick, so ein Verfahren benutze ich auch für die Elemente-Editoren für diverse Spiele. Die Grafikelemente, die aus Zeichen- und Farbreihen bestehen, eignen sich besonders gut für das Verschachteln. Da kann man sehr viel rausholen, wenn die Daten entsprechend aufgebaut sind.

    C64Studio: Bitte melde dich an, um diesen Link zu sehen. - Bitte melde dich an, um diesen Link zu sehen. --- C64Studio WIP: Bitte melde dich an, um diesen Link zu sehen. - Bitte melde dich an, um diesen Link zu sehen. --- Bitte melde dich an, um diesen Link zu sehen.

  • Kann ich mir gut vorstellen, dass Du für Deinen Anwendungsfall so einige Bytes sparen kannst!

    Ich glaube so wie Du haben auch andere Coder sich Lösungen für Ihren Anwendungsfall geschrieben. Ich wollte nun ein allgemeines Werkzeug zur Verfügung stellen, welches sich (hoffentlich) für alle Anwendungsfälle eignet und auch einsetzbar ist, ohne das Verfahren dahinter verstehen zu müssen.