lib/fletcher16.h

   1 /*
   2  *      BIRD Library -- Fletcher-16 checksum
   3  *
   4  *      (c) 2015 Ondrej Zajicek <santiago@crfreenet.org>
   5  *      (c) 2015 CZ.NIC z.s.p.o.
   6  *
   7  *      Can be freely distributed and used under the terms of the GNU GPL.
   8  */
   9
  10 /**
  11  * DOC: Fletcher-16 checksum
  12  *
  13  * Fletcher-16 checksum is a position-dependent checksum algorithm used for
  14  * error-detection e.g. in OSPF LSAs.
  15  *
  16  * To generate Fletcher-16 checksum, zero the checksum field in data, initialize
  17  * the context by fletcher16_init(), process the data by fletcher16_update(),
  18  * compute the checksum value by fletcher16_final() and store it to the checksum
  19  * field in data by put_u16() (or other means involving htons() conversion).
  20  *
  21  * To verify Fletcher-16 checksum, initialize the context by fletcher16_init(),
  22  * process the data by fletcher16_update(), compute a passing checksum by
  23  * fletcher16_compute() and check if it is zero.
  24  */
  25
  26 #ifndef _BIRD_FLETCHER16_H_
  27 #define _BIRD_FLETCHER16_H_
  28
  29 #include "nest/bird.h"
  30
  31
  32 struct fletcher16_context
  33 {
  34   int c0, c1;
  35 };
  36
  37
  38 /**
  39  * fletcher16_init - initialize Fletcher-16 context
  40  * @ctx: the context
  41  */
  42 static inline void
  43 fletcher16_init(struct fletcher16_context *ctx)
  44 {
  45   ctx->c0 = ctx->c1 = 0;
  46 }
  47
  48 /**
  49  * fletcher16_update - process data to Fletcher-16 context
  50  * @ctx: the context
  51  * @buf: data buffer
  52  * @len: data length
  53  *
  54  * fletcher16_update() reads data from the buffer @buf and updates passing sums
  55  * in the context @ctx. It may be used multiple times for multiple blocks of
  56  * checksummed data.
  57  */
  58 static inline void
  59 fletcher16_update(struct fletcher16_context *ctx, const u8* buf, int len)
  60 {
  61   /*
  62    * The Fletcher-16 sum is essentially a sequence of
  63    * ctx->c1 += ctx->c0 += *buf++, modulo 255.
  64    *
  65    * In the inner loop, we eliminate modulo operation and we do some loop
  66    * unrolling. MODX is the maximal number of steps that can be done without
  67    * modulo before overflow, see RFC 1008 for details. We use a bit smaller
  68    * value to cover for initial steps due to loop unrolling.
  69    */
  70
  71 #define MODX 4096
  72
  73   int blen, i;
  74
  75   blen = len % 4;
  76   len -= blen;
  77
  78   for (i = 0; i < blen; i++)
  79     ctx->c1 += ctx->c0 += *buf++;
  80
  81   do {
  82     blen = MIN(len, MODX);
  83     len -= blen;
  84
  85     for (i = 0; i < blen; i += 4)
  86     {
  87       ctx->c1 += ctx->c0 += *buf++;
  88       ctx->c1 += ctx->c0 += *buf++;
  89       ctx->c1 += ctx->c0 += *buf++;
  90       ctx->c1 += ctx->c0 += *buf++;
  91     }
  92
  93     ctx->c0 %= 255;
  94     ctx->c1 %= 255;
  95
  96   } while (len);
  97 }
  98
  99
 100 /**
 101  * fletcher16_update_n32 - process data to Fletcher-16 context, with endianity adjustment
 102  * @ctx: the context
 103  * @buf: data buffer
 104  * @len: data length
 105  *
 106  * fletcher16_update_n32() works like fletcher16_update(), except it applies
 107  * 32-bit host/network endianity swap to the data before they are processed.
 108  * I.e., it assumes that the data is a sequence of u32 that must be converted by
 109  * ntohl() or htonl() before processing. The @buf need not to be aligned, but
 110  * its length (@len) must be multiple of 4. Note that on big endian systems the
 111  * host endianity is the same as the network endianity, therefore there is no
 112  * endianity swap.
 113  */
 114 static inline void
 115 fletcher16_update_n32(struct fletcher16_context *ctx, const u8* buf, int len)
 116 {
 117   /* See fletcher16_update() for details */
 118
 119   int blen, i;
 120
 121   do {
 122     blen = MIN(len, MODX);
 123     len -= blen;
 124
 125     for (i = 0; i < blen; i += 4)
 126     {
 127 #ifdef CPU_BIG_ENDIAN
 128       ctx->c1 += ctx->c0 += *buf++;
 129       ctx->c1 += ctx->c0 += *buf++;
 130       ctx->c1 += ctx->c0 += *buf++;
 131       ctx->c1 += ctx->c0 += *buf++;
 132 #else
 133       ctx->c1 += ctx->c0 += buf[3];
 134       ctx->c1 += ctx->c0 += buf[2];
 135       ctx->c1 += ctx->c0 += buf[1];
 136       ctx->c1 += ctx->c0 += buf[0];
 137       buf += 4;
 138 #endif
 139     }
 140
 141     ctx->c0 %= 255;
 142     ctx->c1 %= 255;
 143
 144   } while (len);
 145 }
 146
 147 /**
 148  * fletcher16_final - compute final Fletcher-16 checksum value
 149  * @ctx: the context
 150  * @len: total data length
 151  * @pos: offset in data where the checksum will be stored
 152  *
 153  * fletcher16_final() computes the final checksum value and returns it.
 154  * The caller is responsible for storing it in the appropriate position.
 155  * The checksum value depends on @len and @pos, but only their difference
 156  * (i.e. the offset from the end) is significant.
 157  *
 158  * The checksum value is represented as u16, although it is defined as two
 159  * consecutive bytes. We treat them as one u16 in big endian / network order.
 160  * I.e., the returned value is in the form that would be returned by get_u16()
 161  * from the checksum field in the data buffer, therefore the caller should use
 162  * put_u16() or an explicit host-to-network conversion when storing it to the
 163  * checksum field in the data buffer.
 164  *
 165  * Note that the returned checksum value is always nonzero.
 166  */
 167 static inline u16
 168 fletcher16_final(struct fletcher16_context *ctx, int len, int pos)
 169 {
 170   int x = ((len - pos - 1) * ctx->c0 - ctx->c1) % 255;
 171   if (x <= 0)
 172     x += 255;
 173
 174   int y = 510 - ctx->c0 - x;
 175   if (y > 255)
 176     y -= 255;
 177
 178   return (x << 8) | y;
 179 }
 180
 181
 182 /**
 183  * fletcher16_compute - compute Fletcher-16 sum for verification
 184  * @ctx: the context
 185  *
 186  * fletcher16_compute() returns a passing Fletcher-16 sum for processed data.
 187  * If the data contains the proper Fletcher-16 checksum value, the returned
 188  * value is zero.
 189  */
 190 static inline u16
 191 fletcher16_compute(struct fletcher16_context *ctx)
 192 {
 193   return (ctx->c0 << 8) | ctx->c1;
 194 }
 195
 196 #endif