lib/checksum.c

   1 /*
   2  * Checksum routine for Internet Protocol family headers (C Version).
   3  *
   4  * Refer to "Computing the Internet Checksum" by R. Braden, D. Borman and
   5  * C. Partridge, Computer Communication Review, Vol. 19, No. 2, April 1989,
   6  * pp. 86-101, for additional details on computing this checksum.
   7  */
   8
   9 #include <zebra.h>
  10 #include "checksum.h"
  11
  12 #define add_carry(dst, add)                                                    \
  13         do {                                                                   \
  14                 typeof(dst) _add = (add);                                      \
  15                 dst += _add;                                                   \
  16                 if (dst < _add)                                                \
  17                         dst++;                                                 \
  18         } while (0)
  19
  20 uint16_t in_cksumv(const struct iovec *iov, size_t iov_len)
  21 {
  22         const struct iovec *iov_end;
  23         uint32_t sum = 0;
  24
  25         union {
  26                 uint8_t bytes[2];
  27                 uint16_t word;
  28         } wordbuf;
  29         bool have_oddbyte = false;
  30
  31         /*
  32          * Our algorithm is simple, using a 32-bit accumulator (sum),
  33          * we add sequential 16-bit words to it, and at the end, fold back
  34          * all the carry bits from the top 16 bits into the lower 16 bits.
  35          */
  36
  37         for (iov_end = iov + iov_len; iov < iov_end; iov++) {
  38                 const uint8_t *ptr, *end;
  39
  40                 ptr = (const uint8_t *)iov->iov_base;
  41                 end = ptr + iov->iov_len;
  42                 if (ptr == end)
  43                         continue;
  44
  45                 if (have_oddbyte) {
  46                         have_oddbyte = false;
  47                         wordbuf.bytes[1] = *ptr++;
  48
  49                         add_carry(sum, wordbuf.word);
  50                 }
  51
  52                 while (ptr + 8 <= end) {
  53                         add_carry(sum, *(const uint32_t *)(ptr + 0));
  54                         add_carry(sum, *(const uint32_t *)(ptr + 4));
  55                         ptr += 8;
  56                 }
  57
  58                 while (ptr + 2 <= end) {
  59                         add_carry(sum, *(const uint16_t *)ptr);
  60                         ptr += 2;
  61                 }
  62
  63                 if (ptr + 1 <= end) {
  64                         wordbuf.bytes[0] = *ptr++;
  65                         have_oddbyte = true;
  66                 }
  67         }
  68
  69         /* mop up an odd byte, if necessary */
  70         if (have_oddbyte) {
  71                 wordbuf.bytes[1] = 0;
  72                 add_carry(sum, wordbuf.word);
  73         }
  74
  75         /*
  76          * Add back carry outs from top 16 bits to low 16 bits.
  77          */
  78
  79         sum = (sum >> 16) + (sum & 0xffff); /* add high-16 to low-16 */
  80         sum += (sum >> 16);                 /* add carry */
  81         return ~sum;
  82 }
  83
  84 /* Fletcher Checksum -- Refer to RFC1008. */
  85 #define MODX                 4102U   /* 5802 should be fine */
  86
  87 /* To be consistent, offset is 0-based index, rather than the 1-based
  88    index required in the specification ISO 8473, Annex C.1 */
  89 /* calling with offset == FLETCHER_CHECKSUM_VALIDATE will validate the checksum
  90    without modifying the buffer; a valid checksum returns 0 */
  91 uint16_t fletcher_checksum(uint8_t *buffer, const size_t len,
  92                            const uint16_t offset)
  93 {
  94         uint8_t *p;
  95         int x, y, c0, c1;
  96         uint16_t checksum = 0;
  97         uint16_t *csum;
  98         size_t partial_len, i, left = len;
  99
 100         if (offset != FLETCHER_CHECKSUM_VALIDATE)
 101         /* Zero the csum in the packet. */
 102         {
 103                 assert(offset
 104                        < (len - 1)); /* account for two bytes of checksum */
 105                 csum = (uint16_t *)(buffer + offset);
 106                 *(csum) = 0;
 107         }
 108
 109         p = buffer;
 110         c0 = 0;
 111         c1 = 0;
 112
 113         while (left != 0) {
 114                 partial_len = MIN(left, MODX);
 115
 116                 for (i = 0; i < partial_len; i++) {
 117                         c0 = c0 + *(p++);
 118                         c1 += c0;
 119                 }
 120
 121                 c0 = c0 % 255;
 122                 c1 = c1 % 255;
 123
 124                 left -= partial_len;
 125         }
 126
 127         /* The cast is important, to ensure the mod is taken as a signed value.
 128          */
 129         x = (int)((len - offset - 1) * c0 - c1) % 255;
 130
 131         if (x <= 0)
 132                 x += 255;
 133         y = 510 - c0 - x;
 134         if (y > 255)
 135                 y -= 255;
 136
 137         if (offset == FLETCHER_CHECKSUM_VALIDATE) {
 138                 checksum = (c1 << 8) + c0;
 139         } else {
 140                 /*
 141                  * Now we write this to the packet.
 142                  * We could skip this step too, since the checksum returned
 143                  * would
 144                  * be stored into the checksum field by the caller.
 145                  */
 146                 buffer[offset] = x;
 147                 buffer[offset + 1] = y;
 148
 149                 /* Take care of the endian issue */
 150                 checksum = htons((x << 8) | (y & 0xFF));
 151         }
 152
 153         return checksum;
 154 }