Image compression

[djangojames]

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)

6502.org wrote:

Image no longer available: https://github.com/djangojames/exploratory/raw/master/blog/stairs.png

6502.org wrote:

Image no longer available: https://github.com/djangojames/exploratory/raw/master/blog/porsche.png

6502.org wrote:

Image no longer available: https://github.com/djangojames/exploratory/raw/master/blog/maxine.png

and here are the results

Code: Select all

           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/exploratory

Code: Select all

             ;+ 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

[BigEd]

There's a compressor described here
http://www.retrosoftware.co.uk/forum/vi ... f=73&t=999
which might be worth a look. Compression is offline in a high level language, and decompression routine is 76 bytes of 6502 code.

It might also be worth digging into the Bad Apple demo thread for compression ideas:
http://www.stardot.org.uk/forums/viewto ... 68#p160968
although this is video compression, so adjacent frames are similar, but it's not unlike images where adjacent lines are similar.

[pnoyes]

LZW is simple enough to implement with reasonable compression.

[rwiker]

There's also lz4, for which there are 6502/65c02 versions of the unpacker available (weighing in at 143 and 136 bytes, respectively).