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
cmp_i(const void * v1,const void * v2)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
cmp_checked_i(const void * v1,const void * v2)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
cmp_ll(const void * v1,const void * v2)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
cmp_checked_ll(const void * v1,const void * v2)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
cmp_d(const void * v1,const void * v2)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
cmp_checked_d(const void * v1,const void * v2)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
check_result(char * sub,size_t es,char * got,char * expected,struct test_distribution * d,int m,int n)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
fill_sawtooth_i(void * v,int n,int m)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
fill_sawtooth_ll(void * v,int n,int m)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
fill_sawtooth_double(void * v,int n,int m)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
fill_random_i(void * v,int n,int m)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
fill_random_ll(void * v,int n,int m)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
fill_random_double(void * v,int n,int m)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
fill_stagger_i(void * v,int n,int m)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
fill_stagger_ll(void * v,int n,int m)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
fill_stagger_double(void * v,int n,int m)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
fill_plateau_i(void * v,int n,int m)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
fill_plateau_ll(void * v,int n,int m)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
fill_plateau_double(void * v,int n,int m)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
fill_shuffle_i(void * v,int n,int m)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
fill_shuffle_ll(void * v,int n,int m)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
fill_shuffle_double(void * v,int n,int m)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
fill_bsd_killer_i(void * v,int n,int m)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
fill_bsd_killer_ll(void * v,int n,int m)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
fill_bsd_killer_double(void * v,int n,int m)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
fill_med3_killer_i(void * v,int n,int m)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
fill_med3_killer_ll(void * v,int n,int m)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
fill_med3_killer_double(void * v,int n,int m)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
print_timing(struct test_distribution * d,char * sub,int m,int n,double elapsed)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
do_test(struct test_distribution * d,char * sub,int m,int n,size_t es,void * y,void * z)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
test_perturbed_i(struct test_distribution * d,int n,void * vx,void * vy,void * vz)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
test_perturbed_ll(struct test_distribution * d,int n,void * vx,void * vy,void * vz)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
test_perturbed_double(struct test_distribution * d,int n,void * vx,void * vy,void * vz)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
test_simple_i(struct test_distribution * d,int n,void * vx,void * vy,void * vz)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
test_simple_ll(struct test_distribution * d,int n,void * vx,void * vy,void * vz)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
test_simple_double(struct test_distribution * d,int n,void * vx,void * vy,void * vz)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
test_antiqsort(struct test_distribution * d,int n,void * vx,void * vy,void * vz)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
run_tests(int n,const char * name)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
usage(void)721 usage(void)
722 {
723 fprintf(stderr, "usage: qsort_test [-dvt] [-n test_name] [num ...]\n");
724 exit(1);
725 }
726
727 int
main(int argc,char * argv[])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