Frisch gepreßt ist halb gespeichert Dateikompression auf dem CPC Viel Material und wenig Platz–Ökonomie ist gefragt. Wie Sie Binärdateien auf engstem (Diskettenspeicher-)Raum aufbewahren, zeigt Ihnen unser Turbo-Cruncher. Als im Jahr 1985 die erste “Datenpresse” für den CPC erschien, galt dies als Meilenstein am Weg in eine kompaktere Welt. Die Theorie dahinter war einfach: Bildschirmdateien belegen auf der Diskette 17 kByte. Eine genaue Untersuchung fördert Überraschendes zutage: MEMORY &3FFF: LOAD “SCREEN”,&4000:FOR A=&4000 TO &7FFF:PRINT HEX$(A),HEX$( PEEK(A)):NEXT Ein Wert wiederholt sich oft bis zu 80mal, bis zur nächsten Byteschlange. Genau darauf basierte der erste Datenverdichter. Das Komprimierprogramm (auch Cruncher = Zermalmer genannt) zählt, wie oft jedes Byte in der Folge vorkommt und ersetzt diese Reihe dann durch zwei Bytes: 1) Länge der Folge. (Reihen länger als 255 Bytes wurden geteilt.) 2) Gemeinsamer Bytewert der Folge. Das Gegenstück, der Entpacker (oder Decruncher, Expander), hat dann leichtes Spiel: Das zweite Byte wird einfach x-mal an die Zieladresse kopiert, wobei x durch das erste Byte bestimmt wird. Das entsprechende Packprogramm ist schnell und einfach erstellt, das Komprimieren einer Bildschirmdatei dauert etwa eine Sekunde, der Pack-Faktor beträgt dabei 10 bis 15 Prozent. Statt 16 kByte ist der Screen nur noch um die 14 kByte groß. Hoher Packfaktor gefragt Doch wehe dem, der statt einer Bildschirmdatei ein Maschinenprogramm durch einen solchen Cruncher jagt: Hier folgen fast nie zwei oder mehr gleiche Bytes aufeinander, der Komprimierer wird zum Expander und bläht das Programm gut zur doppelten Länge auf. Die CPC-Welt braucht also ein einfach zu bedienendes Komprimierprogramm mit einem den Aufwand mehr als rechtfertigenden Pack-Faktor. Auch sollten reine Maschinencode-Programme ohne Komplikationen auf einen Bruchteil komprimiert werden. Das Verfahren, das wir bei unserem hier abgedruckten “Quetschprogramm” verwenden, haben wir “Misch-Crunch-Verfahren” genannt. Es erreicht bei Bildschirmdateien einen Packfaktor von 55 bis 75 Prozent. Es läßt sich auch für Maschinencode-Programme verwenden, allerdings liegt der Packfaktor hier etwas niedriger. Das Grundprinzip des “Misch-Crunch-Verfahrens” ist relativ einfach: 1) Gleiche Bytes werden wie oben beschrieben zusammengefaßt. 2) Nichtkomprimierbare Bytes werden unverändert weiterkopiert. 3) Zusammenfassung von Bytefolgen nach einem abgewandelten LZSS–(Lempel, Ziv, Storer, Szymansky)-Packverfahren (siehe auch 10/11’91, S. 42-47). Das reguläre LZSS-Verfahren wurde eigentlich zur schnelleren Datenübertragung entwickelt und bedient sich eines Ringpuffers. Um effektiv mit diesem Puffer arbeiten zu können, muß dieser sehr groß sein. Für unser Packprogramm haben wir deshalb auf einen solchen Zwischenspeicher verzichtet. Unsere Variante funktioniert daher folgendermaßen: Der Kompressor durchsucht unermüdlich die Quelldatei daraufhin, ob die aktuelle, nicht komprimierbare Bytefolge schon einmal in die Zieldatei kopiert wurde. Wird er fündig, speichert er nun einen Zeiger auf die Position des letzten Vorkommens und die Anzahl der von dort zu kopierenden Bytes. Je einfacher die Theorie, desto schwieriger ist oft die praktische Umsetzung. Wie kennzeichnet man die einzelnen Verfahren, ohne die Datei unnötigerweise aufzublähen? Nach langwierigen Tests der Häufigkeitsverteilungen haben wir für dieses Programm folgende Kennzeichung für die insgesamt fünf Kompressionsmöglichkeiten festgelegt: (Die Varianten sind der besseren Verständlichkeit wegen am Beispiel des Entpackers erklärt.) System 1: 1 Byte, Aufbau: 00XXXXXX: Hierbei handelt es sich um eine spezielle Kurzversion des LZSS-Verfahrens. Stößt der Expander auf ein Byte, dessen 6. und 7. Bit zurückgesetzt sind, macht er folgendes: 1) Er zieht von der aktuellen Zieladresse XXXXXX Bytes ab (binär, also maximal 63). 2) Dann kopiert er von dort drei Bytes an die reguläre Zieladresse. 3) Diese wird dabei um drei erhöht. Diese Verfahren ist speziell für Maschinenprogrammdateien gedacht. Hierbei werden sich wiederholende Unterprogrammaufrufe oder absolute Sprünge von drei Byte (&CD, &18, &BB) auf ein Byte gepackt. System 2: 3 Bytes, Aufbau: 01XXXXXX YYYYYYYY ZZZZZZZZ: Das reguläre LZSS-Verfahren: 1) Der Expander subtrahiert YYYYYYYYZZZZZZZZ von der Zieladresse (kann also jetzt den gesamten Speicher adressieren), 2) kopiert von dort XXXXXX Bytes (wieder maximal 63), 3) und addiert XXXXXX zur Zieladresse. Damit lassen sich alle schon einmal aufgetretenen Bytesequenzen erfassen. System 3: 2 Bytes, Aufbau: 100XXXXX YYYYYYYY Hier werden Bytefolgen gekennzeichnet: Der Entpacker kopiert XXXXX-mal das Byte YYYYYYYY an die Zieladresse und erhöht diese um XXXXX. System 4: 1 Byte, Aufbau: 11XXXXXX System 5: 2 Bytes, Aufbau: 101XXXXX YYYYYYYY Mit den beiden letzten Methoden werden Byteketten, für die der Kompressor keine Packmöglichkeit gefunden hat, für den Expander gekennzeichnet. Sind es weniger als 64 Bytes, kommt System 4 zum Einsatz, sonst System 5. Der Entpacker kopiert also lediglich XXXXXX beziehungsweise XXXXXYYYYYYYY Bytes von der Quelladresse zur Zieladresse und erhöht beide entsprechend. Nun zum Programm selbst. Zuerst geben Sie Listing 1 ein und speichern es unter dem Namen COMPACT.BAS ab. Anschließend tippen Sie die Listings 2, 3 und 4 ab. Diese erzeugen nach dem Start kurze Binärdateien. Nun sollten sich auf Ihrem Datenträger folgende Dateien befinden (die Reihenfolge sollten Kassettenbenutzer unbedingt einhalten): 1) COMPACT. BAS - das Hauptprogramm 2) COMPACT. WIN - die Routinen für Fenstertechnik, Laden und Speichern 3) COMPACT.EXP - der Expander 4) COMPACT.COM - der Kompressor Nach dem Programmstart werden die drei Maschinenprogramme nachgeladen, und das Programm meldet sich mit einer kurzen Programmerläuterung. Nach einem Tastendruck wird man nach dem Namen der Quelldatei (die zu packende Datei) und der Zieldatei (Name des fertig gepackten Programms) gefragt. Spätestens jetzt sollte man die Diskette mit der Quelldatei einlegen, denn sämtliche Eingaben und Diskettenzugriffe werden, da das Programm möglichst klein sein sollte, nicht genauer überprüft. Ein neues Fenster verrät dann die betreffenden Dateiinformationen, Kassetten (REM-Zeile 220)- oder XYDOS-User müssen notfalls in Zeile 210 entsprechende Änderungen vornehmen. ┌─────────────────────────────────────────────────────────────────────────────┐ │ Die Funktionen der Datei COMPACT.WIN: │ │ CALL &A500,1: Der Speicherbereich &C000-&FFFF wird nach &4000 kopiert und │ │ der Bildschirmspeicher nach dort verlegt. │ │ CALL &A500,2: Der Bildschirmspeicher wird wieder nach &C000 verlegt. │ │ CALL &A500,3: Der gesamte Bildschirm wird mit dem gestreiften │ │ Hintergrundmuster gefüllt. │ │ CALL &A500,Adr,Breite,Höhe,4: An Video-RAM-Adresse Adr wird ein │ │ Window-Schatten mit angegebener Breite und Höhe gezeichnet. │ │ CALL &A500,5: Die Datei, deren Name bei &1FF1 steht, wird nach &2000 │ │ geladen. │ │ CALL &A500,6: Obige Datei wird wieder gespeichert. │ └─────────────────────────────────────────────────────────────────────────────┘ Patch für Kassettenbenutzer An dieser Stelle sollte man sich am besten die Anfangsadresse und die Startadresse des Programms merken, da diese später abgefragt wird. Ebenfalls sollte man besonders auf die Länge der Quelldatei achten. Sie darf theoretisch zwar &8500 Bytes betragen, praktisch dürfte allerdings in vielen Fällen ein Absturz die Folge sein. Die zu packende Datei wird nach &2000 geladen, die komprimierten Daten landen direkt dahinter. In obigem Falle also bei &A500, wo normalerweise bald der Betriebssystembereich beginnt. Dieser wird zwar nach &E500 in den Video-RAM gerettet, doch es bleiben trotzdem nur &E500-&A500=&4000 oder 16384 Bytes frei. Läßt sich die Datei also nicht von &8500 auf &4000 komprimieren, stürzt das Programm ab. Hundertprozentig gefahrlos verläuft das Packen von bis zu &6280 oder 25216 Byte langen Dateien. Nach einem Tastendruck beginnt der Packer hörbar seine Arbeit. Die nervtötende Sirene dient als letztes Kommunikationsmittel mit dem Anwender, da der Bildschirmspeicher schon mit wichtigen Daten vollgestopft ist und ein visueller Kontakt somit ausscheidet. Ein kompletter Tondurchlauf von hoch nach tief zeigt an, daß der Cruncher wieder 256 Bytes erfolgreich gepackt hat. So läßt sich die Dauer des Packvorganges bestimmen: (Dateilänge\256) Sirenendurchläufe, dann ist es geschafft. Nach einem “Plop” ist der Packvorgang beendet, und ein Statusscreen präsentiert einige Infos wie Packfaktor und so weiter. Jetzt kann man sich aussuchen, ob die gepackte Datei allein oder mit dem Entpacker gekoppelt abgespeichert werden soll. Entscheidet man sich für die erste Möglichkeit, muß man sich selbst um das Entpacken kümmern. Dazu lädt man die gepackte Datei und den Entpacker COMPACT.EXP an eine beliebige Adresse. Der Aufruf erfolgt dann mit CALL ADR, QUELLE, ZIEL, (gecrunchte) LÄNGE Quellcodes zu den Maschinenprogrammen sind auf der Databox zu finden. Beim LZSS-Verfahren muß der Packer für jedes einzelne Byte den Speicher fast komplett durchforsten, was trotz des leistungsfähigen CPDR-Kommandos mit einiger Wartezeit verbunden ist. (Das Komprimieren eines Screens dauert etwa 4 Minuten!) Der Aufruf des Packers erfolgt von BASIC aus mit CALL &1E00, Start, Ziel, Länge. Der Entpacker ist weitaus übersichtlicher als der Kompressor. Er muß sich ja auch nur nach dessen Anweisungen richten und stur das Programm in den Speicher schreiben. Dementsprechend schnell ist auch die Durchführung: Ein 16-kByte-Block wird in Sekundenbruchteilen entpackt. Außerdem ist der Entpacker frei im Speicher verschiebbar. Um zum Beispiel einen gepackten Screen wieder auf den Bildschirm zu holen, empfiehlt sich folgendes Programm: 10 MEMORY &5EFF 20 LOAD “COMPACT. EXP”, &5F00: LOAD “SCREEN”, &6000 30 CALL &5F00, &6000, &C000, PEEK (&A76D)+256*PEEK(&A76E) Probleme ergeben sich erst bei langen Dateien; manchmal kann auch eine Überschneidung von Quell- und Zielbereich notwendig sein. Grundsätzlich gilt dann die Faustregel: Zieladresse unter Quelladresse. Auch kann man mehrere bereits gepackte Dateien aneinanderhängen und zusammen entpacken. Hier experimentiert man am besten selbst etwas herum. Für die meisten Anwendungsfälle genügt eigentlich die zweite Variante: Anbindung des Entpackers an die Datei. Wählt man diese Option, muß nur noch die Zieladresse (bei Screens also &C000) festgelegt werden, der Rest läuft automatisch ab. Zum Entpacken genügt folgende Zeile: 10 MEMORY ADR-1:LOAD “SCREEN”, ADR:CALL ADR In diesem Fall ist eine Überschneidung beider Bereiche aber zu vermeiden, da sich sonst der Entpacker selbst überschreibt. Trotzdem wird diese bequemere Art des Entpackens fast allen Ansprüchen gerecht. Hat man zum Beispiel ein BASIC-Programm geschrieben, das im Bereich &6000 bis &A000 Sprites, Zeichensätze oder ähnliches speichert, nutzt man am besten den Bildschirmspeicher: 10 MODE 2:INK 0, 0:INK 1, 0: ’Keine Anzeige 20 MEMORY &5FFF 30 LOAD “SPRITES”, &C000:CALL &C000:’Entpacken der Daten näch &6000 40 MODE 2:INK 1,26:’Reste löschen, Anzeige ein Elmar Krieger/jg