Mic1，微汇编语言，创建乘法器

Question

我目前正在使用微汇编语言（MAL）并使用 Mic1mmv 模拟器来测试它。我试图弄清楚如何编写一个将两个数字相乘的程序，但我正在努力弄清楚如何做到这一点。

下面是加法和减法的 MAL 代码：

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

举个例子，假设我想做 3 x 4。我的想法是取 3 并与另一个 3 相加 4 次（3+3+3+3），但我还没有弄清楚如何我可以制作一个 if/else/循环或倒计时来跟踪它被添加在一起的次数。

如果有人知道如何解决这个问题或者有任何提示，我将非常感激，谢谢！

Answer 1

我知道这个问题有点老了，但也许我仍然可以帮助其他试图理解这个问题的人。

\n

显而易见的答案

\n

给定乘法a * b. 正如您所猜测的，首先想到的明显答案是计算b + b + b + b + [...]。事实上，这是一个正确的方法，尽管现在所需的计算周期完全取决于 b，因此 b 越大，该方法计算所需的时间就越长。

\n

更好的方法

\n

但是，当然，有一个解决方案。考虑到先前的乘法，a * b其中两个数字都是无符号的并且都是 32 位，b 可以被描述为 (0 <= i <= 32) 的和b(i) * 2^(i)。现在，如果我们将其与 a 相乘，我们会得到b(i) * (a * 2^(i))(0 <= i <= 32)。因此，为了用文字解释它，我们遍历每个位并将其对应的二进制值相乘。现在的结果只是每次计算的总和。这样我们最多可以进行 32 次计算。

\n

在 C 代码中，它看起来像这样：

\n

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

\n

但这段代码目前还无法转换为微指令。

\n

\n
1. for且if无法 1:1 翻译
\n
2. 我们受限于 ALU 的能力，即移位操作
\n
3. ALU 只能产生数字 0、1 和 -1
\n

\n

在下面的第二种方法中，我们用 while 循环替换 for 循环。这是可能的，因为我们每次通过移位位将 b 减半，因此 b 在某一点必须等于 0。明确经过32个轮班后。

\n

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

\n

现在我们可以替换更高的控制结构，例如 while 循环：

\n

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

\n

现在我们可以开始将其投影到 mic-1 上。

\n

\n
1. 变量 a 在堆栈上位于变量 b 之下。因此，我们首先必须启动读取指令。这意味着 a 将出现在 MDR 寄存器中。
\n
2. 变量 b 位于堆栈顶部。这意味着它的值已经在寄存器 TOS 中。
\n
3. 为了保存和更新最终结果，我将其命名为“产品”，我们只剩下寄存器 OPC，因为它是唯一没有限制的其他寄存器
\n

\n

我们还必须将所有操作投射到 mic-1 上。

\n

\n
1. 检查 b == 0 是否可以通过查看 Z 标志立即完成（零标志，如果 ALU 的输出为 0，则为 1）
\n
2. 测试是否b & 1 == 0必须分两步完成，因此我们使用寄存器 H 来存储 1
\n
3. 将 a 向左移位 1 不能直接由 ALU 完成，但a = a << 1只能是a = a + a，因为我们是二进制的
\n
4. b 右移 1 可以直接由 ALU 完成
\n

\n

完成所有这些后，让我们看看我们现在处于什么位置：

\n

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

\n

现在我们可以将其直接翻译成微汇编程序：

\n

imul1  |\xc2\xa0MAR = SP = SP - 1; rd\nimul2  |\xc2\xa0OPC = 0\nloop   |\xc2\xa0Z = TOS; if (Z) goto finish; else goto imul4 \nimul4  |\xc2\xa0H=1\nimul5  |\xc2\xa0Z = TOS AND H; if (Z) goto next; else goto imul6 \nimul6  |\xc2\xa0H = MDR\nimul7  |\xc2\xa0OPC = OPC + H\nnext   |\xc2\xa0H = MDR\nimul9  |\xc2\xa0MDR = MDR + H\nimul10 |\xc2\xa0TOS = TOS >> 1; goto loop\nfinish |\xc2\xa0MDR = TOS = OPC; wr; goto Main1\n

\n