8a134ec68
Denys Vlasenko
2017-04-11
Subject
libbb: move isqrt from factor, use it in diff too
Binary
No binary (build failed)
Architecture & Compiler Flags
—
Build Log
(log yok)
Commit Diff GitHub →
coreutils/factor.c+1 -18
| @@ -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: */ | |
editors/diff.c+0 -11
| @@ -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); | |
include/libbb.h+2 -0
| @@ -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; | |
libbb/isqrt.c+60 -0
| @@ -0,0 +1,60 @@ | |
| + | /* |
| + | * Copyright (C) 2017 Denys Vlasenko <[email protected]> |
| + | * |
| + | * 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 |