Annotation of embedaddon/bird/lib/fletcher16.h, revision 1.1

1.1     ! misho       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

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>