 |
VOOZH | about |
|
VOOZH | about |
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").
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.
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.
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.
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
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:
| 👁 Image |
Wikipedia: Datenkompression |
| 👁 Image |
Wikipedia: Shannon-Fano-Kodierung |
| 👁 Image |
Wikipedia: Lempel-Ziv-Welch-Algorithmus |
| 👁 Image |
Wikipedia: Entropiekodierung |
