[patch] fix __div64_32 to do division properly

[patch] fix __div64_32 to do division properly

[Randolph Chung]

The generic __div64_32 in lib/div64.c only handles "small" divisors. If
the divisor is full 32-bits, it returns invalid results. This patch 
fixes it. (this is used e.g. in nanosleep)

thanks
randolph

Index: lib/div64.c
===================================================================
RCS file: /var/cvs/linux-2.6/lib/div64.c,v
retrieving revision 1.1
diff -u -p -r1.1 div64.c
--- lib/div64.c	29 Jul 2003 17:02:19 -0000	1.1
+++ lib/div64.c	24 Oct 2003 04:10:59 -0000
@@ -25,25 +25,27 @@
 
 uint32_t __div64_32(uint64_t *n, uint32_t base)
 {
-	uint32_t low, low2, high, rem;
+	uint64_t rem = *n;
+	uint64_t b = base;
+	uint64_t res = 0, d = 1;
 
-	low   = *n   & 0xffffffff;
-	high  = *n  >> 32;
-	rem   = high % (uint32_t)base;
-	high  = high / (uint32_t)base;
-	low2  = low >> 16;
-	low2 += rem << 16;
-	rem   = low2 % (uint32_t)base;
-	low2  = low2 / (uint32_t)base;
-	low   = low  & 0xffff;
-	low  += rem << 16;
-	rem   = low  % (uint32_t)base;
-	low   = low  / (uint32_t)base;
+	if (b > 0) {
+		while (b < rem) {
+			b <<= 1;
+			d <<= 1;
+		}
+	}
 
-	*n = low +
-		((uint64_t)low2 << 16) +
-		((uint64_t)high << 32);
+	do {
+		if (rem >= b) {
+			rem -= b;
+			res += d;
+		}
+		b >>= 1;
+		d >>= 1;
+	} while (d);
 
+	*n = res;
 	return rem;
 }
 

-- 
Randolph Chung
Debian GNU/Linux Developer, hppa/ia64 ports
http://www.tausq.org/

Re: [patch] fix __div64_32 to do division properly

[Linus Torvalds]

On Sun, 26 Oct 2003, Randolph Chung wrote:
>
> Hi Linus, this was sent to lkml a few days ago. Pls consider applying
> for 2.6 :-)

As far as I can tell, this one is buggy and can cause total lockups with 
an infinite loop:

> +	if (b > 0) {
> +		while (b < rem) {
> +			b <<= 1;
> +			d <<= 1;
> +		}
> +	}

The "shift up until big enough" is _not_ valid: if the thing we divide is 
large (high bit set and some other bits set too), then shifting 'b' up may 
never make 'b' bigger than 'rem'.

It looks like this should be trivially triggerable by just dividing ~0ULL 
with pretty much anything.

Or did I miss something?

Also, I have to say that it seems silly to do the old "one bit at a time"  
thing when most hardware will have at least a 32/32 divide (and even if it
doesn't have a hardware 32-bit divide, the "one bit at a time"  algorithm
will be faster for regular 32-bit values).

Note that the reduction of the high 32 bits can be done with all 32-bit 
math.

So with the overflow case fixed, and with a 32/32 initial reduction of the 
high bits, the thing would look something like this:

	uint32_t __div64_32(uint64_t *n, uint32_t base)
	{
		uint64_t rem = *n;
		uint64_t b = base;
		uint64_t res, d = 1;
		uint32_t high = rem >> 32;
		uint64_t top;
	
		/* Reduce the thing a bit first */
		res = 0;
		if (high >= base) {
			high /= base;
			res = (uint64_t) high << 32;
			rem -= (uint64_t) (high*base) << 32;
		}

		while ((int64_t)b > 0 && b < rem) {
			b <<= 1;
			d <<= 1;
		}
	
		do {
			if (rem >= b) {
				rem -= b;
				res += d;
			}
			b >>= 1;
			d >>= 1;
		} while (d);
	
		*n = res;
		return rem;
	}
	
but I have not really verified this for any reasonable amount of values..

If you can verify this some way (test at least a somewhat interesting 
subset), please re-send the patch. 

Remember: be _careful_ with math. Overflow is nasty.

		Linus

Re: [patch] fix __div64_32 to do division properly

[Randolph Chung]

> As far as I can tell, this one is buggy and can cause total lockups with 
> an infinite loop:

oops, you are absolutely right....

your version seems to be ok. i tested it with all two-bit combinations
of dividend and divisors,  i.e.

for (b1 = 63; b1 > 0; b1--) {
    for (b2 = b1-1; b2 > 0; b2--) {
        for (b3 = 31; b3 > 0; b3--) {
            for (b4 = b3-1; b4 > 0; b4--) {
                dividend = (1ULL<<b1) | (1ULL<<b2);
                divisor = (1UL<<b3) | (1UL<<b4);
                testdiv(dividend, divisor);
            }
        }
    }
}

and it seems to be ok (and it catches the problem you pointed out). is
that an interesting enough subset? :-)

anyway, here's a new patch tested as above and with the original
nanosleep problem. (i removed the top variable from your version since
it's not used)

thx
randolph
-- 
Randolph Chung
Debian GNU/Linux Developer, hppa/ia64 ports
http://www.tausq.org/


Index: lib/div64.c
===================================================================
RCS file: /var/cvs/linux-2.6/lib/div64.c,v
retrieving revision 1.1
diff -u -p -r1.1 div64.c
--- lib/div64.c	29 Jul 2003 17:02:19 -0000	1.1
+++ lib/div64.c	26 Oct 2003 19:04:47 -0000
@@ -25,25 +25,34 @@
 
 uint32_t __div64_32(uint64_t *n, uint32_t base)
 {
-	uint32_t low, low2, high, rem;
+	uint64_t rem = *n;
+	uint64_t b = base;
+	uint64_t res, d = 1;
+	uint32_t high = rem >> 32;
 
-	low   = *n   & 0xffffffff;
-	high  = *n  >> 32;
-	rem   = high % (uint32_t)base;
-	high  = high / (uint32_t)base;
-	low2  = low >> 16;
-	low2 += rem << 16;
-	rem   = low2 % (uint32_t)base;
-	low2  = low2 / (uint32_t)base;
-	low   = low  & 0xffff;
-	low  += rem << 16;
-	rem   = low  % (uint32_t)base;
-	low   = low  / (uint32_t)base;
+	/* Reduce the thing a bit first */
+	res = 0;
+	if (high >= base) {
+		high /= base;
+		res = (uint64_t) high << 32;
+		rem -= (uint64_t) (high*base) << 32;
+	}
 
-	*n = low +
-		((uint64_t)low2 << 16) +
-		((uint64_t)high << 32);
+	while ((int64_t)b > 0 && b < rem) {
+		b <<= 1;
+		d <<= 1;
+	}
 
+	do {
+		if (rem >= b) {
+			rem -= b;
+			res += d;
+		}
+		b >>= 1;
+		d >>= 1;
+	} while (d);
+
+	*n = res;
 	return rem;
 }