Continuing our series on “Fundamentals Exercises”, we have some more reverse engineering for you! Again, these exercises are designed more as learning experiences rather than simply puzzlers. We hope you find them interesting and educational! Feel free to post your responses here, but we won’t put them on the site until after we post the “official” responses, to avoid spoilers.

Examine the following code, registers, and stack values to determine the following:

1. What is the return value from DemoFunction2?

2. What is the purpose of DemoFunction2?

3. Bonus: Both the last exercise and this week’s exercise involved accessing data at ebp+8. Why ebp+8?

Hints:

1. You probably don’t want to manually walk through every instruction that executes in the loop. Instead, walk through a few iterations to determine the intent of the code.

2. The bracket notation [] in the assembly means to treat the value in brackets as a memory address, and access the value at that address.

3. 32-bit integer return values are stored in eax

0:000> uf 010024d0

asmdemo2!DemoFunction2:

010024d0 55 push ebp

010024d1 8bec mov ebp,esp

010024d3 8b5508 mov edx,dword ptr [ebp+8]

010024d6 33c0 xor eax,eax

010024d8 b920000000 mov ecx,20h

010024dd d1ea shr edx,1

010024df 7301 jnc asmdemo2!DemoFunction2+0x12 (010024e2)

010024e1 40 inc eax

010024e2 e2f9 loop asmdemo2!DemoFunction2+0xd (010024dd)

010024e4 5d pop ebp

010024e5 c3 ret

0:000> r

eax=80002418 ebx=7ffd7000 ecx=00682295 edx=00000000 esi=80002418 edi=00000002

eip=010024d0 esp=0006fe98 ebp=0006fea8 iopl=0 nv up ei pl zr na pe nc

cs=001b ss=0023 ds=0023 es=0023 fs=003b gs=0000 efl=00000246

asmdemo2!DemoFunction2:

010024d0 55 push ebp

0:000> dps esp

0006fe98 0100251c asmdemo2!main+0x20

0006fe9c 80002418

0006fea0 00000002

0006fea4 00000000

0006fea8 0006ff88

0006feac 01002969 asmdemo2!_mainCRTStartup+0x12c

0006feb0 00000002

0006feb4 00682270

0006feb8 006822b8

0006febc f395c17d

0006fec0 00000000

0006fec4 00000000

0006fec8 7ffd7000

0006fecc 00000000

0006fed0 00000000

0006fed4 00000000

0006fed8 00000094

0006fedc 00000006

0006fee0 00000000

0006fee4 00001771

0006fee8 00000002

0006feec 76726553

0006fef0 20656369

0006fef4 6b636150

0006fef8 00003120

0006fefc 00000000

0006ff00 00000000

0006ff04 00000000

0006ff08 00000000

0006ff0c 00000000

0006ff10 00000000

0006ff14 00000000

**[Update: our answer. Posted 12/04/2008]**

We had a great response to this exercise! It was good to see so many of you going through this. There were some readers that found this a good exercise for beginners, and others were looking for a return to Puzzlers. As an FYI, we may do more Puzzlers in the future, but for now we are going to continue on the “Fundamentals Exercise” track to help all our readers build up a solid foundation for debugging.

It was interesting to read how several of you not only gave the answers, but made suggestions for how the code could be optimized! I want to point out that the code we post for these exercises isn’t intended to be the optimal solution; it is written as a learning tool. That said, keep that in-depth feedback coming; I think everyone will benefit from a discussion of optimization.

Answers to exercise 2:

- DemoFunction2 returns 5, which is the number of bits set in 80002418, the value at ebp+8.
- DemoFunction2 finds the hamming weight of the 32-bit value passed to the function (it returns the count of bits that are equal to 1).
- ebp points to the base of the stack frame (the value stored there points to the previous frame's ebp), ebp+4 points to the return address, and ebp+8 points to the first parameter passed to the function. Note that the value of ebp changes in the function prolog, at instruction 010024d1. At this point ebp is set to 0006fe94, so at instruction 010024d3, ebp+8 is 0006fe9c, and [ebp+8] = 80002418.

It looks like the function counts the number of set bits in its argument. Since the argument here is 0x80002418, the return value is 5.

After the prologue, the first argument is at ebp+8 and the stack looks like this

0006fe94 0006fea8 <- ebp,esp (pushed ebp value)

0006fe98 0100251c [ebp+4] (return address)

0006fe9c 80002418 [ebp+8] (first argument)

This looks like naive implemenation of bit counting in 32-bit unsigned value. DemoFunction2(0x80002418) should return 5.

[ebp+8] is used to retrieve the input parameter, because [ebp+4] holds the return address, and [ebp] is used to keep the previous value of ebp.

PS: "Hacker's Delight" by Warren has great chapter on bit counting.

This routine counts the number of bits in the 32 bit integer input variable

int DemoFunction2(int val)

{

return NumberOfBitsTurnedOn(val);

}

int DemoFunction2(int val)

{

int ret = 0;

for (int =0;i<0x20;i++)

{

if (val%2 == 1)

ret++;

val/=2;

}

return ret;

}

ebp+8 is the first argument on the stack, since ebp is initialized from esp. The first 32 bits on the stack is the return address. The next 32 bits is the first argument (the only argument in this case).

1. The return value is 5 for the input 80002418h

2. The function calculates the number of bits set in the argument.

3. EBP is set to the top of stack after the old EBP is pushed. Thus [EBP+0] is old EBP, [EBP+4] is the return address and [EBP+8] is the first argument.

Return value is :0x1.

The purpose of DemoFunction2 is to count number of bits set in given DWORD.

--rc

return value is :0x5.

function calculates number of bits in DWORD which is passed as parameter.

Why ebp+8?

Because as soon as we enter function we push ebp on stack, that move parameter further way by 4 bytes.

--rc

as far as I understand, it counts the set bits in a 32 bit (20h) number.

The parameter passed is 80002418h, which contains 5 set bits, so the return will be 5.

[ebp+8]: as the ebp will contain the stack pointer (mov ebp, esp), this expression will point to one of the elements on the stack.

The top element of the stack is the return address, and the next is the parameter passed.

So ebp+8 will point to the parameter. Now why +8, why not +4? That beats me.

ok, I think I figured out:

esp points to the top of the stack (where the next element will be stored),

esp-4 points to the last element (the return address)

and esp-8 points to the next-to-last element, which is the parameter.

Return value is 5. The function is counts the 1-bits in the 32-bit value passed to the function, which was 0x80002418. EBP+8 accesses the first parameter passed to the function. EBP+4 is the return address to the calling function. EBP points to the EBP of the previous function.

This function can be documented as follows:

; Prototype of the function:

; unsigned int DemoFunction2(unsigned int Value)

asmdemo2!DemoFunction2:

; Create the stack frame

; not really needed here, as we could access relative to ESP, but for completeness... 😉

010024d0 55 push ebp

010024d1 8bec mov ebp,esp

; Get the first (and only) argument to the function ("Value")

010024d3 8b5508 mov edx,dword ptr [ebp+8]

; Clear the internal counter

010024d6 33c0 xor eax,eax

; Make sure to loop for exacty 32 bits

010024d8 b920000000 mov ecx,20h

CountLoop:

; logically shift the Value one bit to the right

; the rightmost bit will be put into the Carry

010024dd d1ea shr edx,1

; if carry is not set, skip the following command

010024df 7301 jnc asmdemo2!DemoFunction2+0x12 (010024e2)

; Increment the counter

; Due to the "jnc" before, this is only executed if the rightmost bit

; before shifting ("shr") was set

010024e1 40 inc eax

; decrement CX; as long as CX has not reached 0, continue the loop

010024e2 e2f9 loop asmdemo2!DemoFunction2+0xd (010024dd)

; "undo" the stack frame

010024e4 5d pop ebp

010024e5 c3 ret

So:

2. Obviously, this function counts the number of "1" bits in the lower 32 bit of the binary representation of its argument.

1. The return value will be 5, as 0x80002418 contains exactly five "1" bits (the hex digits 8, 2, 4, 1, and 8 contain exactly one "1" bit each)

3. EBP+8 is the argument.

When the function just entered (at 010024d0), the stack frame looks like:

++++++++++++++++++

+ return address + esp+0

+----------------+

+ argument + esp+4

++++++++++++++++++

Now, ebp is pushed onto the stack, so we get the following outline:

++++++++++++++++++

+ "old" EBP + esp+0

+----------------+

+ return address + esp+4

+----------------+

+ argument + esp+8

++++++++++++++++++

With the following mov (010024d1), ebp is the same as esp, thus, ebp+8 is the argument.

If you want to use assembler commands seldomly used ("LOOP"), you could also have used ENTER and LEAVE.

Anyway, as I love to generate C code out of assembler, here is some code which would produce the same result (but different instructions):

int DemoFunction2(unsigned int bitmask)

{

int i;

int count = 0;

__asm int 3;

for (i = 32; i > 0; i--) {

if ( (bitmask >> 1) != 0) {

++count;

}

}

return count;

}

Why is bitmask declared as "unsigned int" instead of "int"? Well, because in C, shifting a signed value to the right provokes undefined behaviour. With "unsigned int", I can be sure that it is a logical shift right, and not an arithmetic one or something completely different.

1. What is the return value from DemoFunction2?

5

2. What is the purpose of DemoFunction2?

Return the number of bits that are set, in a 32-bit value

3. Why ebp+8?

It's the first param to the function - ebp+4 is the return address

(1) The return value is 5

(2) The purpose is to count the number of set bits in its argument.

(3) The preamble sets EBP to point to the stack frame for the function and offset +8 is the first argument.

Ah -- counting the number of bits set to 1 in a 32 bit integer value.

You should have a or edx, edx check before the mov ecx, 0x20h and do a jz to 0x010024e4 (in case someone passed in 0 to begin with). Also, you can try using the BSF (bit scan forward instruction), but the performance is likely to the same.

Finally, a reminder to make this things fastcalls -- it's a pity that the 32-bit compiler can't default to ecx and edx for parameter passing.

Isn't legacy a wonderful thing?

Hi,

My answers are:

1. 5

2. It counts the number of set (1) bits in the 0x80002418 number

3. After the function epilog (pusb ebp | mov ebp, esp) ebp+8 is the way to access the first parameter

-George

1. 1

2. Count the bits

3. First argument for this function

Please, more puzzlers instead of exercises. 🙂

Looks like this one is calculating logarithm with base 2 of the number specified as a parameter. Not sure about the return value, I think it will be 12.

DemoFunction2 returns the number of bits set to 1 in its unique argument.

in that case it returns DemoFunction2(0x80002418)=5

ebp+8 is the location of the first parameter in the stack frame

Hi,

Complementing my answer this code remember me the RtlNumberOfSetBits function with returns the number of set bits in a BITMAP structure.

-George

The routine counts bits, specifically it counts the number of ones in a 32-bit word. EAX is first zeroed and ECX holds the loop counter, which is 20h (32d). SHR shifts right and carries the LSB into the carry bit. EAX is incremented for every instance of the carry bit being set, which it will be for every shifted LSB that is a 1 value. The loop is run until all the bits in the word are shifted (ECX=0).

The original argument is 0006ff88 which has 12 one bits. If I recall correctly, [ebp+8] is a calling convention used in C++ (not a C++ expert, just a sysadmin.)

1) arg is 80002418

see each number as nibble, with respective bits set:

8 => 1 bit

2 => 1 bit

4 => 1 bit

1 => 1 bit

8 => 1 bit

----------

5 is the result

2)It counts the number of bits set in the passed in argument.

3) ebp+8 is the address of first argument

stack frame is set up by

push ebp

mov ebp,esp

...

and restored by

pop ebp

ebp + 4 return address

ebp + 8 first arg

calling convention is (I think) cdecl since the stack is not cleared (ret vs ret 4)

1. DemoFunction2 returns an integer with value 5.

2. The purpose is to count the number of bits that have been set in a mask.

3. "push ebp" pushes the old ebp value onto the stack, and then ebp is updated with the new esp. So the stack has grown by 4 bytes. Hence ebp+4 becomes the address where execution returns to after the function returns, and ebp+8 is the argument supplied to DemoFunction2.

1) Return value is 5

2) It calculates number of 1s in a number (80002418 in this case)

3) ebp+8 is pointer to first argument to the function. ebp points to base current stack frame. ebp+4 is return value, and ebp+8 is first argument.

DemoFunction2 returns 5.

Its purpose is to count the number of bit set to one (80002418 => 5 ones).

It shifts the bits one by one in the carry and increments eax when the carry is set, repeating ecx times, that is 32.

The parameters passed are accessed from ebp+8 because this is a c++ call frame.

ebp+4 is the return address, ebp+8 the first parameter, ebp+c the second, and so on.

It was early morning when I read this exercise. Thanks you, that's the perfect thing to wake up the brain.

1. The return value of the function is 5.

2. The function counts the number of 1 bits in the parameter.

3. I think ebp+8 represents the first parameter. Just after the function has been called, [esp] represents return address and [esp+4] represents the first parameter. The function then pushes ebp (4 more bytes on the stack) and copies the new esp to epb.

So:

[ebp+8] = ([esp+4] before ebp has been pushed)

Man, I love these. Real-world debugging is not easy for begginers, but these exercises are possible. Thanks and I'm waiting for the official answer and the next exercise.

eax value when Demofunction2 returns should be 20h.

DemoFunction2 should perform 2^32

Ebp+8 because it's usually the first function parameter, in standard call notation.

DemoFunction2 computes the number of set bits on a given 32-bit number. Here DemoFunction2(0x80002418)=5.

To answer the question #3: ebp+8 references the first argument for the function if frame is set up properly (push ebp; mov ebp, esp).

I just want to thank you for posting these, because these are fun! Here are my answers:

Answers:

1. Return value => 5

2. DemoFunction2 counts the number of bits set in a 32 bit argument and returns that count.

3. [ebp+8] is the first argument passed to the function

/////////////////////////////////////////////////////////////////////////////

// Function: asmdemo2!DemoFunction2:

/////////////////////////////////////////////////////////////////////////////

//

// Save the Prior Frame Pointer to the stack

//

010024d0 55 push ebp

//

// Set the Frame pointer to the current Stack pointer

//

010024d1 8bec mov ebp,esp

//

// Right at this point, the stack looks like:

// EBP = ESP

//

// EPB - N -- Local variables, if any (here there aren't)

// EBP -- Old EBP

// EBP + 4 -- Return Address back to calling function

// EBP + 8 -- First function Arg

//

//

// Put Arg1 into EDX

//

010024d3 8b5508 mov edx,dword ptr [ebp+8]

//

// EAX = 0

//

010024d6 33c0 xor eax,eax

//

// ECX = 0x20 (32)

//

010024d8 b920000000 mov ecx,20h

//

// LOOP_START:

//

// shr => "Unsigned shift right"

// shift EDX right by one bit, the bit shifted out

// will end up in the Carry Flag (CF)

//

010024dd d1ea shr edx,1

//

// jnc => "Jump if not carry (CF = 0)"

// If CF is 0, jump to SKIP_COUNT:

//

010024df 7301 jnc asmdemo2!DemoFunction2+0x12 (010024e2)

//

// Otherwise, if we're here CF = 1, and we are going to

// increment a counter.

// EAX++

//

010024e1 40 inc eax

//

// SKIP_COUNT:

//

// - Decrement ECX (implied by this instruction)

// - If ECX != 0, then "loop" (goto LOOP_START:)

// - Else fall through

//

010024e2 e2f9 loop asmdemo2!DemoFunction2+0xd (010024dd)

//

// Replace the Old Frame Pointer

//

010024e4 5d pop ebp

//

// Return back to the calling function.

// Whatever is in EAX is effectively returned.

//

010024e5 c3 ret

/////////////////////////////////////////////////////////////////////////////

//

// Since we know what the function does, all we need to do is find the

// argument to it. We can just look at the stack...

//

/////////////////////////////////////////////////////////////////////////////

0006fe98 0100251c asmdemo2!main+0x20 <= ret address

0006fe9c 80002418 <= Arg1

0006fea0 00000002

0006fea4 00000000

0006fea8 0006ff88

0006feac 01002969 asmdemo2!_mainCRTStartup+0x12c

1. The return value from DemoFunction2 is 5.

2. DemoFunction2 count's the number of '1' bits in a given 32bit number. (0x80002418 or 10000000000000000010010000011000 in our case)

3. stack position ebp+8 holds the first parameter for the function in most calling conventions (exclude fastcall). we can count on ebp for that purpose as long as the code was not compiled with FPO optimization.

Thank you very much for those wonderful exercises.

Moshe Levi.

This routine is trying to find X, where 2 to the power of X is 0x80002418? Is this right?

I forget the mathematical term for X. 🙁

The source code might have used recursive calling, but I am not sure.

The reason the first parameter is at [ebp+8] is because after "push ebp", esp is pointing at 0006fe94 (esp used to point to 0006fe98?)

So,

[ebp+8] = [0006fe94+8] = [0006fe9c], which holds the value 80002418.

Am I right on this?

1 - 5.

2 - number of positive bits (including sign bit) in the function argument, which is dword.

3 - ebp+8 is used to skip two top stack values (saved previous epb value and function return address) to get function arguments.

1. The return value is 1

2. The function calculates number of set bits in dword that is sent as a parameter.

3. Not sure but:

ebp+0 - return address

ebp+4 - this

ebp+8 - the parameter

1) Returned value is 5

2) It is counting the number of 1 bit in the passed in 80002418h parameter value.

The return value will be 0x5.

This function is returning number of 1's in the given input's binary representation.

ebp+8 is the first parameter passed to this function.

What is the return value from DemoFunction2

It seems to be 5

What is the purpose of DemoFunction2? : No idea ?

Why ebp+8? : It contains the first parameter to function...

Anways, it was fun. Keep posting.

#1) 5

#2) PopCount (Binary Counter)

#3) Paramater #1 after stack frame is setup

Finally, Same code written in assembly

popcount FRAME dwValue

mov ecx,[dwValue]

mov eax,ecx

shr eax,1

and eax,055555555h

sub ecx,eax

mov eax,ecx

shr eax,2

and ecx,033333333h

and eax,033333333h

add ecx,eax

mov eax,ecx

shr eax,4

add eax,ecx

and eax,00F0F0F0Fh

mov ecx,eax

shr ecx,8

add eax,ecx

mov ecx,eax

shr ecx,16

add eax,ecx

and eax,00000003Fh

RET

ENDF

Anyaslys:

DemoFunction2 takes paramter one, a 32 bit paramater, and then continually shifts it 32 times (20h), each time it is shifted the carry flag is checked to see if the shifted bit was set, if it wasn't the final result isn't incremented, if it was, the final result is incremented,, surmising that if each bit causes an increment to the return value the function simply counts the bits of the first paramater passed to our function.

PopCount does the same thing but as if the value needed folded upon itself, take every other bit and add them, then take every two bits and add them, then take every four bits and add them together, all the way until you add 16 bits to 16 bits. The reason for the subtraction instead of addition on first call is the reduction of overflow without the need for anding.

OK ... here is my try.

I think the code snippet is for counting how many 0 bits in the given 32bit unsigned number. The pesudo-C++ code would be like:

UINT DemoFunctions(UINT x)

{

UINT nRet = 0;

for (int i = 0; i < 32; ++i)

{

if (x&1 == 0)

nRet ++;

x = x >> 1;

}

return nRet;

}

From the raw call stack the parameter is [0006fe9c] = 80002418, so the answer should be 27.

5

ret = count of non zero bits

1. CountBitsSetInDword(DWORD dwData = 80002418) = 5

3. ebp is the value of esp, ebp+4 is the return ip, ebp+8 is the first parameter of the function.

It appears that the function counts the number of bits that are set to 1 in the argument passed to the function.

In this example, the argument 80002418 is passed in and I expect the function would return a value of 5 because there are 5 bits set in the argumnet.

Oops - it is ebp+8 (not ebp+4).

The function counts the number of bits set in the ebp+8 location. ebp+8 contains a 00000002 which means EAX should have a 1 in it upon completion of the function.

I incorrectly looked at 80002418 as the routine argument (which is at ebp+4).

Mike R

1. The return value from DemoFunction2 is 5.

2. The function's purpose is to count up the number of bits in the function's first parameter.

3. The data at ebp+8 is always where a function's first parameter is as long as the function was compiled to have a stack frame set up.

That was pretty fun! 🙂

Alan

1. return 5.

2. return the number of 1 bit in arg.