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