recursion – I am having a lab about quick sort in ‘RISC-V’. I have done something but my recursive part kept buggy
I guess is stack pointer problem but I can’t fix it. Here is my code:
.global _start
.data
array1: .word -5 24 -8 45 -15 24 11 7 0 125
hi: .word 9
lo: .word 0
newline: .asciz "\n"
space: .asciz " "
.text
_start:
la s0,array1 #load address of array1[0] in s0
lw s4,hi #last elemnt as pivot, pivot index
lw s5,lo #start point(lo)
lw s2,lo #pivot(p)
mv t6,s5
jal partition
j end
#call function that loop partition
#s2(p),s4(hi),s5(lo),t5(i),t6(j),s3(array1[p])
partition:
addi sp,sp,-16
sw ra,0(sp)
sw s4,4(sp)
sw s5,8(sp) #store hi,lo,ra
jal ra,getVal
mv s3,t0 #the pivot value
mv s9,s4
mv s10,s2
jal ra swap
mv t6,s5 #cell going to check(j)
addi t5,t6,-1 #the last cell that elementpivot
jal ra,getVal
ble t0,s3,less #array1[t6]<=pivot
continue:
addi t6,t6,1
j next
less: addi t5,t5,1 #swap array1[j] with array1[i+1]
mv s10,t6
mv s9,t5
jal ra,swap
j continue
swap:
#swap array1[k1] and array1[k2] which is store in s9,s10,respectively
slli t0,s9,2 #store address of array1[k1] in t0
slli t1,s10,2 #store address of array1[k2] in t1
add t0,s0,t0 #get address of array1[k1]
add t1,s0,t1 #address of array1[k2]
lw t2,0(t0) #t2 store arrary1[k1]
lw t3,0(t1) #t3 store array1[k2]
sw t2,0(t1)
sw t3,0(t0)
jr ra
getVal: #get value of cell (array1[t6])
slli t0,t6,2
add t0,s0,t0
lw t0,0(t0)
jr ra
endPartition:
addi t5,t5,1
sw t5,12(sp) #store pivot after partition
mv s10,t5
mv s9,s4
jal ra,swap
jal ra,printArr
lw s4,4(sp)
lw s5,8(sp)
blt s5,s4,recursion
addi sp,sp,16
jr ra
recursion:
lw s2,12(sp)
addi s4,s2,-1
lw s5,8(sp)
mv s2,s5
mv t6,s5
jal ra,partition #recursion for left side
lw s4,4(sp)
lw s5,8(sp)
lw s2,12(sp)
addi s5,s2,1
mv s2,s5
mv t6,s5
jal ra,partition #resursion for right side
jr ra
printArr:
la t0,array1 #address of array1[0]
li t1,10 #number of element need to print
printloop: #loop for printing the array
beqz,t1,printNewline #print a newline when all element is print
lw a0,0(t0) #print the element
li a7,1
ecall
la a0,space #print a space as delimiter
li a7,4
ecall
addi t0,t0,4 #move to next elemrnt
addi t1,t1,-1 #need to print--
j printloop
printNewline: #print a newline ready for next sequence
la a0,newline
li a7,4
ecall
jr ra #jump back to partitioning
end:
I try drawing a stack graph and figure out after the 4th recursion the sp should go back to -16 (compare with initial). However, it seems that it is at -32? So the become dead-loop.
Initial lo:0,hi:9.
In each partition, I make lo as the initial pivot and swap it with hi.
So in theoretical, after first call the pivot is in 2 which is -5. Then, it recursively call partition again with lo:0,hi,1.
after partition pivot is in 1. It call partition again with lo:0,hi:0.
After this partition, lo>=hi. So it go back to lo:0,hi:1,p:1 and call partition again with lo:2,hi:1.
after this, lo>=hi.so it should go back to lo:0,hi:9,p:2 and call partition with lo:3,hi:9.
But my code start being bug here and enter dead-loop.
Read more here: Source link
