SSE2 16 Byte Integer Vergleich



  • Hallo,

    ich hab einen 16 Byte Typ (uint32_t[4]). Das MSB ist Index 3. Ich möchte nun zwei Werte dieses Typs miteinander vergleichen, ob varA > varB ist.

    Mein Code Ansatz sieht folgendermaßen aus:

    ; lho => EAX
    	; rho => EDX
    _SSE2CmpGt4x16 PROC FAR
    	IF regSave
    		push ebx
    	ENDIF
    
    	movdqa xmm0, XMMWORD PTR [eax]
    	movdqa xmm1, XMMWORD PTR [edx]
    
    	prefetchnta [eax+30h]
    	prefetchnta [edx+30h]
    
    	movdqa xmm2, XMMWORD PTR [eax+10h]
    	movdqa xmm3, XMMWORD PTR [eax+10h]
    
    	movdqa xmm4, XMMWORD PTR [eax+20h]
    	movdqa xmm5, XMMWORD PTR [eax+20h]
    
    	movdqa xmm6, XMMWORD PTR [eax+30h]
    	movdqa xmm7, XMMWORD PTR [eax+30h]
    
    	pcmpgtd xmm0, xmm1
    	pcmpgtd xmm2, xmm3
    	pcmpgtd xmm4, xmm5
    	pcmpgtd xmm6, xmm7
    
    	pmovmskb eax, xmm0
    	pmovmskb ebx, xmm2
    	pmovmskb ecx, xmm4
    	pmovmskb edx, xmm6
    
    	bsr	eax, eax							; search MSB | returns 0-31 or undefined (ZF set)
    	jz _undefined
    	bt eax, 31
    
    _undefined:
    
    	bsr	 ebx, ebx
    	bsr	 ecx, ecx
    	bsr  edx, edx	
    
    	IF regSave
    		pop ebx
    	ENDIF
    
    	ret
    _SSE2CmpGt4x16 ENDP
    

    Wie man sieht, hängt es aber. Wie am Namen evtl. auch zu erkennen ist, werden der Funktion direkt 256 Byte gegeben, um 4x16 Byte auf ein mal miteinander zu vergleichen (das ist so gewünscht).

    Das Problem ist jedoch, dass ich nach dem Aufruf von pcmpgtd nur folgende Informationen gewonnen habe:

    ist x[0] > y[0] ?
    ist x[1] > y[1] ?
    ist x[2] > y[2] ?
    ist x[3] > y[3] ?

    Ich will aber wissen, ob x[0:3] > y[0:3] ist, was sich daraus aber nicht ergibt. Hat jemand eine Idee?



  • du möchtest also zwei 128Bit Integers vergleichen?



  • masm schrieb:

    du möchtest also zwei 128Bit Integers vergleichen?

    Genau.

    Ich hab dafür ja auch eine funktionierende Lösung, allerdings muss man dafür pcmpgtd mit jeweils vertauschten Operanden zweifach ausführen.

    pcmpgtq steht mir auf den Rechnern, wo das Programm laufen soll, leider nicht zur Verfügung.



  • du meinst also eien Vorzeichenlosen Datentyp? Grundsätlich würde ich sagen, das SSE für so etwas nicht geeignet ist (für signed 128Bit kansst du IMO vergessen).

    pcmpeqd vergleicht unter berücksichtigung des Vorzeichens - kann mir also nur schwer vorstellen, dass du es damit überhaupt zum laufen gebracht hast.
    Die einzige Möglichkeit die mir grade einfallen würde, währe mit pmin/maxub + pcmpeqb zu arbeiten - würde dann aber nur für unsigned Integers gehn. Ob sich aber der Aufwand aber lohnt???



  • masm schrieb:

    Ob sich aber der Aufwand aber lohnt???

    Generell kannst du es schon rausfinden. Ist aber extrem umständlich. So sieht's bisher aus (code nicht fertig):

    uint32_t SSE2CmpGt4x16(
    	__in  const uint32_t lho[4],
    	__in  const uint32_t rho[4]
    )
    {
    	__asm
    	{
    [asm]		push ebp								
    		mov  ebp, esp								
    		push ebx									
    
    		mov  eax, lho								
    		mov  edx, rho								
    
    		sub  ebp, 40h								// allocate 64 byte on stack
    		and  ebp, -10h								// align by 16
    
    		movdqa xmm0, XMMWORD PTR [eax]				
    		movdqa xmm1, XMMWORD PTR [edx]				
    
    		prefetchnta [eax+30h]						
    		prefetchnta [edx+30h]						
    
    		movdqa xmm2, XMMWORD PTR [eax+10h]
    		movdqa xmm3, XMMWORD PTR [eax+10h]
    
    		movdqa xmm4, XMMWORD PTR [eax+20h]
    		movdqa xmm5, XMMWORD PTR [eax+20h]
    
    		movdqa xmm6, XMMWORD PTR [eax+30h]
    		movdqa xmm7, XMMWORD PTR [eax+30h]
    
    		pcmpgtd xmm0, xmm1							// lho[0] > rho[0] ?
    		pcmpgtd xmm2, xmm3							// lho[1] > rho[1] ?
    		pcmpgtd xmm4, xmm5							// lho[2] > rho[2] ?
    		pcmpgtd xmm6, xmm7							// lho[3] > rho[3] ?
    
    		movdqa [ebp], xmm0							// save result of xmm0 > xmm1
    		movdqa [ebp+10h], xmm2						// save result of xmm2 > xmm3
    		movdqa [ebp+20h], xmm4						// save result of xmm4 > xmm5
    		movdqa [ebp+30h], xmm6						// save result of xmm6 > xmm7
    
    		movdqa xmm1, XMMWORD PTR [eax]
    		movdqa xmm3, XMMWORD PTR [eax+10h]
    		movdqa xmm5, XMMWORD PTR [eax+20h]
    		movdqa xmm7, XMMWORD PTR [eax+30h]
    
    		pcmpgtd xmm0, xmm1							// rho[0] > lho[0] ?
    		pcmpgtd xmm2, xmm3							// rho[1] > lho[1] ?
    		pcmpgtd xmm4, xmm5							// rho[2] > lho[2] ?
    		pcmpgtd xmm6, xmm7							// rho[3] > lho[3] ?
    
    		movdqa xmm1, [ebp]							// load previous result
    		movdqa xmm3, [ebp+10h]						//			""
    		movdqa xmm5, [ebp+20h]						//			""
    		movdqa xmm7, [ebp+30h]						//			""
    
    		pmovmskb eax, xmm0							// packed move bit mask from lho[0] > rho[0] ?
    		pmovmskb ebx, xmm1							//				""			 lho[0] < rho[0] ?
    		pmovmskb ecx, xmm2							//				""			 lho[1] > rho[1] ?
    		pmovmskb edx, xmm3							//				""			 lho[1] < rho[1] ?
    
    		bsr  eax, eax								// al = MSB of eax
    		setz ah										// if al undefined then ah = 1
    		bsr  ebx, ebx								// bl = MSB of ebx
    		setz bh										// if bl undefined then bh = 1
    		bsr  ecx, ecx								// cl = MSB of ecx
    		setz ch										// if cl undefined then ch = 1
    		bsr  edx, edx								// dl = MSB of edx
    		setz dh										// if dl undefined then dh = 1
    
    		ror eax, 8
    		ror ebx, 8
    		ror ecx, 8
    		ror edx, 8
    
    		cmp  eax, ebx
    		seta ah
    		cmp  ecx, edx
    		seta ch
    
    		movzx eax, ah
    		or   ah, ch
    
    		push eax
    
    		pmovmskb eax, xmm4							// packed move bit mask from lho[2] > rho[2] ?
    		pmovmskb ebx, xmm5							//				""			 lho[2] < rho[2] ?
    		pmovmskb ecx, xmm6							//				""			 lho[3] > rho[3] ?
    		pmovmskb edx, xmm7							//				""			 lho[3] < rho[3] ?
    
    		bsr  eax, eax								// al = MSB of eax
    		setz ah										// if al undefined then ah = 1
    		bsr  ebx, ebx								// bl = MSB of ebx
    		setz bh										// if bl undefined then bh = 1
    		bsr  ecx, ecx								// cl = MSB of ecx
    		setz ch										// if cl undefined then ch = 1
    		bsr  edx, edx								// dl = MSB of edx
    		setz dh										// if dl undefined then dh = 1
    
    		ror eax, 8
    		ror ebx, 8
    		ror ecx, 8
    		ror edx, 8
    
    		cmp  eax, ebx
    		seta ah
    		cmp  ecx, edx
    		seta ch
    
    		movzx edx, ah
    		movzx ecx, ch
    
    		shl  edx, 16
    		shl  ecx, 24
    
    		pop  eax
    
    		or   eax, edx
    		or   eax, ecx
    
    		// eax[0] = lho[0] > rho[0] ?
    		// eax[1] = lho[1] > rho[1] ?
    		// eax[2] = lho[2] > rho[2] ?
    		// eax[3] = lho[3] > rho[3] ?
    
    		pop  ebx									
    		pop  ebp[/asm]									
    	}
    }
    


  • mhh...
    da sind aber ein par Fehler drin:
    Du verwendest eax an Stellen von denen ich anheme das es edx sein sollte.
    Bsp:

    movdqa xmm2, XMMWORD PTR [eax+10h]
            movdqa xmm3, XMMWORD PTR [eax+10h] ;<- edx ?
    

    Und das verstehe ich auch nicht:

    cmp  eax, ebx
            seta ah
            cmp  ecx, edx
            seta ch
    

    Warum Vergleicht du hier Register, die Bits aus verschiedenen Wertepaaren (OWORD's im Array) entahlten ?
    Außerdem Versthe ich nicht, wie du durch Vertauschen der Vergleichoperanden darauf schießt, welches der OWORD's größer/kleiner ist. Könntes du das mal einem Beispiel erklären?

    masm



  • Hier mal mein Vorschlag (von dem ich glaube, dass er jeder normalen x86-Variante unterlegen ist):

    .data
        align 16
        _x dq 0,-1
        _y dq -1,1
    .code
    
        xor ecx,ecx
        movdqa xmm0,OWORD ptr _x
        movdqa xmm4,xmm0
        pminub xmm0,OWORD ptr _y
        pcmpeqb xmm4,OWORD ptr _y   ; cmpGE x,y
        pcmpeqb xmm0,OWORD ptr _y   ; cmpEQ x,y
        psubb xmm0,xmm4             ; xmm0 = cmpGT x,y (gilt nur für die signe-Bits)
    
        pmovmskb eax,xmm0
        pmovmskb edx,xmm4
    @@: test eax,eax
        jz @F
        not edx
        and edx,0ffffh
        bsr eax,eax
        bsr edx,edx
        cmp eax,edx
        sete cl         ; ecx = 1: x > y
    @@:
    


  • upps: die Kommentare in Zeile 11 und 12 sind vertauscht 🤡


  • Mod

    Mein Vorschlag ohne bitscan (+1 sse-instruktion; -7 integer-ops gegenüber masms Version) - wobei ich ebenso davon ausgehe, dass das nichts bringt. Da CPUS, die nur SSE2 unterstützen, grundsätzlich intern 64bit Datenpfade haben, besteht von vornherein bestenfalls eine Chance doppelter Geschwindigkeit gegenüber gewöhnlichen Integeroperationen. Das wird locker durch den erhöhten Organisationsaufwand aufgefressen.

    .data
        align 16
        bias db 16 dup 80h
    .code
    
        movdqa xmm0, bias
        movdqa xmm1, xmm0
        paddb  xmm0, x
        paddb  xmm1, y
        movdqa xmm2, xmm1
        pcmpgtb xmm1, xmm0  ; y > x
        pcmpgtb xmm0, xmm2  ; x > y
        pmovmskb eax, xmm0
        pmovmskb edx, xmm1
        cmp eax, edx
        setg eax
    

    P.S.: Der erhöhte Organisationsaufwand hier primär deshalb, weil pcmpgtb einen signed-Vergleich durchführt, deshalb die vorherige Addition.


Log in to reply