]>
git.proxmox.com Git - mirror_frr.git/blob - tests/lib/test_checksum.c
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
27 struct thread_master
*master
;
40 static struct csum_vals ospfd_vals
, isisd_vals
;
42 typedef size_t testsz_t
;
43 typedef uint16_t testoff_t
;
45 /* Fletcher Checksum -- Refer to RFC1008. */
48 /* The final reduction phase.
49 * This one should be the original ospfd version
51 static uint16_t reduce_ospfd(struct csum_vals
*vals
, testsz_t len
,
59 x
= ((len
- off
- 1) * c0
- c1
) % 255;
67 /* take care endian issue. */
68 return htons((x
<< 8) + y
);
75 /* slightly different concatenation */
76 static uint16_t reduce_ospfd1(struct csum_vals
*vals
, testsz_t len
,
84 x
= ((len
- off
- 1) * c0
- c1
) % 255;
91 /* take care endian issue. */
92 return htons((x
<< 8) | (y
& 0xff));
99 /* original isisd version */
100 static uint16_t reduce_isisd(struct csum_vals
*vals
, testsz_t len
,
105 #define c0 vals->a.c0
106 #define c1 vals->a.c1
109 mul
= (len
- off
) * (c0
);
126 return htons((x
<< 8) | (y
& 0xff));
134 /* Is the -1 in y wrong perhaps? */
135 static uint16_t reduce_isisd_yfix(struct csum_vals
*vals
, testsz_t len
,
140 #define c0 vals->a.c0
141 #define c1 vals->a.c1
144 mul
= (len
- off
) * (c0
);
161 return htons((x
<< 8) | (y
& 0xff));
169 /* Move the mods yp */
170 static uint16_t reduce_isisd_mod(struct csum_vals
*vals
, testsz_t len
,
175 #define c0 vals->a.c0
176 #define c1 vals->a.c1
179 mul
= (len
- off
) * (c0
);
196 return htons((x
<< 8) | (y
& 0xff));
204 /* Move the mods up + fix y */
205 static uint16_t reduce_isisd_mody(struct csum_vals
*vals
, testsz_t len
,
210 #define c0 vals->a.c0
211 #define c1 vals->a.c1
214 mul
= (len
- off
) * (c0
);
231 return htons((x
<< 8) | (y
& 0xff));
239 struct reductions_t
{
241 uint16_t (*f
)(struct csum_vals
*, testsz_t
, testoff_t
);
243 {.name
= "ospfd", .f
= reduce_ospfd
},
244 {.name
= "ospfd-1", .f
= reduce_ospfd1
},
245 {.name
= "isisd", .f
= reduce_isisd
},
246 {.name
= "isisd-yfix", .f
= reduce_isisd_yfix
},
247 {.name
= "isisd-mod", .f
= reduce_isisd_mod
},
248 {.name
= "isisd-mody", .f
= reduce_isisd_mody
},
252 /* The original ospfd checksum */
253 static uint16_t ospfd_checksum(uint8_t *buffer
, testsz_t len
, testoff_t off
)
255 uint8_t *sp
, *ep
, *p
, *q
;
258 uint16_t checksum
, *csum
;
260 csum
= (uint16_t *)(buffer
+ off
);
265 for (ep
= sp
+ len
; sp
< ep
; sp
= q
) {
269 for (p
= sp
; p
< q
; p
++) {
277 ospfd_vals
.a
.c0
= c0
;
278 ospfd_vals
.a
.c1
= c1
;
280 // printf ("%s: len %u, off %u, c0 %d, c1 %d\n",
281 // __func__, len, off, c0, c1);
283 x
= ((int)(len
- off
- 1) * (int)c0
- (int)c1
) % 255;
297 /* take care endian issue. */
298 checksum
= htons((x
<< 8) | (y
& 0xff));
303 /* the original, broken isisd checksum */
304 static uint16_t iso_csum_create(uint8_t *buffer
, testsz_t len
, testoff_t off
)
313 uint16_t checksum
, *csum
;
314 int i
, init_len
, partial_len
;
318 csum
= (uint16_t *)(buffer
+ off
);
327 partial_len
= MIN(len
, MODX
);
329 for (i
= 0; i
< partial_len
; i
++) {
340 isisd_vals
.a
.c0
= c0
;
341 isisd_vals
.a
.c1
= c1
;
343 mul
= (init_len
- off
) * c0
;
364 checksum
= htons((x
<< 8) | (y
& 0xFF));
368 /* return the checksum for user usage */
372 static int verify(uint8_t *buffer
, testsz_t len
)
385 partial_len
= MIN(len
, 5803U);
387 for (i
= 0; i
< partial_len
; i
++) {
397 if (c0
== 0 && c1
== 0)
403 static int /* return checksum in low-order 16 bits */
404 in_cksum_optimized(void *parg
, int nbytes
)
406 unsigned short *ptr
= parg
;
407 register long sum
; /* assumes long == 32 bits */
408 register unsigned short answer
; /* assumes unsigned short == 16 bits */
411 * Our algorithm is simple, using a 32-bit accumulator (sum),
412 * we add sequential 16-bit words to it, and at the end, fold back
413 * all the carry bits from the top 16 bits into the lower 16 bits.
417 count
= nbytes
>> 1; /* div by 2 */
418 for (ptr
--; count
; --count
)
421 if (nbytes
& 1) /* Odd */
422 sum
+= *(uint8_t *)(++ptr
); /* one byte only */
425 * Add back carry outs from top 16 bits to low 16 bits.
428 sum
= (sum
>> 16) + (sum
& 0xffff); /* add high-16 to low-16 */
429 sum
+= (sum
>> 16); /* add carry */
430 answer
= ~sum
; /* ones-complement, then truncate to 16 bits */
435 static int /* return checksum in low-order 16 bits */
436 in_cksum_rfc(void *parg
, int count
)
439 unsigned short *addr
= parg
;
440 /* Compute Internet Checksum for "count" bytes
441 * beginning at location "addr".
443 register long sum
= 0;
446 /* This is the inner loop */
450 /* Add left-over byte, if any */
452 sum
+= *(uint8_t *)addr
;
455 /* Fold 32-bit sum to 16 bits */
457 sum
= (sum
& 0xffff) + (sum
>> 16);
462 int main(int argc
, char **argv
)
464 /* 60017 65629 702179 */
465 #define MAXDATALEN 60017
466 #define BUFSIZE MAXDATALEN + sizeof(uint16_t)
467 uint8_t buffer
[BUFSIZE
];
469 #define EXERCISESTEP 257
473 uint16_t ospfd
, isisd
, lib
, in_csum
, in_csum_res
, in_csum_rfc
;
476 exercise
+= EXERCISESTEP
;
477 exercise
%= MAXDATALEN
;
479 for (i
= 0; i
< exercise
; i
+= sizeof(long int)) {
480 long int rand
= random();
482 for (j
= sizeof(long int); j
> 0; j
--)
483 buffer
[i
+ (sizeof(long int) - j
)] =
484 (rand
>> (j
* 8)) & 0xff;
487 in_csum
= in_cksum(buffer
, exercise
);
488 in_csum_res
= in_cksum_optimized(buffer
, exercise
);
489 in_csum_rfc
= in_cksum_rfc(buffer
, exercise
);
490 if (in_csum_res
!= in_csum
|| in_csum
!= in_csum_rfc
)
491 printf("verify: in_chksum failed in_csum:%x, in_csum_res:%x,"
492 "in_csum_rfc %x, len:%d\n",
493 in_csum
, in_csum_res
, in_csum_rfc
, exercise
);
495 ospfd
= ospfd_checksum(buffer
, exercise
+ sizeof(uint16_t),
497 if (verify(buffer
, exercise
+ sizeof(uint16_t)))
498 printf("verify: ospfd failed\n");
499 isisd
= iso_csum_create(buffer
, exercise
+ sizeof(uint16_t),
501 if (verify(buffer
, exercise
+ sizeof(uint16_t)))
502 printf("verify: isisd failed\n");
503 lib
= fletcher_checksum(buffer
, exercise
+ sizeof(uint16_t),
505 if (verify(buffer
, exercise
+ sizeof(uint16_t)))
506 printf("verify: lib failed\n");
509 printf("Mismatch in values at size %d\n"
510 "ospfd: 0x%04x\tc0: %d\tc1: %d\tx: %d\ty: %d\n"
511 "isisd: 0x%04x\tc0: %d\tc1: %d\tx: %d\ty: %d\n"
513 exercise
, ospfd
, ospfd_vals
.a
.c0
,
514 ospfd_vals
.a
.c1
, ospfd_vals
.x
, ospfd_vals
.y
,
515 isisd
, isisd_vals
.a
.c0
, isisd_vals
.a
.c1
,
516 isisd_vals
.x
, isisd_vals
.y
, lib
);
518 /* Investigate reduction phase discrepencies */
519 if (ospfd_vals
.a
.c0
== isisd_vals
.a
.c0
520 && ospfd_vals
.a
.c1
== isisd_vals
.a
.c1
) {
522 for (i
= 0; reducts
[i
].name
!= NULL
; i
++) {
523 ospfd
= reducts
[i
].f(
525 exercise
+ sizeof(uint16_t),
527 printf("%20s: x: %02x, y %02x, checksum 0x%04x\n",
530 ospfd_vals
.y
& 0xff, ospfd
);
534 printf("\n uint8_t testdata [] = {\n ");
535 for (i
= 0; i
< exercise
; i
++) {
536 printf("0x%02x,%s", buffer
[i
],
537 (i
+ 1) % 8 ? " " : "\n ");