OpenSourceRouting / quagga-snap / 439c52f1900

Commits

Joakim Tjernlund authored and Paul Jakma committed 439c52f1900 01 Dec 2008

Add test for Internet checksum.

Add 2 impl. of the Internet Checksum. One new optimized nad
one form RFC 1071. Turns out that the current Quagga in_cksum()
is buggy. On Big Endian routers it miscalculates odd sized buffers.

tests/test-checksum.c

Modified

-420
-421
+      len -= partial_len;
-422
+    }
-423
-424
+  if (c0 == 0 && c1 == 0)
-425
+    return 0;
-426
-427
+  return 1;
-428
+}
-429
-+
+int  /* return checksum in low-order 16 bits */
-+
+in_cksum_optimized(void *parg, int nbytes)
-+
+{
-+
+	u_short *ptr = parg;
-+
+	register long		sum;		/* assumes long == 32 bits */
-+
+	register u_short	answer;		/* assumes u_short == 16 bits */
-+
+	register int count;
-+
+	/*
-+
+	 * Our algorithm is simple, using a 32-bit accumulator (sum),
-+
+	 * we add sequential 16-bit words to it, and at the end, fold back
-+
+	 * all the carry bits from the top 16 bits into the lower 16 bits.
-+
+	 */
-+
-+
+	sum = 0;
-+
+	count = nbytes >> 1; /* div by 2 */
-+
+	for(ptr--; count; --count)
-+
+	  sum += *++ptr;
-+
-+
+	if (nbytes & 1) /* Odd */
-+
+	  sum += *(u_char *)(++ptr);   /* one byte only */
-+
-+
+	/*
-+
+	 * Add back carry outs from top 16 bits to low 16 bits.
-+
+	 */
-+
-+
+	sum  = (sum >> 16) + (sum & 0xffff);	/* add high-16 to low-16 */
-+
+	sum += (sum >> 16);			/* add carry */
-+
+	answer = ~sum;		/* ones-complement, then truncate to 16 bits */
-+
+	return(answer);
-+
+}
-+
-+
-+
+int /* return checksum in low-order 16 bits */
-+
+in_cksum_rfc(void *parg, int count)
-+
+/* from RFC 1071 */
-+
+{
-+
+	u_short *addr = parg;
-+
+	/* Compute Internet Checksum for "count" bytes
-+
+	 *         beginning at location "addr".
-+
+	 */
-+
+	register long  sum = 0;
-+
-+
+	while (count > 1)  {
-+
+	  /*  This is the inner loop */
-+
+	  sum += *addr++;
-+
+	  count -= 2;
-+
+	}
-+
+	/*  Add left-over byte, if any */
-+
+	if (count > 0) {
-+
+	  sum += *(u_char *)addr;
-+
+	}
-+
-+
+	/*  Fold 32-bit sum to 16 bits */
-+
+	while (sum>>16)
-+
+           sum = (sum & 0xffff) + (sum >> 16);
-+
+	return ~sum;
-+
+}
-+
-+
-489
+int
-490
+main(int argc, char **argv)
-491
+{
-492
+/* 60017 65629 702179 */
-493
+#define MAXDATALEN 60017
-494
+#define BUFSIZE MAXDATALEN + sizeof(u_int16_t)
-495
+  u_char buffer[BUFSIZE];
-496
+  int exercise = 0;
-497
+#define EXERCISESTEP 257
-498
-499
+  srandom (time (NULL));
-500
-501
+  while (1) {
--
+    u_int16_t ospfd, isisd, lib;
--
-+
+    u_int16_t ospfd, isisd, lib, in_csum, in_csum_res, in_csum_rfc;
-+
+    int i,j;
-+
-505
+    exercise += EXERCISESTEP;
-506
+    exercise %= MAXDATALEN;
-507
--
+    for (int i = 0; i < exercise; i += sizeof (long int)) {
-+
+    for (i = 0; i < exercise; i += sizeof (long int)) {
-509
+      long int rand = random ();
-510
--
+      for (int j = sizeof (long int); j > 0; j--)
-+
+      for (j = sizeof (long int); j > 0; j--)
-512
+        buffer[i + (sizeof (long int) - j)] = (rand >> (j * 8)) & 0xff;
-513
+    }
-514
-+
+    in_csum = in_cksum(buffer, exercise);
-+
+    in_csum_res = in_cksum_optimized(buffer, exercise);
-+
+    in_csum_rfc = in_cksum_rfc(buffer, exercise);
-+
+    if (in_csum_res != in_csum || in_csum != in_csum_rfc)
-+
+      printf ("verify: in_chksum failed in_csum:%x, in_csum_res:%x,"
-+
+	      "in_csum_rfc %x, len:%d\n",
-+
+	      in_csum, in_csum_res, in_csum_rfc, exercise);
-+
-523
+    ospfd = ospfd_checksum (buffer, exercise + sizeof(u_int16_t), exercise);
-524
+    if (verify (buffer, exercise + sizeof(u_int16_t)))
-525
+      printf ("verify: ospfd failed\n");
-526
+    isisd = iso_csum_create (buffer, exercise + sizeof(u_int16_t), exercise);
-527
+    if (verify (buffer, exercise + sizeof(u_int16_t)))
-528
+      printf ("verify: isisd failed\n");
-529
+    lib = fletcher_checksum (buffer, exercise + sizeof(u_int16_t), exercise);
-530
+    if (verify (buffer, exercise + sizeof(u_int16_t)))
-531
+      printf ("verify: lib failed\n");
-532
-538
+              exercise,
-539
+              ospfd, ospfd_vals.a.c0, ospfd_vals.a.c1, ospfd_vals.x, ospfd_vals.y,
-540
+              isisd, isisd_vals.a.c0, isisd_vals.a.c1, isisd_vals.x, isisd_vals.y,
-541
+              lib
-542
+              );
-543
-544
+      /* Investigate reduction phase discrepencies */
-545
+      if (ospfd_vals.a.c0 == isisd_vals.a.c0
-546
+          && ospfd_vals.a.c1 == isisd_vals.a.c1) {
-547
+        printf ("\n");
--
+        for (int i = 0; reducts[i].name != NULL; i++) {
-+
+        for (i = 0; reducts[i].name != NULL; i++) {
-549
+          ospfd = reducts[i].f (&ospfd_vals,
-550
+                                exercise + sizeof (u_int16_t),
-551
+                                exercise);
-552
+          printf ("%20s: x: %02x, y %02x, checksum 0x%04x\n",
-553
+                  reducts[i].name, ospfd_vals.x & 0xff, ospfd_vals.y & 0xff, ospfd);
-554
+        }
-555
+      }
-556
-557
+      printf ("\n  u_char testdata [] = {\n  ");
--
+      for (int i = 0; i < exercise; i++) {
-+
+      for (i = 0; i < exercise; i++) {
-559
+        printf ("0x%02x,%s",
-560
+                buffer[i],
-561
+                (i + 1) % 8 ? " " : "\n  ");
-562
+      }
-563
+      printf ("\n}\n");
-564
+      exit (1);
-565
+    }
-566
+  }
-567
+}

quagga-snap

Commits

Jira Issues

Add shortcut