lib: Add strongly typed 64bit int_sqrt
Subsystems (2)
PATCH v12 1/3 lib: Add strongly typed 64bit int_sqrt
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.
--- include/linux/kernel.h | 9 +++++++++ lib/int_sqrt.c | 32 ++++++++++++++++++++++++++++++++ 2 files changed, 41 insertions(+)
include/linux/kernel.h +9 -0
@@ -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;
lib/int_sqrt.c +32 -0
@@ -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
Signature · 1 line
2.15.0
Quoted 5 lines · Crt Mori
There is no option to perform 64bit integer sqrt on 32bit platform. Added stronger typed
int_sqrt64enables the 64bit calculations to be performed on 32bit platforms. Using same algorithm asint_sqrt()with strong typing provides enough precision also on 32bit platforms, but it sacrifices some performance.
[]
lib/int_sqrt.c
Quoted 1 line
lib/int_sqrt.c +0
-0
[]
Quoted 8 lines
lib/int_sqrt.c +4
-0@@ -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
lib/int_sqrt.c unsigned long int_sqrt(unsigned long x) · line 53
Quoted 10 lines
lib/int_sqrt.c +10
-0+* 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.
Quoted 17 lines
lib/int_sqrt.c +17
-0+ + 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
Quoted 30 lines · Joe Perches
Quoted 5 lines · Crt Mori
There is no option to perform 64bit integer sqrt on 32bit platform. Added stronger typed
int_sqrt64enables the 64bit calculations to be performed on 32bit platforms. Using same algorithm asint_sqrt()with strong typing provides enough precision also on 32bit platforms, but it sacrifices some performance.[]
lib/int_sqrt.c
Quoted 1 line
lib/int_sqrt.c +0
-0[]
Quoted 8 lines
lib/int_sqrt.c +4
-0@@ -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 lib/int_sqrt.c unsigned long int_sqrt(unsigned long x) · line 53
Quoted 10 lines
lib/int_sqrt.c +10
-0+* 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:
Quoted 6 lines
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?
Quoted 17 lines
Quoted 17 lines
lib/int_sqrt.c +17
-0+ + 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
Quoted 34 lines · Crt Mori
Quoted 33 lines · Joe Perches
Quoted 5 lines · Crt Mori
There is no option to perform 64bit integer sqrt on 32bit platform. Added stronger typed
int_sqrt64enables the 64bit calculations to be performed on 32bit platforms. Using same algorithm asint_sqrt()with strong typing provides enough precision also on 32bit platforms, but it sacrifices some performance.[]
lib/int_sqrt.c
Quoted 1 line
lib/int_sqrt.c +0
-0[]
Quoted 8 lines
lib/int_sqrt.c +4
-0@@ -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 lib/int_sqrt.c unsigned long int_sqrt(unsigned long x) · line 53
Quoted 10 lines
lib/int_sqrt.c +10
-0+* 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);
Quoted 9 lines
Quoted 3 lines
to reduce the loop cost below when the
value is small enough.In existing
int_sqrtits only 1 and I assume that is more to protect from loop execution with 0 or 1. Since there is no difference (except fls64) withint_sqrtI 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.
Quoted 17 lines
Quoted 17 lines
Quoted 17 lines
lib/int_sqrt.c +17
-0+ + 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
Quoted 45 lines · Crt Mori
Quoted 34 lines · Crt Mori
Quoted 33 lines · Joe Perches
Quoted 5 lines · Crt Mori
There is no option to perform 64bit integer sqrt on 32bit platform. Added stronger typed
int_sqrt64enables the 64bit calculations to be performed on 32bit platforms. Using same algorithm asint_sqrt()with strong typing provides enough precision also on 32bit platforms, but it sacrifices some performance.[]
lib/int_sqrt.c
Quoted 1 line
lib/int_sqrt.c +0
-0[]
Quoted 8 lines
lib/int_sqrt.c +4
-0@@ -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 lib/int_sqrt.c unsigned long int_sqrt(unsigned long x) · line 53
Quoted 10 lines
lib/int_sqrt.c +10
-0+* 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);Quoted 9 lines
Quoted 3 lines
to reduce the loop cost below when the
value is small enough.In existing
int_sqrtits only 1 and I assume that is more to protect from loop execution with 0 or 1. Since there is no difference (except fls64) withint_sqrtI assume there is no need to call it to avoid loop?
Quoted 5 lines
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);Quoted 17 lines
Quoted 17 lines
Quoted 17 lines
Quoted 17 lines
lib/int_sqrt.c +17
-0+ + 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
Joe Perches
Acked-byQuoted 4 lines · Crt Mori
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:
Jonathan Cameron
maintainerQuoted 10 lines · On Mon, 15 Jan 2018 02:36:15 -0800 Joe Perches <[email protected]> wrote:
Quoted 4 lines · Crt Mori
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 <[email protected]>
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