[PATCH v12 1/3] lib: Add strongly typed 64bit int_sqrt

[PATCH v12 1/3] lib: Add strongly typed 64bit int_sqrt

[Crt Mori]

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(+)

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
-- 
2.15.0

Re: [PATCH v12 1/3] lib: Add strongly typed 64bit int_sqrt

[Joe Perches]

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

Re: [PATCH v12 1/3] lib: Add strongly typed 64bit int_sqrt

[Joe Perches]

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

Re: [PATCH v12 1/3] lib: Add strongly typed 64bit int_sqrt

[Crt Mori]

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

Re: [PATCH v12 1/3] lib: Add strongly typed 64bit int_sqrt

[Crt Mori]

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

Re: [PATCH v12 1/3] lib: Add strongly typed 64bit int_sqrt

[Crt Mori]

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

Re: [PATCH v12 1/3] lib: Add strongly typed 64bit int_sqrt

[Joe Perches]

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>

Re: [PATCH v12 1/3] lib: Add strongly typed 64bit int_sqrt

[Joe Perches]

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>

Re: [PATCH v12 1/3] lib: Add strongly typed 64bit int_sqrt

[Jonathan Cameron]

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

>