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