In article <1175609409.840388.295420@e65g2000hsc.googlegroups .com>, "Brad" <bradmbreer@gmail.com> writes:
> martinmk's post is incorrect. It simply sums the two 16-bit words.
>
> Oops if I read the title earlier I would have seen that you were
> talking about UDP.
>
> UDP's checksum uses the 16-bit one's complement of the one's
> complement sum.
>
> In other words, all 16-bit words are summed together using one's
> complement:
>
> 1110011001100110 and 1101010101010101 (original 16-bit words)
>
> The one's complement of these are:
>
> 0001100110011001 and 0010101010101010

NO! That completely misunderstands one's complement arithmetic.

The proposed algorithm is incorrect.

[Briefly, that proposed algorithm was a+b = ~(~a+~b) ignoring carry]

Example using incorrect algorithm:

01 + 01 = ~(10 + 10) = ~00 = 11. *WRONG*

The one's complement sum of 01 + 01 is, in fact, 10. The carry matters.


Deep background...

The name "one's complement" arithmetic derives from the way that it
supports signed quantities. The encoding of a negative number
is the bit-by-bit "one's complement" of the encoding of the
corresponding positive number.

The encoding of +1 in sixteen bit one's complement is 0000000000000001
The encoding of -1 in sixteen bit one's complement is 1111111111111110

You may notice that zero has two encodings. All ones and all zeroes.


In order to add two signed numbers encoded in one's complement format,
the requisite algorithm is:

"Add the two numbers as ordinary unsigned binary numbers"
"If there is a carry, increment the result using ordinary unsigned addition"

Let's try it.

-1 1111111111111110
+ +1 0000000000000001
---- ----------------
0 1111111111111111

Yes. It works. Remember that all one's is an encoding of zero.

[It turns out that the all zeroes form will never appear as the result
of an addition operation unless both addends were zero]


-1 1111111111111110
+ +2 0000000000000010
---- -----------------
1 (1)0000000000000000
0000000000000001 (add the carry back in)
-----------------
1 0000000000000001

Yes. It works.

-2 1111111111111101
+ +1 0000000000000001
---- ----------------
-1 1111111111111110

Yes. It works.


Now back to the context at hand -- UDP checksum computation...

The use of one's complement format to represent signed quantities
was never very common. And using a flavor of signed arithmetic to
do a checksum computation doesn't make a whole lot of sense at first
glance. So why would someone choose "one's complement" for a checksum
algorithm?

For at least three good reasons.

1. The sixteen one's complement code space only uses 65535 codes.
That leaves one unused code to represent "no checksum computed".

2. It turns out that the one's complement addition algorithm is
endian-neutral. If you are on a little-endian machine
you can add up a column of big-endian ones-complement numbers by
pretending that they are little-endian ones-complement numbers.

The answer the little-endian machine computes will be bit-for-bit
identical to the answer a big-endian machine computes.

3. Computation of the checksum can be further accelerated on machines
with word lengths greater than 16 bits.


Now, back to the example...

> 1110011001100110 and
> 1101010101010101 (original 16-bit words)
------------------
(1)1011101110111011 (unsigned binary sum)
0000000000000001 (adding carry back in)
-------------------
1011101110111100 (ones complement sum)
-------------------
0100010001000011 (ones complement of ones complement sum)


Demonstration that little-endian arithmetic gets the same result...

0110011011100110 (first addend byte-flipped)
0101010111010101 (second addend byte-flipped)
-------------------
(0)1011110010111011 (unsigned binary sum)
0000000000000000 (no carry to add in)
-------------------
1011110010111011 (ones complement sum)
-------------------
0100001101000100 (ones complement of ones complement sum

0100010001000011 (byte-flipped back to big-endian)
> 0100010001000011 (earlier result cut-and-pasted for comparison)