Tile compression

mic_ · Post by **mic_** » Sat Aug 29, 2009 12:50 pm

I've made a small update to my image converter and packer. An LZSS decoder suitable for decoding directly to VRAM on the Megadrive is now included.

The tool itself is a command line application that can take an image in most common formats, resize it, reduce the number of colors, remove redundant tiles and LZSS compress the resulting data.

The Megadrive decoder is intended for GNU toolchains, and is currently about 170 bytes (which could probably be optimized a bit). It uses a few kB of RAM during decoding, starting from 0xFF8000 by default but that can be changed with a compile-time define.

tomaitheous · Post by **tomaitheous** » Sat Aug 29, 2009 7:12 pm

An LZSS decoder suitable for decoding directly to VRAM on the Megadrive is now included.

What's the ring buffer size?

I see you have SNES planar support. PCE tiles are stored in the same format. I found that storing the tiles in packed pixel format lead to better compression for LZSS. Converting on the fly while decompressing.

mic_ · Post by **mic_** » Sat Aug 29, 2009 7:19 pm

It's 4096 bytes by default, but you can adjust that by using either of these options when converting the image:

Code: Select all

-dict n	   Set the LZSS dictionary size in bytes. Valid values are 1024, 2048 and 4096.

-autocomp    Automatically choose the best settings for the LZSS encoder.

I haven't written a decoder for the SNES yet, so compressed tiles are only supported on the SMS/GG/Genesis. For the SMS/GG there are options in the converter to discard unused bitplanes.

As for the PCE, I was already aware of that:

Code: Select all

else if ((target == TARGET_SNES) || (target == TARGET_TGX))

So the PCE is already a supported target, I just haven't written a test program for it yet.

Chilly Willy · Post by **Chilly Willy** » Sun Aug 30, 2009 12:28 am

Great little app! It's tools like this that help bring more homebrew to a platform.

mic_ · Post by **mic_** » Mon Nov 30, 2009 5:51 pm

The tool now supports the 32X as well. Bitmaps can be converted to either linear 8-bit (-format l8) or direct color (-format d15). Since the tool already does LZSS encoding and includes a decoding routine for the 32X I didn't bother to add support for the 32X's RLE mode, but perhaps I will in a future version.

http://jiggawatt.org/badc0de/sixpack/

tomaitheous · Post by **tomaitheous** » Tue Dec 01, 2009 4:39 am

Great to see you're still working on this

Can I do some requests?

mic_ · Post by **mic_** » Tue Dec 01, 2009 6:59 am

Can I do some requests?

You can give suggestions

tomaitheous · Post by **tomaitheous** » Wed Dec 02, 2009 4:33 pm

Actually, maybe you already have support for this(?): 4bit linear pixel to planar on decompression? But packed 4bit, not padded.

mic_ · Post by **mic_** » Wed Dec 02, 2009 6:52 pm

Nope I haven't, but it's something I'm planning. You're talking about SNES now? Because I have no plans on writing any kind of LZSS decoder for the TurboGrafx in the near future

There's support for the TurboGrafx in the converter though. At least for pattern data output, but I've recently also added support for nametable/palette data output for the TurboGrafx (though that version hasn't been released yet).

What's missing is a test program for the TurboGrafx that will load the pattern/nametable/palette data to show a picture on screen. Most of the code I've found on the net has been for PCEAS, and I want to use WLA-DX so there are some minor differences to sort out. Also I have no idea which emulator to use.. I'd prefer one with some decent debugging capabilities (disassembler, memory viewer, BG/palette viewer). I have a TurboGrafx and a PCEFlash to test stuff with, but that's no good during the early development process.

mic_ · Post by **mic_** » Thu Dec 03, 2009 9:43 am

After some initial testing it seems like storing the data in a linear fashion saves about 15% on the compressed output size compared to planar data. Now I'll just have to write the decoders. Since they'll be specific for each tile format I'll probably concentrate on 4-bit and 8-bit tiles.

mic_ · Post by **mic_** » Wed Dec 09, 2009 5:15 pm

The converter now supports the 32X RLE framebuffer mode (use -target 32x -format rl8). Besides the compressed bitmap data and the palette data it will generate a file with an .ltb extension which contains the line table data (16 bits per scanline).

http://jiggawatt.org/badc0de/sixpack/

Chilly Willy · Post by **Chilly Willy** » Wed Dec 09, 2009 6:57 pm

Nice! Not sure when, but I'll get some use from this one day.

tomaitheous · Post by **tomaitheous** » Fri Dec 11, 2009 7:19 am

mic_ wrote:Nope I haven't, but it's something I'm planning. You're talking about SNES now? Because I have no plans on writing any kind of LZSS decoder for the TurboGrafx in the near future

There's support for the TurboGrafx in the converter though. At least for pattern data output, but I've recently also added support for nametable/palette data output for the TurboGrafx (though that version hasn't been released yet).

What's missing is a test program for the TurboGrafx that will load the pattern/nametable/palette data to show a picture on screen. Most of the code I've found on the net has been for PCEAS, and I want to use WLA-DX so there are some minor differences to sort out. Also I have no idea which emulator to use.. I'd prefer one with some decent debugging capabilities (disassembler, memory viewer, BG/palette viewer). I have a TurboGrafx and a PCEFlash to test stuff with, but that's no good during the early development process.

Not SNES, but TG16. PCEAS has some advantages over wla-dx (for labels and self modifying code). As for the tg16, I can't write the decompressor myself

As for a emulator, nothing beats mednafen for accuracy and the great debugger.

mic_ · Post by **mic_** » Fri Dec 11, 2009 9:37 am

Like I said, I have no plans in the forseeable future to write an LZSS decoder for the TurboGrafx. Any CPU without 16-bit registers is just too much of a hassle to write a decoder for IMO

But if you're a hardcore HuC6280 coder who wants to roll his own decoder and just aren't familiar with the algorithm, here's an example of what it might look like in C:

Code: Select all

// 12 bits means a dictionary size of 4096 bytes.
#define DICT_BITS	(12)
#define DICT_SIZE	(1 << DICT_BITS)

#define THRESHOLD	(2)

// 4 bits will be used to encode the string lengths in this
// case, which gives us a maximum string length of 18 bytes.
#define LEN_BITS	(16 - DICT_BITS)
#define LEN_MASK	((1 << LEN_BITS) - 1)

#define MAX_STRING	((1 << LEN_BITS) + THRESHOLD)


unsigned char textBuf[DICT_SIZE];

void lzss_decode(unsigned char *dest, unsigned char *src, int srcLen)
{
	int i, srcPos;
	unsigned char flags, numFlags, c, idx, j, strLen;
	unsigned short readPos, writePos;

	// Fill the text buffer with the same value used by the encoder
	for (i = 0; i < DICT_SIZE - MAX_STRING; i++)
		textBuf[i] = 0;

	srcPos = 0;
	writePos = DICT_SIZE - MAX_STRING;

	while (srcPos < srcLen)
	{
		// Read the flags byte
		flags = src[srcPos++];
		numFlags = 8;
			

		// Go through each of the 8 flags in the flags byte
		while ((0 != numFlags--) && (srcPos < srcLen))
		{
			if (flags & 1)
			{
				// Output the input byte directly
				*dest++ = src[srcPos++];
			}
			else
			{
				// This is a string offset and length encoded
				// in 16 bits.
				idx = src[srcPos++];
				j = src[srcPos++];
				readPos = ((j & 0xF0) << LEN_BITS) | idx;			
				strLen = (j & LEN_MASK) + THRESHOLD + 1;
				while (strLen--)
				{
					c = textBuf[readPos];
					readPos = (readPos + 1) & (DICT_SIZE - 1);
					textBuf[writePos] = c;
					writePos = (writePos + 1) & (DICT_SIZE - 1);
					*dest++ = c;
				}
			}
			// Shift out the flag that we just checked
			flags >>= 1;
		}
	}
}

Note that I haven't tested this code, I just wrote it off the top of my head to demonstrate the algorithm in a relatively clear way.

tomaitheous · Post by **tomaitheous** » Fri Dec 11, 2009 7:18 pm

As for the tg16, I can't write the decompressor myself

Opps typo. Corrected. "As for the tg16, I can write the decompressor myself". Cool, I'll work on the TG16 one decompressor then.