Wie funktioniert diese 128-Bit-Integer-Multiplikation in Assembly (x86-64)?

Question

Ich lese Computer Systems: A Programmer's Perspective und die Hausaufgaben sollten beschreiben, wie dieser Algorithmus funktioniert.

C Funktion:

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

Montage:

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 

Ich weiß nicht, warum es führt: xh * yl + yh * xl = value which we add after unsigned multiplication

Answer 1

Was GCC tut, ist die Verwendung der Eigenschaft, die Multiplikation signiert mit the following formula durchgeführt werden kann.

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

Trotz der Tatsache, dass es keine Notwendigkeit, dies der Satz x86-64 Anweisung da in diesem Fall zu tun ist, hat einen gezeichneter 64-Bit · 64-Bit-128-Bit-Befehl (imul mit einem Operanden) Diesem Formel ist in anderen Fällen nützlich. Zum Beispiel zum Implementieren signed 128-bit multiplication with SSE2/AVX2/AVX512 oder zum Implementieren 256-bit multiplication when the instruction set only does 128-bit multiplication (wie mit x86-64).

GCC implementiert diese Formel ein wenig anders. Nehmen wir das Vorzeichenbit und erweitern es auf das ganze Wort, rufen Sie diese Funktion sign_ext auf, dann gibt die Funktion -1 oder 0 zurück. Dann was GCC tat ist:

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

zum Beispiel sign_ext(x)*y in pseudo-Anweisungen für 64-Bit-Wörter ist

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

So, jetzt fragen Sie (oder fragen gemeint):

Warum ist diese Formel wahr?

Das ist eine gute Frage. Ich fragte die gleiche Frage auch und njuffa wrote

@Zboson: Es folgt direkt aus Zweierkomplement Komplement-Darstellung. Z.B. 32-Bit-Ganzzahlen -n und -m werden als vorzeichenlose Zahlen x=2**32-n, y=2**32-m dargestellt. Wenn Sie diese multiplizieren, haben Sie x*y = 2**64 - 2**32*n - 2**32*m + n*m. Die mittleren Terme geben die notwendigen Korrekturen für die obere Hälfte des Produkts an. Das Arbeiten mit einem einfachen Beispiel mit -1 * -1 sollte sehr lehrreich sein.

Answer 2

Wie immer Compiler-Optionen Rolle. Dieser Quellcode mit gcc -Og (für das Debuggen optimieren) produces very similar asm to your listing (das Cast-Zeichen-erweitert beide Operanden auf 128 Bit vor einer vollen 128x128-> 128 multiplizieren). Dies ist genau das, was der C-Standard sagt (integer promotion). Wenn Sie über die Compilerausgabe sprechen, sollten Sie immer sagen, welche Version von welchem ​​Compiler mit welchen Optionen. Oder schreiben Sie einfach einen Link auf godbolt, wie oben.

(Edit:. Oops, Quelle und asm aus einem Buch waren, die nicht, dass Informationen gegeben hat)

Mit gcc -O3 nimmt gcc sich die Tatsache zunutze, dass beide Operanden noch wirklich nur 64-Bit sind, so a single imul is enough.

---

Die sar $63, %rcx gehört-sign verlauf rsi in rcx:rsi, wie cqtorax in rdx:rax Anmelde erstreckt.

---

dieser Antwort Die meisten wurde bereits von anderen Menschen in den Kommentaren gegeben, aber ich glaube nicht, dass jemand anderes, dass die Ausgabe fast genau das asm bemerkt gcc -Og/-O1 gibt.

Answer 3

Um zu verstehen, warum wir diese Operationen tun, versuchen zu interpretieren int128_t als: 2^64 * xh + xl

so, wenn wir zwei int128_t ganze Zahlen multiplizieren wollen, werden wir die folgenden:

x = 2^64 * xh + xl

y = 2^64 * yh + yl

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

Und das ist genau das, was die Assembler-Code tut:

yh =% RDX yl =% rax

xh =% rcx xl =% rsi

2^64 * xh * yl: ist imulq %rax, %rcx 2^64 zeigt an, dass wir dies auf die hohe Ordnung

2^64 * yh * XL Bits hinzufügen müssen: imulq %rsi, %rdx ist 2^64 zeigt an, dass wir diese Bits zu den höherwertigen

hinzufügen müssen 2^128 * xh * yh: Diese Operation wird nicht benötigt, sin ce 2^128 * xh * yh passt nicht in 128-Bit-Integer.Es stellt nur Zeichen-Bit-Informationen dar und kann ignoriert werden.

xl * yl: ist mulq %rsi

Ich hoffe, dass diese Dinge aufklärt!