Czytanie kodu assembler

Question

Witam, moim zadaniem jest odtworzenie funkcji z kodu assembler. Kod przedstawiam niżej 

  400584:       53                      push   rbx 
  400585:       48 89 fb                mov    rbx,rdi
  400588:       b8 01 00 00 00  mov     eax,0x1
  40058d:       48 85 ff                test   rdi,rdi
  400590:       7e 18                   jle    4005aa <compute+0x26>
  400592:       48 8d 7f ff             lea    rdi,[rdi-0x1]
  400596:       e8 e9 ff ff ff          call   400584 <compute>
  40059b:       48 89 df                mov    rdi,rbx
  40059e:       48 29 c7                sub    rdi,rax
  4005a1:       e8 de ff ff ff          call   400584 <compute>
  4005a6:       48 83 c0 01             add    rax,0x1
  4005aa:       5b                      pop    rbx
  4005ab:       c3                      ret    

Wiem, że rozwiazanie to:
 

return n <= 0 ? 1 : compute(n - compute(n - 1)) + 1;

Tylko nie wiem skąd mam wiedzieć, że wywołanie funkcji compute jest zagnieżdżone

Comments

Rozumiem, że ten kod to właśnie funkcja compute. To jest 400584. W funkcji masz 2 razy wywołanie CALL 400584 - czyli rekurencyjne.

---

Tak tak jednak nie wiem czemu argumentem funckji compute jest ponownie compute

Answer 1

Tak tak jednak nie wiem czemu argumentem funckji compute jest ponownie compute

to się tłumaczy bezpośrednio:

                                                                compute(n - compute(n - 1)) + 1;

400592:       48 8d 7f ff             lea    rdi,[rdi-0x1]                          n - 1
400596:       e8 e9 ff ff ff          call   400584 <compute>               compute(     )
40059b:       48 89 df                mov    rdi,rbx            
40059e:       48 29 c7                sub    rdi,rax                    n -
4005a1:       e8 de ff ff ff          call   400584 <compute>   compute(                  )
4005a6:       48 83 c0 01             add    rax,0x1                                        + 1;

Comments

Okej rozumiem twoją odpowiedź jednak nie potrafię tego przełożyć na drugi kod: 

 400584:       48 89 5c 24 f0          mov    QWORD PTR [rsp-0x10],rbx
  400589:       48 89 6c 24 f8         mov    QWORD PTR [rsp-0x8],rbp
  40058e:       48 83 ec 18            sub    rsp,0x18
  400592:       48 89 fb               mov    rbx,rdi
  400595:       48 83 ff 01            cmp    rdi,0x1
  400599:       7e 1d                  jle    4005b8 <compute+0x34>
  40059b:       48 8d 7f ff            lea    rdi,[rdi-0x1]
  40059f:       e8 e0 ff ff ff         call   400584 <compute>
  4005a4:       48 89 c5               mov    rbp,rax
  4005a7:       48 89 df               mov    rdi,rbx
  4005aa:       48 d1 ff               sar    rdi,1
  4005ad:       e8 d2 ff ff ff         call   400584 <compute>
  4005b2:       48 89 eb               mov    rbx,rbp
  4005b5:       48 29 c3               sub    rbx,rax
  4005b8:       48 89 d8               mov    rax,rbx
  4005bb:       48 8b 5c 24 08         mov    rbx,QWORD PTR [rsp+0x8]
  4005c0:       48 8b 6c 24 10         mov    rbp,QWORD PTR [rsp+0x10]
  4005c5:       48 83 c4 18            add    rsp,0x18
  4005c9:       c3                     ret    
  4005ca:       90                     nop
  4005cb:       90                     nop

Tutaj rozwiązanie to 

return n <= 1 ? n : compute(n - 1) - compute(n / 2);

W tym przypadku obie funkcje compute nie są zagnieżdżone 

---

"Zagnieżdżenie" to ładny graficzny sposób na zapisanie "wynik jednej funkcji staje się wejściem do drugiej". Trzeba do tego spojrzeć przez jakie rejestry przechodzą dane.

W pierwszym jest:

400596:       e8 e9 ff ff ff          call   400584 <compute>
40059b:       48 89 df                mov    rdi,rbx
40059e:       48 29 c7                sub    rdi,rax
4005a1:       e8 de ff ff ff          call   400584 <compute>

Wyjście pierwszego wywołania (rax) jest użyte w operacji `sub`, a wynik odejmowania (rdi) staje się argumentem drugiego wywołania.

W drugim:

 40059f:       e8 e0 ff ff ff         call   400584 <compute>
 4005a4:       48 89 c5               mov    rbp,rax
 4005a7:       48 89 df               mov    rdi,rbx
 4005aa:       48 d1 ff               sar    rdi,1
 4005ad:       e8 d2 ff ff ff         call   400584 <compute>

Wynik pierwszego wywołania (rax) jest odłożony na bok (do rejestru rbp), a wejściem do drugiego wywołania jest jedynie wartość rbx podzielona przez 2.

---

Wszystkie jest dla mnie jasne. Wielkie dzięki!