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 | |
| 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.
| -rw-r--r-- | regress/lib/libc/qsort/Makefile | 4 | ||||
| -rw-r--r-- | regress/lib/libc/qsort/qsort_test.c | 14 |
2 files changed, 8 insertions, 10 deletions
diff --git a/regress/lib/libc/qsort/Makefile b/regress/lib/libc/qsort/Makefile index d3c4e2baa22..9062e26f956 100644 --- a/regress/lib/libc/qsort/Makefile +++ b/regress/lib/libc/qsort/Makefile @@ -1,9 +1,7 @@ -# $OpenBSD: Makefile,v 1.1 2017/05/17 14:47:06 millert Exp $ +# $OpenBSD: Makefile,v 1.2 2017/05/17 20:28:35 millert Exp $ PROG= qsort_test CFLAGS+=-Wall -LDADD+= -lm -DPADD+= ${LIBM} qsort-regress: ${PROG} ./${PROG} 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; |