]>
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
28 struct thread_master
*master
;
41 static struct csum_vals ospfd_vals
, isisd_vals
;
43 typedef size_t testsz_t
;
44 typedef uint16_t testoff_t
;
46 /* Fletcher Checksum -- Refer to RFC1008. */
49 /* The final reduction phase.
50 * This one should be the original ospfd version
52 static uint16_t reduce_ospfd(struct csum_vals
*vals
, testsz_t len
,
60 x
= ((len
- off
- 1) * c0
- c1
) % 255;
68 /* take care endian issue. */
69 return htons((x
<< 8) + y
);
76 /* slightly different concatenation */
77 static uint16_t reduce_ospfd1(struct csum_vals
*vals
, testsz_t len
,
85 x
= ((len
- off
- 1) * c0
- c1
) % 255;
92 /* take care endian issue. */
93 return htons((x
<< 8) | (y
& 0xff));
100 /* original isisd version */
101 static uint16_t reduce_isisd(struct csum_vals
*vals
, testsz_t len
,
106 #define c0 vals->a.c0
107 #define c1 vals->a.c1
110 mul
= (len
- off
) * (c0
);
127 return htons((x
<< 8) | (y
& 0xff));
135 /* Is the -1 in y wrong perhaps? */
136 static uint16_t reduce_isisd_yfix(struct csum_vals
*vals
, testsz_t len
,
141 #define c0 vals->a.c0
142 #define c1 vals->a.c1
145 mul
= (len
- off
) * (c0
);
162 return htons((x
<< 8) | (y
& 0xff));
170 /* Move the mods yp */
171 static uint16_t reduce_isisd_mod(struct csum_vals
*vals
, testsz_t len
,
176 #define c0 vals->a.c0
177 #define c1 vals->a.c1
180 mul
= (len
- off
) * (c0
);
197 return htons((x
<< 8) | (y
& 0xff));
205 /* Move the mods up + fix y */
206 static uint16_t reduce_isisd_mody(struct csum_vals
*vals
, testsz_t len
,
211 #define c0 vals->a.c0
212 #define c1 vals->a.c1
215 mul
= (len
- off
) * (c0
);
232 return htons((x
<< 8) | (y
& 0xff));
240 struct reductions_t
{
242 uint16_t (*f
)(struct csum_vals
*, testsz_t
, testoff_t
);
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
},
253 /* The original ospfd checksum */
254 static uint16_t ospfd_checksum(uint8_t *buffer
, testsz_t len
, testoff_t off
)
256 uint8_t *sp
, *ep
, *p
, *q
;
259 uint16_t checksum
, *csum
;
261 csum
= (uint16_t *)(buffer
+ off
);
266 for (ep
= sp
+ len
; sp
< ep
; sp
= q
) {
270 for (p
= sp
; p
< q
; p
++) {
278 ospfd_vals
.a
.c0
= c0
;
279 ospfd_vals
.a
.c1
= c1
;
281 // printf ("%s: len %u, off %u, c0 %d, c1 %d\n",
282 // __func__, len, off, c0, c1);
284 x
= ((int)(len
- off
- 1) * (int)c0
- (int)c1
) % 255;
298 /* take care endian issue. */
299 checksum
= htons((x
<< 8) | (y
& 0xff));
304 /* the original, broken isisd checksum */
305 static uint16_t iso_csum_create(uint8_t *buffer
, testsz_t len
, testoff_t off
)
314 uint16_t checksum
, *csum
;
315 int i
, init_len
, partial_len
;
319 csum
= (uint16_t *)(buffer
+ off
);
328 partial_len
= MIN(len
, MODX
);
330 for (i
= 0; i
< partial_len
; i
++) {
341 isisd_vals
.a
.c0
= c0
;
342 isisd_vals
.a
.c1
= c1
;
344 mul
= (init_len
- off
) * c0
;
365 checksum
= htons((x
<< 8) | (y
& 0xFF));
369 /* return the checksum for user usage */
373 static int verify(uint8_t *buffer
, testsz_t len
)
386 partial_len
= MIN(len
, 5803U);
388 for (i
= 0; i
< partial_len
; i
++) {
398 if (c0
== 0 && c1
== 0)
404 static int /* return checksum in low-order 16 bits */
405 in_cksum_optimized(void *parg
, int nbytes
)
407 unsigned short *ptr
= parg
;
408 register long sum
; /* assumes long == 32 bits */
409 register unsigned short answer
; /* assumes unsigned short == 16 bits */
412 * Our algorithm is simple, using a 32-bit accumulator (sum),
413 * we add sequential 16-bit words to it, and at the end, fold back
414 * all the carry bits from the top 16 bits into the lower 16 bits.
418 count
= nbytes
>> 1; /* div by 2 */
419 for (ptr
--; count
; --count
)
422 if (nbytes
& 1) /* Odd */
423 sum
+= *(uint8_t *)(++ptr
); /* one byte only */
426 * Add back carry outs from top 16 bits to low 16 bits.
429 sum
= (sum
>> 16) + (sum
& 0xffff); /* add high-16 to low-16 */
430 sum
+= (sum
>> 16); /* add carry */
431 answer
= ~sum
; /* ones-complement, then truncate to 16 bits */
436 static int /* return checksum in low-order 16 bits */
437 in_cksum_rfc(void *parg
, int count
)
440 unsigned short *addr
= parg
;
441 /* Compute Internet Checksum for "count" bytes
442 * beginning at location "addr".
444 register long sum
= 0;
447 /* This is the inner loop */
451 /* Add left-over byte, if any */
453 sum
+= *(uint8_t *)addr
;
456 /* Fold 32-bit sum to 16 bits */
458 sum
= (sum
& 0xffff) + (sum
>> 16);
463 int main(int argc
, char **argv
)
465 /* 60017 65629 702179 */
466 #define MAXDATALEN 60017
467 #define BUFSIZE MAXDATALEN + sizeof(uint16_t)
468 uint8_t buffer
[BUFSIZE
];
470 #define EXERCISESTEP 257
474 uint16_t ospfd
, isisd
, lib
, in_csum
, in_csum_res
, in_csum_rfc
;
477 exercise
+= EXERCISESTEP
;
478 exercise
%= MAXDATALEN
;
480 for (i
= 0; i
< exercise
; i
+= sizeof(long int)) {
481 long int rand
= frr_weak_random();
483 for (j
= sizeof(long int); j
> 0; j
--)
484 buffer
[i
+ (sizeof(long int) - j
)] =
485 (rand
>> (j
* 8)) & 0xff;
488 in_csum
= in_cksum(buffer
, exercise
);
489 in_csum_res
= in_cksum_optimized(buffer
, exercise
);
490 in_csum_rfc
= in_cksum_rfc(buffer
, exercise
);
491 if (in_csum_res
!= in_csum
|| in_csum
!= in_csum_rfc
)
492 printf("verify: in_chksum failed in_csum:%x, in_csum_res:%x,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 ");