2 * Copyright (C) 2008 Sun Microsystems, Inc.
4 * This file is part of Quagga.
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
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.
16 * You should have received a copy of the GNU General Public License along
17 * with this program; see the file COPYING; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
29 struct thread_master
*master
;
42 static struct csum_vals ospfd_vals
, isisd_vals
;
44 typedef size_t testsz_t
;
45 typedef uint16_t testoff_t
;
47 /* Fletcher Checksum -- Refer to RFC1008. */
50 /* The final reduction phase.
51 * This one should be the original ospfd version
53 static uint16_t reduce_ospfd(struct csum_vals
*vals
, testsz_t len
,
61 x
= ((len
- off
- 1) * c0
- c1
) % 255;
69 /* take care endian issue. */
70 return htons((x
<< 8) + y
);
77 /* slightly different concatenation */
78 static uint16_t reduce_ospfd1(struct csum_vals
*vals
, testsz_t len
,
86 x
= ((len
- off
- 1) * c0
- c1
) % 255;
93 /* take care endian issue. */
94 return htons((x
<< 8) | (y
& 0xff));
101 /* original isisd version */
102 static uint16_t reduce_isisd(struct csum_vals
*vals
, testsz_t len
,
107 #define c0 vals->a.c0
108 #define c1 vals->a.c1
111 mul
= (len
- off
) * (c0
);
128 return htons((x
<< 8) | (y
& 0xff));
136 /* Is the -1 in y wrong perhaps? */
137 static uint16_t reduce_isisd_yfix(struct csum_vals
*vals
, testsz_t len
,
142 #define c0 vals->a.c0
143 #define c1 vals->a.c1
146 mul
= (len
- off
) * (c0
);
163 return htons((x
<< 8) | (y
& 0xff));
171 /* Move the mods yp */
172 static uint16_t reduce_isisd_mod(struct csum_vals
*vals
, testsz_t len
,
177 #define c0 vals->a.c0
178 #define c1 vals->a.c1
181 mul
= (len
- off
) * (c0
);
198 return htons((x
<< 8) | (y
& 0xff));
206 /* Move the mods up + fix y */
207 static uint16_t reduce_isisd_mody(struct csum_vals
*vals
, testsz_t len
,
212 #define c0 vals->a.c0
213 #define c1 vals->a.c1
216 mul
= (len
- off
) * (c0
);
233 return htons((x
<< 8) | (y
& 0xff));
241 struct reductions_t
{
243 uint16_t (*f
)(struct csum_vals
*, testsz_t
, testoff_t
);
245 {.name
= "ospfd", .f
= reduce_ospfd
},
246 {.name
= "ospfd-1", .f
= reduce_ospfd1
},
247 {.name
= "isisd", .f
= reduce_isisd
},
248 {.name
= "isisd-yfix", .f
= reduce_isisd_yfix
},
249 {.name
= "isisd-mod", .f
= reduce_isisd_mod
},
250 {.name
= "isisd-mody", .f
= reduce_isisd_mody
},
254 /* The original ospfd checksum */
255 static uint16_t ospfd_checksum(uint8_t *buffer
, testsz_t len
, testoff_t off
)
257 uint8_t *sp
, *ep
, *p
, *q
;
260 uint16_t checksum
, *csum
;
262 csum
= (uint16_t *)(buffer
+ off
);
267 for (ep
= sp
+ len
; sp
< ep
; sp
= q
) {
271 for (p
= sp
; p
< q
; p
++) {
279 ospfd_vals
.a
.c0
= c0
;
280 ospfd_vals
.a
.c1
= c1
;
282 // printf ("%s: len %u, off %u, c0 %d, c1 %d\n",
283 // __func__, len, off, c0, c1);
285 x
= ((int)(len
- off
- 1) * (int)c0
- (int)c1
) % 255;
299 /* take care endian issue. */
300 checksum
= htons((x
<< 8) | (y
& 0xff));
305 /* the original, broken isisd checksum */
306 static uint16_t iso_csum_create(uint8_t *buffer
, testsz_t len
, testoff_t off
)
315 uint16_t checksum
, *csum
;
316 int i
, init_len
, partial_len
;
320 csum
= (uint16_t *)(buffer
+ off
);
329 partial_len
= MIN(len
, MODX
);
331 for (i
= 0; i
< partial_len
; i
++) {
342 isisd_vals
.a
.c0
= c0
;
343 isisd_vals
.a
.c1
= c1
;
345 mul
= (init_len
- off
) * c0
;
366 checksum
= htons((x
<< 8) | (y
& 0xFF));
370 /* return the checksum for user usage */
374 static int verify(uint8_t *buffer
, testsz_t len
)
387 partial_len
= MIN(len
, 5803U);
389 for (i
= 0; i
< partial_len
; i
++) {
399 if (c0
== 0 && c1
== 0)
405 static int /* return checksum in low-order 16 bits */
406 in_cksum_optimized(void *parg
, int nbytes
)
408 unsigned short *ptr
= parg
;
409 register long sum
; /* assumes long == 32 bits */
410 register unsigned short answer
; /* assumes unsigned short == 16 bits */
413 * Our algorithm is simple, using a 32-bit accumulator (sum),
414 * we add sequential 16-bit words to it, and at the end, fold back
415 * all the carry bits from the top 16 bits into the lower 16 bits.
419 count
= nbytes
>> 1; /* div by 2 */
420 for (ptr
--; count
; --count
)
423 if (nbytes
& 1) /* Odd */
424 sum
+= *(uint8_t *)(++ptr
); /* one byte only */
427 * Add back carry outs from top 16 bits to low 16 bits.
430 sum
= (sum
>> 16) + (sum
& 0xffff); /* add high-16 to low-16 */
431 sum
+= (sum
>> 16); /* add carry */
432 answer
= ~sum
; /* ones-complement, then truncate to 16 bits */
437 static int /* return checksum in low-order 16 bits */
438 in_cksum_rfc(void *parg
, int count
)
441 unsigned short *addr
= parg
;
442 /* Compute Internet Checksum for "count" bytes
443 * beginning at location "addr".
445 register long sum
= 0;
448 /* This is the inner loop */
452 /* Add left-over byte, if any */
454 sum
+= *(uint8_t *)addr
;
457 /* Fold 32-bit sum to 16 bits */
459 sum
= (sum
& 0xffff) + (sum
>> 16);
464 int main(int argc
, char **argv
)
466 /* 60017 65629 702179 */
467 #define MAXDATALEN 60017
468 #define BUFSIZE MAXDATALEN + sizeof(uint16_t)
469 uint8_t buffer
[BUFSIZE
];
471 #define EXERCISESTEP 257
472 struct prng
*prng
= prng_new(0);
475 uint16_t ospfd
, isisd
, lib
, in_csum
, in_csum_res
, in_csum_rfc
;
478 exercise
+= EXERCISESTEP
;
479 exercise
%= MAXDATALEN
;
481 printf("\rexercising length %d\033[K", exercise
);
483 for (i
= 0; i
< exercise
; i
++)
484 buffer
[i
] = prng_rand(prng
);
486 in_csum
= in_cksum(buffer
, exercise
);
487 in_csum_res
= in_cksum_optimized(buffer
, exercise
);
488 in_csum_rfc
= in_cksum_rfc(buffer
, exercise
);
489 if (in_csum_res
!= in_csum
|| in_csum
!= in_csum_rfc
)
490 printf("\nverify: in_chksum failed in_csum:%x, in_csum_res:%x,in_csum_rfc %x, len:%d\n",
491 in_csum
, in_csum_res
, in_csum_rfc
, exercise
);
494 uint16_t in_csum_iov
;
496 iov
[0].iov_base
= buffer
;
497 iov
[0].iov_len
= exercise
/ 2;
498 iov
[1].iov_base
= buffer
+ iov
[0].iov_len
;
499 iov
[1].iov_len
= exercise
- iov
[0].iov_len
;
501 in_csum_iov
= in_cksumv(iov
, 2);
502 if (in_csum_iov
!= in_csum
)
503 printf("\nverify: in_cksumv failed, lens: %zu+%zu\n",
504 iov
[0].iov_len
, iov
[1].iov_len
);
507 /* force split with byte leftover */
508 iov
[0].iov_base
= buffer
;
509 iov
[0].iov_len
= (exercise
/ 2) | 1;
510 iov
[1].iov_base
= buffer
+ iov
[0].iov_len
;
512 iov
[2].iov_base
= buffer
+ iov
[0].iov_len
+ 2;
513 iov
[2].iov_len
= exercise
- iov
[0].iov_len
- 2;
515 in_csum_iov
= in_cksumv(iov
, 3);
516 if (in_csum_iov
!= in_csum
)
517 printf("\nverify: in_cksumv failed, lens: %zu+%zu+%zu, got %04x, expected %04x\n",
518 iov
[0].iov_len
, iov
[1].iov_len
,
519 iov
[2].iov_len
, in_csum_iov
, in_csum
);
521 /* force split without byte leftover */
522 iov
[0].iov_base
= buffer
;
523 iov
[0].iov_len
= (exercise
/ 2) & ~1UL;
524 iov
[1].iov_base
= buffer
+ iov
[0].iov_len
;
526 iov
[2].iov_base
= buffer
+ iov
[0].iov_len
+ 2;
527 iov
[2].iov_len
= exercise
- iov
[0].iov_len
- 2;
529 in_csum_iov
= in_cksumv(iov
, 3);
530 if (in_csum_iov
!= in_csum
)
531 printf("\nverify: in_cksumv failed, lens: %zu+%zu+%zu, got %04x, expected %04x\n",
532 iov
[0].iov_len
, iov
[1].iov_len
,
533 iov
[2].iov_len
, in_csum_iov
, in_csum
);
536 if (exercise
>= FLETCHER_CHECKSUM_VALIDATE
)
539 ospfd
= ospfd_checksum(buffer
, exercise
+ sizeof(uint16_t),
541 if (verify(buffer
, exercise
+ sizeof(uint16_t)))
542 printf("\nverify: ospfd failed\n");
543 isisd
= iso_csum_create(buffer
, exercise
+ sizeof(uint16_t),
545 if (verify(buffer
, exercise
+ sizeof(uint16_t)))
546 printf("\nverify: isisd failed\n");
547 lib
= fletcher_checksum(buffer
, exercise
+ sizeof(uint16_t),
549 if (verify(buffer
, exercise
+ sizeof(uint16_t)))
550 printf("\nverify: lib failed\n");
553 printf("\nMismatch in values at size %d\n"
554 "ospfd: 0x%04x\tc0: %d\tc1: %d\tx: %d\ty: %d\n"
555 "isisd: 0x%04x\tc0: %d\tc1: %d\tx: %d\ty: %d\n"
557 exercise
, ospfd
, ospfd_vals
.a
.c0
,
558 ospfd_vals
.a
.c1
, ospfd_vals
.x
, ospfd_vals
.y
,
559 isisd
, isisd_vals
.a
.c0
, isisd_vals
.a
.c1
,
560 isisd_vals
.x
, isisd_vals
.y
, lib
);
562 /* Investigate reduction phase discrepencies */
563 if (ospfd_vals
.a
.c0
== isisd_vals
.a
.c0
564 && ospfd_vals
.a
.c1
== isisd_vals
.a
.c1
) {
566 for (i
= 0; reducts
[i
].name
!= NULL
; i
++) {
567 ospfd
= reducts
[i
].f(
569 exercise
+ sizeof(uint16_t),
571 printf("%20s: x: %02x, y %02x, checksum 0x%04x\n",
574 ospfd_vals
.y
& 0xff, ospfd
);
578 printf("\n uint8_t testdata [] = {\n ");
579 for (i
= 0; i
< exercise
; i
++) {
580 printf("0x%02x,%s", buffer
[i
],
581 (i
+ 1) % 8 ? " " : "\n ");