Line data    Source code

       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        3000 : uint16_t in_cksumv(const struct iovec *iov, size_t iov_len)
      21             : {
      22        3000 :         const struct iovec *iov_end;
      23        3000 :         uint32_t sum = 0;
      24             : 
      25        3000 :         union {
      26             :                 uint8_t bytes[2];
      27             :                 uint16_t word;
      28             :         } wordbuf;
      29        3000 :         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        7902 :         for (iov_end = iov + iov_len; iov < iov_end; iov++) {
      38        4902 :                 const uint8_t *ptr, *end;
      39             : 
      40        4902 :                 ptr = (const uint8_t *)iov->iov_base;
      41        4902 :                 end = ptr + iov->iov_len;
      42        4902 :                 if (ptr == end)
      43           0 :                         continue;
      44             : 
      45        4902 :                 if (have_oddbyte) {
      46           0 :                         have_oddbyte = false;
      47           0 :                         wordbuf.bytes[1] = *ptr++;
      48             : 
      49           0 :                         add_carry(sum, wordbuf.word);
      50             :                 }
      51             : 
      52       38343 :                 while (ptr + 8 <= end) {
      53       33441 :                         add_carry(sum, *(const uint32_t *)(ptr + 0));
      54       33441 :                         add_carry(sum, *(const uint32_t *)(ptr + 4));
      55             :                         ptr += 8;
      56             :                 }
      57             : 
      58        8382 :                 while (ptr + 2 <= end) {
      59        3480 :                         add_carry(sum, *(const uint16_t *)ptr);
      60             :                         ptr += 2;
      61             :                 }
      62             : 
      63        4902 :                 if (ptr + 1 <= end) {
      64           0 :                         wordbuf.bytes[0] = *ptr++;
      65           0 :                         have_oddbyte = true;
      66             :                 }
      67             :         }
      68             : 
      69             :         /* mop up an odd byte, if necessary */
      70        3000 :         if (have_oddbyte) {
      71           0 :                 wordbuf.bytes[1] = 0;
      72           0 :                 add_carry(sum, wordbuf.word);
      73             :         }
      74             : 
      75             :         /*
      76             :          * Add back carry outs from top 16 bits to low 16 bits.
      77             :          */
      78             : 
      79        3000 :         sum = (sum >> 16) + (sum & 0xffff); /* add high-16 to low-16 */
      80        3000 :         sum += (sum >> 16);                   /* add carry */
      81        3000 :         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        1459 : uint16_t fletcher_checksum(uint8_t *buffer, const size_t len,
      92             :                            const uint16_t offset)
      93             : {
      94        1459 :         uint8_t *p;
      95        1459 :         int x, y, c0, c1;
      96        1459 :         uint16_t checksum = 0;
      97        1459 :         uint16_t *csum;
      98        1459 :         size_t partial_len, i, left = len;
      99             : 
     100        1459 :         if (offset != FLETCHER_CHECKSUM_VALIDATE)
     101             :         /* Zero the csum in the packet. */
     102             :         {
     103         456 :                 assert(offset
     104             :                        < (len - 1)); /* account for two bytes of checksum */
     105         456 :                 csum = (uint16_t *)(buffer + offset);
     106         456 :                 *(csum) = 0;
     107             :         }
     108             : 
     109        1459 :         p = buffer;
     110        1459 :         c0 = 0;
     111        1459 :         c1 = 0;
     112             : 
     113        2918 :         while (left != 0) {
     114        1459 :                 partial_len = MIN(left, MODX);
     115             : 
     116       59337 :                 for (i = 0; i < partial_len; i++) {
     117       57878 :                         c0 = c0 + *(p++);
     118       57878 :                         c1 += c0;
     119             :                 }
     120             : 
     121        1459 :                 c0 = c0 % 255;
     122        1459 :                 c1 = c1 % 255;
     123             : 
     124        1459 :                 left -= partial_len;
     125             :         }
     126             : 
     127             :         /* The cast is important, to ensure the mod is taken as a signed value.
     128             :          */
     129        1459 :         x = (int)((len - offset - 1) * c0 - c1) % 255;
     130             : 
     131        1459 :         if (x <= 0)
     132        1016 :                 x += 255;
     133        1459 :         y = 510 - c0 - x;
     134        1459 :         if (y > 255)
     135         234 :                 y -= 255;
     136             : 
     137        1459 :         if (offset == FLETCHER_CHECKSUM_VALIDATE) {
     138        1003 :                 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         456 :                 buffer[offset] = x;
     147         456 :                 buffer[offset + 1] = y;
     148             : 
     149             :                 /* Take care of the endian issue */
     150         456 :                 checksum = htons((x << 8) | (y & 0xFF));
     151             :         }
     152             : 
     153        1459 :         return checksum;
     154             : }