Mipsでニードル再帰

Question

は私の大学のために私は、Mipsで議会内の特定のニードルアルゴリズムをプログラミングする必要があります。

私は、ほぼ完成していますが、私はまだ大きな問題があることを願っています：私が実行したときそれは、最後のいくつかの手紙に止まり、「回転する」ことはありません。

私のブランチは正しいと思います。私はスタック割り当てに何か問題があると思いますが、解決方法はわかりません。ほとんど一週間試してみましたが、一週間しか残っていません。

私はあなたの問題を解決するのに役立つことを願っています。

.data 

word1: .asciiz "teflon" 
word2: .asciiz "telefon" 
newLine: .asciiz "\n" 

.text 
.globl main 

# $a0 : word 1 
# $a1 : word 2 
# returns via $v0 : best alignment score 
#s0- current word1-char , s1- current word2-char , s2-word1-length, s3-word2-length,s5-recursion-counter,t2-temporary-result, 
#t3-temporary-result, t4-temporary-result 


needleman_wunsch: 

    # Fuegen Sie Ihren Code zum Beispiel hier ein. 
    # Auch der restliche Inhalt dieser Datei darf 
    # von Ihnen nach Belieben angepasst werden. 
    add $v0,$0,$0   #result=0 
    add $s5,$0,$0   #counter=0 
    add $t2,$0,$0   #result1=0 
    add $t3,$0,$0   #result2=0 
    add $t4,$0,$0   #result3=0 

rekursionsadresse: 

    addi $s5,$s5,1   #counter++ 
    #addi $a0,$a0,1   #$s0=&word1[i] 
    #addi $a1,$a1,1   #$s1=&word2[j] 
    lb $s0,0($a0)   #$s0=word1[i] 
    lb $s1,0($a1)   #$s1=word1[j] 
    add $t0,$a0,$0   #save $a0 in $t0 
    add $t1,$v0,$0   #save $v0 in $t1 

# move $a0,$s0   #load string adress in to $a0 
# li $v0,11    #load syscall for string printing 
# syscall     #print string 
# move $a0,$s1   #load string adress in to $a0 
# syscall     #print string 
# move $a0,$t1   #load current result into $a0 
# li $v0,1    #load syscall to integer printing 
# syscall     #print current result 
    move $a0,$s5 
    li $v0,1 
    syscall     #print counter 
# la  $a0, newLine 
# addi $v0, $0, 4 
# syscall 

    move $a0,$t0   #restore $a0 
    move $v0,$t1   #restore $v0 
    move $t1,$a1   #store $a1 

    move $a0,$t0   #restore $a0 
    move $a1,$t1   #restore $a1 

    beqz $s0,if10   #if |word1| == 0 goto if10 
    beqz $s1,if01   #if |word2| == 0 goto if01 ; case |word1| >=1 and |word2|>=1 



#calculate result1 (score(word1[i+1],word2[j+1])+eq(word1[0],word2[0])) 

    addi $sp,$sp,-12  #stackreservation for 3 values 
    sw $ra,8($sp)   #save $ra on stack 
    sw $a1,4($sp)   #save $a1 on stack 
    sw $a0,0($sp)   #save $a0 on stack 

    addi $a0,$a0,1   #get next character 
    addi $a1,$a1,1   #get next character 
    jal rekursionsadresse #$v0=score(word1[i+1],word2[j+1]) 

    lw $a0,0($sp)   #load $a0 from stack 
    lw $a1,4($sp)   #load $a1 from stack 
    lw $ra,8($sp)   #load $ra from stack 
    addi $sp,$sp,12   #restore stackpointer 
eq: 
    lb $s0,0($a0)   #load current character from word1 
    lb $s1,0($a1)   #load current character from word2 
    bne $s0,$s1,neq  #if chars are not equal goto not equal (neq) 
    addi $v0,$v0,4   #increase result by 4 
    j marker    #jump to marker 
neq: 
    addi, $v0,$v0,-2  #decrease result by 2 

marker: 

    move $t2,$v0   #store return result1 


#calculate result2 (score(word1[i],word2[j+1])-3) 


    addi $sp,$sp,-12  #stackreservation for 3 values 
    sw $ra,8($sp)   #save $ra on stack 
    sw $a1,4($sp)   #save $a1 on stack 
    sw $a0,0($sp)   #save $a0 on stack 

    addi $a1,$a1,1   #get next character 
    jal rekursionsadresse #$v0=score(word1[i],word2[j+1]) 
    addi $v0,$v0,-3   #$v0=score(word1[i],word2[j+1])-3 

    lw $a0,0($sp)   #load $a0 from stack 
    lw $a1,4($sp)   #load $a1 from stack 
    lw $ra,8($sp)   #load $ra from stack 
    addi $sp,$sp,12   #restore stackpointer 
    move $t3,$v0   #save result3 

#calculate result3 (score(word1[i+1],word2[j])-3) 


    addi $sp,$sp,-12  #stackreservation for 3 values 
    sw $ra,8($sp)   #save $ra on stack 
    sw $a1,4($sp)   #save $a1 on stack 
    sw $a0,0($sp)   #save $a0 on stack 

    addi $a0,$a0,1   #word1-index i +=1 
    jal rekursionsadresse #$v0=score(word1[i+1],word2[j]) 
    addi $v0,$v0,-3   #$v0=score(word1[i+1],word2[j])-3 

    lw $a0,0($sp)   #load $a0 from stack 
    lw $a1,4($sp)   #load $a1 from stack 
    lw $ra,8($sp)   #load $ra from stack 
    addi $sp,$sp,12   #restore stackpointer 
    move $t4,$v0   #save result3 


#compare the 3 results 
    bgt $t2,$t3,ifmax  #if result1 > result2 goto max3 
    bgt $t4,$t3,max3  #if result3 > result2 goto max3 
    move $v0,$t3   #store biggest result in $v0 
    jr $ra    #return to needleman_wunsch 
ifmax: 
    bgt $t4,$t2,max3  #if result3 > result1 goto max3 
    move $v0,$t2   #store biggest result in $v0 
    jr $ra    #return to needleman_wunsch 
max3: 
    move $v0,$t4   #store biggest result in $v0 
    jr $ra    #return to needleman_wunsch 


if01:      #case |word1| >=1 and |word2|==0  
    addi $sp,$sp,-12  #stackreservation for 3 values 
    sw $ra,8($sp)   #save $ra on stack 
    sw $a1,4($sp)   #save $a1 on stack 
    sw $a0,0($sp)   #save $a0 on stack 

    addi $a0,$a0,1   #get next character 
    jal rekursionsadresse #$v0=score(word1[i+1],word2[j]) 
    addi $v0,$v0,-3   #$v0=score(word1[i+1],word2[j])-3 

    lw $a0,0($sp)   #load $a0 from stack 
    lw $a1,4($sp)   #load $a1 from stack 
    lw $ra,8($sp)   #load $ra from stack 
    addi $sp,$sp,12   #restore stackpointer 
    jr $ra    #jump back to last method 

if10:      #case |word1| == 0 
    beqz $s1,if11   #if |word2|==0 goto if1.1 ;case |word1| ==0 and |word2|>=1 

    addi $sp,$sp,-12  #stackreservation for 3 values 
    sw $ra,8($sp)   #save $ra on stack 
    sw $a1,4($sp)   #save $a1 on stack 
    sw $a0,0($sp)   #save $a0 on stack 

    addi $a1,$a1,1   #get next character 
    jal rekursionsadresse #$v0=score(word1[i],word2[j+1]) 
    addi $v0,$v0,-3   #$v0=score(word1[i],word2[j+1])-3 

    lw $a0,0($sp)   #load $a0 from stack 
    lw $a1,4($sp)   #load $a1 from stack 
    lw $ra,8($sp)   #load $ra from stack 
    addi $sp,$sp,12   #restore stackpointer 
    jr $ra    #jump back to last method 

if11:      #case |word1| ==0 and |word2|==0 
    add $v0,$0,$0   #return 0 
    jr $ra    #jump back to last method 




main: 
    addi $sp, $sp, -4 
    sw $ra, 0($sp) 

    la $a0, word1 
    la $a1, word2 
    jal needleman_wunsch 

    # Geben Sie auf jeden Fall den Score auf der 
    # Konsole aus. 
    addi $a0, $v0, 0 
    li $v0, 1 
    syscall 

    lw $ra, 0($sp) 
    addi $sp, $sp, 4 
    jr $ra 

Answer 1

申し訳ありませんが、非常に速いです。 友人の助けを借りて私が見つけた解決策は、$ t2のような余分なレジスタに戻り結果を格納することです。

Answer 2

ソリューションを見つけましたか？ は多分これは必要ありません。

move $a0,$t0   #restore $a0 
move $v0,$t1   #restore $v0 
->move $t1,$a1   #store $a1 

move $a0,$t0   #restore $a0 
->move $a1,$t1   #restore $a1 

あなたは$ T1に$ A1を格納し、2行、後でそれを復元なぜ？