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