[MPlayer-dev-eng] Patches for NUT

[Michael Niedermayer]

Hi

On Sun, Feb 05, 2006 at 06:17:53PM -0500, Rich Felker wrote:
[...]
> > > > I also considered 16 bit checksum, as adler32 is kind of a waste on 10-20 
> > > > bytes, but 16 bits is too weak. :/
> > > 
> > > How is using 32 bits to verify 80-160 bits overkill?
> > 
> > Because of adler's behavior... after testing, I found that about 8 bits are 
> > almost always zero (15 byte message), so it's effectively a 27 bit checksum 
> > taking up 32 bits... (max values are 12 bits 'a' and 15 bits 'b')
> > 
> > 24 bit adler is even weirder than adler16, so that's no good. Does anyone 
> > have any other thoughts regarding this?
> 
> I see. Michael, can you help with this? I have no good knowledge about
> effectiveness of checksums.

yep, wanted to comment on that anyway ...
adler isnt the best checksum around, but its fast and simple
the adler checksum is made of 2 parts s1 and s2

s1= sum of all b[i]       % 65521
s2= sum of all b[i]*(n-i) % 65521
checksum= (s2<<16) + s1

so s1 and s2 are
a           a
a+b         2a+b
a+b+c       3a+2b+c
a+b+c+d     4a+3b+2c+d
...         ...

for n bytes s1 <= 255*n and s2 <= 255*n*(n+1)/2
so for 15 bytes s1 <= 3825 (12bit) and s2 <= 30600 (15bit) -> only 27bits
possible non zero, and the distribution of s1 and s2 will be far from
random, thats somewhat bad ...

now how much of s1 and s2 do we need to store?
for 1 byte errors s1%256 is plenty to detect
for 2 byte errors s1 wont change as long as the errors are e and -e and the
error we can throw in s2 with that is (pos1 - pos2)*e so if we just store 
s2 % 257 and s1 % 511 or 512 then we should be able to detect all 2 byte 
errors as long as n<=257
for 3 byte errors s1 wont change as long as the errors are a,b,-a-b
                last-2, last-1, last
s2 factor            3,      2,    1
additative error:   +1      -2    +1

wont be detected no matter how much of s1 and s2 is stored
x bit crcs can always detect all burst errors with x or less bits, adler 
fails at a 17 bit burst with just 3 fliped bits

[...]
-- 
Michael