diff options
Diffstat (limited to '')
| -rw-r--r-- | src/insertion_sort.s | 88 |
1 files changed, 43 insertions, 45 deletions
diff --git a/src/insertion_sort.s b/src/insertion_sort.s index 4e7b981..ed4ade2 100644 --- a/src/insertion_sort.s +++ b/src/insertion_sort.s @@ -3,72 +3,70 @@ # PURPOSE : Sorts array A, with references to arrays A_i, based on the given # key in A_i, address and size of A. # INPUTS : rdi = address for A -# rsi = length of A in 64 bit chunks +# rsi = number of coordinates n # rdx = index of key to sort by # OUTPUTS : rax = address for sorted A # CLOBBERS: none -# NOTES : Preserves all registers. Recursive psudocode taken from -# https://en.wikipedia.org/wiki/Insertion_sort # -------------------------------------------- .section .text .globl insertion_sort .type insertion_sort, @function insertion_sort: - # Save registers - push %rbx - push %rbp - push %r12 - push %r13 + push %r8 + push %r9 + push %r10 + push %r11 push %r14 push %r15 + cmp $1, %rsi # n <= 1 -> done + jle done - cmp $0, %rsi # Check if length of array is zero - je end # Jump to end if it is + movq $1, %r15 # i , start with 2nd element - subq $1, %rsi # Decrease size of array - push %rsi # Save array size across recursive call - call insertion_sort # Sort recursively - pop %rsi # Restore array size +loop: + # load A[i] + movq (%rdi,%r15,8), %r8 # pointer to key -> r8 + movq (%r8,%rdx,8), %r9 # key -> r9 - movq (%rdi, %rsi, 8), %rbp # Save address at A[n] in rbp - movq (%rbp, %rdx, 8), %rbx # Save value of A[n] in rbx + # set up index - 1 now + movq %r15, %r14 # j -> r14 + decq %r14 - movq %rsi, %r15 # Save copy of n in r15 - subq $1, %r15 # Make r15 = n-1 = j +inner_loop: + cmpq $0, %r14 # if j < 0 stop + jl insert_key -while: - cmp $0, %r15 # Compare j with 0 - jl end_while # Go to end if less than + # load A[j] + movq (%rdi, %r14, 8), %r10 # pointer to key -> r10 + movq (%r10, %rdx, 8), %r11 # key -> r11 - movq (%rdi, %r15, 8), %rbp # Save address at A[j] to rbp - movq (%rbp, %rdx, 8), %r12 # Move value at A[j] into r12 - cmp %r12, %rbx # Compare A[j] with A[n] - jge end_while # Go to end if greater than or equal + # compare at A[i] with A[j] + cmpq %r11, %r9 + jge insert_key # if A[i] >= A[j] stop - movq %r15, %r14 # Duplicate r15 into r14 - addq $1, %r14 # And add 1: j+1 - movq (%rdi, %r14, 8), %rbp # Save address of A[j+1] in rbp - movq %r12, (%rbp, %rdx, 8) # Move value at A[j] into value at A[j+1] - - subq $1, %r15 # j = j - 1 + # if A[i] < A[j] + movq %r10, 8(%rdi, %r14, 8) # pointer to key of j -> A[j+1] - jmp while # Go back to start of loop + decq %r14 # move to j - 1 + jmp inner_loop -end_while: - addq $1, %r15 # j = j + 1 - movq (%rdi, %r15, 8), %rbp # Move address at A[j] into rbp - movq %rbx, (%rbp, %rdx) # A[j] = x -end: - # Restore registers +insert_key: + movq %r8, 8(%rdi,%r14,8) + + # take the next number now + incq %r15 # i++ + cmpq %rsi, %r15 # if i < n there are still numbers left to be sorted + jl loop + jmp done + +done: + movq %rdi, %rax pop %r15 pop %r14 - pop %r13 - pop %r12 - pop %rbp - pop %rbx - + pop %r11 + pop %r10 + pop %r9 + pop %r8 ret - - |