Какова цель инструкций LEA в этой функции и что делает общая рекурсия?

Question

Я пытался выяснить, что делает следующая рекурсивная функция:

func4:
0x08048cfa <+0>:    push   edi
0x08048cfb <+1>:    push   esi
0x08048cfc <+2>:    push   ebx
0x08048cfd <+3>:    mov    ebx,DWORD PTR [esp+0x10] // First arg
0x08048d01 <+7>:    mov    edi,DWORD PTR [esp+0x14] // Second arg
0x08048d05 <+11>:   test   ebx,ebx // if (ebx == 0) { eax = 0; return ???;}
0x08048d07 <+13>:   jle    0x8048d34 <func4+58>
0x08048d09 <+15>:   mov    eax,edi
0x08048d0b <+17>:   cmp    ebx,0x1 // if (ebx == 1) {return ???;} 
0x08048d0e <+20>:   je     0x8048d39 <func4+63>
0x08048d10 <+22>:   sub    esp,0x8
0x08048d13 <+25>:   push   edi
0x08048d14 <+26>:   lea    eax,[ebx-0x1]// eax = ebx-1
0x08048d17 <+29>:   push   eax
0x08048d18 <+30>:   call   0x8048cfa <func4>
0x08048d1d <+35>:   add    esp,0x8 // esp += 8
0x08048d20 <+38>:   lea    esi,[edi+eax*1] // esi = edi + eax
0x08048d23 <+41>:   push   edi
0x08048d24 <+42>:   sub    ebx,0x2 // ebx -= 2
0x08048d27 <+45>:   push   ebx
0x08048d28 <+46>:   call   0x8048cfa <func4>
0x08048d2d <+51>:   add    esp,0x10 // esp += 10
0x08048d30 <+54>:   add    eax,esi // eax += esi
0x08048d32 <+56>:   jmp    0x8048d39 <func4+63>
0x08048d34 <+58>:   mov    eax,0x0 // eax = 0
0x08048d39 <+63>:   pop    ebx
0x08048d3a <+64>:   pop    esi
0x08048d3b <+65>:   pop    edi
0x08048d3c <+66>:   ret

На сегодняшний день я выяснил, что он принимает ebx, уменьшает его на единицу, передает обратно самому себеи повторяется до тех пор, пока не достигнет одного из базовых вариантов, затем переходит к следующему шагу рекурсии.Однако я не до конца понял, что делает эта ветвь рекурсии или что esp делает в этом контексте.

Есть ли какие-либо подсказки относительно того, как действовать?Я уже несколько раз проходил через GDB, но на самом деле не заметил какого-либо паттерна, который помог бы мне определить, что происходит.

Answer 1

Похоже, вы не знаете, что результат возвращается в регистр eax.Имея это в виду, код не сложен для понимания.Предполагая, что используется соглашение о вызовах cdecl (поскольку стек очищается вызывающей стороной), оно аналогично функции js:

function func4(a, b)
{
    if (a <= 0) return 0;
    if (a == 1) return b;
    return b + func4(a-1, b) + func4(a-2, b);
}

и является кодом asm с комментариями

func4:
0x08048cfa <+0>:    push   edi              ; save non-volatile registers
0x08048cfb <+1>:    push   esi
0x08048cfc <+2>:    push   ebx
0x08048cfd <+3>:    mov    ebx, [esp+0x10]  ; ebx <- a
0x08048d01 <+7>:    mov    edi, [esp+0x14]  ; edi <- b
0x08048d05 <+11>:   test   ebx, ebx         ; if (a <= 0)
0x08048d07 <+13>:   jle    0x8048d34        ;   return 0
0x08048d09 <+15>:   mov    eax, edi         ; result <- 0
0x08048d0b <+17>:   cmp    ebx, 0x1         ; if (a == 1)
0x08048d0e <+20>:   je     0x8048d39        ;   return result;
0x08048d10 <+22>:   sub    esp, 0x8         ; this is useless
0x08048d13 <+25>:   push   edi              ; passing 2nd arguments
0x08048d14 <+26>:   lea    eax, [ebx-0x1]   ; 
0x08048d17 <+29>:   push   eax              ; passing 1st arguments
0x08048d18 <+30>:   call   0x8048cfa<func4> ; ax = func4(a - 1, b)
0x08048d1d <+35>:   add    esp, 0x8         ; clean up the stak after calling
0x08048d20 <+38>:   lea    esi, [edi+eax*1] ; temp = b + func4(a - 1, b)
0x08048d23 <+41>:   push   edi              ; passing 2nd arguments
0x08048d24 <+42>:   sub    ebx, 0x2         ;
0x08048d27 <+45>:   push   ebx              ; passing 1st arguments
0x08048d28 <+46>:   call   0x8048cfa<func4> ; ax = func4(a - 2, b)
0x08048d2d <+51>:   add    esp, 0x10        ; clean up the stak and the useless 8 bytes
0x08048d30 <+54>:   add    eax, esi         ; result = func4(a - 2, b) + temp
0x08048d32 <+56>:   jmp    0x8048d39        ; 
0x08048d34 <+58>:   mov    eax, 0x0         ; jump to here when a <= 0
0x08048d39 <+63>:   pop    ebx
0x08048d3a <+64>:   pop    esi
0x08048d3b <+65>:   pop    edi
0x08048d3c <+66>:   ret

LEA предназначен для расчета смещений памяти, но он широко используется для умножения и сложения слияния, потому что это быстро и удобно.Еще два преимущества: 1) вы можете присвоить результат регистру, отличному от исходных регистров;2) это не влияет на флаги.