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:
- 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...
# 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.
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.
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