This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

Checksum for savestates

Checksum for savestates
by on (#208583)
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?
Re: Checksum for savestates
by on (#208586)
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.
Re: Checksum for savestates
by on (#208591)
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?
Re: Checksum for savestates
by on (#208592)
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.
Re: Checksum for savestates
by on (#208595)
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?
Re: Checksum for savestates
by on (#208596)
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.
Re: Checksum for savestates
by on (#208598)
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.
Re: Checksum for savestates
by on (#208600)
Good point! Did any games actually check for that though? I would have assumed it's usually an all-or-nothing deal.
Re: Checksum for savestates
by on (#208601)
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.
Re: Checksum for savestates
by on (#208604)
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.
Re: Checksum for savestates
by on (#208607)
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.

Quote:
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.
Re: Checksum for savestates
by on (#208608)
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.
Re: Checksum for savestates
by on (#208609)
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.
Re: Checksum for savestates
by on (#208617)
The cc65 runtime includes crc32 and adler32. Adler32 is faster.
Re: Checksum for savestates
by on (#208629)
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.

Quote:
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.
Re: Checksum for savestates
by on (#208633)
Tecmo super bowl uses a simple two byte checksum. If the current checksum doesn't match the saved checksum it wipes the entire SRAM.
Re: Checksum for savestates
by on (#208637)
Pokun wrote:
I love these screens since they show up so rarely.

I've never even heard of those screens. Got some examples?
Re: Checksum for savestates
by on (#208639)
calima wrote:
The cc65 runtime includes crc32 and adler32. Adler32 is faster.

I read that Adler32 has some weaknesses in that it's pretty easy to have the same hash value if only a few bytes are changed around.

CRC32 in cc65 requires 4 x 256 bytes in RAM. I wouldn't want to use an implementation that needs so many RAM values.
Re: Checksum for savestates
by on (#208640)
If you want a cryptographic hash, neither CRC32 nor adler32 are suitable.

If you don't want a cryptographic hash, you don't need to worry about byte shuffling. That isn't the kind of failure mode that will come from save RAM corruption.
Re: Checksum for savestates
by on (#208642)
DRW wrote:
I read that Adler32 has some weaknesses in that it's pretty easy to have the same hash value if only a few bytes are changed around.

That's a cryptographic weakness, i.e. it's easy for an attacker to modify the data without changing the hash. That's a different problem than just detecting errors in transmission.

You don't need to worry about attacks, though, users can already modify stuff easily in this case.

Your problem is just error detection, which Adler32 is actually designed for and relatively good at.


Edit: LOL ninja'd by lidnariq making the exact same distinction i did.
Re: Checksum for savestates
by on (#208645)
I don't need a cryptographic hash or any protection against hackers, only one where even a small difference already produces a completely different result to reliably spot corrupted data.

Regarding adler32, Wikipedia says:
https://en.wikipedia.org/wiki/Adler-32 wrote:
Adler-32 has a weakness for short messages with few hundred bytes, because the checksums for these messages have a poor coverage of the 32 available bits.

The German Wikipedia mentions this:
If byte n of the input is incremented by k, byte n + 1 is decremented by 2 x k and Byte n + 2 is incremented by k, then s1 (the sum of all bytes) and s2 (the sum of all in-between values of s1) remain unchanged.

So, doesn't this description mean that if three bytes next to each other are corrupted in this specific way, that the hash value still remains the same?
Re: Checksum for savestates
by on (#208646)
You're describing a complex enough process that it can basically be assumed to not happen by chance.
Re: Checksum for savestates
by on (#208648)
When wikipedia says it's "weak" it's a relative comparison against similar 32-bit checksums.

e.g. if you were comparing it against pretty much any 16-bit checksum it's rather strong.

For protection against errors in an NES save game, a 32-bit checksum is almost absurdly overpowered. 8 bits is probably already more than sufficient?

Think about it this way, if you had some sort of ideal hash (e.g. truly "cryptographically secure"), an 8-bit hash should give you a 1 in 256 chance of detecting an error. That's pretty good already, isn't it? Like the "weakness" of Adler32 is sort of like comparing a 1 in 4 billion chance to a 1 in 1 billion chance; the question is whether the result is still good enough, the magnitudes matter here. (...and the only result of failing to identify the error is just a save game with some wrong data in it, rather than just being destroyed. Not really a big deal?)

Here's some info on just how "weak" that weakness isn't:
https://guru.multimedia.cx/crc32-vs-adler32/
Re: Checksum for savestates
by on (#208659)
Bregalad wrote:
DRW wrote:
Savestates is an emulator-only thing.

Not really. There were devices, namely some late Game Copier models, that you can save the state of games to FDS disks, to be restored for later play. It's correct that battery save files normally don't contain (nearly) complete dumps of the system's states though, so indeed the terms have to be used carefully to avoid confusion. This applies to many later consoles using memory cards too.

I think in systems where storage is less of a concern, for example, PCs, some games probably dump (nearly) everything to their save files (so these files are indeed savestates), but for console games, especially on those retro systems, it's usually not cost effective to have the hardware or memory chips to hold the relatively huge states of games.
Re: Checksum for savestates
by on (#208660)
Yeah those devices are what I meant by special hardware. Modern flashcarts may also allow saving the state of the machine to a certain extent.
Western PC RPGs tend to allow you to store any item in any drawer or chest in the game and remembers them when saving, but even for that it may be enough if it only needs to remember changes I guess.

Sumez wrote:
Pokun wrote:
I love these screens since they show up so rarely.

I've never even heard of those screens. Got some examples?
Probably about any Dragon Quest game that uses a battery for saving (I and II uses passwords, although English Dragon Warrior I and II might have the screen). Joy Mecha Fight is another one I remember (when I bought it the battery was already old), I just tried it in an emulator by manually corrupting the save in a hex editor. It's just a text box that tells you the data corrupted in Japanese and some sound plays.
Re: Checksum for savestates
by on (#208661)
CRC16 should be good enough for practical error detection in most cases I can think of, and Greg Cook's tableless CRC16 is fast enough (66 cycles per byte).
Re: Checksum for savestates
by on (#218114)
i have made an adler32 online hash generator and the link is https://hash.onlinetoolsland.com/adler-32/,if you want to try it ,that will be good
Re: Checksum for savestates
by on (#218117)
What's the license on that calculation script? (Or should I call Hormel?)

In any case, I took this opportunity to write an (untested) implementation of Adler-32 based on the description at Wikipedia. I will warn that it's weak for messages smaller than about 1000 bytes because the sum won't reach the wrap at the prime modulus 65521.
Code:
MOD_ADLER = 65521
.proc adler32
src = locals+$00
negcountlo = locals+$02
negcounthi = locals+$03
a_lo = locals+$04
a_hi = locals+$05
b_lo = locals+$06
b_hi = locals+$07

  lda #1
  sta a_lo
  lsr a
  sta a_hi
  sta b_lo
  sta b_hi
  ldy src
  sta src
  byteloop:
    ; a += *src++
    lda (src),y
    iny
    bne :+
      inc src+1
    :
    clc
    adc a_lo
    sta a_lo
    lda #0
    adc a_hi
    sta a_hi

    ; if (a >= 65521) a -= 65521
    bcs a_overflow
    lda a_lo
    adc #65536-MOD_ADLER
    lda a_hi
    adc #0
    bcc a_no_overflow
    a_overflow:
      ; carry always set
      lda a_lo
      adc #65536-MOD_ADLER-1  ; compensate for carry
      sta a_lo
      lda a_hi
      adc #0
      sta a_hi
      clc
    a_no_overflow:
   
    ; b += a
    lda b_lo
    adc a_lo
    sta b_lo
    lda b_hi
    adc a_hi
    sta b_hi

    ; if (b >= 65521) b -= 65521
    bcs b_overflow
    lda b_lo
    adc #65536-MOD_ADLER
    lda b_hi
    adc #0
    bcc b_no_overflow
    b_overflow:
      ; carry always set
      lda b_lo
      adc #65536-MOD_ADLER-1  ; compensate for carry
      sta b_lo
      lda b_hi
      adc #0
      sta b_hi
    b_no_overflow:

    inc negcountlo
    bne byteloop
    inc negcounthi
    bne byteloop

  sty src
  rts
.endproc


EDIT: The difference between this and the version bundled with cc65 is that 1. mine uses the fact that 65536-65521 fits into 8 bits, and 2. mine doesn't call a bunch of stack manipulation in the inner loop.
Re: Checksum for savestates
by on (#218131)
tepples, you of all people should have remembered the posts above :P