8

Computer Systems: A Programmer's Perspectiveを読んでいて、宿題はこのアルゴリズムがどのように機能するかを説明することでした。

C 関数:

void store_prod(__int128 *dest, int64_t x, int64_t y) {
    *dest = x * (__int128)y;
}

組み立て：

movq %rdx, %rax
cqto
movq  %rsi, %rcx
sarq  $63,  %rcx
imulq %rax, %rcx
imulq %rsi, %rdx
addq  %rdx, %rcx
mulq  %rsi
addq  %rcx, %rdx
movq  %rax, (%rdi)
movq  %rdx, 8(%rdi)
ret

なぜそれが実行されるのかわかりません：xh * yl + yh * xl = value which we add after unsigned multiplication

4

3 に答える 3

2

GCC が行っているのは、次の式を使用して符号付き乗算ができるという性質を利用していることです。

(hi,lo) = unsigned(x*y)
hi -= ((x<0) ? y : 0)  + ((y<0) ? x : 0)

この場合、x86-64 命令セットには符号付き 64 ビット * 64 ビットから 128 ビットへの命令 (imulオペランドが 1 つ) があるため、これを行う必要はないという事実にもかかわらず、この式は他の場合に役立ちます。たとえば、SSE2/AVX2/AVX512 で符号​​付き 128 ビット乗算を実装する場合や、命令セットが 128 ビット乗算のみを行う場合(x86-64 など) に 256 ビット乗算を実装する場合などです。

ただし、GCC はこの式を少し異なる方法で実装しました。符号ビットを取得して単語全体に拡張する場合、この関数を呼び出すと、関数はまたはsign_extを返します。次に、GCCが行ったことは次のとおりです。-10

hi += sign_ext(x)*y + sign_ext(y)*x

たとえばsign_ext(x)*y、64ビットワードの疑似命令では

sarq  $63, x    ; sign_ext(x)
imulq   y, x    ; sign_ext(x)*y

だから今、あなたは尋ねます（または尋ねるつもりです）：

なぜこの式は正しいのでしょうか?

それは良い質問です。私もこれと同じ質問をし、njuffa が書いた

@Zboson: 2 の補数表現から直接続きます。たとえば、32 ビット整数-nであり-m、符号なし数値として表されますx=2**32-n, y=2**32-m。あなたが持っているそれらを乗算する場合x*y = 2**64 - 2**32*n - 2**32*m + n*m。中間項は、製品の上半分に必要な修正を示します。-1*-1 を使用した簡単な例を見てみると、非常に有益であることがわかります。

于 2015-11-25T09:40:55.053 に答える
2

なぜこの操作を行うのかを理解するために、int128_t を次のように解釈してみてください: 2^64 * xh + xl

したがって、2 つの int128_t 整数を乗算する場合は、次のようにします。

x = 2^64 * xh + xl

y = 2^64 * yh + イル

x * y = (2^128 * xh * yh) + (2^64 * xh * yl) + (2^64 * yh * xl) + (yl * xl)

そして、これはまさに、アセンブリ コードが行うことです。

yh = %rdx yl = %rax

xh = %rcx xl = %rsi

2^64 * xh * yl: is imulq %rax, %rcx2^64 は、これを上位ビットに追加する必要があることを示します

2^64 * yh * xl: is imulq %rsi, %rdx2^64 は、これを上位ビットに追加する必要があることを示します

2^128 * xh * yh: 2^128 * xh * yh128 ビット整数に収まらないため、この操作は必要ありません。これは符号ビット情報のみを表し、無視することができます。

xl * yl: はmulq %rsi

これで問題が解決することを願っています！

于 2015-11-21T10:11:13.970 に答える