[9fans] snap checksum

[9fans] snap checksum

[erik quanstrom]

does anyone know if the function /sys/src/cmd/snap/take.c:/^sumr
can return 0 for a buffer that is not all zeros?

i think it can not, since for sum&1, the next sum at least
has 0x8000 set and otherwise if (sum&1) == 0, then either
sum == 0 or sum>>1 != 0.

fletcher-16 seems similar except for the extra sum.  does anyone
know of any writeups on this algorithm?  or at least an example
that shows that sum can return 0 for a non-zeroed buffer?

- erik

Re: [9fans] snap checksum

[Russ Cox]

> does anyone know if the function /sys/src/cmd/snap/take.c:/^sumr
> can return 0 for a buffer that is not all zeros?
> 
> i think it can not, since for sum&1, the next sum at least
> has 0x8000 set and otherwise if (sum&1) == 0, then either
> sum == 0 or sum>>1 != 0.

>>		if(sum & 1)
>>			sum = 0xffff & ((sum>>1)+*s+0x8000);
>>		else
>>			sum = 0xffff & ((sum>>1)+*s);

your logic does not account for the addition of *s,
which can cause an overflow that clears the 0x8000 bit.
ff 80 80 80 80 80 80 80 80 01.

> fletcher-16 seems similar except for the extra sum.  does anyone
> know of any writeups on this algorithm?  or at least an example
> that shows that sum can return 0 for a non-zeroed buffer?

sumr computes the same function as
plan 9's sum -r, which is also the same function as
seventh edition's sum.  i have always assumed the -r
stood for "research" as in research unix, although 
the plan 9 manual describes it as "system v's sum -r" and
other manuals describe it as the "historical bsd algorithm."
it does seem to have appeared first in v7.

russ

Re: [9fans] snap checksum

[erik quanstrom]

> > does anyone know if the function /sys/src/cmd/snap/take.c:/^sumr
> > can return 0 for a buffer that is not all zeros?
> > 
> > i think it can not, since for sum&1, the next sum at least
> > has 0x8000 set and otherwise if (sum&1) == 0, then either
> > sum == 0 or sum>>1 != 0.
> 
> >>		if(sum & 1)
> >>			sum = 0xffff & ((sum>>1)+*s+0x8000);
> >>		else
> >>			sum = 0xffff & ((sum>>1)+*s);
> 
> your logic does not account for the addition of *s,
> which can cause an overflow that clears the 0x8000 bit.
> ff 80 80 80 80 80 80 80 80 01.
> 

d'oh.  i must need more sleep. i forgot to add *s back in.

thanks for the historical perspective.

- erik

Re: [9fans] snap checksum

[Douglas A. Gwyn]

> sumr computes the same function as
> plan 9's sum -r, which is also the same function as
> seventh edition's sum.  i have always assumed the -r
> stood for "research" as in research unix, although
> the plan 9 manual describes it as "system v's sum -r" and
> other manuals describe it as the "historical bsd algorithm."
> it does seem to have appeared first in v7.

The "-r" option was added to the System V "sum", which
by default actually does a true modulo 2^16 sum of the bytes,
to obtain the Research version.  However, I think the "r"
may have been meant as a mnemonic for "rotating" rather
than "Research"; the "-r" algorithm rotates the accumulator
as the bytes are added to it.

Of course neither of these is as reliable as a polynomial-
based (feedback shift register) checksum for actual
checksumming applications.