tests/lib/test_checksum.c

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