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.

# IMAGIC komprimiert:

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:

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

  1. Begonnen wird mit dem ersten Bild der Animation: Es wird ganz normal gepackt, wie bisher.
  2. 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.
  3. Das Ergebnis wird dann gepackt.
  4. 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...

# Der Header einer Imagic-Datei

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.

# Direktes Differenzpacken

Das zweite Verfahren ist die "direkte Differenzkomprimierung”, wie sie vom IMAGIC-COMPILER beim Zusammensetzen eines Films eingesetzt wird:

  1. 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).
  2. Das Basisbild wird gepackt, wie bisher.
  3. 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.
  4. Gleiche Bildteile werden wie eine “transparente” Fläche in wenigen Bytes komprimiert.
  5. 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
Aus: ST-Computer 12 / 1988, Seite 99

Links

Copyright-Bestimmungen: siehe Über diese Seite