Annotation of embedaddon/bird/lib/fletcher16.h, revision 1.1.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