[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"

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;

		for (i = 0; i < exercise; i += sizeof(long int)) {
			long int rand = 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("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);

		ospfd = ospfd_checksum(buffer, exercise + sizeof(uint16_t),
				       exercise);
		if (verify(buffer, exercise + sizeof(uint16_t)))
			printf("verify: ospfd failed\n");
		isisd = iso_csum_create(buffer, exercise + sizeof(uint16_t),
					exercise);
		if (verify(buffer, exercise + sizeof(uint16_t)))
			printf("verify: isisd failed\n");
		lib = fletcher_checksum(buffer, exercise + sizeof(uint16_t),
					exercise);
		if (verify(buffer, exercise + sizeof(uint16_t)))
			printf("verify: lib failed\n");

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