Forums

Sega Master System / Mark III / Game Gear
SG-1000 / SC-3000 / SF-7000 / OMV
Home - Forums - Games - Scans - Maps - Cheats - Credits
Music - Videos - Development - Hacks - Translations - Homebrew

View topic - Sonic 1 graphics compression

Reply to topic
Author Message
  • Site Admin
  • Joined: 19 Oct 1999
  • Posts: 12820
  • Location: London
Reply with quote
Sonic 1 graphics compression
Post 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.
  View user's profile Send private message Visit poster's website
  • Joined: 08 Dec 2013
  • Posts: 197
Reply with quote
Post Posted: Tue Feb 18, 2014 5:17 pm
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.

  View user's profile Send private message Visit poster's website
  • Site Admin
  • Joined: 19 Oct 1999
  • Posts: 12820
  • Location: London
Reply with quote
Post 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.
  View user's profile Send private message Visit poster's website
  • Joined: 16 Dec 2008
  • Posts: 31
  • Location: UK
Reply with quote
Post Posted: Tue Feb 18, 2014 7:19 pm
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...
  View user's profile Send private message
  • Site Admin
  • Joined: 19 Oct 1999
  • Posts: 12820
  • Location: London
Reply with quote
Post 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.

  View user's profile Send private message Visit poster's website
  • Joined: 16 Dec 2008
  • Posts: 31
  • Location: UK
Reply with quote
Post Posted: Tue Feb 18, 2014 8:54 pm
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);
  View user's profile Send private message
  • Site Admin
  • Joined: 19 Oct 1999
  • Posts: 12820
  • Location: London
Reply with quote
Post 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

  View user's profile Send private message Visit poster's website
  • Joined: 08 Dec 2013
  • Posts: 197
Reply with quote
Post Posted: Tue Feb 18, 2014 11:45 pm
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?
  View user's profile Send private message Visit poster's website
  • Site Admin
  • Joined: 19 Oct 1999
  • Posts: 12820
  • Location: London
Reply with quote
Post 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.
  View user's profile Send private message Visit poster's website
  • Site Admin
  • Joined: 19 Oct 1999
  • Posts: 12820
  • Location: London
Reply with quote
Post 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.

  View user's profile Send private message Visit poster's website
  • Joined: 04 Nov 2004
  • Posts: 265
  • Location: Deutschland
Reply with quote
Post Posted: Wed Feb 19, 2014 8:59 pm
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.
  View user's profile Send private message Visit poster's website
  • Site Admin
  • Joined: 19 Oct 1999
  • Posts: 12820
  • Location: London
Reply with quote
Post 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...
  View user's profile Send private message Visit poster's website
  • Joined: 08 Dec 2013
  • Posts: 197
Reply with quote
Post Posted: Wed Feb 19, 2014 9:59 pm
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 :)
  View user's profile Send private message Visit poster's website
  • Site Admin
  • Joined: 19 Oct 1999
  • Posts: 12820
  • Location: London
Reply with quote
Post 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).
  View user's profile Send private message Visit poster's website
Reply to topic



Back to the top of this page

Back to SMS Power!