Последние 3 дня я работаю над заданием, которое просит нас реализовать алгоритм быстрой сортировки в MIPS. Нам дают этот кусок кода C:
void swap(int v[], int k, int l) {
int temp = v[k];
v[k] = v[l];
v[l] = temp;
}
int partition(int v[], int n) {
int pivot = v[n-1];
int i = 0;
for (int j = 0; j < n - 1; j++)
if (v[j] < pivot)
swap(v,i++,j);
swap(v, i, n - 1);
return (i);
}
void qsort(int v[], int n) {
if (n > 1) {
int p = partition(v, n);
qsort(v,p);
qsort(&v[p+1],n-p-1);
}
}
и нас просят «перевести» это в MIPS. Функция partition() дана нам в MIPS, и мы должны реализовать две другие (qsort() и swap()). Хорошо, swap() протестирован и работает, поэтому я пытаюсь реализовать qsort(), и мне нужно сохранить в стеке адреса, к которым qsort() вернется после того, как это будет сделано (для рекурсии). Проблема в том, что независимо от того, что я делаю, будь то игра с указателями стека и фрейма или явная попытка установить пустые ячейки, когда выполняется partition(), заменяет моего массива некоторыми из его собственные данные. Любые идеи по решению этого?
Мой код здесь (все без комментариев не мое, игнорируйте переходы к printArray, я опускаю его из-за того, что он не имеет отношения к остальному коду):
.globl v
.data
.align 2
v:
.word 3
.word 10
.word 8
.word 2
.word 7
.word 1
.word 5
.word 9
.word 6
.word 4
.text
main:
addiu $sp,$sp,-40
sw $ra,36($sp)
sw $fp,32($sp)
move $fp,$sp
li $v0,10 # 0xa
move $s0, $v0
sw $v0,28($fp)
lw $a1,28($fp)
la $a0, v
jal printArray
lw $a1,28($fp)
la $a0, v
jal qsort
la $a0, v
move $a1, $s0
jal printArray
move $v0,$0
move $sp,$fp
lw $ra,36($sp)
lw $fp,32($sp)
addiu $sp,$sp,40
jr $ra
swap:
move $t0, $a0 #store the address of the first cell of the array (we need this for finding v[k]'s address)
move $t1, $a0 #same as above (need this for the address of v[l])
move $t4, $a1 #load k into t4
sll $t4, $t4, 2 #turn k into bytes to be offset
add $t0, $a0, $t4 #find the address of v[k]
move $t4, $a2 #load l into a1
sll $t4, $t4, 2 #turn l into bytes to be offset
add $t1, $a0, $t4 #find the address of v[l]
lw $t2, 0($t0) #store the element with index k in t2 (t2: temp in the C code)
lw $t3, 0($t1) #store the element with index l in t3
sw $t2, 0($t1) #store the element with index k in the address where v[l] was
sw $t3, 0($t0) #store v[l] where v[k] was
jr $ra
nop
partition:
addiu $sp,$sp,-56
sw $ra,44($sp)
sw $fp,40($sp)
move $fp,$sp
sw $a0,48($fp)
sw $a1,52($fp)
lw $v1,52($fp)
li $v0,1073676288 # 0x3fff0000
ori $v0,$v0,0xffff
addu $v0,$v1,$v0
sll $v0,$v0,2
lw $v1,48($fp)
addu $v0,$v1,$v0
lw $v0,0($v0)
sw $v0,36($fp)
sw $0,28($fp)
sw $0,32($fp)
b part_loop
nop
part_for:
lw $v0,32($fp)
sll $v0,$v0,2
lw $v1,48($fp)
addu $v0,$v1,$v0
lw $v1,0($v0)
lw $v0,36($fp)
slt $v0,$v1,$v0
beq $v0,$0,part_noswap
nop
lw $v0,28($fp)
addiu $v1,$v0,1
sw $v1,28($fp)
lw $a2,32($fp)
move $a1,$v0
lw $a0,48($fp)
jal swap
part_noswap:
lw $v0,32($fp)
addiu $v0,$v0,1
sw $v0,32($fp)
part_loop:
lw $v0,52($fp)
addiu $v1,$v0,-1
lw $v0,32($fp)
slt $v0,$v0,$v1
bne $v0,$0,part_for
nop
lw $v0,52($fp)
addiu $v0,$v0,-1
move $a2,$v0
lw $a1,28($fp)
lw $a0,48($fp)
jal swap
lw $v0,28($fp)
move $sp,$fp
lw $ra,44($sp)
lw $fp,40($sp)
addiu $sp,$sp,56
jr $ra
qsort:
move $t5, $ra #store temporarily the ret.addr. of qsort's caller
jal RetAddrMng #then store it on the stack
addi $t6, $t6, 1 #add 1 to t6, which counts the number of times qsort has been called
bgt $a1, 1, sort #sorting will continue if n > 1
sort:
jal partition
move $a1, $v0 #move 'p' from result to be the argument of the next qsort
jal qsort
jr $ra
RetAddrMng:
sll $t6, $t6, 2 #turn the number of times into offset bytes by quadrupling them
add $sp, $sp, $t6 #move the stack pointer 4*<number of times> bytes to find the next cell
sw $t5, 0($sp) #store the address in t5 into the stack
srl $t6, $t6, 2 #we will need again the number of times, so we invert the transformation by dividing with 4
jr $ra #continue with qsort
К вашему сведению, я работаю на MARS 4.5.
Заранее спасибо.