Signed 64 by 32 integer divisions

Question

Assuming you have a udive machine command that does a separate 64 by 32 case of unsigned division, accepting a (32-bit dividend <32) / 32bit divisor, we can do a full 64 by 32 split using the following:

// assume: a / b guaranteed not to overflow a = 64bit dividend, ah & al are hi & lo 32bits respectively b = 32bit divisor q1 = udive(ah, b) // (ah << 32) / b r1 = -(q1 * b) // remainder of the above, shortcut since ah & 0xffffffff == 0 q2 = al / b // al / b using regular unsigned division r2 = al - (q2 * b) // remainder of the above q = q1 + q2 r = r1 + r2 // r < r2, r overflowed and is >32bits, implies r > b since b is 32bits // r >= b, quotient too small by 1, adjust if (r < r2) or (r >= b) q = q + 1 return q 

However, the signed case gives me problems. Assuming an equivalent sdive statement that executes a signed version of udive, I can't completely decide how to deal with leftovers and something else.

Answer 1

I think your unsigned code would be easier to read, if it were explicit, about which variables were 32-bit, which were 64-bit, and whether the mappings were matched or unsigned.

Hacker Delight is usually good for this kind of low-level arithmetic. I don't have a copy at the moment, but its code for 64 / 64-> 64, given 64 / 32-> 32, is online: http://www.hackersdelight.org/HDcode/newCode/divDouble.c

This is a signed case, simply accepting the absolute values ​​of the inputs, doing an unsigned division, and then reversing the sign of the result bit if the inputs have a different sign. This tells me that this is probably the best approach (it is certainly easier to prove the alternatives are correct). You may need a special case when the dividend is the smallest possible integer if it does not just fall out in the wash.

Answer 2

thanks for the answer. I looked at the hacker enthusiasm. If you look at the divdi3 function in HD format, then the DIVS call, the 64 / 32-> 32 command, when the divider is 32-bit, and the result, as you know, does not overflow. The machine I work on does not have general instructions 64 / 32-> 32, it has a special case mentioned above. The above function for 64 / 32-> 32 is my implementation for DIVU in the unsigned case, so I am trying to work out something similar for DIVS.

I could just forget about the DIVS path, but that in the vast majority of cases, and I want to hit it as much as possible, it's just a complicated implementation.

Sorry for the incomprehensible pseudo-code, but everything is unsigned and mostly 32-bit.

 DIVU(uint64 a, uint32 b) { // assume: a / b guaranteed not to overflow // a = 64bit dividend, ah & al are hi & lo 32bits respectively // b = 32bit divisor uint32 q1 = udive(ah, b) // (ah << 32) / b uint32 r1 = -(q1 * b) // remainder of the above, shortcut for (ah << 32) - (q1 * b) since (ah << 32) & 0xffffffff == 0 uint32 q2 = al / b // al / b using regular unsigned division uint32 r2 = al - (q2 * b) // remainder of the above uint32 q = q1 + q2 uint32 r = r1 + r2 // r < r2, r overflowed and is >32bits, implies r > b since b is 32bits // r >= b, quotient too small by 1, adjust if (r < r2) or (r >= b) q = q + 1 return q } 

Answer 3

You can ignore the special case of optimizing divdi3 when calling div; what I wanted to draw attention to was the fact that when divdi3 needs to perform full-size division, it does this by calling udivdi3, and not having a signature equivalent, equivalent to the udivdi3 algorithm.

Looking in Knuth vol 2, I see that it also basically says that you signed the division in the process of accepting absolute values, doing unsigned separation, and then fixing the sign bit after that. This makes intuitive sense for me, because the signed additions numbers 2s do not have the convenient property that a == (ah * 2 ^ 32) + al, which are unsigned numbers, so it is not so easy to collect 64-bit operations by acting on two separately.

Before-and-after, there shouldn't be so many extra loops over an unsigned section ...

PS: what kind of strange CPU is it, anyway ?:-)