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慣例に従ってサブルーチン呼び出し全体で保持されず、その慣習に従っているようです。そのため、次の 2 つの選択肢があります。

  1. iプロローグ/エピローグで自分でレジスタを保存する必要がある場合は、保存されているレジスタに保存します。に対して既にこれを行っています$s0。
  2. $t0または、サブルーチン呼び出しの前後でスタックに自分自身を保存します

どちらの場合も、ローカル用に追加のスペースが必要になるため、(エピローグの一致するコードと共に) に変更addi $sp, $sp, -16します。addi $sp, $sp, -20オプション #1 を選択した場合は、たとえば、を使用し$s1て保存しiます。$s1の場合と同様に、保存および復元するコードを追加します$s0。オプション #2 を選択した場合は、の前にスタックにjal anagram書き込み、後で再ロードするコードを の周りに追加します。$t0jal

于 2012-11-29T22:19:56.337 に答える