-5

変数を送信するときに、 Cプリプロセッサの include ステートメントで次の算術関数を実行したいと考えていますx。

#define calc_addr_data_reg (x) ( base_offset + ((x/7) * 0x20) + data_reg_offset)

ビットシフトを使用して除算と乗算演算を実装するにはどうすればよいですか? 除算演算では、商だけが必要です。

4

1 に答える 1

4

質問に答えるには、

「この式はCプリプロセッサで正しいですか？」

何も悪いことはありません。

ビットシフトを使用して除算と乗算の演算を実装するにはどうすればよいですか？除算演算では、商だけが必要です。

コンパイラーは、ほとんどすべての場合よりも、コードを最適化するためのより良い仕事をします。StackOverflowにこれを行う方法を尋ねる必要がある場合は、GCCよりも優れたパフォーマンスを発揮するのに十分な知識がありません。私は確かにそうしないことを知っています。しかし、ここでgccがそれを最適化する方法を尋ねたので。

@ EdHeal、

これには、適切に応答するためにもう少し余裕が必要でした。あなたが与えた例（ゲッターとセッター）では絶対に正しいですが、この特定の例でinlineは、関数を実行すると、数回呼び出されると仮定すると、バイナリの側がわずかに増加します。

GCCは関数を次のようにコンパイルします。

mov ecx, edx
mov edx, -1840700269
mov eax, edi
imul    edx
lea eax, [rdx+rdi]
sar eax, 2
sar edi, 31
sub eax, edi
sal eax, 5
add esi, eax
lea eax, [rsi+rcx]
ret

これは、関数を呼び出して戻り値を取得するためのアセンブリよりも多くのバイトです。これは、3つpushのステートメント、呼び出し、戻り値、およびポップステートメント（おそらく）です。

-Osを使用すると、次のようにコンパイルされます。

mov eax, edi
mov ecx, 7
mov edi, edx
cdq
idiv    ecx
sal eax, 5
add eax, esi
add eax, edi
ret

これは、コールリターンプッシュおよびポップよりも少ないバイトです。

したがって、この場合、インライン化するときにコードが小さいか大きいかどうかに関係なく、彼がどのコンパイラフラグを使用するかが非常に重要になります。

もう一度操作するには：

そこにあるコードの意味を説明する：

この投稿の次の部分は、http：//porn.quiteajolt.com/2008/04/30/the-voodoo-of-gcc-part-i/から直接リッピングされています。

この怪物に対する適切な反応は「何を待つか」です。私がより多くの説明を使用できると思ういくつかの特定の指示：

movl $-1840700269, -4(%ebp)

-1840700269 = -015555555555（8進数）（先行ゼロで示されます）。見た目がかっこいいので、8進数表現を使用します。

imull %ecx

これにより、％ecxと％eaxが乗算されます。これらのレジスタには両方とも32ビットの数値が含まれているため、この乗算によって64ビットの数値が生成される可能性があります。これは1つの32ビットレジスタに収まらないため、結果は2つに分割されます。製品の上位32ビットは％edxに入れられ、下位32ビットは％eaxに入れられます。

leal (%edx,%ecx), %eax

これにより、％edxと％ecxが追加され、結果が％eaxに入れられます。leaの表向きの目的はアドレス計算であり、これをaddとmovの2つの命令として記述する方が明確ですが、実行には2クロックサイクルかかりますが、これには1つしかかかりません。

また、この命令は前の命令（％edxに格納されている）の乗算の上位32ビットを使用し、％eaxの下位32ビットを上書きするため、乗算の上位ビットのみが使用されることに注意してください。

sarl $2, %edx   # %edx = %edx >> 2

技術的には、sar（算術右シフト）が>>演算子と同等であるかどうかは、実装によって定義されます。gccは、演算子が符号付き数値の算術シフトであることを保証します（「符号付き `>>'は符号拡張によって負の数に作用します」）。すでにgccを使用したことがあるので、残りの部分で使用していると仮定します。この投稿の（私がいるので）。

sarl $31, %eax

％eaxは32ビットレジスタであるため、[-231、231-1]の範囲の整数で動作します。これは興味深いものを生み出します。この計算では、2つの可能な結果しか得られません。数値が0以上の場合、シフトは何があっても数値を0に減らします。数値が0未満の場合、結果は-1になります。

これらのステップのいくつかは正確に32ビット幅の整数に依存しているため、これはこのアセンブリをCに直接書き直したものですが、念のために整数幅のパラノイアがあります。

int32_t divideBySeven(int32_t num) {
    int32_t eax, ecx, edx, temp; // push %ebp / movl %esp, %ebp / subl $4, %esp
    ecx = num; // movl 8(%ebp), %ecx
    temp = -015555555555; // movl $-1840700269, -4(%ebp)
    eax = temp; // movl -4(%ebp), %eax

    // imull %ecx - int64_t casts to avoid overflow
    edx = ((int64_t)ecx * eax) >> 32; // high 32 bits
    eax = (int64_t)ecx * eax; // low 32 bits

    eax = edx + ecx; // leal (%edx,%ecx), %eax
    edx = eax; // movl %eax, %edx
    edx = edx >> 2; // sarl $2, %edx

    eax = ecx; // movl %ecx, %eax
    eax = eax >> 31; // sarl $31, %eax

    ecx = edx; // movl %edx, %ecx
    ecx = ecx - eax; // subl %eax, %ecx
    eax = ecx; // movl %ecx, %eax
    return eax; // leave / ret
}

ここには明らかに非効率的なものがたくさんあります。不要なローカル変数、不要な変数スワッピング、eax =（int64_t）ecx * eax1; まったく必要ありません（完成のために含めただけです）。それでは、それを少しクリーンアップしましょう。この次のリストでは、各ブロックの上に対応するアセンブリがあり、ほとんどのがらくたが削除されています。

int32_t divideBySeven(int32_t num) {
    // pushl %ebp
    // movl %esp, %ebp
    // subl $4, %esp
    // movl 8(%ebp), %ecx
    // movl $-1840700269, -4(%ebp)
    // movl -4(%ebp), %eax
    int32_t eax, edx;
    eax = -015555555555;

    // imull %ecx
    edx = ((int64_t)num * eax) >> 32;

    // leal (%edx,%ecx), %eax
    // movl %eax, %edx
    // sarl $2, %edx
    edx = edx + num;
    edx = edx >> 2;

    // movl %ecx, %eax
    // sarl $31, %eax
    eax = num >> 31;

    // movl %edx, %ecx
    // subl %eax, %ecx
    // movl %ecx, %eax
    // leave
    // ret
    eax = edx - eax;
    return eax;
}

そして最終バージョン：

int32_t divideBySeven(int32_t num) {
    int32_t temp = ((int64_t)num * -015555555555) >> 32;
    temp = (temp + num) >> 2;
    return (temp - (num >> 31));
}

「なぜ彼らはそうするのか」という明白な質問にはまだ答えていません。そして、その答えはもちろんスピードです。最初のリストで使用されている整数除算命令idivは、実行になんと43クロックサイクルかかります。しかし、gccが生成する除算なしの方法には、かなり多くの命令があるので、全体的に本当に高速ですか？これがベンチマークがある理由です。

int main(int argc, char *argv[]) {
    int i = INT_MIN;
    do {
        divideBySeven(i);
        i++;
    } while (i != INT_MIN);

    return 0;
}

可能なすべての整数をループしますか？もちろん！両方の実装でテストを5回実行し、時間のタイミングを合わせました。gccのユーザーCPU時間は45.9、45.89、45.9、45.99、および46.11秒でしたが、idiv命令を使用したアセンブリの時間は62.34、62.32、62.44、62.3、および62.29秒でした。つまり、ナイーブな実装は約36％実行されました。平均して遅い。うん。

コンパイラの最適化は素晴らしいことです。

さて、私は戻ってきました、なぜこれが機能するのですか？

int32_t divideBySeven(int32_t num) {
    int32_t temp = ((int64_t)num * -015555555555) >> 32;
    temp = (temp + num) >> 2;
    return (temp - (num >> 31));
}

最初の部分を見てみましょう：

int32_t temp = ((int64_t)num * -015555555555) >> 32;

なぜこの数？

さて、2 ^ 64を7で割って、何が飛び出すか見てみましょう。

2^64 / 7 = 2635249153387078802.28571428571428571429

それは混乱のように見えますが、8進数に変換するとどうなりますか？

0222222222222222222222.22222222222222222222222

それは非常にきれいな繰り返しパターンです、確かにそれは偶然ではありえません。つまり、7は0b111であり、99で割ると、10進数で繰り返しパターンが得られる傾向があることを覚えています。したがって、7で割ると、8進数で繰り返しパターンが得られることは理にかなっています。

では、私たちの番号はどこから来るのでしょうか？

(int32_t)-1840700269と同じです(uint_32t)2454267027

* 7 = 17179869189

そして最後に17179869184は2^34

これは、17179869189が7 2^34の最も近い倍数であることを意味します。言い換えれば、2454267027は、 7を掛けたときに2の累乗に非常に近いに収まる最大の数です。uint32_t

この数字は8進数で何ですか？

0222222222223

何でこれが大切ですか？さて、7で割りたいのですが、この数はおよそ2 ^34/7...です。したがって、これを掛けてから34回左シフトすると、正確な数に非常に近い数が得られるはずです。

最後の2行は、近似誤差を修正するために設計されたように見えます。

おそらく、この分野でもう少し知識や専門知識を持っている人がこれに気付くことができます。

>>> magic = 2454267027
>>> def div7(a):
...   if (int(magic * a >> 34) != a // 7):
...     return 0
...   return 1
... 
>>> for a in xrange(2**31, 2**32):
...   if (not div7(a)):
...     print "%s fails" % a
...

失敗は3435973841で始まります。これは、おかしなことに0b11001100110011001100110011010001です。

于 2013-03-07T01:25:45.757 に答える