Forums

Edit: split from http://www.smspower.org/forums/viewtopic.php?p=78028#78028

kroc wrote

Sonic 1 on the SMS has a quick and effective image compression algo. It splits the tileset into lines per tile and groups the same ones and the different ones. I've disassembled the routine so it wouldn't be difficult to implement.

Is the Sonic compression format documented? If you can give us the decompressor, someone (maybe me) can write a compressor plugin for BMP2Tile, and then we can get it made easy to use for homebrew. The only reason the Phantasy Star RLE compression is used so widely is because it was the first to be supported this way; but at the moment, Phantasy Star Gaiden compression is the "best" we have. Also, if it beats Sonic, you might swap the format to get some extra ROM space for your project.

The compression format is documented here: http://info.sonicretro.org/SCHG:Sonic_the_Hedgehog_%288-bit%29#Art_Compression

As an example, Green Hill's tileset (256 tiles) runs from $32FE6 to $34577, 5'522 bytes long. Uncompressed, it would be 8'192 bytes, so about a 48% savings. I don't know if Phantasy Star compression would be better, I've attached the Green Hill tileset for you to test with.

Sonic1-GreenHill-tiles.png (5.29 KB)

There's a bunch of duplicate tiles in there, but I'll assume they're the right ones. Here's what I get, ordered from large to small:

8,192 sonic1_greenhill_tiles_291 (tiles).bin
5,698 sonic1_greenhill_tiles_291 (tiles).hskcompr
5,663 sonic1_greenhill_tiles_291 (tiles).pscompr
5,522 <Sonic>
4,527 sonic1_greenhill_tiles_291 (tiles).psgcompr

Phantasy Star Gaiden is winning here too, by quite a margin. It's a fairly complex decompressor, taking 219 bytes, but quite cleverly tuned to the SMS graphics format.

Just for laughs, I ran the GHZ tileset through the Sonic 2 compressor. It did a shockingly poor job: 6,266 bytes. I think I've just found my weekend project...

So I wrote a compressor for the Sonic format, but it looks like I got something wrong, because I'm getting better compression than what you specified - 4964 bytes, in fact. PS Gaiden still wins, though.

I'm slightly curious how I saved so many bytes. I get the same 256-byte bitmask table as the Sonic data, which I count as having 1164 bits set (duplicate rows) and 884 unset (unique rows). I'd therefore expect 1164 bytes of duplicate row data and 884*4=3536 bytes of row graphics data, plus the 8 byte header, totalling 8 + 256 + 1164 + 3536 = 4964 bytes. Instead it seems to be 8 + 256 + 1722 + 3664 = 5650 bytes. Maybe there's a bunch of junk in the data? Did you write your own compressor yet?

Also, the first two bytes of the header are entirely unnecessary so you can avoid them too, if that helps... some more of the header could be avoided too, but only at the cost of rather a lot of CPU time.

gfxcomp_sonic1.zip (25.64 KB)

This is wrong! Don't use it, see below.

The indices in the duplicate row data may be multi-byte. If the index is >= 0xF0 then it's written as two bytes. You'd need something like:

uint16_t index = (uint16_t) std::distance(artData.begin(), it);
if(index >= 0xF0)
{
duplicateRows.push_back((uint8_t) (0xF0 | (index >> 8)));
}
duplicateRows.push_back((uint8_t) index);

Ah, I missed that :) 5522 bytes it is, so plenty of scope to free up some ROM space if you swap out the compression...

I added a copy of the decompressor here: http://www.smspower.org/Development/SonicTheHedgehogTileDecoder although it could use some cleaning up to be ready to compile in isolation.

I didn't bother with the tilemap compression, but it might also turn out to be uncompetitive...

gfxcomp_sonic1.zip (38.59 KB)

Bugfixed version

Thanks, this thread has been very useful. I will look at moving Sonic 1 to the Phantasy Star Gaiden format at a later date, so thanks for your work. Is there documentation on how to compress into this format?

http://www.smspower.org/Development/Compression#PhantasyStarGaidenDictionaryCodi...

I suggest trying to use my compressor DLL, it's probably VB-compatible. There is a standalone exe knocking around in the PS1JERT source.

Here's a slightly tweaked version of the decompressor ready for use with the above compressor. I modified it to save a few bytes of ROM space - it compiles to 115 bytes, needs 8 bytes of RAM, and has to run during VBlank or with the screen off, as I removed the delays between writes. It feels like it could be made faster/smaller still, but I'm not inclined to bother as it's not very competitive compression-wise anyway.

Sonic decompressor.zip (2.1 KB)

And how does the decompression speed compare? It can be of importance, too. :) You should put in the delays between writes in again and make them optional. It can make sense to have the same decompressor with and without them within the same program.

It feels no faster than the Phantasy Star decompressor, but I didn't time it. I guess I could make the delays optional, and also tune them to exactly 29 cycles, but there's no widely compatible way to conditionally exclude code, and we're starting to see new assemblers appearing these days...

Worry not, Sonic 1 always loads tilesets with the screen off.
Thanks for the amazing work! It won't be used just yet, I still have an assembler and a disassembly to complete, but it will become a part of it all. Every byte saved on data is more for the user to play with :)

Well, at some point I'd like to work on my old plan to have the compression plugins support decompression, to help with finding other games using the same compression. This might then help us discover games with novel compression routines and see if we can't do better than PS Gaiden. For now it seems to be a clear winner, though (although it does require 34 bytes of RAM, which is on the high side).

Author	Message
Maxim Site Admin Joined: 19 Oct 1999 Posts: 14741 Location: London	Sonic 1 graphics compression Posted: Tue Feb 18, 2014 4:08 pm Last edited by Maxim on Tue Feb 18, 2014 5:40 pm; edited 1 time in total
	Edit: split from http://www.smspower.org/forums/viewtopic.php?p=78028#78028 kroc wrote Sonic 1 on the SMS has a quick and effective image compression algo. It splits the tileset into lines per tile and groups the same ones and the different ones. I've disassembled the routine so it wouldn't be difficult to implement. Is the Sonic compression format documented? If you can give us the decompressor, someone (maybe me) can write a compressor plugin for BMP2Tile, and then we can get it made easy to use for homebrew. The only reason the Phantasy Star RLE compression is used so widely is because it was the first to be supported this way; but at the moment, Phantasy Star Gaiden compression is the "best" we have. Also, if it beats Sonic, you might swap the format to get some extra ROM space for your project.

Kroc Joined: 08 Dec 2013 Posts: 200	Posted: Tue Feb 18, 2014 5:17 pm
Kroc Joined: 08 Dec 2013 Posts: 200	The compression format is documented here: http://info.sonicretro.org/SCHG:Sonic_the_Hedgehog_%288-bit%29#Art_Compression As an example, Green Hill's tileset (256 tiles) runs from $32FE6 to $34577, 5'522 bytes long. Uncompressed, it would be 8'192 bytes, so about a 48% savings. I don't know if Phantasy Star compression would be better, I've attached the Green Hill tileset for you to test with. Sonic1-GreenHill-tiles.png (5.29 KB)

Maxim Site Admin Joined: 19 Oct 1999 Posts: 14741 Location: London	Posted: Tue Feb 18, 2014 5:56 pm
	There's a bunch of duplicate tiles in there, but I'll assume they're the right ones. Here's what I get, ordered from large to small: 8,192 sonic1_greenhill_tiles_291 (tiles).bin 5,698 sonic1_greenhill_tiles_291 (tiles).hskcompr 5,663 sonic1_greenhill_tiles_291 (tiles).pscompr 5,522 <Sonic> 4,527 sonic1_greenhill_tiles_291 (tiles).psgcompr Phantasy Star Gaiden is winning here too, by quite a margin. It's a fairly complex decompressor, taking 219 bytes, but quite cleverly tuned to the SMS graphics format.

Glitch Joined: 16 Dec 2008 Posts: 38 Location: UK	Posted: Tue Feb 18, 2014 7:19 pm
Glitch Joined: 16 Dec 2008 Posts: 38 Location: UK	Just for laughs, I ran the GHZ tileset through the Sonic 2 compressor. It did a shockingly poor job: 6,266 bytes. I think I've just found my weekend project...

Maxim Site Admin Joined: 19 Oct 1999 Posts: 14741 Location: London	Posted: Tue Feb 18, 2014 7:35 pm Last edited by Maxim on Tue Feb 18, 2014 9:12 pm; edited 1 time in total
	So I wrote a compressor for the Sonic format, but it looks like I got something wrong, because I'm getting better compression than what you specified - 4964 bytes, in fact. PS Gaiden still wins, though. I'm slightly curious how I saved so many bytes. I get the same 256-byte bitmask table as the Sonic data, which I count as having 1164 bits set (duplicate rows) and 884 unset (unique rows). I'd therefore expect 1164 bytes of duplicate row data and 884*4=3536 bytes of row graphics data, plus the 8 byte header, totalling 8 + 256 + 1164 + 3536 = 4964 bytes. Instead it seems to be 8 + 256 + 1722 + 3664 = 5650 bytes. Maybe there's a bunch of junk in the data? Did you write your own compressor yet? Also, the first two bytes of the header are entirely unnecessary so you can avoid them too, if that helps... some more of the header could be avoided too, but only at the cost of rather a lot of CPU time. gfxcomp_sonic1.zip (25.64 KB) This is wrong! Don't use it, see below.

Glitch Joined: 16 Dec 2008 Posts: 38 Location: UK	Posted: Tue Feb 18, 2014 8:54 pm
Glitch Joined: 16 Dec 2008 Posts: 38 Location: UK	The indices in the duplicate row data may be multi-byte. If the index is >= 0xF0 then it's written as two bytes. You'd need something like: uint16_t index = (uint16_t) std::distance(artData.begin(), it); if(index >= 0xF0) { duplicateRows.push_back((uint8_t) (0xF0 \| (index >> 8))); } duplicateRows.push_back((uint8_t) index);

Maxim Site Admin Joined: 19 Oct 1999 Posts: 14741 Location: London	Posted: Tue Feb 18, 2014 9:08 pm
	Ah, I missed that :) 5522 bytes it is, so plenty of scope to free up some ROM space if you swap out the compression... I added a copy of the decompressor here: http://www.smspower.org/Development/SonicTheHedgehogTileDecoder although it could use some cleaning up to be ready to compile in isolation. I didn't bother with the tilemap compression, but it might also turn out to be uncompetitive... gfxcomp_sonic1.zip (38.59 KB) Bugfixed version

Kroc Joined: 08 Dec 2013 Posts: 200	Posted: Tue Feb 18, 2014 11:45 pm
Kroc Joined: 08 Dec 2013 Posts: 200	Thanks, this thread has been very useful. I will look at moving Sonic 1 to the Phantasy Star Gaiden format at a later date, so thanks for your work. Is there documentation on how to compress into this format?

Maxim Site Admin Joined: 19 Oct 1999 Posts: 14741 Location: London	Posted: Wed Feb 19, 2014 8:16 am
	http://www.smspower.org/Development/Compression#PhantasyStarGaidenDictionaryCodi... I suggest trying to use my compressor DLL, it's probably VB-compatible. There is a standalone exe knocking around in the PS1JERT source.

Maxim Site Admin Joined: 19 Oct 1999 Posts: 14741 Location: London	Posted: Wed Feb 19, 2014 8:03 pm
	Here's a slightly tweaked version of the decompressor ready for use with the above compressor. I modified it to save a few bytes of ROM space - it compiles to 115 bytes, needs 8 bytes of RAM, and has to run during VBlank or with the screen off, as I removed the delays between writes. It feels like it could be made faster/smaller still, but I'm not inclined to bother as it's not very competitive compression-wise anyway. Sonic decompressor.zip (2.1 KB)

Martin Joined: 04 Nov 2004 Posts: 273	Posted: Wed Feb 19, 2014 8:59 pm
Martin Joined: 04 Nov 2004 Posts: 273	And how does the decompression speed compare? It can be of importance, too. :) You should put in the delays between writes in again and make them optional. It can make sense to have the same decompressor with and without them within the same program.

Maxim Site Admin Joined: 19 Oct 1999 Posts: 14741 Location: London	Posted: Wed Feb 19, 2014 9:51 pm
	It feels no faster than the Phantasy Star decompressor, but I didn't time it. I guess I could make the delays optional, and also tune them to exactly 29 cycles, but there's no widely compatible way to conditionally exclude code, and we're starting to see new assemblers appearing these days...

Kroc Joined: 08 Dec 2013 Posts: 200	Posted: Wed Feb 19, 2014 9:59 pm
Kroc Joined: 08 Dec 2013 Posts: 200	Worry not, Sonic 1 always loads tilesets with the screen off. Thanks for the amazing work! It won't be used just yet, I still have an assembler and a disassembly to complete, but it will become a part of it all. Every byte saved on data is more for the user to play with :)

Maxim Site Admin Joined: 19 Oct 1999 Posts: 14741 Location: London	Posted: Wed Feb 19, 2014 10:51 pm
	Well, at some point I'd like to work on my old plan to have the compression plugins support decompression, to help with finding other games using the same compression. This might then help us discover games with novel compression routines and see if we can't do better than PS Gaiden. For now it seems to be a clear winner, though (although it does require 34 bytes of RAM, which is on the high side).

Forums

View topic - Sonic 1 graphics compression