'and' conditional strange value explanation [X86 Assembly]

Question

i'm new to X86 Assembly programming and i have a few beginner questions i cant seem to find the answer to. I have the following code, that i for the most part, understand:

        mov    edx,edi
        shr    edx,1
        and    edx,0x55555555
        sub    edi,edx
        mov    eax,edi
        shr    edi,0x2
        and    eax,0x33333333
        and    edi,0x33333333
        add    edi,eax
        mov    eax,edi
        shr    eax,0x4
        add    eax,edi
        and    eax,0xf0f0f0f
        imul   eax,eax,0x1010101
        shr    eax,0x18
        ret

My questions are, first of all, what value gets put into edx on the first line?

My main question though, is what are the hexadecimal values and what do they do... i converted them to decimal to see if they had any special meaning but they seem to be random hexadecimal values and i don't quite understand what they do.

Last question is, if i have a value in edx and i do:

mov eax,edi

Does this remove the value from edi or does it just make a copy of it and store it in the eax register?

Any help would be appreciated.

Answer 1

An explanation of the code. It generates the number of bits set in edi. Commented code. It would help to step through the code to see what is going on. The clever code is the initial instructions. Looking at each of the 16 2 bit fields, the values can be 0,1,2,3. The right shift, and 5, puts the msb into the lsb of each 2 bit field. The subtract (edi -= edx) converts each 2 bit field into a count, 0->0, 1->1, 2->1, 3->2. After that, 2 bit fields are added to form 4 bit fields, then 4 bit fields added to form 8 bit fields, and a multiply used to sum up the 8 bit fields.

        mov     edx,edi                 ;edx = edi
        shr     edx,1                   ;mov upr 2 bit field bits to lwr
        and     edx,055555555h          ; and mask them
        sub     edi,edx                 ;edi = 2 bit field counts
                                        ; 0->0, 1->1, 2->1, 3->1
        mov     eax,edi
        shr     edi,02h                 ;mov upr 2 bit field counts to lwr
        and     eax,033333333h          ;eax = lwr 2 bit field counts
        and     edi,033333333h          ;edx = upr 2 bit field counts
        add     edi,eax                 ;edi = 4 bit field counts
        mov     eax,edi
        shr     eax,04h                 ;mov upr 4 bit field counts to lwr
        add     eax,edi                 ;eax = 8 bit field counts
        and     eax,00f0f0f0fh          ; after the and
        imul    eax,eax,01010101h       ;eax bit 24->28 = bit count
        shr     eax,018h                ;eax bit 0->4 = bit count

Answer 2

#include <stdio.h>

unsigned int fun ( unsigned int edi )
{
    unsigned int edx;
    unsigned int eax;

    //mov    edx,edi
    edx=edi;
    //shr    edx,1
    edx>>=1;
    //and    edx,0x55555555
    edx&=0x55555555;
    //sub    edi,edx
    edi-=eax;
    //mov    eax,edi
    eax=edi;
    //shr    edi,0x2
    edi>>=2;
    //and    eax,0x33333333
    eax&=0x33333333;
    //and    edi,0x33333333
    edi&=0x33333333;
    //add    edi,eax
    edi+=eax;
    //mov    eax,edi
    eax=edi;
    //shr    eax,0x4
    eax>>=4;
    //add    eax,edi
    eax=edi;
    //and    eax,0xf0f0f0f
    eax&=0x0F0F0F0F;
    //imul   eax,eax,0x1010101
    eax=eax*0x01010101;
    //shr    eax,0x18
    eax>>=0x18; //24
    //ret
    return(eax);
}


int main ( void )
{
    unsigned int ra;
    unsigned int rb;
    for(ra=0;ra<100;ra++)
    {
        rb=fun(ra);
        printf("0x%08X 0x%08X\n",ra,rb);
    }
    printf("0x%08X\n",fun(0xFFFFFFFF));
    printf("0x%08X\n",fun(0x55555555));
    printf("0x%08X\n",fun(0xAAAAAAAA));
    printf("0x%08X\n",fun(0x33333333));
    return(0);
}

as mentioned in the other answer this is some tricky pattern perhaps or algorithm, not yet obvious to me, also looks just random-ish as the author just wants to see if you understand the various operations and doesnt have some trick up their sleeve...

Hopefully the above clears the air on what is going on.

Note how nicely the assembly syntax translates visually to a real or pseudocode with the destination on the left, there is no flip flop required to read the asm nor the C. Intel, arm, and other syntaxes make it very easy to write and read. Dont have to twist your brain around. Eventually if you learn enough assembly languages though, you can go both ways. Its like big endian vs little endian.

Answer 3

This appears to be Intel ass-backward syntax, which means (a) all instructions take the destination as their first operand, and (b) a bare numeric literal is an immediate operand, not a memory address.

Therefore:

what value gets put into edx on the first line?

Whatever was in edi when control reaches the first line, will be copied into edx. If this is the body of a function, then it's at least plausible that edi holds its single integer argument; that would be consistent with one of the common calling conventions for x86-64; however, I note that there is nothing else in here to indicate that this is 64-bit code, and in 32-bit mode it would be on the stack instead.

what are the hexadecimal values and what do they do

They are just numbers. Several of them are repeating binary patterns, e.g. 0x55555555 is 0b01010101010101010101010101010101 and 0x33333333 is 0b00110011001100110011001100110011 — so, for instance, and edx, 0x55555555 clears all of the even-numbered bits of register edx.

It appears that the code overall is doing some kind of clever arithmetic cleverness, but I cannot tell what mathematical function it computes just by looking at it.

Does [mov eax,edi] remove the value from edi or does it just make a copy of it

It just makes a copy.