ST-Ecke: Bildhaft aus- und eingepackt
In den vergangenen Monaten haben wir uns mit den unterschiedlichsten Bildformaten beschäftigt und diese näher beschrieben. In der vierten und damit letzten Folge unserer Bildformate haben wir uns dem IMAGIC-Format verschrieben. Dabei haben wir uns auf vielfachen Wunsch doch dazu entschlossen, nicht nur den Entpacker sondern auch den Packer für dieses Format zu veröffentlichen. Natürlich arbeitet der hier veröffentlichte Packer nicht mit allen Finessen wie in IMAGIC selbst, aber er packt so schon faszinierend gut. Aber zunächst wollen wir noch ein wenig der Theorie fröhnen...
Durchschaut
In den letzten Folgen unserer Reihe haben wir schon mehrfach festgestellt, daß ein Bild uns leider nicht den Gefallen tut. nur ganz bestimmte Bytes zu benutzen, sondern in den Bilddaten können immer alle Bytes enthalten sein, die es gibt;
von $00 für 8 weiße Punkte
über $55 oder $AA für grau
bis zu $FF = schwarz
Bitweise im Klartext: $55 = %01010101
(beispielsweise, monochrom).
Ein Bild packen bedeutet, daß man Ketten gleicher Bytes zu möglichst wenigen Kontrollbytes zusammenfaßt, aus denen der Entpacker erkennt, wie er die alte Bildinformation wieder erstellen kann. Da jedoch alle 256 möglichen Bytes in den Bilddaten Vorkommen können, muß man eine Codiervorschrift ersinnen, die es trotzdem ermöglicht, die Kontrollinformation in den gepackten Bilddaten zu erkennen. Die einfachste Möglichkeit wäre es natürlich, das 257. Byte zu verwenden, um die Kontrollinformation zu markieren. Nur leider ist es bis jetzt trotz intensivster Forschungsarbeiten nicht gelungen, dieses Byte zu entdecken. So bleiben uns praktisch nur noch zwei weitere Möglichkeiten:
Der Packer und der Zähler
Die erste Möglichkeit haben wir bereits bei den IFF- und VDI-Formaten kennengelernt: Jeder zusammenhängenden Kette von Informationen wird ein “Zählerbyte” vorangestellt, das besagt, wieviel reine Datenbytes jetzt folgen. Gleichzeitig besagt hierbei meist ein negatives Byte, daß eine Kette von m GLEICHEN Bytes folgt. Folgerichtig gibt es auch ein postives Byte, das die Anzahl der unterschiedlichen Bytes kodiert. Der Vorteil dieser Methode liegt darin, daß unser Code immer transparent bleibt, Steuerbytes und Datenbytes sind genau voneinander getrennt,der Auspacker weiß anhand der Zählerbytes genau, wie lang eine Kette von reinen Datenbytes ist.
Da ein Byte in einem solchen Fall nur Werte von 0.. 127 für positive Zahlen und -1 ... -128 für negative Zahlen annehmen kann, liegt hier auch der Nachteil der Methode: Die maximale Länge einer Kette, egal ob gepackt oder ungepackt, kann nur 127 Bytes betragen. Danach muß wieder ein neues Zählerbyte folgen. Das kann durchaus dazu führen, daß ein gepackter einmal auch länger als ein ungepackter Code wird. Die Unterbrechungen verlangsamen außerdem den Vorgang des Entpackens ein wenig. Ein weiterer Nachteil: Diese Methode läßt keine wirklichen “Codebäume” zu, mit denen man noch weitere Informationen verschlüsseln kann, wie man das zum Beispiel bei “direkter” Differenzkomprimierung benötigt.
Dem Code entflohen das ESCAPE-Byte
So ganz unsinnig, wie Sie meinen, ist die Idee vom 257. Byte gar nicht: Wenn es natürlich auch mit 8 Bits genau 256 (2 hoch 8) verschiedene Kombinationen gibt, so “bestimmt” man ganz einfach eines dieser Bytes zum ESCAPE-Byte (Fluchtbyte) - so etwas ähnliches hatten wir schon beim STAD-Format. Immer wenn in den komprimierten Daten dieses ESCAPE-Byte auftritt, erkennt der Ent-packer daran, daß jetzt neue Steuerinformationen folgen. “Halt!” werden Sie sagen, “was passiert, wenn aber genau dieses ESCAPE-Byte in den Bilddaten vorkommt? Wir wollen doch nicht auf dieses schöne Byte im Bild verzichten?”. Natürlich nicht! In diesem Fall schreiben wir das ESCAPE-Byte einfach ZWEIMAL hintereinander hin. Daran erkennt jetzt unser Entpacker, daß wirklich das ESCAPE-Byte gemeint ist und schreibt es nur EINMAL in das ausgepackte Zielbild.
So, somit ist das Unmögliche möglich gemacht: Wir haben ‘257 unterschiedliche Bytes’ zur Verfügung! Wenn man jetzt ganz listig vorgeht, so bestimmt man dasjenige Byte zum ESCAPE-Byte, das am wenigsten häufig im ungepackten Bild vorkommt. Denn jedesmal, wenn das ESCAPE-Byte erscheint, bekommt unser Bilderpacker einen Schluckauf, weil dieses Byte ja verdoppelt werden muß. Da ist es natürlich sinnvoll, ein Byte auszuwählen, das diese Verdopplung möglichst selten erforderlich macht.
Wie man das ESCAPE-Byte bestimmt, können Sie beispielsweise schön in der Routine GETESCAPE sehen, die im Assemblercode des IMAGIC-Packers enthalten ist.
Komprimierte Bilddaten aus dem Zeichen- und Animationsprogramm DENISE aus dem IMAGIC-Paket.
32 Bytes Farbpalette nach dem ATARI ST Standard,
Bytes 7 .. 38,
Auflösung LOW ( *.IC1 ), MED ( *.IC2 ), HIGH ( *.IC3 ),
Dateilänge variabel, abhängig vom Bildinhalt,
Kennung:
- Bytes 1..4 = ‘IMDC’
- Bytes 5, 6 = Auflösung ( 0=LOW, 1=MED, 2=HIGH ).
O Code-Baum, o Code-Baum...
... du grünst nicht nur zur Winterszeit, nein auch im Sommer, wenn es schneit! Also was ist ein Codebaum? Ganz einfach: Eine Verzweigungs-Vorschrift.
Unser ESCAPE-Byte sei die “WURZEL” unseres Baums. Dann bestimmt das darauffolgende Byte, auf welchem Ast wir uns weiter bewegen. Da ein Byte 256 Werte annehmen kann, gibt es also bereits 256 Äste und damit 256 Möglichkeiten zur Verzweigung! Ein Ast ist bereits vergeben: Das ESCAPE-Byte selbst noch einmal, das dann zu einem Datenbyte im Zielbild wird.
Da unser erzeugter Code möglichst kurz sein soll, ist es sinnvoll, die notwendigen Entscheidungen möglichst schnell zu treffen, also ein ganzes Bündel von Ästen zu einer Richtung zusammenzufassen: Nehmen wir an, eine Codeentscheidung bestehe immer aus drei Bytes:
<ESCAPE-Byte> <Zähler-Byte> <Datenbyte>
so sieht man sofort, daß es nicht sinnvoll ist, Wiederholungsketten von weniger als 4 Bytes Länge gepackt zu speichern, da sonst das Ergebnis länger als oder nur gleich lang sein würde wie die ungepackte Speicherung. Wenn wir den Wertebereich des Zähler-Bytes um Eins nach oben verschieben, können wir mit den Bytes ($03) .. ($FF) Zählerwerte von 4 .. 256 erreichen. Somit stehen die Zähler-Bytes ($01) und ($02) frei zu unserer Verfügung, da sie niemals auftreten können. Wir setzen Sie in unserem Codebaum ein:
Identische Bytes in einer Folge
Ein Byte $nn ($nn = $03.. $FF) bedeutet, daß <nn+1> identische Bytes folgen: Der Auspacker nimmt das nächste Byte und packt es <nn+1> mal in das Zielbild aus. Ein Zählerbyte = ($01) bedeutet, daß der gesamte Zählwert um 256 Bytes erhöht wird, weitere ($01)-Bytes können folgen, womit wir den meist vorhandenen Nachteil, daß nur Wiederholungen kleiner gleich 256 möglich sind, umgangen haben. Nach ($00) folgt dann noch ein normales Zählerbyte, für den nicht durch 256 teilbaren Rest (für Kenner: Modulo 256) ...Schauen wir uns das an einem Beispiel an, wird es bestimmt verständlich:
($ESC)($01)($01)($00)($20)($55)
bedeutet demnach
"Es sind 256 + 256 + 33 = 545 Bytes
mit dem Wert $55 auszupacken".
Ein Bild wird abhängig
Ein Zählerbyte ($02) hat eine weitere Sonderstellung: Es gilt als zweites ESCAPE-Byte, zur besseren Unterscheidung SAME-Byte genannt (Für alle, die der englischen Sprache nicht so gewachsen sind, sei am Rande erwähnt, daß SAME soviel wie ‘ähnlich’ bedeutet.). Tritt es auf, führt der Codebaum eine weitere Verzweigung durch: Es wird entschieden, ob folgende Teile des Bildes differenzkomprimiert sind (siehe unten), oder ob das Ende der komprimierten Daten erreicht ist. Es gelten jetzt die gleichen Regeln wie für das Zählerbyte für identische Bytefolgen: ($nn = $03 .. $FF) bedeutet: <nn+1> folgende Bytes sind gleich wie im Basisbild, der Auspacker tut hier nichts anderes mehr, als brav die Adresse im Zielbild hochzuzählen. Ein Zählerbyte = ($01) bedeutet auch hier: Zählerwert um 256 Bytes erhöhen. Und auch an dieser Stelle wollen wir unseren interessierten Leser nicht ohne Beispiel lassen:
($ESC)($02)($01)($01)($00)($20) =
545 Bytes differenz komprimiert.
Die besondere Codekette ($ESC)-($02)($00) ist die Endemarke für unseren Auspacker, der sich daraufhin erschöpft zurücklehnt: Fertig!
Der kleine Unterschied Differenzpacken
Stellen Sie sich vor, Sie sind ein begeisterter Anhänger von JOHN WAYNE (oder einem nicht unbekannten Präsidenten) und möchten eine kleine Szene aus seinem bewegten Filmleben einmal auf Ihrem ATARI-Rechner nachempfinden:
Sie entwerfen also folgendes Szenario: Die Wüste von Arizona, strahlendblauer Himmel, im Hintergrund ein Bergmassiv, ansonsten rötlicher Staub soweit das Auge reicht. John, als Meldereiter der Armee, reitet in gestrecktem Galopp von rechts kommend in das Bild. Ungefähr in der Bildmitte erblickt sein treues Pferd Rosalie eine Klapperschlange vor sich auf dem Boden, scheut auf - und John fliegt in hohem Bogen in den Sand. Es geht hier jetzt nur um das Packen, nicht um das Niveau unserer Beispiele ...)
Nehmen wir also weiterhin an, die ganze Sequenz dauert so ca. 5 Sekunden, Sie benötigen also ungefähr 75 Einzelbilder, um sie halbwegs ruckfrei vorzuführen. Wenn Ihr ATARI ST jetzt nicht gerade mit 4 Megabyte Speicher ausgerüstet ist, wird es ziemlich eng im Speicher zugehen. Weil Ihr Bild so einen schönen blauen Himmel hat und sich der Sand in gleichmäßigem Rot präsentiert, können Sie beim Packen der Einzelbilder einen Gewinn von 50% erzielen. Macht 75 * 16000 Bytes = 1,2 Megabytes - immer noch zuviel für einen 1040 ST. Doch eigentlich sind sich alle Bilder Ihres kleinen Films doch sehr ähnlich: Der gesamte Bildhintergrund ist immer gleich, das bräuchte man doch nur einmal abzuspeichern ...sprachs und hatte auch schon eine Lösung parat, denn genau hier wird jetzt das Differenzpacken interessant! Es wird nur noch abgespeichert, was sich in einem Bild in Bezug auf ein anderes Bild ändert. Alles, was in beiden Bildern identisch ist, wird wie eine “transparente” Fläche (oder auch wie im Trickfilm eine Folie ) beschrieben und kann dann wie bisher komprimiert werden. Jetzt erreichen Sie einen Gewinn zwischen 80% und 90% -die Animation paßt spielend in den Speicher ...
Bei der Differenzkomprimierung gibt es zwei unterschiedliche Techniken, deren Vorgehensweise wie folgt ist:
Exklusive Veroderung
- Begonnen wird mit dem ersten Bild der Animation: Es wird ganz normal gepackt, wie bisher.
- Das zweite Bild wird jetzt mit dem ersten Bild “exklusiv verodert" (XOR), das heißt, es bleiben nur die Punkte stehen, die in beiden Bildern UNTERSCHIEDLICH sind.
- Das Ergebnis wird dann gepackt.
- Das dritte Bild wird mit dem zweiten Bild “exklusiv verodert” und so weiter.
Auf diese Weise erhalten wir eine gepackte Bildfolge, die nur aus den Unterschieden von aufeinanderfolgenden Bildern besteht. Beim Auspacken wird jedes Bild wieder auf seinen Vorgänger “exklusiv verodert”, die ursprüngliche Bildfolge entsteht...
Bytes 1.. 4: ‘IMDC’ als ASCII-Text für “Imagic Delta Compressed”
Bytes 5.. 6: Auflösung 0=Low, 1=Medium, 2=High
Bytes 7..38: Farbpalette 16 Worte
Bytes 39..40: Datum der Erstellung im GEMDOS-Format ( Tgetdate ). 1)
Bytes 4L.42: Uhrzeit der Erstellung im GEMDOS-Format ( Tgettime ).
Bytes 43..50: Name des Basisbilds. == 0 2)
Bytes 51..52: Länge der komprimierten Packdaten.
Bytes 53..56: Registriemummer. 3)
Bytes 57..64: reserviert. == 0 4)
1) Dadurch wird es möglich, immer festzustellen, wann ein Bild erstellt wurde. Datum und Uhrzeit einer Datei werden von GEMDOS nämlich leider hei der Erstellung einer Dateikopie immer neu gesetzt. Die Angabe ist optional, sie darf auch = 0 sein.
2) Derzeit wird die Differenzkomprimierung bei einzeln gespeicherten Bildern von IMAGIC nicht unterstützt. Der Platz ist für eine spätere Erweiterung reserviert. Zur Zeit sind alle 8 Bytes = 0 zu setzen.
3) Es besteht die Möglichkeit, die Registriernummer des Programms einzutragen, mit dem das Bild erzeugt wurde. Damit lassen sich Raubkopien registrierter Programme besser zurückverfolgen. Die Angabe ist optional und kann auch = 0 sein.
4) Reserviert für spätere Erweiterungen. Sollte = 0 sein.
Das zweite Verfahren ist die "direkte Differenzkomprimierung”, wie sie vom IMAGIC-COMPILER beim Zusammensetzen eines Films eingesetzt wird:
- Als erstes ist der Benutzer aufgefordert, ein BASISBILD zu bestimmen, das als Hintergrund der Animation gilt und sich möglichst wenig von allen weiteren Bildern unterscheidet: in unserem Beispiel also das Bild mit dem leeren Hintergrund, ohne die Akteure (John Wayne and his horse, you know).
- Das Basisbild wird gepackt, wie bisher.
- Bei jedem weiteren Folgebild wird jetzt in jedem kleinen Detail bestimmt,ob es gleich zu dem bekannten Basisbild ist. Dieser Arbeitschritt wird vom Packer direkt durchgeführt, die Bilder werden also nicht vorher verodert.
- Gleiche Bildteile werden wie eine “transparente” Fläche in wenigen Bytes komprimiert.
- Wenn erforderlich, kann das Basisbild gewechselt werden, es bleibt aber in der Regel für eine ganze Kette von Bildern das gleiche. Bedenken Sie aber, daß bei einer Veränderung des Basisbildes alle abhängigen Bilder neu komprimiert werden müssen.
Auf diese Weise erhalten wir eine Folge von Einzelbildern, die voneinander UNABHÄNGIG sind. Jedes Bild kann zusammen mit dem Basisbild für sich allein ausgepackt werden. Beim Auspacken wird immer erst eine Kopie des Basisbildes erstellt, in die der Auspacker die noch vorhandenen Änderungen schreibt. Dieses Verfahren hat einige Vorteile: Man kann einen Film jetzt nicht nur in fester Folge, sondern beliebig abspielen, vorwärts, rückwärts, ...! Weiterhin ist in den meisten Fällen das Ergebnis deutlich kürzer als bei der “XOR”-Komprimierung: Wenn sich das Pferd von einem Bild zum nächsten weiterbewegt, entstehen bei der Exklusiv-Veroderung Differenzdaten nicht nur an der Stelle, wo das Pferd neu gezeichnet, sondern auch dort, wo es aus dem letzten Bild herausgenommen werden muß. Nachteilig ist die direkte Differenzkomprimierung nur dann, wenn sich der gesamte Bildinhalt von Bild zu Bild geringfügig aber stetig ändert, der Unterschied zu dem festen Basisbild also immer größer wird. Hier wird es dann erforderlich sein, ab und zu ein neues Basisbild zu bestimmen.
Bildabtastung
Oh! Bei der Entwicklung von Strategien, Bilder möglichst gut zu packen, sind wir noch nicht am Ende! Bis jetzt läuft unser Packer schön brav von links nach rechts Zeile für Zeile das Quellbild ab und versucht dabei, möglichst lange Ketten von gleicher Information zu finden. Für das nächste Beispiel werden wir zum Praktiker und besorgen uns zunächst einen großes Blatt Papier, einen dicken Filzstift und eine Schere. Sie zeichnen viele verschiedene Linien, Muster etc. auf dieses Blatt, unter anderem auch mehrere große schwarze Rechtecke. Wenn Sie dieses Blatt Papier mit einer Schere in viele schmale horizontale Streifen zerschneiden und diese Streifen dann hintereinander zu einem langen Band auf den Boden legen, haben Sie eine Kette von Informationen so, wie unser Packer bis jetzt ein Bild Zeile für Zeile abtastet. Ihre schwarzen Rechtecke erscheinen auf dem Papierband als kurze schwarze Streifen, immer wieder unterbrochen von den unregelmäßigen Linien und Mustern, die sonst auf dem Papier zu sehen waren. Entsprechend kurz sind auch die Ketten zusammenhängender Information, die der Packer auf einmal verschlüsseln kann. Wenn wir jedoch ein Bild als zweidimensionale Datenstruktur auffassen und unseren Packer befähigen, das Bild in mehrere Rechtecke zu unterteilen, die er dann nacheinander abtastet, erhalten wir auf einmal viel öfters zusammenhängende Blöcke mit gleicher Information. Das ist genau die Arbeitsweise, mit der die verschiedenen Packer von IMAGIC ein Bild zweidimensional abtasten. Unter glücklichen Umständen kann die Komprimierungsrate dabei noch einmal um 50% gegenüber der linearen Abtastung gesteigert werden.
Da IMAGIC nicht weiß, welche Abtastung für ein Bild das optimale Ergebnis bringt, wurden aus den vielen hundert Möglichkeiten durch statistische Versuche die 19 effektivsten Algorithmen ausgewählt. Sie entsprechen den IMAGIC-Packern #2.. #20. Packer #1 ist der lineare Packer, der ein Bild in horizontalen Streifen abtastet. IMAGIC probiert beim Packen eines Bildes einfach alle 20 Algorithmen durch und merkt sich die Länge der entstehenden, komprimierten Daten. Der Algorithmus mit der geringsten Länge gewinnt.
IN MEDIAS RES: Der Aufbau einer IMAGIC-Bilddatei
Kommen wir zu den Fakten und schauen uns den Aufbau einer IMAGIC-Datei an. IMAGIC-Bilder haben einen 64 Byte-Header mit folgenden Informationen: Die ersten vier Bytes enthalten den Text IMDC, was eine Erkennung der Datei ermöglicht und ein Akronym für “IMAGIC DELTA COMPRESSED" darstellt. In den Bytes fünf und sechs finden wir die Auflösung des Bildes verschlüsselt, wobei 0 low, 1 medium und 2 high bedeutet. Die in der IMG-Datei so stiefmütterlich behandelte Farbpalette bringen wir in den Bytes 7 bis 38 unter, auf die in den beiden folgenden Bytes das Datum der Erstellung im GEMDOS-Format folgt. Dadurch wird es möglich, immer festzustellen, wann ein Bild erstellt wurde. Datum und Uhrzeit einer Datei werden von GEMDOS nämlich leider bei der Erstellung einer Dateikopie immer neu gesetzt. Die Angabe ist optional, sie darf auch = 0 sein. Für den Namen eines Bildes sehen wir acht Buchstaben vor, der also mit im Header vorhanden ist. Derzeit wird die Differenzkomprimierung bei einzeln gespeicherten Bildern von IMAGIC nicht unterstützt. Der Platz ist für eine spätere Erweiterung reserviert - zur Zeit sind alle 8 Bytes = 0 zu setzen. Die Länge der komprimierten Packdaten halten wir in Bytes 51 und 52 fest, während die Bytes 53 bis 56 eine Seriennummer enthalten. Es besteht die Möglichkeit, die Regi-striemummer des Programms einzutragen, mit dem das Bild erzeugt wurde. Damit lassen sich Raubkopien registrierter Programme besser zurückverfolgen; auch diese Angabe ist optional und kann = 0 sein. Die letzten vier Bytes sind für spätere Anwendungen reserviert und sollten daher Null sein.
Der IMAGIC-Packer!
Wir haben einige Briefe bekommen, deren Absender sich wünschten, daß wir einen Packer veröffentlichen. Wir haben uns entschlossen, den Linearpacker von IMAGIC zu veröffentlichen (Jörg und Alex sei Dank). Dieser Packer erzeugt Bilder, die genau den Konventionen des IMAGIC-Formats entsprechen. Gepackt werden können Bilder aller Auflösungen(!) des ATARI ST. Der vorgestellte Algorithmus entspricht dabei dem Packer #1 aus dem IMAGIC-Paket und führt eine lineare Abtastung des Quellbildes durch. Eine Differenzkomprimierung wird für Einzelbilder nicht durchgeführt. Auch wenn wir ihn veröffentlichen, die Erklärung soll nicht über die Dokumentation hinausgehen - die Grundlagen zum Verständnis des Packers sind in den letzten Folgen der ST-Ecke gelegt worden.
Der IMAGIC-Auspacker
...packt alle mit IMAGIC oder dem vorgestellten Packer erstellten Bilder. Er ist auch bereits für das Auspacken differenzkomprimierter Bilder vorbereitet.
Resümee
Eine noch höhere Packdichte ist machbar, wenn man Datenstrukturen erkennt und packt, die kleiner als ein Byte sind (Bitpacker). Dabei kann dann ein noch optimalerer Codebaum erstellt werden, wenn beispielsweise die Häufigkeiten der vorkommenden Bitfolgen im Bild beachtet werden. Schön gelöst ist das zum Beispiel bei der ARC (Archive Utility), einem PD-Programm zur Komprimierung und Archivierung von Daten. Für den praktischen Einsatz bei IM AGIC ist die Anwendung der Bit-Komprimierung leider nicht geeignet, weil das Packen und Entpacken sehr viel Zeit erfordern.
The Final Curtain
Nun fällt der Vorhang über unseren bildlichen Streifzug, und wir hoffen, daß wir ein wenig Licht in das Dunkel gebracht haben. Einige unterschiedliche Formate haben wir nicht nur als Format selbst, sondern auch mit den entsprechenden Routinen veröffentlicht, so daß sie direkt verwendet werden können. Wichtig war es uns, die Vor- und Nachteile der Packformate aufzuzeigen, und, daß der Leser bemerkt, daß es nicht DEN Packalgorithmus gibt, sondern nur einen für das spezielle Problem ausgesuchten. Wie überall im Leben muß man Kompromisse schließen und sich (natürlich im übertragenen Sinne) das beste Preis-/Leistungsverhältnis heraussuchen. Viel Spaß und Erfolg dabei wünschen Jörg Drücker und Stefan Höhn, die sich vielleicht irgendwann mit einer BILD-Nachlese wieder zurückmelden.
Die ST-Ecke widmet sich in den nächsten Monaten wieder ausgesuchten Einzelthemen, und ich kann Ihnen ankündigen, daß wir ein paar nette Sachen auf Lager haben. Versprochen!
Literaturhinweise für Besessene:
Codierungsregeln nach Shannon, Huffman und Lempel-Zev in diversen Informatik-Büchern.
Dokumentation zur Archive-Utility.
(PD, auf Diskette).
* modul AUSPACK.S
* Assemblermodul zum Auspacken von
* verschiedenen gepackten Bildformaten.
* Assembler: Metacomco MACRO Assembler
* für andere Assembler den Stern am Anfang
* durch Semikolon ersetzen
* Originalauszug aus dem Grafikpaket IMAGIC
* von APPLICATION SYSTEMS /// HEIDELBERG.
* Version 1.0
* verfasst am 8- 8-1988 von Jörg Drücker
* erweitert am 15- 9-1988 GEM VDI und STAD Formate.
* erweitert am 22-10-1988 IMAGIC Format.
* Copyright (c) 1988 by IMAGIC GRAFIK.
* *
* IMAGIC BILDER *
* auspacken *
* *
xdef DEC_IMAG
DEC_IMAG: bsr GET_PAR * Parameter holen
cmpi.1 #'IMDC',(a0)* check header
bne ERR_DONE * not IMAGIC compressed.
bsr ERASE_PIC
lea 64(a0),a0 * skip header
bsr IMAG_DECOMP
bra ALL_DONE
* *
* Fehlerausgang *
* Booleanwert FALSE zurückgeben *
* *
ERR_DONE: moveq #0,d0 * "error"
bra.s RETURN
* *
* Normalausgang *
* Booleanwert TRUE zurückgeben *
* *
ALL_DONE: moveq #1,d0 * "no error"
RETURN: movem.l (sp)+,d7/a6 * restore d7/a6
movea.1 (sp)+,a0
lea 12(sp),sp * cleanup stack
jmp (a0) * rts
* *
* Hilfsfunktion *
* Parameter vom Stack holen *
* Register korrekt setzen *
* *
GET_PAR: lea 8(sp),a4 * Zeiger auf Parameter
move.w (a4)+,d0 * RESOLUTION
move.w (a4)+,d6 * PICLEN
movea.1 (a4)+,a1 * PICTURE
movea.1 (a4)+,a0 * COMPRESSED DATA
move.l (sp)+,a5 * Return Adresse
movem.l d7/a6,-(sp) * Register retten
jmp (a5)
* *
* Hilfsfunktion *
* Bildinhalt löschen *
* *
* a1 = picture
* d6 = picturelen ( 32000 or more, but always a multiple of 64 bytes ! )
ERASE_PIC: movem.l d0-d7/a1-a2,-(sp)
moveq #0,d0
moveq #0,d1
moveq #0,d2
moveq #0,d3
moveq #0,d4
moveq #0,d5
moveq #0,d7
move.1 d0,a2 * "0" ins a2
adda.w d6,a1 * upper border
lsr.w #6,d6 * picturelen div 64
subq.w #1,d6 * Zähler -1
clrpic: movem.l d0-d5/d7/a2,-(a1) * 32 bytes
movem.l d0-d5/d7/a2,-(a1) * 32 bytes
dbra d6,clrpic
movem.l (sp)+,d0-d7/a1-a2
rts
*====================================*
* *
* Routinen zur Dekomprimierung *
* *
* IMAGIC Dekomprimierung *
* *
* (c) 1987 by Jörg Drücker *
* *
* a0 = IMAGIC komprimierter Code
* a1 = Zielbild
*
* d6 = Anzahl Bytes im Zielbild ( = 32000 ) "piclen"
IMAG_DECOMP:
* Teil I.
*
* Entscheiden, ob IMAGIC Bild gepackt ist:
tst.b (a0) * 1. Byte
bne.s DO_UNSQZ * Null ? -> dann Bilddaten kopieren!
* Teil Ib.
*
* Nicht komprimierte Bilddaten einfach
* kopieren.
* Beachte: Die Bilddaten liegen nicht auf
* einer geraden Addresse, also ist ein
* Byte-Copy nötig !
addq.l #1,a0
lsr.w #2,d6
subq.w #1,d6 * piclen/4 -1
COPY_L2: move.b (a0)+,(a1)+ * BYTE COPY durchführen
move.b (a0)+,(a1)+
move.b (a0)+,(a1)+
move.b (a0)+,(a1)+
dbra d6,COPY_L2
rts * Nach Hause telefonieren ...
* Teil II.
*
* Dekomprimierung vorbereiten:
DO_UNSQZ: link a2,#-8 * lokalen BSS linken
move.1 a1,-4(a2) * obere Bilddatengrenze errechnen
movea.1 a1,a3
add.w d6,a3 * untere Bilddatengrenze errechnen
move.1 a3,-8(a2)
moveq #0,d1 * Register löschen
moveq #0,d2
* Teil III.
*
* Los geht's - codierte Daten auspacken:
move.b (a0)+,d1
move.b (a0)+,d2
move.b (a0)+,d7
mulu #80,d2
cmp.b #-1,d1
bne.s NOT_NEGATIVE
move.w d6,d1
move.w #1,d2
NOT_NEGATIVE:
movea.w d2,a4
move.w d2,d6
subq.w #1,d6
move.w d1,d5
subq.w #1,d5
movea.w d5,a3
neg.w d1
muls d2,d1
addq.l #1,d1
movea.1 d1,a5
muls d5,d2
movea.1 d2,a6
moveq #1,d1
moveq #3,d2
moveq #2,d4
moveq #0,d0
EX_LOOP: move.b (a0)+,d0
cmp.b d0,d7 * (ESC) byte
beq.s ZERO_1
ZERO_2: cmpa.l -4(a2),a1
bmi IMAG_END * Untergrenze überprüfen
cmpa.l -8(a2),a1
bpl IMAG_END * Obergrenze überprüfen
move.b d0,(a1) * Ein Byte Zielbild schreiben
adda.1 a4,a1
dbra d5,EX_LOOP
move.w a3,d5
adda.1 a5,a1
dbra d6,EX_LOOP
move.w a4,d6
subq.w #1,d6
adda.1 a6,a1
bra.s EX_LOOP
ZERO_1: move.b (a0)+,d0 * Zähler oder doppeltes (ESC) Byte ?
cmp.b d0,d7
beq.s ZERO_2
moveq #0,d3 * "multiple" Zähler löschen
cmp.w d2,d0
bpl.s ADD_BYTE
CHK_02: cmp.b d4,d0 * (SAM) - Markierung ?
bne.s CHK_01
move.b (a0)+,d0 * Zähler holen
beq.s IMAG_END * "(ESC)(SAM)00" -> Ende !
cmp.w d2,d0
bpl.s ADD_S_BYTE
cmp.b d4,d0
bne.s CHK_S_01
CHK_S_00: move.b (a0)+,d0
beq.s EX_LOOP
bra.s CHK_S_00
CHK_S_01: cmp.b d1,d0
bne.s SKIP_S_EOM
addi.w #256,d3 * Zähler +256
move.b (a0)+,d0
bra.s CHK_S_01 * nächstes Zählerbyte
SKIP_S_EOM:
move.b (a0)+,d0* (EOM)-Byte weglesen
ADD_S_BYTE:
add.w d0,d3 * Zählerrest addieren
SAME_LOOP:
* differenzkomprimiertes Zielbild:
* Die entsprech. Anzahl Bytes ist identisch wie im
* Basisbild.
adda.l a4,a1
dbra d5,SAME_INCR
move.w a3,d5
adda.l a5,a1
dbra d6,SAME_INCR
move.w a4,d6
subq.w #1,d6
adda.1 a6,a1
SAME_INCR:
dbra d3,SAME_LOOP
bra.s EX_LOOP
CHK_01: cmp.b d1,d0
bne.s SKIP_EOM
addi.w #256,d3 * Zähler +256
move.b (a0)+,d0
bra.s CHK_01 * nächstes Zählerbyte
SKIP_EOM: move.b (a0)+,d0* (EOM)-Byte weglesen
ADD_BYTE: add.w d0,d3 * Zählerrest addieren [
move.b (a0)+,d0 * Datenbyte
UNSQ_LOOP:
* Folgeketten-Komprimierung:
* Die entsprechende Anzahl Bytes ist identisch,
* daher wird das Datenbyte n-mal in das Zielbild
* geschrieben.
cmpa.1 -4(a2),a1
bmi.s IMAG_END * untere Grenze prüfen
cmpa.1 -8 (a2),a1
bpl.s IMAG_END * obere Grenze prüfen
move.b d0,(a1) * Zielbyte schreiben
adda.l a4,a1
dbra d5,UNSQ_INCR
move.w a3,d5
adda.l a5,a1
dbra d6,UNSQ_INCR
move.w a4,d6
subq.w #1,d6
adda.l a6,a1
UNSQ_INCR:
dbra d3,UNSQ_LOOP
bra EX_LOOP
*
* Auspackvorgang beendet:
IMAG_END: unlk a2 * lokalen BSS freigeben
rts * home, sweet home again
*======================================*
end
Listing 1: Das Auspackprogramm
programm BILDEINLESEN ( input, output )
{ Diese Programmteile gehören zu einen PASCAL-Programm, das in
vorangegangenen Folgen der ST-Ecke schon auszugsweise
veröffentlicht wurde. Diese Zeile sind allein natürlich
nicht lauffähig ! }
{...in den Copyright-Block }
erweitert am 22-20-1988 IMAGIC Einpacker.
{...bei den globalen Variablen }
DATEILAENGE : integer;
ANTWORT : char;
{...hinter COL_VDI }
{ Assemblerroutine zur Codierung in das gepackte IMAGIC-Format: }
function SQZ_IMAG (PICTURE, COMP : DATA_POINTER ): integer;
external;
{...hinter HOLE_FARBEN }
function SETZE_BILDDATEN ( PICTURE, WRITEBUF : DATA_POINTER;
FARBEN : COLOUR_PTR ): integer;
{ Erstelle Bild im IMAGIC - Format: }
type IMAGIC_HEADER = packed record
{ 64 Bytes IMAGIC compressed file header: }
ID : packed array [ 1..4 ] of char;
ES : integer;
OLOR : COLOUR_DATA;
ATE : integer;
IME integer;
ASE : packed array [ 1..8 ] of char;
ENGTH integer;
EGIS : long_integer;
es_1 :long_integer;
es_2 : long_integer {-reserved- }
end;
var IMAGIC : packed record case boolean of
false : ( HEADER : ^IMAGIC_HEADER);
true ( DATA : DATA_POINTER)
end;
SQZLEN,
I : integer;
{ Zusätzliche Systemfunktionen: }
function Tgetdate : integer;
{ Systemdatum holen }
gemdos ( $2A );
function Tgettime : integer;
{ Systemzeit holen }
gemdos ( $2C );
begin
SQZLEN := SQZ_IMAG ( PICTURE,
ADDR_OFFSET ( WRITEBUF,
64) ); { Bild packen }
IMAGIC.DATA := WRITEBUF;
with IMAGIC.HEADER^ do begin
{ IMAGIC - Dateiheader erstellen: }
ID := 'IMDC'; { "IMAGIC DELTA COMPRESSED" }
RES := AUFLOESUNG; { Bildschirm }
COLOR := FARBEN^; { Farbpalette }
DATE := Tgetdate; {Datum der Erstel.}
TIME := Tgettime; {Uhrzeit der Erstel.}
for I := 1 to 8 do { kein Basisbild }
BASE [ I ] := chr ( 0 ) ;
LENGTH := SQZLEN; { Länge der komprimierten Daten }
REGIS := $4711; { Registriernummer unseres Programms}
res_1 := 0; { reserviert für Erweiterungen }
res_2 := 0
end;
SETZE_BILDDATEN := SQZLEN + 64 { gesamte Datenlänge }
end; { SETZE_BILDDATEN }
procedure SPEICHERE_BILD (BILDBUF : DATA_POINTER;
LAENGE : long_integer) ;
{ Speichere gepacktes IMAGIC-Bild: }
var OK : boolean;
POINT,
SLASH,
I : integer;
ZIELDATEI : packed file of byte;
{ Zusätzliche Systemfunktionen: }
function fwrite ( handle : integer; count: long_integer;
buffer : DATA_POINTER ) : long_integer;
{ Schreiben von Daten in eine Datei }
gemdos ( $40 );
begin
POINT := 0;
SLASH := 0;
{ Suche LETZTEN Punkt und Backslash "\" im Dateinamen: }
for I := length ( DATEINAME ) downto 1 do begin
if ( DATEINAME [ I ] = '.' ) and
( POINT = 0 ) then
POINT := I;
if ( DATEINAME [ I ] = '\' ) and ( SLASH = 0 ) then
SLASH := I
end;
if POINT > SLASH then
{ Dateiname hat eine Extension, sonst ist die Extension im Ordnernamen }
{ lösche vorhandene Extension: }
delete ( DATEINAME, POINT, length
( DATEINAME ) - POINT +1 );
{ setze korrekte Extension für IMAGIC - Bild:
*.IC1 - für niedere Auflösung,
*.IC2 - für mittlere Auflösung,
*.IC3 - für hohe Auflösung
}
DATEINAME := concat ( DATEINAME, '.IC',
chr ( ord ( '1' ) + AUFLOESUNG )
{ Zieldatei erstellen, ggf. vorher löschen: }
rewrite ( ZIELDATEI, DATEINAME );
OK := io_result = 0;
if OK then
{ Dateiinhalt schreiben: }
OK := fwrite ( handle ( ZIELDATEI ), LAENGE,BILDBUF ) = LAENGE;
if not OK then begin
{ Im Fehlerfall unbedingt versuchen, Zieldatei wieder zu löschen: }
erase ( ZIELDATEI );
writeln () chr ( 27 ), 'E', chr ( 7 ) );
{ Bildschirm löschen, Warnton }
writeln ( 'Fehler beim Schreiben der Bilddatei !' );
writeln;
writeln ( 'Weiter mit <RETURN>' );
readln
end
end; { SPEICHERE_BILD }
{... im Hauptprogramm hinter HOLE_FARBEN, setpalette,HOLE_BILDDATEN }
{ Bildinhalt im IMAGIC Format packen: }
DATEILAENGE := SETZE_BILDDATEN ( BILDSCHIRM, LESEBUFFER,
DATA, BILDFARBE);
readln; { warte nur auf Tastendruck }
{...hinter write(chr(27), 'e') ; }
if PIC_TYPE <> P_IMAGIC then begin
{ Cursor in die unterste Zeile, Zeile löschen }
write ( chr ( 27 ), 'Y', chr ( 32+24 ), chr ( 32 ),chr ( 27 ), 'K' );
write ( 'Speichern im IMAGIC Format ? (J/N): ' );
readln ( ANTWORT );
setpalette ( SYSTEMFARBE );
{ Ursprüngliche Palette wiederherstellen }
if ( ANTWORT = 'J' ) or ( ANTWORT ='j' )
then
{ Bild als gepacktes IMAGIC-Bild abspeichern }
SPEICHERE_BILD ( LESEBUFFER.DATA , DATEILAENGE )
end
else
setpalette ( SYSTEMFARBE );
{ Ursprüngliche Palette wiederherstellen }
{Das war der letzte Teil unseres PASCAL-Programms )
Listing 2: Das Bildeinleseprogramm
* modul EINPACK.S
*
* Assemblermodul IMAGIC Packer.
* Assembler: Metacomco MACRO Assembler
* für andere Assembler den Stern am Anfang
* durch Semikolon ersetzen
*
* Originalauszug aus dem Grafikpaket IMAGIC
* von APPLICATION SYSTEMS /// HEIDELBERG.
* Version 1.0
* verfasst am 22-10-1988 von Jörg Drücker
*
* Copyright (c) 1988 by IMAGIC GRAFIK.
PICTURELEN: equ 32000 * Bildgröße
*
* IMAGIC Komprimierung
*
* (c) 1987 by Jörg Drücker.
*
xdef SQZ_IMAG
END_SQZ: equ 31 ( End-of-data Flag )
PICTURE: equ 8
DESTINATION: equ 4
*===========================================
SQZ_IMAG:
* Teil I.
*
* (ESC)-Byte ermitteln:
movea.l PICTURE+8(sp),a0 * Bilddaten
bsr GET_ESCAPE
* ermittle (ESC)-Byte -> d0.b
moveq #0,d5
move.b d0,d5 * d5 = (ESC)
* Teil II.
*
* Datenaddressen ermitteln,
* Komprimierung vorbereiten:
movea.l PICTURE(sp),a0 * Bilddaten
movea.l DESTINATION(sp),a1
* kompr. Zielgebiet
move.w #PICTURELEN-1,d6 * Bytezähler
move.w #256,d4
moveq #3,d2
* Teil III.
*
* Quellbild im IMAGIC-Format codieren:
move.b (a0),d0 * Byte holen
moveq #-1,d3 * Initialwert Zähler
move.b d3,(a1)+
move.b #1,(a1)+
move.b d5,(a1)+
bra.s GET_NEXT* nächstes Byte holen
RECOUNT: tst.l d5 * Ende der Daten erreicht ?
bmi END_SQUEEZE
moveq #0,d3 * Zähler rücksetzen
GET_NEXT: move.b d0,d1 * letztes Byte sichern
move.b (a0)+,d0 * nächstes Byte holen
dbra d6,NEXT_BYTE * Bytezähler dekrementieren
bset #END_SQZ,d5 * "Ende-der-Daten" Flag setzen
bra.s WRITE_SQZ * und Daten schreiben
NEXT_BYTE:
cmp.b d0,d1 * vergl. aktuelles Byte mit Vorgänger
bne.s WRITE_SQZ
addq.w #1,d3 * Zähler inkrementieren
bra.s GET_NEXT * ... es gibt viel zu tun
* ( packen wir's ein ! )
*
* Die Kette gleicher Bytes ist unterbrochen,
* jetzt werden die Daten geschrieben:
WRITE_SQZ:
cmp.w d2, d3
* Komprimierung lohnt erst ab >3 Bytes !
bmi.s WR_M_SINGLE
*
* Für mehr als 3 gleiche Bytes wird ein
* Datenfeld (ESC)(Zähler)(Byte) geschrieben:
move.b d5,(a1)+ * (ESC) Byte schreiben
cmp.w d5,d3
beq.s WR_M_EOM
MULT_CT: cmp.w d4,d3
bmi.s M_NO_EOM
sub.w d4,d3
M_CT_2: move.b #01,(a1)+ * (01) für jeweils 256 Bytes
sub.w d4, d3
bpl.s M_CT_2
add.w d4,d3
WR_M_EOM: clr.b (a1)+
M_NO_EOM: move.b d3,(a1)+ * Zähler schreiben
move.b d1,(a1)+ * Datenbyte schreiben
bra RECOUNT
*
* Eine Komprimierung lohnt nicht,
* die Datenbytes werden einzeln geschrieben:
WR_M_SINGLE:
move.b d1,(a1)+ * Datenbyte
cmp.b d5,d1
bne.s WR_M_NEQ
*
* Datenbyte = (ESC) Byte ?
* jetzt muss (ESC)(ESC) geschrieben werden:
move.b d5,(a1)+ * (ESC) Byte
WR_M_NEQ: dbra d3,WR_M_SINGLE
bra.s RECOUNT
*
* Die Komprimierung ist beendet,
* das zuletzt gelesene Byte muß
* noch geschrieben werden:
END_SQUEEZE:
move.b d0,(a1)+ * letztes Datenbyte
cmp.b d5,d0
bne.s END_NEQ
move.b d5,(a1)+ * (ESC) Byte verdoppeln
*
* Die Datenmarke (ESC)(SAM)(00)
* wird geschrieben, um das Ende der
* Daten zu markieren:
END_NEQ: move.b d5,(a1)+ * (ESC)
move.b #$02,(a1)+ * (SAM)
clr.b (a1)+ * (00)
*
* Teil IV.
*
* Jetzt wird geprüft, ob die komprimierten
* Daten kürzer sind, als das Quellbild:
movea.l DESTINATION(sp),a2
* Startaddress Zielgebiet
suba.l a2,a1 * Ende-Start = kompr. Länge
move.1 a1,d0 * in dO zurückliefern
cmpi.w #PICTURELEN,d0 * Ergebnis > 32000 Bytes ?
ble.s ITS_OK * nein, dann war's gut
* Teil IVb.
*
* Das Ergebnis ist länger !!!
* -> also wird einfach das Quellbild
* kopiert.
move.w #PICTURELEN/4-1,d0 * Zähler
movea.l PICTURE(sp),a0 * Quellbild
movea.l a2,a1 * Zielgebiet
clr.b (a1) + * "segment_length" = 0 * = unkomprimiert !
* Bildinformation BYTEWEISE kopieren !
COP_LOOP: move.b (a0)+,(a1)+ * block copy
move.b (a0)+,(a1)+
move.b (a0)+,(a1)+
move.b (a0)+,(a1)+
dbra d0,COP_LOOP
suba.l a2,a1 * Länge
move.1 a1,d0 *in d0 zurück
ITS_OK: movea.l (sp)+,a0 * Heimataddresse
addq.l #PICTURE,sp * stack korrigieren
jmp (a0) * bye ...
*===========================================
*
* Escape - Byte ermitteln.
* Das Escape - Byte ist das Byte, das
* am wenigsten häufig im Bild vorkommt ...
*
* a0: Adresse Bilddaten
GET_ESCAPE:
link a6,#-512 * Zähltabelle einrichten
* Teil I.
*
* Zähltabelle auf Null setzen:
movea.1 sp,a3 * Startaddresse Tabelle
moveq #127,d3 * 256 Zählerwerte
CLR_LOOP: clr.l (a3)+ * Tabelle löschen
dbra d3,CLR_LOOP
* Teil II.
*
* Byte - Häufigkeiten im Bild ermitteln:
movea.1 sp,a3
move.w #PICTURELEN-1,d4 * 32000 Bytes zählen
ADD_LOOP: clr.w d3
move.b (a0)+,d3 * Byte holen
add.w d3,d3
addq.w #1,0(a3,d3.w) *Zählwert für jew. Byte erhöhen
dbra d4,ADD_LOOP
* Teil III.
*
* Byte mit der geringsten Häufigkeit
* ermitteln:
move.w #255-3,d3
move.w (a3),d4 * Startwert:Byte (00)
addq.l #6,a3 * Bytes (01) und (02) sind reserviert !
moveq #0,d0 * Noch ist (00) derFavorit ...
moveq #$03,d2 * ... und wir fahren bei (03) fort
CMP_LOOP: move.w (a3)+,d5
beq.s FINISH * Null ? besser geht's nicht
cmp.w d4,d5 * besser ?
bpl.s MORE
move.w d5,d4 * neuer Anhaltswert
move.w d2,d0 * und ein neuer Favorit
MORE: addq.w #1,d2 * nächster Kandidat
dbra d3,CMP_LOOP
bra.s RETURN
FINISH: move.w d2, d0
RETURN: unlk a6 * stack freigeben
rts * Return To Somewhere
*=======================================
end
Listing 3: Das Einpackprogramm
Jörg Drücker