← ST-Computer 09 / 1992

Block-orientiertes Bildpacken

Programmierpraxis

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.

Rechtecke ab der linken oberen Ecke. Das graue hat die grĂ¶ĂŸte FlĂ€che.

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