PROWAREtech
x86 Assembly: Quick Sort (qsort) Procedure
The famous quicksort algorithm in x86 assembly.
Use MASM for Visual C++ Express Edition 2005 to compile this procedure.
This same procedure is available in 64-bit x64 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. Functions like strcmp and
wcsicmp_asm function in this manner. This version of quick
sort uses insertion sort to sort smaller sub arrays. An example of using the procedure follows.
The procedure token must be proceeded by a underscore so that the linker will find it for a C/C++ compilation.
TITLE 'extern "C" void qisort(void *array[], const unsigned size, int (*compare_func)(const void *element1, const void *element2));'
.386P
.model FLAT
PUBLIC _qisort
_TEXT SEGMENT
_MAX_ISORT_SIZE = 30
_qisort PROC NEAR
push ecx
push ebx
mov ebx, DWORD PTR [esp+16] ; size
cmp ebx, _MAX_ISORT_SIZE
push ebp
push esi
push edi
jbe insertion_sort
quick_sort:
mov eax, DWORD PTR [esp+24] ; array
mov ecx, ebx
shr ecx, 1
mov edx, DWORD PTR [eax+ecx*4]
lea ebp, DWORD PTR [ebx*4]
mov DWORD PTR [esp+28], edx ; [esp+28] = pivot (middle)
mov edi, eax
lea esi, DWORD PTR [eax+ebp-4]
label2:
cmp edi, esi
ja SHORT label7
label3:
mov eax, DWORD PTR [esp+28] ; pivot (middle)
mov ecx, DWORD PTR [edi]
mov ebx, DWORD PTR [esp+32] ; compare_func
push eax
push ecx
call ebx
add esp, 8
test eax, eax
jge SHORT label4
add edi, 4
cmp edi, esi
ja SHORT label8
jmp SHORT label3
label4:
cmp edi, esi
ja SHORT label8
label5:
mov edx, DWORD PTR [esp+28] ; pivot (middle)
mov eax, DWORD PTR [esi]
push edx
push eax
call ebx
add esp, 8
test eax, eax
jle SHORT label6
sub esi, 4
cmp edi, esi
ja SHORT label8
jmp SHORT label5
label6:
cmp edi, esi
ja SHORT label8
mov eax, DWORD PTR [edi]
mov ecx, DWORD PTR [esi]
mov DWORD PTR [edi], ecx
mov DWORD PTR [esi], eax
mov eax, DWORD PTR [esp+24] ; array
add edi, 4
sub esi, 4
jmp SHORT label2
label7:
mov ebx, DWORD PTR [esp+32] ; compare_func
jmp SHORT label9
label8:
mov eax, DWORD PTR [esp+24] ; array
label9:
sub esi, eax
sar esi, 2
push ebx
inc esi
push esi
push eax
call _qisort
mov edx, DWORD PTR [esp+36] ; array
sub ebp, edi
add ebp, edx
sar ebp, 2
mov ebx, ebp
add esp, 12
cmp ebx, _MAX_ISORT_SIZE
mov DWORD PTR [esp+24], edi ; [esp+24] = array
ja quick_sort
insertion_sort:
mov ebp, 1
cmp ebx, ebp
jbe SHORT label14
mov edx, DWORD PTR [esp+24] ; array
lea esi, DWORD PTR [edx+4]
mov DWORD PTR -4+[esp+20], esi
label10:
test ebp, ebp
mov eax, DWORD PTR [esi]
mov DWORD PTR [esp+28], eax ; [esp+28] = temp for swapping
mov edi, ebp
jbe SHORT label13
add esi, -4 ; fffffffcH
label11:
mov ecx, DWORD PTR [esi]
mov edx, DWORD PTR [esp+28] ; [esp+28] = temp for swapping
push ecx
push edx
call DWORD PTR [esp+40] ; compare_func
add esp, 8
test eax, eax
jge SHORT label12
mov eax, DWORD PTR [esi]
mov DWORD PTR [esi+4], eax
dec edi
sub esi, 4
test edi, edi
ja SHORT label11
label12:
mov esi, DWORD PTR -4+[esp+20]
label13:
mov ecx, DWORD PTR [esp+28] ; [esp+28] = temp for swapping
mov edx, DWORD PTR [esp+24] ; array
inc ebp
add esi, 4
cmp ebp, ebx
mov DWORD PTR [edx+edi*4], ecx
mov DWORD PTR -4+[esp+20], esi
jb SHORT label10
label14:
pop edi
pop esi
pop ebp
pop ebx
pop ecx
ret 0
_qisort ENDP
_TEXT ENDS
END
See the x64 assembly example for a study of the quicksort algorithm in assembly.
This is an example program using the above qisort procedure to sort an array of integers.
#include <stdlib.h>
#include <time.h>
extern "C" void qisort(void *array[], const unsigned size, int (*compare_func)(const void *element1, const void *element2));
int compare_ascending(const int a, const int b)
{
return a - b;
}
int array[1000000];
int main()
{
srand(time(NULL));
int i;
unsigned size = sizeof(array)/sizeof(void*);
for(i = 0; i < size; i++)
{
if(rand() % 3 == 0)
array[i] = -rand();
else
array[i] = rand();
}
qisort((void **)array, size, (int (*)(const void*,const void*))compare_ascending);
return 0;
}
This is an example program using the above qisort procedure with objects.
#include <stdio.h>
#include <string.h>
extern "C" void qisort(void *array[], const unsigned size, int (*compare_func)(const void *element1, const void *element2));
class Person
{
char last[100], first[100];
Person(){}
public:
Person(const char *lastname, const char *firstname)
{
strcpy_s(last, lastname);
strcpy_s(first, firstname);
}
const char *lastname() const {return last;}
const char *firstname() const {return first;}
};
int compare_people(const Person *p1, const Person *p2)
{
if(int i = strcmp(p1->lastname(), p2->lastname()))
return i;
return strcmp(p1->firstname(), p2->firstname());
}
int main()
{
Person *array[] = {
new Person("Smith","John"),
new Person("Smith","Jane"),
new Person("Bleaux","Joe"),
new Person("Jackson","Miles"),
new Person("Jackson","Andrew")
};
unsigned size = sizeof(array)/sizeof(void*);
qisort((void **)array, size, (int (*)(const void*,const void*))compare_people);
for(int i = 0; i < size; delete array[i++])
printf("%s, %s\r\n", array[i]->lastname(), array[i]->firstname());
return 0;
}
This quick sort procedure sorts an array of integers.
TITLE 'extern "C" void __stdcall qsort(int array[], const unsigned int size);'
;void __stdcall qsort(int array[], const unsigned int size) {
; if (size > 1) {
; int pivot = array[size / 2];
; int *left = array;
; int *right = array + size - 1;
; while (1) {
; while ((left <= right) && (*left < pivot)) left++;
; while ((left <= right) && (*right > pivot)) right--;
; if (left > right) break;
; int temp = *left;
; *left++ = *right;
; *right-- = temp;
; }
; qisort(array, right - array + 1);
; qisort(left, array + size - left);
; }
;}
.386P
.model FLAT
PUBLIC _qsort@8
_TEXT SEGMENT
_qsort@8 PROC NEAR
;if (size > 1) {
mov eax, DWORD PTR [esp+8] ; size
cmp eax, 1
jbe SHORT label8
push ebx
push ebp
push esi
push edi
mov edi, DWORD PTR [esp+20] ; array
label1:
; int pivot = array[size / 2];
mov ecx, eax
shr ecx, 1
mov edx, DWORD PTR [edi+ecx*4]
; int *left = array;
; int *right = array + size - 1;
lea ebx, DWORD PTR [eax*4]
mov esi, edi
lea eax, DWORD PTR [ebx+edi-4]
label2:
; while (1) {
; while ((left <= right) && (*left < pivot)) left++;
cmp esi, eax
ja SHORT label7
label3:
cmp DWORD PTR [esi], edx
jge SHORT label4
add esi, 4
cmp esi, eax
ja SHORT label7
jmp SHORT label3
label4:
; while ((left <= right) && (*right > pivot)) right--;
cmp esi, eax
ja SHORT label7
label5:
cmp DWORD PTR [eax], edx
jle SHORT label6
sub eax, 4
cmp esi, eax
ja SHORT label7
jmp SHORT label5
label6:
; if (left > right) break;
cmp esi, eax
ja SHORT label7
; int temp = *left;
; *left++ = *right;
mov ebp, DWORD PTR [eax]
mov ecx, DWORD PTR [esi]
mov DWORD PTR [esi], ebp
add esi, 4
; *right-- = temp;
mov DWORD PTR [eax], ecx
sub eax, 4
jmp SHORT label2
label7:
; }
; qsort(array, right - array + 1);
sub eax, edi
sar eax, 2
inc eax
push eax
push edi
call _qsort@8
; qsort(left, array + size - left);
sub ebx, esi
add ebx, edi
sar ebx, 2
mov eax, ebx
cmp eax, 1
mov edi, esi
ja SHORT label1
pop edi
pop esi
pop ebp
pop ebx
label8:
ret 8
_qsort@8 ENDP
_TEXT ENDS
END
This quicksort algorithm uses insertion sort when sorting a subarray of 30 or less elements; so big arrays are sorted with quicksort and insertion sort cleans up the little ones for a roughly 20% performance improvement.
TITLE 'extern "C" void __stdcall qisort(int array[], const unsigned int size);'
;void __stdcall qisort(int array[], const unsigned int size) {
; if (size > 30) {
; int pivot = array[size / 2];
; int *left = array;
; int *right = array + size - 1;
; while (1) {
; while ((left <= right) && (*left < pivot)) left++;
; while ((left <= right) && (*right > pivot)) right--;
; if (left > right) break;
; int temp = *left;
; *left++ = *right;
; *right-- = temp;
; }
; qisort(array, right - array + 1);
; qisort(left, array + size - left);
; }
; else {
; for (unsigned int i = 1; i < size; ++i) {
; int temp = array[i];
; unsigned int j = i;
; while (j > 0 && temp < array[j - 1]) {
; array[j] = array[j - 1];
; j--;
; }
; array[j] = temp;
; }
; }
;}
.386P
.model FLAT
PUBLIC _qisort@8
_TEXT SEGMENT
_MAX_ISORT_SIZE = 30
_qisort@8 PROC NEAR
push ebx
push ebp
;if (size > 30) {
mov ebp, DWORD PTR [esp+12] ; array
push esi
push edi
mov edi, DWORD PTR [esp+24] ; size
cmp edi, _MAX_ISORT_SIZE
jbe SHORT insertion_sort
quick_sort:
; int pivot = array[size / 2];
mov eax, edi
shr eax, 1
mov edx, DWORD PTR [ebp+eax*4]
; int *left = array;
; int *right = array + size - 1;
shl edi, 2
mov esi, ebp
lea eax, DWORD PTR [edi+ebp-4]
quick_sort_loop:
; while (1) {
; while ((left <= right) && (*left < pivot)) left++;
cmp esi, eax
ja SHORT label5
label1:
cmp DWORD PTR [esi], edx
jge SHORT label2
add esi, 4
cmp esi, eax
ja SHORT label5
jmp SHORT label1
label2:
; while ((left <= right) && (*right > pivot)) right--;
cmp esi, eax
ja SHORT label5
label3:
cmp DWORD PTR [eax], edx
jle SHORT label4
sub eax, 4
cmp esi, eax
ja SHORT label5
jmp SHORT label3
label4:
; if (left > right) break;
cmp esi, eax
ja SHORT label5
; int temp = *left;
; *left++ = *right;
mov ebx, DWORD PTR [eax]
mov ecx, DWORD PTR [esi]
mov DWORD PTR [esi], ebx
add esi, 4
; *right-- = temp;
mov DWORD PTR [eax], ecx
sub eax, 4
jmp SHORT quick_sort_loop
label5:
; }
; qisort(array, right - array + 1);
sub eax, ebp
sar eax, 2
inc eax
push eax
push ebp
call _qisort@8
; qisort(left, array + size - left);
sub edi, esi
add edi, ebp
sar edi, 2
cmp edi, _MAX_ISORT_SIZE
mov ebp, esi
ja SHORT quick_sort
;}
;else {
insertion_sort:
; for (unsigned int i = 1; i < size; ++i) {
mov esi, 1
cmp edi, esi
jbe SHORT label10
lea ecx, DWORD PTR [ebp+4]
mov DWORD PTR 8+[esp+12], ecx
label6:
; unsigned int j = i;
; while (j > 0 && temp < array[j - 1]) {
test esi, esi
mov ebx, DWORD PTR [ecx]
mov eax, esi
jbe SHORT label9
; int temp = array[i];
add ecx, -4
label7:
; unsigned int j = i;
; while (j > 0 && temp < array[j - 1]) {
mov edx, DWORD PTR [ecx]
cmp ebx, edx
jge SHORT label8
; array[j] = array[j - 1];
mov DWORD PTR [ecx+4], edx
; j--;
dec eax
sub ecx, 4
test eax, eax
ja SHORT label7
label8:
; unsigned int j = i;
; while (j > 0 && temp < array[j - 1]) {
mov ecx, DWORD PTR 8+[esp+12]
label9:
; }
; else {
; for (unsigned int i = 1; i < size; ++i) {
inc esi
add ecx, 4
cmp esi, edi
; }
; array[j] = temp;
mov DWORD PTR [ebp+eax*4], ebx
mov DWORD PTR 8+[esp+12], ecx
jb SHORT label6
label10:
pop edi
pop esi
pop ebp
pop ebx
ret 8
_qisort@8 ENDP
_TEXT ENDS
END
Comment
