fix __div64_32 to do division properly
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 3 lines · Randolph Chung
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:
Review
Quoted 6 lines
(quoted diff) +6
-0+ 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
Quoted 2 lines
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
Signature · 62 lines
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;
}