Re: fix int_sqrt() for very large numbers

2019-01-21 Thread Crt Mori
On Mon, 21 Jan 2019 at 01:20, Linus Torvalds wrote: > > On Sun, Jan 20, 2019 at 4:15 AM Florian La Roche > wrote: > > > > @@ -52,7 +52,7 @@ u32 int_sqrt64(u64 x) > > if (x <= ULONG_MAX) > > return int_sqrt((unsigned long) x); > > > > - m = 1ULL << (fls64(x) & ~1ULL);

Re: fix int_sqrt() for very large numbers

2019-01-20 Thread Linus Torvalds
On Sun, Jan 20, 2019 at 4:15 AM Florian La Roche wrote: > > @@ -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); I've applied this par

Re: fix int_sqrt() for very large numbers

2019-01-20 Thread Linus Torvalds
On Sun, Jan 20, 2019 at 9:30 PM Crt Mori wrote: > > I have just re-read the patch submit discussion and a sqrt of 64bit > number can never be more than 32bit. That is why u32 return value is > enough. Right. And that's exactly why I thought it was so odd how the mlx90632.c driver - which is the o

Re: fix int_sqrt() for very large numbers

2019-01-20 Thread Crt Mori
On Sun, 20 Jan 2019 at 09:31, Crt Mori wrote: > > On Sun, 20 Jan 2019 at 04:49, Linus Torvalds > wrote: > > > > On Sun, Jan 20, 2019 at 12:01 PM Will Deacon wrote: > > > > > > > @@ -52,7 +52,7 @@ u32 int_sqrt64(u64 x) > > > > if (x <= ULONG_MAX) > > > > return int_sqrt((unsig

Re: fix int_sqrt() for very large numbers

2019-01-20 Thread Crt Mori
On Sun, 20 Jan 2019 at 04:49, Linus Torvalds wrote: > > On Sun, Jan 20, 2019 at 12:01 PM Will Deacon wrote: > > > > > @@ -52,7 +52,7 @@ u32 int_sqrt64(u64 x) > > > if (x <= ULONG_MAX) > > > return int_sqrt((unsigned long) x); > > > > > > - m = 1ULL << (fls64(x) & ~1ULL); >

Re: fix int_sqrt() for very large numbers

2019-01-19 Thread Linus Torvalds
On Sun, Jan 20, 2019 at 5:03 PM Florian La Roche wrote: > > The real bug is that we compute 1 to 64 for bit 0 to bit 63, whereas > the algorithm expects 0 to 63 for the value of m. Florian, you seem to be in denial. __fls() returns 0-63. Your patch is *wrong* for the __fls() use, because when yo

Re: fix int_sqrt() for very large numbers

2019-01-19 Thread Florian La Roche
Hello all, my comment said ffs(), but the code only uses fls() and that's what I meant. Am So., 20. Jan. 2019 um 04:49 Uhr schrieb Linus Torvalds : > But yes, our current int_sqrt64() does seem buggy as-is, because it's > *supposed* to work on u64's, even if I don't think we really have any > us

Re: fix int_sqrt() for very large numbers

2019-01-19 Thread Linus Torvalds
On Sun, Jan 20, 2019 at 12:01 PM Will Deacon wrote: > > > @@ -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); > > This just looks li

Re: fix int_sqrt() for very large numbers

2019-01-19 Thread Will Deacon
On Sat, Jan 19, 2019 at 04:14:50PM +0100, Florian La Roche wrote: > 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. This is confusing, because the patch doesn't go near an __ffs(). > Just subtracting 1 is an

fix int_sqrt() for very large numbers

2019-01-19 Thread 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, Floria