tests/test-checksum.c

   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 }