Adding upstream version 8.4.4.upstream/8.4.4upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 587 insertions, 0 deletions

diff --git a/tests/lib/test_checksum.c b/tests/lib/test_checksum.c
new file mode 100644
index 0000000..9a7f2b1
--- /dev/null
+++ b/tests/lib/test_checksum.c
@@ -0,0 +1,587 @@
+/*
+ * Copyright (C) 2008 Sun Microsystems, Inc.
+ *
+ * This file is part of Quagga.
+ *
+ * Quagga is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2, or (at your option) any
+ * later version.
+ *
+ * Quagga is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; see the file COPYING; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <zebra.h>
+#include <stdlib.h>
+#include <time.h>
+
+#include "checksum.h"
+#include "network.h"
+#include "prng.h"
+
+struct thread_master *master;
+
+struct acc_vals {
+	int c0;
+	int c1;
+};
+
+struct csum_vals {
+	struct acc_vals a;
+	int x;
+	int y;
+};
+
+static struct csum_vals ospfd_vals, isisd_vals;
+
+typedef size_t testsz_t;
+typedef uint16_t testoff_t;
+
+/* Fletcher Checksum -- Refer to RFC1008. */
+#define MODX                 4102U
+
+/* The final reduction phase.
+ * This one should be the original ospfd version
+ */
+static uint16_t reduce_ospfd(struct csum_vals *vals, testsz_t len,
+			     testoff_t off)
+{
+#define x vals->x
+#define y vals->y
+#define c0 vals->a.c0
+#define c1 vals->a.c1
+
+	x = ((len - off - 1) * c0 - c1) % 255;
+
+	if (x <= 0)
+		x += 255;
+	y = 510 - c0 - x;
+	if (y > 255)
+		y -= 255;
+
+	/* take care endian issue. */
+	return htons((x << 8) + y);
+#undef x
+#undef y
+#undef c0
+#undef c1
+}
+
+/* slightly different concatenation */
+static uint16_t reduce_ospfd1(struct csum_vals *vals, testsz_t len,
+			      testoff_t off)
+{
+#define x vals->x
+#define y vals->y
+#define c0 vals->a.c0
+#define c1 vals->a.c1
+
+	x = ((len - off - 1) * c0 - c1) % 255;
+	if (x <= 0)
+		x += 255;
+	y = 510 - c0 - x;
+	if (y > 255)
+		y -= 255;
+
+	/* take care endian issue. */
+	return htons((x << 8) | (y & 0xff));
+#undef x
+#undef y
+#undef c0
+#undef c1
+}
+
+/* original isisd version */
+static uint16_t reduce_isisd(struct csum_vals *vals, testsz_t len,
+			     testoff_t off)
+{
+#define x vals->x
+#define y vals->y
+#define c0 vals->a.c0
+#define c1 vals->a.c1
+	uint32_t mul;
+
+	mul = (len - off) * (c0);
+	x = mul - c0 - c1;
+	y = c1 - mul - 1;
+
+	if (y > 0)
+		y++;
+	if (x < 0)
+		x--;
+
+	x %= 255;
+	y %= 255;
+
+	if (x == 0)
+		x = 255;
+	if (y == 0)
+		y = 1;
+
+	return htons((x << 8) | (y & 0xff));
+
+#undef x
+#undef y
+#undef c0
+#undef c1
+}
+
+/* Is the -1 in y wrong perhaps? */
+static uint16_t reduce_isisd_yfix(struct csum_vals *vals, testsz_t len,
+				  testoff_t off)
+{
+#define x vals->x
+#define y vals->y
+#define c0 vals->a.c0
+#define c1 vals->a.c1
+	uint32_t mul;
+
+	mul = (len - off) * (c0);
+	x = mul - c0 - c1;
+	y = c1 - mul;
+
+	if (y > 0)
+		y++;
+	if (x < 0)
+		x--;
+
+	x %= 255;
+	y %= 255;
+
+	if (x == 0)
+		x = 255;
+	if (y == 0)
+		y = 1;
+
+	return htons((x << 8) | (y & 0xff));
+
+#undef x
+#undef y
+#undef c0
+#undef c1
+}
+
+/* Move the mods yp */
+static uint16_t reduce_isisd_mod(struct csum_vals *vals, testsz_t len,
+				 testoff_t off)
+{
+#define x vals->x
+#define y vals->y
+#define c0 vals->a.c0
+#define c1 vals->a.c1
+	uint32_t mul;
+
+	mul = (len - off) * (c0);
+	x = mul - c1 - c0;
+	y = c1 - mul - 1;
+
+	x %= 255;
+	y %= 255;
+
+	if (y > 0)
+		y++;
+	if (x < 0)
+		x--;
+
+	if (x == 0)
+		x = 255;
+	if (y == 0)
+		y = 1;
+
+	return htons((x << 8) | (y & 0xff));
+
+#undef x
+#undef y
+#undef c0
+#undef c1
+}
+
+/* Move the mods up + fix y */
+static uint16_t reduce_isisd_mody(struct csum_vals *vals, testsz_t len,
+				  testoff_t off)
+{
+#define x vals->x
+#define y vals->y
+#define c0 vals->a.c0
+#define c1 vals->a.c1
+	uint32_t mul;
+
+	mul = (len - off) * (c0);
+	x = mul - c0 - c1;
+	y = c1 - mul;
+
+	x %= 255;
+	y %= 255;
+
+	if (y > 0)
+		y++;
+	if (x < 0)
+		x--;
+
+	if (x == 0)
+		x = 255;
+	if (y == 0)
+		y = 1;
+
+	return htons((x << 8) | (y & 0xff));
+
+#undef x
+#undef y
+#undef c0
+#undef c1
+}
+
+struct reductions_t {
+	const char *name;
+	uint16_t (*f)(struct csum_vals *, testsz_t, testoff_t);
+} reducts[] = {
+	{.name = "ospfd", .f = reduce_ospfd},
+	{.name = "ospfd-1", .f = reduce_ospfd1},
+	{.name = "isisd", .f = reduce_isisd},
+	{.name = "isisd-yfix", .f = reduce_isisd_yfix},
+	{.name = "isisd-mod", .f = reduce_isisd_mod},
+	{.name = "isisd-mody", .f = reduce_isisd_mody},
+	{NULL, NULL},
+};
+
+/* The original ospfd checksum */
+static uint16_t ospfd_checksum(uint8_t *buffer, testsz_t len, testoff_t off)
+{
+	uint8_t *sp, *ep, *p, *q;
+	int c0 = 0, c1 = 0;
+	int x, y;
+	uint16_t checksum, *csum;
+
+	csum = (uint16_t *)(buffer + off);
+	*(csum) = 0;
+
+	sp = buffer;
+
+	for (ep = sp + len; sp < ep; sp = q) {
+		q = sp + MODX;
+		if (q > ep)
+			q = ep;
+		for (p = sp; p < q; p++) {
+			c0 += *p;
+			c1 += c0;
+		}
+		c0 %= 255;
+		c1 %= 255;
+	}
+
+	ospfd_vals.a.c0 = c0;
+	ospfd_vals.a.c1 = c1;
+
+	// printf ("%s: len %u, off %u, c0 %d, c1 %d\n",
+	//        __func__, len, off, c0, c1);
+
+	x = ((int)(len - off - 1) * (int)c0 - (int)c1) % 255;
+
+	if (x <= 0)
+		x += 255;
+	y = 510 - c0 - x;
+	if (y > 255)
+		y -= 255;
+
+	ospfd_vals.x = x;
+	ospfd_vals.y = y;
+
+	buffer[off] = x;
+	buffer[off + 1] = y;
+
+	/* take care endian issue. */
+	checksum = htons((x << 8) | (y & 0xff));
+
+	return (checksum);
+}
+
+/* the original, broken isisd checksum */
+static uint16_t iso_csum_create(uint8_t *buffer, testsz_t len, testoff_t off)
+{
+
+	uint8_t *p;
+	int x;
+	int y;
+	uint32_t mul;
+	uint32_t c0;
+	uint32_t c1;
+	uint16_t checksum, *csum;
+	int i, init_len, partial_len;
+
+	checksum = 0;
+
+	csum = (uint16_t *)(buffer + off);
+	*(csum) = checksum;
+
+	p = buffer;
+	c0 = 0;
+	c1 = 0;
+	init_len = len;
+
+	while (len != 0) {
+		partial_len = MIN(len, MODX);
+
+		for (i = 0; i < partial_len; i++) {
+			c0 = c0 + *(p++);
+			c1 += c0;
+		}
+
+		c0 = c0 % 255;
+		c1 = c1 % 255;
+
+		len -= partial_len;
+	}
+
+	isisd_vals.a.c0 = c0;
+	isisd_vals.a.c1 = c1;
+
+	mul = (init_len - off) * c0;
+
+	x = mul - c1 - c0;
+	y = c1 - mul - 1;
+
+	if (y > 0)
+		y++;
+	if (x < 0)
+		x--;
+
+	x %= 255;
+	y %= 255;
+
+	if (x == 0)
+		x = 255;
+	if (y == 0)
+		y = 1;
+
+	isisd_vals.x = x;
+	isisd_vals.y = y;
+
+	checksum = htons((x << 8) | (y & 0xFF));
+
+	*(csum) = checksum;
+
+	/* return the checksum for user usage */
+	return checksum;
+}
+
+static int verify(uint8_t *buffer, testsz_t len)
+{
+	uint8_t *p;
+	uint32_t c0;
+	uint32_t c1;
+	int i, partial_len;
+
+	p = buffer;
+
+	c0 = 0;
+	c1 = 0;
+
+	while (len) {
+		partial_len = MIN(len, 5803U);
+
+		for (i = 0; i < partial_len; i++) {
+			c0 = c0 + *(p++);
+			c1 += c0;
+		}
+		c0 = c0 % 255;
+		c1 = c1 % 255;
+
+		len -= partial_len;
+	}
+
+	if (c0 == 0 && c1 == 0)
+		return 0;
+
+	return 1;
+}
+
+static int /* return checksum in low-order 16 bits */
+	in_cksum_optimized(void *parg, int nbytes)
+{
+	unsigned short *ptr = parg;
+	register long sum;       /* assumes long == 32 bits */
+	register unsigned short answer; /* assumes unsigned 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 += *(uint8_t *)(++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);
+}
+
+
+static int /* return checksum in low-order 16 bits */
+	in_cksum_rfc(void *parg, int count)
+/* from RFC 1071 */
+{
+	unsigned 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 += *(uint8_t *)addr;
+	}
+
+	/*  Fold 32-bit sum to 16 bits */
+	while (sum >> 16)
+		sum = (sum & 0xffff) + (sum >> 16);
+	return ~sum;
+}
+
+
+int main(int argc, char **argv)
+{
+/* 60017 65629 702179 */
+#define MAXDATALEN 60017
+#define BUFSIZE MAXDATALEN + sizeof(uint16_t)
+	uint8_t buffer[BUFSIZE];
+	int exercise = 0;
+#define EXERCISESTEP 257
+	struct prng *prng = prng_new(0);
+
+	while (1) {
+		uint16_t ospfd, isisd, lib, in_csum, in_csum_res, in_csum_rfc;
+		int i;
+
+		exercise += EXERCISESTEP;
+		exercise %= MAXDATALEN;
+
+		printf("\rexercising length %d\033[K", exercise);
+
+		for (i = 0; i < exercise; i++)
+			buffer[i] = prng_rand(prng);
+
+		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("\nverify: 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);
+
+		struct iovec iov[3];
+		uint16_t in_csum_iov;
+
+		iov[0].iov_base = buffer;
+		iov[0].iov_len = exercise / 2;
+		iov[1].iov_base = buffer + iov[0].iov_len;
+		iov[1].iov_len = exercise - iov[0].iov_len;
+
+		in_csum_iov = in_cksumv(iov, 2);
+		if (in_csum_iov != in_csum)
+			printf("\nverify: in_cksumv failed, lens: %zu+%zu\n",
+			       iov[0].iov_len, iov[1].iov_len);
+
+		if (exercise >= 6) {
+			/* force split with byte leftover */
+			iov[0].iov_base = buffer;
+			iov[0].iov_len = (exercise / 2) | 1;
+			iov[1].iov_base = buffer + iov[0].iov_len;
+			iov[1].iov_len = 2;
+			iov[2].iov_base = buffer + iov[0].iov_len + 2;
+			iov[2].iov_len = exercise - iov[0].iov_len - 2;
+
+			in_csum_iov = in_cksumv(iov, 3);
+			if (in_csum_iov != in_csum)
+				printf("\nverify: in_cksumv failed, lens: %zu+%zu+%zu, got %04x, expected %04x\n",
+				       iov[0].iov_len, iov[1].iov_len,
+				       iov[2].iov_len, in_csum_iov, in_csum);
+
+			/* force split without byte leftover */
+			iov[0].iov_base = buffer;
+			iov[0].iov_len = (exercise / 2) & ~1UL;
+			iov[1].iov_base = buffer + iov[0].iov_len;
+			iov[1].iov_len = 2;
+			iov[2].iov_base = buffer + iov[0].iov_len + 2;
+			iov[2].iov_len = exercise - iov[0].iov_len - 2;
+
+			in_csum_iov = in_cksumv(iov, 3);
+			if (in_csum_iov != in_csum)
+				printf("\nverify: in_cksumv failed, lens: %zu+%zu+%zu, got %04x, expected %04x\n",
+				       iov[0].iov_len, iov[1].iov_len,
+				       iov[2].iov_len, in_csum_iov, in_csum);
+		}
+
+		if (exercise >= FLETCHER_CHECKSUM_VALIDATE)
+			continue;
+
+		ospfd = ospfd_checksum(buffer, exercise + sizeof(uint16_t),
+				       exercise);
+		if (verify(buffer, exercise + sizeof(uint16_t)))
+			printf("\nverify: ospfd failed\n");
+		isisd = iso_csum_create(buffer, exercise + sizeof(uint16_t),
+					exercise);
+		if (verify(buffer, exercise + sizeof(uint16_t)))
+			printf("\nverify: isisd failed\n");
+		lib = fletcher_checksum(buffer, exercise + sizeof(uint16_t),
+					exercise);
+		if (verify(buffer, exercise + sizeof(uint16_t)))
+			printf("\nverify: lib failed\n");
+
+		if (ospfd != lib) {
+			printf("\nMismatch in values at size %d\n"
+			       "ospfd: 0x%04x\tc0: %d\tc1: %d\tx: %d\ty: %d\n"
+			       "isisd: 0x%04x\tc0: %d\tc1: %d\tx: %d\ty: %d\n"
+			       "lib: 0x%04x\n",
+			       exercise, ospfd, ospfd_vals.a.c0,
+			       ospfd_vals.a.c1, ospfd_vals.x, ospfd_vals.y,
+			       isisd, isisd_vals.a.c0, isisd_vals.a.c1,
+			       isisd_vals.x, isisd_vals.y, lib);
+
+			/* Investigate reduction phase discrepencies */
+			if (ospfd_vals.a.c0 == isisd_vals.a.c0
+			    && ospfd_vals.a.c1 == isisd_vals.a.c1) {
+				printf("\n");
+				for (i = 0; reducts[i].name != NULL; i++) {
+					ospfd = reducts[i].f(
+						&ospfd_vals,
+						exercise + sizeof(uint16_t),
+						exercise);
+					printf("%20s: x: %02x, y %02x, checksum 0x%04x\n",
+					       reducts[i].name,
+					       ospfd_vals.x & 0xff,
+					       ospfd_vals.y & 0xff, ospfd);
+				}
+			}
+
+			printf("\n  uint8_t testdata [] = {\n  ");
+			for (i = 0; i < exercise; i++) {
+				printf("0x%02x,%s", buffer[i],
+				       (i + 1) % 8 ? " " : "\n  ");
+			}
+			printf("\n}\n");
+			exit(1);
+		}
+	}
+}