Fast bitwise swap?

[dedndave]

i would think a 256 byte LUT would be a good comprimise between size and speed
really, how fast does this thing need to be ?
just my 2 cents - lol
now, you are 2 cents richer, i guess   :bg
don't spend it all at once

[drizz]

Hello everyone,
:8)

Code Select Expand

MirrorEAX:
bswap eax
mov edx,00001111000011110000111100001111b
and edx,eax
and eax,11110000111100001111000011110000b
shl edx,4
shr eax,4
or eax,edx
mov edx,00110011001100110011001100110011b
and edx,eax
and eax,11001100110011001100110011001100b
shr eax,2
lea eax,[edx*4+eax]; shl edx,2; or eax,edx
mov edx,01010101010101010101010101010101b
and edx,eax
and eax,10101010101010101010101010101010b
shr eax,1
lea eax,[edx*2+eax]; shl edx,1; or eax,edx


[dedndave]

very cool, Drizz   :U
i will have to remember that one - lol
did you just make that up ? - or have you used it before ?

[MichaelW]

The attachment tests everything except the SSE2 code, all for 32-bit values and encapsulated in procedures without a stack frame.
Cycle counts on a P3:

Code Select Expand


27 cycles, qword 256-byte-lut, 313 bytes
101 cycles, dave shr-rcl-loop, 19 bytes
12 cycles, drizz stir-fry, 64 bytes
13 cycles, drizz/lingo, 68 bytes


[sinsi]

Q6600

Code Select Expand


7 cycles, qword 256-byte-lut, 313 bytes
63 cycles, dave shr-rcl-loop, 19 bytes
6 cycles, drizz stir-fry, 64 bytes


One day drizz you will comment your code so we know what in the hell you are on about  :bg very cool.

[lingo]

MichaelW,
Please include this in your test as a bitswap_drizz_1:(not tested) :wink

Code Select Expand

align 16
bitswap_drizz proc ddval:DWORD
pop ecx
pop eax
bswap        eax
mov edx,eax
and eax,11110000111100001111000011110000b
shr eax,4
and edx,00001111000011110000111100001111b
shl edx,4
mov ecx, 00110011001100110011001100110011b
or eax, edx
mov edx, eax
and eax,11001100110011001100110011001100b
shr eax,2
and edx,ecx
lea eax,[edx*4+eax]; shl edx,2; or eax,edx
mov ecx,01010101010101010101010101010101b
        mov             edx,eax
        and eax,10101010101010101010101010101010b
        shr eax,1
and edx,ecx
lea eax,[edx*2+eax]; shl edx,1; or eax,edx
jmp dword ptr [esp-2*4]

[sinsi]

Code Select Expand


7 cycles, qword 256-byte-lut, 313 bytes
63 cycles, dave shr-rcl-loop, 19 bytes
6 cycles, drizz stir-fry, 68 bytes

Replaced. 4 bytes more, jj will not be happy, jan.

edit:replaced into the drizz stir-fry, sorry lingo. :red

[lingo]

sinsi,
Please test it for me too..:
The code is by bitRake and Nexo :wink

Code Select Expand



align 16
bitNexo proc ddval:DWORD
pop  edx
pop  eax
mov  edx,eax
shr  eax,1
and  edx,055555555h
and  eax,055555555h
lea  eax,[2*edx+eax]
mov  edx,eax
shr  eax,2
and  edx,033333333h
and  eax,033333333h
lea  eax,[4*edx+eax]
mov  edx,eax
shr  eax,4
and  edx,0F0F0F0Fh
and  eax,0F0F0F0Fh
shl  edx,4
add  eax,edx
bswap eax
jmp  dword ptr [esp-2*4]

[drizz]

did you just make that up ? - or have you used it before ?

I remembered that i used similar technique for bit count (popcnt), so I just applied that for mirroring.

One day drizz you will comment your code so we know what in the hell you are on about  :bg very cool.

Code Select Expand

0123 4567 89AB CDEF | GHIJ KLMN OPQR STUV
------------------------------------------- swap 16 bits _
GHIJ KLMN OPQR STUV | 0123 4567 89AB CDEF                 \ bswap
------------------------------------------- swap 8 bits  _/
OPQR STUV GHIJ KLMN | 89AB CDEF 0123 4567
------------------------------------------- swap 4 bits
STUV OPQR KLMN GHIJ | CDEF 89AB 4567 0123
------------------------------------------- swap 2 bits
UVST QROP MNKL IJGH | EFCD AB89 6745 2301
------------------------------------------- swap 1 bit
VUTS RQPO NMLK JIHG | FEDC BA98 7654 3210


[dedndave]

        lea     [reg32+n*reg32]

for n <> 1, it isn't a very fast instruction on many processors

[lingo]

You can try without lea..:

Code Select Expand


align 16
swapbits proc ddval:DWORD
pop  ecx
pop  eax
        bswap   eax           
mov     edx,eax       
and     eax,00F0F0F0Fh
xor     edx,eax       
rol     eax,8           
or      eax,edx
mov     edx,eax
and     eax,033333333h
xor     edx,eax
rol     eax,4
or      eax,edx       
mov     edx,eax       
and     eax,055555555h
xor     edx,eax
rol     eax,2
or      eax,edx
ror     eax,7           
jmp     ecx

[dedndave]

i like how you TRIED to sneak those XOR's in there on us - lol
that is the best non-simd code yet, i think

[sinsi]

Code Select Expand

align 16
swapbits proc ddval:DWORD
pop ecx
pop eax
...
jmp ecx

Just a question, aren't cpu's optimised for call/ret?
Wouldn't a simple "mov eax,[esp+4]" with a "ret 4" be quicker?

[jj2007]

The attachment tests everything except the SSE2 code, all for 32-bit values and encapsulated in procedures without a stack frame.
Cycle counts on a P3:

Code Select Expand


27 cycles, qword 256-byte-lut, 313 bytes
101 cycles, dave shr-rcl-loop, 19 bytes
12 cycles, drizz stir-fry, 64 bytes
13 cycles, drizz/lingo, 68 bytes


Code Select Expand

bitswap_qword endp
size_qword = $-bitswap_qword+256

Interesting technique to get the code size, thanks Michael. It fails for ml 9.0 but JWasm and ml 6.14 are fine.
My timings on Celeron M:

Code Select Expand

9 cycles, qword 256-byte-lut, 313 bytes
114 cycles, dave shr-rcl-loop, 19 bytes
9 cycles, drizz stir-fry, 64 bytes
9 cycles, drizz/lingo, 68 bytes

New algos proposed by Lingo:

Code Select Expand

9       cycles for swapbits
7       cycles for bitNexo
9       cycles for bitswap_drizz


[lingo]

"Wouldn't a simple "mov eax,[esp+4]" with a "ret 4" be quicker?"

With my CPU NO...I like drizz's algo so, just copied and changed "mov eax,[esp+4]"&"ret 4"
with "pop ecx"&"jmp ecx" and you can see the difference:

Code Select Expand



C:\My Documents\ASM\bitswap>test
00010010 00110100 01010110 01111000
00011110 01101010 00101100 01001000
00011110 01101010 00101100 01001000
00011110 01101010 00101100 01001000

8 cycles, qword 256-byte-lut, 313 bytes
6 cycles, drizz stir-fry, 64 bytes
3 cycles, drizzNew stir-fry, 61 bytes

Press any key to exit...

3 cycles and 3 bytes less. :wink