Skip to contentSkip to conversation

lib: Add strongly typed 64bit int_sqrt

PATCH Superseded Crt Mori 3 participants 7 messages Jan 9, 2018 – Feb 4, 2018

Subsystems (2)

v12 of 13 Superseded Latest is v13 →

lore
Share & tools
lore

Crt Mori

author
#0 lore raw

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
index 0ad4c3044cf9..e4a3dc64e650 100644
@@ -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
index 1ef4cc344977..737fca54bb02 100644
@@ -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
#1 lore raw
Quoted 5 lines · 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.

[]

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
author
#2 lore raw
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_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.

[]

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
author
#3 lore raw
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_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.

[]

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_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.

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
author
#4 lore raw
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_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.

[]

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_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 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
Acked-by
#5 lore raw
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:

maintainer
#6 lore raw
Quoted 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:

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

Quoted 1 line