Annotation of embedaddon/quagga/tests/test-checksum.c, revision 1.1
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: }
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