MIPS 快速排序数组
MIPS quicksort an array
我正在尝试将一段 "C" 代码转换为 MIPS 汇编语言以供学习之用。我写了 MIPS 代码，但我在某个地方做错了，没有得到想要的输出。当我 运行 程序时，它显示完全不同的数字。请纠正我哪里做错了？
C代码：
void swap(int array[], int a, int b) {
int t = array[a];
array[a] = array[b];
array[b] = t;
}
int partition (int arr[], int low, int high) {
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high- 1; j++) {
if (arr[j] <= pivot) {
i++; // increment index of smaller element
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
写入的 MIPS：
.data # Defines variable section of an assembly routine.
array: .word 12,1,13,10,3,5,2,1 # Define a variable named array as a word (integer) array.
.text # Defines the start of the code section for the program .
.globl main
main:
la $t0, array # Moves the address of array into register $t0.
addi $a0, $t0, 0 # Set argument 1 to the array.
addi $a1, $zero, 0 # Set argument 2 to (low = 0)
addi $a2, $zero, 7 # Set argument 3 to (high = 7, last index in array)
jal quickSort # Call quick sort
li $v0, 10 # Terminate program run and
syscall # Exit
### My code start from here
quickSort:
addi $sp, $sp, -20 #Make room on stack for 5 registers
sw $ra, 16($sp) #save return address on memory
sw $a0, 12($sp) #save a0
sw $a1, 8($sp) #save a1
sw $a2, 4($sp) #save a2
sw $s0 , 0($sp) #save $s0
slt $t1, $a1, $a2 #t1=1 --> low < high, otherwise 0
beq $t1, $zero, Exit #if low > high, branch to Exit
jal partition #call if low < high
move $s0, $v0 #load partition output to s0
addi $a2, $s0, -1 #a2 = pi - 1
jal quickSort #calling quickSort
addi $a1, $s0, 1 #a1 = pi + 1
lw $a2, 4($sp) #loading original a2
jal quickSort #calling quickSort
Exit:
lw $s0, 0($sp)
lw $a2, 4($sp)
lw $a1, 8($sp)
lw $a0, 12($sp)
lw $ra, 16($sp)
addi $sp, $sp, 20
jr $ra
partition:
addi $sp, $sp, -24
sw $ra, 20($sp)
sw $s0, 16($sp)
sw $s1, 12($sp)
sw $s2, 8($sp)
sw $s3, 4($sp)
sw $s4, 0($sp)
sll $t1, $a2, 2 #t1 = 4 * high
add $t1, $a0, $t1 #t1 = *arr + t1
lw $s0, 0($t1) #s0, pivot = arr[high]
addi $s1, $a1, -1 #i=low -1
add $s2, $a1, $zero #j=low
add $s3, $a2, $zero #s3=high
forloop:
addi $t2, $s3, -1 #t2 = high - 1
slt $t3, $t2, $s2 #t3=1 --> j> high - 1
bne $t3, $zero, Exit1 #if j>high -1 branch to Exit 1
sll $t4, $s2,2 #t4 = 4j
add $t4, $a0, $t4 #t4 = *arr + 4j
lw $s4, 0($t4) #s4 = arr[j]
slt $t5, $s0, $s4 #t5=1 --> arr[j] > pivot
beq $t5, $zero, Exit2 #if arr[j] <= pivot, branch to Exit2
addi $s2, $s2, 1 #j++
j forloop #jump to forloop
Exit2:
addi $s1, $s1, 1 #i++
move $a1, $s1 #a1 = i
move $a2, $s2 #a2 = j
jal swap #calling swap
addi $s2, $s2, 1 #j++
j forloop #calling forloop
Exit1:
addi $s1, $s1, 1 #i=i+1
move $a1, $s1 #a1=i+1
move $a2, $s3 #a2=high
jal swap #calling swap
move $v0, $a1 #return i+1
lw $ra, 20($sp)
lw $s0, 16($sp)
lw $s1, 12($sp)
lw $s2, 8($sp)
lw $s3, 4($sp)
lw $s4, 0($sp)
jr $ra
swap:
addi $sp, $sp, -8 # Make room for two elements
sw $ra, 4($sp) # Save return address
sw $s5, 0($sp) # Save s5 register
sll $t6, $a1, 2 #t6 = a*4
add $t6, $a0, $t6 #t6 = *a0 + 4a
lw $s5, 0($t6) #t = array[a]
sll $t7, $a2, 2 #t7 = b*4
add $t7, $a0, $t7 #$t7 = *a0 + 4b
lw $t8, 0($t7) #t8 = array[b]
sw $t8, 0($t6) #array[a] = array[b]
sw $s5, 0($t7) #array[b] = t
lw $s5, 0($sp)
lw $ra, 4($sp)
addi $sp, $sp, 8
jr $ra
这里是快速排序的MIPS程序。摘自：https://github.com/bharathkarumudi/MIPS/blob/master/quicksort.asm
#------------------------------------#
# Authored by: Bharath Karumudi #
# Purpose Quicksort in MIPS #
#------------------------------------#
.data # Defines variable section of an assembly routine.
array: .word 12,15,10,5,7,3,2,1 # Define a variable named array as a word (integer) array.
# After your program has run, the integers in this array
# should be sorted.
.text # Defines the start of the code section for the program .
.globl main
main:
la $t0, array # Moves the address of array into register $t0.
addi $a0, $t0, 0 # Set argument 1 to the array.
addi $a1, $zero, 0 # Set argument 2 to (low = 0)
addi $a2, $zero, 7 # Set argument 3 to (high = 7, last index in array)
jal quicksort # Call quick sort
li $v0, 10 # Terminate program run and
syscall # Exit
swap: #swap method
addi $sp, $sp, -12 # Make stack room for three
sw $a0, 0($sp) # Store a0
sw $a1, 4($sp) # Store a1
sw $a2, 8($sp) # store a2
sll $t1, $a1, 2 #t1 = 4a
add $t1, $a0, $t1 #t1 = arr + 4a
lw $s3, 0($t1) #s3 t = array[a]
sll $t2, $a2, 2 #t2 = 4b
add $t2, $a0, $t2 #t2 = arr + 4b
lw $s4, 0($t2) #s4 = arr[b]
sw $s4, 0($t1) #arr[a] = arr[b]
sw $s3, 0($t2) #arr[b] = t
addi $sp, $sp, 12 #Restoring the stack size
jr $ra #jump back to the caller
partition: #partition method
addi $sp, $sp, -16 #Make room for 5
sw $a0, 0($sp) #store a0
sw $a1, 4($sp) #store a1
sw $a2, 8($sp) #store a2
sw $ra, 12($sp) #store return address
move $s1, $a1 #s1 = low
move $s2, $a2 #s2 = high
sll $t1, $s2, 2 # t1 = 4*high
add $t1, $a0, $t1 # t1 = arr + 4*high
lw $t2, 0($t1) # t2 = arr[high] //pivot
addi $t3, $s1, -1 #t3, i=low -1
move $t4, $s1 #t4, j=low
addi $t5, $s2, -1 #t5 = high - 1
forloop:
slt $t6, $t5, $t4 #t6=1 if j>high-1, t7=0 if j<=high-1
bne $t6, $zero, endfor #if t6=1 then branch to endfor
sll $t1, $t4, 2 #t1 = j*4
add $t1, $t1, $a0 #t1 = arr + 4j
lw $t7, 0($t1) #t7 = arr[j]
slt $t8, $t2, $t7 #t8 = 1 if pivot < arr[j], 0 if arr[j]<=pivot
bne $t8, $zero, endfif #if t8=1 then branch to endfif
addi $t3, $t3, 1 #i=i+1
move $a1, $t3 #a1 = i
move $a2, $t4 #a2 = j
jal swap #swap(arr, i, j)
addi $t4, $t4, 1 #j++
j forloop
endfif:
addi $t4, $t4, 1 #j++
j forloop #junp back to forloop
endfor:
addi $a1, $t3, 1 #a1 = i+1
move $a2, $s2 #a2 = high
add $v0, $zero, $a1 #v0 = i+1 return (i + 1);
jal swap #swap(arr, i + 1, high);
lw $ra, 12($sp) #return address
addi $sp, $sp, 16 #restore the stack
jr $ra #junp back to the caller
quicksort: #quicksort method
addi $sp, $sp, -16 # Make room for 4
sw $a0, 0($sp) # a0
sw $a1, 4($sp) # low
sw $a2, 8($sp) # high
sw $ra, 12($sp) # return address
move $t0, $a2 #saving high in t0
slt $t1, $a1, $t0 # t1=1 if low < high, else 0
beq $t1, $zero, endif # if low >= high, endif
jal partition # call partition
move $s0, $v0 # pivot, s0= v0
lw $a1, 4($sp) #a1 = low
addi $a2, $s0, -1 #a2 = pi -1
jal quicksort #call quicksort
addi $a1, $s0, 1 #a1 = pi + 1
lw $a2, 8($sp) #a2 = high
jal quicksort #call quicksort
endif:
lw $a0, 0($sp) #restore a0
lw $a1, 4($sp) #restore a1
lw $a2, 8($sp) #restore a2
lw $ra, 12($sp) #restore return address
addi $sp, $sp, 16 #restore the stack
jr $ra #return to caller
我正在尝试将一段 "C" 代码转换为 MIPS 汇编语言以供学习之用。我写了 MIPS 代码，但我在某个地方做错了，没有得到想要的输出。当我 运行 程序时，它显示完全不同的数字。请纠正我哪里做错了？
C代码：
void swap(int array[], int a, int b) {
int t = array[a];
array[a] = array[b];
array[b] = t;
}
int partition (int arr[], int low, int high) {
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high- 1; j++) {
if (arr[j] <= pivot) {
i++; // increment index of smaller element
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
写入的 MIPS：
.data # Defines variable section of an assembly routine.
array: .word 12,1,13,10,3,5,2,1 # Define a variable named array as a word (integer) array.
.text # Defines the start of the code section for the program .
.globl main
main:
la $t0, array # Moves the address of array into register $t0.
addi $a0, $t0, 0 # Set argument 1 to the array.
addi $a1, $zero, 0 # Set argument 2 to (low = 0)
addi $a2, $zero, 7 # Set argument 3 to (high = 7, last index in array)
jal quickSort # Call quick sort
li $v0, 10 # Terminate program run and
syscall # Exit
### My code start from here
quickSort:
addi $sp, $sp, -20 #Make room on stack for 5 registers
sw $ra, 16($sp) #save return address on memory
sw $a0, 12($sp) #save a0
sw $a1, 8($sp) #save a1
sw $a2, 4($sp) #save a2
sw $s0 , 0($sp) #save $s0
slt $t1, $a1, $a2 #t1=1 --> low < high, otherwise 0
beq $t1, $zero, Exit #if low > high, branch to Exit
jal partition #call if low < high
move $s0, $v0 #load partition output to s0
addi $a2, $s0, -1 #a2 = pi - 1
jal quickSort #calling quickSort
addi $a1, $s0, 1 #a1 = pi + 1
lw $a2, 4($sp) #loading original a2
jal quickSort #calling quickSort
Exit:
lw $s0, 0($sp)
lw $a2, 4($sp)
lw $a1, 8($sp)
lw $a0, 12($sp)
lw $ra, 16($sp)
addi $sp, $sp, 20
jr $ra
partition:
addi $sp, $sp, -24
sw $ra, 20($sp)
sw $s0, 16($sp)
sw $s1, 12($sp)
sw $s2, 8($sp)
sw $s3, 4($sp)
sw $s4, 0($sp)
sll $t1, $a2, 2 #t1 = 4 * high
add $t1, $a0, $t1 #t1 = *arr + t1
lw $s0, 0($t1) #s0, pivot = arr[high]
addi $s1, $a1, -1 #i=low -1
add $s2, $a1, $zero #j=low
add $s3, $a2, $zero #s3=high
forloop:
addi $t2, $s3, -1 #t2 = high - 1
slt $t3, $t2, $s2 #t3=1 --> j> high - 1
bne $t3, $zero, Exit1 #if j>high -1 branch to Exit 1
sll $t4, $s2,2 #t4 = 4j
add $t4, $a0, $t4 #t4 = *arr + 4j
lw $s4, 0($t4) #s4 = arr[j]
slt $t5, $s0, $s4 #t5=1 --> arr[j] > pivot
beq $t5, $zero, Exit2 #if arr[j] <= pivot, branch to Exit2
addi $s2, $s2, 1 #j++
j forloop #jump to forloop
Exit2:
addi $s1, $s1, 1 #i++
move $a1, $s1 #a1 = i
move $a2, $s2 #a2 = j
jal swap #calling swap
addi $s2, $s2, 1 #j++
j forloop #calling forloop
Exit1:
addi $s1, $s1, 1 #i=i+1
move $a1, $s1 #a1=i+1
move $a2, $s3 #a2=high
jal swap #calling swap
move $v0, $a1 #return i+1
lw $ra, 20($sp)
lw $s0, 16($sp)
lw $s1, 12($sp)
lw $s2, 8($sp)
lw $s3, 4($sp)
lw $s4, 0($sp)
jr $ra
swap:
addi $sp, $sp, -8 # Make room for two elements
sw $ra, 4($sp) # Save return address
sw $s5, 0($sp) # Save s5 register
sll $t6, $a1, 2 #t6 = a*4
add $t6, $a0, $t6 #t6 = *a0 + 4a
lw $s5, 0($t6) #t = array[a]
sll $t7, $a2, 2 #t7 = b*4
add $t7, $a0, $t7 #$t7 = *a0 + 4b
lw $t8, 0($t7) #t8 = array[b]
sw $t8, 0($t6) #array[a] = array[b]
sw $s5, 0($t7) #array[b] = t
lw $s5, 0($sp)
lw $ra, 4($sp)
addi $sp, $sp, 8
jr $ra
这里是快速排序的MIPS程序。摘自：https://github.com/bharathkarumudi/MIPS/blob/master/quicksort.asm
#------------------------------------#
# Authored by: Bharath Karumudi #
# Purpose Quicksort in MIPS #
#------------------------------------#
.data # Defines variable section of an assembly routine.
array: .word 12,15,10,5,7,3,2,1 # Define a variable named array as a word (integer) array.
# After your program has run, the integers in this array
# should be sorted.
.text # Defines the start of the code section for the program .
.globl main
main:
la $t0, array # Moves the address of array into register $t0.
addi $a0, $t0, 0 # Set argument 1 to the array.
addi $a1, $zero, 0 # Set argument 2 to (low = 0)
addi $a2, $zero, 7 # Set argument 3 to (high = 7, last index in array)
jal quicksort # Call quick sort
li $v0, 10 # Terminate program run and
syscall # Exit
swap: #swap method
addi $sp, $sp, -12 # Make stack room for three
sw $a0, 0($sp) # Store a0
sw $a1, 4($sp) # Store a1
sw $a2, 8($sp) # store a2
sll $t1, $a1, 2 #t1 = 4a
add $t1, $a0, $t1 #t1 = arr + 4a
lw $s3, 0($t1) #s3 t = array[a]
sll $t2, $a2, 2 #t2 = 4b
add $t2, $a0, $t2 #t2 = arr + 4b
lw $s4, 0($t2) #s4 = arr[b]
sw $s4, 0($t1) #arr[a] = arr[b]
sw $s3, 0($t2) #arr[b] = t
addi $sp, $sp, 12 #Restoring the stack size
jr $ra #jump back to the caller
partition: #partition method
addi $sp, $sp, -16 #Make room for 5
sw $a0, 0($sp) #store a0
sw $a1, 4($sp) #store a1
sw $a2, 8($sp) #store a2
sw $ra, 12($sp) #store return address
move $s1, $a1 #s1 = low
move $s2, $a2 #s2 = high
sll $t1, $s2, 2 # t1 = 4*high
add $t1, $a0, $t1 # t1 = arr + 4*high
lw $t2, 0($t1) # t2 = arr[high] //pivot
addi $t3, $s1, -1 #t3, i=low -1
move $t4, $s1 #t4, j=low
addi $t5, $s2, -1 #t5 = high - 1
forloop:
slt $t6, $t5, $t4 #t6=1 if j>high-1, t7=0 if j<=high-1
bne $t6, $zero, endfor #if t6=1 then branch to endfor
sll $t1, $t4, 2 #t1 = j*4
add $t1, $t1, $a0 #t1 = arr + 4j
lw $t7, 0($t1) #t7 = arr[j]
slt $t8, $t2, $t7 #t8 = 1 if pivot < arr[j], 0 if arr[j]<=pivot
bne $t8, $zero, endfif #if t8=1 then branch to endfif
addi $t3, $t3, 1 #i=i+1
move $a1, $t3 #a1 = i
move $a2, $t4 #a2 = j
jal swap #swap(arr, i, j)
addi $t4, $t4, 1 #j++
j forloop
endfif:
addi $t4, $t4, 1 #j++
j forloop #junp back to forloop
endfor:
addi $a1, $t3, 1 #a1 = i+1
move $a2, $s2 #a2 = high
add $v0, $zero, $a1 #v0 = i+1 return (i + 1);
jal swap #swap(arr, i + 1, high);
lw $ra, 12($sp) #return address
addi $sp, $sp, 16 #restore the stack
jr $ra #junp back to the caller
quicksort: #quicksort method
addi $sp, $sp, -16 # Make room for 4
sw $a0, 0($sp) # a0
sw $a1, 4($sp) # low
sw $a2, 8($sp) # high
sw $ra, 12($sp) # return address
move $t0, $a2 #saving high in t0
slt $t1, $a1, $t0 # t1=1 if low < high, else 0
beq $t1, $zero, endif # if low >= high, endif
jal partition # call partition
move $s0, $v0 # pivot, s0= v0
lw $a1, 4($sp) #a1 = low
addi $a2, $s0, -1 #a2 = pi -1
jal quicksort #call quicksort
addi $a1, $s0, 1 #a1 = pi + 1
lw $a2, 8($sp) #a2 = high
jal quicksort #call quicksort
endif:
lw $a0, 0($sp) #restore a0
lw $a1, 4($sp) #restore a1
lw $a2, 8($sp) #restore a2
lw $ra, 12($sp) #restore return address
addi $sp, $sp, 16 #restore the stack
jr $ra #return to caller