6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Is the array-to-be-sorted supposed to be hardcoded in or were you supposed to take user input? \$\endgroup\$ – Mast Apr 7 '18 at 9:45
  • \$\begingroup\$ Let me give you a thought experiment: What would happen if you commented out the push edx, mov edx, [ebp + 16], and pop edx from _partition@12? Passing parameters on the stack is a common way to call functions, and there are benefits to using a known and understood parameter passing protocol. But it's not the only way, or even the fastest. For a pure asm program (such as this), passing (some of) the parameters in registers might be useful. \$\endgroup\$ – David Wohlferd Apr 7 '18 at 12:59
  • \$\begingroup\$ @ David Wohlferd If i didn't use edx, I would have to read [ebp + 16] from memory for every iteration of the loop L2, which is supposed to be slow. The rational is that it's better to read it from memory just once into a register. \$\endgroup\$ – William Apr 7 '18 at 14:53
  • \$\begingroup\$ @ Mast We are not given the initial array to be sorted, and I don't know how to generate an array of random integers in assembly, so I just hardcoded one. There is some I/O but I left that out because it was too much code to post here. \$\endgroup\$ – William Apr 7 '18 at 14:58
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @ Regiter use. I've been choosing registers almost arbitrarily! LOL it seems like a bit too much fuss to worry about what roles each reg is supposed to play. I see what you mean about ecx (p), though. It could have been the counter instead of assigning it's value to another counter variable. I didn't notice that. : ) \$\endgroup\$ – William Apr 7 '18 at 23:08
  • \$\begingroup\$ @ EAX in _quicksort. Wow! That's a huge bug I didn't notice. But mysteriously, it works. For the past 30 minutes I've been trying to figure out why the program works. lol I think it's because _quicksort first sets the value of eax (with it's partition call) before it uses it to make other calls. The result is that it's not affected by any changes to eax made by the calling function, and in turn, it doesn't have any affect on it's calls to itself - the net result, nothing changes, no bug. It worked out without having to fix it. lol. I'll save and restore eax anyway to stick to convention. \$\endgroup\$ – William Apr 7 '18 at 23:23
  • \$\begingroup\$ @Calling covention in partition. This is a good point, i never thought of that. We're supposed to stick to std_call convention, but you're right. If it's a subroutine that's only used by this function, there's no reason to stick to any specific convention. No need to even bother with a stack frame. Good observation. \$\endgroup\$ – William Apr 7 '18 at 23:34
  • \$\begingroup\$ @Duplicate coditional jmp. Hmmm. This never crossed my mind cause that's not even possible in the control structures in high level languages. That's like a combination of while and do-while. But is saving a jump instruction really more efficient than duplicating cmp instructions? \$\endgroup\$ – William Apr 7 '18 at 23:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.