MIPS完全置换失败

Question

我有一个任务将以下代码转换为汇编（MIPS），我可以做所有其他部分但返回部分因为我基本上不知道如何保存前一个i的值。

#include <stdio.h>
#include <stdlib.h>

int symbol[7], array[7];
int n;

void FullArray(int index)
{
    int i;
    if(index>=n)
    {
        for(i=0;i<n;i++)
        {
            printf("%d ",array[i]);
        }
        printf("\n");
        return;
    }
    for(i=0;i<n;i++)
    {
        printf("here4");
        if(symbol[i]==0)
        {
            array[index] = i+1;
            symbol[i]=1;
            FullArray(index+1);
            symbol[i]=0;
        }
    }
}
int main(void)
{
    int i;
    scanf("%d", &n);
    FullArray(0);
    return 0;
}

这是我的MIPS代码：

.data
    array: .space 28
    symbol:.space 28
    ispace:     .asciiz " "
    ienter:     .asciiz "\n"
.text
    li $v0, 5
    syscall
    move $t0, $v0

    move $s0, $t0 #n
    move $s1, $zero #index
    move $s2, $zero #i=0
    move $s5, $zero
    j fullarray

fullarray:
    bge $s1, $s0, print #if index is larger or equal to n, go to print loop
    j always

print:
    move $s2, $zero #i=0
    j print2

print2:
    bge $s2, $s0, always #while i<n

    move $s3, $s2
    add $s3, $s3, $s2
    sll $s3, $s3, 1

    lw $t0, array($s3)

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

    la $a0, ispace
    li $v0, 4
    syscall

    addi $s2, $s2, 1
    blt $s2, $s0, print2

    la $a0, ienter
    li $v0, 4
    syscall

    jr $ra

always:
    move $s2, $zero #i=0
    j always2

always2:
    bge $s2, $s0, end #while i<n

    move $s3, $s2
    add $s3, $s3, $s2
    sll $s3, $s3, 1

    lw $t0, symbol($s3) #load symbol of the current array number
    beq $t0, $zero, storearray #store array value
    addi $s2, $s2, 1 #i++
    blt $s2, $s0, always2
    j end

storearray:
    move $s4, $s1
    add $s4, $s4, $s1
    sll $s4, $s4, 1

    addi $t2, $s2, 1 #set array number to i+1
    sw $t2, array($s4)

    addi $t2, $zero, 1
    sw $t2, symbol($s3) #set the symbol of the current array number to 1

    sub $sp, $sp, 12
    sw $ra, 0($sp)  #save $ra
    sw $s1, 4($sp) #save index
    sw $s2, 8($sp)

    addi $s1, $s1, 1 #index + 1

    jal fullarray

    lw $s1, 4($sp)
    lw $s2, 8($sp)

    lw $ra, 0($sp)
    add $sp, $sp, 12

    move $s4, $s1
    add $s4, $s4, $s1
    sll $s4, $s4, 1

    move $s2, $s1
    move $s3, $s2
    add $s3, $s3, $s2
    sll $s3, $s3, 1

    sw $zero, symbol($s3) #set the symbol of current array number to 0
    addi $s2, $s2, 1 #i++
    blt $s2, $s0, always2
    beq $s1, $zero, end
    jr $ra

end:

预期输出示例为：

（输入= 4）

1 2 3 4

1 2 4 3

1 3 2 4

1 3 4 2

1 4 2 3

1 4 3 2

2 1 3 4

2 1 4 3

2 3 1 4

2 3 4 1

等等

但我的代码总是让我回头

1 2 3 4

1 2 4 3

1 2 4 3

1 2 4 3

...

1 2 4 3

请帮忙！

Answer 1

我建议尝试从头开始再写一次。

您当前的MIPS代码使用s0, s1, ...作为全局变量，这对于非递归代码非常合理，但递归通常基于编写代码的本地/功能方式。

而你的错误来自滥用s#寄存器，多次不小心添加无用的指令和冗余计算，直到你最终偶然修改你原本想要保留的东西。

一些草图如何（我将）组织代码：

---

main part

Init s0 = n，这个作为“全局变量”，不需要改变。

但在那之后尝试模仿C-like函数调用fullArray(0);：

start:
    # read N from user, set $s0 to N
    ...

    # call recursive function fullarray with argument value 0
    move $a0, $zero  # first argument "index" = 0
    jal fullarray    # call the function (not jump)

    li   $v0,10      # exit syscall
    syscall

这部分与你的相似，但是你输入fullarray而不是j，所以你将很难有时间终止整个代码，而原始的C算法只会耗尽所有嵌套循环并返回jal，不需要在main内终止条件的额外测试。

并且在跳入函数之前初始化函数的LOCAL变量。这应该听起来很奇怪，在编写源代码时尝试遵循“局部性”原则，当事物通常在源中准确写入它们所属/正在使用的位置时。局部变量应该在函数内初始化（并且接近它们的实际使用，而不是前面的很多行）。当你知道你不会再调用一些可以修改它们的子程序时，你应该使用非保留的fullarray寄存器作为本地人。

（这只是惯例，因为程序员编写代码负责保存$t#寄存器，它们与$s#寄存器在物理上相同，CPU没有任何区别......但是经验丰富的MIPS汇编程序员会考虑它们有点不同，阅读源时）

---

$t# function overview design

让我们使用常见的调用约定，其中fullarray包含函数的参数，a0是返回地址，函数不应该修改$ra寄存器。

$s#

（发布之前的“编辑”：在实现时，我注意到我已经计划在头部保留

fullarray:
    if (a0 "index" >= N) { print_array; return; }
    preserve in stack: $ra (return address) and $s1 (will be modified)
    for (s1 : all_possible_symbols) {  // that's range 1..N
        if (symbol s1 is used already) continue;
        mark symbol s1 as used;
        array[a0 "index"] = s1;
        fullarray(index + 1); // <=> ++a0; jal fullarray; --a0;

        // because symbol ("i" variable) is in $s1, it is still valid even here!
        // (if function fullarray() is correct and preserves $s# registers)

        // EDIT: in common convention function is allowed to modify a0,
        // but this design expect it to be preserved! (sort of bug)

        unmark symbol s1 (is unused now);
    } //for(all symbols s1 on position "index")
    restore $ra and $s1 and $sp
    jr $ra

以简化/性能原因，但公共调用约定不要求，所以这是自定义调用约定）

---

$a0 function implementation - first try

让我有点奇怪，你已经有多少代码，虽然听起来很简单。现在我会在第一个版本中将其重写为asm，如下所示：

（注意我使用fullarray数组用于byte和array，因为最大N只有7，所以不需要使用symbol值，它简化了索引，不需要* 4来计算地址）

word

这是关于“fullarray：”函数的核心（没有打印）的约20个伪指令。你的核心部分有大约40个伪指令。但是大多数每条指令都应该与原始算法/意图明确连接，只有在MIPS汇编不允许单指令实现的情况下只需要很少的帮助指令（比如

fullarray:
    # extra requirement for this fullarray function: preserve also $a0!

    # if (a0 "index" >= N) { print_array; return; }
    bge $a0, $s0, print_array

    # preserve in stack: $ra (return address) and $s1 (will be modified)
    addi $sp, $sp, -8
    sw   $ra, 0($sp)  #save return address
    sw   $s1, 4($sp)  #preserve old $s1 value

    # for (s1 : all_possible_symbols) {  // that's range 1..N
    # this will be actually do {} while() loop, because we know N is valid (the main should test input!)
    move $s1, $zero   # s1 = current symbol index, going from zero to N-1 (symbol = index+1)
symbol_loop:
    #here: s0 = N, s1 = symbol index, a0 = array index

    # if (symbol s1 is used already) continue;
    lb   $t0, symbol($s1)
    bnez $t0, symbol_loop_advance

    # mark symbol s1 as used (by N value, any non-zero value is good, N is non-zero and in $s0)
    sb   $s0, symbol($s1)

    # array[a0 "index"] = s1;
    addi $t0, $s1, 1      # t0 = symbol value (= symbol_index+1) (avoiding $s# usage for temporary)
    sb   $t0, array($a0)  # array[a0] = symbol

    # call fullrray(index+1) recursively
    addi $a0, $a0, 1
    jal  fullarray
    addi $a0, $a0, -1

    # unmark symbol s1 (is unused now)
    sb   $zero, symbol($s1)

    # end of for/do_while loop
symbol_loop_advance:
    addi $s1, $s1, 1      # next symbol index
    blt  $s1, $s0, symbol_loop   # while(symbol_index < N);

    # restore $ra and $s1 and $sp ($a0 is also preserved, that's extra requirement)
    lw   $ra, 0($sp)  #restore return address
    lw   $s1, 4($sp)  #restore old $s1 value
    addi $sp, $sp, 8

    # return from function
    jr $ra

print_array:
    # extra requirement for this fullarray function: preserve also $a0!
    #TODO printing (don't modify any $s# register, or $ra)
    jr $ra  # return

必须先从内存中获取值，然后才能测试它） 。

---

if (symbol[i]) function implementation - improvements suggestions

现在汇编主要是关于性能（有时在汇编中编写代码的另一个好理由是代码的大小）。在MIPS上，通常代码大小会直接影响性能。

如果要检查该函数的反汇编，在本机MIPS指令中（在编译后在MARS：“执行”选项卡中的“基本”列中），您将注意到fullarray / symbol内存使用周围的部分确实增长了很多。在MIPS上加载地址并不简单，你还有一些备用的array寄存器，所以你可以使用一些替换全局值，只加载一次符号/数组地址，如：

$s#

然后在函数内部，您可以重用该值进行寻址：

    # somewhere in main before calling fullarray(0)
    la   $s6, symbol
    la   $s7, array

这将产生更少的本机MIPS指令=更小更快的代码。

同样，当最大N为7时，你可以完全摆脱

    # if (symbol s1 is used already) continue;
    addu $t1, $s6, $s1    # t1 = symbol($s1)
    lb   $t0, ($t1)
    bnez $t0, symbol_loop_advance

    # mark symbol s1 as used (by N value, any non-zero value is good, N is non-zero and in $s0)
    sb   $s0, ($t1)

    # array[a0 "index"] = s1;
    addu $t1, $s7, $a0    # t1 = array($a0)
    addi $t0, $s1, 1      # t0 = symbol value (= symbol_index+1) (avoiding $s# usage for temporary)
    sb   $t0, ($t1)       # array[a0] = symbol

数组，并使用存储在寄存器中的位图，通过特定位设置/未设置来标记符号的使用（MIPS寄存器是32位大，所以这将很容易地工作到N = 32）。

并且我会调整+1发生的位置（符号索引与屏幕上的符号），通常在ASM / C编程中，您希望事物从0开始，并以N-1结束，因此我将在symbol中生成符号0的排列..N-1，并对打印部件中的人1..N符号执行+1修复，只需重新格式化输出。

如果它是我的代码，我会将符号重命名为更有意义的东西，例如：

array

用编程语言编写代码时，请始终对其进行编辑，直到它读得很好。想象一下，你是程序员，他没有编写原始的源代码，但需要帮助他的同事，或修复其他人的代码中的错误 - 以这样的心态阅读你的代码，看看哪些不是很清楚，什么可以更好地评论（主要是“意图”代码的一小部分应该实现），函数/变量的名称是有意义的，代码需要更多的空白区域以便更具可读性等。

在源代码写入易于阅读的源中投入时间将在调试和维护阶段快速返回。通常，源的读取/编辑次数比写入的次数多很多倍。

---

另外，我甚至会更积极地重用/保留寄存器中的值，避免内存，并避免递归（因为根本不需要这个任务， 它甚至使它变得更难 ）。我会以这样的代码结束：

how it would look written by me

array = permutation
symbol = used_symbols
fullarray = permutate_position
print = show_permutation
print2 = show_permutation_symbol
...etc...

在编写之后，实际上非递归版本的控制流程更加难以理解，花了相当长的时间来编写它，并且谢天谢地第一次尝试，所以我没有调试它（但这就是为什么它需要很多时候写它，大概约2小时，直到我设法清理它，它有意义，并很好地融合在一起）。

但从性能的角度来看，这是大约200B长的代码，你的大约是350B。执行指令的总量也会低很多，因为我一直在内存中存储/恢复符号是其使用位掩码，而不是触及堆栈。 （虽然输出到控制台的“打印整数”会使它实际上与原始代码一样慢...如果我会考虑任务的“打印”部分 - 我认为只有排列生成器是主要焦点 - 我会改变置换生成器直接生成整行字符串，改变ASCII字母本身，而不是整数元素，这将删除需要“打印整数”调用，这是迄今为止执行最复杂的代码（遗憾的是隐藏在MARS模拟器实现中，不是在MIPS程序集中创建，因此您无法在调试器中查看内容以查看将整数值作为字符串打印需要多少工作量。

它可以稍微缩短几个字节，但我试图保持它有点可读，所以你有机会阅读它，并了解它是如何工作的。它应该有点棘手，希望使用你可能不知道或尚未使用的几个概念（例如bit-set来存储/检查使用/未使用哪些符号，使用内存地址而不是主要的索引值循环等...）。当然它不是递归的，所以你不能把它作为你的班级的解决方案...修复你的，与我的“第一次尝试”的例子和调试器一起并不困难。

（还有一件事......关于

.eqv MAX_N, 8           # 8 will work at most (BTW, that's ~40k of permutations)

.data

permutation:    .space MAX_N
# must follow in memory the permutation array directly, at +MAX_N offset, do not move it
symbol_masks:   .space MAX_N     # current symbol mask per position in "permutation" array

input_N_prompt: .asciiz "Enter N (permutation size, 1..7): "

.text

start:
    li   $v0, 4
    la   $a0, input_N_prompt
    syscall             # display input prompt
    li   $v0, 5
    syscall             # read integer from user
    # validate N (1 <= N <= MAX_N)
    blez $v0, start
    bgt  $v0, MAX_N, start

    # initialize global "variables"
    move $s0, $v0       # s0 = N
    move $s1, $zero     # s1 = symbols used (none) = bitmask, each symbol has one bit
    la   $s2, permutation # s2 = permutation.begin() address
    addu $s3, $s2, $s0  # s3 = permutation.end() address
    addi $s4, $zero, 1  # s4 = 1
    move $t7, $s2       # t7 = current position in permutation (address)

symbol_loop_init_position:
    # initialize current (position) symbol to 0 with mask 0x01
    sb   $zero, ($t7)
    sb   $s4, MAX_N($t7)

symbol_loop:            # loops through all symbols for current position $t7
    # will try if symbol at current position is valid
    lb   $t0, MAX_N($t7)  # load bit mask of current symbol
    and  $at, $t0, $s1    # check usage
    beq  $at, $t0, advance_to_next_symbol # when used, advance to next symbol

    # valid symbol in permutation found, mark symbol as used
    or   $s1, $s1, $t0
    # advance to next position
    addi $t7, $t7, 1
    bne  $t7, $s3, symbol_loop_init_position

    # permutation is complete, display it
    jal  print_permutation
    # after print continue with "symbol_loop_retreat" logic (back to valid position)

symbol_loop_retreat:    # current position "exhausted" in search (or printed), retreat
    beq  $t7, $s2, all_permutations_printed  # retreating from first position => end
    addi $t7, $t7, -1   # retreat one position back
    lb   $at, MAX_N($t7)# load bitmask of current symbol at current position
    xor  $s1, $s1, $at  # unmark the currently used symbol
    # and try next symbol for new (previous) current position

advance_to_next_symbol:
    lb   $at, ($t7)
    addi $at, $at, 1    # advance to next symbol value
    beq  $at, $s0, symbol_loop_retreat # symbol == N -> retreat to previous position
    sb   $at, ($t7)     # store next symbol into permutation
    lb   $at, MAX_N($t7)
    sll  $at, $at, 1    # advance also symbol bitmask
    sb   $at, MAX_N($t7)
    j    symbol_loop    # and try it in permutation, if the new symbol is valid

all_permutations_printed:
    # terminate execution
    li   $v0, 10
    syscall

# not a general subroutine, using known registers heavily, modifies only v0, a0 (t7 = s3 at end (again))
print_permutation:
    move $t7, $s2        # permutation.begin() address for display loop
print_permutation_loop:
    # print one symbol from permutation
    move $v0, $s4        # v0 = 1 (print integer)
    lb   $a0, ($t7)      # load permutation symbol (in 0..N-1 value)
    add  $a0, $a0, $s4   # do +1 to make it "human" formatted 1..N value
    syscall
    # print single space character
    li   $v0, 11
    li   $a0, ' '
    syscall
    # loop until all symbols were printed
    addi $t7, $t7, 1     # ++address of current symbol
    bne  $t7, $s3, print_permutation_loop
    # print newline character
    li   $v0, 11
    li   $a0, '\n'
    syscall
    jr   $ra             # return

注册用法...而不是那样做，如果你不是100％肯定如何安全地做到这一点，基本上你必须知道哪些指令是本机MIPS，哪些是伪指令，如那些经常使用$at寄存器进行中间计算，因此使用$at获取某些值的代码将会突然使用某些伪指令...我使用$at作为部分有趣的挑战，使其更复杂，我不会在一些严肃的生产代码中。）

---

还有一件关于你原始代码的事情，我忘了提及，但它表明你理解了这个概念，但需要练习才能获得更多技能（不用担心，它伴随着你编写的代码量，需要时间） ：

像这样的代码：

$at

基本上是s3 = s2 * 4，但是以复杂的方式：s3 = s2，s3 + = s2（即s2 * 2），s3 << = 1（s3 = s3 * 2）。

它可以通过MIPS上的单个指令完成：

    move $s3, $s2
    add $s3, $s3, $s2
    sll $s3, $s3, 1

这是你的主要错误的部分原因，因为你一直使用几个寄存器，直到你偶然改变“i”（当你可以通过单个指令简单地设置一个临时寄存器时）。