Return to fletcher16.h CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird / lib

bird 1.6.3

    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