Re: Checksums (was Re: Ping, checksum algorithm?)


Dave Borman (dab%oliver.CRAY.COM@uc.msc.umn.edu)
Fri, 25 Mar 88 11:49:32 CST


I feel compelled to respond to the recent explanation of the TCP/IP
checksum algorithm, because the explanation makes things harder than
they really are.

So how do you calculate the checksum? You add up all the 16 bit words
over the data that you want to checksum, and add all the carrys back
into the sum. When you are all done, you take the one's complement
of the final sum.

For outgoing packets, put 0 into the checksum field, calculate
the checksum, and fill it in.

For incoming packets, the checksum will calculate to 0 if the
data is correct.

That is it. Sweet and simple.

What about machine byte order? You can ignore it. It doesn't matter.
That's one of the great thing about this algorithm. Look at it
this way: as you pull the words from memory, they get byte swapped
into the register. So, all of our sum is done byte swapped. But
when you write the sum back out to memory, it swaps it back for you.

Another way of looking at the checksum: it sums up all the even bytes
into one sum, and all the odd bytes into another. All of the carries
from the even byte sum get added into the odd byte sum, and all of the
carries from the odd byte sum get added into the even byte sum.
The following table explicitly shows that the calculated checksum would be
calculated the same by bytes, Big-endian, and Little-endian byte order,
and in 16 bits or 32 bits at a time.

                                        Big-endian Little-endian
byte 0/1 0x00 0x01 0x0001 0x0100
byte 2/3 0xf2 0x03 0xf203 0x03f2
byte 4/5 0xf4 0xf5 0xf4f5 0xf5f4
byte 6/7 0xf6 0xf7 0xf6f7 0xf7f6
                ----- ----- ------- -------
sum1: 0x2dc 0x1f0 0x2ddf0 0x1F2DC

                0xdc 0xf0 0xddf0 0xf2dc
carrys: 1 2 2 1
                ---- ---- ------ ------
sum2: 0xdd 0xf2 0xddf2 0xf2dd

1's comp: 0x22 0x0d 0x220d 0x0d22

cksum back
to memory: 0x22 0x0d 0x22 0x0d 0x22 0x0d

For doing it 32 bits at a time, (like 4.3BSD does):

byte 0/1/2/3 0x0001f203 0x010003f2
byte 4/5/6/7 0xf4f5f6f7 0xf5f4f7f6
                ---------- ----------
sum1: 0xf4f7e8fa 0xf6f4fbe8

top half: 0xf4f7 0xf6f4
bottom half: 0xe8fa 0xfbe8
                ------- -------
sum2: 0x1ddf1 0x1f2dc

                0xddf1 0xf2dc
carrys: 1 1
                ------ ------
sum3: 0xddf2 0xf2dd

1's comp: 0x220d 0x0d22

back to memory: 0x22 0x0d 0x22 0x0d

Since I'm explaining all this, let me explain a tricky point for when
your data is not contiguous. Assume your data that you are checksuming
is in two pieces, and further that the the first chunk ends on an odd
byte boundry, and the second chunk begins on an even byte boundry.

You can calculate this in two pieces: one checksum for each piece
of data. Then, you swap the bytes of the second piece, and add it
into the first piece to get your final sum. (Or swap bytes on the first
piece, do the sum, and swap the bytes again. Depending on the implementation,
one or the other may be faster...) This gives you the speed
of doing word aligned operations, and you only need to add a minimal
amount of processing.

(note: when the byte count is odd, you fill in the missing part
with zeros)

        0/1 0x00 0x01 0x0001
        2/ 0xf2 0xf200
                                 ------
sum1: 0xf201

        4/5 0x03 0xf4 0x03f4
        6/7 0xf5 0xf6 0xf5f6
        8/ 0xf7 0xf700
                                -------
sum2: 0x1f0ea

sum2: 0xf0ea
carry: 1
                                 ------
sum3: 0xf0eb

sum1: 0xf201
sum3 byte swapped: 0xebf0
                                -------
sum4: 0x1ddf1

sum4: 0xddf1
carry: 1
sum5: 0xddf2

This got a little longer than I expected, but hopefully this should
clear things up some more.
                        -Dave Borman
                        CRAY Research, Inc.



This archive was generated by hypermail 2.0b3 on Thu Mar 09 2000 - 14:41:31 GMT