[ntp:questions] Re: Tinker and tos configuration commands....

Terje Mathisen terje.mathisen at hda.hydro.com
Thu Feb 10 08:47:08 UTC 2005

David L. Mills wrote:
> Terje,
> I beg to differ. The IP checksum is vulnerable to byte swap and reorder. 
> The most common error in the old days was with the venerable IMP11-A 
> interface for the PDP11. It was a 16-bit interface with a byte-swap 
> switch. It often was set to the wrong position, with result the bytes 
> were swapped in error, but not caught by the checksum. Sure, it was fast 

Shall we just say that there are many error modes such a simple checksum 
will fail to catch, but that it has still managed to be quite helpful 
over the years?

> to compute and my 16-bit PDP11 programs did that. The real challenge, 
> however, was doing a 16-bit checksum calculation on a 36-bit machine 
> like TOPS20 or Multics. Many a grad studen worked out a deliciously 
> intricate way to to a 16-bit checksum of a span of 36-bit words.

The key here isn't the register bitsize, but the network interface: 
Since IP packets by definition consists of an even number of 8-bit 
bytes, these bytes has to be stored in memory in some manner, right?

Either you use bitlevel packing, and make room for 4.5 bytes in each 
word/register, which means that you get 18 bytes or 9 byte-pairs in 4 
memory words, or you store a limited number (i.e. 4) of bytes in each word.

In the second case you either pack 32 bits into the lower (or higher) 32 
bits of a 36 bit word, or you extend each byte to 9 bits. The second 
version is probably the most 'fun' to handle checksum calculations for!

If I were faced with that particular problem, and needed to make it 
efficient, I'd employ a couple of tricks:

The IP checksum can be calculated separately for the high and the low 
bytes of each pair, then combined afterwards.

By first splitting each word into two, one with the high bytes and one 
with the low, and then shifting the high half down, I can keep two 
accumulators and simply add all words together (taking care to handle 
the case where the last word only contains a single pair!):

Since there are 10 free bits above each 8-bit accumulator position, I 
can add together at least 1024 such words (i.e. 4K of data) before 
overflwo can become a problem. For IP packets which are even larger than 
this, I'd simply call this routine once for every 4 K instance.

/* 8-bit bytes stored in 9-bit fields: */
#define MASK 0o377000377
#define BIGENDIAN 0

unsigned ip_copy_and_checksum(word *dest, word *buffer, unsigned pairs)
   word w, hi, lo, hisum = 0, losum = 0;
   unsigned p;

   for (p = 1; p < pairs; p += 2) {  /* Two pairs per word */
     w = *buffer++;
     *dest++ = w;
     lo = w & MASK;
     hi = (w >> 9) & MASK;
     losum += lo;
     hisum += hi;
   if (p == pairs) { /* Odd number of pairs? */
     w = *buffer;
     *dest = w;
/* I don't know if this machine is little or big endian, add a
    shift right by 18 in case of big endian storage within a word! */
     losum += (w >> (BIGENDIAN? 18:0)) & 255;
     hisum += (w >> (9+(BIGENDIAN? 18:0)) & 255;
   /* Merge high & low half of each accumulator: */
   losum = (losum & 0o777777) + (losum >> 18);
   hisum = (hisum & 0x777777) + (hisum >> 18);

   /* Wrap all carries around: */
   hisum += losum >> 8;
   losum &= 255;
   losum += hisum >> 8;
   hisum = (hisum & 255) + (losum >> 8);
   losum &= 255;

   return (hisum << 9) + losum;

PS. If you don't like this approach, then there is another alternative 
which doesn't require splitting each input word into high and low parts:

Use a single accumulator, but set the top bit in each 9-bit subfield 
before adding in the next word, then extract the top bit of the result 
and store as a separate global carry count:

   for (p = 1; p < pairs; p += 2) {  /* Two pairs per word */
     w = *buffer++;
     *dest++ = w;
     acc = (acc | 0o400400400) + w; /* Propagate interbyte carries! */
     carry += acc >> 35;    /* Add top bit to global carry */
     acc &= 0o377777777777; /* and clear it away */
- <Terje.Mathisen at hda.hydro.com>
"almost all programming can be viewed as an exercise in caching"

More information about the questions mailing list