tatatat0
Smash Journeyman
- Joined
- Jan 28, 2015
- Messages
- 412
I decided to make some sorting algorithms in PowerPC and share them here. I made bubble sorting first, and plan on maybe making radix or quick sort later.
Bubble Sort[tatatat0]:
Notes:
During the bubblesortloopswap subroutines I was unsure whether or not to use
or
because I am unsure of the implications of the superscalar technology of the PowerPC architecture allowing multiple instructions to be ran at the conncurently during a single clock cycle. Although the difference would be a single clok cycle I'd like to optimize my code as much as possible. I learned about the concept of superscalar processing abstractly in the architecture through a brief explanation in the first few pages of the book "PowerPC Compiler Writer's Guide". If you know of how exactly the concept works concretely in the PowerPC Architecture I'd like to know.
For the implementations of arrays I didn't want to assume or enforce a certain type of array. While I could have enforced an array whose length of the array is in the first doubleworld of the array and the elements following afterwards I wanted to allow many different types of 32 bit arrays to be allowed.
I chose not to have my function take complete control of the processor until it was done for quite a few reasons. I wanted my function to be able to run concurrently with other funtions in a multi-threaded environment and also prevent stalling with extremely large input arrays.
How to implement this function:
In order to implement this function you first need to have an existing general 32 bit array. If you don't have an array allocating memory dynamically for the array is system and implementation dependent so I shall not include instructions for that. As long as the elements of the array are in order the array can be high level and contain functions assigned to it. Before you do anything thoughyou should push the reserved registers as well as the link register to the stack. The rest of the inputs required aren't difficult to obtain. Use a bl or bla to the function shall perform it. However, running the function once is not a certainty that the list is sorted. Instead, one iteration of the function only runs through the list once. The return register r4 will indicate whether or not the list is sorted. If r4 is equal 0 it isn't sorted, and if r4 is equal to 1 it is sorted. In order to fully sort a list you should run a while loop whose conditional is r4 equalling 0. If the conditional is checked at the beginning of the loop make sure to set r4 to 0 before the loop first executes. After the while loops ends you can pop the reserved registers from the stack.
If I made any mistakes please tell me. I made sure to flow chart out the code beforehand. You can use this anywhere you want, just credit me.
Bubble Sort[tatatat0]:
Code:
bubblesort:
#Reserved registers:
# r3: Array pointer
# r4: isSorted boolean
# r5: Array length -> end of array pointer
# r6: Sort direction boolean
# r7: Array element pointer 1
# r8: Array element pointer 2
# r9: Temporary array element register 1
# r10: Temporary array element register 2
#Input registers:
# r3: Pointer to first element of 32 bit array
# r5: Length of array in items
# r6: Boolean which determins whether to sort from least to greatest or greatest to least. All bits except the Least Significant Bit are ignored.
# Values:
# 0: Least to greatest.
# 1: Greatest to least.
#Return registers:
# r3: Array pointer
# r4: isSorted boolean
li r4,0x1 #set isSorted to true
cmplwi r5,0x1 #check if array length is less than 1 items
ble- bubblesortend #is sorted
mr r7,r3
subi r4,r4,0x1 #aligns to array that starts at index zero instead of one
mulli r4,r4,0x4 #offset to last element of array
add r4,r4,r7 #sets r4 equal to pointer
#sets r7 and r8 equal to pointers to the first and second items of array
mr r7,r3
mr r8,r3
addi r8,r8,0x4
cmplwi r6,0x1 #checks sort order
beq- bubblesortloopgtlstart
bubblesortloopltg:
#load items into r9 and r10
lwz r9,0x0(r7)
lwz r10,0x0(r8)
cmpw r9,r10
bge+ bubblsortloopltgswap
bubblesortloopltgend:
cmpw r8,r5 #checks if done iterating through array
beq- bubblesortend
addi r7,r7,0x4
addi r8,r8,0x4 #increments item pointers
b bubblesortloopltg
bubblesortloopltgswap:
stw r9,0x0(r8)
stw r10,0x0(r7)
li r4,0x0
b bubblesortloopltgend
bubblesortloopgtlstart:
mr r7,r5
mr r8,r5
subi r8,r8,0x4 #load last two item pointers into r7 and r8
bubblesortloopgtl:
lwz r9,0x0(r7)
lwz r10,0x0(r8)
cmpw r9,r10
bge+ bubblesortloopgtlswap
bubblesortloopgtlend:
cmpw r8,r3
beq- bubblesortend #check if reached first item of array
subi r7,r7,0x4
subi r8,r8,0x4 #decrement item pointers
b bubblesortloopgtl
bubblesortloopgtlswap:
stw r9,0x0(r8)
stw r10,0x0(r7)
li r4,0x0
b bubblesortloopgtlend
bubblesortend:
blrDuring the bubblesortloopswap subroutines I was unsure whether or not to use
Code:
stw r9,0x0(r8)
stw r10,0x0(r7)
#ltgloop example shown above
Code:
stw r9,0x4(r7)
stw r10,0x0(r7)For the implementations of arrays I didn't want to assume or enforce a certain type of array. While I could have enforced an array whose length of the array is in the first doubleworld of the array and the elements following afterwards I wanted to allow many different types of 32 bit arrays to be allowed.
I chose not to have my function take complete control of the processor until it was done for quite a few reasons. I wanted my function to be able to run concurrently with other funtions in a multi-threaded environment and also prevent stalling with extremely large input arrays.
How to implement this function:
In order to implement this function you first need to have an existing general 32 bit array. If you don't have an array allocating memory dynamically for the array is system and implementation dependent so I shall not include instructions for that. As long as the elements of the array are in order the array can be high level and contain functions assigned to it. Before you do anything thoughyou should push the reserved registers as well as the link register to the stack. The rest of the inputs required aren't difficult to obtain. Use a bl or bla to the function shall perform it. However, running the function once is not a certainty that the list is sorted. Instead, one iteration of the function only runs through the list once. The return register r4 will indicate whether or not the list is sorted. If r4 is equal 0 it isn't sorted, and if r4 is equal to 1 it is sorted. In order to fully sort a list you should run a while loop whose conditional is r4 equalling 0. If the conditional is checked at the beginning of the loop make sure to set r4 to 0 before the loop first executes. After the while loops ends you can pop the reserved registers from the stack.
If I made any mistakes please tell me. I made sure to flow chart out the code beforehand. You can use this anywhere you want, just credit me.
