I have been posting over in the General section about an adventure game project I am working on. Out of that has come the need for image compression. Rather than just pick out the best one from the demoscenesters bag of tricks I decided the best way to learn about it was to do it. It is also a topic close to my programming heart as I remember doing similar code for 68000 in the early nineties. Yeah, compressing stuff onto 720k floppies was a popular thing with the kids back then.
Requirements- Decompression algorithm must be simple, so I have a chance of writing the 6502
- Compression can be more complex- it will be implemented in a different language, doesn't need to run on target architecture
- I must be able to implement it quickly, as part of the wider project constraints
- Compression ratio must be reasonable, but does not have to be 7Zip good. Just better than RLE will be fine
- Must be able to blit to a screen buffer at the same time as decompression, there will be no space for temporary buffers
- No variable bit-width encoding- too complex for the moment (probably)
Here are my test images, they are all 104x104 pixel bitmaps (specifically, C64 hi-res mode, with 169 bytes of colour data, though the algorithm should be suitable for any bitmap data stored in bit-per-pixel format)
and here are the results
Code:
Original Improved
cellardoor 1352 1070
porsche 1352 1141
maxine 1352 817
The algorithm is very simple, it is a sliding-window method, one byte signals a pattern that has been seen before then the following byte contains the length of the pattern match in the hi-nybble and the offset to the pattern in the lo-nybble. A 'trick' (specific to image compression, over say text compression) is that a 0 offset indicates an offset of exactly one scanline.
The decompressor is very simple, here is the 6502 code for decompressing an image directly to a screen buffer that is wider than the source image. It uses a couple of 6502 tricks including 'reverse subtraction' and popping a couple of bytes off the stack to return directly to a caller from the middle of a function. The X register is held at 0 for much of the time, which is useful for indirect zero page addressing.
If anyone has any ideas on compressing colour attribute data I would love to hear them- this technique does not work at all well, typically saving 10-30 bytes. I would also be grateful if anyone could point me in the direction of state-of-the-art compression for 8 bit targets.
If you feel like this would be useful in your project, the compression algorithm is in compress.lisp in the github project,
https://github.com/djangojames/exploratoryCode:
;+ DECOMPRESS
DECOMPRESS 09E6 850A STA $0A ;Store the height
;Get the LFB
09E8 A200 LDX #$00
09EA 860C STX $0C
09EC A100 LDA ($00,X)
09EE 8508 STA $08
;Get a byte from the data and either emit
;it to the screen or check for the special
;LFB which signals a pattern
NEXT 09F0 E600 INC $00 ;DATA
09F2 D002 BNE $09F6
09F4 E601 INC $01 ;DATA + 1
09F6 A100 LDA ($00,X)
09F8 C508 CMP $08
09FA F006 BEQ $0A02 ;PATTERN
09FC 20630A JSR $0A63 ;EMIT
09FF 4CF009 JMP $09F0 ;NEXT
;Found a pattern. Extract the offset and
;set up a src pointer and a column to copy from
PATTERN 0A02 E600 INC $00 ;DATA
0A04 D002 BNE $0A08
0A06 E601 INC $01 ;DATA + 1
0A08 A100 LDA ($00,X)
0A0A 290F AND #$0F
0A0C F012 BEQ $0A20 ;ROW-ABOVE
;Pattern is on the same row, so we use the same
;scanline pointer for the source, but offset the
;column index by the amount in the lo-nybble
0A0E 49FF EOR #$FF
0A10 38 SEC
0A11 650C ADC $0C
0A13 850B STA $0B
0A15 A502 LDA $02 ;DEST
0A17 8504 STA $04 ;SRC
0A19 A503 LDA $03 ;DEST + 1
0A1B 8505 STA $05 ;SRC + 1
0A1D 4C310A JMP $0A31 ;COPY
ROW-ABOVE 0A20 A502 LDA $02 ;DEST
0A22 38 SEC
0A23 E928 SBC #$28
0A25 8504 STA $04 ;SRC
0A27 A503 LDA $03 ;DEST + 1
0A29 E900 SBC #$00
0A2B 8505 STA $05 ;SRC + 1
0A2D A50C LDA $0C
0A2F 850B STA $0B
;Get the pattern width from the hi-nybble
COPY 0A31 A100 LDA ($00,X)
0A33 4A LSR
0A34 4A LSR
0A35 4A LSR
0A36 4A LSR
0A37 18 CLC
0A38 6903 ADC #$03
0A3A AA TAX
NEXT-PATTERN 0A3B A50B LDA $0B
0A3D C509 CMP $09
0A3F D011 BNE $0A52 ;NOT-WRAPPED
0A41 18 CLC
0A42 A504 LDA $04 ;SRC
0A44 6928 ADC #$28
0A46 8504 STA $04 ;SRC
0A48 A505 LDA $05 ;SRC + 1
0A4A 6900 ADC #$00
0A4C 8505 STA $05 ;SRC + 1
0A4E A900 LDA #$00
0A50 850B STA $0B
NOT-WRAPPED 0A52 A8 TAY
0A53 B104 LDA ($04),Y
0A55 A40C LDY $0C
0A57 9102 STA ($02),Y
0A59 20630A JSR $0A63 ;EMIT
0A5C E60B INC $0B
0A5E CA DEX
0A5F D0DA BNE $0A3B ;NEXT-PATTERN
0A61 F08D BEQ $09F0 ;NEXT
;Emit a byte to the screen
EMIT 0A63 A40C LDY $0C
0A65 9102 STA ($02),Y
0A67 C8 INY
0A68 98 TYA
0A69 C509 CMP $09
0A6B D016 BNE $0A83 ;EMIT-END
;Scanline wrap
0A6D 18 CLC
0A6E A502 LDA $02 ;DEST
0A70 6928 ADC #$28
0A72 8502 STA $02 ;DEST
0A74 A503 LDA $03 ;DEST + 1
0A76 6900 ADC #$00
0A78 8503 STA $03 ;DEST + 1
0A7A A000 LDY #$00
0A7C C60A DEC $0A
0A7E D003 BNE $0A83 ;EMIT-END
;We are done, pop the stack return directly to caller
0A80 68 PLA
0A81 68 PLA
0A82 60 RTS
EMIT-END 0A83 840C STY $0C
0A85 60 RTS
;- DECOMPRESS
Login
Register
FAQ
Search
