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

// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * Copyright (C) 2008 Sun Microsystems, Inc.
 */

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