* Re: [9fans] snap checksum
@ 2008-01-12 19:06 Russ Cox
2008-01-12 19:30 ` erik quanstrom
2008-01-16 9:43 ` Douglas A. Gwyn
0 siblings, 2 replies; 4+ messages in thread
From: Russ Cox @ 2008-01-12 19:06 UTC (permalink / raw)
To: 9fans
> 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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [9fans] snap checksum
2008-01-12 19:06 [9fans] snap checksum Russ Cox
@ 2008-01-12 19:30 ` erik quanstrom
2008-01-16 9:43 ` Douglas A. Gwyn
1 sibling, 0 replies; 4+ messages in thread
From: erik quanstrom @ 2008-01-12 19:30 UTC (permalink / raw)
To: 9fans
> > 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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [9fans] snap checksum
2008-01-12 19:06 [9fans] snap checksum Russ Cox
2008-01-12 19:30 ` erik quanstrom
@ 2008-01-16 9:43 ` Douglas A. Gwyn
1 sibling, 0 replies; 4+ messages in thread
From: Douglas A. Gwyn @ 2008-01-16 9:43 UTC (permalink / raw)
To: 9fans
> 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.
^ permalink raw reply [flat|nested] 4+ messages in thread
* [9fans] snap checksum
@ 2008-01-11 19:39 erik quanstrom
0 siblings, 0 replies; 4+ messages in thread
From: erik quanstrom @ 2008-01-11 19:39 UTC (permalink / raw)
To: 9fans
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
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2008-01-16 9:43 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2008-01-12 19:06 [9fans] snap checksum Russ Cox
2008-01-12 19:30 ` erik quanstrom
2008-01-16 9:43 ` Douglas A. Gwyn
-- strict thread matches above, loose matches on Subject: below --
2008-01-11 19:39 erik quanstrom
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).