Statistics
| Branch: | Revision:

iof-bird / bird-2.0.1 / lib / fletcher16.h @ 6b3f1a54

History | View | Annotate | Download (5.21 KB)

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