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.

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
Aus: ST-Computer 09 / 1992, Seite 88

Links

Copyright-Bestimmungen: siehe Über diese Seite