#AutoIt3Wrapper_UseX64=n ; 32Bit-Modus #include #include ;~ #include "assembleit2_64.au3" #Region ASM-Code #cs ASM_Sort Use32 ; 32Bit Modus! mov esi,dword[esp+4] ; esi = Pointer auf die Datenstruct mov edx,dword[esp+8] ; edx = right = Anzahl der Daten dec edx ; um eins verringern, weil die Datenstruct bei 0 beginnt xor ecx,ecx ; ecx (auf 0 setzen) @check1: ; Schleife, zum testen, ob die Daten bereits sortiert sind (aufwaerts) mov eax,dword[esi+ecx*4] ; eax = Data[ecx] inc ecx ; ecx++ cmp ecx,edx ; ecx > edx? ja @SortReturn ; Ja, dann alle Daten getestet, also bereits sortiert (Funktion beenden) cmp eax,dword[esi+ecx*4] jbe @check1 ; Wenn Data[ecx] <= Data[ecx+1], dann weiter mit @check1 xor ecx,ecx ; ecx (auf 0 setzen) @check2: ; Schleife, zum testen, ob die Daten bereits sortiert sind (abwaerts) mov eax,dword[esi+ecx*4] ; eax = Data[ecx] inc ecx ; ecx++ cmp ecx,edx ; ecx > edx? ja @SortReturn ; Ja, dann alle Daten getestet, also bereits sortiert (Funktion beenden) cmp eax,dword[esi+ecx*4] jae @check2 ; Wenn Data[ecx] >= Data[ecx+1], dann weiter mit @check2 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) @SortReturn: 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 (ebx = split) pop ecx edx ; ecx und edx wiederherstellen 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: ; Funktion zum partitionieren der Daten 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 ; right zurueckgeben (ebx) #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 = '0x8B7424048B5424084A31C98B048E4139D1771D3B048E76F331C98B048E4139D1770E3B048E73F331C95251E801000000C38B4C24048B54240839D1735089D029C883F82D7F2B89CF478B1CBE89F839C87614395C86FC760E660F6E4486FC660F7E048648EBE8891C864739D776DBC208005251E818000000595A53525351E8AEFFFFFF5A5B435253E8A4FFFFFFC208008B4C24048B54240889D029C8D1E801C8660F6E048E660F6E0C86660F7E0486660F7E0C8E660F7ECF89C84889D34340393C8672FA4B393C9E77FA39D8730E8B0C868B149E891486890C9EEBE2C3' 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] = $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 ASM-Code aufrufen $iTimer = TimerInit() ;~ $ret = _AssembleIt2('dword', 'ASM_Sort', 'ptr', $pData, 'dword', $iCount) $ret = DllCallAddress('uint:cdecl', $__g_pASMCode, 'ptr', $pData, 'dword', $iCount) $ret = $ret[0] ConsoleWrite(StringFormat('ASM_Sort:\t%.3f ms\n', Round(TimerDiff($iTimer), 3))) #EndRegion ASM-Code aufrufen #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 #Region AutoIt ArraySort $aData = $aRanData ; damit die Ausgangsbedingungen gleich sind $iTimer = TimerInit() _ArraySort($aData, 0, 0, 0, 0, 1) ; mit Dual-Pivot aufrufen (ist hier schneller) ConsoleWrite(StringFormat('_ArraySort:\t%.3f ms\n', Round(TimerDiff($iTimer), 3))) #EndRegion AutoIt ArraySort ;~ _ArrayDisplay($aData) _MemVirtualFree($__g_pMem, $__g_iMemSize, $MEM_DECOMMIT)