Skip to content

Instantly share code, notes, and snippets.

@baines baines/quicksort.s
Last active Jan 16, 2017

Embed
What would you like to do?
x86_64 asm quicksort
#!/bin/bash
# (gdb) r
# -> SIGTRAP
# (gdb) x/12g $rax
# -> stuff is sorted
// 2>/dev/null; as -g $0 -o $0.o && ld $0.o -o $0.bin && gdb $0.bin; exit
.data
stuff: # numbers to sort
.quad 74, 3, 53, 11, 52, 94, 16, 12, 48, 88, 19, 82
len = (. - stuff) / 8
.text
.global _start
quicksort:
dec %rdi # base case
jle end
push %rbx
mov %rdi, %rax # swap index -> rax
lea (%rsi, %rdi, 8), %rbx # pivot addr -> rbx
mov %rdi, %rcx # loop counter -> rcx
mov (%rbx), %r8 # pivot value -> r8
compare:
mov -8(%rsi, %rcx, 8), %rdx
cmp %r8, %rdx # compare array[rcx-1] against pivot
jl noswap
xchg %rdx, -8(%rsi, %rax, 8)# swap array[rcx-1] and index if pivot bigger
mov %rdx, -8(%rsi, %rcx, 8)
dec %rax # and decrease the index
noswap:
loop compare # keep comparing until %rcx == 0
xchg %r8, (%rsi, %rax, 8) # done comparing, swap pivot into position
mov %r8, (%rbx)
sub %rax, %rdi # calc size for 2nd recursion
push %rdi # and store in stack
mov %rax, %rdi # set new size argument for 1st recursion
lea 8(%rsi, %rax, 8), %rax # calc array for 2nd recursion
push %rax # and store in stack
call quicksort # do 1st/lower recursion
pop %rsi # get stuff back off the stack
pop %rdi
pop %rbx
jmp quicksort # tail recursion for 2nd/upper section
# quicksort(array + index + 1, size - index - 1)
end:
ret
_start:
sub $8, %rsp
mov $stuff, %rsi
mov $len, %rdi
call quicksort
mov $stuff, %rax # put &stuff in %rax for gdb
int $3 # breakpoint
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.