algorithm - 如何将此排序算法转换为 mips 程序集

Question

我的计算机体系结构作业是用 MIPS 汇编编写一个程序，该程序可以按升序对二维数组进行排序。我用 Java 写了一个可以做到这一点的 bubblesort 算法；然而，我对 MIPS 还是很陌生，不知道如何在 MIPS 语法中使用相同的逻辑。

具体来说，我如何在 MIPS 中构造 while-for 循环？我知道 if 和方法调用是如何转换的(jal/j/jr 和 bgt/blt/slt)，但我无法理解如何构建我的 for 循环

public class D2ArraySort {

    public static int[][] switchValsEnd(int[][] a, int i, int j) {
        int temp;
        temp = a[i][j];
        a[i][j] = a[i + 1][0];
        a[i + 1][0] = temp;
        return a;
    }

    public static int[][] switchVals(int[][] a, int i, int j) {
        int temp;
        temp = a[i][j];
        a[i][j] = a[i][j + 1];
        a[i][j + 1] = temp;
        return a;
    }

    public static int[][] sort(int[][] a) {
        while (true) {
            for (int i = 0; i < a.length; i++) {
                for (int j = 0; j < a[i].length; j++) {
                    if (j == a[i].length - 1 && i != a.length - 1) {
                        if (a[i][j] < a[i + 1][0]) {
                            a = switchValsEnd(a, i, j);
                            i = 0;
                            j = -1;
                        }
                    } else {
                        if (j == a[i].length - 1) {
                            return a;
                        }
                        if (a[i][j] < a[i][j + 1]) {
                            a = switchVals(a, i, j);
                            i = 0;
                            j = -1;
                        }
                    }
                }
            }
        }
    }

    public static void main(String[] args) { // don't need main other than to call j sort
        int[][] input_data = { // global input_data
                {2, 0, -7, -1, 3, 8, -4, 10},
                {-9, -16, 15, 13, 1, 4, -3, 14},
                {-8, -10, -15, 6, -13, -5, 9, 12},
                {-11, -14, -6, 11, 5, 7, -2, -12},
        };
        int[][] output_data = sort(input_data); // jal sort
        for (int i = 0; i < output_data.length; i++) {
            System.out.print("( ");
            for (int j = 0; j < output_data[i].length; j++) {
                System.out.print(output_data[i][j] + ", ");
            }
            System.out.println(")");
        }
    }    
}

预期输出:( 15, 14, 13, 12, 11, 10, 9, 8, )( 7, 6, 5, 4, 3, 2, 1, 0, )在此处输入代码(-1、-2、-3、-4、-5、-6、-7、-8、)(-9, -10, -11, -12, -13, -14, -15, -16, )

到目前为止的 MIPS 程序集(我不知道从哪里开始使用 while-for 循环):也忽略我不完整的主要方法哈哈

#
#  Author: Joshua Baroni
#  Date: October 16, 2019
#  Description: Sorting 2D array in descending order
#
.text
.align 4

main:


sort:

    la $t4, vals #t0 is number up to outer loop
    la $t1, vals #t1 is number comparing to inner loop
    addi $t1,$t1,4
    la $t8,vals
    add $t8,$t0,$t8
    la $t9,vals
    add $t9,$t0,$t9
    addi $t9,$t9,-4
    loops: lw $t2,($t4) #get number 1 outer loop
    lw $t3,($t1) #get number 2 inner loop
    bgt $t2,$t3, next #don't need to swap
    sw $t3,($t4) #swap
    sw $t2,($t1)
    next: addi $t1,$t1,4
    bgt $t1,$t8,loops #inner loop done?
    addi $t4,$t4,4 #yes-increment outer loop
    move $t1,$t4
    addi $t1,$t1,4
    bgt $t4,$t9,loops #outer loop done?


.data
.align 4
Input_data:
    .word 2, 0, -7, -1, 3, 8, -4, 10
    .word -9, -16, 15, 13, 1, 4, -3, 14
    .word -8, -10, -15, 6, -13, -5, 9, 12
    .word -11, -14, -6, 11, 5, 7, -2, -12
Output_data:
    .word 0, 0, 0, 0, 0, 0, 0, 0
    .word 0, 0, 0, 0, 0, 0, 0, 0
    .word 0, 0, 0, 0, 0, 0, 0, 0
    .word 0, 0, 0, 0, 0, 0, 0, 0

Answer 1

.data
.align 4
Input_data:

    .word 2, 0, -7, -1, 3, 8, -4, 10
    .word -9, -16, 15, 13, 1, 4, -3, 14
    .word -8, -10, -15, 6, -13, -5, 9, 12
    .word -11, -14, -6, 11, 5, 7, -2, -12

Output_data:
        .word 0, 0, 0, 0, 0, 0, 0, 0
        .word 0, 0, 0, 0, 0, 0, 0, 0
        .word 0, 0, 0, 0, 0, 0, 0, 0
        .word 0, 0, 0, 0, 0, 0, 0, 0

    comma: .asciiz ", "

    parenthesis_open: .asciiz "("

    parenthesis_close: .asciiz ")"

    newline: .asciiz "\n"

    .text
    .globl main
    main:


        jal sort     # call sort function

        li $t0,0       # j=0
        li $t2,0       # i=0

        # int[][] output_data = sort(input_data);

        copy_array_i:       # loop for int i ....

            addiu  $t2,$t2,32   # i = i+1 (+32 in reality , each line has 8 elements * 4 bytes each one )

            copy_array_j:       # loop for int j ..

            lw $t1,Input_data($t0)     # $t1 = a[i][j]
            sw $t1,Output_data($t0)    # store the element to Output_data at same index


        addiu $t0,$t0,4            # index = index +1 (+4 in reality because each number weights 4 bytes)

        bne $t0,$t2,copy_array_j    # if index != output_data[i].length -1 , jump to for (int j...)


        bne $t2,128,copy_array_i    # if i != 128 (4 bytes *8 elements * 4 lines )


        li $s1,0
        li $s2,0

        print_out:
            addiu $s2,$s2,32
            la $a0, parenthesis_open  #load address into $a0
            li $v0, 4      #call to print string
        syscall

        inner_loop:
        lw $s0,Output_data($s1)  # $s0 = Output_data[i][j]

        li $v0, 1       #print the Output_data element
        move $a0, $s0
        syscall 
        addiu $s1,$s1,4

            la $a0, comma  #load address into $a0
            li $v0, 4      #call to print comma
        syscall
        bne $s1,$s2,inner_loop  

            la $a0, parenthesis_close  #load address into $a0
            li $v0, 4      #call to print parenthesis closed
        syscall

        la $a0, newline  #load address into $a0
            li $v0, 4      #call to print newline
        syscall

        #addiu $s3,$s3,32

        bne $s2,128,print_out

    li $v0, 10 # system call for exit
    syscall


    sort:
    addi $sp,$sp,-4
    sw $ra,0($sp)


        li $s0,128            # a.length  8*4*4
        li $s5,96           # a.length -1 8*4*3
        li $s1,32            # a[i].length  8*4 bytes
        li $s2,28            # a[i].length -1  7*4 bytes
        li $s3,0             # i
        li $s4,0             # j

    while:

        li $s3,0  # i = 0

        for_i:

            li $s4,0   # j =0
            for_j:

                seq  $t0,$s4,$s2 # if j == a[i].length -1 => $t0 =1 else $t0=0
                sne  $t1,$s3,$s5 # if i != a.length -1  => $t1=1 else $t1=0
                and  $t2,$t0,$t1  # logical and between $t0 and $t1 , storing the result into $t2
                bne  $t2,1,else   # if !(j == a[i].length - 1 && i != a.length - 1)  go to else label


                li $t0,0           # $t0 =0
                li $t1,0           # $t1=0
                addu $t0,$s3,$s4   # $t0 = i + j

                lw $t2,Input_data($t0)  # to get  a[i][j] into $t2


                addiu $t1,$s3,32    # $t1 = i+1  (+1 => +32 bytes)

                lw $t3,Input_data($t1)   # to get a[i+1][0]


                bge $t2,$t3, inc_i_or_j  # if a[i][j] >= a[i+1][0] go to inc_i_or_j label

                move $a0,$s3            # first parameter => i
                move $a1,$s4            # second parameter => j
                jal switchValsEnd       # call switchValsEnd function

                li $3,0                 #  i=0

                li $s4,0                # j=0

                j for_j                # go to for int j  ....

                inc_i_or_j:            #inc_i_or_j label

                beq $s3,$s5,while       # if i == a.length -1 => go to while label

                addiu $s3,$s3,32        # else  i=i+1
                j for_i                 # jump to for_i label

            else:

            bne $s4,$s2,second_if           # if j!= a[i].length -1  go to second if 


            lw $ra,0($sp)                    # restore return address stored into stack
            addiu $sp,$sp,4                  # free stack
            jr $ra              # jump to caller (main)


            second_if:

            li $t0,0
            li $t3,0
            addu $t0,$s3,$s4                # $t0 = i+j


            lw $t4,Input_data($t0)  # a[i][j]

            addu $t3,$s3,$s4                # $t0 = i+j
            addiu $t3,$t3,4                 # $t3 = i+ (j+1)

            lw $t5,Input_data($t3)   #  a[i][j + 1]

            bge $t4,$t5,inc_j         # if a[i][j] >= a[i][j+1] go to inc_j label               

            move $a0,$s3             # first parameter i
            move $a1,$s4             # second parameter j
            jal switchVals           # call switchVals function


            li $s3,0                # i=0
            li $s4,0                # j=0

            j for_j                 # jump to for int j ...

            inc_j:                   # inc_j label
                addiu $s4,$s4,4  # j = j+1 (+4 because each number = 4 bytes )
                j for_j          # jump to for (int j ...)


switchValsEnd:
    addi $sp,$sp,-4         #allocate space in stack (4 bytes)
    sw $ra,0($sp)           # store return address 

    li $t2,0        

    addu $t2,$a0,$a1         # $t2 =i + j

    lw $t4,Input_data($t2)   # temp= a[i][j]

    li $t1,0

    addu  $t1,$t1,$a0         # $t1 = i
    addiu $t1,$t1,32          # $t1 = i+1 (+32)


    lw $t5,Input_data($t1)  # a[i+1][0]

    sw $t5,Input_data($t2)  #     a[i][j] = a[i + 1][0];


    sw $t4,Input_data($t1)   # a[i+1][0] = temp

    lw $ra,0($sp)            # restore $ra (return address ) from stack 
    addi $sp,$sp,4            # free stack's element 
    jr $ra                   # return to caller ( sort function )

switchVals:
    addi $sp,$sp,-4
    sw $ra,0($sp)

    # $a0 = i
    # $a1 = j
    li $t1,0
    li $t7,0

    addu $t1,$a0,$a1         # $t1 = i+j


    lw $t3,Input_data($t1)   # temp  = a[i][j]

    addu $t5,$a0,$a1         # $t5 = i + j
    addiu $t5,$t5,4          # $t5 = i + (j+1)

    lw $t8,Input_data($t5)        # a[i] [j+1]

    sw $t8,Input_data($t1)  #     a[i][j] = a[i][j+1];


    sw $t3,Input_data($t5)   #   a[i][j] = a[i][j + 1];

    lw $ra,0($sp)            # restore $ra (return address ) from stack 
    addi $sp,$sp,4            # free stack's element 
    jr $ra                   # return to caller ( sort function )