## iof-bird-daemon / lib / fletcher16.h @ c8cafc8e

History | View | Annotate | Download (5.21 KB)

1 | 77edab64 | Ondrej Zajicek | ```
/*
``` |
---|---|---|---|

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` |