Just wondering what types of compression scheme you guy use or have used for the 65xx.

I've traced though quite a few CD games for the system I've been working with, documenting as I go, and found quite a few variants of LZSS, some basic RLE ones, and one unique RLE routine.

Pucrunch is by far the best compression scheme I've seen for 65xx - http://www.cs.tut.fi/~albert/Dev/pucrunch/. I've converted it for the huc6280 8k page system, so the source swaps out banks as it's reading the destination. This saves work space/ram as the source file only needs 8k of ram to read from, regardless of total size.

There's aPlib written for the z80 (http://www.smspower.org/maxim/smssoftware/aplib.html). I've been told this app is on par with Pucrunch and sometimes beating it. I haven't got around to converting it to 65xx as the syntax for the assembler is a bit strange. The GB(gameboy) assembler syntax version it easier to understand, but I haven't gotten around to it. Also, the GB being closer to a 8080 than a z80 also makes a little easier to convert IMO.


Most of, if not all, the stuff I need to compress are graphics. The video ram is only accessible via a 16bit port, so I'm in the process of converting pucrunch decompression routine to a circular buffer system for mem->I/O or I/O->I/O decompression. The circular buffer is the length of the LZ window.

I've generally used RLE for compressing graphics on the Apple/6502; obviously there are better algorithms for getting the size of the compressed image much smaller than that, but it's simple to do and gives a fair amount of compression, so it's been good enough. Variations on the RLE theme were pretty common on the Apple II; for example, to create the effect of more colors, it was common to make even rows be one color and odd rows be a different color, so rather than compress the image in the order it was stored in memory, the odd rows would be compressed, then the even rows (or vice versa). The modern equivalent of this RLE-style compression would be a .png file. (.png files support many more features, of course.)

Another common compression method was to store a sequence of commands to redraw the picture, in assembly, it might look like:



This method was used in a number of adventure games; when you went from one room to the next, you'd watch it draw the scene, giving it a slightly animated feel; for example, if you went outside, it might draw house as a triangle on top of a square, and the then paint the house using the flood fill (well, there'd be doors and windows too, but you get the idea). For speed reasons, a simplified flood fill algorithm was typically used. This simplified algorithm wouldn't be able to fill complex shapes like spirals. Instead the simplified flood fill would be called multiple times at different starting coordinates to fill in a complex shape section by section. The modern equivalent of this compression method would be a .svg file (or a postscript file).

In terms of compression that wasn't graphics-specific, plain old Huffman compression was used, but was ultimately supplanted by a utility called Shrinkit, which supported multiple compression methods (the modern equivalent here being a .zip file). LZW/LZ78-style compression was the method commonly used. There's a C program out there whose name escapes me (Nulib, maybe?) written for maximum portability so that Shrinkit archive files can be created/extracted/viewed under DOS, Unix, etc.

Anyway, it depends on what you're hoping to accomplish. Whether you want decompression to be fast, so that pictures can be displayed quickly, or whether you want the compressed image to be as small as possible so that you can fit as many images in memory as possible, etc.

Well... all the graphic data I'm using is pretty complex in detail. It's for a tile/sprite display system. The the screen is made up of 8x8 bitmap tiles each allowing up to 16 colors assigned from any one of 16 sub palettes, which are assigned 3bit RGB values (9bit RGB). The tiles are stored in planar format, but are stored in composite order. This really sucks for compression. I usually convert the tiles to 4bit packed(linear) format before compressing with LZSS which helps a lot. RLE is pretty useless for me though, with an exception for font characters.

So, has anyone here tried Pucrunch for the 6502? Just curious...

What, precisely, does "composite order" mean?

The tile being a 4bit planar 8x8 bitmap, each 8x8 plane would/should normally succeed the next, but in composite format the first two planes are interleaved between plane 0 and 1. After the first two complete 8x8 interleaving planes, then the next two planes follow (interleaved as well).

Like this:

p0 <-8 pixel row plane 0 (byte)
p1 <-8 pixel row plane 1 (byte)
p0
p1
p0
p1
p0
p1
p0
p1
p0
p1
p0
p1
p0 <- last 8 pixel row (byte)
p1 <- last 8 pixel row (byte)

p2 <-8 pixel row plane 2 (byte)
p3 <-8 pixel row plane 3 (byte)
p2
p3
p2
p3
p2
p3
p2
p3
p2
p3
p2
p3
p2 <- last 8 pixel row (byte)
p3 <- last 8 pixel row (byte)

That gives a total of 32bytes.

I assume they did this because for compatibility with the 2 bit planar tile mode for the Video processor (it was never officially used that I know of though). The SNES (Super Nintendo) video processor has the same 2/4bit formats. The reason why the planes are interleaved is because the video processor is word based access and so it can grab both planes in a single read access.

Ahh, that reminds me of how the Atari ST formatted its video data:

P0 P1 P2 P3 P0 P1 P2 P3 for 16-color mode, 320x200, where each Px was a 16-bit word.

P0 P1 P0 P1 P0 P1 P0 P1 for 4-color mode, 640x200

P0 P0 P0 P0 P0 P0 P0 P0 for 2-color mode, 640x400.

Ordering it this way allowed a single DMA channel to serve the same job as what other systems used 4 for.

(The Amiga, for example, and 25 DMA channels, of which no less than 16 or so were used for video-related purposes.)

I'm probably rehashing something you've already thought of, but is it possible perhaps to arrange the color palette so that compression is higher when just doing a linear transform of the data?

I've never written any games before so I'm just throwing out ideas.