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    dO,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



Links

Copyright-Bestimmungen: siehe Über diese Seite
Classic Computer Magazines
[ Join Now | Ring Hub | Random | << Prev | Next >> ]