Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!ucbvax!BERSERKLY.CRAY.COM!dab
From: dab@BERSERKLY.CRAY.COM (David Borman)
Newsgroups: comp.protocols.tcp-ip
Subject: Re: TCP checksums
Message-ID: <9105311628.AA24660@berserkly.cray.com>
Date: 31 May 91 16:28:27 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Distribution: world
Organization: The Internet
Lines: 59

> In 1's complement arithmetic there are two ways of writing "zero". In C they
> are 0x0000 and 0xffff (16-bit).  I can't see any reason why the checksum would
> need to always come out to be nonzero (i.e. 0x0000 could happen).
> 
> Consider the 16-bit ones complement of the 16-bit ones complement sum of a
> bunch of numbers that happen to add up to 0xffff (such as, say, 0xff00 and
> 0x00ff with a bunch of 0x0000's too). Yikes! It is all zeroes.
> 
> The TCP checksum is never optional (though you can use a different one if you
> like, by supporting RFC1146-style checksum algorithm negotiation), but it is
> not clear to me that it cann never be all zeroes.
> 
> In fact, I can't figure out a way that the checksum would ever be 0xffff
> ("negative zero").  If you can think of a set of 16-bit values whose TCP
> checksum is 0xffff let me know.  Since 0xffff + 0xffff = 0xffff (and not
> 0x000), I can't figure out a sum that comes out to 0x0000 in order to get
> complemented to 0xffff by the vanilla TCP checksum algorithm.
> 
> -Johnny Checksum

An interesting observation, and not very hard to prove.

If you look at the sequence of numbers incrementing by 1 at
the wrap around point, you have:

		... FFFE, FFFF, 0001, 0002 ...

Notice that 0000 is skipped, because:

		FFFF + 0001 = 10000 = 0001.

So, the only way that the 1's sum would be 0000 would be if each of
w1 through wn were equal to zero.

If you take the 1's complement of the sequence, you have:

		... 0001, 0000, FFFE, FFFD

Which is just the sequence of numbers decrementing by 1, at the
wrap around point.

So, just as addition will never yield a value of 0000, subtraction
will never yield a value of FFFF.  Another way of stating it is that
when the 1's sum wraps, it will give you -0, when the 1's difference
wraps, it will give you +0.

If you wanted to, since 0000 and FFFF are both identity elements, if
the 1's sum was computed to be FFFF, you could replace it with 0000,
and send the 1's complement of it across as the checksum, and everything
will work just fine; on the destination machine the checksum will still
compute as valid.

In fact, if you look at the BSD udp_output() code, if the checksum
is calculated to 0000, it is replaced with FFFF to ensure that the
destination machine will verify the checksum rather than skip the
checksum.  Because the TCP checksum is required, it doesn't bother
to change 0000 into FFFF.

			-David Borman, dab@cray.com