]>
Commit | Line | Data |
---|---|---|
46f4a4d2 PJ |
1 | /* |
2 | * Copyright (C) 2008 Sun Microsystems, Inc. | |
3 | * | |
4 | * This file is part of Quagga. | |
5 | * | |
6 | * Quagga is free software; you can redistribute it and/or modify it | |
7 | * under the terms of the GNU General Public License as published by the | |
8 | * Free Software Foundation; either version 2, or (at your option) any | |
9 | * later version. | |
10 | * | |
11 | * Quagga is distributed in the hope that it will be useful, but | |
12 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | * General Public License for more details. | |
15 | * | |
16 | * You should have received a copy of the GNU General Public License | |
17 | * along with Quagga; see the file COPYING. If not, write to the Free | |
18 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA | |
19 | * 02111-1307, USA. | |
20 | */ | |
21 | ||
5d4b8cf2 PJ |
22 | #include <zebra.h> |
23 | #include <stdlib.h> | |
24 | #include <time.h> | |
25 | ||
26 | #include "checksum.h" | |
27 | ||
28 | struct thread_master *master; | |
29 | ||
30 | struct acc_vals { | |
31 | int c0; | |
32 | int c1; | |
33 | }; | |
34 | ||
35 | struct csum_vals { | |
36 | struct acc_vals a; | |
37 | int x; | |
38 | int y; | |
39 | }; | |
40 | ||
41 | static struct csum_vals ospfd_vals, isisd_vals; | |
42 | ||
43 | typedef size_t testsz_t; | |
44 | typedef uint16_t testoff_t; | |
45 | ||
46 | /* Fletcher Checksum -- Refer to RFC1008. */ | |
47 | #define MODX 4102 | |
6b0655a2 | 48 | |
5d4b8cf2 PJ |
49 | /* The final reduction phase. |
50 | * This one should be the original ospfd version | |
51 | */ | |
52 | static u_int16_t | |
53 | reduce_ospfd (struct csum_vals *vals, testsz_t len, testoff_t off) | |
54 | { | |
55 | #define x vals->x | |
56 | #define y vals->y | |
57 | #define c0 vals->a.c0 | |
58 | #define c1 vals->a.c1 | |
59 | ||
60 | x = ((len - off - 1) * c0 - c1) % 255; | |
61 | ||
62 | if (x <= 0) | |
63 | x += 255; | |
64 | y = 510 - c0 - x; | |
65 | if (y > 255) | |
66 | y -= 255; | |
67 | ||
68 | /* take care endian issue. */ | |
69 | return htons ((x << 8) + y); | |
70 | #undef x | |
71 | #undef y | |
72 | #undef c0 | |
73 | #undef c1 | |
74 | } | |
75 | ||
76 | /* slightly different concatenation */ | |
77 | static u_int16_t | |
78 | reduce_ospfd1 (struct csum_vals *vals, testsz_t len, testoff_t off) | |
79 | { | |
80 | #define x vals->x | |
81 | #define y vals->y | |
82 | #define c0 vals->a.c0 | |
83 | #define c1 vals->a.c1 | |
84 | ||
85 | x = ((len - off - 1) * c0 - c1) % 255; | |
86 | if (x <= 0) | |
87 | x += 255; | |
88 | y = 510 - c0 - x; | |
89 | if (y > 255) | |
90 | y -= 255; | |
91 | ||
92 | /* take care endian issue. */ | |
93 | return htons ((x << 8) | (y & 0xff)); | |
94 | #undef x | |
95 | #undef y | |
96 | #undef c0 | |
97 | #undef c1 | |
98 | } | |
99 | ||
100 | /* original isisd version */ | |
101 | static u_int16_t | |
102 | reduce_isisd (struct csum_vals *vals, testsz_t len, testoff_t off) | |
103 | { | |
104 | #define x vals->x | |
105 | #define y vals->y | |
106 | #define c0 vals->a.c0 | |
107 | #define c1 vals->a.c1 | |
108 | u_int32_t mul; | |
109 | ||
110 | mul = (len - off)*(c0); | |
111 | x = mul - c0 - c1; | |
112 | y = c1 - mul - 1; | |
113 | ||
114 | if (y > 0) | |
115 | y++; | |
116 | if (x < 0) | |
117 | x--; | |
118 | ||
119 | x %= 255; | |
120 | y %= 255; | |
121 | ||
122 | if (x == 0) | |
123 | x = 255; | |
124 | if (y == 0) | |
125 | y = 1; | |
126 | ||
127 | return htons ((x << 8) | (y & 0xff)); | |
128 | ||
129 | #undef x | |
130 | #undef y | |
131 | #undef c0 | |
132 | #undef c1 | |
133 | } | |
134 | ||
135 | /* Is the -1 in y wrong perhaps? */ | |
136 | static u_int16_t | |
137 | reduce_isisd_yfix (struct csum_vals *vals, testsz_t len, testoff_t off) | |
138 | { | |
139 | #define x vals->x | |
140 | #define y vals->y | |
141 | #define c0 vals->a.c0 | |
142 | #define c1 vals->a.c1 | |
143 | u_int32_t mul; | |
144 | ||
145 | mul = (len - off)*(c0); | |
146 | x = mul - c0 - c1; | |
147 | y = c1 - mul; | |
148 | ||
149 | if (y > 0) | |
150 | y++; | |
151 | if (x < 0) | |
152 | x--; | |
153 | ||
154 | x %= 255; | |
155 | y %= 255; | |
156 | ||
157 | if (x == 0) | |
158 | x = 255; | |
159 | if (y == 0) | |
160 | y = 1; | |
161 | ||
162 | return htons ((x << 8) | (y & 0xff)); | |
163 | ||
164 | #undef x | |
165 | #undef y | |
166 | #undef c0 | |
167 | #undef c1 | |
168 | } | |
169 | ||
170 | /* Move the mods yp */ | |
171 | static u_int16_t | |
172 | reduce_isisd_mod (struct csum_vals *vals, testsz_t len, testoff_t off) | |
173 | { | |
174 | #define x vals->x | |
175 | #define y vals->y | |
176 | #define c0 vals->a.c0 | |
177 | #define c1 vals->a.c1 | |
178 | u_int32_t mul; | |
179 | ||
180 | mul = (len - off)*(c0); | |
181 | x = mul - c1 - c0; | |
182 | y = c1 - mul - 1; | |
183 | ||
184 | x %= 255; | |
185 | y %= 255; | |
186 | ||
187 | if (y > 0) | |
188 | y++; | |
189 | if (x < 0) | |
190 | x--; | |
191 | ||
192 | if (x == 0) | |
193 | x = 255; | |
194 | if (y == 0) | |
195 | y = 1; | |
196 | ||
197 | return htons ((x << 8) | (y & 0xff)); | |
198 | ||
199 | #undef x | |
200 | #undef y | |
201 | #undef c0 | |
202 | #undef c1 | |
203 | } | |
204 | ||
205 | /* Move the mods up + fix y */ | |
206 | static u_int16_t | |
207 | reduce_isisd_mody (struct csum_vals *vals, testsz_t len, testoff_t off) | |
208 | { | |
209 | #define x vals->x | |
210 | #define y vals->y | |
211 | #define c0 vals->a.c0 | |
212 | #define c1 vals->a.c1 | |
213 | u_int32_t mul; | |
214 | ||
215 | mul = (len - off)*(c0); | |
216 | x = mul - c0 - c1; | |
217 | y = c1 - mul; | |
218 | ||
219 | x %= 255; | |
220 | y %= 255; | |
221 | ||
222 | if (y > 0) | |
223 | y++; | |
224 | if (x < 0) | |
225 | x--; | |
226 | ||
227 | if (x == 0) | |
228 | x = 255; | |
229 | if (y == 0) | |
230 | y = 1; | |
231 | ||
232 | return htons ((x << 8) | (y & 0xff)); | |
233 | ||
234 | #undef x | |
235 | #undef y | |
236 | #undef c0 | |
237 | #undef c1 | |
238 | } | |
239 | ||
240 | struct reductions_t { | |
241 | const char *name; | |
242 | u_int16_t (*f) (struct csum_vals *, testsz_t, testoff_t); | |
243 | } reducts[] = { | |
244 | { .name = "ospfd", .f = reduce_ospfd }, | |
245 | { .name = "ospfd-1", .f = reduce_ospfd1 }, | |
246 | { .name = "isisd", .f = reduce_isisd }, | |
247 | { .name = "isisd-yfix", .f = reduce_isisd_yfix }, | |
248 | { .name = "isisd-mod", .f = reduce_isisd_mod }, | |
249 | { .name = "isisd-mody", .f = reduce_isisd_mody }, | |
250 | { NULL, NULL }, | |
251 | }; | |
6b0655a2 | 252 | |
5d4b8cf2 PJ |
253 | /* The original ospfd checksum */ |
254 | static u_int16_t | |
255 | ospfd_checksum (u_char *buffer, testsz_t len, testoff_t off) | |
256 | { | |
257 | u_char *sp, *ep, *p, *q; | |
258 | int c0 = 0, c1 = 0; | |
259 | int x, y; | |
260 | u_int16_t checksum, *csum; | |
261 | ||
262 | csum = (u_int16_t *) (buffer + off); | |
263 | *(csum) = 0; | |
264 | ||
265 | sp = buffer; | |
266 | ||
267 | for (ep = sp + len; sp < ep; sp = q) | |
268 | { | |
269 | q = sp + MODX; | |
270 | if (q > ep) | |
271 | q = ep; | |
272 | for (p = sp; p < q; p++) | |
273 | { | |
274 | c0 += *p; | |
275 | c1 += c0; | |
276 | } | |
277 | c0 %= 255; | |
278 | c1 %= 255; | |
279 | } | |
280 | ||
281 | ospfd_vals.a.c0 = c0; | |
282 | ospfd_vals.a.c1 = c1; | |
283 | ||
284 | //printf ("%s: len %u, off %u, c0 %d, c1 %d\n", | |
285 | // __func__, len, off, c0, c1); | |
286 | ||
287 | x = ((int)(len - off - 1) * (int)c0 - (int)c1) % 255; | |
288 | ||
289 | if (x <= 0) | |
290 | x += 255; | |
291 | y = 510 - c0 - x; | |
292 | if (y > 255) | |
293 | y -= 255; | |
294 | ||
295 | ospfd_vals.x = x; | |
296 | ospfd_vals.y = y; | |
297 | ||
298 | buffer[off] = x; | |
299 | buffer[off + 1] = y; | |
300 | ||
301 | /* take care endian issue. */ | |
302 | checksum = htons ((x << 8) | (y & 0xff)); | |
303 | ||
304 | return (checksum); | |
305 | } | |
306 | ||
307 | /* the original, broken isisd checksum */ | |
308 | static u_int16_t | |
309 | iso_csum_create (u_char * buffer, testsz_t len, testoff_t off) | |
310 | { | |
311 | ||
312 | u_int8_t *p; | |
313 | int x; | |
314 | int y; | |
315 | u_int32_t mul; | |
316 | u_int32_t c0; | |
317 | u_int32_t c1; | |
318 | u_int16_t checksum, *csum; | |
319 | int i, init_len, partial_len; | |
320 | ||
321 | checksum = 0; | |
322 | ||
323 | csum = (u_int16_t *) (buffer + off); | |
324 | *(csum) = checksum; | |
325 | ||
326 | p = buffer; | |
327 | c0 = 0; | |
328 | c1 = 0; | |
329 | init_len = len; | |
330 | ||
331 | while (len != 0) | |
332 | { | |
333 | partial_len = MIN(len, MODX); | |
334 | ||
335 | for (i = 0; i < partial_len; i++) | |
336 | { | |
337 | c0 = c0 + *(p++); | |
338 | c1 += c0; | |
339 | } | |
340 | ||
341 | c0 = c0 % 255; | |
342 | c1 = c1 % 255; | |
343 | ||
344 | len -= partial_len; | |
345 | } | |
346 | ||
347 | isisd_vals.a.c0 = c0; | |
348 | isisd_vals.a.c1 = c1; | |
349 | ||
350 | mul = (init_len - off) * c0; | |
351 | ||
352 | x = mul - c1 - c0; | |
353 | y = c1 - mul - 1; | |
354 | ||
355 | if (y > 0) | |
356 | y++; | |
357 | if (x < 0) | |
358 | x--; | |
359 | ||
360 | x %= 255; | |
361 | y %= 255; | |
362 | ||
363 | if (x == 0) | |
364 | x = 255; | |
365 | if (y == 0) | |
366 | y = 1; | |
367 | ||
368 | isisd_vals.x = x; | |
369 | isisd_vals.y = y; | |
370 | ||
371 | checksum = htons((x << 8) | (y & 0xFF)); | |
372 | ||
373 | *(csum) = checksum; | |
374 | ||
375 | /* return the checksum for user usage */ | |
376 | return checksum; | |
377 | } | |
378 | ||
379 | static int | |
380 | verify (u_char * buffer, testsz_t len) | |
381 | { | |
382 | u_int8_t *p; | |
383 | u_int32_t c0; | |
384 | u_int32_t c1; | |
5d4b8cf2 PJ |
385 | int i, partial_len; |
386 | ||
387 | p = buffer; | |
5d4b8cf2 PJ |
388 | |
389 | c0 = 0; | |
390 | c1 = 0; | |
391 | ||
392 | while (len) | |
393 | { | |
394 | partial_len = MIN(len, 5803); | |
395 | ||
396 | for (i = 0; i < partial_len; i++) | |
397 | { | |
398 | c0 = c0 + *(p++); | |
399 | c1 += c0; | |
400 | } | |
401 | c0 = c0 % 255; | |
402 | c1 = c1 % 255; | |
403 | ||
404 | len -= partial_len; | |
405 | } | |
406 | ||
407 | if (c0 == 0 && c1 == 0) | |
408 | return 0; | |
409 | ||
410 | return 1; | |
411 | } | |
412 | ||
1dba254e | 413 | static int /* return checksum in low-order 16 bits */ |
439c52f1 JT |
414 | in_cksum_optimized(void *parg, int nbytes) |
415 | { | |
416 | u_short *ptr = parg; | |
417 | register long sum; /* assumes long == 32 bits */ | |
418 | register u_short answer; /* assumes u_short == 16 bits */ | |
419 | register int count; | |
420 | /* | |
421 | * Our algorithm is simple, using a 32-bit accumulator (sum), | |
422 | * we add sequential 16-bit words to it, and at the end, fold back | |
423 | * all the carry bits from the top 16 bits into the lower 16 bits. | |
424 | */ | |
425 | ||
426 | sum = 0; | |
427 | count = nbytes >> 1; /* div by 2 */ | |
428 | for(ptr--; count; --count) | |
429 | sum += *++ptr; | |
430 | ||
431 | if (nbytes & 1) /* Odd */ | |
432 | sum += *(u_char *)(++ptr); /* one byte only */ | |
433 | ||
434 | /* | |
435 | * Add back carry outs from top 16 bits to low 16 bits. | |
436 | */ | |
437 | ||
438 | sum = (sum >> 16) + (sum & 0xffff); /* add high-16 to low-16 */ | |
439 | sum += (sum >> 16); /* add carry */ | |
440 | answer = ~sum; /* ones-complement, then truncate to 16 bits */ | |
441 | return(answer); | |
442 | } | |
443 | ||
444 | ||
1dba254e | 445 | static int /* return checksum in low-order 16 bits */ |
439c52f1 JT |
446 | in_cksum_rfc(void *parg, int count) |
447 | /* from RFC 1071 */ | |
448 | { | |
449 | u_short *addr = parg; | |
450 | /* Compute Internet Checksum for "count" bytes | |
451 | * beginning at location "addr". | |
452 | */ | |
453 | register long sum = 0; | |
454 | ||
455 | while (count > 1) { | |
456 | /* This is the inner loop */ | |
457 | sum += *addr++; | |
458 | count -= 2; | |
459 | } | |
460 | /* Add left-over byte, if any */ | |
461 | if (count > 0) { | |
462 | sum += *(u_char *)addr; | |
463 | } | |
464 | ||
465 | /* Fold 32-bit sum to 16 bits */ | |
466 | while (sum>>16) | |
467 | sum = (sum & 0xffff) + (sum >> 16); | |
468 | return ~sum; | |
469 | } | |
470 | ||
471 | ||
5d4b8cf2 PJ |
472 | int |
473 | main(int argc, char **argv) | |
474 | { | |
475 | /* 60017 65629 702179 */ | |
476 | #define MAXDATALEN 60017 | |
477 | #define BUFSIZE MAXDATALEN + sizeof(u_int16_t) | |
478 | u_char buffer[BUFSIZE]; | |
479 | int exercise = 0; | |
480 | #define EXERCISESTEP 257 | |
481 | ||
482 | srandom (time (NULL)); | |
483 | ||
484 | while (1) { | |
439c52f1 JT |
485 | u_int16_t ospfd, isisd, lib, in_csum, in_csum_res, in_csum_rfc; |
486 | int i,j; | |
487 | ||
5d4b8cf2 PJ |
488 | exercise += EXERCISESTEP; |
489 | exercise %= MAXDATALEN; | |
490 | ||
439c52f1 | 491 | for (i = 0; i < exercise; i += sizeof (long int)) { |
5d4b8cf2 PJ |
492 | long int rand = random (); |
493 | ||
439c52f1 | 494 | for (j = sizeof (long int); j > 0; j--) |
5d4b8cf2 PJ |
495 | buffer[i + (sizeof (long int) - j)] = (rand >> (j * 8)) & 0xff; |
496 | } | |
497 | ||
439c52f1 JT |
498 | in_csum = in_cksum(buffer, exercise); |
499 | in_csum_res = in_cksum_optimized(buffer, exercise); | |
500 | in_csum_rfc = in_cksum_rfc(buffer, exercise); | |
501 | if (in_csum_res != in_csum || in_csum != in_csum_rfc) | |
502 | printf ("verify: in_chksum failed in_csum:%x, in_csum_res:%x," | |
503 | "in_csum_rfc %x, len:%d\n", | |
504 | in_csum, in_csum_res, in_csum_rfc, exercise); | |
505 | ||
5d4b8cf2 PJ |
506 | ospfd = ospfd_checksum (buffer, exercise + sizeof(u_int16_t), exercise); |
507 | if (verify (buffer, exercise + sizeof(u_int16_t))) | |
508 | printf ("verify: ospfd failed\n"); | |
509 | isisd = iso_csum_create (buffer, exercise + sizeof(u_int16_t), exercise); | |
510 | if (verify (buffer, exercise + sizeof(u_int16_t))) | |
511 | printf ("verify: isisd failed\n"); | |
512 | lib = fletcher_checksum (buffer, exercise + sizeof(u_int16_t), exercise); | |
513 | if (verify (buffer, exercise + sizeof(u_int16_t))) | |
514 | printf ("verify: lib failed\n"); | |
515 | ||
516 | if (ospfd != lib) { | |
517 | printf ("Mismatch in values at size %u\n" | |
518 | "ospfd: 0x%04x\tc0: %d\tc1: %d\tx: %d\ty: %d\n" | |
519 | "isisd: 0x%04x\tc0: %d\tc1: %d\tx: %d\ty: %d\n" | |
520 | "lib: 0x%04x\n", | |
521 | exercise, | |
522 | ospfd, ospfd_vals.a.c0, ospfd_vals.a.c1, ospfd_vals.x, ospfd_vals.y, | |
523 | isisd, isisd_vals.a.c0, isisd_vals.a.c1, isisd_vals.x, isisd_vals.y, | |
524 | lib | |
525 | ); | |
526 | ||
527 | /* Investigate reduction phase discrepencies */ | |
528 | if (ospfd_vals.a.c0 == isisd_vals.a.c0 | |
529 | && ospfd_vals.a.c1 == isisd_vals.a.c1) { | |
530 | printf ("\n"); | |
439c52f1 | 531 | for (i = 0; reducts[i].name != NULL; i++) { |
5d4b8cf2 PJ |
532 | ospfd = reducts[i].f (&ospfd_vals, |
533 | exercise + sizeof (u_int16_t), | |
534 | exercise); | |
535 | printf ("%20s: x: %02x, y %02x, checksum 0x%04x\n", | |
536 | reducts[i].name, ospfd_vals.x & 0xff, ospfd_vals.y & 0xff, ospfd); | |
537 | } | |
538 | } | |
539 | ||
540 | printf ("\n u_char testdata [] = {\n "); | |
439c52f1 | 541 | for (i = 0; i < exercise; i++) { |
5d4b8cf2 PJ |
542 | printf ("0x%02x,%s", |
543 | buffer[i], | |
544 | (i + 1) % 8 ? " " : "\n "); | |
545 | } | |
546 | printf ("\n}\n"); | |
547 | exit (1); | |
548 | } | |
549 | } | |
550 | } |