Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site ucbvax.BERKELEY.EDU
Path: utzoo!decvax!decwrl!ucbvax!bbnccv.arpa!jdreyer
From: jdreyer@BBNCCV.ARPA (Jonathan Dreyer)
Newsgroups: mod.protocols.tcp-ip
Subject: Re: IP, ICMP, TCP, and UDP checksumming.
Message-ID: <8510232322.AA23506@UCB-VAX>
Date: Wed, 23-Oct-85 19:14:00 EDT
Article-I.D.: UCB-VAX.8510232322.AA23506
Posted: Wed Oct 23 19:14:00 1985
Date-Received: Thu, 24-Oct-85 11:09:36 EDT
Sender: daemon@ucbvax.BERKELEY.EDU
Organization: The ARPA Internet
Lines: 38
Approved: tcp-ip@ucb-vax.arpa

The following argument is so simple, it must be wrong.

You should never have to "normalize" a ones complement checksum.

In the following, by "sum" or "+" I mean the ones complement sum, by
"0" I mean positive zero (all bits are zero), and by "full checksum
computation" I mean the complement of the (ones complement) sum.

Let S be the sum of all the words in a message except the checksum
field.  The checksum field of the message should thus contain ~S.  The
full checksum computation on the message with the checksum in place is
thus

	~(S + ~S).

But the sum of anything and its complement is all ones (~0) so

	~(S + ~S) = ~(~0) = 0.

This argument is based on commutativity and associativity of the ones
complement sum.  I think this is a valid assumption but don't have the
patience to verify it.

Another way of looking at it is to note that you can never get 0 in a
sum unless both addends are 0.  Think of it: you can only get zero (of
one flavor or other) when the addends are inverses, and the addends are
inverses only when they are complements or both zero.  Thus there are
three ways to get a sum of some kind of zero:

	0 + 0 = 0
	~0 + (+/~ 0) = ~0         (left as exercise)
	nonzero + ~nonzero = ~0.

Thus a full checksum computation (complement of the sum) can never
yield ~0, except when all the data is 0.  In this special case, the
checksum field should be ~0 so again the full checksum computation
yields 0.  Thus, in no case can the full checksum computation yield
~0.