Path: utzoo!utgpu!water!watmath!clyde!att-cb!osu-cis!tut.cis.ohio-state.edu!husc6!think!ames!pasteur!ucbvax!oliver.CRAY.COM!dab
From: dab@oliver.CRAY.COM (Dave Borman)
Newsgroups: comp.protocols.tcp-ip
Subject: Re:  Checksums (was Re: Ping, checksum algorithm?)
Message-ID: <8803251749.AA01012@oliver.cray.com>
Date: 25 Mar 88 17:49:32 GMT
Sender: usenet@ucbvax.BERKELEY.EDU
Organization: The Internet
Lines: 119


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.