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