News: 11 March 2016 - Forum Rules
Current Moderators - DarkSol, KingMike, MathOnNapkins, Azkadellia, Danke

Author Topic: Best compression method to use in a Snes game  (Read 8044 times)

DougRPG

  • Full Member
  • ***
  • Posts: 146
    • View Profile
Best compression method to use in a Snes game
« on: March 02, 2013, 11:18:41 am »
Hi, I need to find a compression method that gives me a very good compression rate. Even using two levels of compression, if necessary. Needs to be feasible to be used in a Snes game.

What do you suggest? What was the best compression methods you guys found in a Snes game?


KingMike

  • Forum Moderator
  • Hero Member
  • *****
  • Posts: 6923
  • *sigh* A changed avatar. Big deal.
    • View Profile
Re: Best compression method to use in a Snes game
« Reply #1 on: March 02, 2013, 11:22:32 am »
I'm not sure if it's the best, but LZSS seems to have been the most popular compression form used.
"My watch says 30 chickens" Google, 2018

FAST6191

  • Hero Member
  • *****
  • Posts: 2611
    • View Profile
Re: Best compression method to use in a Snes game
« Reply #2 on: March 02, 2013, 11:53:47 am »
I have been trying to read up on SNES compression as that is where most of the really interesting stuff stopped. I am mainly here to say there is a difference between runs on a SNES in reasonable time, runs on a SNES for a low end game and runs on a SNES in a game where every cycle counts and you have to try adding your decompression method in on top of what was formerly a straight copy/DMA transfer.

It can be quite unwieldy to make tweaks to after you have divined the best method for a given version of your hack but do also look at heavy game specific dictionary compression, DTE/MTE or even simple dual characters on a single tile, pointer construction (super mega fireball gives you the spells fireball, mega fireball and super mega fireball if the pointers are done right) and such like.

I can not say I would ever recommend double compression outside of a lossy compression method though. LZSS is probably as good as it gets though RLE, simple bitpacking and to a lesser extent huffman seem to have often appeared for reasons of limited CPU time. Even on the PC these days it is still largely a variation on LZSS but with a lot of tweaks towards memory, effective window size and general resources available and things like not doing it on a file by file basis in an archive but rather every file in the archive.

Bregalad

  • Hero Member
  • *****
  • Posts: 2644
    • View Profile
Re: Best compression method to use in a Snes game
« Reply #3 on: March 02, 2013, 11:56:50 am »
There is not an algorithm who gives best compression for everything, but rather a set of algorithms that works well for different kinds of input data.

I can only make publicity for the utility I wrote especially for this kind of cases.

Nightcrawler

  • Hero Member
  • *****
  • Posts: 5761
    • View Profile
    • Nightcrawler's Translation Corporation
Re: Best compression method to use in a Snes game
« Reply #4 on: March 02, 2013, 01:07:00 pm »
Dictionary with LZSS is usually the best bet here with the best overall performance, resource usage, ease of implementation, and ratios. Alternatively, you can look at seeing if Huffman is a good fit for your game and script.

These are just generic methodologies. The actual ratio you end up with depends upon your implementation details such as buffer sizes, tables, or other variables. Then, there's your source data and compressor quality. You could have a great and complicated algorithm, but without a quality compressor to take full advantage, your results will still come out poor.
TransCorp - Over 20 years of community dedication.
Dual Orb 2, Wozz, Emerald Dragon, Tenshi No Uta, Glory of Heracles IV SFC/SNES Translations

Dwedit

  • Sr. Member
  • ****
  • Posts: 303
    • View Profile
    • Dwedit's Website
Re: Best compression method to use in a Snes game
« Reply #5 on: March 03, 2013, 09:53:18 am »
I'm still a huge fan of Aplib.  Good compression rate, and fast to decompress.
"We are merely sprites that dance at the beck and call of our button-pressing overlord."

magno

  • RHDN Patreon Supporter!
  • Full Member
  • *****
  • Posts: 157
    • View Profile
    • Traducciones Magno
Re: Best compression method to use in a Snes game
« Reply #6 on: March 04, 2013, 07:41:45 am »
You can get the best compression ratio by using LZH, and IMO, is the best compression scheme for text. If you are clever enough, you can even skip the dictionary compression and only compress using Huffman.
The advantages of LZH are:

 * fast to decode: the bitstream is easily decoded with a few 65C816 instructions
 * great compression ratio: the most repetitive tour text is, the better compression (I compressed RS3 script from 180Kbytes down to 115Kbytes, including dictionary and Huffman tree)

The disadvantages:

 * you need some spare RAM in the SNES to allocate some variables to control the decoding process
 * the compression process can be a bit complex if you want to get the most of LZH

Bregalad

  • Hero Member
  • *****
  • Posts: 2644
    • View Profile
Re: Best compression method to use in a Snes game
« Reply #7 on: March 04, 2013, 10:14:45 am »
Could you guy expand more on what is Aplib and LZH ?
I'd really like to leave no stone unturned in my compess tools :)
(well I mean excluding anything that is too complex like 7-Zip, deflate and the like)

KC

  • Full Member
  • ***
  • Posts: 209
    • View Profile
Re: Best compression method to use in a Snes game
« Reply #8 on: March 04, 2013, 10:55:35 am »
Huffman as a text compression can be greatly enhanced by using more than one tree. It is very efficient if you use a different tree depending on the last byte you decoded (which would require up to 256 trees). An 'l' is much more likely to be followed by another 'l' than by a 'v', so the 'l' can have a shorter encoding in this situation. After a 'q', though, it would be much less likely and could therefore be encoded with a much longer bitstring. If a specific character is always followed by the same character, this could even be encoded with 0 bits, as the sub tree doesn't have to include any of the other characters and would be effictively empty except for one leaf.
As a real life example, in SRWJ I compressed 2.3mb of text down to around 1.1mb with it and a small dictionary. It doesn't require any additional memory for decoding and you only have to decode the parts that you need.

Bregalad

  • Hero Member
  • *****
  • Posts: 2644
    • View Profile
Re: Best compression method to use in a Snes game
« Reply #9 on: March 04, 2013, 11:03:27 am »
But isn't it incredibly conplex to encode and decode (up to) 256 different trees ?

As a generic huffman tree can't be encoded in less than 256 bytes, a 1st order system like one that you mention would require 64kb only to store the 256 trees.
Neededless to say, you'd require the data to be huge (>>64kb) in order to be efficient.

KC

  • Full Member
  • ***
  • Posts: 209
    • View Profile
Re: Best compression method to use in a Snes game
« Reply #10 on: March 04, 2013, 11:24:29 am »
The trees don't have to be complete for every possible value. They only need to contain the values that are actually used, so a tree could have anywhere between 1 and who knows how many nodes, and generally, you don't need more than 30 leaves (much less on average). You normally don't need all 256 trees either.
In my example, all trees together were 11kb, and the tree format was really unefficient. It was further bloated by the dictionary references, which were all a single byte.

Encoding 256 trees isn't any more complex than encoding one. You just change the tree you use your operations on after every byte. For decoding, you just parse a different tree depending on the last byte. It's not any more complex either.
« Last Edit: March 04, 2013, 12:33:40 pm by KC »

Zoinkity

  • Hero Member
  • *****
  • Posts: 562
    • View Profile
Re: Best compression method to use in a Snes game
« Reply #11 on: March 04, 2013, 04:05:30 pm »
There's also the 'fixed dictionary' variants, usually dedicated to things like ASCII text.  Preconstructed tables also shrink individual filesizes as they don't require the bitstream for the dictionary, but how untabulated values are handled is specific to the compression format. 

I assume you mean LZH as in the basic method and not LHA's LZH implementation, as that would be about as nasty as shoving zlib in there.  In fact, they get similiar compression ratios.

The intrinsic problem with choosing something is balancing memory requirements, CPU speed, and compression rates.  For instance, anything bytewise will require less processing than bitwise operations but will be larger in filesizes.  A faster decompression algorithm will probably get a worse compression ratio.  Some formats may require larger buffers, or in-place decompression may require more DMA, etc.

Bregalad

  • Hero Member
  • *****
  • Posts: 2644
    • View Profile
Re: Best compression method to use in a Snes game
« Reply #12 on: March 05, 2013, 05:12:37 am »
I think 1st order (or was it 2nd order ?) Huffman could be explored in my CompressTools.
For text with upper and lower case, you'd need about 2*26 trees of 2*26 nodes so this can be stored in about (2*26)*(2*26) = 2074 bytes, which is reasonable.

The problem is that, as the number of symbols used goes larger, both the amount of trees and their sizes goes larger, and it quickly becomes a big mess.

Another problem I'd think is : Which tree do you use for the very first symbol ? I think I could use either a different tree, or use the same one as the tree for symbol 0x00 for example, which is a "dirty hack" but it'd work and be easier to implement.

About LZH, I assume it's yet another LZ77 variant, so this means it requires to decompress and entire "sliding window" in size, and those are usually at least 8kb in size, which is a lot or RAM. Although on the SNES RAM is not so much a problem as on the NES.

henke37

  • Hero Member
  • *****
  • Posts: 643
    • View Profile
Re: Best compression method to use in a Snes game
« Reply #13 on: March 06, 2013, 11:48:58 am »
You could just store the first symbol as is.

LostTemplar

  • Hero Member
  • *****
  • Posts: 906
    • View Profile
    • au-ro-ra.net
Re: Best compression method to use in a Snes game
« Reply #14 on: March 07, 2013, 07:42:42 am »
True, but a dedicated tree might further reduce the number of required bits because most sentences/dialogs start with uppercase letters etc. If it's worth the trouble for like 2 bits per compressed string is another question, though.

DougRPG

  • Full Member
  • ***
  • Posts: 146
    • View Profile
Re: Best compression method to use in a Snes game
« Reply #15 on: March 07, 2013, 10:48:08 am »
Thank you guys....

Some Sega Genesis games uses this Multiple Huffman approach, like Landstalker, Shinning Force 2....

But how much better the multiple Huffman is, compared with the normal Huffman? Is there some study that compares the two methods?


This LZH is feasible to be used in a Snes game?


PS: LostTemplar, your inbox is Full.......

Hiei-

  • Sr. Member
  • ****
  • Posts: 373
    • View Profile
Re: Best compression method to use in a Snes game
« Reply #16 on: March 08, 2013, 08:30:14 am »
True, but a dedicated tree might further reduce the number of required bits because most sentences/dialogs start with uppercase letters etc. If it's worth the trouble for like 2 bits per compressed string is another question, though.

Sorry to post here, but your inbox is full since the last week, and as it seems you didn't received my email (sent you the french translated script of Arabian Nights), I don't see any other ways to contact you (I posted in the Arabian Nights thread but it's probably not visible because of the auto-merge function).

Bisqwit

  • Sr. Member
  • ****
  • Posts: 369
  • Polite, but politically incorrect.
    • View Profile
    • http://iki.fi/bisqwit/
Re: Best compression method to use in a Snes game
« Reply #17 on: March 10, 2013, 12:05:57 am »
Are you hacking an existing game, or creating a new one?
You might investigate what methods the game already uses. Maybe you could use an algorithm that was used in another game. Chrono Trigger for instance has a built-in LZ-based decompressor. You can find a document explaining the compression e.g. here: http://www.romhacking.net/documents/152/
A C++ implementation of the compressor (and decompressor) is found in Chronotools.

What do you plan to compress? Text? Level data? Graphics? Program code? Bytecode? Other?