diff options
| -rw-r--r-- | coreutils/factor.c | 19 | ||||
| -rw-r--r-- | editors/diff.c | 11 | ||||
| -rw-r--r-- | include/libbb.h | 2 | ||||
| -rw-r--r-- | libbb/isqrt.c | 60 |
4 files changed, 63 insertions, 29 deletions
diff --git a/coreutils/factor.c b/coreutils/factor.c index f910fdb44..11cc04f92 100644 --- a/coreutils/factor.c +++ b/coreutils/factor.c @@ -44,24 +44,7 @@ typedef unsigned long half_t; #error Cant find an integer type which is half as wide as ullong #endif -/* Returns such x that x+1 > sqrt(N) */ -static inline half_t isqrt(wide_t N) -{ - half_t x; - unsigned shift; - - shift = WIDE_BITS - 2; - x = 0; - do { - x = (x << 1) + 1; - if ((wide_t)x * x > (N >> shift)) - x--; /* whoops, that +1 was too much */ - shift -= 2; - } while ((int)shift >= 0); - return x; -} - -static NOINLINE half_t isqrt_odd(wide_t N) +static half_t isqrt_odd(wide_t N) { half_t s = isqrt(N); /* Subtract 1 from even s, odd s won't change: */ diff --git a/editors/diff.c b/editors/diff.c index 0eb825cfb..3304edb26 100644 --- a/editors/diff.c +++ b/editors/diff.c @@ -295,17 +295,6 @@ static int search(const int *c, int k, int y, const struct cand *list) } } -static unsigned isqrt(unsigned n) -{ - unsigned x = 1; - while (1) { - const unsigned y = x; - x = ((n / x) + x) >> 1; - if (x <= (y + 1) && x >= (y - 1)) - return x; - } -} - static void stone(const int *a, int n, const int *b, int *J, int pref) { const unsigned isq = isqrt(n); diff --git a/include/libbb.h b/include/libbb.h index a2c699b54..04071639a 100644 --- a/include/libbb.h +++ b/include/libbb.h @@ -342,6 +342,8 @@ extern int *const bb_errno; uint64_t bb_bswap_64(uint64_t x) FAST_FUNC; #endif +unsigned long FAST_FUNC isqrt(unsigned long long N); + unsigned long long monotonic_ns(void) FAST_FUNC; unsigned long long monotonic_us(void) FAST_FUNC; unsigned long long monotonic_ms(void) FAST_FUNC; diff --git a/libbb/isqrt.c b/libbb/isqrt.c new file mode 100644 index 000000000..817b7d036 --- /dev/null +++ b/libbb/isqrt.c @@ -0,0 +1,60 @@ +/* + * Copyright (C) 2017 Denys Vlasenko <vda.linux@googlemail.com> + * + * Licensed under GPLv2, see file LICENSE in this source tree. + */ + +//kbuild:lib-y += isqrt.o + +#ifndef ISQRT_TEST +# include "libbb.h" +#else +/* gcc -DISQRT_TEST -Wall -O2 isqrt.c -oisqrt && ./isqrt $((RANDOM*RANDOM)) */ +# include <stdlib.h> +# include <stdio.h> +# include <time.h> +# define FAST_FUNC /* nothing */ +#endif + +/* Returns such x that x+1 > sqrt(N) */ +unsigned long FAST_FUNC isqrt(unsigned long long N) +{ + unsigned long x; + unsigned shift; +#define LL_WIDTH_BITS (unsigned)(sizeof(N)*8) + + shift = LL_WIDTH_BITS - 2; + x = 0; + do { + x = (x << 1) + 1; + if ((unsigned long long)x * x > (N >> shift)) + x--; /* whoops, that +1 was too much */ + shift -= 2; + } while ((int)shift >= 0); + return x; +} + +#ifdef ISQRT_TEST +int main(int argc, char **argv) +{ + unsigned long long n = argv[1] ? strtoull(argv[1], NULL, 0) : time(NULL); + for (;;) { + unsigned long h; + n--; + h = isqrt(n); + if (!(n & 0xffff)) + printf("isqrt(%llx)=%lx\n", n, h); + if ((unsigned long long)h * h > n) { + printf("BAD1: isqrt(%llx)=%lx\n", n, h); + return 1; + } + h++; + if ((unsigned long long)h * h != 0 /* this can overflow to 0 - not a bug */ + && (unsigned long long)h * h <= n) + { + printf("BAD2: isqrt(%llx)=%lx\n", n, h); + return 1; + } + } +} +#endif |