It is currently Thu Sep 20, 2018 6:44 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 29 posts ]  Go to page Previous  1, 2
Author Message
PostPosted: Fri Nov 24, 2017 3:37 pm 
Offline

Joined: Sun May 03, 2015 8:19 pm
Posts: 95
Tecmo super bowl uses a simple two byte checksum. If the current checksum doesn't match the saved checksum it wipes the entire SRAM.


Top
 Profile  
 
PostPosted: Fri Nov 24, 2017 3:46 pm 
Offline
User avatar

Joined: Thu Sep 15, 2016 6:29 am
Posts: 741
Location: Denmark (PAL)
Pokun wrote:
I love these screens since they show up so rarely.

I've never even heard of those screens. Got some examples?


Top
 Profile  
 
PostPosted: Fri Nov 24, 2017 3:59 pm 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1684
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.

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
PostPosted: Fri Nov 24, 2017 4:02 pm 
Offline

Joined: Sun Apr 13, 2008 11:12 am
Posts: 7532
Location: Seattle
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.


Top
 Profile  
 
PostPosted: Fri Nov 24, 2017 4:11 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6809
Location: Canada
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.


Top
 Profile  
 
PostPosted: Fri Nov 24, 2017 4:16 pm 
Offline
User avatar

Joined: Sat Sep 07, 2013 2:59 pm
Posts: 1684
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?

_________________
Available now: My game "City Trouble".
Website: https://megacatstudios.com/products/city-trouble
Trailer: https://youtu.be/IYXpP59qSxA
Gameplay: https://youtu.be/Eee0yurkIW4
German Retro Gamer article: http://i67.tinypic.com/345o108.jpg


Top
 Profile  
 
PostPosted: Fri Nov 24, 2017 4:21 pm 
Offline

Joined: Sun Apr 13, 2008 11:12 am
Posts: 7532
Location: Seattle
You're describing a complex enough process that it can basically be assumed to not happen by chance.


Top
 Profile  
 
PostPosted: Fri Nov 24, 2017 4:33 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6809
Location: Canada
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/


Top
 Profile  
 
PostPosted: Fri Nov 24, 2017 10:01 pm 
Offline
User avatar

Joined: Sun Dec 12, 2010 10:27 pm
Posts: 321
Location: Hong Kong
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.


Top
 Profile  
 
PostPosted: Fri Nov 24, 2017 10:32 pm 
Offline

Joined: Tue May 28, 2013 5:49 am
Posts: 1008
Location: Hokkaido, Japan
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.


Top
 Profile  
 
PostPosted: Fri Nov 24, 2017 10:44 pm 
Online

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20562
Location: NE Indiana, USA (NTSC)
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).


Top
 Profile  
 
PostPosted: Mon May 07, 2018 7:05 am 
Offline

Joined: Mon May 07, 2018 7:03 am
Posts: 1
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


Top
 Profile  
 
PostPosted: Mon May 07, 2018 7:53 am 
Online

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20562
Location: NE Indiana, USA (NTSC)
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.


Top
 Profile  
 
PostPosted: Mon May 07, 2018 11:44 am 
Offline

Joined: Tue Oct 06, 2015 10:16 am
Posts: 796
tepples, you of all people should have remembered the posts above :P


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 29 posts ]  Go to page Previous  1, 2

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group