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>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to fletcher16.h CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird / lib