Почему imul используется для умножения чисел без знака?

Я скомпилировал следующую программу:

#include <stdint.h>

uint64_t usquare(uint32_t x) {
  return (uint64_t)x * (uint64_t)x;
}

Это разборки:

 0: 89 f8                   mov    eax,edi
 2: 48 0f af c0             imul   rax,rax
 6: c3                      ret

Но imul - это команда для умножения подписанных чисел. Почему он используется gcc тогда?

/edit: при использовании uint64_t сборка аналогична:

0:  48 0f af ff             imul   rdi,rdi
4:  48 89 f8                mov    rax,rdi
7:  c3                      ret

Ответ 1

ПРЕДУПРЕЖДЕНИЕ Этот ответ длинный!

... и он заполнен ненужными объяснениями - но я всегда хотел написать что-то более продолжительное относительно умножения.

Немного теории

При умножении двух чисел a и b длины n результат имеет длину 2 n ^† и, самое главное, k-я цифра зависит только от младших k цифр (дается доказательство в Приложении A).

x86 `imul` две формы

Инструкция умножения x86 imul представлена в двух формах: полной форме и частичной форме.

Первая форма имеет вид n × n → 2 n, что означает, что она дает результат в два раза больше размера операндов - мы знаем из теории, почему это имеет смысл. Например

imul ax         ;16x16->32, Result is dx:ax
imul rax        ;64x64->128, Result is rdx:rax

Вторая форма имеет вид n × n → n, это обязательно вырезает некоторую информацию.
В частности, эта форма принимает только младшие n бит результата.

imul ax, ax          ;16x16->16, Lower WORD of the result is ax
imul rax, rax        ;64x64->64, Lower QWORD of the result is rax

Только одна версия операнда имеет первую форму.

Две инструкции: `imul` vs `mul`

Независимо от используемой формы, процессор всегда вычисляет результат с размером в два раза больше операндов (т.е. как первая форма).
Чтобы иметь возможность сделать это, операнды сначала преобразуются из их размера n в размер 2 n (например, от 64 до 128 бит).
Дополнительную информацию см. В Приложении B.

Умножение выполняется, и полный или частичный результат сохраняется в месте назначения.

Разница между imul и mul заключается в том, как преобразуются операнды.
Поскольку размер расширен, этот тип преобразования называется extension.

Инструкция mul просто заполняет верхнюю часть нулями - она равна нулю.
Команда imul реплицирует бит высокого порядка (первый слева) - это называется расширением знака и имеет интересное свойство преобразования двух дополнений подписали количество n бит в число со знаком 2 n битов с одинаковыми знаками и модулем (т.е. он делает то же самое, читателю остается найти встречный пример для случая с нулевым расширением),

     How mul extends              How imul extends       
       and operand                  and operand

     +----+       +----+          +----+       +----+
     |0...|       |1...|          |0...|       |1...|
     +----+       +----+          +----+       +----+  

+----+----+  +----+----+     +----+----+  +----+----+
|0000|0...|  |0000|1...|     |0000|0...|  |1111|1...|
+----+----+  +----+----+     +----+----+  +----+----+

Тезис

Разница между imul и mul заметна только от (n + 1) -го бита вперед.
Для 32-разрядного операнда это означает, что только верхняя 32-битная часть полного результата в конечном итоге будет отличаться.

Это легко увидеть, поскольку младшие n бит одинаковы для обеих команд, и, как мы знаем из теории, первые n бит результата зависят только от первых n бит операндов.

Таким образом, тезис: результат частичной формы imul идентичен результату mul.

Затем почему imul выходит?
Поскольку он более гибкий - он имеет два или три операнда, а mul имеет очень древний интерфейс.
Поскольку он устанавливает флаги в соответствии с подписанным умножением - CF и OF устанавливаются, если частичный результат отбрасывает какую-либо значимую информацию (техническое условие: расширение знака частичного результата отличается от полного результата), например, в случае переполнения.
Именно поэтому две и три формы операндов не называются mul, что в противном случае было бы идеально подходящим именем.

Практика

Чтобы проверить все это на практике, мы можем запросить компилятор ^{[ Комментарий от BeeOnRope}

Кроме того, расширение знака, вероятно, также концептуально

Аналогично расширение знака может происходить "концептуально", но, вероятно, не в аппаратном обеспечении. У них не будет дополнительных проводов и транзисторов только для того, чтобы сделать знак или нулевое расширение, что добавило бы много большого количества в уже огромный множитель, но будет использовать некоторые другие трюки, чтобы выполнить умножение "как бы", которое произошло.

Комментарий от BeeOnRope

^† Двоичные числа длины n находятся в порядке величины 2 ⁿ поэтому умножение двух таких чисел имеет порядок 2 ⁿ · 2 ⁿ= 2 ^{n + n}= 2 ^{2 n}. Как и длина длины 2 n.

Ответ 2

#include <stdint.h>

uint64_t fun0 ( uint32_t x )
{
    return (uint64_t)x * (uint64_t)x;
}
uint64_t fun1 ( uint32_t x )
{
    return ((uint64_t)x) * ((uint64_t)x);
}
uint64_t fun2 ( uint64_t x )
{
    return (x * x);
}



0000000000000000 <fun0>:
   0:   89 f8                   mov    %edi,%eax
   2:   48 0f af c0             imul   %rax,%rax
   6:   c3                      retq   
   7:   66 0f 1f 84 00 00 00    nopw   0x0(%rax,%rax,1)
   e:   00 00 

0000000000000010 <fun1>:
  10:   89 f8                   mov    %edi,%eax
  12:   48 0f af c0             imul   %rax,%rax
  16:   c3                      retq   
  17:   66 0f 1f 84 00 00 00    nopw   0x0(%rax,%rax,1)
  1e:   00 00 

0000000000000020 <fun2>:
  20:   48 89 f8                mov    %rdi,%rax
  23:   48 0f af c7             imul   %rdi,%rax
  27:   c3                      retq

ИЗМЕНИТЬ

даже если вы укажете все 64-битные без знака, он генерирует тот же результат

0x00FF * 0x00FF = 0xFE01
0xFFFF * 0xFFFF = 0xFFFE0001
so
0xFF * 0xFF = 0x01

Расширение знака

не имеет значения для младших 64 бит, поэтому вы можете использовать imul для 8, 16, 32 и 64-битных операндов, подписанных или неподписанных.