I am currently trying to convert a quicksort algorithm in C code into MASM assembly code. I'm having some trouble and it would be great if anyone who has done this before can help me.

Here is the C code



/*
Quick Sort (Sorting array A[size])

While Low is less than High
{
Choose Pivot as the element at position A[Low]
While A[High] is greater than Pivot, decrement High; else move A[High] to A[Low]
While A[Low] is less than Pivot, increment Low; else move A[Low] to A[High]
}
Move Pivot into A[High], see Pivot position as High.
If Low is less than Pivot point, recursively call Quick Sort with Low =
Low, High = Pivot point - 1
If High is greater than Pivot point, recursively call Quick Sort with Low =
Pivot point + 1, High = High.
*/

#define SWAP(x, y) temp = (x); (x) = (y); (y) = temp

void quicksort(int *sort, int low, int high){
int temp;
int pivot;
int m;
int i;
if(low < high){
SWAP(sort[low], sort[(high+low)/2]);
pivot = sort[low];
m = low;
for (i = low + 1; i <= high; i++){
if (sort[i] < pivot) {
m++;
SWAP(sort[m], sort[i]);
}
}
SWAP(sort[low], sort[m]);
quicksort(sort, low, m - 1);
quicksort(sort, m + 1, high);
}
}



Here is what i've worked out so far for the assembly code. I don't expect it to be correct at all.




QSort PROC qARRAY:DWORD, qLOW:DWORD, qHIGH:DWORD
LOCAL temp:DWORD,
pivot:DWORD,
m:DWORD,
i:DWORD,
mid:DWORD,
last:DWORD,
first:DWORD

;if(low < high)
cmp qLOW, qHIGH
jl sort
jmp exit

sort:
;SWAP(sort[low], sort[(high+low)/2]);
mov esi, qARRAY
mov first, [esi+qLOW]

mov eax, [esi+qHIGH]
add eax, first
shr eax, 1
mov mid, eax

xchg first, mid
mov [esi], first

;pivot = sort[low];
mov pivot, [esi]
;m = low;
mov m, qLOW

;for (i = low + 1; i <= high; i++){
;i = low + 1
mov i, qLOW + 1
forloop:
cmp i, qHIGH
jnle exit

;if (sort[i] < pivot)
mov temp, [esi+i]
cmp temp, pivot
jl l1:

;SWAP(sort[m], sort[i]);

l1:
inc m
loop forloop

;SWAP(sort[low], sort[m]);

;quicksort(sort, low, m - 1);
INVOKE QSort, OFFSET qARRAY, ...;

;quicksort(sort, m + 1; high);

exit:
ret
QSort ENDP
Posted on 2005-03-04 18:51:52 by magicgnome
magicgnome,

A reasonable approach is to compiler the C algo with VC making sure you set it to asm output. Turn the optimisation OFF and build it. It will make the code output easier to read if you set the function as __stdcall.

You then need to manually optimise the file yourself and the trick is to set up a test piece and keep checking it after each change so you don't mess the algo up.
Posted on 2005-03-04 20:41:02 by hutch--
Greetings,

you can go to http://www.masmforum.com/simple/index.php to get both answers in case you need.
Posted on 2005-03-04 21:01:28 by Xor Stance
Xor - Both answers? I only asked one question.
hutch - Thanks. I tried disassembling with VC, but the resulting asm code was very optimized and not very readable. I'm not sure what the flags are to turn optimization off.
Posted on 2005-03-04 23:31:08 by magicgnome
Ah, This thread has a good implementation of quicksort.

http://www.win32asmcommunity.net/board/viewtopic.php?t=2361
Posted on 2005-03-05 00:58:36 by magicgnome
I meant when you need to ask something, you can ask there or here; to get different answers. Maybe there you will get the answer faster or here.
Because some members don't like to be there or viceversa or they don't recognize that board or viceversa.

http://flatassembler.net/ another powerful asm where some users register too, just to confirm.
Posted on 2005-03-05 09:14:15 by Xor Stance