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 --- libbb/isqrt.c | 58 +++++++++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 55 insertions(+), 3 deletions(-) (limited to 'libbb') 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