Skip to contentSkip to conversation

Make div64_u64() precise on 32bit platforms

PATCH Brian Behlendorf 3 participants 7 messages Oct 12, 2010 – Oct 21, 2010 Library code

lore
Share & tools
lore
#0 lore raw

I'm resending the patch as is and adding what I hope are the right CCs. Also let me explain why I opted to add abs64() and use the gcc builtin.

Quoted 1 line

Can't we just improve abs? Say,

I was reluctant to change abs() since it would have a much larger impact on the code base. Using typeof() should be OK but if any of the callers mistakenly call abs() with an unsigned value then we could see compiler warnings about '__x < 0' being a useless conditional.

Quoted 3 lines

This is a bit unusual. I mean, it is not that common to use gcc builtins in the normal code. And, it seems, we can use __fls(divisor >> 32) or just fls64() instead ?

I opted for the gcc builtin because I felt it made the code more readable. I also suspect it will perform slightly better than __fls() on some archs. For example, on powerpc __fls() in implemented using the 'cntlzw' instruction. It returns (BITS_PER_LONG - 1 - cntlzw) which is wasted work since my function would immediately undo this to get back cntlzw. If I was lucky the compiler would optimize this away for me but if I use the builtin I don't need to take the chance.

Signature · 2 lines
Thanks,
Brian Behlendorf
Quoted 1 line

From 3b30f1cf78f88b40360dd65816941cf2be9dd60d Mon Sep 17 00:00:00 2001

From: Brian Behlendorf <[email protected]>
Date: Thu, 5 Aug 2010 14:59:11 -0700
Subject: [PATCH] Fix div64_u64 for 32bit platforms

The current implementation of div64_u64 for 32bit systems returns an approximately correct result when the divisor exceeds 32bits. Since doing 64bit division using 32bit hardware is a long since solved problem we just use one of the existing proven methods.

Additionally, add a div64_s64 function to correctly handle doing signed 64bit division.

---
 include/linux/kernel.h |    5 +++
 include/linux/math64.h |   12 +++++++++
 lib/div64.c            |   64 +++++++++++++++++++++++++++++++++++++++--------
 3 files changed, 70 insertions(+), 11 deletions(-)
include/linux/kernel.h +5 -0
index 5de838b..7a00dff 100644
@@ -162,6 +162,11 @@ extern int _cond_resched(void);
 		(__x < 0) ? -__x : __x;		\
 	})
 
+#define abs64(x) ({				\
+		s64 __x = (x);			\
+		(__x < 0) ? -__x : __x;		\
+	})
+
 #ifdef CONFIG_PROVE_LOCKING
 void might_fault(void);
 #else
include/linux/math64.h +12 -0
index c87f152..23fcdfc 100644
@@ -35,6 +35,14 @@ static inline u64 div64_u64(u64 dividend, u64 divisor)
 	return dividend / divisor;
 }
 
+/**
+ * div64_s64 - signed 64bit divide with 64bit divisor
+ */
+static inline s64 div64_s64(s64 dividend, s64 divisor)
+{
+	return dividend / divisor;
+}
+
 #elif BITS_PER_LONG == 32
 
 #ifndef div_u64_rem
@@ -53,6 +61,10 @@ extern s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder);
 extern u64 div64_u64(u64 dividend, u64 divisor);
 #endif
 
+#ifndef div64_s64
+extern s64 div64_s64(s64 dividend, s64 divisor);
+#endif
+
 #endif /* BITS_PER_LONG */
 
 /**
lib/div64.c +53 -11

79 lines not on this page · raw message

Signature · 1 line
1.5.4.5

#include <linux/module.h>

/*
* Verification test for div64_u64.
*/

#ifndef abs64

#define abs64(x) ({			\
	s64 __x = (x);			\
	(__x < 0) ? -__x : __x;		\
})

#endif

int div64_u64_test(void)

{
	u64 uu, vu, qu, ru;
	int n, i, j, errors = 0;
	const u64 tabu[] = {
	    0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
	    10, 11, 12, 13, 14, 15, 16, 1000, 2003,
	    32765, 32766, 32767, 32768, 32769, 32760,
	    65533, 65534, 65535, 65536, 65537, 65538,
	    0x7ffffffeULL, 0x7fffffffULL, 0x80000000ULL, 0x80000001ULL,
	    0x7000000000000000ULL, 0x7000000080000000ULL, 0x7000000080000001ULL,
	    0x7fffffffffffffffULL, 0x7fffffff8fffffffULL, 0x7fffffff8ffffff1ULL,
	    0x7fffffff00000000ULL, 0x7fffffff80000000ULL, 0x7fffffff00000001ULL,
	    0x8000000000000000ULL, 0x8000000080000000ULL, 0x8000000080000001ULL,
	    0xc000000000000000ULL, 0xc000000080000000ULL, 0xc000000080000001ULL,
	    0xfffffffffffffffdULL, 0xfffffffffffffffeULL, 0xffffffffffffffffULL,
	};

	printk("%s", "Testing unsigned 64-bit division.\n");
	n = sizeof(tabu) / sizeof(tabu[0]);
	for (i = 0; i < n; i++) {
		for (j = 1; j < n; j++) {
			uu = tabu[i];
			vu = tabu[j];
			qu = div64_u64(uu, vu);
			ru = uu - qu * vu;
			if (qu > uu || ru >= vu) {
				printk("%016llx/%016llx != %016llx "
				   "rem %016llx\n", uu, vu, qu, ru);
				errors++;
			}
		}
	}

	if (errors) {
		printk("Failed %d/%d tests\n", errors, n * (n - 1));
	} else {
		printk("Passed all %d tests\n", n * (n - 1));
	}

	return 0;
}

void div64_u64_exit(void) { }

module_init(div64_u64_test);
module_exit(div64_u64_exit);

#include <linux/module.h>

/*
* Verification test for div64_s64.
*/

#ifndef abs64

#define abs64(x) ({			\
	s64 __x = (x);			\
	(__x < 0) ? -__x : __x;		\
})

#endif

int div64_s64_test(void)

{
	s64 u, v, q, r;
	int n, i, j, k, errors = 0;
	const s64 tabs[] = {
	    0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
	    10, 11, 12, 13, 14, 15, 16, 1000, 2003,
	    32765, 32766, 32767, 32768, 32769, 32760,
	    65533, 65534, 65535, 65536, 65537, 65538,
	    0x7ffffffeLL, 0x7fffffffLL, 0x80000000LL, 0x80000001LL,
	    0x7000000000000000LL, 0x7000000080000000LL, 0x7000000080000001LL,
	    0x7fffffffffffffffLL, 0x7fffffff8fffffffLL, 0x7fffffff8ffffff1LL,
	    0x7fffffff00000000LL, 0x7fffffff80000000LL, 0x7fffffff00000001LL,
	    0x0123456789abcdefLL, 0x00000000abcdef01LL, 0x0000000012345678LL,
	};

	printk("%s", "Testing signed 64-bit division.\n");
	n = sizeof(tabs) / sizeof(tabs[0]);
	for (i = 0; i < n; i++) {
		for (j = 1; j < n; j++) {
			for (k = 0; k <= 3; k++) {
				u = (k & 1)  ? -tabs[i] : tabs[i];
				v = (k >= 2) ? -tabs[j] : tabs[j];

				q = div64_s64(u, v);
				r = u - q * v;
				if (abs64(q) >  abs64(u) ||
				    abs64(r) >= abs64(v) ||
				    (r != 0 && (r ^ u) < 0)) {
					printk("%016llx/%016llx != %016llx "
					    "rem %016llx\n", u, v, q, r);
					errors++;
				}
			}
		}
	}

	if (errors) {
		printk("Failed %d/%d tests\n", errors, n * (n - 1));
	} else {
		printk("Passed all %d tests\n", n * (n - 1));
	}

	return 0;
}

void div64_s64_exit(void) { }

module_init(div64_s64_test);
module_exit(div64_s64_exit);

linux-2.6.35

Testing Summary | x86_64 | x86 |
--------------------+-----------------+

linux-2.6.35        | PASS   | FAIL   |
linux-2.6.35+patch  | PASS   | PASS   |

Testing Details (x86_64)
--------------------------------------------------------------------------
* PASS - linux-2.6.35
Testing unsigned 64-bit division.
Passed all 2756 tests

* PASS - linux-2.6.35+patch
Testing unsigned 64-bit division.
Passed all 2756 tests
Testing signed 64-bit division.
Passed all 2162 tests

Testing Details (x86)
--------------------------------------------------------------------------
* FAIL - linux-2.6.35
Testing unsigned 64-bit division. 7000000080000000/7000000080000001 != 0000000000000001 rem ffffffffffffffff 7fffffff8fffffff/7fffffffffffffff != 0000000000000001 rem ffffffff90000000 7fffffff8ffffff1/7fffffffffffffff != 0000000000000001 rem ffffffff8ffffff2 7fffffff8ffffff1/7fffffff8fffffff != 0000000000000001 rem fffffffffffffff2 7fffffff00000000/7fffffff00000001 != 0000000000000001 rem ffffffffffffffff 7fffffff80000000/7fffffffffffffff != 0000000000000001 rem ffffffff80000001 7fffffff80000000/7fffffff8fffffff != 0000000000000001 rem fffffffff0000001 7fffffff80000000/7fffffff8ffffff1 != 0000000000000001 rem fffffffff000000f 8000000000000000/8000000080000000 != 0000000000000001 rem ffffffff80000000 8000000000000000/8000000080000001 != 0000000000000001 rem ffffffff7fffffff 8000000080000000/8000000080000001 != 0000000000000001 rem ffffffffffffffff c000000000000000/c000000080000000 != 0000000000000001 rem ffffffff80000000 c000000000000000/c000000080000001 != 0000000000000001 rem ffffffff7fffffff c000000080000000/c000000080000001 != 0000000000000001 rem ffffffffffffffff fffffffffffffffd/7fffffffffffffff != 0000000000000002 rem ffffffffffffffff fffffffffffffffd/fffffffffffffffe != 0000000000000001 rem ffffffffffffffff fffffffffffffffe/ffffffffffffffff != 0000000000000001 rem ffffffffffffffff Failed 17/2756 tests

* PASS - linux-2.6.35+patch
Testing unsigned 64-bit division.
Passed all 2756 tests
Testing signed 64-bit division.
Passed all 2162 tests

#1 lore raw
Quoted 10 lines · Brian Behlendorf

I'm resending the patch as is and adding what I hope are the right CCs. Also let me explain why I opted to add abs64() and use the gcc builtin.

Quoted 1 line

Can't we just improve abs? Say,

I was reluctant to change abs() since it would have a much larger impact on the code base. Using typeof() should be OK but if any of the callers mistakenly call abs() with an unsigned value then we could see compiler warnings about '__x < 0' being a useless conditional.

I see. Probably in this case we want this warning. But I agree, it is better to make a separate patch for such a change.

Quoted 6 lines
Quoted 3 lines

This is a bit unusual. I mean, it is not that common to use gcc builtins in the normal code. And, it seems, we can use __fls(divisor >> 32) or just fls64() instead ?

I opted for the gcc builtin because I felt it made the code more readable. I also suspect it will perform slightly better than __fls() on some archs.

Well, compared to div_64() we are going to do, this is nothing. But I won't argue.

I think the patch is correct. A couple of questions though,

Quoted 1 line

+ * 'http://www.hackersdelight.org/HDcode/newCode/divDouble.c'

404

Quoted 11 lines

u64 div64_u64(u64 dividend, u64 divisor)
{

lib/div64.c +4 -5
-	u32 high, d;
-
-	high = divisor >> 32;
-	if (high) {
-		unsigned int shift = fls(high);
+	u64 u0, quot0, quot1;
+	u32 rem;
+	int n;
+

lib/div64.c s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder) · line 107

Quoted 10 lines
lib/div64.c +10 -0
+	if (divisor >> 32 == 0) {
+		if (dividend >> 32 < divisor) {
+			return div_u64_rem(dividend, divisor, &rem);
+		} else {
+			u0 = dividend & 0xFFFFFFFF;
+			quot1 = div_u64_rem(dividend >> 32, divisor, &rem);
+			u0 += ((u64)rem << 32);
+			quot0 = div_u64_rem(u0, divisor, &rem);
+			return (quot1 << 32) + quot0;
+		}

Looks correct... but I can't understand these complications. Looks like we can just do

	if ((divisor >> 32) == 0) {
		div_u64(dividend, divisor);
	} else {
	...

No?

lib/div64.c s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder) · line 111

Quoted 4 lines
lib/div64.c +4 -0
+	} else {
+		n = __builtin_clzll(divisor);
+		quot1 = div_u64_rem(dividend >> 1, (divisor << n) >> 32, &rem);
+		quot0 = (quot1 << n) >> 31;

I can't understand this "dividend >> 1". It seems to me that

		quot1 = div_u64(dividend, (divisor << n) >> 32);
		quot0 = (quot1 << n) >> 32;

should be equally correct. Or I missed some overflow?

Anyway this looks correct, but I almost died trying to understand this code (or, better say, to convince myself I can understand it ;)

Looks like, if we denote

A = dividend
B = divisor
K = 1ull << (32 - n)

then

		quot0 = A / (B - (B % K))

which is obviously >= A/B. All we need is to ensure is that it is <= A/B + 1, and this seems to be true.

So, I believe the patch is correct.

A bit off-topic,

Quoted 9 lines
			uu = tabu[i];
			vu = tabu[j];
			qu = div64_u64(uu, vu);
			ru = uu - qu * vu;
			if (qu > uu || ru >= vu) {
				printk("%016llx/%016llx != %016llx "
				   "rem %016llx\n", uu, vu, qu, ru);
				errors++;
			}

I wouldn't trust this check too much. I mean, it can miss an error. For example, consider something like

	vu = -1ll
	uu = vu / 2
	qu = 2		// suppose that div64_u64() is very wrong

Afaics, this wrong qu passes the check.

Oleg.

#2 lore raw
Quoted 42 lines · Oleg Nesterov
Quoted 12 lines · Brian Behlendorf

u64 div64_u64(u64 dividend, u64 divisor)
{

lib/div64.c +4 -5
-	u32 high, d;
-
-	high = divisor >> 32;
-	if (high) {
-		unsigned int shift = fls(high);
+	u64 u0, quot0, quot1;
+	u32 rem;
+	int n;
+

lib/div64.c s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder) · line 107

Quoted 10 lines
lib/div64.c +10 -0
+	if (divisor >> 32 == 0) {
+		if (dividend >> 32 < divisor) {
+			return div_u64_rem(dividend, divisor, &rem);
+		} else {
+			u0 = dividend & 0xFFFFFFFF;
+			quot1 = div_u64_rem(dividend >> 32, divisor, &rem);
+			u0 += ((u64)rem << 32);
+			quot0 = div_u64_rem(u0, divisor, &rem);
+			return (quot1 << 32) + quot0;
+		}

Looks correct... but I can't understand these complications. Looks like we can just do

	if ((divisor >> 32) == 0) {
		div_u64(dividend, divisor);
	} else {
	...

No?

lib/div64.c s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder) · line 111

Quoted 4 lines
lib/div64.c +4 -0
+	} else {
+		n = __builtin_clzll(divisor);
+		quot1 = div_u64_rem(dividend >> 1, (divisor << n) >> 32, &rem);
+		quot0 = (quot1 << n) >> 31;

I can't understand this "dividend >> 1". It seems to me that

Quoted 4 lines
		quot1 = div_u64(dividend, (divisor << n) >> 32);
		quot0 = (quot1 << n) >> 32;

should be equally correct. Or I missed some overflow?

Thinking more about this with a fresh head, we don't event need quot1, unless I missed something. We can do

		quot0 = div_u64((dividend << n) >> 32, (divisor << n) >> 32);

instead. Or, better,

		n = 32 - __builtin_clzll(divisor);
		quot0 = div_u64(dividend >> n, divisor >> n);

And 32 - clzll == fls.

So, I think it can be really trivial, see the test-case below, seems to work (you need 64bit machine to test).

What do you think? I do not trust my math skills.

Oleg.

#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
#include <sys/fcntl.h>
#include <assert.h>

typedef unsigned long long u64;
typedef unsigned long u32;

static inline u64 div_u64(u64 A, u32 B)

{
	return A / B;
}

static inline unsigned long __fls(unsigned long word)

{
	asm("bsr %1,%0"
	    : "=r" (word)
	    : "rm" (word));
	return word;
}

u64 div64_u64(u64 A, u64 B)

{
	u32 high = B >> 32;
	u64 quot;

	if (high == 0) {
		quot = div_u64(A, B);
	} else {
		int n = 1 + __fls(high);
		quot = div_u64(A >> n, B >> n);

		if (quot != 0)
			quot--;
		if ((A - quot * B) >= B)
			quot++;
	}

	return quot;
}

int main(void)

{
	int fd, n;

	fd = open("/dev/urandom", O_RDONLY);
	assert(fd >= 0);

	for (n = 1;; ++n) {
		u64 xx[2], rs;

		assert(read(fd, xx, sizeof(xx)) == sizeof(xx));

		if (xx[1] == 0)
			continue;

		rs = div64_u64(xx[0], xx[1]);

		if (rs != xx[0] / xx[1]) {
			printf("ERR!! %llx / %llx = %llx : %llx\n",
				xx[0] , xx[1], xx[0] / xx[1], rs);
			return 1;
		}

		if (!(n %100000))
			printf("passed: %d\n", n);
	}
}
#3 lore raw
Quoted 14 lines
Quoted 14 lines

Review

Quoted 10 lines
(quoted diff) +10 -0
+	if (divisor >> 32 == 0) {
+		if (dividend >> 32 < divisor) {
+			return div_u64_rem(dividend, divisor, &rem);
+		} else {
+			u0 = dividend & 0xFFFFFFFF;
+			quot1 = div_u64_rem(dividend >> 32, divisor, &rem);
+			u0 += ((u64)rem << 32);
+			quot0 = div_u64_rem(u0, divisor, &rem);
+			return (quot1 << 32) + quot0;
+		}

Looks correct... but I can't understand these complications. Looks like we can just do

Quoted 6 lines
Quoted 6 lines
	if ((divisor >> 32) == 0) {
		div_u64(dividend, divisor);
	} else {
	...

No?

The idea here, as described in the formal proof, is to cleanly handle the overflow case. When I implemented this I assumed the overflow case would in fact be a problem. To my surprise your right it doesn't seem to be causing any trouble. In practice I can't find any cases where it is a problem on i386.

Quoted 10 lines
Quoted 6 lines

I can't understand this "dividend >> 1". It seems to me that

		quot1 = div_u64(dividend, (divisor << n) >> 32);
		quot0 = (quot1 << n) >> 32;

should be equally correct. Or I missed some overflow?

Thinking more about this with a fresh head, we don't event need quot1, unless I missed something. We can do

Quoted 8 lines
		quot0 = div_u64((dividend << n) >> 32, (divisor << n) >> 32);

instead. Or, better,

		n = 32 - __builtin_clzll(divisor);
		quot0 = div_u64(dividend >> n, divisor >> n);

And 32 - clzll == fls.

Once again, the extra complexity was only there to handle to overflow case.

Quoted 4 lines

So, I think it can be really trivial, see the test-case below, seems to work (you need 64bit machine to test).

What do you think? I do not trust my math skills.

I think we should use your simpler version. There's no good reason to make this more complicated than it needs to be. I haven't been able to find a test case where your changes get the wrong result.

The updated patch is against linux-2.6.35 and passes all the previous test cases.

Thanks,
Brian

Quoted 1 line

From 35755c57cb45f7d30abcd88a8e2fc1ccc5beecfd Mon Sep 17 00:00:00 2001

From: Brian Behlendorf <[email protected]>
Date: Thu, 5 Aug 2010 14:59:11 -0700
Subject: [PATCH] Fix div64_u64 for 32bit platforms

The current implementation of div64_u64 for 32bit systems returns an approximately correct result when the divisor exceeds 32bits. Since doing 64bit division using 32bit hardware is a long since solved problem we just use one of the existing proven methods.

Additionally, add a div64_s64 function to correctly handle doing signed 64bit division.

---
 include/linux/kernel.h |    5 ++++
 include/linux/math64.h |   12 +++++++++++
 lib/div64.c            |   52 ++++++++++++++++++++++++++++++++++++++---------
 3 files changed, 59 insertions(+), 10 deletions(-)
include/linux/kernel.h +5 -0
index 8317ec4..ed6371c 100644
@@ -162,6 +162,11 @@ extern int _cond_resched(void);
 		(__x < 0) ? -__x : __x;		\
 	})
 
+#define abs64(x) ({				\
+		s64 __x = (x);			\
+		(__x < 0) ? -__x : __x;		\
+	})
+
 #ifdef CONFIG_PROVE_LOCKING
 void might_fault(void);
 #else
include/linux/math64.h +12 -0
index c87f152..23fcdfc 100644
@@ -35,6 +35,14 @@ static inline u64 div64_u64(u64 dividend, u64 divisor)
 	return dividend / divisor;
 }
 
+/**
+ * div64_s64 - signed 64bit divide with 64bit divisor
+ */
+static inline s64 div64_s64(s64 dividend, s64 divisor)
+{
+	return dividend / divisor;
+}
+
 #elif BITS_PER_LONG == 32
 
 #ifndef div_u64_rem
@@ -53,6 +61,10 @@ extern s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder);
 extern u64 div64_u64(u64 dividend, u64 divisor);
 #endif
 
+#ifndef div64_s64
+extern s64 div64_s64(s64 dividend, s64 divisor);
+#endif
+
 #endif /* BITS_PER_LONG */
 
 /**
lib/div64.c +42 -10

68 lines not on this page · raw message

Signature · 1 line
1.7.1
#4 lore raw

Andrew, please drop

	lib-div64c-document-that-div64_u64-is-not-precise-on-32bit-platforms.patch
Quoted 4 lines · Brian Behlendorf

I think we should use your simpler version. There's no good reason to make this more complicated than it needs to be. I haven't been able to find a test case where your changes get the wrong result.

Great!

Quoted 8 lines

From: Brian Behlendorf <[email protected]>
Date: Thu, 5 Aug 2010 14:59:11 -0700
Subject: [PATCH] Fix div64_u64 for 32bit platforms

The current implementation of div64_u64 for 32bit systems returns an approximately correct result when the divisor exceeds 32bits. Since doing 64bit division using 32bit hardware is a long since solved problem we just use one of the existing proven methods.

Brian, you forgot to add your sob. Hopefully Andrew can add

maintainer
#5 lore raw
Quoted 21 lines · On Thu, 21 Oct 2010 20:12:20 +0200 Oleg Nesterov <[email protected]> wrote:

Andrew, please drop

	lib-div64c-document-that-div64_u64-is-not-precise-on-32bit-platforms.patch
Quoted 4 lines · Brian Behlendorf

I think we should use your simpler version. There's no good reason to make this more complicated than it needs to be. I haven't been able to find a test case where your changes get the wrong result.

Great!

Quoted 8 lines

From: Brian Behlendorf <[email protected]>
Date: Thu, 5 Aug 2010 14:59:11 -0700
Subject: [PATCH] Fix div64_u64 for 32bit platforms

The current implementation of div64_u64 for 32bit systems returns an approximately correct result when the divisor exceeds 32bits. Since doing 64bit division using 32bit hardware is a long since solved problem we just use one of the existing proven methods.

Quoted 5 lines

Brian, you forgot to add your sob. Hopefully Andrew can add

OK..

Just to tie all this off, you originally said "We have a bug report which blames div64_u64() on 32bit platforms.". Where is that bug report?

Thanks.