[mirror_frr.git] / tests / lib / test_checksum.c

/*
 * 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"

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
	srandom(time(NULL));

	while (1) {
		uint16_t ospfd, isisd, lib, in_csum, in_csum_res, in_csum_rfc;
		int i, j;

		exercise += EXERCISESTEP;
		exercise %= MAXDATALEN;

		printf("\rexercising length %d\033[K", exercise);

		for (i = 0; i < exercise; i += sizeof(long int)) {
			long int rand = frr_weak_random();

			for (j = sizeof(long int); j > 0; j--)
				buffer[i + (sizeof(long int) - j)] =
					(rand >> (j * 8)) & 0xff;
		}

		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);
		}

		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);
		}
	}
}
Commit	Line	Data
d62a17ae	1	/*
46f4a4d2 PJ	2	* Copyright (C) 2008 Sun Microsystems, Inc.
	3	*
	4	* This file is part of Quagga.
	5	*
	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
	9	* later version.
	10	*
	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.
	15	*
896014f4 DL	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
46f4a4d2 PJ	19	*/
46f4a4d2 PJ	20
5d4b8cf2 PJ	21	#include <zebra.h>
	22	#include <stdlib.h>
	23	#include <time.h>
	24
	25	#include "checksum.h"
5920b3eb	26	#include "network.h"
5d4b8cf2 PJ	27
	28	struct thread_master *master;
	29
	30	struct acc_vals {
d62a17ae	31	int c0;
d62a17ae	32	int c1;
5d4b8cf2 PJ	33	};
	34
	35	struct csum_vals {
d62a17ae	36	struct acc_vals a;
	37	int x;
	38	int y;
5d4b8cf2 PJ	39	};
	40
	41	static struct csum_vals ospfd_vals, isisd_vals;
	42
	43	typedef size_t testsz_t;
	44	typedef uint16_t testoff_t;
	45
	46	/* Fletcher Checksum -- Refer to RFC1008. */
db7d7ba4	47	#define MODX 4102U
6b0655a2	48
5d4b8cf2	49	/* The final reduction phase.
d62a17ae	50	* This one should be the original ospfd version
5d4b8cf2	51	*/
d7c0a89a QY	52	static uint16_t reduce_ospfd(struct csum_vals *vals, testsz_t len,
d7c0a89a QY	53	testoff_t off)
5d4b8cf2 PJ	54	{
	55	#define x vals->x
	56	#define y vals->y
	57	#define c0 vals->a.c0
	58	#define c1 vals->a.c1
	59
d62a17ae	60	x = ((len - off - 1) * c0 - c1) % 255;
5d4b8cf2	61
d62a17ae	62	if (x <= 0)
	63	x += 255;
	64	y = 510 - c0 - x;
	65	if (y > 255)
	66	y -= 255;
	67
	68	/* take care endian issue. */
	69	return htons((x << 8) + y);
5d4b8cf2 PJ	70	#undef x
	71	#undef y
	72	#undef c0
	73	#undef c1
	74	}
	75
	76	/* slightly different concatenation */
d7c0a89a QY	77	static uint16_t reduce_ospfd1(struct csum_vals *vals, testsz_t len,
d7c0a89a QY	78	testoff_t off)
5d4b8cf2 PJ	79	{
	80	#define x vals->x
	81	#define y vals->y
	82	#define c0 vals->a.c0
	83	#define c1 vals->a.c1
	84
d62a17ae	85	x = ((len - off - 1) * c0 - c1) % 255;
	86	if (x <= 0)
	87	x += 255;
	88	y = 510 - c0 - x;
	89	if (y > 255)
	90	y -= 255;
5d4b8cf2	91
d62a17ae	92	/* take care endian issue. */
d62a17ae	93	return htons((x << 8) \| (y & 0xff));
5d4b8cf2 PJ	94	#undef x
	95	#undef y
	96	#undef c0
	97	#undef c1
	98	}
	99
	100	/* original isisd version */
d7c0a89a QY	101	static uint16_t reduce_isisd(struct csum_vals *vals, testsz_t len,
d7c0a89a QY	102	testoff_t off)
5d4b8cf2 PJ	103	{
	104	#define x vals->x
	105	#define y vals->y
	106	#define c0 vals->a.c0
	107	#define c1 vals->a.c1
d7c0a89a	108	uint32_t mul;
d62a17ae	109
	110	mul = (len - off) * (c0);
	111	x = mul - c0 - c1;
	112	y = c1 - mul - 1;
5d4b8cf2	113
d62a17ae	114	if (y > 0)
	115	y++;
	116	if (x < 0)
	117	x--;
5d4b8cf2	118
d62a17ae	119	x %= 255;
d62a17ae	120	y %= 255;
5d4b8cf2	121
d62a17ae	122	if (x == 0)
	123	x = 255;
	124	if (y == 0)
	125	y = 1;
5d4b8cf2	126
d62a17ae	127	return htons((x << 8) \| (y & 0xff));
5d4b8cf2 PJ	128
	129	#undef x
	130	#undef y
	131	#undef c0
	132	#undef c1
	133	}
	134
	135	/* Is the -1 in y wrong perhaps? */
d7c0a89a QY	136	static uint16_t reduce_isisd_yfix(struct csum_vals *vals, testsz_t len,
d7c0a89a QY	137	testoff_t off)
5d4b8cf2 PJ	138	{
	139	#define x vals->x
	140	#define y vals->y
	141	#define c0 vals->a.c0
	142	#define c1 vals->a.c1
d7c0a89a	143	uint32_t mul;
d62a17ae	144
	145	mul = (len - off) * (c0);
	146	x = mul - c0 - c1;
	147	y = c1 - mul;
5d4b8cf2	148
d62a17ae	149	if (y > 0)
	150	y++;
	151	if (x < 0)
	152	x--;
5d4b8cf2	153
d62a17ae	154	x %= 255;
d62a17ae	155	y %= 255;
5d4b8cf2	156
d62a17ae	157	if (x == 0)
	158	x = 255;
	159	if (y == 0)
	160	y = 1;
5d4b8cf2	161
d62a17ae	162	return htons((x << 8) \| (y & 0xff));
5d4b8cf2 PJ	163
	164	#undef x
	165	#undef y
	166	#undef c0
	167	#undef c1
	168	}
	169
	170	/* Move the mods yp */
d7c0a89a QY	171	static uint16_t reduce_isisd_mod(struct csum_vals *vals, testsz_t len,
d7c0a89a QY	172	testoff_t off)
5d4b8cf2 PJ	173	{
	174	#define x vals->x
	175	#define y vals->y
	176	#define c0 vals->a.c0
	177	#define c1 vals->a.c1
d7c0a89a	178	uint32_t mul;
5d4b8cf2	179
d62a17ae	180	mul = (len - off) * (c0);
	181	x = mul - c1 - c0;
	182	y = c1 - mul - 1;
5d4b8cf2	183
d62a17ae	184	x %= 255;
d62a17ae	185	y %= 255;
5d4b8cf2	186
d62a17ae	187	if (y > 0)
	188	y++;
	189	if (x < 0)
	190	x--;
5d4b8cf2	191
d62a17ae	192	if (x == 0)
	193	x = 255;
	194	if (y == 0)
	195	y = 1;
	196
	197	return htons((x << 8) \| (y & 0xff));
5d4b8cf2 PJ	198
	199	#undef x
	200	#undef y
	201	#undef c0
	202	#undef c1
	203	}
	204
	205	/* Move the mods up + fix y */
d7c0a89a QY	206	static uint16_t reduce_isisd_mody(struct csum_vals *vals, testsz_t len,
d7c0a89a QY	207	testoff_t off)
5d4b8cf2 PJ	208	{
	209	#define x vals->x
	210	#define y vals->y
	211	#define c0 vals->a.c0
	212	#define c1 vals->a.c1
d7c0a89a	213	uint32_t mul;
d62a17ae	214
	215	mul = (len - off) * (c0);
	216	x = mul - c0 - c1;
	217	y = c1 - mul;
5d4b8cf2	218
d62a17ae	219	x %= 255;
d62a17ae	220	y %= 255;
5d4b8cf2	221
d62a17ae	222	if (y > 0)
	223	y++;
	224	if (x < 0)
	225	x--;
5d4b8cf2	226
d62a17ae	227	if (x == 0)
	228	x = 255;
	229	if (y == 0)
	230	y = 1;
5d4b8cf2	231
d62a17ae	232	return htons((x << 8) \| (y & 0xff));
5d4b8cf2 PJ	233
	234	#undef x
	235	#undef y
	236	#undef c0
	237	#undef c1
	238	}
	239
	240	struct reductions_t {
d62a17ae	241	const char *name;
d7c0a89a	242	uint16_t (f)(struct csum_vals , testsz_t, testoff_t);
5d4b8cf2	243	} reducts[] = {
d62a17ae	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},
	250	{NULL, NULL},
5d4b8cf2	251	};
6b0655a2	252
5d4b8cf2	253	/* The original ospfd checksum */
d7c0a89a	254	static uint16_t ospfd_checksum(uint8_t *buffer, testsz_t len, testoff_t off)
5d4b8cf2	255	{
d7c0a89a	256	uint8_t sp, ep, p, q;
d62a17ae	257	int c0 = 0, c1 = 0;
d62a17ae	258	int x, y;
d7c0a89a	259	uint16_t checksum, *csum;
d62a17ae	260
d7c0a89a	261	csum = (uint16_t *)(buffer + off);
d62a17ae	262	*(csum) = 0;
	263
	264	sp = buffer;
	265
	266	for (ep = sp + len; sp < ep; sp = q) {
	267	q = sp + MODX;
	268	if (q > ep)
	269	q = ep;
	270	for (p = sp; p < q; p++) {
	271	c0 += *p;
	272	c1 += c0;
	273	}
	274	c0 %= 255;
	275	c1 %= 255;
	276	}
	277
	278	ospfd_vals.a.c0 = c0;
	279	ospfd_vals.a.c1 = c1;
	280
	281	// printf ("%s: len %u, off %u, c0 %d, c1 %d\n",
	282	// __func__, len, off, c0, c1);
	283
	284	x = ((int)(len - off - 1) * (int)c0 - (int)c1) % 255;
	285
	286	if (x <= 0)
	287	x += 255;
	288	y = 510 - c0 - x;
	289	if (y > 255)
	290	y -= 255;
	291
	292	ospfd_vals.x = x;
	293	ospfd_vals.y = y;
	294
	295	buffer[off] = x;
	296	buffer[off + 1] = y;
	297
	298	/* take care endian issue. */
	299	checksum = htons((x << 8) \| (y & 0xff));
	300
	301	return (checksum);
5d4b8cf2 PJ	302	}
	303
	304	/* the original, broken isisd checksum */
d7c0a89a	305	static uint16_t iso_csum_create(uint8_t *buffer, testsz_t len, testoff_t off)
5d4b8cf2 PJ	306	{
5d4b8cf2 PJ	307
d7c0a89a	308	uint8_t *p;
d62a17ae	309	int x;
d62a17ae	310	int y;
d7c0a89a QY	311	uint32_t mul;
	312	uint32_t c0;
	313	uint32_t c1;
	314	uint16_t checksum, *csum;
d62a17ae	315	int i, init_len, partial_len;
	316
	317	checksum = 0;
	318
d7c0a89a	319	csum = (uint16_t *)(buffer + off);
d62a17ae	320	*(csum) = checksum;
	321
	322	p = buffer;
	323	c0 = 0;
	324	c1 = 0;
	325	init_len = len;
	326
	327	while (len != 0) {
	328	partial_len = MIN(len, MODX);
	329
	330	for (i = 0; i < partial_len; i++) {
	331	c0 = c0 + *(p++);
	332	c1 += c0;
	333	}
	334
	335	c0 = c0 % 255;
	336	c1 = c1 % 255;
	337
	338	len -= partial_len;
5d4b8cf2 PJ	339	}
5d4b8cf2 PJ	340
d62a17ae	341	isisd_vals.a.c0 = c0;
	342	isisd_vals.a.c1 = c1;
	343
	344	mul = (init_len - off) * c0;
	345
	346	x = mul - c1 - c0;
	347	y = c1 - mul - 1;
	348
	349	if (y > 0)
	350	y++;
	351	if (x < 0)
	352	x--;
	353
	354	x %= 255;
	355	y %= 255;
	356
	357	if (x == 0)
	358	x = 255;
	359	if (y == 0)
	360	y = 1;
	361
	362	isisd_vals.x = x;
	363	isisd_vals.y = y;
	364
	365	checksum = htons((x << 8) \| (y & 0xFF));
	366
	367	*(csum) = checksum;
	368
	369	/* return the checksum for user usage */
	370	return checksum;
5d4b8cf2 PJ	371	}
5d4b8cf2 PJ	372
d7c0a89a	373	static int verify(uint8_t *buffer, testsz_t len)
5d4b8cf2	374	{
d7c0a89a QY	375	uint8_t *p;
	376	uint32_t c0;
	377	uint32_t c1;
d62a17ae	378	int i, partial_len;
	379
	380	p = buffer;
	381
	382	c0 = 0;
	383	c1 = 0;
	384
	385	while (len) {
	386	partial_len = MIN(len, 5803U);
	387
	388	for (i = 0; i < partial_len; i++) {
	389	c0 = c0 + *(p++);
	390	c1 += c0;
	391	}
	392	c0 = c0 % 255;
	393	c1 = c1 % 255;
	394
	395	len -= partial_len;
	396	}
	397
	398	if (c0 == 0 && c1 == 0)
	399	return 0;
	400
	401	return 1;
5d4b8cf2 PJ	402	}
5d4b8cf2 PJ	403
d62a17ae	404	static int /* return checksum in low-order 16 bits */
9d303b37	405	in_cksum_optimized(void *parg, int nbytes)
439c52f1	406	{
d7c0a89a	407	unsigned short *ptr = parg;
d62a17ae	408	register long sum; /* assumes long == 32 bits */
d7c0a89a	409	register unsigned short answer; /* assumes unsigned short == 16 bits */
439c52f1 JT	410	register int count;
	411	/*
	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.
	415	*/
	416
	417	sum = 0;
	418	count = nbytes >> 1; /* div by 2 */
d62a17ae	419	for (ptr--; count; --count)
d62a17ae	420	sum += *++ptr;
439c52f1	421
d62a17ae	422	if (nbytes & 1) /* Odd */
d7c0a89a	423	sum += (uint8_t )(++ptr); /* one byte only */
439c52f1 JT	424
	425	/*
	426	* Add back carry outs from top 16 bits to low 16 bits.
	427	*/
	428
d62a17ae	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 */
	432	return (answer);
439c52f1 JT	433	}
	434
	435
1dba254e	436	static int /* return checksum in low-order 16 bits */
9d303b37	437	in_cksum_rfc(void *parg, int count)
439c52f1 JT	438	/* from RFC 1071 */
439c52f1 JT	439	{
d7c0a89a	440	unsigned short *addr = parg;
439c52f1 JT	441	/* Compute Internet Checksum for "count" bytes
	442	* beginning at location "addr".
	443	*/
d62a17ae	444	register long sum = 0;
439c52f1	445
d62a17ae	446	while (count > 1) {
	447	/* This is the inner loop */
	448	sum += *addr++;
	449	count -= 2;
439c52f1 JT	450	}
	451	/* Add left-over byte, if any */
	452	if (count > 0) {
d7c0a89a	453	sum += (uint8_t )addr;
439c52f1 JT	454	}
	455
	456	/* Fold 32-bit sum to 16 bits */
d62a17ae	457	while (sum >> 16)
d62a17ae	458	sum = (sum & 0xffff) + (sum >> 16);
439c52f1 JT	459	return ~sum;
	460	}
	461
	462
d62a17ae	463	int main(int argc, char **argv)
5d4b8cf2 PJ	464	{
	465	/* 60017 65629 702179 */
	466	#define MAXDATALEN 60017
d7c0a89a QY	467	#define BUFSIZE MAXDATALEN + sizeof(uint16_t)
d7c0a89a QY	468	uint8_t buffer[BUFSIZE];
d62a17ae	469	int exercise = 0;
5d4b8cf2	470	#define EXERCISESTEP 257
d62a17ae	471	srandom(time(NULL));
	472
	473	while (1) {
d7c0a89a	474	uint16_t ospfd, isisd, lib, in_csum, in_csum_res, in_csum_rfc;
d62a17ae	475	int i, j;
	476
	477	exercise += EXERCISESTEP;
	478	exercise %= MAXDATALEN;
	479
89087f23 DL	480	printf("\rexercising length %d\033[K", exercise);
89087f23 DL	481
d62a17ae	482	for (i = 0; i < exercise; i += sizeof(long int)) {
5920b3eb	483	long int rand = frr_weak_random();
d62a17ae	484
	485	for (j = sizeof(long int); j > 0; j--)
	486	buffer[i + (sizeof(long int) - j)] =
	487	(rand >> (j * 8)) & 0xff;
	488	}
	489
	490	in_csum = in_cksum(buffer, exercise);
	491	in_csum_res = in_cksum_optimized(buffer, exercise);
	492	in_csum_rfc = in_cksum_rfc(buffer, exercise);
	493	if (in_csum_res != in_csum \|\| in_csum != in_csum_rfc)
89087f23	494	printf("\nverify: in_chksum failed in_csum:%x, in_csum_res:%x,in_csum_rfc %x, len:%d\n",
d62a17ae	495	in_csum, in_csum_res, in_csum_rfc, exercise);
d62a17ae	496
89087f23 DL	497	struct iovec iov[3];
	498	uint16_t in_csum_iov;
	499
	500	iov[0].iov_base = buffer;
	501	iov[0].iov_len = exercise / 2;
	502	iov[1].iov_base = buffer + iov[0].iov_len;
	503	iov[1].iov_len = exercise - iov[0].iov_len;
	504
	505	in_csum_iov = in_cksumv(iov, 2);
	506	if (in_csum_iov != in_csum)
	507	printf("\nverify: in_cksumv failed, lens: %zu+%zu\n",
	508	iov[0].iov_len, iov[1].iov_len);
	509
	510	if (exercise >= 6) {
	511	/* force split with byte leftover */
	512	iov[0].iov_base = buffer;
	513	iov[0].iov_len = (exercise / 2) \| 1;
	514	iov[1].iov_base = buffer + iov[0].iov_len;
	515	iov[1].iov_len = 2;
	516	iov[2].iov_base = buffer + iov[0].iov_len + 2;
	517	iov[2].iov_len = exercise - iov[0].iov_len - 2;
	518
	519	in_csum_iov = in_cksumv(iov, 3);
	520	if (in_csum_iov != in_csum)
	521	printf("\nverify: in_cksumv failed, lens: %zu+%zu+%zu, got %04x, expected %04x\n",
	522	iov[0].iov_len, iov[1].iov_len,
	523	iov[2].iov_len, in_csum_iov, in_csum);
	524
	525	/* force split without byte leftover */
	526	iov[0].iov_base = buffer;
	527	iov[0].iov_len = (exercise / 2) & ~1UL;
	528	iov[1].iov_base = buffer + iov[0].iov_len;
	529	iov[1].iov_len = 2;
	530	iov[2].iov_base = buffer + iov[0].iov_len + 2;
	531	iov[2].iov_len = exercise - iov[0].iov_len - 2;
	532
	533	in_csum_iov = in_cksumv(iov, 3);
	534	if (in_csum_iov != in_csum)
	535	printf("\nverify: in_cksumv failed, lens: %zu+%zu+%zu, got %04x, expected %04x\n",
	536	iov[0].iov_len, iov[1].iov_len,
	537	iov[2].iov_len, in_csum_iov, in_csum);
	538	}
	539
d7c0a89a	540	ospfd = ospfd_checksum(buffer, exercise + sizeof(uint16_t),
d62a17ae	541	exercise);
d7c0a89a	542	if (verify(buffer, exercise + sizeof(uint16_t)))
89087f23	543	printf("\nverify: ospfd failed\n");
d7c0a89a	544	isisd = iso_csum_create(buffer, exercise + sizeof(uint16_t),
d62a17ae	545	exercise);
d7c0a89a	546	if (verify(buffer, exercise + sizeof(uint16_t)))
89087f23	547	printf("\nverify: isisd failed\n");
d7c0a89a	548	lib = fletcher_checksum(buffer, exercise + sizeof(uint16_t),
d62a17ae	549	exercise);
d7c0a89a	550	if (verify(buffer, exercise + sizeof(uint16_t)))
89087f23	551	printf("\nverify: lib failed\n");
d62a17ae	552
d62a17ae	553	if (ospfd != lib) {
89087f23	554	printf("\nMismatch in values at size %d\n"
d62a17ae	555	"ospfd: 0x%04x\tc0: %d\tc1: %d\tx: %d\ty: %d\n"
	556	"isisd: 0x%04x\tc0: %d\tc1: %d\tx: %d\ty: %d\n"
	557	"lib: 0x%04x\n",
	558	exercise, ospfd, ospfd_vals.a.c0,
	559	ospfd_vals.a.c1, ospfd_vals.x, ospfd_vals.y,
	560	isisd, isisd_vals.a.c0, isisd_vals.a.c1,
	561	isisd_vals.x, isisd_vals.y, lib);
	562
	563	/* Investigate reduction phase discrepencies */
	564	if (ospfd_vals.a.c0 == isisd_vals.a.c0
	565	&& ospfd_vals.a.c1 == isisd_vals.a.c1) {
	566	printf("\n");
	567	for (i = 0; reducts[i].name != NULL; i++) {
	568	ospfd = reducts[i].f(
	569	&ospfd_vals,
d7c0a89a	570	exercise + sizeof(uint16_t),
d62a17ae	571	exercise);
	572	printf("%20s: x: %02x, y %02x, checksum 0x%04x\n",
	573	reducts[i].name,
	574	ospfd_vals.x & 0xff,
	575	ospfd_vals.y & 0xff, ospfd);
	576	}
	577	}
	578
d7c0a89a	579	printf("\n uint8_t testdata [] = {\n ");
d62a17ae	580	for (i = 0; i < exercise; i++) {
	581	printf("0x%02x,%s", buffer[i],
	582	(i + 1) % 8 ? " " : "\n ");
	583	}
	584	printf("\n}\n");
	585	exit(1);
	586	}
	587	}
5d4b8cf2	588	}