From e33bd4aaa2d6558fc1b008cd2e3bcc5c4f392be2 Mon Sep 17 00:00:00 2001 From: Denys Vlasenko Date: Wed, 4 Feb 2026 19:41:41 +0100 Subject: libbb: use narrow isqrt() when 64-bit one is not needed (only "factor" uses it) function old new delta isqrt_ull - 84 +84 create_J 1809 1808 -1 isqrt 106 38 -68 ------------------------------------------------------------------------------ (add/remove: 1/0 grow/shrink: 0/2 up/down: 84/-69) Total: 15 bytes Signed-off-by: Denys Vlasenko --- coreutils/factor.c | 2 +- include/libbb.h | 7 ++++++- libbb/isqrt.c | 58 +++++++++++++++++++++++++++++++++++++++++++++++++++--- 3 files changed, 62 insertions(+), 5 deletions(-) diff --git a/coreutils/factor.c b/coreutils/factor.c index 90e9ed761..4df523f28 100644 --- a/coreutils/factor.c +++ b/coreutils/factor.c @@ -136,7 +136,7 @@ static void factorize(wide_t N); static half_t isqrt_odd(wide_t N) { - half_t s = isqrt(N); + half_t s = isqrt_ull(N); /* s^2 is <= N, (s+1)^2 > N */ /* If s^2 in fact is EQUAL to N, it's very lucky. diff --git a/include/libbb.h b/include/libbb.h index aacff42ee..7cca925b9 100644 --- a/include/libbb.h +++ b/include/libbb.h @@ -408,7 +408,12 @@ unsigned FAST_FUNC bb_popcnt_long(unsigned long m); #define bb_popcnt_long(m) bb_popcnt_32(m) #endif -unsigned long FAST_FUNC isqrt(unsigned long long N); +unsigned FAST_FUNC isqrt(unsigned long N); +#if LLONG_MAX > LONG_MAX +unsigned long FAST_FUNC isqrt_ull(unsigned long long N); +#else +# define isqrt_ull(N) isqrt(N) +#endif unsigned long long monotonic_ns(void) FAST_FUNC; unsigned long long monotonic_us(void) FAST_FUNC; diff --git a/libbb/isqrt.c b/libbb/isqrt.c index 817b7d036..507c7d637 100644 --- a/libbb/isqrt.c +++ b/libbb/isqrt.c @@ -9,15 +9,42 @@ #ifndef ISQRT_TEST # include "libbb.h" #else -/* gcc -DISQRT_TEST -Wall -O2 isqrt.c -oisqrt && ./isqrt $((RANDOM*RANDOM)) */ +// gcc -DISQRT_TEST -Wall -Os -ffunction-sections isqrt.c -S -fverbose-asm +// gcc -DISQRT_TEST -Wall -Os -ffunction-sections isqrt.c -c +// gcc -DISQRT_TEST -Wall -Os -ffunction-sections isqrt.c -oisqrt && ./isqrt $((RANDOM*RANDOM)) # include # include # include +# include # define FAST_FUNC /* nothing */ #endif /* Returns such x that x+1 > sqrt(N) */ -unsigned long FAST_FUNC isqrt(unsigned long long N) + +/* Stolen from kernel code */ +unsigned FAST_FUNC isqrt(unsigned long x) +{ + unsigned long y = 0; + unsigned long m = 1UL << (8*sizeof(x) - 2); + // ^^^^^ should be m = 1UL << ((fls(x) - 1) & ~1UL); + // but calculating fls() would take time and code + + do { + unsigned long b = y + m; + y >>= 1; + if (x >= b) { + x -= b; + y += m; + } + m >>= 2; + } while (m); + return y; +} + +#if LLONG_MAX > LONG_MAX +# if defined(i386) +/* Smaller code on this register-starved arch */ +unsigned long FAST_FUNC isqrt_ull(unsigned long long N) { unsigned long x; unsigned shift; @@ -33,15 +60,40 @@ unsigned long FAST_FUNC isqrt(unsigned long long N) } while ((int)shift >= 0); return x; } +# else +/* Stolen from kernel code */ +unsigned long FAST_FUNC isqrt_ull(unsigned long long x) +{ + unsigned long long y = 0; + unsigned long long m = 1ULL << (8*sizeof(x) - 2); + // ^^^^^ should be m = 1ULL << ((fls(x) - 1) & ~1ULL); + // but calculating fls() would take time and code + + do { + unsigned long long b = y + m; + y >>= 1; + if (x >= b) { + x -= b; + y += m; + } + m >>= 2; + } while (m); + return y; +} +# endif +#endif /* wide version needed */ #ifdef ISQRT_TEST +# if LLONG_MAX == LONG_MAX +# define isqrt_ull(N) isqrt(N) +# endif 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); + h = isqrt_ull(n); if (!(n & 0xffff)) printf("isqrt(%llx)=%lx\n", n, h); if ((unsigned long long)h * h > n) { -- cgit v1.2.3-55-g6feb