GEOS Bitmap Compaction Strategy
| Ariel's GEOS Programmer's Reference Guide | ||
|---|---|---|
| Back: Preface | Up: Contents | Next: GEOS Kernal Routines |
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
;
clc
lda source
adc dest+0
sta dest+0
bcc noInc ;carry was set if adc above overflowed
inc dest+1
noInc:
.endm
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
sec
sbc source
sta dest+0
bcs noDec ;carry was clear if sbc above underflowed
dec dest+1
noDec:
.endm
These definitions are entirely conjecture, inferred from their usage below, and may or may not be correct.
~ArielMT
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:
BitCompact
DESCRIPTION:
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:
C64:
Set dispBufferOn appropriately (to reflect which screen buffer to grab data from) and...
Cnvrt40:
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).
C128:
(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...
Cnvrt80:
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
;bitmap.
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).
Apple:
Use the Apple GEOS Kernal routines ReadScanLine and ReadBackLine to convert the internal Apple screen format into linear bitmap format. Nice and simple.
CALLED BY:
PASSED:
| 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. |
RETURNS:
| r0 | Points to byte following last byte in compacted data. |
DESTROYED:
a, x, y, r1-r6
PSEUDO CODE / STRATEGY:
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.
KNOWN BUGS / SIDE EFFECTS / IDEAS:
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.
(mgl)
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.
BitCompact:
10$:
; 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.
CountRepeat:
; 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
GetUnique:
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
rts