1

我正在将以下递归 java 程序转换为 MIPS asm。该算法计算所有可能的数字排序/排列。但是递归调用在 for 循环中。我需要在我的 MIPS 版本中保留变量“i”，但我不知道在哪里添加它。我的算法是正确的，只是我的 $t0（即“i”）永远不会重置为 0。我只是不知道如何/在何处将其保存在堆栈中或何时将其从堆栈中取出。任何帮助表示赞赏。

import java.util.Arrays;


public class Test 
{
    private static void swap(int[] v, int i, int j) 
    {
        int t = v[i]; 
        v[i] = v[j]; 
        v[j] = t;
    }

    public void permute(int[] v, int n) 
    {
        if (n == 1) 
            System.out.println(Arrays.toString(v));
        else 
        {
            for (int i = 0; i < n; i++) 
            {
                permute(v, n-1);
                if (n % 2 == 1) 
                    swap(v, 0, n-1);
                else 
                    swap(v, i, n-1);
            }
        }
    }

    public static void main(String[] args) 
    {
        int[] ns = {1, 2, 3, 4};
        new Test().permute(ns, ns.length);
    }

}

和 mips 函数注意：我正在排列字符串，而不是整数，但算法是相同的。

#----------------------------------------------
# anagram - Prints all the permutations of 
# the given word
#     a0 - the word to compute the anagrams
#     s0 - n, the length of the word
#     a1 - n - 1 (length-1)
#----------------------------------------------
anagram:
addi $sp, $sp, -16

sw $a0, 0($sp)
sw $a1, 4($sp)
sw $s0, 8($sp)
sw $ra, 12($sp)

add $s0, $a1, $zero         # this is n

addi $a1, $s0, -1           # n-1
beq $s0, 1, printS
init: move $t0, $zero       # t0 = i = 0
logic: slt $t1, $t0, $s0        # Set t1 = 1 if t0 < length
       beqz $t1, endAnagram     # if it's zero, it's the end of the loop

jal anagram

li $t2, 2
div $s0, $t2
mfhi $t3

beqz $t3, even          # if even branch to even, otherwise it will go to odd
odd: # swap the n-1 char with the first
add $t4, $a0, $zero
add $t5, $a0, $a1

lb $t6, 0($t4)          # first char
lb $t7, 0($t5)          # n-1 char

sb $t7, 0($t4)          # swap the two
sb $t6, 0($t5)

j inc # skip the even section

even: # swap the ith char with n-1 char
add $t4, $a0, $t0           # ith char
add $t5, $a0, $a1           # n-1 char

lb $t6, 0($t4)          # ith char
lb $t7, 0($t5)          # n-1 char

sb $t7, 0($t4)          # swap the two
sb $t6, 0($t5)

inc: addi $t0, $t0, 1           # t0++;
j logic

endAnagram:
# reset stack pointers
lw $a0, 0($sp)
lw $a1, 4($sp)
lw $s0, 8($sp)
lw $ra, 12($sp)
addi $sp, $sp, 16           # adjust stack
jr $ra

printS: # print string and jump to return
   jal printString # calls printString function which prints the string

   j endAnagram
4

1 回答 1

1

$t0根据约定，跨子例程调用不保留，您似乎遵循该约定。因此，您有两个选择：

  1. 您可以存储i在保留的寄存器中，在这种情况下，您需要自己在序言/尾声中保留该寄存器。您已经为$s0.
  2. 或者您将$t0自己保存在堆栈中，围绕子程序调用

在这两种情况下，您都需要为当地人提供额外的空间，因此请更改addi $sp, $sp, -16为addi $sp, $sp, -20（以及尾声中的匹配代码）。如果您选择选项 #1，例如使用$s1存储i. 添加代码以保存和恢复$s1，就像您为$s0. 如果您选择选项 #2，请在 之前添加jal anagram写入$t0堆栈的代码jal，然后在之后重新加载它。

于 2012-11-29T22:19:56.337 回答