Ханойские Башни в Ассамблее MIPS - PullRequest
Новая
       48

Ханойские Башни в Ассамблее MIPS

0 голосов
/ 04 мая 2018

Я бы хотел реализовать алгоритм Hanoi Towers в сборке MIPS.

Стержни обозначены A, B и C.

Ввод - количество дисков, а выход - последовательность ходов, необходимых для решения проблемы.

Например: Если ввод 3, вывод должен быть: 

A>C
A>B
C>B
A>C
B>A
B>C
A>C

Мне удалось получить результат с номерами стержней, т.е. 1>3 вместо A>C, со следующим кодом: 

.data

NewLine: .asciiz      "\n"
To: .asciiz      ">"

.globl main
.text  

main:

  li $v0, 5
  syscall
  add $a0, $v0, $zero 

  addi $a1, $zero, 1        
  addi $a2, $zero, 3        
  addi $a3, $zero, 2        
  jal hanoi1

  li $v0, 10            
  syscall

hanoi1:        

  addi $t0, $a0, 0  
  addi $t1, $zero, 1
  bne $a0, $t1, hanoi2
  li $v0, 1             
  move $a0, $a1
  syscall
  li $v0, 4         
  la $a0, To
  syscall
  li $v0, 1             
  move $a0, $a2
  syscall
  li $v0, 4         
  la $a0, NewLine
  syscall
  addi $a0, $t0, 0      
  jr $ra

hanoi2:

  addi $sp, $sp, -20

  sw $ra, 16($sp)
  sw $a3, 12($sp)       
  sw $a2, 8($sp)    
  sw $a1, 4($sp)    
  sw $a0, 0($sp)        

  addi $t3, $a3, 0      
  addi $a3, $a2, 0      
  addi $a2, $t3, 0      
  addi $a0, $a0, -1             
  jal hanoi1   

  lw $ra, 16($sp)
  lw $a3, 12($sp)       
  lw $a2, 8($sp)        
  lw $a1, 4($sp)        
  lw $a0, 0($sp)        

  addi $t0, $a0, 0      
  addi $t1, $zero, 1
  li $v0, 1             
  move $a0, $a1
  syscall
  li $v0, 4         
  la $a0, To
  syscall
  li $v0, 1             
  move $a0, $a2
  syscall
  li $v0, 4         
  la $a0, NewLine
  syscall
  addi $a0, $t0, 0      

  addi $t3, $a3, 0      
  addi $a3, $a1, 0      
  addi $a1, $t3, 0      
  addi $a0, $a0, -1             
  jal hanoi1 
  lw $ra, 16($sp)

  addi $sp, $sp, 20

  add $v0, $zero, $t5
  jr $ra

Я пытался добавить ярлыки, такие как: 

PrintA:
  li  $v0, 4 
  la  $a0, A
  syscall
  jr $ra

И добавьте beq к ветке с правой меткой: 

beq $a1, $t7, PrintA # $t7=1
beq $a1, $t8, PrintB # $t8=2
beq $a1, $t9, PrintC # $t9=3

Но программа попала в бесконечный цикл, возможно потому, что я неправильно обработал $ra.

Так что моя проблема в том, что я не могу понять, как преобразовать числа стержней в буквы.

Буду признателен за любую помощь.

1 Ответ

0 голосов
/ 04 мая 2018

Чтобы использовать jr $ra для возврата куда-либо, вы должны сначала установить регистр $ra с адресом для возврата, это то, что делает jal перед ветвлением, помещая адрес следующей инструкции в ra.

т.е. использовать это: 

    beq $a1, $t7, PrintA # $t7=1
    beq $a1, $t8, PrintB # $t8=2
    beq $a1, $t9, PrintC # $t9=3

с вариантами PrintA/B/C, оканчивающимися на jr $ra, означает, что если вы не хотите печатать что-либо там, следующая инструкция вместо блока beq тоже будет jr $ra, заканчивая этот поток кода.

Затем вы можете сделать это так: 

    move $a0, <number of rod (from)>
    # make sure you have current `ra` stored in stack to not lose it
    jal  print_rod    # will set ra to address of next line
    ... continue with printing "To" string
    ... and then you can reuse the same subroutine to display second rod
    move $a0, <number of rod (to)>
    jal  print_rod    # will set ra to address of next line
    ... do remaining things (? if any), restore ra, continue

И поместите число стержня в преобразование букв в подпрограмму print_rod. Это может выглядеть как 3x beq с тремя разными хвостами и с использованием jr $ra для возврата из каждого варианта обратно в приведенный выше код, но если вы подумаете об этом с точки зрения математики и сборки, вы конвертируете значения [ 1, 2, 3] на буквы [A, B, C].

Существует syscal, v0=11 «печатный символ», и в качестве аргумента a0 требуется символ ASCII.

Если вы проверите таблицу кодирования ASCII, вы увидите, что буква A кодируется как значение 65, B равно 66 и C равно 67. И ваш ввод - значение 1, 2 или 3. Во всех случаи для преобразования числового значения стержня в букву ASCII, вам нужно только добавить +64 к нему.

т.е. ваш текущий способ отображения номера стержня: 

  li $v0, 1
  move $a0, $a1
  syscall

Нужна только небольшая модификация: 

  li     $v0, 11       # print character service
  addi   $a0, $a1, 64  # number to ASCII letter (1->A, 2->B, 3->C)
  syscall

И все, ветвления нет (ветвление обычно медленнее, чем при простом вычислении, например addi).

Ваш текущий источник имеет разные части кода, которые идентичны другим, вы хотите снова потратить некоторое время, пытаясь понять, какие части кода отличаются, и оставить только те, и использовать один код для идентичного пути, либо извлекая это идентичный код в подпрограмме (используя его с помощью jal subroutine+jr $ra) или перестановка потока кода, чтобы он был похож на: 

  # something to be done in every iteration
  # if (next_part_should_not_execute) branch to skip_part_2
  # part 2 of code - being run just under certain condition
skip_part_2:
  # if (next_part_should_not_execute) branch to skip_part_3
  # part 3 of code - being run just under certain other condition
skip_part_3:
  # part 4 of code, being run every iteration, unconditionally

Таким образом, вам все еще нужна только одна копия инструкции «часть 4» в источнике, но части 2 и 3 будут выполняться только при выполнении определенных условий.

...