diff options
| author |   millert <millert@openbsd.org> | 2017-05-17 20:28:35 +0000 |
|---|---|---|
| committer | millert <millert@openbsd.org> | 2017-05-17 20:28:35 +0000 |
| commit | 885ba15a9478d45a50efb5e5e21f21c254afe42b (patch) | |
| tree | e1e4263dabda25b671242a753e3119c4cae67463 /regress/lib/libc/qsort/qsort_test.c | |
| parent | Add "killer" input from "algorithmic complexity attacks and libc (diff) | |
| download | wireguard-openbsd-885ba15a9478d45a50efb5e5e21f21c254afe42b.tar.xz wireguard-openbsd-885ba15a9478d45a50efb5e5e21f21c254afe42b.zip | |
Approximate nlgn instead of using libm. The same approximation may
be used in qsort.c in a later commit.
Diffstat (limited to 'regress/lib/libc/qsort/qsort_test.c')
| -rw-r--r-- | regress/lib/libc/qsort/qsort_test.c | 14 |
1 files changed, 7 insertions, 7 deletions
diff --git a/regress/lib/libc/qsort/qsort_test.c b/regress/lib/libc/qsort/qsort_test.c index b23f3e61905..3b36eb06b49 100644 --- a/regress/lib/libc/qsort/qsort_test.c +++ b/regress/lib/libc/qsort/qsort_test.c @@ -18,7 +18,6 @@ #include <stdlib.h> #include <string.h> #include <setjmp.h> -#include <math.h> #include <err.h> /* @@ -235,16 +234,17 @@ run_tests(int m, int n) { int *x, *y, *z; int ret = 0; - double nlgn; + int idx, nlgn = 0; enum distribution dist; /* - * The expected number of compares is A * n * log2(n) - * where A is between 1 and 2. If A is greater than 1.5 - * we'll print a warning. If A is greater than 10 we - * abort the test since qsort has probably gone quadratic. + * We expect A*n*lg(n) compares where A is between 1 and 2. + * For A > 1.5, print a warning. + * For A > 10 abort the test since qsort has probably gone quadratic. */ - nlgn = n * log2(n); + for (idx = n - 1; idx > 0; idx >>= 1) + nlgn++; + nlgn *= n; max_compares = nlgn * 1.5; abrt_compares = nlgn * 10; |