### Author Topic: Reverse all bits of a DWORD  (Read 3181 times)

#### AW

• Member
• Posts: 2583
• Let's Make ASM Great Again!
##### Reverse all bits of a DWORD
« on: November 01, 2019, 01:53:40 AM »
For example: ‭‭0010 0110 0111 1000 1001 1001 1001 0101‬‬ should be reversed to: 1010 1001 1001 1001 0001 1110 0110 0100

This is a challenge, the solution with the minimum number of 32-bit ASM instructions wins. I have a solution with 8 instructions. Anyone can do in less?
« Last Edit: November 01, 2019, 02:59:02 AM by AW »

#### hutch--

• Member
• Posts: 8013
• Mnemonic Driven API Grinder
##### Re: Reverse all bits of a DWORD
« Reply #1 on: November 01, 2019, 02:40:17 AM »
I have not got time to do it but what about BSWAP then use a 0 to 255 lookup table ? Should be 5 instructions.
hutch at movsd dot com
http://www.masm32.com

#### AW

• Member
• Posts: 2583
• Let's Make ASM Great Again!
##### Re: Reverse all bits of a DWORD
« Reply #2 on: November 01, 2019, 02:58:32 AM »
I have not got time to do it but what about BSWAP then use a 0 to 255 lookup table ? Should be 5 instructions.

I would rather prefer no lookup tables. However, using BSWAP then reverse the bits in each byte is an idea but should take more than 8 instructions all together.

#### nidud

• Member
• Posts: 2032
##### Re: Reverse all bits of a DWORD
« Reply #3 on: November 01, 2019, 03:25:32 AM »

mov ecx,32
B:  shr edx,1
rcl eax,1
loop B

#### AW

• Member
• Posts: 2583
• Let's Make ASM Great Again!
##### Re: Reverse all bits of a DWORD
« Reply #4 on: November 01, 2019, 03:53:22 AM »

mov ecx,32
B:  shr edx,1
rcl eax,1
loop B

Very good  , eax don't need to be zeroed but you need 1 more instruction to load edx. This makes 5. Probably it is not possible to do better. Congratulations.

This was mine:

Code: [Select]
`       xor eax, eax mov ecx, 32revert: ; revert bits mov ebx, esi add eax, eax and ebx, 1 shr esi, 1 or eax, ebx loop revert`

#### daydreamer

• Member
• Posts: 1466
• building nextdoor
##### Re: Reverse all bits of a DWORD
« Reply #5 on: November 01, 2019, 03:55:44 AM »
For example: ‭‭0010 0110 0111 1000 1001 1001 1001 0101‬‬ should be reversed to: 1010 1001 1001 1001 0001 1110 0110 0100

This is a challenge, the solution with the minimum number of 32-bit ASM instructions wins. I have a solution with 8 instructions. Anyone can do in less?
maybe reciprocal calculation smallest
SIMD fan and macro fan
Happy new year 2021 that can only turn out to become better than worse 2020 :)

#### hutch--

• Member
• Posts: 8013
• Mnemonic Driven API Grinder
##### Re: Reverse all bits of a DWORD
« Reply #6 on: November 01, 2019, 04:14:26 AM »
Loop code has more than 8 executed instructions.
hutch at movsd dot com
http://www.masm32.com

#### TimoVJL

• Member
• Posts: 657
##### Re: Reverse all bits of a DWORD
« Reply #7 on: November 01, 2019, 04:34:07 AM »
Why not in C too
Code: [Select]
`//#include <intrin.h>// 0011 1101 0010 0110// 0110 0100 1011 1100// 3D26h -> 64BC// 0010 0110 0111 1000 1001 1001 1001 0101// 1010 1001 1001 1001 0001 1110 0110 0100// 26789995h -> A9991E64hunsigned char _bittest(const long *valueptr, long index);unsigned char _bittestandset(long *valueptr, long index);#if defined(__clang__)unsigned char _interlockedbittestandreset(volatile long *valueptr, long index);#elseunsigned char _interlockedbittestandreset(long *valueptr, long index);#endifint printf(const char * restrict format, ...);#pragma comment(lib, "msvcrt.lib")void __cdecl mainCRTStartup(void){ //long ul = 0x3D26; long ul = 0x26789995; long ul2 = 0; //int i1 = _bit_scan_forward(ul); // first bit to set //int i2 = _bit_scan_reverse(ul); // last bit to set //for (int i=i1,j=31;i<=i2;i++,j--) { for (int i=0,j=31;i<=31;i++,j--) { if (_bittest((const long int *)&ul, i)) { _bittestandset(&ul2, j); printf("1"); } else { _interlockedbittestandreset(&ul2, j); printf("0"); } } printf("\n%lXh %lXh\n", ul, ul2);}`without header intrin.h, C compilers accept local defines for testing.
EDIT:
Code: [Select]
`unsigned char _bittest(const long *valueptr, long index);unsigned char _bittestandset(long *valueptr, long index);void __cdecl mainCRTStartup(void){ long ul = 0x26789995; long ul2 = 0; for (int i=0,j=31; j; i++,j--) { if (_bittest((const long int *)&ul, i)) _bittestandset(&ul2, j); } printf("\n%lXh %lXh\n", ul, ul2);}`
Code: [Select]
`.386includelib msvcrt.libpublic mainCRTStartup.datafmt db "%lXh %lXh",10,0.codemainCRTStartup:  push ebp  mov ebp, esp  sub esp, 8h  mov dword ptr [ebp-4h], 26789995h  mov dword ptr [ebp-8h], 0h  xor eax, eax  mov edx, 1FhL1:  bt dword ptr [ebp-4h], eax  setb cl  test cl, cl  jz @F  bts dword ptr [ebp-8h], edx@@:  setb cl  add eax, 1h  sub edx, 1h  jnz L1  push dword ptr [ebp-8h]  push dword ptr [ebp-4h]  push offset fmt  call printf  add esp, 0Ch  mov esp, ebp  pop ebp  retend`
Code: [Select]
`void print_bits(long val){ char *p, s[40]; p = s; for (int i=31; i>=0; i--) { if (_bittest((const long int *)&val, i)) *p = '1'; else *p = '0'; //if (val & (1<<i)) *p = '1'; else *p = '0'; p++; if (!(i%4)) { *p = ' '; p++; } } *(--p) = 0; puts(s);}`
« Last Edit: November 01, 2019, 09:07:25 PM by TimoVJL »
May the source be with you

#### jj2007

• Member
• Posts: 11040
• Assembler is fun ;-)
##### Re: Reverse all bits of a DWORD
« Reply #8 on: November 01, 2019, 05:50:36 AM »
Code: [Select]
` or edx, -1 m2m ecx, 32@@: dec ecx jle @F ror eax, 1 jc @B btr edx, ecx jmp @B@@:`

#### AW

• Member
• Posts: 2583
• Let's Make ASM Great Again!
##### Re: Reverse all bits of a DWORD
« Reply #9 on: November 01, 2019, 06:22:29 AM »
Some AMDs have the XOP instruction set which contains an instruction called VPPERM that allows to produce bit reversal. I presume the XOP is deprecated and recent AMDs don't have it.

#### HSE

• Member
• Posts: 1511
• <AMD>< 7-32>
##### Re: Reverse all bits of a DWORD
« Reply #10 on: November 01, 2019, 06:35:20 AM »

Code: [Select]
`edx = 00100110011110001001100110010101y, challenge [awch1.asm, 77]eax = 10101001100110010001111001100100y, Nidud [awch1.asm, 85]eax = 10101001100110010001111001100100y, AW [awch1.asm, 108]edx = 10101001100110010001111001100101y, JJ [awch1.asm, 124]   Oops!`

#### nidud

• Member
• Posts: 2032
##### Re: Reverse all bits of a DWORD
« Reply #11 on: November 01, 2019, 06:53:35 AM »
Code: [Select]
` or edx, -1 m2m ecx, 32@@: dec ecx jle @F ror eax, 1 jc @B btr edx, ecx jmp @B@@:`
ror eax, 1
jc @F
btr edx, ecx
@@:

#### HSE

• Member
• Posts: 1511
• <AMD>< 7-32>
##### Re: Reverse all bits of a DWORD
« Reply #12 on: November 01, 2019, 07:09:19 AM »

Code: [Select]
`edx = 00100110011110001001100110010101y, challenge [awch1.asm, 45]eax = 10101001100110010001111001100100y, Nidud (4 active lines, value in edx) [awch1.asm, 52]eax = 10101001100110010001111001100100y, AW (8 active lines, value in esi) [awch1.asm, 66]edx = 10101001100110010001111001100100y, JJ-Nidud (11 active lines, value in eax) [awch1.asm, 83]`

#### jj2007

• Member
• Posts: 11040
• Assembler is fun ;-)
##### Re: Reverse all bits of a DWORD
« Reply #13 on: November 01, 2019, 08:04:30 AM »
@HSE: Why 11 "active lines"? It's 8 instructions. But if you insist, it can be done in 8 lines, too:
Code: [Select]
` or edx, -1 m2m ecx, 32@@: dec ecx jle \$+11 ror eax, 1 jc @B btr edx, ecx jmp @B`

#### TimoVJL

• Member
• Posts: 657
##### Re: Reverse all bits of a DWORD
« Reply #14 on: November 01, 2019, 08:40:47 AM »
Cleaned from C code:
Code: [Select]
`.386includelib msvcrt.libpublic mainCRTStartup.datafmt db "%lXh %lXh",10,0.codemainCRTStartup:  push ebp  mov ebp, esp  sub esp, 8h  mov dword ptr [ebp-4h], 26789995h  mov dword ptr [ebp-8h], 0h  xor eax, eax  mov edx, 1FhL1:  bt dword ptr [ebp-4h], eax  ;setb cl ; useless  ;test cl, cl ; useless  jnb @F ; jz @F  bts dword ptr [ebp-8h], edx@@:  ;setb cl ; useless  add eax, 1h  sub edx, 1h  jnz L1  push dword ptr [ebp-8h]  push dword ptr [ebp-4h]  push offset fmt  call printf  add esp, 0Ch  mov esp, ebp  pop ebp  retend`
May the source be with you