1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
|
/*
* BIRD Library -- Fletcher-16 checksum
*
* (c) 2015 Ondrej Zajicek <santiago@crfreenet.org>
* (c) 2015 CZ.NIC z.s.p.o.
*
* Can be freely distributed and used under the terms of the GNU GPL.
*/
/**
* DOC: Fletcher-16 checksum
*
* Fletcher-16 checksum is a position-dependent checksum algorithm used for
* error-detection e.g. in OSPF LSAs.
*
* To generate Fletcher-16 checksum, zero the checksum field in data, initialize
* the context by fletcher16_init(), process the data by fletcher16_update(),
* compute the checksum value by fletcher16_final() and store it to the checksum
* field in data by put_u16() (or other means involving htons() conversion).
*
* To verify Fletcher-16 checksum, initialize the context by fletcher16_init(),
* process the data by fletcher16_update(), compute a passing checksum by
* fletcher16_compute() and check if it is zero.
*/
#ifndef _BIRD_FLETCHER16_H_
#define _BIRD_FLETCHER16_H_
#include "nest/bird.h"
struct fletcher16_context
{
int c0, c1;
};
/**
* fletcher16_init - initialize Fletcher-16 context
* @ctx: the context
*/
static inline void
fletcher16_init(struct fletcher16_context *ctx)
{
ctx->c0 = ctx->c1 = 0;
}
/**
* fletcher16_update - process data to Fletcher-16 context
* @ctx: the context
* @buf: data buffer
* @len: data length
*
* fletcher16_update() reads data from the buffer @buf and updates passing sums
* in the context @ctx. It may be used multiple times for multiple blocks of
* checksummed data.
*/
static inline void
fletcher16_update(struct fletcher16_context *ctx, const u8* buf, int len)
{
/*
* The Fletcher-16 sum is essentially a sequence of
* ctx->c1 += ctx->c0 += *buf++, modulo 255.
*
* In the inner loop, we eliminate modulo operation and we do some loop
* unrolling. MODX is the maximal number of steps that can be done without
* modulo before overflow, see RFC 1008 for details. We use a bit smaller
* value to cover for initial steps due to loop unrolling.
*/
#define MODX 4096
int blen, i;
blen = len % 4;
len -= blen;
for (i = 0; i < blen; i++)
ctx->c1 += ctx->c0 += *buf++;
do {
blen = MIN(len, MODX);
len -= blen;
for (i = 0; i < blen; i += 4)
{
ctx->c1 += ctx->c0 += *buf++;
ctx->c1 += ctx->c0 += *buf++;
ctx->c1 += ctx->c0 += *buf++;
ctx->c1 += ctx->c0 += *buf++;
}
ctx->c0 %= 255;
ctx->c1 %= 255;
} while (len);
}
/**
* fletcher16_update_n32 - process data to Fletcher-16 context, with endianity adjustment
* @ctx: the context
* @buf: data buffer
* @len: data length
*
* fletcher16_update_n32() works like fletcher16_update(), except it applies
* 32-bit host/network endianity swap to the data before they are processed.
* I.e., it assumes that the data is a sequence of u32 that must be converted by
* ntohl() or htonl() before processing. The @buf need not to be aligned, but
* its length (@len) must be multiple of 4. Note that on big endian systems the
* host endianity is the same as the network endianity, therefore there is no
* endianity swap.
*/
static inline void
fletcher16_update_n32(struct fletcher16_context *ctx, const u8* buf, int len)
{
/* See fletcher16_update() for details */
int blen, i;
do {
blen = MIN(len, MODX);
len -= blen;
for (i = 0; i < blen; i += 4)
{
#ifdef CPU_BIG_ENDIAN
ctx->c1 += ctx->c0 += *buf++;
ctx->c1 += ctx->c0 += *buf++;
ctx->c1 += ctx->c0 += *buf++;
ctx->c1 += ctx->c0 += *buf++;
#else
ctx->c1 += ctx->c0 += buf[3];
ctx->c1 += ctx->c0 += buf[2];
ctx->c1 += ctx->c0 += buf[1];
ctx->c1 += ctx->c0 += buf[0];
buf += 4;
#endif
}
ctx->c0 %= 255;
ctx->c1 %= 255;
} while (len);
}
/**
* fletcher16_final - compute final Fletcher-16 checksum value
* @ctx: the context
* @len: total data length
* @pos: offset in data where the checksum will be stored
*
* fletcher16_final() computes the final checksum value and returns it.
* The caller is responsible for storing it in the appropriate position.
* The checksum value depends on @len and @pos, but only their difference
* (i.e. the offset from the end) is significant.
*
* The checksum value is represented as u16, although it is defined as two
* consecutive bytes. We treat them as one u16 in big endian / network order.
* I.e., the returned value is in the form that would be returned by get_u16()
* from the checksum field in the data buffer, therefore the caller should use
* put_u16() or an explicit host-to-network conversion when storing it to the
* checksum field in the data buffer.
*
* Note that the returned checksum value is always nonzero.
*/
static inline u16
fletcher16_final(struct fletcher16_context *ctx, int len, int pos)
{
int x = ((len - pos - 1) * ctx->c0 - ctx->c1) % 255;
if (x <= 0)
x += 255;
int y = 510 - ctx->c0 - x;
if (y > 255)
y -= 255;
return (x << 8) | y;
}
/**
* fletcher16_compute - compute Fletcher-16 sum for verification
* @ctx: the context
*
* fletcher16_compute() returns a passing Fletcher-16 sum for processed data.
* If the data contains the proper Fletcher-16 checksum value, the returned
* value is zero.
*/
static inline u16
fletcher16_compute(struct fletcher16_context *ctx)
{
return (ctx->c0 << 8) | ctx->c1;
}
#endif
|
