1 /* 2 * Copyright (c) 2017 Todd C. Miller <millert@openbsd.org> 3 * 4 * Permission to use, copy, modify, and distribute this software for any 5 * purpose with or without fee is hereby granted, provided that the above 6 * copyright notice and this permission notice appear in all copies. 7 * 8 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 9 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 10 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 11 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 12 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 13 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 14 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 15 */ 16 17 #include <sys/time.h> 18 19 #include <stdbool.h> 20 #include <stdio.h> 21 #include <stdlib.h> 22 #include <string.h> 23 #include <setjmp.h> 24 #include <time.h> 25 #include <unistd.h> 26 #include <err.h> 27 28 /* 29 * Test program based on Bentley & McIlroy's "Engineering a Sort Function". 30 * Uses mergesort(3) to check the results. 31 * 32 * Additional "killer" input taken from: 33 * David R. Musser's "Introspective Sorting and Selection Algorithms" 34 * http://calmerthanyouare.org/2014/06/11/algorithmic-complexity-attacks-and-libc-qsort.html 35 * M. D. McIlroy's "A Killer Adversary for Quicksort" 36 */ 37 38 /* 39 * TODO: 40 * test with unaligned elements (char[]?) 41 */ 42 struct test_distribution { 43 const char *name; 44 void (*fill)(void *x, int n, int m); 45 int (*test)(struct test_distribution *d, int n, void *x, void *y, void *z); 46 int (*cmp)(const void *v1, const void *v2); 47 int (*cmp_checked)(const void *v1, const void *v2); 48 }; 49 50 #define MINIMUM(a, b) (((a) < (b)) ? (a) : (b)) 51 #define MAXIMUM(a, b) (((a) > (b)) ? (a) : (b)) 52 53 static size_t compares; 54 static size_t max_compares; 55 static size_t abrt_compares; 56 static sigjmp_buf cmpjmp; 57 static bool dump_table, timing, verbose; 58 59 extern int antiqsort(int n, int *a, int *ptr); 60 61 static int 62 cmp_i(const void *v1, const void *v2) 63 { 64 const int a = *(const int *)v1; 65 const int b = *(const int *)v2; 66 67 return a > b ? 1 : a < b ? -1 : 0; 68 } 69 70 static int 71 cmp_checked_i(const void *v1, const void *v2) 72 { 73 const int a = *(const int *)v1; 74 const int b = *(const int *)v2; 75 76 compares++; 77 if (compares > abrt_compares) 78 siglongjmp(cmpjmp, 1); 79 return a > b ? 1 : a < b ? -1 : 0; 80 } 81 82 static int 83 cmp_ll(const void *v1, const void *v2) 84 { 85 const long long a = *(const long long *)v1; 86 const long long b = *(const long long *)v2; 87 88 return a > b ? 1 : a < b ? -1 : 0; 89 } 90 91 static int 92 cmp_checked_ll(const void *v1, const void *v2) 93 { 94 const long long a = *(const long long *)v1; 95 const long long b = *(const long long *)v2; 96 97 compares++; 98 if (compares > abrt_compares) 99 siglongjmp(cmpjmp, 1); 100 return a > b ? 1 : a < b ? -1 : 0; 101 } 102 103 static int 104 cmp_d(const void *v1, const void *v2) 105 { 106 const double a = *(const double *)v1; 107 const double b = *(const double *)v2; 108 109 return a > b ? 1 : a < b ? -1 : 0; 110 } 111 112 static int 113 cmp_checked_d(const void *v1, const void *v2) 114 { 115 const double a = *(const double *)v1; 116 const double b = *(const double *)v2; 117 118 compares++; 119 if (compares > abrt_compares) 120 siglongjmp(cmpjmp, 1); 121 return a > b ? 1 : a < b ? -1 : 0; 122 } 123 124 static int 125 check_result(char *sub, size_t es, char *got, char *expected, struct test_distribution *d, 126 int m, int n) 127 { 128 int i; 129 130 if (verbose || compares > max_compares) { 131 if (sub != NULL) { 132 if (m != 0) { 133 warnx("%s (%s): m: %d, n: %d, %zu compares, " 134 "max %zu(%zu)", d->name, sub, m, n, 135 compares, max_compares, abrt_compares); 136 } else { 137 warnx("%s (%s): n: %d, %zu compares, " 138 "max %zu(%zu)", d->name, sub, n, 139 compares, max_compares, abrt_compares); 140 } 141 } else { 142 if (m != 0) { 143 warnx("%s: m: %d, n: %d, %zu compares, " 144 "max %zu(%zu)", d->name, m, n, 145 compares, max_compares, abrt_compares); 146 } else { 147 warnx("%s: n: %d, %zu compares, " 148 "max %zu(%zu)", d->name, n, 149 compares, max_compares, abrt_compares); 150 } 151 } 152 } 153 154 for (i = 0; i < n; i++) { 155 if (memcmp(got, expected, es) != 0) 156 break; 157 got += es; 158 expected += es; 159 } 160 if (i == n) 161 return 0; 162 163 if (sub != NULL) { 164 warnx("%s (%s): failure at %d, m: %d, n: %d", 165 d->name, sub, i, m, n); 166 } else { 167 warnx("%s: failure at %d, m: %d, n: %d", 168 d->name, i, m, n); 169 } 170 return 1; 171 } 172 173 #define FILL_SAWTOOTH(x, n, m) do { \ 174 int i; \ 175 \ 176 for (i = 0; i < n; i++) \ 177 x[i] = i % m; \ 178 } while (0) 179 180 static void 181 fill_sawtooth_i(void *v, int n, int m) 182 { 183 int *x = v; 184 FILL_SAWTOOTH(x, n, m); 185 } 186 187 static void 188 fill_sawtooth_ll(void *v, int n, int m) 189 { 190 long long *x = v; 191 FILL_SAWTOOTH(x, n, m); 192 } 193 194 static void 195 fill_sawtooth_double(void *v, int n, int m) 196 { 197 double *x = v; 198 FILL_SAWTOOTH(x, n, m); 199 } 200 201 #define FILL_RANDOM(x, n, m) do { \ 202 int i; \ 203 \ 204 for (i = 0; i < n; i++) \ 205 x[i] = arc4random_uniform(m); \ 206 } while (0) 207 208 209 static void 210 fill_random_i(void *v, int n, int m) 211 { 212 int *x = v; 213 FILL_RANDOM(x, n, m); 214 } 215 216 static void 217 fill_random_ll(void *v, int n, int m) 218 { 219 long long *x = v; 220 FILL_RANDOM(x, n, m); 221 } 222 223 static void 224 fill_random_double(void *v, int n, int m) 225 { 226 double *x = v; 227 FILL_RANDOM(x, n, m); 228 } 229 230 #define FILL_STAGGER(x, n, m) do { \ 231 int i; \ 232 \ 233 for (i = 0; i < n; i++) \ 234 x[i] = (i * m + i) % n; \ 235 } while (0) 236 237 238 static void 239 fill_stagger_i(void *v, int n, int m) 240 { 241 int *x = v; 242 FILL_STAGGER(x, n, m); 243 } 244 245 static void 246 fill_stagger_ll(void *v, int n, int m) 247 { 248 long long *x = v; 249 FILL_STAGGER(x, n, m); 250 } 251 252 static void 253 fill_stagger_double(void *v, int n, int m) 254 { 255 double *x = v; 256 FILL_STAGGER(x, n, m); 257 } 258 259 #define FILL_PLATEAU(x, n, m) do { \ 260 int i; \ 261 \ 262 for (i = 0; i < n; i++) \ 263 x[i] = MINIMUM(i, m); \ 264 } while (0) 265 266 static void 267 fill_plateau_i(void *v, int n, int m) 268 { 269 int *x = v; 270 FILL_PLATEAU(x, n, m); 271 } 272 273 static void 274 fill_plateau_ll(void *v, int n, int m) 275 { 276 long long *x = v; 277 FILL_PLATEAU(x, n, m); 278 } 279 280 static void 281 fill_plateau_double(void *v, int n, int m) 282 { 283 double *x = v; 284 FILL_PLATEAU(x, n, m); 285 } 286 287 #define FILL_SHUFFLE(x, n, m) do { \ 288 int i, j, k; \ 289 \ 290 for (i = 0, j = 0, k = 1; i < n; i++) \ 291 x[i] = arc4random_uniform(m) ? (j += 2) : (k += 2); \ 292 } while (0) 293 294 static void 295 fill_shuffle_i(void *v, int n, int m) 296 { 297 int *x = v; 298 FILL_SHUFFLE(x, n, m); 299 } 300 301 static void 302 fill_shuffle_ll(void *v, int n, int m) 303 { 304 long long *x = v; 305 FILL_SHUFFLE(x, n, m); 306 } 307 308 static void 309 fill_shuffle_double(void *v, int n, int m) 310 { 311 double *x = v; 312 FILL_SHUFFLE(x, n, m); 313 } 314 315 #define FILL_BSD_KILLER(x, n, m) do { \ 316 int i, k; \ 317 \ 318 /* 4.4BSD insertion sort optimization killer, Mats Linander */ \ 319 k = n / 2; \ 320 for (i = 0; i < n; i++) { \ 321 if (i < k) \ 322 x[i] = k - i; \ 323 else if (i > k) \ 324 x[i] = n + k + 1 - i; \ 325 else \ 326 x[i] = k + 1; \ 327 } \ 328 } while (0) 329 330 static void 331 fill_bsd_killer_i(void *v, int n, int m) 332 { 333 int *x = v; 334 FILL_BSD_KILLER(x, n, m); 335 336 } 337 338 static void 339 fill_bsd_killer_ll(void *v, int n, int m) 340 { 341 long long *x = v; 342 FILL_BSD_KILLER(x, n, m); 343 344 } 345 346 static void 347 fill_bsd_killer_double(void *v, int n, int m) 348 { 349 double *x = v; 350 FILL_BSD_KILLER(x, n, m); 351 352 } 353 354 #define FILL_MED3_KILLER(x, n, m) do { \ 355 int i, k; \ 356 \ 357 /* \ 358 * Median of 3 killer, as seen in David R Musser's \ 359 * "Introspective Sorting and Selection Algorithms" \ 360 */ \ 361 if (n & 1) { \ 362 /* odd size, store last at end and make even. */ \ 363 x[n - 1] = n; \ 364 n--; \ 365 } \ 366 k = n / 2; \ 367 for (i = 0; i < n; i++) { \ 368 if (i & 1) { \ 369 x[i] = k + x[i - 1]; \ 370 } else { \ 371 x[i] = i + 1; \ 372 } \ 373 } \ 374 } while (0) 375 376 static void 377 fill_med3_killer_i(void *v, int n, int m) 378 { 379 int *x = v; 380 FILL_MED3_KILLER(x, n, m); 381 } 382 383 static void 384 fill_med3_killer_ll(void *v, int n, int m) 385 { 386 long long *x = v; 387 FILL_MED3_KILLER(x, n, m); 388 } 389 390 static void 391 fill_med3_killer_double(void *v, int n, int m) 392 { 393 double *x = v; 394 FILL_MED3_KILLER(x, n, m); 395 } 396 397 static void 398 print_timing(struct test_distribution *d, char *sub, int m, int n, double elapsed) 399 { 400 if (sub != NULL) { 401 if (m != 0) { 402 warnx("%s (%s): m: %d, n: %d, %f seconds", 403 d->name, sub, m, n, elapsed); 404 } else { 405 warnx("%s (%s): n: %d, %f seconds", 406 d->name, sub, n, elapsed); 407 } 408 } else { 409 if (m != 0) { 410 warnx("%s: m: %d, n: %d, %f seconds", 411 d->name, m, n, elapsed); 412 } else { 413 warnx("%s: n: %d, %f seconds", 414 d->name, n, elapsed); 415 } 416 } 417 } 418 419 static int 420 do_test(struct test_distribution *d, char *sub, int m, int n, size_t es, void *y, void *z) 421 { 422 int ret = 0; 423 struct timespec before, after; 424 425 compares = 0; 426 if (sigsetjmp(cmpjmp, 1) != 0) { 427 if (sub != NULL) { 428 warnx("%s (%s): qsort aborted after %zu compares, m: %d, n: %d", 429 d->name, sub, compares, m, n); 430 } else { 431 warnx("%s: qsort aborted after %zu compares, m: %d, n: %d", 432 d->name, compares, m, n); 433 } 434 ret = 1; 435 } else { 436 if (timing) 437 clock_gettime(CLOCK_MONOTONIC, &before); 438 qsort(y, n, es, d->cmp_checked); 439 if (timing) { 440 double elapsed; 441 clock_gettime(CLOCK_MONOTONIC, &after); 442 timespecsub(&after, &before, &after); 443 elapsed = after.tv_sec + after.tv_nsec / 1000000000.0; 444 print_timing(d, sub, m, n, elapsed); 445 } 446 if (check_result(sub, es, y, z, d, m, n) != 0) 447 ret = 1; 448 } 449 return ret; 450 } 451 452 #define TEST_PERTURBED(d, n, x, y, z) do { \ 453 int i, j, m; \ 454 const int es = sizeof(x[0]); \ 455 \ 456 for (m = 1; m < 2 * n; m *= 2) { \ 457 /* Fill in x[n] modified by m */ \ 458 d->fill(x, n, m); \ 459 \ 460 /* Test on copy of x[] */ \ 461 for (i = 0; i < n; i++) \ 462 y[i] = z[i] = x[i]; \ 463 if (mergesort(z, n, es, d->cmp) != 0) \ 464 err(1, NULL); \ 465 if (do_test(d, "copy", m, n, es, y, z) != 0) \ 466 ret = 1; \ 467 \ 468 /* Test on reversed copy of x[] */ \ 469 for (i = 0, j = n - 1; i < n; i++, j--) \ 470 y[i] = z[i] = x[j]; \ 471 if (mergesort(z, n, es, d->cmp) != 0) \ 472 err(1, NULL); \ 473 if (do_test(d, "reversed", m, n, es, y, z) != 0) \ 474 ret = 1; \ 475 \ 476 /* Test with front half of x[] reversed */ \ 477 for (i = 0, j = (n / 2) - 1; i < n / 2; i++, j--) \ 478 y[i] = z[i] = x[j]; \ 479 for (; i < n; i++) \ 480 y[i] = z[i] = x[i]; \ 481 if (mergesort(z, n, es, d->cmp) != 0) \ 482 err(1, NULL); \ 483 if (do_test(d, "front reversed", m, n, es, y, z) != 0) \ 484 ret = 1; \ 485 \ 486 /* Test with back half of x[] reversed */ \ 487 for (i = 0; i < n / 2; i++) \ 488 y[i] = z[i] = x[i]; \ 489 for (j = n - 1; i < n; i++, j--) \ 490 y[i] = z[i] = x[j]; \ 491 if (mergesort(z, n, es, d->cmp) != 0) \ 492 err(1, NULL); \ 493 if (do_test(d, "back reversed", m, n, es, y, z) != 0) \ 494 ret = 1; \ 495 \ 496 /* Test on sorted copy of x[] */ \ 497 if (mergesort(x, n, es, d->cmp) != 0) \ 498 err(1, NULL); \ 499 for (i = 0; i < n; i++) \ 500 y[i] = x[i]; \ 501 if (do_test(d, "sorted", m, n, es, y, x) != 0) \ 502 ret = 1; \ 503 \ 504 /* Test with i%5 added to x[i] (dither) */ \ 505 for (i = 0, j = n - 1; i < n; i++, j--) \ 506 y[i] = z[i] = x[j] + (i % 5); \ 507 if (mergesort(z, n, es, d->cmp) != 0) \ 508 err(1, NULL); \ 509 if (do_test(d, "dithered", m, n, es, y, z) != 0) \ 510 ret = 1; \ 511 } \ 512 } while (0) 513 514 static int 515 test_perturbed_i(struct test_distribution *d, int n, void *vx, void *vy, void *vz) 516 { 517 int *x = vx; 518 int *y = vx; 519 int *z = vz; 520 int ret = 0; 521 522 TEST_PERTURBED(d, n, x, y, z); 523 return ret; 524 } 525 526 static int 527 test_perturbed_ll(struct test_distribution *d, int n, void *vx, void *vy, void *vz) 528 { 529 long long *x = vx; 530 long long *y = vx; 531 long long *z = vz; 532 int ret = 0; 533 534 TEST_PERTURBED(d, n, x, y, z); 535 return ret; 536 } 537 538 static int 539 test_perturbed_double(struct test_distribution *d, int n, void *vx, void *vy, void *vz) 540 { 541 double *x = vx; 542 double *y = vx; 543 double *z = vz; 544 int ret = 0; 545 546 TEST_PERTURBED(d, n, x, y, z); 547 return ret; 548 } 549 550 /* 551 * Like TEST_PERTURBED but because the input is tailored to cause 552 * quicksort to go quadratic we don't perturb the input. 553 */ 554 #define TEST_SIMPLE(d, n, x, y, z) do { \ 555 int i, ret = 0; \ 556 \ 557 /* Fill in x[n] */ \ 558 d->fill(x, n, 0); \ 559 \ 560 /* Make a copy of x[] */ \ 561 for (i = 0; i < n; i++) \ 562 y[i] = z[i] = x[i]; \ 563 if (mergesort(z, n, sizeof(z[0]), d->cmp) != 0) \ 564 err(1, NULL); \ 565 if (do_test(d, NULL, 0, n, sizeof(x[0]), y, z) != 0) \ 566 ret = 1; \ 567 } while (0) 568 569 static int 570 test_simple_i(struct test_distribution *d, int n, void *vx, void *vy, void *vz) 571 { 572 int *x = vx; 573 int *y = vx; 574 int *z = vz; 575 int ret = 0; 576 577 TEST_SIMPLE(d, n, x, y, z); 578 return ret; 579 } 580 581 static int 582 test_simple_ll(struct test_distribution *d, int n, void *vx, void *vy, void *vz) 583 { 584 long long *x = vx; 585 long long *y = vx; 586 long long *z = vz; 587 int ret = 0; 588 589 TEST_SIMPLE(d, n, x, y, z); 590 return ret; 591 } 592 593 static int 594 test_simple_double(struct test_distribution *d, int n, void *vx, void *vy, void *vz) 595 { 596 double *x = vx; 597 double *y = vx; 598 double *z = vz; 599 int ret = 0; 600 601 TEST_SIMPLE(d, n, x, y, z); 602 return ret; 603 } 604 605 /* 606 * Use D. McIlroy's "Killer Adversary for Quicksort" 607 * We don't compare the results in this case. 608 */ 609 static int 610 test_antiqsort(struct test_distribution *d, int n, void *vx, void *vy, void *vz) 611 { 612 struct timespec before, after; 613 int *x = vx; 614 int *y = vx; 615 int i, ret = 0; 616 617 /* 618 * We expect antiqsort to generate > 1.5 * nlgn compares. 619 * If introspection is not used, it will be > 10 * nlgn compares. 620 */ 621 if (timing) 622 clock_gettime(CLOCK_MONOTONIC, &before); 623 i = antiqsort(n, x, y); 624 if (timing) 625 clock_gettime(CLOCK_MONOTONIC, &after); 626 if (i > abrt_compares) 627 ret = 1; 628 if (dump_table) { 629 printf("/* %d items, %d compares */\n", n, i); 630 printf("static const int table_%d[] = {", n); 631 for (i = 0; i < n - 1; i++) { 632 if ((i % 12) == 0) 633 printf("\n\t"); 634 printf("%4d, ", x[i]); 635 } 636 printf("%4d\n};\n", x[i]); 637 } else { 638 if (timing) { 639 double elapsed; 640 timespecsub(&after, &before, &after); 641 elapsed = after.tv_sec + after.tv_nsec / 1000000000.0; 642 print_timing(d, NULL, 0, n, elapsed); 643 } 644 if (verbose || ret != 0) { 645 warnx("%s: n: %d, %d compares, max %zu(%zu)", 646 d->name, n, i, max_compares, abrt_compares); 647 } 648 } 649 650 return ret; 651 } 652 653 static struct test_distribution distributions[] = { 654 { "sawtooth_i", fill_sawtooth_i, test_perturbed_i, cmp_i, cmp_checked_i }, 655 { "sawtooth_ll", fill_sawtooth_ll, test_perturbed_ll, cmp_ll, cmp_checked_ll }, 656 { "sawtooth_d", fill_sawtooth_double, test_perturbed_double, cmp_d, cmp_checked_d }, 657 { "random_i", fill_random_i, test_perturbed_i, cmp_i, cmp_checked_i }, 658 { "random_ll", fill_random_ll, test_perturbed_ll, cmp_ll, cmp_checked_ll }, 659 { "random_d", fill_random_double, test_perturbed_double, cmp_d, cmp_checked_d }, 660 { "stagger_i", fill_stagger_i, test_perturbed_i, cmp_i, cmp_checked_i }, 661 { "stagger_ll", fill_stagger_ll, test_perturbed_ll, cmp_ll, cmp_checked_ll }, 662 { "stagger_d", fill_stagger_double, test_perturbed_double, cmp_d, cmp_checked_d }, 663 { "plateau_i", fill_plateau_i, test_perturbed_i, cmp_i, cmp_checked_i }, 664 { "plateau_ll", fill_plateau_ll, test_perturbed_ll, cmp_ll, cmp_checked_ll }, 665 { "plateau_d", fill_plateau_double, test_perturbed_double, cmp_d, cmp_checked_d }, 666 { "shuffle_i", fill_shuffle_i, test_perturbed_i, cmp_i, cmp_checked_i }, 667 { "shuffle_ll", fill_shuffle_ll, test_perturbed_ll, cmp_ll, cmp_checked_ll }, 668 { "shuffle_d", fill_shuffle_double, test_perturbed_double, cmp_d, cmp_checked_d }, 669 { "bsd_killer_i", fill_bsd_killer_i, test_simple_i, cmp_i, cmp_checked_i }, 670 { "bsd_killer_ll", fill_bsd_killer_ll, test_simple_ll, cmp_ll, cmp_checked_ll }, 671 { "bsd_killer_d", fill_bsd_killer_double, test_simple_double, cmp_d, cmp_checked_d }, 672 { "med3_killer_i", fill_med3_killer_i, test_simple_i, cmp_i, cmp_checked_i }, 673 { "med3_killer_ll", fill_med3_killer_ll, test_simple_ll, cmp_ll, cmp_checked_ll }, 674 { "med3_killer_d", fill_med3_killer_double, test_simple_double, cmp_d, cmp_checked_d }, 675 { "antiqsort", NULL, test_antiqsort, cmp_i, cmp_checked_i }, 676 { NULL } 677 }; 678 679 static int 680 run_tests(int n, const char *name) 681 { 682 void *x, *y, *z; 683 int i, nlgn = 0; 684 int ret = 0; 685 size_t es; 686 struct test_distribution *d; 687 688 /* 689 * We expect A*n*lg(n) compares where A is between 1 and 2. 690 * For A > 1.5, print a warning. 691 * For A > 10 abort the test since qsort has probably gone quadratic. 692 */ 693 for (i = n - 1; i > 0; i >>= 1) 694 nlgn++; 695 nlgn *= n; 696 max_compares = nlgn * 1.5; 697 abrt_compares = nlgn * 10; 698 699 /* Allocate enough space to store ints or doubles. */ 700 es = MAXIMUM(sizeof(int), sizeof(double)); 701 x = reallocarray(NULL, n, es); 702 y = reallocarray(NULL, n, es); 703 z = reallocarray(NULL, n, es); 704 if (x == NULL || y == NULL || z == NULL) 705 err(1, NULL); 706 707 for (d = distributions; d->name != NULL; d++) { 708 if (name != NULL && strncmp(name, d->name, strlen(name)) != 0) 709 continue; 710 if (d->test(d, n, x, y, z) != 0) 711 ret = 1; 712 } 713 714 free(x); 715 free(y); 716 free(z); 717 return ret; 718 } 719 720 __dead void 721 usage(void) 722 { 723 fprintf(stderr, "usage: qsort_test [-dvt] [-n test_name] [num ...]\n"); 724 exit(1); 725 } 726 727 int 728 main(int argc, char *argv[]) 729 { 730 char *nums[] = { "100", "1023", "1024", "1025", "4095", "4096", "4097" }; 731 struct test_distribution *d; 732 int ch, n, ret = 0; 733 char *name = NULL; 734 735 while ((ch = getopt(argc, argv, "dn:tv")) != -1) { 736 switch (ch) { 737 case 'd': 738 dump_table = true; 739 break; 740 case 'n': 741 for (d = distributions; d->name != NULL; d++) { 742 if (strncmp(optarg, d->name, strlen(optarg)) == 0) 743 break; 744 } 745 if (d->name == NULL) 746 errx(1, "unknown test %s", optarg); 747 name = optarg; 748 break; 749 case 't': 750 timing = true; 751 break; 752 case 'v': 753 verbose = true; 754 break; 755 default: 756 usage(); 757 break; 758 } 759 } 760 argc -= optind; 761 argv += optind; 762 763 if (argc == 0) { 764 argv = nums; 765 argc = sizeof(nums) / sizeof(nums[0]); 766 } 767 768 while (argc > 0) { 769 n = atoi(*argv); 770 if (run_tests(n, name) != 0) 771 ret = 1; 772 argc--; 773 argv++; 774 } 775 776 return ret; 777 } 778