Date: Wed, 17 May 2000 23:27:19 -0700 (PDT) From: Matthew Dillon <dillon@apollo.backplane.com> To: Dave Preece <dave.preece@kbgroup.co.nz> Cc: hackers@FreeBSD.ORG Subject: Re: Musings on ip checksumming Message-ID: <200005180627.XAA29185@apollo.backplane.com> References: <67B808B0DD93D211ABEE0000B498356B02BBF9@internet.kbgroup.co.nz>
next in thread | previous in thread | raw e-mail | index | archive | help
:I'm trying to write a simple static NAT, and have got a bit stuck with the
:new checksum in the IP header.... thing with me is that I'm not happy about
:something till I understand it (and it appears that the IP stack is well
:behaved and won't send something unless the IP checksum is right either).
:
:Looking into ping.c for an example we have a checksum calculator (in_cksum)
:that I have been trying to understand. It takes a header and adds all the 16
:bit words to a 32 bit acumulator. Fine. It then takes the top 16 bits and
:adds them to the bottom 16, (adding an additional one if this operation
:itself takes the resulting number to 17). Not what I understand as a
:checksum, but none the less a perfectly valid algorithm.
:
:What I *don't* understand is this: The routine appears to be written as if
:would only work on a big endian system i.e. this would only work if
:u_short's and int's were stored most significant byte first. This impression
:is further underscored by using >> 16 to fold the top 16 bits into the lower
:16 bits. The pile of htons calls and ntohs calls I was expecting to see is
:simply not there.
:
:So, how come it works?
:
:Dave :) (but a bit confused)
:
:
:Ref:
:/usr/src/sbin/ping/ping.c
:/usr/src/lib/libalias/alias_local.h (ADJUST_CHECKSUM)
All the wierdness is because an IP checksum is a 1's complement
summation (not the 2's complement summation we are used to in
the digital world). Some of the earliest computers built used
1's complement to store numbers.
In 1's complement arithmatic there are two 0's. Take an 8 bit
number: 00000000 is a zero, and 11111111 also means zero. Thus
when you add two numbers together and get a carry, you have to
add it back in. 11111111 + 1 == zero + 1 == one, which is
represented by 00000001. (In 2's complement addition there is
only one zero, 00000000. 1111111 means -1. -1 + 1 == 0 (00000000),
so you do not add the carry back in).
An IP checksum is a 16 bit checksum. That is, you do 1's complement
summation of each 16 bit word in the packet.
It turns out, however, that if you have 32 bit wide registers you can
optimize this code to sum 32 bit words and then 'fold' the high word
into the low word when you are done. Since the order of the summation
doesn't matter, it also doesn't matter which order the two 16 bit
halves wind up being in. You get the same result when you fold it.
It also turns out that we don't care whether the byte-ordering within
the 16 bit word is little or big endian -- the answer is the same either
way. The low and high byte of the 16 bit checksum will wind up correct
on both a big and little endian machine simply by virtue of the fact
that if the words in the packet are in the wrong byte order, the checksum
will also wind up in the wrong byte order (and thus be laid out in the
RIGHT order). This is a side effect of 1's complement arithmatic --
the symetry between upper and lower bytes in the word does NOT exist
with 2's complement arithmatic.
For example, take a packet laid out like this:
A3 43 23 F7
Little endian: 0x43A3 0xF723
1's complement: 0x43A3 + 0xF723 = 0x13AC6 = 0x3AC7
Result: 0x3AC7, which little-endian is laid out: 3A C7
Big endian: 0xA343 0x23F7
1's complement: 0xA343 0x23F7 = 0xC73A = 0xC73A
Result: 0xC73A, which big-endian is laid out: 3A C7 (identical!)
-Matt
Matthew Dillon
<dillon@backplane.com>
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-hackers" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200005180627.XAA29185>