32-bit multiplication through 16-bit shifting

Question

I am writing a soft-multiplication function call using shifting and addition. The existing function call goes like this:

unsigned long __mulsi3 (unsigned long a, unsigned long b) {

    unsigned long answer = 0;

    while(b)
    {
        if(b & 1) {
            answer += a;
        };

        a <<= 1;
        b >>= 1;
    }
    return answer;
}

Although my hardware does not have a multiplier, I have a hard shifter. The shifter is able to shift up to 16 bits at one time.

If I want to make full use of my 16-bit shifter. Any suggestions on how can I adapt the code above to reflect my hardware's capabilities? The given code shifts only 1-bit per iteration.

The 16-bit shifter can shift 32-bit unsigned long values up to 16 places at a time. The sizeof(unsigned long) == 32 bits

Answer 1

The basic approach is (assuming shifting by 1) :-

• Shift the top 16 bits
• Set the bottom bit of the top 16 bits to the top bit of the bottom 16 bits
• Shift the bottom 16 bits

Depends a bit on your hardware...

but you could try :-

• assuming unsigned long is 32 bits
• assuming Big Endian

then :-

 union Data32
        {
           unsigned long l;
           unsigned short s[2];
        }; 

unsigned long shiftleft32(unsigned long valueToShift, unsigned short bitsToShift)
{
    union Data32 u;
    u.l  = valueToShift
    u.s[0] <<= bitsToShift;
    u.s[0] |= (u.s[1] >> (16 - bitsToShift);
    u.s[1] <<= bitsToShift

    return u.l;
}

then do the same in reverse for shifting right