# Reverse Engineering Challenge 2 from challenges.re

I am trying to solve reverse engineering problem(s) from https://challenges.re/2/ - this is challenge 2 and the target is to get the highest possible level of understanding what the code does.

``````<f>:
0:          mov    eax,DWORD PTR [esp+0x4]
4:          bswap  eax
6:          mov    edx,eax
8:          and    eax,0xf0f0f0f
d:          and    edx,0xf0f0f0f0
13:          shr    edx,0x4
16:          shl    eax,0x4
19:          or     eax,edx
1b:          mov    edx,eax
1d:          and    eax,0x33333333
22:          and    edx,0xcccccccc
28:          shr    edx,0x2
2b:          shl    eax,0x2
2e:          or     eax,edx
30:          mov    edx,eax
32:          and    eax,0x55555555
37:          and    edx,0xaaaaaaaa
3f:          shr    edx,1
41:          or     eax,edx
43:          ret
``````

Here's my approach to solution, in comments. Because the code does not give me an initial starting point, I am assuming the initial value assignment to be `12 34 56 78`:

``````mov    eax,DWORD PTR [esp+0x4] ; eax < 12 34 56 78 (‭305419896‬d)
bswap  eax               ; eax < 78 56 34 12
mov    edx,eax           ; eax = edx = 78 56 34 12
and    eax,0xf0f0f0f         ; eax = 02 04 06 08
and    edx,0xf0f0f0f0        ; edx = 70 50 30 10
shr    edx,0x4           ; edx = 07 05 03 01
shl    eax,0x4           ; eax = 20 40 60 80
or     eax,edx           ; eax = 27 45 63 81
mov    edx,eax           ; edx = eax = 27 45 63 81
and    eax,0x33333333        ; eax = 23 01 23 01
and    edx,0xcccccccc        ; edx = 04 44 40 80
shr    edx,0x2           ; edx = 01 11 10 20
shl    eax,0x2           ; eax = 8C 04 8C 04
or     eax,edx           ; eax = 8D 15 9C 24
mov    edx,eax           ; eax = edx = 8D 15 9C 24
and    eax,0x55555555          ; eax = 05 15 14 04
and    edx,0xaaaaaaaa        ; edx = 88 00 88 20
add    eax,eax           ; eax = 8D 15 9C 24
shr    edx,1             ; edx = 44 00 44 10
or     eax,edx           ; eax = CD 15 D6 34
ret                  ; return eax > CD 15 D6 34 (3440760372d)
``````

What I still don't get is the big picture - seems like some random mathematical operations without a purpose and probably I am wrong. What gives?

• It's probably just compiler optimizations. What might look like a simple formula to you, can look completely different when compiled. For instance, 2*8. Instead of moving 2 into a register, then 8 into another register, then performing a mul on those two values, it may just move a value into a register, then shift it left or right however many bits to end up at the same value. – dsasmblr Jul 24 '18 at 20:12
• @dsasmblr It is optimized, the challenge author wrote it on his page. My idea is, sans optimization, is there any true `purpose` to this code? – Jishan Jul 24 '18 at 21:09
• I think you're just overthinking it. This snippet of code could represent anything, like maybe an obfuscation/encryption routine. Or it could represent nothing meaningful at all, and all you need to understand is that this routine takes a value, modifies it, and returns the modified value. If you were in a much later challenge, I'd think maybe the author wants you to guess what this code looks like in C, but then you'd be studying compiler optimizations per the compiler(s) noted, etc. I think what you did is enough. =) – dsasmblr Jul 24 '18 at 22:52

It is a bit reversal algorithm. I am not sure if the numbers shown for the OP's examples are correct. If I start (in MS VStudios inline assembler) with `0x12345678` (as a `DWORD`), or

``````0001 0010 0011 0100 0101 0110 0111 1000
``````

then I end up with its bit reversal, being `0x1E6A2C48`, or

``````0001 1110 0110 1010 0010 1100 0100 1000
``````

The algorithm looks similar to the "Generalized Bit Reversal" in the Book "Hackers Delight" by Henry S. Warren Jr., 2nd edition, on p.129 (in my pdf version), although not verified. Quote:

``````if (k & 1) x = (x & 0x55555555) << 1 | (x & 0xAAAAAAAA) >> 1;
if (k & 2) x = (x & 0x33333333) << 2 | (x & 0xCCCCCCCC) >> 2;
if (k & 4) x = (x & 0x0F0F0F0F) << 4 | (x & 0xF0F0F0F0) >> 4;
if (k & 8) x = (x & 0x00FF00FF) << 8 | (x & 0xFF00FF00) >> 8;
if (k & 16) x = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >> 16;
// The last two 'and' operations can be omitted.
``````

you probably have some error in the and operation

``````mov eax,DWORD PTR [esp+0x4]     eax =       12 34 56 78
bswap eax                       eax =       78 56 34 12
mov edx,eax                     edx = eax = 78 56 34 12
and eax,0x0f0f0f0f              eax =       08 06 04 02
and edx,0xf0f0f0f0              edx =       70 50 30 10
shr edx,0x4                     edx =       07 05 03 01
shl eax,0x4                     eax =       80 60 40 20
or eax,edx                      eax =       87 65 43 21
mov edx,eax                     edx =       87 65 43 21
and eax,0x33333333              eax =       03 21 03 21
and edx,0xcccccccc              edx =       84 44 40 00
shr edx,0x2                     edx =       21 11 10 00
shl eax,0x2                     eax =       0c 84 0c 84
or eax,edx                      eax =       2d 95 1c 84
mov edx,eax                     edx = eax = 2d 95 1c 84
and eax,0x55555555              eax =       05 15 14 04
and edx,0xaaaaaaaa              edx =       28 80 08 80
add eax,eax                     eax =       0a 2a 28 08
shr edx,1                       edx =       14 40 04 40
or eax,edx                      eax =       1e 6a 2c 48
ret
``````

lets do it in say python

``````>>> a = 0x78563412
>>> b = 0x0f0f0f0f
>>> c = 0xf0f0f0f0
>>> d = 0x33333333
>>> e = 0xcccccccc
>>> temp = (((((a&b)<<4|(a&c)>>4)&d)<<2) | ((((a&b)<<4|(a&c)>>4)&e)>>2))
>>> hex(((temp & 0x55555555 )*2) | (temp & 0xaaaaaaaa) >> 1)
'0x1e6a2c48L'
``````