[Nottingham] A Little Coding Gem

[Martin]

On 15/11/12 19:57, nlug at lists.grepular.com wrote:
> On 15/11/12 18:08, Martin wrote:
> 
>> Fortune has just served up a little beauty for me just now:
> 
> 
>> n = ((n >>  1) & 0x55555555) | ((n <<  1) & 0xaaaaaaaa); n = ((n
>> >> 2) & 0x33333333) | ((n <<  2) & 0xcccccccc); n = ((n >>  4) & 
>> 0x0f0f0f0f) | ((n <<  4) & 0xf0f0f0f0); n = ((n >>  8) & 
>> 0x00ff00ff) | ((n <<  8) & 0xff00ff00); n = ((n >> 16) & 
>> 0x0000ffff) | ((n << 16) & 0xffff0000);

Listing the g++ assembler for that gives:

( g++ -save-temps -fverbose-asm -masm=intel  bit_reverse.cpp )


        mov     eax, DWORD PTR [rbp-24] # tmp103, z
        mov     DWORD PTR [rbp-20], eax # n, tmp103
        mov     eax, DWORD PTR [rbp-20] # tmp104, n
        sar     eax     # D.21205
        mov     edx, eax        # D.21207, D.21206
        and     edx, 1431655765 # D.21207,
        mov     eax, DWORD PTR [rbp-20] # tmp105, n
        add     eax, eax        # D.21208
        and     eax, -1431655766        # D.21210,
        or      eax, edx        # D.21211, D.21207
        mov     DWORD PTR [rbp-20], eax # n, D.21211
        mov     eax, DWORD PTR [rbp-20] # tmp106, n
        sar     eax, 2  # D.21212,
        mov     edx, eax        # D.21214, D.21213
        and     edx, 858993459  # D.21214,
        mov     eax, DWORD PTR [rbp-20] # tmp107, n
        sal     eax, 2  # D.21215,
        and     eax, -858993460 # D.21217,
        or      eax, edx        # D.21218, D.21214
        mov     DWORD PTR [rbp-20], eax # n, D.21218
        mov     eax, DWORD PTR [rbp-20] # tmp108, n
        sar     eax, 4  # D.21219,
        mov     edx, eax        # D.21221, D.21220
        and     edx, 252645135  # D.21221,
        mov     eax, DWORD PTR [rbp-20] # tmp109, n
        sal     eax, 4  # D.21222,
        and     eax, -252645136 # D.21224,
        or      eax, edx        # D.21225, D.21221
        mov     DWORD PTR [rbp-20], eax # n, D.21225
        mov     eax, DWORD PTR [rbp-20] # tmp110, n
        sar     eax, 8  # D.21226,
        mov     edx, eax        # D.21228, D.21227
        and     edx, 16711935   # D.21228,
        mov     eax, DWORD PTR [rbp-20] # tmp111, n
        sal     eax, 8  # D.21229,
        and     eax, -16711936  # D.21231,
        or      eax, edx        # D.21232, D.21228
        mov     DWORD PTR [rbp-20], eax # n, D.21232
        mov     eax, DWORD PTR [rbp-20] # n.58, n
        mov     edx, eax        # D.21234, n.58
        shr     edx, 16 # D.21234,
        mov     eax, DWORD PTR [rbp-20] # tmp112, n
        sal     eax, 16 # D.21235,
        or      eax, edx        # D.21237, D.21234
        mov     DWORD PTR [rbp-20], eax # n, D.21237


That code uses two registers plus a temporary location.

Mmmm... Can that be done in just two registers on x86_64?...


Cheers,
Martin



-- 
- ------------------ - ----------------------------------------
-    Martin Lomas    - OpenPGP (GPG/PGP) Public Key: 0xCEE1D3B7
- martin @ ml1 co uk - Import from   hkp://subkeys.pgp.net   or
- ------------------ - http:// ml1 .co .uk/martin_ml1_co_uk.gpg