Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!zaphod.mps.ohio-state.edu!swrinde!elroy.jpl.nasa.gov!decwrl!parc!zweig From: zweig@parc.xerox.com (Jonathan M. Zweig) Newsgroups: comp.protocols.tcp-ip Subject: Re: TCP checksums Message-ID: Date: 30 May 91 20:10:04 GMT References: <3270025@hpctdlb.HP.COM> <1991May28.221045.27724@Think.COM> Sender: news@parc.xerox.com Reply-To: zweig.PARC@Xerox.com Organization: Xerox PARC Lines: 45 In fact, I can prove that if the ones-complement arithmetic is done the way I learned it at my mother's knee, then the TCP checksum field will never contain 0xffff, though it can contain 0x0000. I think it was dumb for UDP to use 0x0000 as the "no checksum" value, when 0xffff is impossible (i.e. you could implement a checksum algorithm that doesn't mess around with substituting -0 for 0 since it will never happen in a real datagram). The proof is based on the fact that the ones complement (1C) sum of a set of numbers is 0 (I will use 0 to mean 0x0000 and -0 to mean 0xffff) if and only if all of the numbers are 0. (<==) trivial. Add 0 to 0 and you get 0. (==>) observe that if the set of numbers to be added contains any nonzero (i.e. not 0x0000) number, there will be a 1 in at least one of the bit positions of one of the addends. The only way the corresponding bit in the sum could be 0 is if there are an even number (>=2) of 1's in that column of the sum. But wait! That means there will be a carry out of that position. Since 1C addition has end-around carry (i.e. you can perform the addition bitwise was long as you take the carry bit out of the leftmost single bit addition and add it back to the sum), that carry bit can't "go away". That is, the only way you will stop carrying is by adding the 1 to a bit of the sum that is 0. There is no way in 1C addition to add 1 to anything and have it end up as 0 (it will be -0, possibly, but never 0). This means that the carry bit out the end of any pairwise addition results in a nonzero sum. By induction, we see that there cannot exist a set of numbers not all 0 that add up to 0. Since RFC793 defines the checksum as the bitwise complement of the 1C sum of all the 16-bit words in a datagram, we see that since the sum can never be 0, the complement can never be -0. I am told that there are brain-damaged (to my mind) ways of implementing 1C arithmetic that automagically sustitute 0 for -0 if it is the result of an addition. So we can blame this boneheadedness with the 0/-0 switcheroo on them, I suppose. Does anyone know why UDP chose 0 (rather than -0) to indicate no checksum? Was someone smoking something? It seems to me it has complicated (albeit by only a couple of instructions) every TCP and UDP checksum calculation ever, at a cost to society of millions of dollars (add up all those cycles for me, please). Of course, it's probably far too late to start making a fuss about it now. -Johnny Checksum