[mirror_frr.git] / tests / test-checksum.c

#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                 4102

/* Accumulator phase of checksum */
static 
struct acc_vals
accumulate (u_char *buffer, testsz_t len, testoff_t off)
{
  u_int8_t *p;
  u_int16_t *csum;
  int i, partial_len;
  struct acc_vals ret;
  
  csum = (u_int16_t *) (buffer + off);
  *(csum) = 0;
  
  p = buffer;
  ret.c0 = 0;
  ret.c1 = 0;
  
  while (len != 0)
    {
      partial_len = MIN(len, MODX);

      for (i = 0; i < partial_len; i++)
	{
	  ret.c0 = ret.c0 + *(p++);
	  ret.c1 += ret.c0;
	}

      ret.c0 = ret.c0 % 255;
      ret.c1 = ret.c1 % 255;

      len -= partial_len;
    }
  return ret;
}

/* The final reduction phase.
 * This one should be the original ospfd version 
 */
static u_int16_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 u_int16_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 u_int16_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
  u_int32_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 u_int16_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
  u_int32_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 u_int16_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
  u_int32_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 u_int16_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
  u_int32_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;
  u_int16_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 u_int16_t
ospfd_checksum (u_char *buffer, testsz_t len, testoff_t off)
{
  u_char *sp, *ep, *p, *q;
  int c0 = 0, c1 = 0;
  int x, y;
  u_int16_t checksum, *csum;

  csum = (u_int16_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 u_int16_t
iso_csum_create (u_char * buffer, testsz_t len, testoff_t off)
{

  u_int8_t *p;
  int x;
  int y;
  u_int32_t mul;
  u_int32_t c0;
  u_int32_t c1;
  u_int16_t checksum, *csum;
  int i, init_len, partial_len;

  checksum = 0;
  
  csum = (u_int16_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 (u_char * buffer, testsz_t len)
{
  u_int8_t *p;
  u_int32_t c0;
  u_int32_t c1;
  int i, partial_len;
 
  p = buffer;

  c0 = 0;
  c1 = 0;

  while (len)
    {
      partial_len = MIN(len, 5803);

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


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


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