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.
int mulhs(int u, int v) {牋 unsigned u0, v0, w0; 牋爄nt u1, v1, w1, w2, t; 牋 u0 = u & 0xFFFF;?u1 = u >> 16; 牋爒0 = v & 0xFFFF;?v1 = v >> 16; 牋爓0 = u0*v0; 牋爐?= u1*v0 + (w0 >> 16); 牋爓1 = t & 0xFFFF; 牋爓2 = t >> 16; 牋爓1 = u0*v1 + w1; 牋爎eturn u1*v1 + w2 + (w1 >> 16); }
The algorithm requires 16 basic RISC instructions in either the signed or unsigned version, four of which are multiplications.