208 lines
4.1 KiB
ArmAsm
208 lines
4.1 KiB
ArmAsm
.data
|
|
v: .word 3, 10, 8, 2, 7, 1, 5, 9, 6, 4
|
|
|
|
|
|
# swap(int i, int j) : swaps elements of v[]
|
|
# at positions i and j
|
|
# $a0 = i
|
|
# $a1 = j
|
|
# $s0 = v
|
|
.text
|
|
swap:
|
|
# intro - stack-frame
|
|
addi $sp, $sp, -28
|
|
sw $ra, 24($sp)
|
|
sw $fp, 20($sp)
|
|
|
|
sw $s0, 16($sp) # v
|
|
sw $t0, 12($sp) # temp
|
|
sw $t1, 8($sp) # *v[i]
|
|
sw $t2, 4($sp) # *v[j]
|
|
sw $t3, 0($sp) # buffer
|
|
addi $fp, $sp, 24
|
|
|
|
|
|
move $t1, $s0 # pointer assignements
|
|
sll $a0, $a0, 2
|
|
add $t1, $t1, $a0
|
|
move $t2, $s0
|
|
sll $a1, $a1, 2
|
|
add $t2, $t2, $a1
|
|
|
|
lw $t0, 0($t1) # temp = v[i]
|
|
lw $t3, 0($t2) # v[i] = v[j]
|
|
sw $t3, 0($t1)
|
|
sw $t0, 0($t2) # v[j] = temp
|
|
|
|
# epilogue - stack-frame
|
|
lw $t3, 0($sp)
|
|
lw $t2, 4($sp)
|
|
lw $t1, 8($sp)
|
|
lw $t0, 12($sp)
|
|
lw $s0, 16($sp)
|
|
|
|
lw $fp, 20($sp)
|
|
lw $ra, 24($sp)
|
|
addi $sp, $sp, 28
|
|
jr $ra
|
|
|
|
# partition(int f, int l) : partitions elements in vector v[]
|
|
# between positions f and l, using as pivot the element v[l], such
|
|
# that
|
|
# i < p ==> v[i] <= v[p]
|
|
# i > p ==> v[p] < v[i]
|
|
# The function returns the position p of the pivot.
|
|
# $a0 = f
|
|
# $a1 = l
|
|
# $s0 = v
|
|
# $v0 = p
|
|
.text
|
|
partition:
|
|
# intro - stack-frame
|
|
addi $sp, $sp, -40
|
|
sw $ra, 36($sp)
|
|
sw $fp, 32($sp)
|
|
|
|
sw $s0, 28($sp) # v
|
|
sw $s1, 24($sp) # pivot
|
|
sw $s2, 20($sp) # i
|
|
sw $s3, 16($sp) # j
|
|
sw $s4, 12($sp) # a0 (f)
|
|
sw $s5, 8($sp) # a1 (l)
|
|
sw $t0, 4($sp)
|
|
sw $t1, 0($sp)
|
|
addi $fp, $sp, 36
|
|
|
|
move $s4, $a0
|
|
move $s5, $a1
|
|
move $t0, $s0 # make *v[l]
|
|
move $t1, $a1 # t1 = l
|
|
sll $t1, $t1, 2 # t1 *= 4
|
|
add $t0, $t0, $t1
|
|
lw $s1, 0($t0) # pivot = v[l]
|
|
|
|
move $s2, $s4 # i = f;
|
|
|
|
# for () {
|
|
move $s3, $s4 # j = f;
|
|
_part_loop0:
|
|
slt $t0, $s3, $s5 # j < l
|
|
beq $t0, $0, _part_loop_end
|
|
move $t0, $s0 # make *v[j]
|
|
move $t1, $s3
|
|
sll $t1, $t1, 2
|
|
add $t0, $t0, $t1
|
|
lw $t1, 0($t0) # t1 = v[j]
|
|
# if (v[j] < pivot)
|
|
slt $t0, $t1, $s1
|
|
beq $t0, $0, _part_loop_else
|
|
|
|
move $a0, $s2 # swap (i, j);
|
|
move $a1, $s3
|
|
jal swap
|
|
addi $s2, 1 # i++
|
|
|
|
_part_loop_else:
|
|
addi $s3, 1 # j++
|
|
j _part_loop0 # }
|
|
_part_loop_end:
|
|
move $a0, $s2 # swap (i, l)
|
|
move $a1, $s5
|
|
jal swap
|
|
|
|
move $v0, $s2 #return i
|
|
|
|
# epilogue - stack-frame
|
|
lw $t1, 0($sp)
|
|
lw $t0, 4($sp)
|
|
lw $s5, 8($sp)
|
|
lw $s4, 12($sp)
|
|
lw $s3, 16($sp)
|
|
lw $s2, 20($sp)
|
|
lw $s1, 24($sp)
|
|
lw $s0, 28($sp)
|
|
|
|
lw $fp, 32($sp)
|
|
lw $ra, 36($sp)
|
|
addi $sp, $sp, 40
|
|
jr $ra
|
|
|
|
|
|
# qsort(int f, int l) : sorts the elements of v[]
|
|
# between positions f:l
|
|
# $a0 = f
|
|
# $a1 = l
|
|
# $s0 = v
|
|
.text
|
|
qsort: # qsort entry point
|
|
# intro - stack-frame with 4byte local var @ fp
|
|
addi $sp, $sp, -28 # qsort
|
|
sw $ra, 24($sp)
|
|
sw $fp, 20($sp)
|
|
|
|
sw $s0, 16($sp) # v
|
|
sw $s2, 12($sp) # a0 (f)
|
|
sw $s3, 8($sp) # a1 (l)
|
|
sw $t0, 4($sp)
|
|
addi $fp, $sp, 24
|
|
|
|
move $s2, $a0 # get f, l
|
|
move $s3, $a1
|
|
# if (f < l) {
|
|
slt $t0, $s2, $s3
|
|
beq $t0, $0, _qsort_end
|
|
|
|
move $a0, $s2 # pivot = partition(f, l);
|
|
move $a1, $s3
|
|
jal partition
|
|
sw $v0, 0($sp)
|
|
|
|
move $a0, $s2 # qsort(f, pivot - 1);
|
|
lw $t0, 0($sp)
|
|
addi $t0, $t0, -1
|
|
move $a1, $t0
|
|
jal qsort
|
|
|
|
lw $t0, 0($sp) # qsort(pivot + 1, l);
|
|
addi $t0, $t0, 1
|
|
move $a0, $t0
|
|
move $a1, $s3
|
|
jal qsort
|
|
# }
|
|
_qsort_end:
|
|
# epilogue - stack-frame
|
|
lw $t0, 4($sp)
|
|
lw $s3, 8($sp)
|
|
lw $s2, 12($sp)
|
|
lw $s0, 16($sp)
|
|
|
|
lw $fp, 20($sp)
|
|
lw $ra, 24($sp)
|
|
addi $sp, $sp, 28
|
|
jr $ra # return to caller
|
|
|
|
|
|
.text
|
|
.globl main
|
|
main:
|
|
# intro - stack-frame
|
|
addi $sp, $sp, -12 # main
|
|
sw $ra, 8($sp)
|
|
sw $fp, 4($sp)
|
|
sw $s0, 0($sp)
|
|
addi $fp, $sp, 8
|
|
|
|
li $t0, 10
|
|
|
|
li $a0, 0
|
|
li $a1, 9
|
|
la $s0, v
|
|
jal qsort
|
|
|
|
# epilogue - stack-frame
|
|
lw $s0, 0($sp)
|
|
lw $fp, 4($sp)
|
|
lw $ra, 8($sp)
|
|
addi $sp, $sp, 12
|
|
jr $ra
|