Newsgroups: comp.protocols.tcp-ip
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!mintaka!mintaka.lcs.mit.edu!sra
From: sra@lcs.mit.edu (Rob Austein)
Subject: Re: TCP checksums
In-Reply-To: zweig@parc.xerox.com's message of 30 May 91 20:10:04 GMT
Message-ID: <1991Jun2.204825.14065@mintaka.lcs.mit.edu>
Sender: news@mintaka.lcs.mit.edu
Organization: ITS Lamentation Society
References: <3270025@hpctdlb.HP.COM> <1991May28.221045.27724@Think.COM>
	<zweig.675560793@osric> <zweig.675634204@osric>
Date: Sun, 2 Jun 91 20:48:25 GMT
Lines: 57

One algorithm for computing the ones-complement checksum on a
twos-complement machine works by explictly computing a sum modulo
0xFFFF.  The actual summation can be done in a larger word, and the
properties of the ones-complement sum can be preserved by occasionally
subtracting some large multiple of 0xFFFF.  The final step of this
algorithm returns the ones-complement of the quantity (sum mod
0xFFFF).  Thus, this algorithm will always return 0xFFFF instead of
0x0000.  So, at least in this case, making 0x0000 the excluded value
makes sense.

On certain machines (eg, the PDP-10, where normal fixed-point
arithmetic operates on 36-bit words) this is by far the easiest way to
compute the checksum, because the loop can sum 32-bit quantities
instead of 16-bit quantities without changing the result.

For those interested in the nitty-gritty, here's the UDP checksum code
from the CHIVES domain resolver.  The macro L32INT() obtains a 32-bit
integer from a 36-bit word; this involves some bit-shifting, but you
can think of it as a simple array reference.  ZERO_MOD_0xFFFF is the
largest multiple of 0xFFFF which can be represented as a positive
36-bit twos-complement quantity.

The basic algorithm is from the checksum routine in the ITS monitor.

  int udp_chksum(pkt)
      char *pkt;
  {
      int n, sum, *u;
      struct ip_header *ip_h;
      struct udp_header *udp_h;

      /* Initialize pointers, compute data length */
      ip_h = IP_HEADER(pkt);
      u = (int *) (udp_h = UDP_HEADER(pkt));
      n = ip_h->len - (ip_h->ihl * 4);

      /*
       * Initial sum is pseudo-header:
       *  IP source and destination addresses
       *  IP protocol number
       *  UDP data length (which gets added again part of UDP header!)
       * plus whatever bytes are in the last word of the packet buffer.
       */
      sum = ip_h->sh + ip_h->dh + ip_h->pro + udp_h->ln
	  + (L32INT(u[n/4]) & (~0 << (8 * (4 - (n % 4)))));

      /* Sum everything else, folding when necessary. */
      n /= 4;
      while(--n >= 0)
	  if((sum += L32INT(*u++)) < 0)	/* Carried into the sign bit? */
	      sum -= ZERO_MOD_0xFFFF;	/* Yeah, fix that */

      /* Final folding, return complement. */
      return((sum % 0xFFFF) ^ 0xFFFF);
  }

--Rob Austein