assembly - MIPS 32 位无符号乘法，不使用 mult 或 div

Question

我一直在开发一个程序，可以在不使用 MIPS mult(multu) 或 div(divu) 命令的情况下对两个 32 位无符号整数进行乘法。 我希望输出看起来就像 multu 函数一样，作为 64 位高字/低字组合。 我一直在使用一个模型，其中乘数位于乘积的右侧，如下所示:

for (i=0; i<32; i++)
{
   if LSB(multiplier)==1
   {
       LH product += multiplicand;
   }
   right shift product-multiplier 1;
}

目前在我的代码中，我不确定是否正确处理了 32 位加法中可能的进位位。

无论我选择操作什么整数值，我当前都会得到“0 0”的输出。

在我的代码中，我将最右边的位称为 LSB(低位字)，最左边的位称为 MSB(高位字)。

我的代码:

.data

    promptStart:    .asciiz "This prrogram does AxB without using mult or div"
           getA:    .asciiz "Please enter the first number(multiplicand): "
           getB:    .asciiz "Please enter the second number(multiplier): "

          space:    .asciiz " "

         result:    .asciiz "The product, using my program is: "
         mipMult:   .asciiz "The product, using MIPs multu is: "

       endLine: .asciiz "\n"

.text

main:
    #"welcome" screen
    li  $v0,4           # code for print_string
    la  $a0,promptStart     # point $a0 to prompt string
    syscall             # print the prompt


    li  $v0,4           # code for print_string
    la  $a0,endLine     # point $a0 to prompt string
    syscall             # print the prompt

    #prompt for multiplicand
    li  $v0,4           # code for print_string
    la  $a0,getA        # point $a0 to prompt string
    syscall             # print the prompt

    #acquire multiplicand
    li  $v0,5           # code for read_int
    syscall             # get an int from user --> returned in $v0
    move    $s0,$v0         # move the resulting int to $s0

    move    $s4,$s0         #copy of multiplicand to use in multu

    #prompt for multiplier
    li  $v0,4           # code for print_string
    la  $a0,getB        # point $a0 to prompt string
    syscall             # print the prompt

    #acquire multiplier
    li  $v0,5           # code for read_int
    syscall             # get an int from user --> returned in $v0
    move    $s1,$v0         # move the resulting int to $s0

    move    $s5,$s1         #copy of multiplier to use in multu 

    jal MyMult
    j   print

MyMult:

    #$s2 -> lw product, $s1 -> hw multiplier, $s0 -> multiplicand

    beq $s1, $0, done       # if multiplier=0--> mult gives 0
    beq $s0, $0, done

    move    $t0, $0         #initialize 'counter'= 31
    add $t0, $t0, 31

    move    $s2, $0         #initialize product = 0

    loopOut:
        beq $t0, $0, done   #loop check

        andi    $t1, $s1, 1 #Stores LSB(MSB?) of $s1 in $t1
        bne $t1, $0, loopIn #check if LSB is equal to 1
        srl $s1, $s1, 1
        srl $s2, $s2, 1 #right shift product & multiplier

        add $t0, $t0,-1 # counter = counter -1
        j   loopOut

    loopIn:
        addu    $s2, $s2, $s0   #Lw product($s2/$s1)+= multiplicand($s0)
        sltu    $t2, $s2, $s0   #catch carry-out(0 or 1) and stores in $t2      

        srl $s1, $s1, 1
        srl $s2, $s2, 1 #right shift pro-plier..how to save LSB of $s2?

        #add carry-out $t2 to LSB of product $s2
        addu    $s2, $s2, $t0   #Is this right?

        addu    $t0, $t0,-1 # counter = counter -1
        j   loopOut

    done:
        jr $ra

print:
    # print result string
    li  $v0,4           # code for print_string
    la  $a0,result      # point $a0 to string
    syscall             # print the result string

    # print out the result
    li  $v0,1           # code for print_int
    move    $a0,$s2         # put result in $a0
    syscall             # print out result

    li  $v0,4           # code for print_string
    la  $a0,space       # point $a0 to string
    syscall             # print the result string

    li  $v0,1           # code for print_int
    move    $a0,$s1         # put result in $a0
    syscall             # print out result


    # print the line feed
    li  $v0,4           # code for print_string
    la  $a0,endLine     # point $a0 to string
    syscall             # print the linefeed

doMult:
#Do same computation using Mult
    multu   $s4, $s5
    mfhi    $t0
    mflo    $t1

    li  $v0,4           # code for print_string
    la  $a0,mipMult     # point $a0 to string
    syscall 

    # print out the result
    li  $v0,1           # code for print_int
    move    $a0,$t0         # put high in $a0
    syscall             # print out result

    li  $v0,4           # code for print_string
    la  $a0,space       # point $a0 to string
    syscall             # print the result string

    # print out the result
    li  $v0,1           # code for print_int
    move    $a0,$t1         # put low in $a0
    syscall             # print out result

    # print the line feed
    li  $v0,4           # code for print_string
    la  $a0,endLine     # point $a0 to string
    syscall             # print the linefeed

    # All done, thank you!
    li  $v0,10          # code for exit
    syscall             # exit program

Answer 1

据我所知，甚至你的算法也被破坏了。您应该将被乘数向左移动(用于加法)，将因子向右移动(用于位测试)。产品不应移动。此外，被乘数需要扩展到 64 位，并且您需要 64 位移位来正确跨字边界传输位。

.data

    promptStart:    .asciiz "This program does AxB without using mult or div"
           getA:    .asciiz "Please enter the first number(multiplicand): "
           getB:    .asciiz "Please enter the second number(multiplier): "

          space:    .asciiz " "

         result:    .asciiz "The product, using my program is: "
         mipMult:   .asciiz "The product, using MIPs multu is: "

       endLine: .asciiz "\n"

.text

main:
    #"welcome" screen
    li  $v0,4           # code for print_string
    la  $a0,promptStart # point $a0 to prompt string
    syscall             # print the prompt


    li  $v0,4           # code for print_string
    la  $a0,endLine     # point $a0 to prompt string
    syscall             # print the prompt

    #prompt for multiplicand
    li  $v0,4           # code for print_string
    la  $a0,getA        # point $a0 to prompt string
    syscall             # print the prompt

    #acquire multiplicand
    li  $v0,5           # code for read_int
    syscall             # get an int from user --> returned in $v0
    move    $s0,$v0     # move the resulting int to $s0
    move    $s5,$s0     # copy of multiplicand to use in multu

    #prompt for multiplier
    li  $v0,4           # code for print_string
    la  $a0,getB        # point $a0 to prompt string
    syscall             # print the prompt

    #acquire multiplier
    li  $v0,5           # code for read_int
    syscall             # get an int from user --> returned in $v0
    move    $s1,$v0     # move the resulting int to $s0

    move    $s6,$s1     # copy of multiplier to use in multu

    jal MyMult
    j   print

MyMult:
    move $s3, $0        # lw product
    move $s4, $0        # hw product

    beq $s1, $0, done
    beq $s0, $0, done

    move $s2, $0        # extend multiplicand to 64 bits

loop:
    andi $t0, $s0, 1    # LSB(multiplier)
    beq $t0, $0, next   # skip if zero
    addu $s3, $s3, $s1  # lw(product) += lw(multiplicand)
    sltu $t0, $s3, $s1  # catch carry-out(0 or 1)
    addu $s4, $s4, $t0  # hw(product) += carry
    addu $s4, $s4, $s2  # hw(product) += hw(multiplicand)
next:
    # shift multiplicand left
    srl $t0, $s1, 31    # copy bit from lw to hw
    sll $s1, $s1, 1
    sll $s2, $s2, 1
    addu $s2, $s2, $t0

    srl $s0, $s0, 1     # shift multiplier right
    bne $s0, $0, loop

done:
    jr $ra

print:
    # print result string
    li  $v0,4           # code for print_string
    la  $a0,result      # point $a0 to string
    syscall             # print the result string

    # print out the result
    li  $v0,1           # code for print_int
    move    $a0,$s4     # put result in $a0
    syscall             # print out result

    li  $v0,4           # code for print_string
    la  $a0,space       # point $a0 to string
    syscall             # print the result string

    li  $v0,1           # code for print_int
    move    $a0,$s3     # put result in $a0
    syscall             # print out result


    # print the line feed
    li  $v0,4           # code for print_string
    la  $a0,endLine     # point $a0 to string
    syscall             # print the linefeed

doMult:
#Do same computation using Mult
    multu   $s5, $s6
    mfhi    $t0
    mflo    $t1

    li  $v0,4           # code for print_string
    la  $a0,mipMult     # point $a0 to string
    syscall

    # print out the result
    li  $v0,1           # code for print_int
    move    $a0,$t0         # put high in $a0
    syscall             # print out result

    li  $v0,4           # code for print_string
    la  $a0,space       # point $a0 to string
    syscall             # print the result string

    # print out the result
    li  $v0,1           # code for print_int
    move    $a0,$t1         # put low in $a0
    syscall             # print out result

    # print the line feed
    li  $v0,4           # code for print_string
    la  $a0,endLine     # point $a0 to string
    syscall             # print the linefeed

    # All done, thank you!
    li  $v0,10          # code for exit
    syscall             # exit program