tests/test-checksum.c

   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 \f
  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 \f
 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 }