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都被排序好了
全部评论
(0) 回帖