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