Bomb lab phase_4

Dump of assembler code for function func4
    <+0>: mov %rbx,-0x18(%rsp)
    <+5>: mov %rbp, -0x10(%rsp)
    <+10>: mov %r12,-0x8(%rsp)
    <+15>: sub $0x18,%rsp
    <+19>: mov %edi,%ebx
    <+21>: mov %esi,%ebp
    <+23>: test %edi, %edi
    <+25>: jg 0x400fb2<func4+34>
    <+27>: mov $0x0,%ebp
    <+32>: jmp 0x400fd2<func4+66>
    <+34> cmp $0x1, %edi
    <+37>: je 0x400fd2<func4+66>
    <+39>: lea -0x1(%rbx),%edi
    <+42>: callq 0x400f90 <func4>
    <+47>: mov %eax,%r12d
    <+50>: lea -0x2(%rbx),%edi
    <+53>: mov %ebp,%esi
    <+55>: callq 0x400f90 <func4>
    <+60>: lea (%r12,%rax,1),%eax
    <+64>: add %eax,ebp
    <+66>: mov %ebp, %eax
    <+68>: mov (%rsp),%rbx
    <+72>: mov 0x8(%rsp), %rbp
    <+77>: mov 0x10(%rsp),%r12
    <+82>: add $0x18,%rsp
    <+86>: retq

This is the disassembled code of func4. And I'm not sure whether I understood this function correctly or not.

I didn't write the disassembled code of phase_4 here, but it needs "%d %d" input, and first integer should be in range 1<=x<4. So it should be 1,2,or 3. And register %edi has the value 7 at first. After the call of func4, code compare the value of 0x10(%rsp) and %eax So I should know the %eax value after the call of func4.

I thought, disassembled code of func4 means

put the stack
ebx = edi
ebp = esi
if edi is not zero
    if edi is one: then eax=ebp.
                   rearrange the stack
                   return.
    else: edi = -0x1(rbx)
          func4
          r12d = eax
          edi = -0x2(rbx)
          esi = ebp
          func4
          eax = rax+r12+ebp
          rearrange the stack and return.
else
    ebp=0
    eax=ebp
    return

But with my understanding, I can't solve it. For example, if the original address of %rsp was 0x7fffffffd5a8 then the address would be smaller until the value of edi becomes 0. I found that the value of 0x7fffffffd56f is 0 - and the first func4 call ends- but after that value of 0x7fffffffd56e is also 0 - so the second func4 call ends - and all of registers become 0, including eax.

So I thought the answer of second number is zero, but (1,0), (2,0), (3,0) always explodes bomb.

Cound you guess where I am wrong and help?

Solution 1:

edi and esi are the two arguments to func4. This is according to standard calling convention, but can also be deduced from the fact that these registers are used without initialization, so their value must come from outside. As such, the prototype is int func4(int a, int b).

Line +23 check to see if a > 0, and jumps away if it is. So we can easily trace what happens if the condition is false:

if (a <= 0) return 0;

Line +34 is checking if a == 1, and if so, the current value of ebp is returned, but that has been initialized from esi which is the second argument, b:

if (a == 1) return b;

Otherwise, lines +39..+55 recursively invoke func4. Line +60 adds the result of the two invocations together, and line +64 adds b. So we have:

return func4(a - 1, b) + func4(a - 2, b) + b;

From this you can calculate the returned value for any input.

Of course if you are allowed to use a debugger, you can just let the code run and see what the value of eax is going to be ;)