Wirklich fix für kleine Größen ist Insertion-Sort.
Ok, Insertionsort ist tatsächlich schneller als Bubblesort!
Die Kombination "Quick-/Insertionsort" bringt nochmal ca. 300 ms bei dem 33MP-Bild. Jetzt bin ich bei rund 2700 ms (32-Bit Single-Thread).
Ich lasse jetzt Insertionsort ran, sobald weniger als 32 Pixel in einer Partition sind. Das hat sich bei Versuchen als schnellste Variante ergeben.
Hier ist die neue Version:
AutoIt
#AutoIt3Wrapper_UseX64=n ; 32Bit-Modus
#include <GDIPlus.au3>
#include <Memory.au3>
#include "assembleit2_64.au3"
#Region ASM-Code
#cs _CountUniqueColors ;
Use32 ; 32Bit Modus!
mov esi,dword[esp+4] ; esi = Pixelstruct-Pointer
mov edx,dword[esp+8] ; edx = right & Pixelcounter
;~ _ASMDBG_() ; debug-gui anzeigen
dec edx ; um eins verringern, weil die Pixelstruct bei 0 beginnt
push edx ; edx fuer die Zaehlschleife 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 Pixelstruct sortieren)
pop edx ; edx wiederherstellen
mov eax,1 ; eax auf 1 setzen (Farbzaehler)
mov ebx,dword[esi+edx*4] ; ebx = Farbwert des letzten Pixels (zum Farbvergleich)
@count: ; Zaehlschleife fuer die Farben
dec edx ; Pixelcounter runterzaehlen
mov ecx,dword[esi+edx*4] ; ecx = Farbwert des vorletzten Pixels (zum Farbvergleich)
cmp ecx,ebx ; ecx mit ebx vergleichen
jae @next ; wenn groesser/gleich, dann mit naechsten Pixel weitermachen
inc eax ; wenn kleiner, dann Farbzaehler um eins erhoehen
mov ebx,ecx ; und die dazugehoerige Farbe merken
@next:
cmp edx,0
jnz @count ; wenn noch nicht 0, dann Schleife @count
mov ecx,eax
ret ; Pixelcounter an AutoIt zurueckgeben (eax)
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,32 ; mehr als 32 Pixel?
ja @quick ; wenn ja, dann Quicksort
; Nein, dann Insertionsort
mov edi,ecx
inc edi ; edi = $i = left + 1
@fori:
mov ebx,dword[esi+edi*4] ; ebx = Pixel[Insert]
mov eax,edi ; eax = $j = Insertpos
@forj: ; Einfuegeschleife
cmp eax,ecx ; Anfang erreicht?
jbe @break1 ; Ja, dann @break1
dec eax ; j--
cmp dword[esi+eax*4],ebx ; Pixel[j-1] < Pixel[Insert]
jbe @break2 ; Ja, dann @break2
movd xmm0,dword[esi+eax*4]; Pixel[j-1] holen
inc eax ; j++
movd dword[esi+eax*4],xmm0; als Pixel[j] speichern
dec eax ; j--
jmp @forj ; forj fortsetzen
@break2:
inc eax ; j++ (weil oben [j-1])
@break1:
mov dword[esi+eax*4],ebx ; Pixel[Insert] nach Pixel[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
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
partition:
mov ecx,dword[esp+4] ; ecx = left
mov edx,dword[esp+8] ; edx = right
mov edi,dword[esi+ecx*4] ; edi = Pivotwert = Pixel[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 Pixel[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 Pixel[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] ; Pixel[left] gegen Pixel[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
;~ $binarycode = _AssembleIt2("retbinary", "_CountUniqueColors") ;gibt nur den assemblierten code zurück
;~ ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $binarycode = ' & ($binarycode) & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console
;~ Exit
Global $g_pMem, $g_iMemSize, $bCode, $tCodeBuffer, $hImage, $iW, $iH, $iTimer, $tBitmapData, $pScan0, $tPixel, $pPixel, $tColors, $pColors, $ret
;~ $bCode = "0x8B7424048B5424084A5231C95251E81C0000005AB8010000008B1C964A8B0C9639D973034089CB83FA0075F089C1C38B4C24048B54240839D1735189D029C883F820772C89CF478B1CBE89F839C8761548391C86760E660F6E048640660F7E048648EBE840891C864739D776DAC208005251E818000000595A53525351E8ADFFFFFF5A5B435253E8A3FFFFFFC208008B4C24048B5424088B3C8E89C84889D34340393C8672FA4B393C9E77FA39D8730E8B0C868B149E891486890C9EEBE2C3"
;~ $tCodeBuffer = _dllstructcreate64_("byte[" & StringLen($bCode) / 2 - 1 & "]") ;reserve Memory for opcodes
;~ DllStructSetData($tCodeBuffer, 1, $bCode)
_GDIPlus_Startup()
;~ $hImage = _GDIPlus_BitmapCreateFromFile(@ScriptDir & '\test_4k.jpg')
;~ $hImage = _GDIPlus_BitmapCreateFromFile(@ScriptDir & '\palette.png')
$hImage = _GDIPlus_BitmapCreateFromFile(@ScriptDir & '\test.png')
$aDim = _GDIPlus_ImageGetDimension($hImage)
ConsoleWrite(StringFormat('_GetUniqueColors (ASM)\n%d x %d = %s px\n', $aDim[0], $aDim[1], $aDim[0] * $aDim[1]))
$iTimer = TimerInit()
$tBitmapData = _GDIPlus_BitmapLockBits($hImage, 0, 0, $aDim[0], $aDim[1], BitOR($GDIP_ILMREAD, $GDIP_ILMWRITE), $GDIP_PXF32ARGB)
ConsoleWrite('Zeit (BitmapLockBits): ' & Round(TimerDiff($iTimer), 3) & ' ms' & @CR)
$tPixel = DllStructCreate('dword[' & $tBitmapData.Width * $tBitmapData.Height & '];', $tBitmapData.Scan0) ; erstelle Pixelstruct (dword = 32 Bit pro Pixel)
$pPixel = DllStructGetPtr($tPixel)
ConsoleWrite('Zeit (Pixelstruct): ' & Round(TimerDiff($iTimer), 3) & ' ms' & @CR)
;~ $ret = DllCallAddress("uint:cdecl", DllStructGetPtr($tCodeBuffer), "ptr", $pPixel, "dword", $tBitmapData.Width * $tBitmapData.Height)
;~ $ret = $ret[0]
$ret = _AssembleIt2("dword", "_CountUniqueColors", "ptr", $pPixel, "dword", $tBitmapData.Width * $tBitmapData.Height)
ConsoleWrite('Anzahl der Farben = ' & $ret & @CR)
ConsoleWrite('Zeit: ' & Round(TimerDiff($iTimer), 3) & ' ms' & @CR)
_GDIPlus_BitmapUnlockBits($hImage, $tBitmapData)
$tPixel = 0
$tColors = 0
$tBitmapData = 0
_GDIPlus_BitmapDispose($hImage)
_GDIPlus_Shutdown()
;~ _MemVirtualFree($g_pMem, $g_iMemSize, $MEM_DECOMMIT)
Exit
Func _dllstructcreate64_($struct) ;align auf 16-byte adresse
Local $temp = DllStructCreate($struct)
$g_iMemSize = DllStructGetSize($temp) + 64
Local $ptr = DllStructGetPtr($struct)
Local $a1 = Mod(Number($ptr), 64)
Local $temp = 0
$g_pMem = _MemVirtualAlloc($ptr + $a1, $g_iMemSize, $MEM_COMMIT, $PAGE_EXECUTE_READWRITE)
Local $a2 = Mod(Number($g_pMem), 64) ;rest div 16 adresse = offset
$sstruct = DllStructCreate($struct, (Number($g_pMem) - $a2 + 64))
Return $sstruct ;auf 16 alingned pointer
EndFunc ;==>_dllstructcreate64_
