Thornton 2 dot Com

GEOS Bitmap Compaction Strategy

Ariel's GEOS Programmer's Reference Guide
Back: Preface Up: Contents Next: GEOS Kernal Routines

Go back to GEOS Graphics

The Hitchhiker's Guide to GEOS offers a bitmap compaction strategy almost entirely as a code section better suited for presentation as marked-up text. (For starters, the page width of its code approaches 100 character columns, well over the 80 columns of modern terminal defaults, let alone the 72 columns this website's code block regions top out at on desktop browsers.) Because of this, I have made the decision to reformat the bulk of the comments as regular markup and reformat the code to fit within 72 character columns (almost entirely by trimming whitespace). Aside from this, the only changes are incorporating the handwritten corrections and correcting only the most obvious errors the authors missed.

The original text is on pages 23-26 of the graphics section of the HHGG.

The source code uses a macro, AddBW, that is not defined in geoProgrammer. The way the macro is used, adding a byte from memory to a word in memory, suggests its definition would be:

.macro  AddBW   source,dest
; Add byte source to word dest, store sum in dest
        lda     source
        adc     dest+0
        sta     dest+0
        bcc     noInc      ;carry was set if adc above overflowed
        inc     dest+1

It uses a related macro, SubBW, that is also not defined in geoProgrammer. The way the macro is used, subtracting a byte from memory from a word in memory, suggests its definition would be:

.macro  SubBW   source,dest
; Subtract byte source from word dest, store difference in dest
        lda     dest+0
        sbc     source
        sta     dest+0
        bcs     noDec      ;carry was clear if sbc above underflowed
        dec     dest+1

These definitions are entirely conjecture, inferred from their usage below, and may or may not be correct.


Compaction Strategy

The easiest way to compact a bitmap image is to let geoPaint do it for you by cutting the image out as a photo scrap and pasting it directly into your geoProgrammer source code. Sometimes this method is impractical and you will want to compress images directly from within an application. The following subroutine can be used to compact bitmap data:



Converts linear bitmap data into compacted bitmap format, suitable for passing to routines such as BitmapUp.

When compacting bitmaps directly from screen memory, the data must first be converted from the internal screen format to linear bitmap format. The left edge of the source bitmap must start on a card boundary and the right edge must extend to the end of another card boundary. (Under Apple GEOS, strictly speaking, the edges need not fully extend to a card boundary because the new bitmap routines (NewBitUp, NewBitClip, etc.) can mask bits at the right edge.)

This bitmap data must then be converted to a linear format, where the first byte represents the first eight pixels of the upper-left corner of the bitmap, the next byte represents the next eight pixels and so on to the right edge of the bitmap. The byte following the last byte in a single line of a bitmap is the first byte of the next line. (The actual dimensions of the bitmap will be reconstructed from the WIDTH and HEIGHT parameters passed to the bitmap display routine.

To convert from internal screen format to linear bitmap format:


Set dispBufferOn appropriately (to reflect which screen buffer to grab data from) and...

     ldx     yPos          ; get y coord of top of bitmap
     jsr     GetScanLine   ; use it to calc screen ptrs
     lda     xPos          ; get x pixel coord (lo byte)
     and     #%11111000    ; strip off 3 bits for card x-position
     clc                   ; Add card offset to
     adc     r5L           ; base pointer (lo byte first)
     sta     r5L
     lda     xPos+1        ; (hi byte also)
     adc     r5H
     sta     r5H
     ;At this point, (r5) points to the first byte in
     ;the bitmap (upper-left corner).

Now step through each byte in this scanline by adding 8 to the pointer in r5 (compensating for the card architecture) to get to the next byte, and repeat this process for each line in the bitmap (incrementing yPos appropriately for each scanline).


(40-column, same as C64; 80-column, read on...)

Conveniently, the 80-column data is already in linear bitmap format. The data will probably be coming from the background buffer because the foreground screen is entirely contained on the VDC chip's internal RAM and is difficult to access...

     bit    graphicsMode          ; make sure in 80-col mode
     bpl    Cnvrt40               ; handle 40 like C64
     PushB  dispBufferOn          ; save current dispBuffer
     LoadB  dispBufferOn,#ST_WR_BACK ;force use of back buffer
     ldx    yPos                  ; get y coordinate
     jsr    GetScanLine           ; use it to calc screen ptrs
     MoveW  xPos,r0               ; copy x-position to zp work reg
     ldx    #r0                   ; divide r0 by 8
     ldy    #3                    ; (shift right 3 times)
     jsr    DShiftRight           ; this gives us the card offset
     AddW   r0,r6                 ; add card (byte) offset to scanline addr.
     ;At this point (r6) points to the first byte of the

Now step each byte in this scanline by adding 1 to the pointer in r6 to get to the next byte, and repeat this process for each line in the bitmap (incrementing yPos appropriately).


Use the Apple GEOS Kernal routines ReadScanLine and ReadBackLine to convert the internal Apple screen format into linear bitmap format. Nice and simple.



r0 Pointer to destination buffer to store compacted data (this buffer must be at least 1 and 1/64 of the size of the uncompacted data because it is possible, but unlikely, that the compacted data will actually be larger than the uncompacted data).
r1 Pointer to linear bitmap data to compact.
r2 # of bytes to compact.


r0 Points to byte following last byte in compacted data.


a, x, y, r1-r6


Starts with the first source byte and counts the number of identical bytes following it to determine whether to generate a UNIQUE or REPEAT packet. If there are three or less identical bytes in a row, a UNIQUE packet is generated, four or more generate a REPEAT packet. The packet is placed in the destination buffer and this process is then repeated until all bytes in the source buffer have been compressed.


Only use the UNIQUE and REPEAT compaction types. The BIGCOUNT compaction type is such that it is difficult to determine the compaction payoff point. BIGCOUNT could be used to compress adjacent scanlines that are identical because this type of check would be trivial. The basic scanline could be compressed with UNIQUE and REPEAT, then duplicated by placing it inside a BIGCOUNT.

This routine is not limited to compressing bitmap data. In fact, it works quite well on any data where strings of identical bytes are common (e.g., fonts). It does not, for example, compress text very efficiently. A Huffman-based algorithm yields better results.


MAX_REPEAT   =      127    ; maximum repeat COUNT value
MAX_UNIQUE   =      91     ; maximum unique COUNT value
UNIQ_THRESH  =      3      ; byte count threshold, beyond which a REPEAT
                           ; type should be used instead of UNIQUE.

                           ; r1 = current addr in source buffer
                           ; r0 = current addr in destination buffer
                           ; r2 = # bytes left in source
       jsr    CountRepeat  ; count the # of identical bytes here
       cmp    #UNIQ_THRESH ; Enough repeats to justify REPEAT type?
       ble    20$          ; No, go use UNIQUE
                           ; yes, use REPEAT (A = # to repeat)
       sta    r5L          ; store repeat # for later
       ldy    #0           ; init. index into buffers
       sta    (r0),y       ; store repeat # to destination
       lda    (r1),y       ; get repeat value
       iny                 ; point to next byte in dest buffer
       sta    (r0),y       ; store to destination buffer
       AddVW  #2,r0        ; move up dest. pointer
       bra    100$         ; exit.
20$:                       ;
                           ; use UNIQUE
       jsr    GetUnique    ; Calc # of unique bytes to use
                           ; (A = number of unique)
       ldy    #0           ; init. index into buffers.
       ora    #80          ; convert unique count to packet count value
       sta    (r0),y       ; store to dest.buffer
30$:                       ;
       lda    (r1),y       ; get first unique value
       iny                 ; increment pointer
       sta    (r0),y       ; store to destination buffer
       cpy    r5L          ; done yet? (r5L = repeat #)
       bne    30$          ; loop till done copying
       inc    r5L          ; convert to number to add to dest pointer
       AddBW  r5L,r0       ; move up destination pointer
       dec    r5L          ; correct back to # done
                           ; fall through to exit
100$:                      ;
       AddBW  r5L,r1       ; move up source pointer
       SubBW  r5L,r2       ; subtract off # left in source buffer
       lda    r2L          ; check for zero bytes left
       ora    r2H          ; more to do?
       bne    10$          ; if so, loop
       rts                 ; else, exit.
                           ; r1 = current pointer into source buffer
                           ; r0 = current pointer into destination bfr
                           ; r2 = number of bytes left in source
       ldy    #0           ; initialize relative buffer index
       ldx    #0           ; initialize current repeat count
       lda    (r1),y       ; get first byte
       sta    r6L          ; keep in r6L. This is the byte we're trying
                           ; to match.
10$:                       ;
       lda    r2H          ; more than 255 bytes left in source?
       bne    20$          ; if so, ignore # check
       cpx    r2L          ; else, are we at the last byte?
       beq    90$          ; if so, exit
20$:                       ;
       cpx    #MAX_REPEAT  ; check repeat count with max # of repeats
       beq    90$          ; if at maximum, branch to exit.
       lda    (r1),y       ; does it actually match?
       cmp    r6L          ; check against 1st byte
       bne    90$          ; if no match, exit
       inx                 ; else, we found a match. incr. repeat count
       iny                 ; move to next byte in source
;NOTE -- following branch changed to save a byte.
;        y is never incremented to $00.
;      bra    10$          ; and loop to check it
       bne    10$          ; branch always... iny above will always
                           ; clear z flag
90$:                       ;
       txa                 ; return repeat count in A
       rts                 ; exit
       PushW  r1           ; Save orig pointer
       LoadB  r5L, #0      ; start none unique
10$:                       ;
       inc    r5L          ; do one more unique
       ldx    r5L          ; get # unique so far
       lda    r2H          ; lots left?
       bne    20$          ; if so, skip and check
       cpx    r2L          ; all of them?
       beq    90$          ; if yes, then that many
20$:                       ;
       cpx    #MAX_UNIQUE  ; max # unique
       beq    90$          ; if full, do them
       AddVW  #1,r1        ; move up a byte
       jsr    CountRepeat  ; how many of following bytes are repeats?
       cmp    #UNIQ_THRESH ; Enough to warrant a REPEAT packet?
       ble    10$          ; No, go stuff them in this UNIQUE packet
                           ; Yes, close this UNIQUE packet.
90$:                       ;
       PopW   r1           ; retrieve start pointer
       lda    r5L          ; get # to do unique