iofbird / bird2.0.1 / lib / fletcher16.h @ 6b3f1a54
History  View  Annotate  Download (5.21 KB)
1 
/*


2 
* BIRD Library  Fletcher16 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: Fletcher16 checksum

12 
*

13 
* Fletcher16 checksum is a positiondependent checksum algorithm used for

14 
* errordetection e.g. in OSPF LSAs.

15 
*

16 
* To generate Fletcher16 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 Fletcher16 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 Fletcher16 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 Fletcher16 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 Fletcher16 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 Fletcher16 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 
* 32bit 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 Fletcher16 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 hosttonetwork 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 Fletcher16 sum for verification

184 
* @ctx: the context

185 
*

186 
* fletcher16_compute() returns a passing Fletcher16 sum for processed data.

187 
* If the data contains the proper Fletcher16 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
