#AutoIt3Wrapper_UseX64=n ; 32Bit-Modus #include #include #include "assembleit2_64.au3" #Region ASM-Code #cs ASM_Sort Use32 ; 32Bit Modus! mov edi,dword[esp+4] ; edi = Pointer auf die Paramstruct mov esi,dword[edi] ; esi = Pointer auf die Datenstruct mov edx,dword[edi+4] ; edx = right = Anzahl der Daten dec edx ; um eins verringern, weil die Datenstruct bei 0 beginnt mov eax,dword[edi+8] ; eax = ThreadID movd xmm2,eax ; xmm2 = ThreadID sichern xor ecx,ecx ; ecx = left (auf 0 setzen) push edx ecx ; right und left auf den Stack (fuer Quicksort) call quicksort ; Quicksort aufrufen (die Datenstruct sortieren) ret ; Daten sortiert (Funktion beenden) quicksort: ; die Quick-/Insertionsort-Funktion mov ecx,dword[esp+4] ; ecx = left mov edx,dword[esp+8] ; edx = right cmp ecx,edx ; left und right vergleichen jae @end ; wenn left >= right, dann Funktion beenden mov eax,edx sub eax,ecx ; right - left cmp eax,45 ; mehr als 45 Elemente? jg @quick ; wenn ja, dann Quicksort mov edi,ecx ; Nein, dann Insertionsort inc edi ; edi = $i = left + 1 @fori: mov ebx,dword[esi+edi*4] ; ebx = Data[Insert] mov eax,edi ; eax = $j = Insertpos @forj: ; Einfuegeschleife cmp eax,ecx ; Anfang erreicht? jbe @break ; Ja, dann @break cmp dword[esi-4+eax*4],ebx ; Data[j-1] < Data[Insert] jbe @break ; Ja, dann @break movd xmm0,dword[esi-4+eax*4] ; Data[j-1] holen movd dword[esi+eax*4],xmm0 ; als Data[j] speichern dec eax ; j-- jmp @forj ; forj fortsetzen @break: mov dword[esi+eax*4],ebx ; Data[Insert] nach Data[j] speichern inc edi ; i++ cmp edi,edx ; i > right jbe @fori ; Nein, dann @fori ret 8 ; Insertionsort beendet, Funktion verlassen @quick: ; hier beginnt der Quicksort-Bereich push edx ecx ; edx und ecx auf den Stack (fuer Partition) call partition ; Partition aufrufen Return = ebx (Splitposition) pop ecx edx ; ecx und edx wiederherstellen movd eax,xmm2 ; ThreadID wiederherstellen cmp eax,0 ; ThreadID = 0 (Master-Thread)? jnz @f ; Nein, dann ueberspringen mov eax,ebx ; Ja, dann eax = ebx (Splitposition) ret 8 ; Funktion verlassen (eax = Rueckgabe an AutoIt) @@: push ebx edx ; Register sichern push ebx ecx ; ebx und ecx auf den Stack (right und left fuer Quicksort) call quicksort ; Quicksort aufrufen (rekursiv) pop edx ebx ; Register wiederherstellen inc ebx ; ebx++ push edx ebx ; edx und ebx auf den Stack (right und left fuer Quicksort) call quicksort ; Quicksort aufrufen (rekursiv) @end: ret 8 ; Quicksort-Funktion beendet (2 DWORDs = 8 Byte vom Stack loeschen) partition: mov ecx,dword[esp+4] ; ecx = left mov edx,dword[esp+8] ; edx = right mov eax,edx ; eax = edx (right) sub eax,ecx ; eax = eax - ecx (right minus left) shr eax,1 ; eax shift right (geteilt durch 2) add eax,ecx ; eax += ecx (= middle) movd xmm0,dword[esi+ecx*4] movd xmm1,dword[esi+eax*4] ; swap Data[left] <-> Data[middle] movd dword[esi+eax*4],xmm0 movd dword[esi+ecx*4],xmm1 movd edi,xmm1 ; edi = Pivotwert = Data[left] mov eax,ecx dec eax ; eax = left - 1 mov ebx,edx inc ebx ; ebx = right + 1 @loop: ; Hauptschleife @left: ; Schleife fuer die linke Seite inc eax ; left++ cmp dword[esi+eax*4],edi ; Vergleich Data[left] mit Pivotwert jb @left ; wenn kleiner, dann Schleife @left @right: ; Schleife fuer die rechte Seite dec ebx ; right-- cmp dword[esi+ebx*4],edi ; Vergleich Data[right] mit Pivotwert ja @right ; wenn groesser, dann Schleife @right cmp eax,ebx ; Vergleich left und right jae @return ; wenn groesser/gleich, dann @return mov ecx,dword[esi+eax*4] ; Data[left] gegen Data[right] austauschen mov edx,dword[esi+ebx*4] mov dword[esi+eax*4],edx mov dword[esi+ebx*4],ecx jmp @loop ; und mit @loop fortfahren @return: ret #ce #EndRegion ASM-Code #region AssembleIt ; wenn diese 3 Zeilen aktiv sind, dann wird der obige ASM-Code in Binaercode umgewandelt ;~ $binarycode = _AssembleIt2('retbinary', 'ASM_Sort') ; gibt nur den assemblierten code zurück ;~ ConsoleWrite('$binarycode = "' & $binarycode & '"' & @CRLF) ;~ Exit #EndRegion AssembleIt #Region ASM-Binaercode ; $__g_bASMCode entspricht dem obigen ASM-Code im Binaerformat Global Const $__g_bASMCode = '0x8B7C24048B378B57044A8B4708660F6ED031C95251E801000000C38B4C24048B54240839D1735E89D029C883F82D7F2B89CF478B1CBE89F839C87614395C86FC760E660F6E4486FC660F7E048648EBE8891C864739D776DBC208005251E826000000595A660F7ED083F800750589D8C2080053525351E8A0FFFFFF5A5B435253E896FFFFFFC208008B4C24048B54240889D029C8D1E801C8660F6E048E660F6E0C86660F7E0486660F7E0C8E660F7ECF89C84889D34340393C8672FA4B393C9E77FA39D8730E8B0C868B149E891486890C9EEBE2C3' Global Const $__g_iMemSize = StringLen($__g_bASMCode) / 2 - 1 ; Codelaenge ermitteln Global Const $__g_pMem = _MemVirtualAlloc(0, $__g_iMemSize, $MEM_COMMIT, $PAGE_EXECUTE_READWRITE) ; Virtuellen Speicher reservieren If $__g_pMem = 0 Then Exit MsgBox(16, 'Error!', "Can't allocate virtual memory!") Global $__g_tASMCode = DllStructCreate('byte[' & $__g_iMemSize & ']', $__g_pMem) ; Structur fuer den Binaercode erstellen DllStructSetData($__g_tASMCode, 1, $__g_bASMCode) ; den Binaercode in die Structur schreiben Global $__g_pASMCode = DllStructGetPtr($__g_tASMCode) ; den Pointer der Structur holen ConsoleWrite(StringFormat('ASM-Code-Size:\t%i Bytes\n', $__g_iMemSize)) #EndRegion ASM-Binaercode #Region Test-Vorbereitungen Global $iCount = 1000000, $iTimer, $ret ; $iCount = Anzahl der Array-Elemente Global $aRanData[$iCount], $aData ConsoleWrite(StringFormat('Test-Array:\t%i Elemente\n', $iCount)) #EndRegion Test-Vorbereitungen #Region Zufalls-Array erstellen $iTimer = TimerInit() For $i = 0 To $iCount - 1 ;~ $aRanData[$i] = Random(0, 2^31-1, 1) ;~ $aRanData[$i] = 1 + $i ; aufwaerts sortiert $aRanData[$i] = $iCount - $i ; abwaerts sortiert Next ;~ $tmp = $aRanData[$iCount - 1] ; swap A[last] <-> A[0] ;~ $aRanData[$iCount - 1] = $aRanData[0] ;~ $aRanData[0] = $tmp ConsoleWrite(StringFormat('ArrayCreate:\t%.3f ms\n\n', Round(TimerDiff($iTimer), 3))) #EndRegion Zufalls-Array erstellen #Region Array2Struct $aData = $aRanData ; damit die Ausgangsbedingungen gleich sind $iTimer = TimerInit() Global $tData = DllStructCreate('dword[' & $iCount & ']') Global $pData = DllStructGetPtr($tData) For $i = 0 To $iCount - 1 DllStructSetData($tData, 1, $aData[$i], $i + 1) Next ConsoleWrite(StringFormat('Array2Struct:\t%.3f ms\n', Round(TimerDiff($iTimer), 3))) #EndRegion Array2Struct #Region Master-Thread ; der Master-Thread nimmt die erste Partitionierung vor und die beiden Partitionen ; werden dann von den beiden Einzelthreads parallel sortiert $iTimer = TimerInit() Global $iThreads = 3, $atParam[$iThreads], $apParams[$iThreads], $iSplit, $ahThread[2] For $i = 0 To $iThreads - 1 $atParam[$i] = DllStructCreate('ptr data;dword count;dword threadid') $apParams[$i] = DllStructGetPtr($atParam[$i]) Next DllStructSetData($atParam[0], 'data', $pData) DllStructSetData($atParam[0], 'count', $iCount) DllStructSetData($atParam[0], 'threadid', 0) $ret = DllCallAddress('uint:cdecl', $__g_pASMCode, 'ptr', $apParams[0]) $iSplit = $ret[0] ConsoleWrite(StringFormat('Split-Element:\t%.i\n', $iSplit)) ;~ ConsoleWrite(StringFormat('Split-Thread:\t%.3f ms\n', Round(TimerDiff($iTimer), 3))) #EndRegion Master-Thread #Region Multi-Thread ; die Uebergabeparameter in die Parameter-Struct fuer beide Threads eintragen DllStructSetData($atParam[1], 'data', $pData) DllStructSetData($atParam[1], 'count', $iSplit - 1) DllStructSetData($atParam[1], 'threadid', 1) DllStructSetData($atParam[2], 'data', $pData + ($iSplit + 1) * 4) DllStructSetData($atParam[2], 'count', $iCount - $iSplit - 1) DllStructSetData($atParam[2], 'threadid', 1) $ret = DllCall("kernel32.dll", "hwnd", "CreateThread", "ptr", 0, "dword", 0, "long", $__g_pASMCode, "ptr", $apParams[1], "long", 0, "int*", 0) $ahThread[0] = $ret[0] $ret = DllCall("kernel32.dll", "hwnd", "CreateThread", "ptr", 0, "dword", 0, "long", $__g_pASMCode, "ptr", $apParams[2], "long", 0, "int*", 0) $ahThread[1] = $ret[0] Global $iExit Do $iExit = 0 For $i = 0 To UBound($ahThread) - 1 $ret = DllCall("Kernel32.dll", "uint64", "GetExitCodeThread", "ptr", $ahThread[$i], "dword*", 0) If $ret[2] <> 259 Then $iExit += 1 Next Until $iExit = UBound($ahThread) ConsoleWrite(StringFormat('ASM_Sort:\t%.3f ms\n', Round(TimerDiff($iTimer), 3))) #EndRegion Multi-Thread #Region Struct2Array $iTimer = TimerInit() For $i = 0 To $iCount - 1 $aData[$i] = DllStructGetData($tData, 1, $i + 1) Next ConsoleWrite(StringFormat('Struct2Array:\t%.3f ms\n\n', Round(TimerDiff($iTimer), 3))) #EndRegion Struct2Array ;~ _ArrayDisplay($aData) _MemVirtualFree($__g_pMem, $__g_iMemSize, $MEM_DECOMMIT)