]>
Commit | Line | Data |
---|---|---|
77edab64 OZ |
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 |