ron@BRL.ARPA (Ron Natalie) (10/23/85)
This has come up before, but I don't know if we came up with an answer. When doing the complement of the ones complement sum, do you fix negative zero to be zero; pick one: never, after the sum and before the complement, after the complement. The obvious solution is to never normalize the value you insert in the header but always check for a comparison of 0 equals -0 when doing verification. Or, do we want to get more rigorous. -Ron
jdreyer@BBNCCV.ARPA (Jonathan Dreyer) (10/24/85)
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.
mann@SU-PESCADERO.ARPA (Tim Mann) (10/24/85)
The problem with your analysis is that it depends on a particular way of doing ones-complement arithmetic on a non-ones-complement machine. (Unsigned addition followed by end-around carry, with no normalization step.) If I have a true ones-complement machine, it would be perfectly legitimate for it to automatically normalize ~0 to +0 after every addition, in which case the property "you can never get 0 in a sum unless both addends are 0" does not hold. Also, treating ~0 and +0 as different makes it much more confusing to analyze the arithmetic, since if they are treated as identical, we have modulo (2^n) - 1 arithmetic, whose properties are well-known, but if they are treated as different, the system is not even a group. Nonetheless, I think your analysis is correct. The upshot is that IF you are checking a checksum on a twos-complement machine and doing end-around carry in software, you will never get ~0 after complementing if the checksum is correct. HOWEVER, you will not be robust, since another implementation may put +0 in the checksum field when it meant ~0, in a packet with zeroes in all other fields, in which case you WILL get ~0. (This is the only case in which you will get ~0.) This problem is a common one since it isn't absolutely clear to people who read the IP spec that "the ones complement of the ones-complement sum..." can never be +0. In fact, if one uses the above checksum-checking code to generate checksums as well, it is easy to make that mistake. This is a problem we actually ran into at Stanford a while back. In short, avoid headaches by normalizing. --Tim
don.provan@A.CS.CMU.EDU (10/24/85)
if you checksum the entire message (or header in IP), including the checksum field, you'll always get -0 regardless of what the sending entity put in the checksum field (assuming the packet isn't entirely zero, which isn't legal in IP and TCP and, i think, ICMP and UDP). if everyone used this approach (which, i believe, works just as well if the machine does your ones complement addition, although you'd check for +0 on a machine that normalized), we shouldn't have to worry about which one is "right". of course, when they change the checksum we'll all be up a creek...