Mips Needleman 递归
Mips Needleman Recursion
对于我的大学，我必须在 Mips 汇编中编写一个特定的 Needleman 算法：
我希望我快完成了，但是，我还有一个大问题：当我运行它的时候，它不会停止并且"rotates"放在最后几个字母上。
我认为我的分支是正确的，我的堆栈分配有问题，但我不知道如何解决，我几乎尝试了将近一周，只剩下一周了。
所以我希望你能帮助我解决我的问题。
.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,[=10=],[=10=] #result=0
add $s5,[=10=],[=10=] #counter=0
add $t2,[=10=],[=10=] #result1=0
add $t3,[=10=],[=10=] #result2=0
add $t4,[=10=],[=10=] #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,[=10=] #save $a0 in $t0
add $t1,$v0,[=10=] #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, [=10=], 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,[=10=],[=10=] #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
你找到解决办法了吗？
也许这不是必需的：
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
为什么将$a1 存储在$t1 中并在两行后恢复它？
抱歉没有这么快回答。
我找到的解决方案（在朋友的帮助下）是将 return 结果存储在一个额外的寄存器中，例如 $t2.
对于我的大学，我必须在 Mips 汇编中编写一个特定的 Needleman 算法：
我希望我快完成了，但是，我还有一个大问题：当我运行它的时候，它不会停止并且"rotates"放在最后几个字母上。
我认为我的分支是正确的，我的堆栈分配有问题，但我不知道如何解决，我几乎尝试了将近一周，只剩下一周了。
所以我希望你能帮助我解决我的问题。
.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,[=10=],[=10=] #result=0
add $s5,[=10=],[=10=] #counter=0
add $t2,[=10=],[=10=] #result1=0
add $t3,[=10=],[=10=] #result2=0
add $t4,[=10=],[=10=] #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,[=10=] #save $a0 in $t0
add $t1,$v0,[=10=] #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, [=10=], 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,[=10=],[=10=] #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
你找到解决办法了吗？ 也许这不是必需的：
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
为什么将$a1 存储在$t1 中并在两行后恢复它？
抱歉没有这么快回答。 我找到的解决方案（在朋友的帮助下）是将 return 结果存储在一个额外的寄存器中，例如 $t2.