|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 ; 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.
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...
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).
(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).
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.|
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.
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