Romhacking.net

Romhacking => Programming => Topic started by: justin3009 on May 22, 2016, 06:51:19 pm

Title: Save Game Compression [SNES]?
Post by: justin3009 on May 22, 2016, 06:51:19 pm
I'm rather curious if anyone knows of a method to compress certain data or even combine two bits of data into one just to make things smaller for SRAM.  I'm noticing Tales of Phantasia somehow stores a ludicrous amount of data unlike Breath of Fire 2.. which also uses only three saves as well but I can't quite make heads or tales of what's going on.

I'm wondering if anyone has any experience with something like this?  I'd seriously help out with what I'm hoping to do and I can't think of any other way to do it other than compressing some of the stats down into a single byte or so.
Title: Re: Save Game Compression [SNES]?
Post by: Gemini on May 22, 2016, 07:10:40 pm
Chrono Cross stores pretty much all its save data as bit streams of variable length, so it's not exactly that uncommon even on later systems. That works good for getting rid of redundant bits and makes the data not look human readable, not to mention you'd never run into worst-compressed cases where your data barely fits or overflows.
Title: Re: Save Game Compression [SNES]?
Post by: SunGodPortal on May 22, 2016, 08:46:17 pm
Just curious. What is your ultimate goal here? Why do you need to save space when SNES SRAM is so small?
Title: Re: Save Game Compression [SNES]?
Post by: justin3009 on May 22, 2016, 09:00:58 pm
Including Patty as a character into the game basically.  I want to make room for another PC as well but due to how things are, there's absolutely not enough room in SRAM unless I cut down the game saves to two at most.

The saves consist of PC stats which are 64 bytes each which there are 9 of them.  Then comes their spell tables which is 32 bytes each.  After that is all the Shaman Stat data (Which has been moved into the PC data already which saved 112 bytes), after that it's all the storyline flags.  Before any of the PC stats it has all the items you have in your inventory and in the bank along with your zenny amount, game time, battles, etc..

Thanks to the Shaman Stat data being moved around I have enough room for one more full PC with a spell table, but my end goal was to have room for about 2-3 more if possible.  If I dropped the entirety of the bank data then I could have 3 full new PCs in total with a spell table.

Basically, I just want to save as much room as possible to allow just a couple more characters to be usable.  I can't do much else unless I'm somehow able to shrink down the data heavily, which at this point, I don't think there's any excess data I can technically drop.  I almost thought about dropping the byte that dictates whether your equipment you have is a weapon or not.. but then I forgot that it needs that byte to dictate the quantity as well so that killed that idea.

Edit: Well, it's not the route I totally wanted to go but I think it's a fair trade off.  In the end, I'm going to completely nix the bank from the game.  With that and allowing 13 fully playable characters at max, this will increase the inventory from 48 items to 104 and the item cap will be increased from 9 to 15 and more items will be stackable as well to compensate
Title: Re: Save Game Compression [SNES]?
Post by: Nightcrawler on May 25, 2016, 07:03:31 pm
You can also expand the SRAM area about as easily as you can expand the ROM. The challenge of course is hacking the code to be able to utilize it. ;)
Title: Re: Save Game Compression [SNES]?
Post by: justin3009 on May 26, 2016, 05:10:28 am
SRAM doesn't get properly mirrored in Geigers making it not plausible sadly. I think it'd work fine in other emulators. I should probably switch to bSNES+ soon see if it has any problems with it.
Title: Re: Save Game Compression [SNES]?
Post by: oziphantom on June 13, 2016, 04:12:55 am
Story Bits are probably a good case for RLE. In that you start with
000000000000000000000000000000000000000000000000000
and for the most part will advance at
111111110000000000000000000000000000000000000000000
With the odd missed event here and there like
111101111111001000000000000000000000000000000000000

Hard to say on the others without seeing how the data is packed already.
Title: Re: Save Game Compression [SNES]?
Post by: justin3009 on June 13, 2016, 03:30:32 pm
90% of the SRAM legitimately consisted of your current items, quantity, stats of characters/names, what items you had in the bank, zenny amount, current PCs on screen and spell tables.  Otherwise I think the last couple hundred bytes are all triggers for chests/story flags.  I haven't played through and checked how the story flags update though to really fully figure out what is what.  Otherwise, the rest of the SRAM I already have figured out as it just flat out copies one giant chunk of RAM into SRAM and that's that.
Title: Re: Save Game Compression [SNES]?
Post by: RedGuy on June 15, 2016, 04:00:15 pm
I'm having a hard time coming up with ideas for a lossless re-encoding of the data that's guaranteed to fit without knowing more about the values the data takes.  You already acknowledged the brute-force way of trying to re-encode fields that are known to only have some values in less bytes.

The only idea I came up with is to support a full save vs incremental save.  You would reduce the save states down to supporting only 2 full saves, but 4 or more total incremental saves.  Incremental saves would use some frequency encoding to greatly increase the chance that an incremental save succeeds.  Another way to think about the same thing is to save-groups with common fields which can have several saves within each group.  If an incremental save doesn't work then the user has to accept that they have to replace the entire save group.
Title: Re: Save Game Compression [SNES]?
Post by: Retrolife on July 03, 2016, 03:25:35 am
I dunno it's fine the way it is really since u can save
Title: Re: Save Game Compression [SNES]?
Post by: Squall_FF8 on July 27, 2016, 10:46:56 am
LZ77 or variations will give you average compression of 50%.
 You may play a little bit and make yourself a dictionary for faster compress/decompress routine, but I doubt speed is the problem for you :)

On other hand, instead of storing all the data, you can make tables and store only indexes ...

Quote
Then comes their spell tables which is 32 bytes each
  I dont know the game details, but lets say your game have 32 spells total. Instead of holding indexes to each spell, you can use a bit field 32 bits. 1 mean you know/have Spell_XXX, 0 - not. This way you need only 4 bytes to store spell inventory  ;)
Title: Re: Save Game Compression [SNES]?
Post by: justin3009 on July 27, 2016, 05:33:38 pm
I'd normally try to compress the spells into a smaller few bytes, but the problem is that they can also learn a couple spells from NPC's that can be applied to basically any character.. which could make for a problem.  I think there's 3-4 spells you CAN learn from NPCs.  I could probably cut that down in SRAM if I really tried.  If anything, if their actual spells never change from leveling up, I'd just need that single byte spell byte and that'd pretty much tell the game all that's needed to know.

If I go back and redo this a bit, I could PROBABLY cut down the spell tables to be like 6 bytes in the absolute total which would free up enough room for like 3 more characters.  Although, I'm pretty sure that'll never happen PC wise.  Definitely could ease them down that way though for space.  I didn't even think about that for some reason.  Thanks for that post, that'll help tremendously!
Title: Re: Save Game Compression [SNES]?
Post by: Gemini on July 28, 2016, 07:03:23 am
Use bit streams and remove whatever redundancies. Say, if items have a quantity limit of 99 you can encode them in save data with 7 bits, which would provide some room to fit more stuff if the inventory is big enough (for example: 256 items would take 224 bytes to encode). That will always provide constant compression.
Title: Re: Save Game Compression [SNES]?
Post by: henke37 on July 29, 2016, 10:16:47 am
You can also use some huffman coding. It's quite likely that most inventory items will have a quantity of zero. You can squeeze that down to a single bit. Or even do RLE to note how many items in a row are zero.
Title: Re: Save Game Compression [SNES]?
Post by: justin3009 on July 29, 2016, 10:24:34 am
The only real problem with the item quantities is that they're also used to dictate what kind of item it is, i.e. Weapon, armor, consumable