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