lib: Add strongly typed 64bit int_sqrt
Subsystems (2)
PATCH v13 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. In case values are smaller than ULONG_MAX the standard int_sqrt is used for calculation to maximize the performance due to more native calculations.
--- include/linux/kernel.h | 9 +++++++++ lib/int_sqrt.c | 31 +++++++++++++++++++++++++++++++ 2 files changed, 40 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 +31 -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,33 @@ 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, y =0 ; + +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
Signature · 1 line
2.15.0
Jonathan Cameron
maintainerQuoted 9 lines · On Thu, 11 Jan 2018 11:19:57 +0100 Crt Mori <[email protected]> wrote:
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. In case values are smaller thanULONG_MAXthe standardint_sqrtis used for calculation to maximize the performance due to more native calculations.Signed-off-by Crt Mori <[email protected]>
Applied to the togreg branch of iio.git and pushed out as testing for the autobuilders to play with it.
Thanks all for input on this and to Crt for persistence!
Jonathan
Quoted 71 lines
--- include/linux/kernel.h | 9 +++++++++ lib/int_sqrt.c | 31 +++++++++++++++++++++++++++++++ 2 files changed, 40 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 +31
-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,33 @@ 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, y =0 ; + +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