Packer

Aus C64-Wiki
Wechseln zu: Navigation, Suche

In Bezug auf den C64 bezeichnet man als "Packer" oder auch "Cruncher" oder "Compressor" üblicherweise Anwendungen, mit deren Hilfe Daten komprimiert werden, damit sie weniger Platz im Speicher bzw. auf einem Datenträger einnehmen. Dabei spielt es grundsätzlich keine Rolle, ob es sich bei den Daten um Programme, Text, Musik oder Grafikdaten handelt. Normalerweise wird in dem komprimierten File auch gleichzeitig die Entpackroutine erzeugt, die notwendig ist, um die Daten verlustfrei wieder in den Zustand vor dem Packen zu bringen, so dass sie vom System verarbeitet werden können; diese Art komprimierter Files nennt man daher auch "self-extracting" ("selbstextrahierend").

Inhaltsverzeichnis

[Bearbeiten] Überblick über Kompressionsverfahren

Die wichtigsten und oft miteinander kombiniert eingesetzten Verfahren, die für Datenkomprimierung zum Einsatz kommen, sind Entropie-Kodierung und String-Ersatzverfahren.

Beim Entropieverfahren wird jedem Byte der Ausgangsdaten eine Bitfolge zugewiesen. Der zur Kompression eingesetzte Algorithmus nach Shannon-Fano erstellt einen binären Baum aufgrund der Häufigkeit der zu kodierenden Zeichen bzw. Bytes. Die Weiterentwicklung dieses Verfahrens durch Huffman erstellt dagegen zunächst einen ganzen Wald(!) von Bäumen und sucht anschließend den optimalen Baum für die Kodierung heraus. Wer jetzt glaubt, im Wald zu stehen bzw. den Wald vor lauter Bäumen nicht zu sehen, findet unten weiterführende Links.

Bei den Stringersatz- oder auch "Wörterbuchverfahren" werden mehrfach auftretende Zeichen- bzw. Byte-Folgen einer Datei verschlüsselt und zur Entschlüsselung in ein Wörterbuch ausgelagert. Ein Meilenstein dieses Verfahrens ist der LZW-Algorithmus, benannt nach den Entwicklern Lempel, Ziv und Welch. Die Kompressionssoftware kann ein feststehendes Wörterbuch verwenden, was z.B. dann sinnvoll erscheinen kann, wenn man weiß, dass die zu komprimierenden Daten ausschließlich Text einer bestimmten Sprache enthalten. Um einen möglichst breit gefächerten Einsatz zu ermöglichen, wird aber meistens erst beim ersten Durchsehen der zu komprimierenden Daten dynamisch ein Wörterbuch erstellt, so dass es nicht darauf ankommt, ob die zu packende Bytefolge nun Text oder Code egal welcher Sprache, Grafikdaten oder auch etwas völlig anderes enthält.

[Bearbeiten] Veranschaulichung der Funktionsweise (Stringersatzverfahren)

Egal, ob man ein Programm geschrieben oder sonstige Daten wie Grafik, Musik, Text etc. erstellt hat, entstehen dabei nahezu zwangsläufig sogenannte "redundante" Passagen, d.h. Stellen, die sich wiederholen und somit kürzer und in puncto Speicherbedarf ökonomischer dargestellt werden können. Ein mit Stringersatzverfahren arbeitender Packer nutzt diese Redundanzen aus und erstellt einen Algorithmus, der darauf zielt, eine solche Verkürzung durchzuführen.

[Bearbeiten] Beispiel 1: Text

Der folgende Text würde ungepackt ohne Ladeadresse 64 Byte im Speicher belegen.

WENN FLIEGEN HINTER FLIEGEN FLIEGEN FLIEGEN FLIEGEN FLIEGEN NACH

Ersetzt man die Kombination Leerzeichen + FLIEGEN durch X, erhält man

WENNX HINTERXXXXX NACH

und benötigt nur noch 22 Byte. Da in diesem Beispiel nun nach dem ersten Kompressionsdurchgang X redundant auftritt, kann man X als weiteren Schritt mit der Häufigkeit des Auftretens kombinieren, z.B.

5X <-- 5 für Häufigkeit, X für den zu komprimierenden Ausdruck

so erhält man

WENN1X HINTER5X

und hat die ursprünglichen 64 Bytes bereits auf 15 Bytes reduziert. Zwar kommen noch der zur Dekodierung von X zu LEERZEICHEN + FLIEGEN nötige Eintrag in das Wörterbuch und die Decrunching-Routine zum Auslesen des Wörterbuches hinzu; beides verbraucht Speicherplatz, so dass der Vorgang für eine ohnehin so kleine Datenmenge wie in dem Beispiel praktisch wenig Sinn macht; aber wenn man in einem längeren Text mehrere häufig auftretende Zeichenfolgen identifiziert und codiert und mehrere Kompressionsdurchgänge vornimmt, lässt sich gerade beim Packen von Text leicht eine beeindruckende Komprimierungsrate erzielen.

[Bearbeiten] Beispiel 2: Grafik

Man stelle sich vor, ein Koala-Bild mit den formatüblichen Speicherdimensionen ist erstellt worden. Die Bereiche, die flächig einfarbig sind, nehmen unnötigerweise genauso viel Speicher ein, als wenn jedes Pixel der Fläche eine andere Farbe hätte im Vergleich zu seinen Nachbarn. Der Einfachheit halber seien allein die 1.000 Byte Farbram betrachtet: Wenn - in Farbram-Kacheln gesprochen - die erste Zeile komplett schwarz ist, kann man aus 40 Byte (1 Byte pro Spalte) leicht 2 Byte machen, in einem Byte steht die Information

#$00/#00 -> HEX/DEZ für "Schwarz" 

In dem zweiten Byte steht die Information, wie oft in Folge die Information gültig ist, z.B.

#$28/#40 --> HEX/DEZ für 40 Bytes in Folge, also alle 40 Spalten dieser Zeile

[Bearbeiten] Packer für C64

[Bearbeiten] Historisches und Allgemeines

Seit den 1980er Jahren sind Hunderte von Crunching Tools programmiert worden. In erster Linie ging es darum, fehlerfrei zu immer besseren Komprimierungsraten zu gelangen. Gerade in Crackerkreisen war und ist Crunching eigentlich fast unabdingbar, sei es, um das Original nachhaltig zu verbessern durch Single-Filing oder eine single-sided Version eines eine Diskettenseite übersteigenden Originals zu erstellen oder auch einfach nur um Platz im Speicher zu schaffen, um bei einem One-Filer noch ein Intro vor das eigentliche Programm zu setzen. Nicht selten waren es dementsprechend auch Cracker, die solche Tools selbst programmiert haben. Auch durch einen gewissen Wettbewerb wurden die Packer immer effektiver, teilweise auch bedienerfreundlicher. Welchen Packer man wählt, muss man nicht zwangsläufig von der Kompressionsrate abhängig machen, auch die Geschwindigkeit des Dekomprimierungsprozesses kann eine Rolle spielen, in Demos soll dies gern schnell oder "im Hintergrund" geschehen. Manchmal sind die eigenen Anforderungen so speziell, dass es Sinn machen kann, sich für die jeweiligen Bedürfnisse selbst entsprechende Packer zu erstellen - so nutzt beispielsweise der Ultraflash Noter V3 statische Huffman-Kompression basierend auf der Häufigkeit von Buchstaben in der englischen Sprache. Für die allermeisten Fälle sollten aber eines der nachfolgend genannten Programme genügen:

[Bearbeiten] Auswahl einiger mehr oder weniger gängiger Packer

  • ALZ64
    • pro enorme Kompressionsraten, daher bei der RGCD 16 KByte Cartridge Game Competition 2014 in Mode gekommen
    • neutral nicht direkt auf C64 einsetzbar, Cross-Development
    • neutral / contra der Speicherbereich von $0000 bis $07FF wird nahezu komplett benutzt und überschrieben, so dass nach dem Decrunchen auch ROM-Routinen (BASIC-ROM, KERNAL-ROM) nicht funktionieren, ohne dass man die Bereiche wieder initialisiert
    • contra leider so enorm langwieriges Decrunching, dass der Crunching-Vorteil kürzere Ladezeit ad absurdum geführt wird
  • ByteBoozer
    • pro schnelles Decrunching und gute Kompressionsraten, speziell für Trackmos, also mehrteilige Demos entwickelt
    • pro es gibt den ByteBoozer sowohl als native C64 Software als auch als Cross-Development Version für Windows
  • Exomizer
    • pro sehr gute Kompressionsraten --> besonders RAM-sparende bzw. kleine Resultate
    • pro wird aktiv weiterentwickelt
    • pro nicht allein auf C64 beschränkt, Einsatz auch für andere 6502-kompatible Systeme möglich, z.B. Atari 800 XL bzw. Z80- und 6809-CPUs
    • neutral nicht direkt auf C64 einsetzbar, Cross-Development, in ANSI-C geschrieben und z.B. auf DOS, Windows, Linux lauffähig
    • neutral / contra beim Decrunchen werden einige Speicherbereiche in Zeropage und Stack beeinflusst, so dass unter Umständen erforderlich sein kann, die entsprechenden Bereiche wiederherzustellen oder zu initialisieren
    • contra recht langsamer Decrunching-Prozess
  • PuCrunch
    • pro gegenüber Exomizer schnelleres Decrunching
    • pro Decruncher auch für Z80-CPU
    • neutral nicht direkt auf C64 einsetzbar, Cross-Development
    • contra Kompressionsrate ist grundsätzlich gut, kann aber normalerweise nicht mit Exomizer mithalten
  • Sledgehammer
    • neutral native C64 Software
  • wcrush aka Crush for Windows
    • neutral Wie der Name schon sagt, nicht direkt auf C64 einsetzbar, sondern für Windows User gedacht.

[Bearbeiten] Siehe auch

[Bearbeiten] Weblinks

WP-W11.png Wikipedia: Datenkompression
WP-W11.png Wikipedia: Shannon-Fano-Kodierung
WP-W11.png Wikipedia: Lempel-Ziv-Welch-Algorithmus
WP-W11.png Wikipedia: Entropiekodierung