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.calima wrote:The cc65 runtime includes crc32 and adler32. Adler32 is faster.
CRC32 in cc65 requires 4 x 256 bytes in RAM. I wouldn't want to use an implementation that needs so many RAM values.
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.
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.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.
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.
Regarding adler32, Wikipedia says:
The German Wikipedia mentions this: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.
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?
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:
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.Bregalad wrote:DRW wrote:Savestates is an emulator-only thing.
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.
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.
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.Sumez wrote:I've never even heard of those screens. Got some examples?Pokun wrote:I love these screens since they show up so rarely.
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: Select all
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