From: Florian La Roche <florian.laroche@googlemail.com>
To: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Will Deacon <will.deacon@arm.com>,
Linux List Kernel Mailing <linux-kernel@vger.kernel.org>,
Crt Mori <cmo@melexis.com>, Joe Perches <joe@perches.com>,
Davidlohr Bueso <dave@stgolabs.net>,
Peter Zijlstra <peterz@infradead.org>
Subject: Re: fix int_sqrt() for very large numbers
Date: Sun, 20 Jan 2019 06:03:17 +0100 [thread overview]
Message-ID: <CANZrA2YLtnv+PRBYzcLdFUg4uktx82G8dkoZCic8-ANK-3-7fA@mail.gmail.com> (raw)
In-Reply-To: <CAHk-=wjKgJ-9ypvzq+CB_NKnRk6iAqFtgVPwSH17C5RqJoYF=A@mail.gmail.com>
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
<torvalds@linux-foundation.org>:
> 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
> users that care.
Right. No real bug, just not 100% correct code.
> And as Will mentioned, the regular int_sqrt() looks perfectly fine,
> and subtracting 1 from the __fls() return value would actually
> _introduce_ a bug.
I think no bug introduced as the code handling 0 and 1 is already done.
For __fls() and fls64() I am actually using the folloing code:
/*
* fls - find last (most-significant) bit set
* Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32.
*/
static __always_inline unsigned int flsl(unsigned long x)
{
return x ? sizeof(x) * 8 - __builtin_clzl(x) : 0;
}
Please note the "_builtin_clzl()" instead of the "_builtin_clz()".
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.
best regards,
Florian La Roche
next prev parent reply other threads:[~2019-01-20 5:10 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
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 [this message]
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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CANZrA2YLtnv+PRBYzcLdFUg4uktx82G8dkoZCic8-ANK-3-7fA@mail.gmail.com \
--to=florian.laroche@googlemail.com \
--cc=cmo@melexis.com \
--cc=dave@stgolabs.net \
--cc=joe@perches.com \
--cc=linux-kernel@vger.kernel.org \
--cc=peterz@infradead.org \
--cc=torvalds@linux-foundation.org \
--cc=will.deacon@arm.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).