algorithm - 用mips写俄罗斯农民乘法

Question

我想编写一个使用 mips 的俄罗斯农民乘法的程序，但我遇到了一些问题

/ A method to multiply two numbers using Russian Peasant method
unsigned int russianPeasant(unsigned int a, unsigned int b)
{
    int res = 0;  // initialize result

    // While second number doesn't become 1
    while (b > 0)
    {
         // If second number becomes odd, add the first number to result
         if (b & 1)
             res = res + a;

         // Double the first number and halve the second number
         a = a << 1;
         b = b >> 1;
     }
     return res;
}

我用MARS环境翻译成mips

    .data
msg1: .asciiz "give your first number"
msg2: .asciiz "give the second number"

    .text
#a = $t1
#b = $t2
li $t3,0 #p

li $s1,1
li $s2,2

#display msg1
li $v0,4
la $a0,msg1
syscall
#read first number
li $v0,5
syscall
move $t1,$v0

#display msg2
li $v0,4
la $a0,msg2
syscall
#read second number
li $v0,5
syscall
move $t2,$v0

WHILE: 
    bgt $t2,$zero,DO
    move $a0,$t3
    li $v0,1
    syscall
    li $v0,10
    syscall

DO:
     div $t2,$s2
     mfhi $s0 #r $s0 = $t2 / $s2
     beq $s0,$s1,INC # IF b MOD 2 = 1 I jump to INC
    #a = 2xa
     mul $t1,$t1,$s2

     div $t2,$s2
     mflo $t2 # b = $t2/$s2
     j WHILE 

# i = i+ 1   
INC:
    add $t3,$t3,$t1
    jr $ra 

请问，有人可以帮助我吗？修复“错误:无效的程序计数器值:0x00000000”我搜索了如何修复它，但我对 $ra 有疑问如何在 $ra 中正确保存返回地址？

Answer 1

jr $ra 将跳转到寄存器 $ra 中存储的地址，该地址未由您的代码设置，因此它仍然为零(初始寄存器值来自运行代码之前的 MARS)。然后 CPU 将跳转到地址零，这是失败，并报告。

要使用 jr $ra 从某些代码“返回”，您必须首先使用 jal 指令(或其他修改 $ra 的指令> 内容)来设置 $ra。此外，当你想嵌套多个 jal “子程序调用”时，你必须存储/恢复周围调用的 $ra 以免丢失下一个嵌套的值jal.

以下代码是使用成对的 jal+jr $ra 进行类似“子程序”的调用的示例，并且还示例了这种算法的实现是多么简单汇编(因为实际上 C 源更像是 C 中的汇编，所以你的经验不足使你采取了一种非常复杂和复杂的方法来实现一些可以在汇编中实现的东西，与原始 C 源几乎 1:1):

.text
main:  # just minimal "main" to verify the code works
    # read two integers as input
    li      $v0,5
    syscall
    move    $a0, $v0        # $a0 = a
    li      $v0,5
    syscall
    move    $a1, $v0        # $a1 = b
    # call the russianPeasant subroutine
    jal     russianPeasant  # $v0 = a * b
    nop
    # output result
    move    $a0, $v0
    li      $v0, 1
    syscall
    # terminate
    li      $v0, 10
    syscall

以及子例程本身，可以使用 a0 和 a1 中的参数调用，并在 v0 中返回结果。

# input: $a0 = a, $a1 = b
# output: $v0 = a * b
russianPeasant:
    li      $v0, 0          # res = 0
    beq     $a1, $zero, russianPeasant_b_zero
    nop     # neutralize "Delayed branching" setting ("nop" works with both ON/OFF setting)
russianPeasant_while_b:
    andi    $at, $a1, 1     # test if b is odd, for even b skip the res = res + a
    beq     $at, $zero, russianPeasant_b_even
    nop     # but such neutralization comes with performance cost of course
    add     $v0, $v0, $a0   # res = res + a
russianPeasant_b_even:
    sll     $a0, $a0, 1     # a = a << 1
    srl     $a1, $a1, 1     # b = b >> 1
    bne     $a1, $zero, russianPeasant_while_b  # repeat when (b != 0)
    nop     # on real MIPS production code the instructions are reordered to avoid useless nop
russianPeasant_b_zero:
    jr      $ra             # return res
    nop

代码有意放在每个分支 nop 指令之后，以使其与延迟分支设置 ON 或 OFF 一起工作。

尝试使用带有指令描述的 MARS 帮助 (F1) 来弄清楚它是如何工作的，也可以使用调试器的单步功能来观察运行中的代码，一次一条指令，观察所有的寄存器值和代码流。

在具有延迟分支的真实 MIPS CPU 上，代码可以像这样优化(您可以在 MARS 设置中打开“延迟分支”，使其模拟具有这种有点令人困惑的行为的真实 MIPS CPU ..从您的原始来源看起来就像您在没有延迟分支的情况下学习 MIPS 汇编一样，对于刚开始学习汇编的人来说，这当然是合理的方法，但真正的 MIPS CPU 并不是这样工作的):

# input: $a0 = a, $a1 = b
# output: $v0 = a * b
russianPeasant_real_MIPS:   # second variant supporting delayed branching like real MIPS CPU
    beq     $a1, $zero, russianPeasant2_b_zero
    li      $v0, 0          # res = 0
russianPeasant2_while_b:
    andi    $at, $a1, 1     # test if b is odd, for even b skip the res = res + a
    beq     $at, $zero, russianPeasant2_b_even
    srl     $a1, $a1, 1     # b = b >> 1
    add     $v0, $v0, $a0   # res = res + a
russianPeasant2_b_even:
    bne     $a1, $zero, russianPeasant2_while_b  # repeat when (b != 0)
    sll     $a0, $a0, 1     # a = a << 1
russianPeasant2_b_zero:
    jr      $ra             # return res
    nop