Block-orientiertes Bildpacken
Die meisten Packformate für S/W-Bilder packen aufeinanderfolgende Bytes oder Byte-Folgen. Dies geht schnell und ist ist recht einfach, jedoch nicht für alle Fälle optimal. Das hier vorgestellte Verfahren packt nicht Byte-Folgen, sondern rechteckige Byte-Blöcke und komprimiert so einen 32-KByte-Bildschirm.
Auf dem ST gibt es inzwischen eine ganze Anzahl verschiedener Bildformate, die teilweise mehr oder weniger gut gepackt sind (wenn überhaupt). Das hier vorgestellte Packverfahren für S/W-Bilder ist ein blockorientiertes. Es verpackt 32000-Byte-Bilder, indem es rechteckige Byte-Blöcke der gleichen Farbe (schwarz oder weiß) oder eines einfachen Musters erkennt und entsprechend codiert. Im Vergleich zum DEGAS-Packverfahren, das nur aufeinanderfolgende Bytes erkennt und codiert, ergeben sich hier bei Bildern, die nicht zu komplex sind, eindeutige Vorteile. Bei komplexeren Bildern jedoch, die nicht sehr viele Flächen gleicher Bytes beinhalten, hat DEGAS die Nase wieder vorn (wenn auch nicht sehr weit...).
Der Byte-Block
Die verwendete Bildschirmdarstellung beträgt, wie jeder weiß, 640x400 Pixel, d.h. 80x400 Bytes. Der Algorithmus soll nun gleiche Bytes zu Blöcken zusammenpacken. Deshalb bewegen sich die Werte der x-Koordinaten und der Breiten der Blöcke im Bereich von 0..79, die der y-Koordinaten und Höhen von 0..399. Leider ist dies zu viel, um in einem Byte codiert zu werden.
Um dieses Manko zu beheben, wird nun einfach das oberste Bit der x-Koordinaten, bzw. der Breiten als 9.Bit der y-Koordinaten bzw. der Höhen interpretiert, denn die x-Werte finden in 7 Bit Platz (7 Bit ergeben Werte von 0..127).
Somit wäre die Position und Größe eines Byte-Blockes auf dem Bildschirm eindeutig in 4 Bytes beschrieben. Es fehlt nur noch das Byte selbst, aus dem der Block besteht, und er ist in 5 Bytes codiert.
Auf der Suche nach dem goldenen Block ...
Nun geht es ans Erkennen der Blöcke. Hierzu wird einfach, ausgehend von jedem Byte des Bildschirms, das die linke obere Ecke des Blockes bilden soll, das Rechteck mit dem größten Flächeninhalt berechnet, es sei denn, das zu untersuchende Byte ist schon in einem Block codiert.
Dieser Suchvorgang ist leider nicht so einfach, wie es scheint. Versuchen Sie sich doch einmal einen Algorithmus zu überlegen, der, ausgehend von einem weißen Karo, in einem Kreuzworträtsel das Rechteck mit dem größten Flächeninhalt findet. Die schwarzen Fragefelder wären hierbei die Begrenzung.
Mein Algorithmus geht folgendermaßen vor: Er berechnet die Breite eines möglichen Blockes, ausgehend von der linken oberen Ecke (das momentan zu untersuchende Byte). Mit dieser Breite und der Höhe des Blockes (am Anfang natürlich nur 1) wird der Flächeninhalt dieses Rechteckes berechnet. Dann wird die Breite des Blockes eine Zeile weiter unten gemessen. Mit diesem Wert, der max. die Breite der zuvor untersuchten Zeile annehmen kann, wird erneut der Flächeninhalt berechnet.
Ist dieser Flächeninhalt größer als der bis dahin größte Flächeninhalt, wird er als akt. Wert für diesen Vergleich gesichert. Auch die Breite und Höhe dieses Blockes werden als momentan beste Werte gesichert.
Der Anfangswert der Fläche A ist natürlich für den ersten Durchgang extra klein gewählt.
So wird mit jeder Zeile verfahren, bis die Breite Null wird, sich also ein anderes Byte unter dem Block befindet, an die Grenzen des Bildschirms oder eines anderen Blockes gestoßen wird.
Sind alle Blöcke auf diese Weise gefunden, werden die restlichen Bilddaten einfach linear hinter diese Blockliste geschrieben. Da alle Bytes, die zu Blöcken zusammengefaßt sind, in einem Boolschen Feld markiert sind, fällt es nun leicht, die unverpackten Bilddaten ausfindig zu machen.
Das Entpacken
Vor der Blockliste steht in einem Wort (16 Bit) die Anzahl der Blöcke dieses Bildes. Dann können beim Entpacken der Bilder alle Blöcke in den Bildschirmspeicher kopiert und in einem Boolschen Array markiert werden. Dies ist wichtig, um nun mit den anderen Bilddaten die entstandenen Lücken zu füllen. Zu beachten ist jedoch, daß das oberste Bit der x-Werte als das 9.Bit der äquivalenten y-Werte zu interpretieren ist.
Vielleicht experimentieren Sie ein wenig mit dieser Routine und erweitern sie um die Fähigkeit, Blöcke aus zwei oder mehr Bytes zu erkennen ...
* Blockorientiertes Packen von S/W-Bildern *
* --------------------------------------------- *
* ' pack:' *
* EINGABE: A0 - Adresse des 32000 Bytes Screens *
* A1 - Adresse des 'Packspeichers' *
* AUSGABE: A0 - Adresse des 32000Byte Screens *
* A1 - Adresse des 'Packspeichers' *
* D0.L - Länge der gepackten Datei *
* --------------------------------------------- *
* by Lars Schwabe (c) 1.-592 MAXON Computer *
* (erstellt mit dem Devpac Assembler) *
*************************************************
clr -(sp) * File mit den Bild-
pea fname * daten öffnen
move #$3d,-(sp)
trap #1
addq.l #8,sp
move d0,fhandle
pea screen,buffer * Bitmap einlesen
move.l #32000,-(sp)
move fhandle,-(sp)
move #$3f,-(sp)
trap #1
add.l #12,sp
move fhandle,-(sp) * File schließen
move #$3e,-(sp)
trap #1
addq.l #4,sp
lea screen_buffer,a0
lea pack_speicher,a1
jsr pack
move.l a1,adresse
move.l d0,laenge
clr -(sp) * File für's gepackte
pea save_name * Bild erstellen
move #$3c,-(sp)
trap #1
addq.l #8,sp
move d0,fhandle
move.l adresse,-(sp) * Daten schreiben
move.l laenge,-(sp)
move fhandle,-(sp)
move #$40,-(sp)
trap #1
add.l #12,sp
move fhandle,-(sp) * File schließen
move #$3e,-(sp)
trap #1
addq.l #4,sp
clr -(sp)
trap #1
* --------------------- *
* P A C K R O U T I N E *
* --------------------- *
pack: movem.l d1-d7/a0-a6,-(sp)
move.l a1, a4
clr (a1) * Blockzähler auf null
addq.l #2,a4 * A4=Anfang der Daten
lea boolean,a2
move.l a0,a6 * Daten sichern...
moveq #0,d7 * D6/D7 = X/Y-Zähler
pl1: moveq #0,d6 * (aufwärts zählend)
pl2: move.l ab,a3
move.b (a6}+,d0 * Byte heraussuchen...
cmp.b #1,(a2) * wurde das Byte schon
beq p1_end * bearbeitet???
* größtes Rechteck ab A3 nach D4-D5 schaffen
move.b d0,byte
move.l a2,a5
clr flaeche
clr hoehe
moveq #81,d1 * D1 = Spalten bis zum
sub d6,d1 * rechten Rand
move #401,d2 * D2 = Zeilen bis zum
sub d7,d2 * unteren Rand
moveq #-1,d4 * D4 = vorige Breite
moveq #1,d5 * D5 = Höhe (anfangs 1)
moveq #1,d3 * D3 = akt. Breite
bl1: cmp d1,d3
beq failed * rechten Rand erreicht?
cmp d2,d5
beq ende * unterer Rand erreicht?
cmp.b (a3,d3),d0
bne failed
cmp.b #1,(a5,d3) * ist das Byte schon
beq failed * in einem Block ???
addq #1,d3 * rechts war noch ein Byte
bra.s bl1
failed: cmp #0,d3 * ist der Block nach unten
beq ende * hin abgeschlossen ?
cmp di,d4
bhi neue_b
move d4,d3 * neue Breite > alte
neue_b: move d3,d4
mulu d5,d3 * (Fläche) A = D5 * D3
cmp flaeche,d3 * ist diese kleiner
bls f_kleiner * als die größte ?
move d3,flaeche
move d5,hoehe * (bessere Höhe & A)
f_kleiner: lea 80(a3),a3 * neue Zeile
lea 80(a5),a5 * neue 'Boolean-Reihe'
addq #1,d5
moveq #0,d3 * Breite der akt. Zeile 0
bra.s bl1
* nun muß die passende Breite ermittelt werden
ende: moveq #0,d4
move flaeche,d4
move hoehe,d5
divu d5,d4
* lohnt es sich überhaupt den Block einzutragen?
* d.h. (Fläche) A > 5
move d4,d0
mulu d5,d0
cmp #5,d0
bls p1_end
addq #1,(a1) * Blockzähler erhöhen
move.b d6,(a4)+ * X & Y eintragen
move.b d7,(a4)+
btst #8,d7
beq ybit8
bset #7,-2(a4) * das 7 Bit setzen
ybit8: move.b d4,(a4)+ * Breite/Höhe schreib.
move.b d5,(a4)+
move.b byte,(a4)+ * Byte eintragen
btst #8,d5
beg fill * 7. Bit der Breite
bset #7,-3(a4) * als 8. Bit der Höhe
* im 'Boolean-Feld' die Bytes des Blocks markieren
fill: subq #1,d4 * Breite
subq #1,d5 * Höhe
move.l a2,a5 * A5 = Pointer auf den
f_loop2: move d4,d0 * ersten Wert
f_loop1: move.b #1,(a5,d0)
dbf d0,f_loop1
lea 80(a5),a5
dbf d5,f_loop2
p1_end: addq.l #1,a2 * Boolean-Pointer erhöhen
addq #1,d6 * X-Schleife schließen
cmp #80,d6
bne pl2
addq #1,d7 * Y-Schleife schließen
cmp #400,d7
bne pl1
* alle Blöcke sind eingetragen, jetzt werden
* die restlichen Daten gesucht...
move (a1),d5
mulu #5,d5
addq.l #2,d5 * in D5 wird die
move.l a0,a3 * Länge berechnet
lea boolean,a5
move #399,d1
de_loop2: moveq #79,d0
de_loop1: cmp.b #1,(a5,d0)
beq de_check1
addq.l #1,d5 * Dateilänge erhöhen
move.b (a3,d0),(a4)+
de_check1: dbf d0,de_loop1
lea 80(a3),a3 * neue Bildschirmzeile
lea 80(a5),a5 * neue 'Boolean-Zeile'
dbf d1,de_loop2
move.l d5,d0 * Länge der Datei
movem.l (sp)+,d1-d7/a0-a6
rts
* ************ *
* DATA-Segment *
* ************ *
data
fname dc.b "a:\bilder\olympic.art",0
* Filename der 32000er-Bitmap
even
save_name dc.b "a:\bilder\olympic.com",0
* gepacktes Bild
even
* *********** *
* BSS-Segment *
* *********** *
bss
* vom Hauptprogramm
ssp ds.l 1
adresse ds.l 1
laenge ds.l 1
fhandle ds.w 1
screen_buffer ds.l 8000 * geladenes Bild
pack_speicher ds.l 8000 * gepackte Bilddaten
* ab hier zur Packroutine
boolean ds.l 8000 * Boolschen Array zum Packen
hoehe ds.w 1
flaeche ds.w 1 * Flächeninhalt eines Blocks
byte ds.b 1 * Byte des Blocks
* ENTPACKROUTINE *
* -------------------------------------------- *
* by Lars Schwabe (c) 1992 MAXON Computer *
* ******************************************** *
flaenge = 10206 * hier die Filelänge eintragen
* gepackte Bilddaten lesen
clr -(sp) * Datenfile öffnen
pea fname2
move #$3d,-(sp)
trap #1
addq.l #8,sp
move d0,fhandle
pea pack_speicher * Bitmap einlesen
move.l #flaenge,-(sp)
move fhandle,-(sp)
move #$3f,-(sp)
trap #1
add.l #12,sp
move fhandle,-(sp) * File schließen
move #$3e,-(sp)
trap #1
addq.l #4,sp
dc.w $a00a
move #$03,-(sp)
trap #14
addq.l #2,sp * log. Screen holen
move.l d0,a0 * ZIEL-Adresse
lea pack_speicher,a1 * QUELL-Adresse
jsr repack
dc.w $a009
move #$07,-(sp) * WARTEN...
trap #1
addq.l #2,sp
clr -(sp)
trap #1
* --------------------------- *
* E N T P A C K R O U T I N E *
* --------------------------- *
repack: movem.l d0-d1/d3-d4/a0-a4,-(sp)
lea boolean,a3 * Basis des Arrays
move (a1)+,d3 * D3 = Anz. der Blöcke
subq #1,d3
loop1: moveq #0,d6
moveq #0,d7
move.b (a1)+,d6 * X-Koordinate
move.b (a1)+,d7 * Y-Koordinate
btst #7,d6
beq check1
bset #8,d7 * 8.Bit bei Y setzen
bclr #7,d6 * 7.Bit bei X loschen
check1: moveq #0,d4
moveq #0,d5
move.b (a1)+,d4 * Breite
move.b (a1)+,d5 * Höhe
btst #7,d4
beq check2
bset #8,d5 * 8.Bit der Höhe 1
bclr #7,d4 * 7.Bit der Breite 0
check2: move.l a0,a2 * (Entpackspeichers)
move.l a3,a4 * (Boolschen Felde)
mulu #80,d7
add d7,a2
add d6,a2 * A2 = Startbyte im
add d7,a4 * 32000er-Screen
add d6,a4 * A4 = gleiches Byte, jedoch
subq #1,d5 * im boolschen Feld
subq #1,d4
move.b (a1)+,d0
movem d4-d5,-(sp) * D4/D5 sichern
loop3: move d4,d1
loop2: move.b d0,(a2,d1) * Byte des Blocks
dbf d1,loop2 * eintragen...
lea 80(a2),a2
dbf d5,loop3
* den Block im boolschen Array markieren,
* um die restlichen Bytes zu finden
movem (sp)+,d4-d5
f_loop2:move d4,d0
f_loop1:move.b #1,(a4,d0)
dbf d0,f_loop1
lea 80(a4),a4
dbf d5,f_loop2
dbf d3,loop1 * ab zum nächsten Block
* die Blocke sind eingetragen, jetzt noch die
* Grafikdaten linear in die Lücken schreiben
move #399,d5
grafik_2: moveq #79,d0
grafik_1: cmp.b #1,(a3,d0)
beq gcheck
move.b (a1)+,(a0,d0)
gcheck: dbf d0,grafik_1
lea 80(a3),a3
lea 80(a0),a0
dbf d5,grafik_2
movem.l (sp)+,d0-d1/d3-d4/a0-a4
rts
* ************ *
* DATA-Segment *
* ************ *
data
fname2 dc.b "a:\bilder\starp.com",0
* Filename des gepackten Files
even
* *********** *
* BSS-Segment *
* *********** *
bss
ssp ds.l 1
fhandle ds.w 1
screen_buffer ds.l 8000 * geladenes Bild
pack_speicher ds.l 8000 * gepackte Bilddaten
boolean ds.l 8000
* (um die noch nicht bearbeiteten Bytes zu finden,
* denn die Blöcke sind hier markiert)
Lars Schwabe