アセンブリ分割エラーのCollat​​z関数

Question

Cとx86-64アセンブリ言語の間にハイブリッドプログラムを作成しようとしています。このプログラムは、Collat​​z関数を使用して、1と指定されたパラメータnの間の最大停止時間を計算する必要があります。 main関数はC言語で書かれており、for-loopではアセンブリで記述された外部関数を呼び出します。

コンパイルされたハイブリッドプログラムを2より大きい値で実行すると、セグメンテーションフォルトが発生します。gdb再帰呼び出しを行うとエラーが発生しました。

Cコード：これは私が取得していますエラーです

#include <stdio.h> 
#include <stdlib.h> 

int noOfOp = 0; 

extern int collatz(long long n); 

// The main function. Main expects one parameter n. 
// Then, it computes collatz(1), colllatz(2), ..., collataz(n) and finds the 
// a number m, 1 <= m <= n with the maximum stopping time. 
int main(int argc, char *argv[]){ 
    if (argc != 2) { 
     printf("Parameter \"n\" is missing. \n"); 
     return -1; 
    } else { 
     int max=0; 
     long long maxn=0; 
     int tmp=0; 
     long long n = atoll(argv[1]); 
     for (long long i=1 ; i<=n ; i++) { 
      tmp = collatz(i); 
      if (tmp > max) { 
       max = tmp; 
       maxn=i; 
      } 
     } 
     printf("The largest stopping time between 1 and %lld was %lld ", n,maxn); 
     printf("with the stopping time of %d. \n", max); 
    } 
} 

そして、これは私が書いたx86-64のアセンブリコードです。私はこのコードがアセンブリの適切な理解の欠如を反映していると期待しています。これは、この新しいトピックを完成させるために4日間与えられたクラスの課題です。通常、私はより多くのドキュメントを読んでいたでしょうが、私は単純なのは時間が足りません。アセンブリ言語は難しいです。

.section .text 
.global collatz 

collatz: 
    pushq %rbp   # save old base pointer 
    movq %rsp, %rbp  # create new base pointer 
    subq $16, %rsp  # local variable space 


    cmpq $1, %rdi  # compare n to 1 
    je  is_one   # if n = 1, return noOfOp 

    incq noOfOp   # else n > 1, then increment noOfOp 
    movq %rdi, %rdx  # move n to register rdx 
    cqto     # sign extend rdx:rax 
    movq $2, %rbx  # move 2 to register rbx 
    idivq %rbx   # n/2 -- quotient is in rax, remainder in rdx 
    cmpq $1, %rdx  # compare remainder to 1 
    je  is_odd   # if n is odd, jump to is_odd 
    jl  is_even   # else n is even, jump to is_even 
    leave     # remake stack 
    ret      # return 


is_odd: 
    movq %rdi, %rdx  # move n to register rdx 
    cqto     # sign extend rdx:rax 
    movq $3, %rbx  # move 3 to register rbx 
    imulq %rbx   # n * 3 -- result is in rax:rdx 
    movq %rax, %rdi  # move n to register rdi 
    incq %rdi   # n = n + 1 
    call collatz   # recursive call: collatz(3n+1) <---- this is where the segmentation fault seems to happen 
    leave     # remake stack 
    ret      # return 

is_even: 
    movq %rax, %rdi  # n = n/2 (quotient from n/2 is still in rax) 
    call collatz   # recursive call: collatz(n/2) <---- I seem to have gotten the same error here by commenting out most of the stuff in is_odd 
    leave     # remake stack 
    ret      # return 

is_one: 
    movq noOfOp, %rax # set return value to the value of noOfOp variable 
    leave     # remake stack 
    ret      # return 

私が得ることができるすべての助けと提案に感謝します。 Iコードを検査からわずか参照

Answer 1

2つの問題：

1. noOfOpがx86-64での32ビット・タイプになりint、として宣言されます。しかし、アセンブリコードは、それが64ビット型であるかのように扱われます。具体的には、incqを使用して1をインクリメントします。代わりにincl noOfOpまたはaddl $1, noOfOpにする必要があります。

   collatz関数はintを返すようにプロトタイプ化されていますが、コードではraxに64ビット値を返すように提案しています。呼び出し側は下位32ビットのみを使用するため、問題は発生しませんが、問題が発生する可能性があります。

2. collatz関数を再帰的に呼び出すときは、呼び出し規約を無視しています。あなたがLinux上にいると仮定すると、該当するものはthe System V AMD64 calling conventionになります。ここで、RBPとRBXレジスタは、callee-saveです。したがって、その内容を保存する必要があります。呼び出し規約に慣れ、ルールに従うようにしてください。

   コメント欄の1人が​​示唆するように、関数をアセンブリに変換する前に、CまたはC++で関数を書くのが最も簡単です。これにより、デバッグも容易になり、コンパイラがどのコードを発行するかを見ることもできます。コンパイラの出力を自分の手書きのアセンブリコードと照合することができます。

コードに問題がある可能性があります。デバッガを使用してコードをシングルステップ実行することで、それらを見つけることができます。既にGDBを使用しているので、これは簡単に行うべきです。

Answer 2

ありがとうございました。私の質問がスタックオーバーフローのガイドラインに従わなかった場合、私はお詫び申し上げます。
私は、通常、私はもっと時間があれば、これで他の人には気にしないと言っていました。代わりに、私は適切な道筋で私を導く可能性のあるデバッグサービスではなく、ガイダンスを求めました。

興味のある方は、私はプログラムを手に入れました。私は最初に投稿したものとは異なるアプローチで行き、スピードアップのためにいくつかの変更を加えました。以下は新しいアセンブリコードです。

.section .text 
.global collatz 

collatz: 
    pushq %rbp   # save old base pointer 
    movq %rsp, %rbp  # create new base pointer 
    subq $16, %rsp  # local variable space 

    cmpq $1, %rdi  # compare n to 1 
    je  is_one   # if n = 1, jump to is_one 
          # else n > 1 
    incl noOfOp   # increment noOfOp 
    movq %rdi, %rax  # move n to rax 
    andq $1, %rax  # AND 1 with n 
    jz  is_even   # if n is even jump to is_even 
          # else n is odd 
    movq $3, %rdx  # move 3 to rdx 
    imul %rdx, %rdi  # n = 3 * n 
    incq %rdi   # n = 3n + 1 
    call collatz   # recursive call: collatz(3n+1) 
    leave     # remake stack 
    ret      # return 

is_even: 
    sarq %rdi   # arithmetic right shift by 1 - divide n by 2 
    call collatz   # recursive call: collatz(n/2) 
    leave     # remake stack 
    ret      # return 

is_one: 
    movl noOfOp, %eax # set return value to noOfOp 
    movl $0, noOfOp  # reset noOfOp 
    leave     # remake stack 
    ret      # return 

これは動作します。私がC言語で書いたコードよりも30％高速です。しかし、私は割り当てから、もっと時間を削ってより効果的にすることができることを知っています。誰にでもアイデアがあれば、どのようにコメントすればいいですか。

もう一度ありがとうございます。

Answer 3

上記のコメントでPeterが提案した後、私は彼と他の著名人が同じトピックの別のスレッドで議論したことを読んだ。これは、私がこれらのアイディアのいくつかを実装した後に終了したコードです。これはgcc -O3でコンパイルされたものより30％高速です。どのくらい速くプログラムがこれらの異なる "トリック"になるかを信じることはできません - 私は本当に効率についてたくさん学んでいました。助けてくれた人に感謝します。

.section .text 
.global collatz 

collatz: 
    pushq %rbp     # save old base pointer 
    movq %rsp, %rbp    # create new base pointer 
    subq $16, %rsp    # local variable space 
    movq $-1, %r10    # start counter at -1 

while_loop: 
    incq %r10     # increment counter 
    leaq (%rdi, %rdi, 2), %rdx # rdx = 2 * n + n 
    incq %rdx     # rdx = 3n+1 
    sarq %rdi     # rdi = n/2 
    cmovc %rdx, %rdi    # if CF, rdi = rdx 
            # (if CF was set during right shift (i.e. n is odd) set rdi to 3n+1) 
            # else keep rdi to n/2 
    jnz  while_loop    # if n =/= 1 do loop again: 
            # Z flag is only set if sarq shifts when n is 1 making result 0. 
            # else 
    movq %r10, %rax    # set return value to counter 
    leave       # remake stack 
    ret        # return