38346


以下のアセンブリ言語で書かれた関数をC言語風に書き直したいです。

関数内で同じ関数を呼び出しているので再帰処理をしているところまでは分かるのですが、再帰を抜け出す条件と再帰内で何を計算しているのかが分かりません。

どなたか教えていただけないでしょうか。

[code]

    /* <+0> ~ <+9> 再帰の終了条件 */
    0x00000000004010ac <+0>:    test   %edi,%edi  
    0x00000000004010ae <+2>:    jle    0x4010db <func4+47> /* もしedi<=0なら再帰終了*/ 
    0x00000000004010b0 <+4>:    mov    %esi,%eax 
    0x00000000004010b2 <+6>:    cmp    $0x1,%edi 
    0x00000000004010b5 <+9>:    je     0x4010e5 <func4+57> /* もしedi=1なら再帰終了, 戻り値はARG2(%eax) */
    
    /* <+11> ~ <+14> で呼出先退避レジスタの値をスタックに退避 */
    0x00000000004010b7 <+11>:   push   %r12
    0x00000000004010b9 <+13>:   push   %rbp
    0x00000000004010ba <+14>:   push   %rbx /* <+11> ~ <+14>
    
    /* <+15> ~ <+17> 引数の値を破壊されないよう安全なレジスタへ退避する
    0x00000000004010bb <+15>:   mov    %esi,%ebp /* ARG2 */
    0x00000000004010bd <+17>:   mov    %edi,%ebx /* ARG1 */
    
    /* <+19> ~ <+22> func4(ARG1-1, ARG2)で再帰呼出
    0x00000000004010bf <+19>:   lea    -0x1(%rdi),%edi /* ARG1=%rdi(ARG1)-1 */
    0x00000000004010c2 <+22>:   callq  0x4010ac <func4> 
    
    /* <+27> %r12d=func4一回目の戻り値*1+ARG2+0 */
    0x00000000004010c7 <+27>:   lea    0x0(%rbp,%rax,1),%r12d
    
    /* <+32> ~ <+35> func4(ARG1-2, ARG2)で再帰呼出 */
    0x00000000004010cc <+32>:   lea    -0x2(%rbx),%edi /* ARG1=%rbx(ARG1)-2 */
    0x00000000004010cf <+35>:   mov    %ebp,%esi　/* ARG2 */
    0x00000000004010d1 <+37>:   callq  0x4010ac <func4>
    
    /* <+42> 戻り値=(func4一回目の戻り値*1+ARG2+0)+ARG2 */
    0x00000000004010d6 <+42>:   add    %r12d,%eax
    0x00000000004010d9 <+45>:   jmp    0x4010e1 <func4+53>
    
    /* <+47> ~ <+52> edi<=0の時に0をreturn
    0x00000000004010db <+47>:   mov    $0x0,%eax
    0x00000000004010e0 <+52>:   retq   
    
    /* <+53> ~ <+55> 退避した呼出先退避レジスタの値をスタックから回収 */
    0x00000000004010e1 <+53>:   pop    %rbx
    0x00000000004010e2 <+54>:   pop    %rbp
    0x00000000004010e3 <+55>:   pop    %r12
    0x00000000004010e5 <+57>:   repz retq
    
[/code]


CC BY-SA 3.0
2017-10-01T15:07:19.213
38341
2017-10-17T13:38:51.740
2017-10-17T13:38:51.740
25350
25350
question
assembly
アセンブリ言語で書かれた関数をC言語に書き直す


この質問だと翻訳依頼にしか見えませんが、もっと自分で調べた内容がかけませんか？

まずは `x86-64 ABI` について知ってください。リンク張ってもいいんですが SO
的には１トピックの中で質疑応答が完結する形が望ましいということなのであえて書き下します。いっぱい約束がありますが、今回の話をするには以下の内容だけわかれば十分でしょう。

１．64bit 以下整数・ポインタ・参照は、関数を呼ぶ側が次のレジスタに割付けます。  
引数１（[c](/questions/tagged/c "'c' のタグが付いた質問を表示") の関数呼び出しの左端の引数）から順に `rdi`,
`rsi`, `rdx`, `rcx`, `r8`, `r9`  
64bit 未満の型については上位ビットは不定値です（呼び出された側で無視する必要があります）  
２．引数の７個目以後はスタックに割り振ります  
３．64bit 以下整数・ポインタ・参照の戻り値は `rax` に返されます。  
64bit 未満の型については上位ビットは不定値です（呼び出した側で無視する必要があります）  
４．呼ばれた側の関数は `r12`, `r13`, `r14`, `r15`, `rbx`, `rbp` の値を保存しなければなりません。  
レジスタを使わないか、使うのであればスタックに保存し復帰する必要があります。

`esi` は `rsi` の下３２ビット  
`edi` は `rdi` の下３２ビット

ここまでわかれば順番に読んでいくだけです。最初の数行を訳してみます（ここが再帰の脱出条件になっているようですね）

[code]

    if (arg1<=0) return 0;        /* 0 2 47 48 */
    if (arg1==1) return arg2;     /* 4 6 9 57 */
    
[/code]

以下略（御自分で翻訳してみてください） `lea` が足し算であることが理解できれば簡単です。

`repz retq` については下記ページを参照  
<https://stackoverflow.com/questions/20526361/>  
<http://repzret.org/p/repzret/>  
要するに `retq` と同じ動作をするけれども AMD K8/K10 CPU では `repz retq` のほうがペナルティが少ない（ので高速動作する）
ということのようです。 Intel CPU や AMD でも Bulldozer 以後は `retq` でよいとの事。

* * *

課題であるならそろそろ期限切れと言うことで解説と翻訳を追加。

`<+22>` の再帰呼び出しの際に `edi` は `-1` され `esi` はそのまま。(`edi` は `rdi` の下位３２ビットですから ABI
を満たしています）ということは `<+22>` の再帰は `func4(arg1-1, arg2)` と訳すことができます。

レジスタ保存規則により `<+27>` に到達した時点で `rdi`, `rsi` は値が壊されています。そのため `<+15>-<+17>`
で「壊されないレジスタ」に値を保存してありますし、同様、レジスタ保存規則を満たすために `<+11>-<+14>`
で「壊されない＝壊してはいけない」レジスタの元の値をスタックに保存してあります。

`<+37>` の再帰呼び出しの際には  
\- `rdi` は `rbx-2` であり、ここで `rbx` は旧 `edi` つまり `arg1`  
\- `rsi` は `ebp` であり、ここで `ebp` は旧 `esi` つまり `arg2`  
ですから `func4(arg1-2, arg2)` と訳すことができます。

`<+27>` の `lea` は 旧 `esi` \+ `func4(arg1-1, arg2)` の返却値 * 1 + 0  
`<+42>` の `add` は 上記の値 + `func4(arg1-2, arg2)` の返却値  
保存したレジスタの値を復帰して `retq`

ということで最終翻訳結果は

[code]

    int func4(int arg1, int arg2) {
        if (arg1<=0) return 0;
        if (arg1==1) return arg2;
        return func4(arg1-1, arg2)+arg2+func4(arg1-2, arg2);
    }
    
[/code]

ということになりそうです。フィボナッチ数列に似て非なる式でしょうか？


CC BY-SA 3.0
2017-10-02T00:04:58.793
38346
2017-10-04T05:34:26.520
2017-10-04T05:34:26.520
8589
8589
38341
answer