Mic1, Micro-assembly language, creating a multiplier

Question

I'm currently working with micro-assembly language (MAL) and using the Mic1mmv simulator to test it. I'm trying to figure out how to make a program that multiplies two numbers, but I'm struggling with figuring out how to do so.

Here is the following MAL code for addition and substraction:

iadd1   MAR = SP = SP - 1; rd       // Read in next-to-top word on stack
iadd2   H = TOS                     // H = top of stack
iadd3   MDR = TOS = MDR + H; wr; goto Main1 // Add top two words; write to top of stack

isub1   MAR = SP = SP - 1; rd       // Read in next-to-top word on stack
isub2   H = TOS                    // H = top of stack
isub3   MDR = TOS = MDR - H; wr; goto Main1 // Do subtraction; write to top of stack

As an example, let's say I want to do 3 x 4. My thoughts about doing so is to take 3 and add it with another 3 for 4 times (3+3+3+3), but I have yet to figure out how I can make a if/else/loop or a countdown that keeps track on how many times it has been added together.

If anyone knows how to solve this or have any tips about this, I would be really grateful, thanks!

Answer 1

I know that this question is a bit old, but maybe I can still help someone else who is trying to understand the problem.

Obvious Answer

Given a multiplication a * b. As you guessed, the obvious answer that first comes to mind is to just calculate b + b + b + b + [...]. And in fact that is a correct approach, though the calculation cycles needed completely depend on b now, so the bigger b gets the longer this approach will take to calculate.

The Better Way

But, of course, there is a solution to that. Given the previous multiplication of a * b where both numbers are unsigned and 32 Bit, b can be described as the sum of b(i) * 2^(i)(0 <= i <= 32). Now if we multiply that with a, we get b(i) * (a * 2^(i))(0 <= i <= 32). So to explain it in words, we go through each of the Bits and multiply their corresponding value in Binary. The result is now just the sum of each calculation. That leaves us with a maximum of 32 calculations.

In C Code that would look something like that:

unsigned multiply(unsigned a, unsigned b) { 
    unsigned i, product = 0;
    for (i = 0; i < 32; ++i) {
        if ((b & 1) == 1) { 
            product = product + a;
        }
        a = a << 1;
        b = b >> 1;
    } 
    return product;
}

But this code, as is, can't be translated into microinstructions just yet.

1. for and if can't be translated 1:1
2. We are limited by the capabilities of the ALU, namely the shifting operations
3. The ALU can only produce the numbers 0, 1 and -1

In the following, second, approach we replace the for loop, with a while-loop. That is possible because we half b every time by shifting the bits, so b must be equal to 0 at one point. Explicitly after 32 shifts.

unsigned multiply(unsigned a, unsigned b) { 
    unsigned product = 0;
    while (b != 0) {
        if ((b & 1) == 1) { 
            product = product + a;
        }
        a = a << 1;
        b = b >> 1;
    }
    return product;
}

Now we can replace the higher control structures, such as the while loop:

unsigned multiply(unsigned a, unsigned b) { 
    unsigned product = 0;
loop:
    if (b == 0) goto finish;
    if ((b & 1) == 0) goto next; 
    product = product + a;
next:
    a = a << 1;
    b = b >> 1;
    goto loop;
finish:
    return product; 
}

Now we can start projecting it onto the mic-1.

1. Variable a is under variable b on the stack. Therefore we first have to initiate a read instruction. That means a will be in the MDR register.
2. Variable b is on top of the stack. That means it's value is already in the register TOS.
3. For saving and updating the end result, I named it 'product', we are left with the register OPC as it the only other register with no restrictions

We also have to project all our operations onto the mic-1.

1. Checking if b == 0 can immediately be done by looking at the Z-flag (Zero flag, is 1 if the output of the ALU is 0)
2. Testing if b & 1 == 0 has to be done in two steps, so we use register H to store a 1
3. Bitshifting a to the left by 1 can't be directly done by the ALU but a = a << 1 is nothing else than a = a + a, because we are in binary
4. Bitshifting b to the right by 1 can directly be done by the ALU

With all that out of the way, let's see where we're at:

unsigned multiply(unsigned mdr, unsigned tos) { 
    unsigned z, h, opc = 0;
loop:
    z = tos;
    if (z == 0) goto finish; h = 1;
    z = tos & h;
    if (z == 0) goto next;
    h = mdr;
    opc = opc + h; 
next:
    h = mdr;
    mdr = mdr + h; tos = tos >> 1; goto loop;
finish:
    return opc;
}

Now we can translate this directly into a micro-assembler program:

imul1  | MAR = SP = SP - 1; rd
imul2  | OPC = 0
loop   | Z = TOS; if (Z) goto finish; else goto imul4 
imul4  | H=1
imul5  | Z = TOS AND H; if (Z) goto next; else goto imul6 
imul6  | H = MDR
imul7  | OPC = OPC + H
next   | H = MDR
imul9  | MDR = MDR + H
imul10 | TOS = TOS >> 1; goto loop
finish | MDR = TOS = OPC; wr; goto Main1