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