首页 > MIPS实现简单冒泡排序
头像
Boyn
编辑于 2020-02-07 11:24
+ 关注

MIPS实现简单冒泡排序

MIPS实现简单冒泡排序

在本文中,我们将会用MIPS来实现一段C语言中简单的冒泡排序 C语言的代码如下所示

void sort(int v[], int n)
{
    int i, j;
    for (i = 0; i < n ; i += 1) {
        for (j = i - 1; j >= 0 && v[j] > v[j + 1]; j -= 1){
            swap(v,j)
        }
    }
}

先来分析一下这段程序.

寄存器的分配:
# $a0 = *v, $a1 = n
a0放置数组v的首地址
a1放置n的值
# $s0 = i, $s1 = j
s0放置i的值
s1放置j的值

首先,我们看到有两层的循环,第一层的循环只有对第二层循环的过程和对i的加1,我们可以用简单的语句将其表示出来

        move    $s0,$0  # 将i=0 放到s0寄存器中
for1tst:
        slt     $t0, $s0, $s3       # $t0 = 0 if $s0 >= $ a1  (i >= n)
        beq     $t0, $zero, exit1   # go to exit if $t0 = 0 (i < n)
        addi    $s1, $s0, -1        # j = i -1   
        #  entity
        addi    $s0, $s0, 1         # i+=1
        j       for1tst

这段程序将i初始化为0,并将其放入寄存器s0中. 然后声明了一个for1tst,首先先要判断i是否小于n,slt语句是(set when less than) 在 i < n时,t0会被置为1,反之则为0.在后面声明了一个分支语句,如果t0的值与$0,也就是0相同,程序则跳转到exit1.反之,则会执行实体里面的内容(现在暂空),并且在执行完之后,将i所属寄存器的值+1,并跳回到标签开始. 第一层循环分析完后,我们来看看第二层的循环. 第二层的循环里面,j在初始化之后,是递减的,并且多了一个判断循环退出的条件. 我们先来看看如何判断v[j] > v[j + 1]

# 根据取地址的原则,我们先将jx4,左移两位
    sll     $t1, $s1, 2
# 然后分别取两个数的值
    lw      $t2, 0($t1)         # $t2 = v[j]
    lw      $t3, 4($t1)         # $t3 = v[j+1]
# 再判断他们是否有v[j] > v[j + 1],如果条件不成立,则跳转至结束
    slt     $t0, $t3, $t2       # $t0 = 0 if t3 >= t2  -->  t2 > t3
    beq     $t0, $0, exit2

而判断j是否大于等于0则与上面的相似,不再赘述 有以下框架

for2tst: # the second layer loop
    slti    $t0, $s1, 0         # whether j >= 0 ?
    bne     $t0, $0, exit2
    sll     $t1, $s1, 2
    add     $t1, $a0, $t1
    lw      $t2, 0($t1)         # $t2 = v[j]
    lw      $t3, 4($t1)         # $t3 = v[j+1]
    slt     $t0, $t3, $t2       # $t0 = 0 if t3 >= t2  -->  t2 > t3
    beq     $t0, $0, exit2

    move    $a0, $s2            # the address of v
    move    $a1, $s1            # the value of j
    jal     swap
    addi    $s1, $s1, -1
    j       for2tst   
    # the second layer loop end
exit2:
    addi    $s0, $s0, 1         # i+=1
    j       for1tst             # jump to the first layer loop

而swap,也就是交换函数则相对来说简单得多了,故直接给出

swap:
    sll     $t1, $a1, 2
    add     $t1, $t1, $a0
    lw      $t0, 0($t1)
    lw      $t2, 4($t1)
    sw      $t0, 4($t1)
    sw      $t2, 0($t1)
    jr      $ra

然后我们再把这个程序串起来

# Translate C:
# void sort(int v[], int n)
# {
#     int i, j;
#     for (i = 0; i < n ; i += 1) {
#         for (j = i - 1; j >= 0 && v[j] > v[j + 1]; j -= 1){
#             swap(v,j)
#         }
#     }
# }

# $a0 = *v, $a1 = n
# $s0 = i, $s1 = j
    .data
v:  .word 0x4 0x3 0x1 0x5 0x2 0x6
    .text
    .globl main
main:
    la      $a0,v
    li      $a1,6
    addi    $sp, $sp, -20
    sw      $ra, 16($sp)
    sw      $s3, 12($sp)
    sw      $s2, 8($sp)
    sw      $s1, 4($sp)
    sw      $s0, 0($sp)

    move    $s2, $a0
    move    $s3, $a1
    move    $s0, $0             # i = 0
for1tst: # the first layer loop
    slt     $t0, $s0, $s3       # $t0 = 0 if $s0 >= $ a1  (i >= n)
    beq     $t0, $zero, exit1   # go to exit if $t0 = 0 (i < n)
    addi    $s1, $s0, -1        # j = i -1   
for2tst: # the second layer loop
    slti    $t0, $s1, 0         # whether j >= 0 ?
    bne     $t0, $0, exit2
    sll     $t1, $s1, 2
    add     $t1, $a0, $t1
    lw      $t2, 0($t1)         # $t2 = v[j]
    lw      $t3, 4($t1)         # $t3 = v[j+1]
    slt     $t0, $t3, $t2       # $t0 = 0 if t3 >= t2  -->  t2 > t3
    beq     $t0, $0, exit2

    move    $a0, $s2            # the address of v
    move    $a1, $s1            # the value of j
    jal     swap

    addi    $s1, $s1, -1
    j       for2tst   
    # the second layer loop end
exit2:
    addi    $s0, $s0, 1         # i+=1
    j       for1tst             #jump to the first layer loop
    # the first layer loop end
exit1:
    lw      $ra, 16($sp)
    lw      $s3, 12($sp)
    lw      $s2, 8($sp)
    lw      $s1, 4($sp)
    lw      $s0, 0($sp)      
    addi    $sp, $sp, 20
    jr      $ra
swap:
    sll     $t1, $a1, 2
    add     $t1, $t1, $a0
    lw      $t0, 0($t1)
    lw      $t2, 4($t1)
    sw      $t0, 4($t1)
    sw      $t2, 0($t1)
    jr      $ra

运行实例

我们可以在SPIM中运行上面的程序 加载后,没运行之前,内存区与寄存器区图如下 而在运行之后,内存区的6个words都被排序好了

附录A:MIPS常用指令

全部评论

(0) 回帖
加载中...
话题 回帖