10-10 Incorporation into a Compiler (Unsigned)

There is a difficulty in implementing an algorithm based on direct evaluation of the expressions used in this proof. Although p 2W, which is proved above, the case p = 2W can occur (e.g., for d = 2W - 2 with W 4). When p = 2W, it is difficult to calculate m, because the dividend in (26) does not fit in a 2W-bit word.

However, it can be implemented by the "incremental division and remainder" technique of algorithm magic. The algorithm is given in Figure 10-2 for W = 32. It passes back an indicator a, which tells whether or not to generate an add instruction. (In the case of signed division, the caller recognizes this by M and d having opposite signs.)

Figure 10-2 Computing the magic number for unsigned division.
struct mu {unsigned M;牋牋 // Magic number, 
牋牋牋牋牋int a;牋牋牋牋牋 // "add" indicator, 
牋牋牋牋牋int s;};牋牋牋牋 // and shift amount. 
struct mu magicu(unsigned d) {
牋牋牋牋牋牋牋牋牋牋牋牋牋 // Must have 1 <= d <= 2**32-1. 
牋爄nt p; 
牋爑nsigned nc, delta, q1, r1, q2, r2; 
牋爏truct mu magu; 
牋 magu.a = 0;牋牋牋牋牋牋 // Initialize "add" indicator. 
牋爊c = -1 - (-d)%d;牋牋牋 // Unsigned arithmetic here. 
牋爌 = 31;牋牋牋牋牋牋牋牋 // Init. p. 
牋爍1 = 0x80000000/nc;牋牋 // Init. q1 = 2**p/nc. 
牋爎1 = 0x80000000 - q1*nc;// Init. r1 = rem(2**p, nc). 
牋爍2 = 0x7FFFFFFF/d;牋牋?// Init. q2 = (2**p - 1)/d. 
牋爎2 = 0x7FFFFFFF - q2*d; // Init. r2 = rem(2**p - 1, d). 
牋燿o {
牋牋?p = p + 1; 
牋牋牋if (r1 >= nc - r1) {
牋牋牋牋 q1 = 2*q1 + 1;牋牋牋牋牋?// Update q1. 
牋牋牋牋?/span>r1 = 2*r1 - nc;}牋牋牋牋?// Update r1. 
牋牋牋else {
牋牋牋牋 q1 = 2*q1; 
牋牋牋牋爎1 = 2*r1;} 
牋牋牋if (r2 + 1 >= d - r2) {
牋牋牋牋 if (q2 >= 0x7FFFFFFF) magu.a = 1; 
牋牋牋牋爍2 = 2*q2 + 1;牋牋牋牋牋?// Update q2. 
牋牋牋牋爎2 = 2*r2 + 1 - d;}牋牋牋 // Update r2. 
牋牋牋else {
牋牋牋牋 if (q2 >= 0x80000000) magu.a = 1; 
牋牋牋牋?/span>q2 = 2*q2; 
牋牋牋牋爎2 = 2*r2 + 1;} 
牋牋牋delta = d - 1 - r2; 
牋爙 while (p < 64 && 
牋牋牋牋牋?q1 < delta || (q1 == delta && r1 == 0))); 
magu.M = q2 + 1;牋?牋牋// Magic number 
牋爉agu.s = p - 32;牋牋牋?// and shift amount to return 
牋爎eturn magu;牋牋牋牋牋?// (magu.a was set above). 

Some key points in understanding this algorithm are as follows:

?span style='font:7.0pt "Times New Roman"'>         Unsigned overflow can occur at several places and should be ignored.

?span style='font:7.0pt "Times New Roman"'>         nc = 2W - rem(2W, d) - 1 = (2W - 1) - rem(2W - d, d).

?span style='font:7.0pt "Times New Roman"'>         The quotient and remainder of dividing 2p by nc cannot be updated in the same way as is done in algorithm magic, because here the quantity 2*r1 can overflow. Hence the algorithm has the test "if (r1 >= nc - r1)," whereas "if (2*r1 >= nc)" would be more natural. A similar remark applies to computing the quotient and remainder of 2p - 1 divided by d.

?span style='font:7.0pt "Times New Roman"'>         0 d d - 1, so d is representable as a 32-bit unsigned integer.

?span style='font:7.0pt "Times New Roman"'>         graphics/10icon150.gif

?span style='font:7.0pt "Times New Roman"'>         The subtraction of 2W when the magic number M exceeds 2W - 1 is not explicit in the program; it occurs if the computation of q2 overflows.

?span style='font:7.0pt "Times New Roman"'>         The "add" indicator, magu.a, cannot be set by a straightforward comparison of M to 232, or of q2 to 232 - 1, because of overflow. Instead, the program tests q2 before overflow can occur. If q2 ever gets as large as 232 - 1, so that M will be greater than or equal to 232, then magu.a is set equal to 1. If q2 stays below 232 - 1, then magu.a is left at its initial value of 0.

?span style='font:7.0pt "Times New Roman"'>         Inequality (27) is equivalent to 2p/nc > d.

?span style='font:7.0pt "Times New Roman"'>         The loop test needs the condition "p < 64" because without it, overflow of q1 would cause the program to loop too many times, giving incorrect results.