1kb 6502 Image Compression

Unfortunately I didn't have much time over the Holiday break and I didn't get to finish this. I did however implement a Huffman encoder and funny enough the LZW encoded run length is still better.

I plan on finishing this at some point because image compression is still useful for my game system.

Based on all of the initial comments on this project I decided that LZW is a good initial approach. I implemented an encoder and the results are in: 853 bytes, or 16.6% smaller for the above image. The big question is, is this good enough? Can I implement a decoder and image display routine in 171 bytes??

To test that things are really working I also compressed the following image:

As expected this one is significantly smaller and came in at 163 bytes or 84% smaller.

The LZW algorithm I implemented is compressing run lengths rather than compressing at the byte level. My intuition tells me that this should give better results, but I guess I might as well see what the difference is. The algorithm is as follows:

• 6 bits for the initial dictionary size (0 - 31 will encode black runs, 32-63 encode white runs).
• Alphabet encodes a maximum run length of 32.
• Room for 192 codes with the code length still at 8 bits

I also did an initial stab at using the UP PNG predictor which basically subtracts the previous line from the current, but it didn't make much of a difference. I will see if I can eek out any better performance with the current trajectory I am on. But I need to balance the complexity of the decode algorithm with the compression ratio. Maybe arithmetic is next...