linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* fix int_sqrt() for very large numbers
@ 2019-01-19 15:14 Florian La Roche
  2019-01-20  0:01 ` Will Deacon
                   ` (2 more replies)
  0 siblings, 3 replies; 12+ messages in thread
From: Florian La Roche @ 2019-01-19 15:14 UTC (permalink / raw)
  To: linux-kernel
  Cc: Crt Mori, Joe Perches, Davidlohr Bueso, Will Deacon,
	Peter Zijlstra, Linus Torvalds, Florian La Roche

If an input number x for int_sqrt() has the highest bit set, then
__ffs(x) is 64. (1UL << 64) is an overflow and breaks the algorithm.

Just subtracting 1 is an even better guess for the initial
value of m and that's what also used to be done in earlier
versions of this code.

best regards,

Florian La Roche

Signed-off-by: Florian La Roche <Florian.LaRoche@googlemail.com>
---
 lib/int_sqrt.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/lib/int_sqrt.c b/lib/int_sqrt.c
index 14436f4ca6bd..ea00e84dc272 100644
--- a/lib/int_sqrt.c
+++ b/lib/int_sqrt.c
@@ -23,7 +23,7 @@ unsigned long int_sqrt(unsigned long x)
 	if (x <= 1)
 		return x;
 
-	m = 1UL << (__fls(x) & ~1UL);
+	m = 1UL << ((__fls(x) - 1) & ~1UL);
 	while (m != 0) {
 		b = y + m;
 		y >>= 1;
@@ -52,7 +52,7 @@ u32 int_sqrt64(u64 x)
 	if (x <= ULONG_MAX)
 		return int_sqrt((unsigned long) x);
 
-	m = 1ULL << (fls64(x) & ~1ULL);
+	m = 1ULL << ((fls64(x) - 1) & ~1ULL);
 	while (m != 0) {
 		b = y + m;
 		y >>= 1;
-- 
2.17.1


^ permalink raw reply related	[flat|nested] 12+ messages in thread

end of thread, other threads:[~2019-02-02 13:11 UTC | newest]

Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-01-19 15:14 fix int_sqrt() for very large numbers Florian La Roche
2019-01-20  0:01 ` Will Deacon
2019-01-20  3:48   ` Linus Torvalds
2019-01-20  5:03     ` Florian La Roche
2019-01-20  5:11       ` Linus Torvalds
2019-01-20  8:31     ` Crt Mori
2019-01-20  9:29       ` Crt Mori
2019-01-20 10:00         ` Linus Torvalds
2019-01-21  0:20 ` Linus Torvalds
2019-01-21 20:25   ` Crt Mori
2019-02-02  6:11 ` [LKP] 32bd07585d: kernel_selftests.lib.prime_numbers.sh.fail kernel test robot
2019-02-02 13:10   ` Florian La Roche

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).