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

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/