PROWAREtech
x64 Assembly: Quick Sort (qsort) Procedure
The famous quicksort algorithm in x86-64 (64-bit) assembly.
This code was compiled and tested on Visual Studio 2022.
This same procedure is available in x86 Assembly.
Quicksort is a great, reliable general purpose sorting algorithm. The TITLE
is the C/C++ function declaration.
This short procedure can sort an array of pointers to strings or objects... or anything. compare_func
must return less than zero when element1
is less than element2
, zero when they are equal, and greater than zero when element1
is greater than element2
.This version of quick sort uses insertion sort to sort smaller sub arrays.
TITLE 'extern "C" void qisort(void* array_to_sort[], const unsigned long long array_size, long long (*compare_func)(const void* element1, const void* element2));'
PUBLIC qisort
_TEXT SEGMENT
array_to_sort = 40
array_size = 48
qisort PROC
mov QWORD PTR [rsp+16], rdx
mov QWORD PTR [rsp+8], rcx
sub rsp, 32
cmp QWORD PTR array_size[rsp], 30
ja quick_sort
insertion_sort:
mov r15, QWORD PTR array_to_sort[rsp]
mov r9, 1
insertion_sort_main_loop:
mov rax, QWORD PTR array_size[rsp]
cmp r9, rax
jae exit
mov r11, QWORD PTR [r15+r9*8]
mov r10, r9
insertion_sort_sub_loop:
cmp r10, 0
jbe SHORT exit_insertion_sort_sub_loop
mov rdx, QWORD PTR [r15+r10*8-8]
mov rcx, r11
call r8 ; call the compare_func function
test rax, rax
jge SHORT exit_insertion_sort_sub_loop
mov rdx, QWORD PTR [r15+r10*8-8]
mov QWORD PTR [r15+r10*8], rdx
dec r10 ; r10 is a local variable used for indexing
jmp SHORT insertion_sort_sub_loop
exit_insertion_sort_sub_loop:
mov QWORD PTR [r15+r10*8], r11
inc r9 ; r9 is a local variable used for indexing
jmp insertion_sort_main_loop
quick_sort:
mov rax, QWORD PTR array_size[rsp]
shr rax, 1 ; divide array_size by 2
mov r15, QWORD PTR array_to_sort[rsp]
mov r12, QWORD PTR [r15+rax*8]
mov r14, r15 ; move array_to_sort to left (r14)
mov rax, r15 ; load array_to_sort pointer value
mov r15, QWORD PTR array_size[rsp] ; load array_size
lea r13, QWORD PTR [rax+r15*8-8] ; the right (r13) equals array_to_sort + array_size - 8 bytes
quick_sort_sub_loop_1:
cmp r14, r13 ; compare left (r14) to right (r13)
ja SHORT quick_sort_sub_loop_2
mov rdx, r12 ; move pivot into rdx for call compare_func
mov rcx, QWORD PTR [r14] ; move left into rcx for call compare_func
call r8 ; call the compare_func function
test rax, rax
jge SHORT quick_sort_sub_loop_2
add r14, 8 ; increment left (r14) eight bytes
jmp SHORT quick_sort_sub_loop_1
quick_sort_sub_loop_2:
cmp r14, r13 ; compare left (r14) to right (r13)
ja SHORT quick_sort_check_left_greater_than_right
mov rdx, r12 ; move pivot into rdx for call compare_func
mov rcx, QWORD PTR [r13]
call r8 ; call the compare_func function
test rax, rax
jle SHORT quick_sort_check_left_greater_than_right
sub r13, 8 ; decrement right (r13) eight bytes
jmp SHORT quick_sort_sub_loop_2
quick_sort_check_left_greater_than_right:
cmp r14, r13 ; compare left (r14) to right (r13)
jbe SHORT quick_sort_swap
jmp SHORT call_quick_sort
quick_sort_swap:
mov r11, QWORD PTR [r14] ; move left (r14) value to temp varaible (r11)
mov rcx, QWORD PTR [r13] ; move right (r13) value to rcx
mov QWORD PTR [r14], rcx ; move ecx to left (r14) value
add r14, 8 ; increment left (r14) eight bytes
mov QWORD PTR [r13], r11
sub r13, 8 ; decrement right (r13) eight bytes
jmp quick_sort_sub_loop_1
call_quick_sort:
mov rax, QWORD PTR array_to_sort[rsp]
mov rcx, r13 ; move right (r13) to rcx
sub rcx, rax
mov rdx, rcx
sar rdx, 3
inc rdx ; rdx is the new array_size value (right - array_to_sort + 8 bytes)
mov rcx, QWORD PTR array_to_sort[rsp] ; rcx is the pointer to array_to_sort
call qisort ; r8 is already set to compare_func
mov rax, QWORD PTR array_to_sort[rsp]
mov rcx, QWORD PTR array_size[rsp]
lea rax, QWORD PTR [rax+rcx*8]
sub rax, r14 ; subtract left (r14 - pointer) from rax
sar rax, 3
mov rdx, rax ; set rdx to new array_size (array_to_sort - array_size * 8 - left (r14))
mov rcx, r14 ; set rcx to left (r14) which is the new array_to_sort value
call qisort ; r8 is already set to compare_func
exit:
add rsp, 32
ret 0
qisort ENDP
_TEXT ENDS
END
Comment