| Message ID | 20180109151847.30258-1-cmo@melexis.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
On Tue, 2018-01-09 at 16:18 +0100, Crt Mori wrote: > There is no option to perform 64bit integer sqrt on 32bit platform. > Added stronger typed int_sqrt64 enables the 64bit calculations to > be performed on 32bit platforms. Using same algorithm as int_sqrt() > with strong typing provides enough precision also on 32bit platforms, > but it sacrifices some performance. [] > diff --git a/lib/int_sqrt.c b/lib/int_sqrt.c [] > @@ -36,3 +37,34 @@ unsigned long int_sqrt(unsigned long x) > return y; > } > EXPORT_SYMBOL(int_sqrt); > + > +#if BITS_PER_LONG < 64 > +/** > + * int_sqrt64 - strongly typed int_sqrt function when minimum 64 bit input > + * is expected. > + * @x: 64bit integer of which to calculate the sqrt > + */ > +u32 int_sqrt64(u64 x) > +{ > + u64 b, m; > + u32 y = 0; > + > + if (x <= 1) > + return x; I think this should instead be: if (x <= INT_MAX) return int_sqrt((int)x); to reduce the loop cost below when the value is small enough. > + > + m = 1ULL << (fls64(x) & ~1ULL); > + while (m != 0) { > + b = y + m; > + y >>= 1; > + > + if (x >= b) { > + x -= b; > + y += m; > + } > + m >>= 2; > + } > + > + return y; > +} > +EXPORT_SYMBOL(int_sqrt64); > +#endif -- To unsubscribe from this list: send the line "unsubscribe linux-iio" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 9 January 2018 at 20:23, Joe Perches <joe@perches.com> wrote: > On Tue, 2018-01-09 at 16:18 +0100, Crt Mori wrote: >> There is no option to perform 64bit integer sqrt on 32bit platform. >> Added stronger typed int_sqrt64 enables the 64bit calculations to >> be performed on 32bit platforms. Using same algorithm as int_sqrt() >> with strong typing provides enough precision also on 32bit platforms, >> but it sacrifices some performance. > [] >> diff --git a/lib/int_sqrt.c b/lib/int_sqrt.c > [] >> @@ -36,3 +37,34 @@ unsigned long int_sqrt(unsigned long x) >> return y; >> } >> EXPORT_SYMBOL(int_sqrt); >> + >> +#if BITS_PER_LONG < 64 >> +/** >> + * int_sqrt64 - strongly typed int_sqrt function when minimum 64 bit input >> + * is expected. >> + * @x: 64bit integer of which to calculate the sqrt >> + */ >> +u32 int_sqrt64(u64 x) >> +{ >> + u64 b, m; >> + u32 y = 0; >> + >> + if (x <= 1) >> + return x; > > I think this should instead be: > > if (x <= INT_MAX) > return int_sqrt((int)x); > > to reduce the loop cost below when the > value is small enough. > In existing int_sqrt its only 1 and I assume that is more to protect from loop execution with 0 or 1. Since there is no difference (except fls64) with int_sqrt I assume there is no need to call it to avoid loop? >> + >> + m = 1ULL << (fls64(x) & ~1ULL); >> + while (m != 0) { >> + b = y + m; >> + y >>= 1; >> + >> + if (x >= b) { >> + x -= b; >> + y += m; >> + } >> + m >>= 2; >> + } >> + >> + return y; >> +} >> +EXPORT_SYMBOL(int_sqrt64); >> +#endif -- To unsubscribe from this list: send the line "unsubscribe linux-iio" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 10 January 2018 at 09:15, Crt Mori <cmo@melexis.com> wrote: > On 9 January 2018 at 20:23, Joe Perches <joe@perches.com> wrote: >> On Tue, 2018-01-09 at 16:18 +0100, Crt Mori wrote: >>> There is no option to perform 64bit integer sqrt on 32bit platform. >>> Added stronger typed int_sqrt64 enables the 64bit calculations to >>> be performed on 32bit platforms. Using same algorithm as int_sqrt() >>> with strong typing provides enough precision also on 32bit platforms, >>> but it sacrifices some performance. >> [] >>> diff --git a/lib/int_sqrt.c b/lib/int_sqrt.c >> [] >>> @@ -36,3 +37,34 @@ unsigned long int_sqrt(unsigned long x) >>> return y; >>> } >>> EXPORT_SYMBOL(int_sqrt); >>> + >>> +#if BITS_PER_LONG < 64 >>> +/** >>> + * int_sqrt64 - strongly typed int_sqrt function when minimum 64 bit input >>> + * is expected. >>> + * @x: 64bit integer of which to calculate the sqrt >>> + */ >>> +u32 int_sqrt64(u64 x) >>> +{ >>> + u64 b, m; >>> + u32 y = 0; >>> + >>> + if (x <= 1) >>> + return x; >> >> I think this should instead be: >> >> if (x <= INT_MAX) >> return int_sqrt((int)x); >> >> to reduce the loop cost below when the >> value is small enough. >> > > In existing int_sqrt its only 1 and I assume that is more to protect > from loop execution with 0 or 1. Since there is no difference (except > fls64) with int_sqrt I assume there is no need to call it to avoid > loop? > Nevermind, I see what you mean (should have thought longer before I written). The cost of below loop is because of 64bit calculation is not native on 32bit and we could just use 32bit calculation in that loop. Will send v13 with a fix for this. >>> + >>> + m = 1ULL << (fls64(x) & ~1ULL); >>> + while (m != 0) { >>> + b = y + m; >>> + y >>= 1; >>> + >>> + if (x >= b) { >>> + x -= b; >>> + y += m; >>> + } >>> + m >>= 2; >>> + } >>> + >>> + return y; >>> +} >>> +EXPORT_SYMBOL(int_sqrt64); >>> +#endif -- To unsubscribe from this list: send the line "unsubscribe linux-iio" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 10 January 2018 at 09:33, Crt Mori <cmo@melexis.com> wrote: > On 10 January 2018 at 09:15, Crt Mori <cmo@melexis.com> wrote: >> On 9 January 2018 at 20:23, Joe Perches <joe@perches.com> wrote: >>> On Tue, 2018-01-09 at 16:18 +0100, Crt Mori wrote: >>>> There is no option to perform 64bit integer sqrt on 32bit platform. >>>> Added stronger typed int_sqrt64 enables the 64bit calculations to >>>> be performed on 32bit platforms. Using same algorithm as int_sqrt() >>>> with strong typing provides enough precision also on 32bit platforms, >>>> but it sacrifices some performance. >>> [] >>>> diff --git a/lib/int_sqrt.c b/lib/int_sqrt.c >>> [] >>>> @@ -36,3 +37,34 @@ unsigned long int_sqrt(unsigned long x) >>>> return y; >>>> } >>>> EXPORT_SYMBOL(int_sqrt); >>>> + >>>> +#if BITS_PER_LONG < 64 >>>> +/** >>>> + * int_sqrt64 - strongly typed int_sqrt function when minimum 64 bit input >>>> + * is expected. >>>> + * @x: 64bit integer of which to calculate the sqrt >>>> + */ >>>> +u32 int_sqrt64(u64 x) >>>> +{ >>>> + u64 b, m; >>>> + u32 y = 0; >>>> + >>>> + if (x <= 1) >>>> + return x; >>> >>> I think this should instead be: >>> >>> if (x <= INT_MAX) >>> return int_sqrt((int)x); >>> >>> to reduce the loop cost below when the >>> value is small enough. >>> >> >> In existing int_sqrt its only 1 and I assume that is more to protect >> from loop execution with 0 or 1. Since there is no difference (except >> fls64) with int_sqrt I assume there is no need to call it to avoid >> loop? >> > > Nevermind, I see what you mean (should have thought longer before I > written). The cost of below loop is because of 64bit calculation is > not native on 32bit and we could just use 32bit calculation in that > loop. Will send v13 with a fix for this. > Shouldn't I rather make it if (x <= ULONG_MAX) return int_sqrt((unsigned long) x); >>>> + >>>> + m = 1ULL << (fls64(x) & ~1ULL); >>>> + while (m != 0) { >>>> + b = y + m; >>>> + y >>= 1; >>>> + >>>> + if (x >= b) { >>>> + x -= b; >>>> + y += m; >>>> + } >>>> + m >>= 2; >>>> + } >>>> + >>>> + return y; >>>> +} >>>> +EXPORT_SYMBOL(int_sqrt64); >>>> +#endif -- To unsubscribe from this list: send the line "unsubscribe linux-iio" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Wed, 2018-01-10 at 09:37 +0100, Crt Mori wrote: > Shouldn't I rather make it > > if (x <= ULONG_MAX) > return int_sqrt((unsigned long) x); With this change: (I believe done in v13) and as requested by Crt Mori in a private email: Acked-by: Joe Perches <joe@perches.com> -- To unsubscribe from this list: send the line "unsubscribe linux-iio" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Mon, 15 Jan 2018 02:36:15 -0800 Joe Perches <joe@perches.com> wrote: > On Wed, 2018-01-10 at 09:37 +0100, Crt Mori wrote: > > Shouldn't I rather make it > > > > if (x <= ULONG_MAX) > > return int_sqrt((unsigned long) x); > > With this change: (I believe done in v13) and > as requested by Crt Mori in a private email: > > Acked-by: Joe Perches <joe@perches.com> Thanks Joe, I've applied v13 which indeed does have this change. Applied to the togreg branch of iio.git where it will sit until after the merge window. For now I'll only be pushing that out as a build test branch so still time for improvements without having to revert or anything. Thanks, Jonathan > -- To unsubscribe from this list: send the line "unsubscribe linux-iio" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/include/linux/kernel.h b/include/linux/kernel.h index 0ad4c3044cf9..e4a3dc64e650 100644 --- a/include/linux/kernel.h +++ b/include/linux/kernel.h @@ -460,6 +460,15 @@ extern int func_ptr_is_kernel_text(void *ptr); unsigned long int_sqrt(unsigned long); +#if BITS_PER_LONG < 64 +u32 int_sqrt64(u64 x); +#else +static inline u32 int_sqrt64(u64 x) +{ + return (u32)int_sqrt(x); +} +#endif + extern void bust_spinlocks(int yes); extern int oops_in_progress; /* If set, an oops, panic(), BUG() or die() is in progress */ extern int panic_timeout; diff --git a/lib/int_sqrt.c b/lib/int_sqrt.c index 1ef4cc344977..737fca54bb02 100644 --- a/lib/int_sqrt.c +++ b/lib/int_sqrt.c @@ -7,6 +7,7 @@ #include <linux/kernel.h> #include <linux/export.h> +#include <linux/bitops.h> /** * int_sqrt - rough approximation to sqrt @@ -36,3 +37,34 @@ unsigned long int_sqrt(unsigned long x) return y; } EXPORT_SYMBOL(int_sqrt); + +#if BITS_PER_LONG < 64 +/** + * int_sqrt64 - strongly typed int_sqrt function when minimum 64 bit input + * is expected. + * @x: 64bit integer of which to calculate the sqrt + */ +u32 int_sqrt64(u64 x) +{ + u64 b, m; + u32 y = 0; + + if (x <= 1) + return x; + + m = 1ULL << (fls64(x) & ~1ULL); + while (m != 0) { + b = y + m; + y >>= 1; + + if (x >= b) { + x -= b; + y += m; + } + m >>= 2; + } + + return y; +} +EXPORT_SYMBOL(int_sqrt64); +#endif
There is no option to perform 64bit integer sqrt on 32bit platform. Added stronger typed int_sqrt64 enables the 64bit calculations to be performed on 32bit platforms. Using same algorithm as int_sqrt() with strong typing provides enough precision also on 32bit platforms, but it sacrifices some performance. Signed-off-by: Crt Mori <cmo@melexis.com> --- include/linux/kernel.h | 9 +++++++++ lib/int_sqrt.c | 32 ++++++++++++++++++++++++++++++++ 2 files changed, 41 insertions(+)