lib/checksum.c

   1 /*
   2  *      BIRD Library -- IP One-Complement Checksum
   3  *
   4  *      (c) 1999--2000 Martin Mares <mj@ucw.cz>
   5  *
   6  *      Can be freely distributed and used under the terms of the GNU GPL.
   7  */
   8
   9 /**
  10  * DOC: Miscellaneous functions.
  11  */
  12
  13 #include <stdarg.h>
  14
  15 #include "nest/bird.h"
  16 #include "checksum.h"
  17
  18 static u16                              /* One-complement addition */
  19 add16(u16 sum, u16 x)
  20 {
  21   u16 z = sum + x;
  22   return z + (z < sum);
  23 }
  24
  25 static u32
  26 add32(u32 sum, u32 x)
  27 {
  28   u32 z = sum + x;
  29   return z + (z < sum);
  30 }
  31
  32 static u16
  33 ipsum_calc_block(u16 *x, unsigned len, u16 sum)
  34 {
  35   int rest;
  36   u32 tmp, *xx;
  37
  38   /*
  39    *  A few simple facts about the IP checksum (see RFC 1071 for detailed
  40    *  discussion):
  41    *
  42    *    o  It's associative and commutative.
  43    *    o  It's byte order independent.
  44    *    o  It's word size independent.
  45    *
  46    *  This gives us a neat 32-bits-at-a-time algorithm which respects
  47    *  usual alignment requirements and is reasonably fast.
  48    */
  49
  50   ASSERT(!(len % 2));
  51   if (!len)
  52     return sum;
  53   len >>= 1;
  54   if ((unsigned long) x & 2)            /* Align to 32-bit boundary */
  55     {
  56       sum = add16(sum, *x++);
  57       len--;
  58     }
  59   rest = len & 1;
  60   len >>= 1;
  61   tmp = 0;
  62   xx = (u32 *) x;
  63   while (len)
  64     {
  65       tmp = add32(tmp, *xx++);
  66       len--;
  67     }
  68   sum = add16(sum, add16(tmp & 0xffff, tmp >> 16U));
  69   if (rest)
  70     sum = add16(sum, *(u16 *) xx);
  71   return sum;
  72 }
  73
  74 static u16
  75 ipsum_calc(void *frag, unsigned len, va_list args)
  76 {
  77   u16 sum = 0;
  78
  79   for(;;)
  80     {
  81       sum = ipsum_calc_block(frag, len, sum);
  82       frag = va_arg(args, void *);
  83       if (!frag)
  84         break;
  85       len = va_arg(args, unsigned);
  86     }
  87   return sum;
  88 }
  89
  90 /**
  91  * ipsum_verify - verify an IP checksum
  92  * @frag: first packet fragment
  93  * @len: length in bytes
  94  *
  95  * This function verifies whether a given fragmented packet
  96  * has correct one's complement checksum as used by the IP
  97  * protocol.
  98  *
  99  * It uses all the clever tricks described in RFC 1071 to speed
 100  * up checksum calculation as much as possible.
 101  *
 102  * Result: 1 if the checksum is correct, 0 else.
 103  */
 104 int
 105 ipsum_verify(void *frag, unsigned len, ...)
 106 {
 107   va_list args;
 108   u16 sum;
 109
 110   va_start(args, len);
 111   sum = ipsum_calc(frag, len, args);
 112   va_end(args);
 113   return sum == 0xffff;
 114 }
 115
 116 /**
 117  * ipsum_calculate - compute an IP checksum
 118  * @frag: first packet fragment
 119  * @len: length in bytes
 120  *
 121  * This function calculates a one's complement checksum of a given fragmented
 122  * packet.
 123  *
 124  * It uses all the clever tricks described in RFC 1071 to speed
 125  * up checksum calculation as much as possible.
 126  */
 127 u16
 128 ipsum_calculate(void *frag, unsigned len, ...)
 129 {
 130   va_list args;
 131   u16 sum;
 132
 133   va_start(args, len);
 134   sum = ipsum_calc(frag, len, args);
 135   va_end(args);
 136   return 0xffff - sum;
 137 }