![[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|
Return to test-checksum.c CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / tests |
1.1 misho 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
27:
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;
1.1.1.2 ! misho 35: int i, partial_len;
1.1 misho 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;
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: };
266:
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;
399: int i, partial_len;
400:
401: p = buffer;
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:
1.1.1.2 ! misho 427: static int /* return checksum in low-order 16 bits */
1.1 misho 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:
1.1.1.2 ! misho 459: static int /* return checksum in low-order 16 bits */
1.1 misho 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:
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) {
499: u_int16_t ospfd, isisd, lib, in_csum, in_csum_res, in_csum_rfc;
500: int i,j;
501:
502: exercise += EXERCISESTEP;
503: exercise %= MAXDATALEN;
504:
505: for (i = 0; i < exercise; i += sizeof (long int)) {
506: long int rand = random ();
507:
508: for (j = sizeof (long int); j > 0; j--)
509: buffer[i + (sizeof (long int) - j)] = (rand >> (j * 8)) & 0xff;
510: }
511:
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:
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");
545: for (i = 0; reducts[i].name != NULL; i++) {
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 ");
555: for (i = 0; i < exercise; i++) {
556: printf ("0x%02x,%s",
557: buffer[i],
558: (i + 1) % 8 ? " " : "\n ");
559: }
560: printf ("\n}\n");
561: exit (1);
562: }
563: }
564: }