8-2. High-Order Half of 64-Bit Product

Here we consider the problem of computing the high-order 32 bits of the product of two 32-bit integers. This is the function of our basic RISC instructions multiply high signed (mulhs) and multiply high unsigned (mulhu).

For unsigned multiplication, the algorithm in the upper half of Figure 8-1 works well. Rewrite it for the special case m = n = 2, with loops unrolled, obvious simplifications made, and the parameters changed to 32-bit unsigned integers.

For signed multiplication, it is not necessary to code the “correction steps” in the lower half of Figure 8-1. These can be omitted if proper attention is paid to whether the intermediate results are signed or unsigned (declaring them to be signed causes the right shifts to be sign-propagating shifts). The resulting algorithm is shown in Figure 8-2. For an unsigned version, simply change all the int declarations to unsigned.

Figure 8-2. Multiply high signed.

int mulhs(int u, int v) {
   unsigned u0, v0, w0; 
   int u1, v1, w1, w2, t; 

   u0 = u & 0xFFFF;  u1 = u >> 16; 
   v0 = v & 0xFFFF;  v1 = v >> 16; 
   w0 = u0*v0; 
   t  = u1*v0 + (w0 >> 16); 
   w1 = t & 0xFFFF; 
   w2 = t >> 16; 
   w1 = u0*v1 + w1; 
   return u1*v1 + w2 + (w1 >> 16); 
} 

The algorithm requires 16 basic RISC instructions in either the signed or unsigned version, four of which are multiplications.