From mboxrd@z Thu Jan  1 00:00:00 1970
To: 9fans@cse.psu.edu
Subject: Re: [9fans] snap checksum
From: "Russ Cox" <rsc@swtch.com>
Date: Sat, 12 Jan 2008 14:06:10 -0500
MIME-Version: 1.0
Content-Type: text/plain; charset="US-ASCII"
Content-Transfer-Encoding: 7bit
Message-Id: <20080112190615.5E7541E8C3A@holo.morphisms.net>
Topicbox-Message-UUID: 2cb5a768-ead3-11e9-9d60-3106f5b1d025

> 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