Trying to reverse engineer a function

Question

I'm trying to understand assembly in x86 more. I have a mystery function here that I know returns an int and takes an int argument. So it looks like int mystery(int n){}. I can't figure out the function in C however. The assembly is:

mov  %edi, %eax
lea  0x0(,%rdi, 8), %edi
sub  %eax, %edi
add  $0x4, %edi
callq < mystery _util >
repz retq

< mystery _util >
mov  %edi, %eax
shr  %eax
and  $0x1, %edi
and  %edi, %eax
retq

I don't understand what the lea does here and what kind of function it could be.

Answer 1

The assembly code appeared to be computer generated, and something that was probably compiled by GCC since there is a repz retq after an unconditional branch (call). There is also an indication that because there isn't a tail call (jmp) instead of a call when going to mystery_util that the code was compiled with -O1 (higher optimization levels would likely inline the function which didn't happen here). The lack of frame pointers and extra load/stores indicated that it isn't compiled with -O0

Multiplying x by 7 is the same as multiplying x by 8 and subtracting x. That is what the following code is doing:

lea  0x0(,%rdi, 8), %edi
sub  %eax, %edi

LEA can compute addresses but it can be used for simple arithmetic as well. The syntax for a memory operand is displacement(base, index, scale). Scale can be 1, 2, 4, 8. The computation is displacement + base + index * scale. In your case lea 0x0(,%rdi, 8), %edi is effectively EDI = 0x0 + RDI * 8 or EDI = RDI * 8. The full calculation is n * 7 - 4;

The calculation for mystery_util appears to simply be

n &= (n>>1) & 1;

If I take all these factors together we have a function mystery that passes n * 7 - 4 to a function called mystery_util that returns n &= (n>>1) & 1.

Since mystery_util returns a single bit value (0 or 1) it is reasonable that bool is the return type.

I was curious if I could get a particular version of GCC with optimization level 1 (-O1) to reproduce this assembly code. I discovered that GCC 4.9.x will yield this exact assembly code for this given C program:

#include<stdbool.h>

bool mystery_util(unsigned int n)
{
    n &= (n>>1) & 1;
    return n;
}

bool mystery(unsigned int n)
{
    return mystery_util (7*n+4);
}

The assembly output is:

mystery_util:
        movl    %edi, %eax
        shrl    %eax
        andl    $1, %edi
        andl    %edi, %eax
        ret
mystery:
        movl    %edi, %eax
        leal    0(,%rdi,8), %edi
        subl    %eax, %edi
        addl    $4, %edi
        call    mystery_util
        rep ret

You can play with this code on godbolt.

---

Important Update - Version without bool

I apparently erred in interpreting the question. I assumed the person asking this question determined by themselves that the prototype for mystery was int mystery(int n). I thought I could change that. According to a related question asked on Stackoverflow a day later, it seems int mystery(int n) is given to you as the prototype as part of the assignment. This is important because it means that a modification has to be made.

The change that needs to be made is related to mystery_util. In the code to be reverse engineered are these lines:

mov  %edi, %eax
shr  %eax

EDI is the first parameter. SHR is logical shift right. Compilers would only generate this if EDI was an unsigned int (or equivalent). int is a signed type an would generate SAR (arithmetic shift right). This means that the parameter for mystery_util has to be unsigned int (and it follows that the return value is likely unsigned int. That means the code would look like this:

unsigned int mystery_util(unsigned int n)
{
    n &= (n>>1) & 1;
    return n;
}

int mystery(int n)
{
    return mystery_util (7*n+4);
}

mystery now has the prototype given by your professor (bool is removed) and we use unsigned int for the parameter and return type of mystery_util. In order to generate this code with GCC 4.9.x I found you need to use -O1 -fno-inline. This code can be found on godbolt. The assembly output is the same as the version using bool.

If you use unsigned int mystery_util(int n) you would discover that it doesn't quite output what we want:

mystery_util:
        movl    %edi, %eax
        sarl    %eax          ; <------- SAR (arithmetic shift right) is not SHR
        andl    $1, %edi
        andl    %edi, %eax
        ret

Answer 2

The LEA is just a left-shift by 3, and truncating the result to 32 bit (i.e. zero-extending EDI into RDI implicilty). x86-64 System V passes the first integer arg in RDI, so all of this is consistent with one int arg. LEA uses memory-operand syntax and machine encoding, but it's really just a shift-and-add instruction. Using it as part of a multiply by a constant is a common compiler optimization for x86.

The compiler that generated this function missed an optimization here; the first mov could have been avoided with

lea  0x0(,%rdi, 8), %eax     # n << 3 = n*8
sub  %edi, %eax              # eax = n*7
lea  4(%rax), %edi           # rdi = 4 + n*7

But instead, the compiler got stuck on generating n*7 in %edi, probably because it applied a peephole optimization for the constant multiply too late to redo register allocation.

---

mystery_util returns the bitwise AND of the low 2 bits of its arg, in the low bit, so a 0 or 1 integer value, which could also be a bool.

(shr with no count means a count of 1; remember that x86 has a special opcode for shifts with an implicit count of 1. 8086 only has counts of 1 or cl; immediate counts were added later as an extension and the implicit-form opcode is still shorter.)

Answer 3

The LEA performs an address computation, but instead of dereferencing the address, it stores the computed address into the destination register. In AT&T syntax, lea C(b,c,d), reg means reg = C + b + c*d where C is a constant, and b,c are registers and d is a scalar from {1,2,4,8}. Hence you can see why LEA is popular for simple math operations: it does quite a bit in a single instruction. (*includes correction from prl's comment below)

There are some strange features of this assembly code: the repz prefix is only strictly defined when applied to certain instructions, and retq is not one of them (though the general behavior of the processor is to ignore it). See Michael Petch's comment below with a link for more info. The use of lea (,rdi,8), edi followed by sub eax, edi to compute arg1 * 7 also seemed strange, but makes sense once prl noted the scalar d had to be a constant power of 2. In any case, here's how I read the snippet:

mov  %edi, %eax          ; eax = arg1
lea  0x0(,%rdi, 8), %edi ; edi = arg1 * 8
sub  %eax, %edi          ; edi = (arg1 * 8) - arg1 = arg1 * 7
add  $0x4, %edi          ; edi = (arg1 * 7) + 4
callq < mystery _util >  ; call mystery_util(arg1 * 7 + 4)
repz retq                ; repz prefix on return is de facto nop.


< mystery _util >
mov  %edi, %eax          ; eax = arg1
shr  %eax                ; eax = arg1 >> 1
and  $0x1, %edi          ; edi = 1 iff arg1 was odd, else 0
and  %edi, %eax          ; eax = 1 iff smallest 2 bits of arg1 were both 1.
retq

Note the +4 on the 4th line is entirely spurious. It cannot affect the outcome of mystery_util.

So, overall this ASM snippet computes the boolean (arg1 * 7) % 4 == 3.