trjhtr

My task was to implement Quick Sort in assembly from pseudocode.

;*******************************************************************************
; This program implements the Quick Sort algorithm and sorts an array
;
; Author: William 
; Date: 4/6/18

 TITLE Quick Sort 
 .386 
 .model flat, stdcall
 .stack 4096

; prototype from Kernel32 lib
ExitProcess PROTO, dwExitCode:DWORD 

.data

; An array of 25 random integers to be sorted
array DWORD 43, 91, 97, 63, 52,
 58, 99, 19, 33, 26,
 77, 11, 41, 89, 27,
 99, 98, 68, 26, 5,
 73, 47, 46, 59, 21 

.code

;-------------------------------------------------------------------------------
; _partition@12 (A , p, r)
;
; Quicksort subroutine
;
; Entry: A @ ebp + 8 ; pointer to array being sorted
; p @ ebp + 12 ; integer index to start of sub-array
; r @ ebp + 16 ; integer index to end of sub-array 
; 
; Local: x ; The pivot 
; i ; index of smaller element
;
; Exit: the index of the pivot stored in eax
;-------------------------------------------------------------------------------
_partition@12:
 ; set up stack, save regs
 push ebp
 mov ebp, esp
 push ebx
 push ecx
 push edx
 push esi
 push edi

; Load function parameters into registers and initialize local variables
 mov ebx, [ebp + 8] ; A stored in ebx
 mov ecx, [ebp + 12] ; p stored in ecx
 mov edx, [ebp + 16] ; r stored in edx
 mov esi, [ebx + edx * 4] ; x initialized to A[r] 
 lea edi, [ecx - 1] ; i initialized to p - 1

 ; Loop from index p to r - 1
 mov eax, ecx ; j (loop count) initialized to p
L2: cmp eax, edx
 jnl endL2

 ; If A[j] <= x
 cmp [ebx + eax * 4], esi
 jnle endIf1
 inc edi ; i = i + 1

 ; swap A[i] with A[j]
 mov ecx, [ebx + edi * 4]
 xchg ecx, [ebx + eax * 4]
 mov [ebx + edi * 4], ecx
endIf1:
 inc eax
 jmp L2
endL2:
 ; swap A[i + 1] with A[r]
 inc edi ; i = i + 1
 mov ecx, [ebx + edi * 4]
 xchg ecx, [ebx + edx * 4]
 mov [ebx + edi * 4], ecx

 mov eax, edi ; return i + 1

 ; clean up stack, restore regs
 pop edi
 pop esi
 pop edx
 pop ecx
 pop ebx
 pop ebp
 ret 12

;-------------------------------------------------------------------------------
; _quickSort@12 (A , p, r)
;
; Sorts array of DWORD integers
;
; Entry: A @ ebp + 8 ; pointer to array to being sorted
; p @ ebp + 12 ; integer index to start of sub-array
; r @ ebp + 16 ; integer index to end of sub-array 
; 
;-------------------------------------------------------------------------------
_quickSort@12:
 ; set up stack, save regs
 push ebp
 mov ebp, esp
 push ebx
 push ecx
 push edx

 ; Load function parameters into registers
 mov ebx, [ebp + 8] ; A stored in ebx
 mov ecx, [ebp + 12] ; p stored in ecx
 mov edx, [ebp + 16] ; r stored in edx

 ; if (p < r)
 cmp ecx, edx
 jnl endIf2

 ;q = Partition(A, p, r) 
 push edx
 push ecx
 push ebx
 call _partition@12 ; q stored in eax

 ;Quicksort(A, p, q - 1)
 dec eax
 push eax
 push ecx
 push ebx
 call _quickSort@12

 ;Quicksort(A, q + 1, r)
 add eax, 2
 push edx
 push eax
 push ebx 
 call _quickSort@12
endIf2:
 ; clean up stack, restore regs
 pop edx
 pop ecx
 pop ebx
 pop ebp
 ret 12

main:
 push 24
 push 0
 push OFFSET array
 call _quickSort@12

 ; array is sorted, but code does not
 ; print it to the console

 INVOKE ExitProcess, 0
 END main

This was the pseudocode I used:

Partition(A, p, r)
x = A[r]
i = p - 1 
for j = p to r - 1
 if A[j] <= x
 i = i + 1
 exchange A[i] with A[j]
exchange A[i + 1] with A[r]
return i + 1

Quicksort(A, p, r)
if p < r
 q = Partition(A, p, r)
 Quicksort(A, p, q - 1)
 Quicksort(A, q + 1, r)

I took the advice given to me on my last post and loaded all function parameters into registers instead of reading and writing to memory over and over. All criticism is appreciated.

This is just a review of the code; I have not verified that the assembly code correctly implements the algorithm in the pseudocode.

Your use of some of the registers is a bit atypical. EAX is typically used as a temporary register or accumulator (so much so that some operations on it have shorter encodings than if those same operations are done with other registers). In your "swap" code, this would normally use EAX instead of ECX. You're using EAX as a count, but you start it off by copying the value from ECX. So just use ECX as the count, and EAX to cycle temporary values thru.

Which leads to my next point: when you make your recursive _quickSort calls, you assume that the value in EAX will not change during the first call, but it can since you're not saving and restoring the value during the call. This will make the second call work on the wrong bounds, resulting in either a longer execution (by sorting a larger area than necessary) or incorrect results (if the full area isn't sorted).

Since _partition is only used locally, it could be given a non-mangled name and parameters passed directly in the registers, rather than using the stack. (The same applies to _quickSort, but if you're going to use this code in a later project, or call it from another language, you might want to keep the passing of parameters on the stack.)

At the end of your while loop (between the endIf1 and endL2 labels), rather than unconditionally jumping to the top of the loop and checking the condition, check the condition and conditionally jump back to the top of the loop. This duplicates the condition check, but avoids an extra jump when the loop terminates. It is also a common optimization in some compiled languages (specifically C and C++).

Your use of negative conditions in conditional jump instructions is (for me) harder to read than the equivalent positive ones. JNL (jump not less) is the same as JGE (jump greater or equal), and JNLE (jump not less or equal) equal to JG (jump greater). Nothing wrong with what you have, but I'm used to the positive versions. Just stay consistent with your usage.