Checksum for savestates

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Checksum for savestates

Post by DRW »

What method did licensed NES games implement to check whether a savestate was corrupted and has therefore be presented as empty or whether the savestate is fine?
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
Pokun
Posts: 2675
Joined: Tue May 28, 2013 5:49 am
Location: Hokkaido, Japan

Re: Checksum for savestates

Post by Pokun »

I assume you are talking about the battery backup RAM and such used for save data. The term savestate is usually used for saving the state of the logic in the machine, which can only be done in an emulator or with special hardware.

I also would like to know this. From the few games I've inspected they used two bytes at the end of the data as some kind of checksum or something to see if there are save data (which may be only one or two bytes in FDS games to save level progress) in the save file. If it's incorrect it will just wipe the save file and write a new checksum. The only way to reinitialize some FDS games (without a way to manually write the disk) is to try to get a corrupt save file by for example turning off power during the write. In battery backup games you can at least disconnect the battery.
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: Checksum for savestates

Post by DRW »

Yes, I'm talking about the battery save. My next game has battery savestates and I want to include a hash value to make sure that savestates weren't accidentally corrupted. (They're either correct or get deleted.)

I can of course implement any random hash function, but I was asking whether a common method already exists.


By the way, did any NES game ever save battery data twice in case the savestate gets corrupted, so that it can still be corrected with the backup copy?

Or is this nonsensical since data corruption for WRAM (for example when not holding Reset when turning the game off) would spread across the whole RAM block anyway and would influence hundreds of bytes instead of just one or two?
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
lidnariq
Posts: 11429
Joined: Sun Apr 13, 2008 11:12 am

Re: Checksum for savestates

Post by lidnariq »

Most games with battery save use some kind of trivial checksum/CRC. I've never heard of anyone having found any evidence of error recovery.

I've been meaning to write a BCH-21/31 forward-error correction implementation for the NES for a while, but I don't know whether it would help with battery save corruption.
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: Checksum for savestates

Post by DRW »

Regarding backup, the big question is: From a technical viewpoint, if there is save corruption, would this only concern a few single bytes, so that a backup can be useful? Or does incorrect handling cause a whole spreading of data corruption over the whole RAM, so that every savestate and its backup will have a good bunch of incorrect bytes?
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
User avatar
Sumez
Posts: 919
Joined: Thu Sep 15, 2016 6:29 am
Location: Denmark (PAL)

Re: Checksum for savestates

Post by Sumez »

Why would you want to use a checksum to verify the data? Are you expecting people to manipulate their save data? I'd say if people go to the lengths required to do that, I think they deserve it. :D

It's much easier to just make up for example three hardcoded bytes that will always appear at a specific place in your save data, it would have the same chance of a fake positive as a checksum of the same size.
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: Checksum for savestates

Post by DRW »

Sumez wrote:Why would you want to use a checksum to verify the data?
Specifically for save corruption due to hardware failure. I don't want any byte of the game status to be in an invalid situation, so that the game might glitch.
Sumez wrote:It's much easier to just make up for example three hardcoded bytes that will always appear at a specific place in your save data, it would have the same chance of a fake positive as a checksum of the same size.
This will not help detect random bit corruption.
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
User avatar
Sumez
Posts: 919
Joined: Thu Sep 15, 2016 6:29 am
Location: Denmark (PAL)

Re: Checksum for savestates

Post by Sumez »

Good point! Did any games actually check for that though? I would have assumed it's usually an all-or-nothing deal.
Pokun
Posts: 2675
Joined: Tue May 28, 2013 5:49 am
Location: Hokkaido, Japan

Re: Checksum for savestates

Post by Pokun »

The games I've checked doesn't allow even one bit to be wrong or it will reinitialize the whole save file. I would think stray writes that may happen when turning off without holding reset could affect any number of bytes, but probably not the whole RAM. After all it's just random instructions that may execute when the CPU's voltage isn't stable anymore, and you are very unlucky if those random instructions happens to be writes in the cart RAM area. Also if the user resets or turns off power in the middle of saving, only part of the whole save block will be written and will become unreadable, so this will not affect the whole RAM either and must be considered too.

If you don't have too much save data in your game and don't need the rest of the RAM as extra work RAM, I think having multiple copies for recovery might be a good idea.

Edit: You might also want to do like many games do and display a special screen, whenever the battery RAM is reinitialized, that tells the user that save data has corrupted and wasn't able to be recovered, this makes it easy for the user to know that the battery is probably dying. An option to manually wipe the save data is also nice to have so you don't have to rip out the battery.
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: Checksum for savestates

Post by DRW »

Sumez wrote:Good point! Did any games actually check for that though? I would have assumed it's usually an all-or-nothing deal.
Well, what do you think how the all or nothing deal is ensured in the first place if there's no hash value?
Pokun wrote:The games I've checked doesn't allow even one bit to be wrong or it will reinitialize the whole save file.
In my case, I would do it on a per-savestate basis: If I have three slots, then I save three hash values.
Pokun wrote:If you don't have too much save data in your game and don't need the rest of the RAM as extra work RAM, I think having multiple copies for recovery might be a good idea.
The 8 KB will probably more than I ever need for the saveable statuses. And regular RAM will be more than enough for the regular game RAM itself, I would assume.

I might use the WRAM to copy code there that doesn't fit into the fixed bank anymore, so that I can have more than 16 KB of code without having to switch banks.
(Switching banks for code is something that I'd like to avoid unless it's a really, really separated area that's guaranteed not never access any other ROM stuff that might be in yet another bank.
One example for code that can safely go into a variable bank: The savestate screen logic.)
Pokun wrote:Edit: You might also want to do like many games do and display a special screen, whenever the battery RAM is reinitialized, that tells the user that save data has corrupted and wasn't able to be recovered, this makes it easy for the user to know that the battery is probably dying.
But this will make the people think something is wrong with their game when they turn it on the first time.
Nah, in this case, the save state will be treated as empty.

Also, in this case, I can simply delete a savestate by setting its hash value to 0. There would be no distinction between "valid, but empty state" and "empty state because it's invalid".
Pokun wrote:An option to manually wipe the save data is also nice to have so you don't have to rip out the battery.
Sure, this will be part of the game anyway.
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
User avatar
Bregalad
Posts: 8055
Joined: Fri Nov 12, 2004 2:49 pm
Location: Divonne-les-bains, France

Re: Checksum for savestates

Post by Bregalad »

DRW wrote:Yes, I'm talking about the battery save. My next game has battery savestates
It is completely false to use the word savestate for this. Please stop, you'll only be confusing people, NES-related vocabulary is already enough confusing/confused as it is. Savestates is an emulator-only thing. You're refering to battery saves.

As for your question, Final Fantasy II and Final Fantasy 3 uses a simple 16-byte checksum, calculated with the adc instruction. If the checksum is wrong, the save is considered to be "empty", but I don't think it'll be erased (I could be wrong), just that loading from it is impossible and trying to do so will trigger a new game.

Unlike most games, Dragon Quest games explicitly tells you when a save file is corrupt and there's even a music dedicated to that. I however do not know how the checksum mechanic works.

It is unfortunately mysterious why save corruption happens but it happen all the time, and that regardless whether reset is pressed or not when turning the console off. Note that turning the hardware off is only one of the possible cause for corruption, turning it on and having software glitches are two of the other possibilities when it comes to possible SRAM corruption, also having bad cart contacts too (this is typically the case with 72-pin frontloaders).

I do not know if any game duplicates the data, but it would make sense to do so, especially since save game data typically uses only a small part of the available 8k SRAM. With FInal Fantasy III I had to systematically save my data in two slots or even all 3 slots, to be sure at least one of those would be preserved. It happened quite regularly that one of the slot was erased, but never (so far) all slots simultaneously. So yes, SRAM corruption indeed does not appear on the whole chip at once.

If you are serious about analysing the problem I'd recommend you write tests program to test exactly that and see which parts of SRAM are corrupted and how.

As for the idea to add redundancy to allow recovery, CD ROMs use a row/column XOR based method that only adds some redundancy (about 20% ?) but allows to fix read errors most of the time. Maybe this would be interesting to apply that to NES saves (it's just an idea, perhaps it doesn't work the same way).

For example, if the save file is 1k ($400 bytes), you can make it virtually of 32 "lines" and 32 "columns" of bytes, and have the XOR of each row/column stored. This adds only 64 bytes of data (6.25% of total size), and if only one single byte is corrupted, it can be recovered. The drawback is that if more than one byte is corrupted, this does not work anymore.
and you are very unlucky if those random instructions happens to be writes in the cart RAM area.
Trust me you don't need to be very unlucky, just plain unlucky, for that to happen.
User avatar
FrankenGraphics
Formerly WheelInventor
Posts: 2064
Joined: Thu Apr 14, 2016 2:55 am
Location: Gothenburg, Sweden
Contact:

Re: Checksum for savestates

Post by FrankenGraphics »

Two methods beside "just" checksums. None is perfect. They cover for different things.

1
-Save two times in sequence
-Compare them
-if not equal: increase error_level, attempt again
if error level is larger than, say 3, escape.

This may reduce corruption caused during normal operation (however unlikely, maybe a sudden mains voltage fluctuation strangles power adapter ultimately the cpu for example), but it probably isn't sureproof against bad contacts.

2
If your savefile is really small, you could keep a save history for backup purposes. If the checksum is corrupt, revert to latest functioning one in a stack of n. Edit: Actually, stack might be the wrong word, because we rely on the items not changing place. Anyway, Notify the user while doing so. For example, if you have 10 (or 3, or 2) save instances (not to be confused with conventional save slots) for one campaign/user, alternate which one is overwritten by increasing the pointer each time a save has been made. Store the pointer separately for next session so the right one can be loaded. When loading; if the checksum says the file has been corrupted, decrease the pointer so that the next previous save is loaded instead.

...3
Thirdly, although this might not be a practical option(?), be on the look for hardware alternatives with write protection.
Last edited by FrankenGraphics on Fri Nov 24, 2017 8:35 am, edited 1 time in total.
User avatar
Dwedit
Posts: 4922
Joined: Fri Nov 19, 2004 7:35 pm
Contact:

Re: Checksum for savestates

Post by Dwedit »

Final Fantasy Mystic Quest on the SNES used multiple copies of each game save with checksums to ensure validity.

If you want to find out if NES games did the same thing, then look at the save file with a hex editor. Duplicates of the game saves will look obvious.

A common technique in TASes (tool assisted speedruns) is to do cycle accurate saved game overwriting to create a hybrid save of the partial saved game, and also mess around with the variables of the game before saving to get the correct checksum on the save file. For example, overwrite the X coordinate and Y coordinate on the overworld map separately.
You can't do this on Final Fantasy Mystic Quest due to multiple copies of the save file.
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!
calima
Posts: 1745
Joined: Tue Oct 06, 2015 10:16 am

Re: Checksum for savestates

Post by calima »

The cc65 runtime includes crc32 and adler32. Adler32 is faster.
Pokun
Posts: 2675
Joined: Tue May 28, 2013 5:49 am
Location: Hokkaido, Japan

Re: Checksum for savestates

Post by Pokun »

DRW wrote:In my case, I would do it on a per-savestate basis: If I have three slots, then I save three hash values.
Yes of course, if you have multiple save files you need separate checks for them all or else all save files would be wiped even when only one of them corrupts.
But this will make the people think something is wrong with their game when they turn it on the first time.
Nah, in this case, the save state will be treated as empty.
I would include an explanation to avoid that. Or simply just print a simple message "Save data cleared!" or even "No save data found!" so that it doesn't look like an error.
Bregalad wrote:Unlike most games, Dragon Quest games explicitly tells you when a save file is corrupt and there's even a music dedicated to that. I however do not know how the checksum mechanic works.
Yeah many later NES games do it, and it's common for later systems like SNES and N64. Dragon Quest plays the dramatic melody that normally plays when you are cursed, and other games also often use a screen with some dramatic effect that scares the shit out of you (maybe the games where tested with the battery in the factory so these screens don't show up the first time for the buyer). I love these screens since they show up so rarely.
Post Reply