News:

MASM32 SDK Description, downloads and other helpful links
MASM32.com New Forum Link
masmforum WebSite

Fast bitwise swap?

Started by jj2007, November 17, 2009, 04:52:55 PM

Previous topic - Next topic

dedndave

#15
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)
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
The truth cannot be learned ... it can only be recognized.

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

#18
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:

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

eschew obfuscation

sinsi

Q6600

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.
Light travels faster than sound, that's why some people seem bright until you hear them.

lingo

MichaelW,
Please include this in your test as a bitswap_drizz_1:(not tested) :winkalign 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


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
Light travels faster than sound, that's why some people seem bright until you hear them.

lingo

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

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

Quote from: dedndave on November 19, 2009, 01:55:54 AM
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.
Quote from: sinsi on November 19, 2009, 04:06:31 AM
One day drizz you will comment your code so we know what in the hell you are on about  :bg very cool.
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
The truth cannot be learned ... it can only be recognized.

dedndave

        lea     [reg32+n*reg32]

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

lingo

You can try without lea..:
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

Quote from: lingo on November 19, 2009, 03:51:07 PM
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?
Light travels faster than sound, that's why some people seem bright until you hear them.

jj2007

Quote from: MichaelW on November 19, 2009, 03:57:06 AM
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:

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



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:
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:
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:

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