TITLE q.asm
comment|
Makes a console program q.exe illustrating the QuickSort algo.
sample build-file:
if exist q.obj del q.obj
if exist q.exe del q.exe
\masm32\bin\ml /c /coff q.asm
if errorlevel 1 goto end
\masm32\bin\Link /SUBSYSTEM:CONSOLE q.obj
if errorlevel 1 goto end
dir q.exe
:end
|
.386
.model flat, stdcall
option casemap :none
include \masm32\include\kernel32.inc
includelib \masm32\lib\kernel32.lib
QuickSort PROTO :DWORD,:DWORD,:DWORD
.data
mydata dd " EEE"," FFF"," DDD"," AAA"," GGG"," BBB"," CCC"
myitemcount equ 7
myscratch dd myitemcount dup (?) ;work area of the same size as the data
AmtWritten dd ?
.code
mycomparer:
;The input to the comparer routine is a pair (eax,edx), which in practice might be e.g. the
;addresses of two asciiz strings to compare lexicographically. The comparer routine returns
;its result in the flags. The comparer must save ebp, ebx, esi, and DF.
cmp eax,edx ;Trivial routine, for illustration.
ret
Go:
mov ebx,offset mycomparer
invoke QuickSort, myitemcount, addr myscratch, addr mydata
invoke GetStdHandle, -11 ; = STD_OUTPUT_HANDLE
invoke WriteConsoleA, eax, addr mydata, 4*myitemcount, addr AmtWritten, 0
invoke ExitProcess,0
QuickSort PROC itemcount:DWORD,scratchsite:DWORD,datasite:DWORD
LOCAL nextlower:DWORD,nexthigher:DWORD,pivotsite:DWORD
mov eax,scratchsite
mov nextlower,eax ;nextlower and nexthigher are pointers for MainLoop.
mov eax,itemcount ;nextlower starts at the bottom of the work area and
dec eax ;gets incremented. nexthigher starts at the top and
jle QuickSort_ret ;gets decremented.
mov ecx,eax ;loop count
shl eax,2 ;4 bytes per item
add eax,scratchsite
mov nexthigher,eax
mov esi,datasite
lodsd
xchg eax,edx ;edx will be pivot
MainLoop: ;Mainloop puts one item in its final location and all
lodsd ;the others either above or below that item.
push eax
push edx
push ecx
call ebx
pop ecx
pop edx
pop eax
jb short @F ;i.e. jump if the pivot edx is bigger than eax
mov edi,nexthigher
stosd
sub nexthigher,4
jmp short LoopMainLoop
@@:
mov edi,nextlower
stosd
mov nextlower,edi
LoopMainLoop:
loop MainLoop
mov edi,nextlower ;At this point nexthigher = nextlower + 4
mov [edi],edx ;Poke edx into its final location
mov pivotsite,edi
mov eax,edi ;Will calculate new itemcount, for the lower chunk, in eax.
mov esi,scratchsite
sub eax,esi
mov edi,datasite
mov ecx,itemcount
rep movsd ;copy the scratch area to the data area
shr eax,2
;sort the stuff below the pivot:
invoke QuickSort,eax,scratchsite,datasite
;for the stuff above the pivot, we calculate the datasite in edx,
;scratchsite in ecx, and itemcount in eax.
mov eax,pivotsite
mov ecx,eax
add ecx,4
mov edx,ecx
sub edx,scratchsite
add edx,datasite
sub eax,scratchsite
shr eax,2
neg eax
add eax,itemcount
dec eax
;ready to do the stuff above the pivot:
invoke QuickSort,eax,ecx,edx
QuickSort_ret:
ret
QuickSort ENDP
END Go