Reverse Engineering a recursive function
<p>I have as a homework to reverse a function</p>

<p>The assembler output is this: </p>

<pre><code>0x00000000004010c4 &lt;+0&gt;:    sub    $0x18,%rsp
0x00000000004010c8 &lt;+4&gt;:    lea    0xc(%rsp),%rcx
0x00000000004010cd &lt;+9&gt;:    lea    0x8(%rsp),%rdx
0x00000000004010d2 &lt;+14&gt;:   mov    $0x402995,%esi
0x00000000004010d7 &lt;+19&gt;:   mov    $0x0,%eax
0x00000000004010dc &lt;+24&gt;:   callq  0x400cb0 &lt;__isoc99_sscanf@plt&gt;
0x00000000004010e1 &lt;+29&gt;:   cmp    $0x2,%eax
0x00000000004010e4 &lt;+32&gt;:   jne    0x4010ed &lt;phase_4+41&gt;
0x00000000004010e6 &lt;+34&gt;:   cmpl   $0xe,0x8(%rsp)
0x00000000004010eb &lt;+39&gt;:   jbe    0x4010f2 &lt;phase_4+46&gt;
0x00000000004010ed &lt;+41&gt;:   callq  0x401671 &lt;explode_bomb&gt;
0x00000000004010f2 &lt;+46&gt;:   mov    $0xe,%edx
0x00000000004010f7 &lt;+51&gt;:   mov    $0x0,%esi
0x00000000004010fc &lt;+56&gt;:   mov    0x8(%rsp),%edi
0x0000000000401100 &lt;+60&gt;:   callq  0x401086 &lt;func4&gt;
0x0000000000401105 &lt;+65&gt;:   cmp    $0x3,%eax
0x0000000000401108 &lt;+68&gt;:   jne    0x401111 &lt;phase_4+77&gt;
0x000000000040110a &lt;+70&gt;:   cmpl   $0x3,0xc(%rsp)
0x000000000040110f &lt;+75&gt;:   je     0x401116 &lt;phase_4+82&gt;
0x0000000000401111 &lt;+77&gt;:   callq  0x401671 &lt;explode_bomb&gt;
0x0000000000401116 &lt;+82&gt;:   add    $0x18,%rsp
0x000000000040111a &lt;+86&gt;:   retq   
</code></pre>

<p>My solution to this function looks like this:
I think func4 should return 3</p>

<pre><code>int phase4(const char* read ) {
int var1, var2;
if ((sscanf(read, "%d %d", &amp;var1, &amp;var2) != 2) || (var1 &lt; 0xe))
    explode_bomb();

if (func4(var1, 0, 0xe /*14*/) != 3)
    explode_bomb();

if (var2 != 3)
    explode_bomb();
return 3;
}
</code></pre>

<p>func4 looks like this:</p>

<pre><code>0x0000000000401086 &lt;+0&gt;:    sub    $0x8,%rsp
0x000000000040108a &lt;+4&gt;:    mov    %edx,%eax
0x000000000040108c &lt;+6&gt;:    sub    %esi,%eax
0x000000000040108e &lt;+8&gt;:    mov    %eax,%ecx
0x0000000000401090 &lt;+10&gt;:   shr    $0x1f,%ecx
0x0000000000401093 &lt;+13&gt;:   add    %ecx,%eax
0x0000000000401095 &lt;+15&gt;:   sar    %eax
0x0000000000401097 &lt;+17&gt;:   lea    (%rax,%rsi,1),%ecx
0x000000000040109a &lt;+20&gt;:   cmp    %edi,%ecx
0x000000000040109c &lt;+22&gt;:   jle    0x4010aa &lt;func4+36&gt;
0x000000000040109e &lt;+24&gt;:   lea    -0x1(%rcx),%edx
0x00000000004010a1 &lt;+27&gt;:   callq  0x401086 &lt;func4&gt;
0x00000000004010a6 &lt;+32&gt;:   add    %eax,%eax
0x00000000004010a8 &lt;+34&gt;:   jmp    0x4010bf &lt;func4+57&gt;
0x00000000004010aa &lt;+36&gt;:   mov    $0x0,%eax
0x00000000004010af &lt;+41&gt;:   cmp    %edi,%ecx
0x00000000004010b1 &lt;+43&gt;:   jge    0x4010bf &lt;func4+57&gt;
0x00000000004010b3 &lt;+45&gt;:   lea    0x1(%rcx),%esi
0x00000000004010b6 &lt;+48&gt;:   callq  0x401086 &lt;func4&gt;
0x00000000004010bb &lt;+53&gt;:   lea    0x1(%rax,%rax,1),%eax
0x00000000004010bf &lt;+57&gt;:   add    $0x8,%rsp
0x00000000004010c3 &lt;+61&gt;:   retq   
</code></pre>

<p>My c code looks like this:</p>

<pre><code>int func4(unsigned rsi, unsigned rdi, unsigned rdx) {
unsigned rax = rdx;
rax -= rsi;
unsigned rcx = rax;
rcx &gt;&gt;= (unsigned)0x1f;
rax += rcx;
rax &gt;&gt;= (signed)1;
rcx = rax + rsi;
if (rcx &lt;= rdi) {
    rax = 0;
    if (rcx &gt;= rdi)
        return rax;
    else {
        rax = func4(rdi, rsi + 1, rdx);
        rax = rax + rax + 1;
    }
} else {
    rdx = rcx - 1;
    rax = func4(rdi, rsi, rdx);
    rax = rax + rax;
}
return rax;
}
</code></pre>

<p>But when I try the values from -512 to 512 I never get 3 as a result; what am I doing wrong?</p>

<p>EDIT:</p>

<p>I found the solution it looks like this:</p>

<pre><code>int func4(int32_t di, int32_t si, int32_t dx) {
int32_t ax = dx;
ax = ax - si;
int32_t cx = ax;
cx = (uint32_t)cx &gt;&gt; (uint32_t)0x1f;
ax = ax + cx;
ax = (int32_t)ax &gt;&gt; (int32_t)1;
cx = ax + si;

if (cx &lt;= di)
    goto first;

dx = cx - 1;
ax = func4(di, si, dx);
ax = ax + ax;
goto fin;

first:
   ax = 0;
   if (cx &gt;= di)
       goto fin;

si = cx + 1;
ax = func4(di, si, dx);
ax = ax + ax + 1;

fin:
    return ax;
}
</code></pre>