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

Question

Я читаю Компьютерные системы: Перспектива программиста, и домашнее задание состояло в том, чтобы описать, как работает этот алгоритм.

С функция:

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 использует свойство умножения со знаком, используя следующую формулу.

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

Несмотря на то, что в этом нет необходимости, поскольку в этом случае набор команд x86-64 имеет 64-битную *64-битную или 128-битную инструкцию со знаком (imul с одним операндом) эта формула полезна в других случаях. Например, для реализации 128-разрядного умножения со знаком с SSE2/AVX2/AVX512 или для 256-разрядного умножения, когда набор команд выполняет только 128-разрядное умножение (например, с 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

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

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

Это хорошее питание. Я тоже задал этот же вопрос и нюффа написал

@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 (оптимизировать для отладки) производит очень похожую asm к вашему листингу (знак приведения расширяет оба операнда до 128 бит до полного умножения 128x128->128). Это именно то, что говорит стандарт C, должно произойти (целочисленное продвижение). Если вы собираетесь поговорить о выводе компилятора, вы должны всегда указывать, какая версия какого компилятора с какими параметрами. Или просто разместите ссылку на него на Godbolt, как показано выше.

(Изменить: упс, источник и asm были из книги, которая не дала этой информации.)

С gcc -O3 GCC использует тот факт, что оба операнда все еще на самом деле только 64-битные, поэтому один imul достаточно

---

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

---

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

Answer 3

Чтобы понять, почему мы делаем эти операции, попробуйте интерпретировать int128_t как: 2^64 * xh + xl

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

х = 2 ^ 64 * хх + хл

у = 2 ^ 64 * гг + гг

поэтому 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: есть imulq %rax, %rcx 2 ^ 64 указывает, что нам нужно добавить это к старшим битам

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

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

xl * yl: есть mulq %rsi

Я надеюсь, что это проясняет ситуацию!