Rotate Bits SSE

[guga]

Hi Guys

I made a couple of routines to rotate bits from rigth and left using MMX instructions, but i´m failing to do it for Se2. Can someone help ? Also, can these be optimized ?

The MMX instruction are as this:

Rotate Left

Code: [Select]


      rotl64 -  Rotate Left bits in MM0 register N times.

       Parameters:
                   Count (Input). The total amount of times the register should be shifted left

       Return Value:
                    The shifted value is stored in MM0 register. (See also, remarks below)

       Remarks:
                  The function uses MM0 register to perform the rotation. So, on input, MM0 must already be filled.

       Example of usage:

      [tttt: Q$ 1] ; A qword variable that hold "1" as value
      movq MM0 Q$Value
      call rotl64 1 ; rotate 1 left by bit


Proc rotl64:
    Arguments @Count

    mov eax D@Count
    movq MM2 MM0
    movd MM3 eax
    sub eax 64
    neg eax
    movd MM4 eax
    psllq MM0 MM3
    psrlq MM2 MM4
    por MM0 MM2

EndP



Rotate Right

Code: [Select]


      rotr64 -  Rotate Right bits in MM0 register N times.

       Parameters:
                   Count (Input). The total amount of times the register should be shifted right

       Return Value:
                    The shifted value is stored in MM0 register. (See also, remarks below)

       Remarks:
                  The function uses MM0 register to perform the rotation. So, on input, MM0 must already be filled.

      [tttt: Q$ 1] ; A qword variable that hold "1" as value
      movq MM0 Q$Value
      call rotr64 1 ; rotate 1 right by bit

Proc rotr64:
    Arguments @Count

    mov eax D@Count
    movq MM2 MM0
    movd MM3 eax
    sub eax 64
    neg eax
    movd MM4 eax
    psrlq MM0 MM3
    psllq MM2 MM4
    por MM0 MM2

EndP


Now...How to do a similar thing (left and right) for 128 Bits ? I tried this one below, but it is not working :(

Code: [Select]

Proc rot128:
    Arguments @Count

    mov eax D@Count
    movdqu XMM2 XMM0
    movd XMM3 eax
    sub eax 128
    neg eax
    movd XMM4 eax
    psllq XMM0 XMM3
    psrlq XMM2 XMM4
    por XMM0 XMM2

EndP


[daydreamer]

Now...How to do a similar thing (left and right) for 128 Bits ? I tried this one below, but it is not working :(

Code: [Select]

Proc rot128:
    Arguments @Count

    mov eax D@Count
    movdqu XMM2 XMM0
    movd XMM3 eax
    sub eax 128
    neg eax
    movd XMM4 eax
    psllq XMM0 XMM3
    psrlq XMM2 XMM4
    por XMM0 XMM2

EndP


you should use PSLLDQ (double quadword) instead of PSLLQ (only 64bit quadword) versions instead

[jj2007]

you should use PSLLDQ (double quadword) instead of PSLLQ (only 64bit quadword) versions instead

Marinus, Magnus, PSLLDQ shifts bytes while PSLLQ shifts bits.

[mineiro]

The version below is not SSE2. Sorry, I didn't check for optimization or others instructions.

mov rax,0123456789abcdefh   ;high
mov rdx,0123456789abcdefh   ;low
mov ecx,8         ;count
shld rax,rdx,cl         ;shift left rotate higher
shl rdx,cl         ;shift left rotate lower

Rotating to the left is to multiply the number N times by 2. Depending, you may need two variables for the carry even to create a rcl or rol version at each step.
Maybe this can be usefull to others tries.

---edit---
I assembled your source file and now understand. It's something like:

Code: [Select]

mov rax,0f123456789abcdefh ;high
 mov rdx,0123456789abcdefh ;low
 mov rbx,0
 mov ecx,8 ;count
 shld rbx,rax,cl                 ;rbx=high bits of rax
 shld rax,rdx,cl ;rotate n bits agregating
 shl rdx,cl ;shift left rotate lower, inserting zeros at right side
 or rdx,rbx                ;join, logical add


[Siekmanski]

you should use PSLLDQ (double quadword) instead of PSLLQ (only 64bit quadword) versions instead

Marinus, PSLLDQ shifts bytes while PSLLQ shifts bits.

Am I PSHUFD with Magnus? 

[mineiro]

hello sir guga,
This is a quick try;  psllq deals with 2 qwords instead of 1 oword(128)

Code: [Select]

.data
align 32
number    dq 0123456789abcdefh,0fedcba9876543210h
low_mask dq 0ffffffffffffffffh,0000000000000000h ;reversed because using qword
high_mask  dq 0000000000000000h,0ffffffffffffffffh

.code
mov eax,4 ;count
movdqu xmm0,oword ptr [number] ;xmm0=fedcba98765432100123456789abcdef
movdqu xmm1,xmm0
movdqu xmm2,xmm0
pand xmm1,oword ptr [high_mask] ;xmm1=FEDCBA98765432100000000000000000
pand xmm2,oword ptr [low_mask] ;xmm2=00000000000000000123456789ABCDEF
movd xmm3,eax ;xmm3=counter
psllq xmm0,xmm3 ;xmm0=EDCBA98765432100123456789ABCDEF0

sub eax,64
neg eax
movd xmm4,eax ;xmm4=3c
psrlq xmm1,xmm4 ;xmm1=000000000000000F0000000000000000
psrlq xmm2,xmm4 ;xmm2=00000000000000000000000000000000
pxor xmm3,xmm3 ;zero
movhlps xmm3,xmm1 ;high part of 1 to lower part of 3
movlhps xmm3,xmm2 ;lower part of 2 to higher part of 3
;xmm3=0000000000000000000000000000000F
por xmm0,xmm3 ;concatenate

--edit---
I measure both procedures and the first that don't uses SSE perform better in my machine.

[jj2007]

Am I PSHUFD with Magnus? 

Corrected, sorry

[Siekmanski]

No worries, 'The mouth speaks what the heart is full of' 

[guga]

Hi Mineiro, tks, but not working. Try with Rotating 64 and 65 Bits. The result will be 0.

number    dq 0123456789abcdefh,0fedcba9876543210h
The input are:
0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0111_0110_0101_0100_0011_0010_0001_0000_1000_1001_1010_1011_1100_1101_1110_1111

and the output should be:

Rotate 64 Bts
1110_1100_1010_1000_0110_0100_0010_0001_0001_0011_0101_0111_1001_1011_1101_1110_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000

Rotate 65 bits
1101_1001_0101_0000_1100_1000_0100_0010_0010_0110_1010_1111_0011_0111_1011_1100_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0000_0001

[guga]

Ops...edited, wrong

[mineiro]

That's working or not to your needs sir guga? I can change the code to fit your needs.
I suppose shl deals with N-1, so, maximum counter can hold will be 63. Well, now that you said that I need review result with counter being zero, 64 or above.

[guga]

Hi Mineiro

No. It´s not working. The goal is to rotate left and right all the bits on a 128 bit data. What the code was doing is shifting the bits (also only for 64) which causes the zeroing of the lo half of the 128 bits, rather then rotating all bits by XXX times.

[mineiro]

Maybe this can work, please check. If this works we can deal with rotate right.

Code: [Select]

.data
 align 32
 number    dq 3,0
 low_mask dq 0ffffffffffffffffh,0000000000000000h ;reversed because using qword
 high_mask  dq 0000000000000000h,0ffffffffffffffffh

 .code
  mov eax,127 ;count range 0 to 128
  movdqu xmm0,oword ptr [number]
  movdqu xmm1,xmm0
  .if eax >= 64
      movhlps xmm0,xmm1 ;switch high and low
    movlhps xmm0,xmm1
    sub eax,64
  .endif

    movdqu xmm1,xmm0
    movdqu xmm2,xmm0

    pand xmm1,oword ptr [high_mask]
    pand xmm2,oword ptr [low_mask]
    movd xmm3,eax
    psllq xmm0,xmm3

    sub eax,64
    neg eax
    movd xmm4,eax
    psrlq xmm1,xmm4
    psrlq xmm2,xmm4
    pxor xmm3,xmm3
    movhlps xmm3,xmm1
    movlhps xmm3,xmm2
    por xmm0,xmm3


[Siekmanski]

Cool challenge.

EDIT: Sorry, I misunderstood the question and posted the wrong code. 
I'll try again and if it works, post some code that does the job.

[mineiro]

by XXX times.

obscene 

I figured it was not necessary to use masks, I cleaned the code.

Code: [Select]

  mov eax,127 ;count range 0 to 128
  movdqu xmm0,oword ptr [number]

  .if eax >= 64
    movdqu xmm1,xmm0
      movhlps xmm0,xmm1 ;switch high and low
    movlhps xmm0,xmm1
    sub eax,64
  .endif

    movdqu xmm1,xmm0
    movd xmm3,eax
    psllq xmm0,xmm3

    sub eax,64
    neg eax
    movd xmm4,eax
    psrlq xmm1,xmm4
    movhlps xmm3,xmm1
    movlhps xmm3,xmm1
    por xmm0,xmm3