Как это 128-битное целочисленное умножение работает в сборке (x86-64)?

Question

Я читаю 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

Answer 1

Что GCC делает, это свойство, которое может быть выполнено с помощью умножения, используя the following formula.

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

Несмотря на то, что нет необходимости делать это, так как в этом случае набор команд x86-64 имеет знаковое 64-разрядное * 64-бит 128-битной инструкции (imul с одним операндом) это формула полезна в других случаях. Например, для реализации signed 128-bit multiplication with SSE2/AVX2/AVX512 или для реализации 256-bit multiplication when the instruction set only does 128-bit multiplication (например, с x86-64).

GCC реализовал эту формулу несколько иначе. Если мы возьмем знаковый бит и распространим его на все слово, вызовите эту функцию sign_ext, тогда функция вернет -1 или 0. Тогда что GCC сделал это:

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 

Итак, теперь вы спрашиваете (или хотел спросить):

Почему эта формула истинна?

Это хорошее qeustion. Я тоже задал этот вопрос, и njuffa wrote

@Zboson: Он следует непосредственно из представления дополнений дополнений двух. Например. 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 должна оказаться очень поучительной.

Answer 2

Как всегда, опции компилятора значения. Этот исходный код с gcc -Og (оптимизирован для отладки) produces very similar asm to your listing (литой знак - расширяет оба операнда до 128 бит, прежде чем делать полный 128x128-> 128 умножить). Это именно то, что должно сказать стандарт C (целое продвижение). Если вы собираетесь поговорить о выходе компилятора, вы всегда должны указать, какую версию компилятора использовать с какими параметрами. Или просто разместите ссылку на нее по адресу godbolt, как и выше.

(Edit:. Упс, источник и ASM были из книги, которые не давали эту информацию)

С gcc -O3, GCC использует тот факт, что оба операнда являются до сих пор на самом деле только 64-разрядные, so a single imul is enough.

---

sar $63, %rcx является частью знака удлинителей rsi в rcx:rsi, так же, как cqto вход проходит rax в rdx:rax.

---

Большая часть этого ответа было дано уже другими людьми в комментариях, но я не думаю, что кто-то заметил, что gcc -Og/-O1 дает почти точно, что выход ассемблера.

Answer 3

Для того, чтобы понять, почему мы делаем это операции, пытаются интерпретировать int128_t как: 2^64 * хк + х

поэтому если мы хотим, чтобы умножить два int128_t целых чисел, мы сделаем следующее:

х = 2^64 * хк + х

у = 2^64 * YH + ил

так х * у = (2^128 * XH * YH) + (2^64 * XH * yl) + (2^64 * yh * xl) + (yl * xl)

И это именно то, что код сборки делает:

YH =% RDX ил =% Ракс

хк =% RCX х =% рши

2^64 * хк * ил: это imulq %rax, %rcx 2^64 указывает на то, что нам нужно, чтобы добавить это высокого порядка битов

2^64 * YH * х: есть imulq %rsi, %rdx 2^64 указывает на то, что нам нужно, чтобы добавить это биты высокого порядка

2^128 * xh * yh: эта операция не нужна, грех ce 2^128 * xh * yh не будет вписываться в 128-битное целое число.Он представляет только информацию о битах знака и может быть проигнорирован.

х * ил: это mulq %rsi

Я надеюсь, что это очищает вещи!