如何在 MIPS 中遍历二进制堆？

Question

.data

decoder_heap: .asciiz "_ETIANMSURWDKGOHVF*L*PJBXCYZQ**54*3***2&*+****16=/***(*7***8*90"
str_eingabe: .asciiz "morse_in:"
str_ausgabe: .asciiz "\ntext_out: "
str_rueckgabewert: .asciiz "\nRueckgabewert: "
buf_out: .space 256

.text

.eqv SYS_PUTSTR 4
.eqv SYS_PUTCHAR 11
.eqv SYS_PUTINT 1
.eqv SYS_EXIT 10

main:
    
    li $v0, SYS_PUTSTR
    la $a0, str_eingabe
    syscall

    li $v0, SYS_PUTSTR
    la $a0, test_msg
    syscall
    
    li $v0, SYS_PUTSTR
    la $a0, str_rueckgabewert
    syscall

    move $v0, $zero


    la $a0, decoder_heap
    la $a1, test_msg
    la $a2, buf_out
    jal morse
    
    
    move $a0, $v0
    li $v0, SYS_PUTINT
    syscall
    
    li $v0, SYS_PUTSTR
    la $a0, str_ausgabe
    syscall
    
    li $v0, SYS_PUTSTR
    la $a0, buf_out
    syscall

    
    li $v0, SYS_EXIT
    syscall

.data

test_msg: .asciiz ".... .- .-.. .-.. ---"

.text

morse:

    lb $t0, 0($a1)
    
    beq $t0, '\0', exit

decoderLoop:

    lb $t0, 0($a1)
    
    beq $t0, ' ', positionInHeap
    beq $t0, '\0', positionInHeap
    
    #
    
    beq $t0, '.', isDot
    beq $t0, '-', isDash
    
    j exit
    
isDot:

    #
    
    addi $a1, $a1, 1
    j decoderLoop

isDash:

    #
    
    addi $a1, $a1, 1
    j decoderLoop


positionInHeap: blt $a0, 63, positionInHeap

    lb $t1, 0($a0)
    sb $t1, 0($a2)
    
    addi $a1, $a1, 1
    addi $a2, $a2, 1
    addi $v0, $v0, 1
    
    j morse

exit:
    
    jr $ra
    

所以这是一项家庭作业，我已经走到了这一步，但我在某一时刻确实很挣扎。我已经在 MIPS-Assembler 中编写了这段代码，汇编器对我来说仍然很新。我已经了解了这门语言的基础知识，但我还有很多东西需要学习。

此代码将莫尔斯电码解码为 ASCIIZ 字符串输出。我们不允许修改标签“morse”上方的代码（仅限“test_msg”），并且我们还必须准确使用这些寄存器。因此，我认为如果我能够正确找到“decoder_heap”中每个点和破折号的索引，我的代码就可以工作。 “decoder_heap”是一个二叉堆，要选择当前节点的左子节点，如果读取到一个点，则必须设置 k = 2k + 1。右节点也是如此；如果读取了破折号，则设置 k = 2k + 2，其中 k 是当前索引。我完全对这个k感到困惑。

我的第一次尝试是在 $a0 中添加 $a0 和 $a0，并添加 1 表示点，添加 2 表示破折号。但我得到了算术溢出。我非常感谢您在这方面的帮助。非常感谢您考虑我的请求。

我也想过将 $a0 + $a0 存储在寄存器中，就像 $t2 一样，但这仍然不起作用。

这是修订版：

morse:

    lb $t0, 0($a1)
    
    beq $t0, '\0', exit
    
    li $t2, 0
    
decoderLoop:

    lb $t0, 0($a1)
    
    beq $t0, ' ', positionInHeap
    beq $t0, '\0', positionInHeap
    
    add $t2, $t2, $t2
    
    addi $t2, $t2, 1
    
    beq $t0, '.', isDot
    beq $t0, '-', isDash
    
    j exit
    
isDot:
    
    addi $a1, $a1, 1
    j decoderLoop

isDash:

    add $t2, $t2, 1
    addi $a1, $a1, 1
    j decoderLoop


positionInHeap:
    
    add $a0, $a0, $t2

    lb $t1, 0($a0)
    sb $t1, 0($a2)
    
    addi $a1, $a1, 1
    addi $a2, $a2, 1
    addi $v0, $v0, 1
    
    j morse

exit:
    
    jr $ra

Answer 1

.data

test_msg: .asciiz ".... .- .-.. .-.. ---"

.text

morse: 

    lb $t0, 0($a1)
    
    beq $t0, '\0', exit 
    
    la $a0, decoder_heap 
    
    li $t2, 0 
    
    
decoderLoop:

    lb $t0, 0($a1)
    
    bge  $t2, 63, ignoreMorse
    
    
    beq $t0, ' ', positionInHeap
    beq $t0, '\0', positionInHeap
    
    add $t2, $t2, $t2
    
    addi $t2, $t2, 1
    
    beq $t0, '.', isDot
    beq $t0, '-', isDash
    
    j exit
    
isDot:
    
    addi $a1, $a1, 1
    j decoderLoop

isDash: 
    add $t2, $t2, 1
    addi $a1, $a1, 1
    j decoderLoop


positionInHeap: 
    
    add $a0, $a0, $t2 # Die Adresse des ASCIIZ Zeichens wird ermittelt

    lb $t1, 0($a0)
    sb $t1, 0($a2)
    
    addi $a1, $a1, 1 
    addi $a2, $a2, 1 
    addi $v0, $v0, 1 
    
    j morse
    
ignoreMorse: 

    addi $a1, $a1, 1
    
    j morse

exit: 
    
    jr $ra

所以，主要问题是我无法弄清楚如何正确索引解码器堆。结果我必须分别存储和计算索引。我还重置了以下莫尔斯电码的索引和指针。

再次感谢杰斯特的帮助！