Подписанная и неподписанная арифметическая реализация на x86

Ответ 1

Если вы посмотрите на различные команды умножения x86, глядя только на 32-битные варианты и игнорируя BMI2, вы найдете их:

• imul r/m32 (умноженное на 32x32- > 64)
• imul r32, r/m32 (32x32- > 32 умножить) *
• imul r32, r/m32, imm (32x32- > 32 умножить) *
• mul r/m32 (32x32- > 64 беззнакового умножения)

Обратите внимание, что только "расширяющееся" умножение имеет неподписанный аналог. Две формы в середине, отмеченные звездочкой, являются как подписанными, так и беззнаковыми умножениями, потому что для случая, когда вы не получаете эту дополнительную "верхнюю часть", это то же самое.

"Расширяющиеся" умножения не имеют прямого эквивалента в C, но компиляторы могут (и часто делают) использовать эти формы в любом случае.

Например, если вы скомпилируете это:

uint32_t test(uint32_t a, uint32_t b)
{
    return a * b;
}

int32_t test(int32_t a, int32_t b)
{
    return a * b;
}

С GCC или некоторым другим относительно разумным компилятором вы получите что-то вроде этого:

test(unsigned int, unsigned int):
    mov eax, edi
    imul    eax, esi
    ret
test(int, int):
    mov eax, edi
    imul    eax, esi
    ret

(фактический вывод GCC с -O1)

Таким образом, подпись не имеет значения для умножения (по крайней мере, не для типа умножения, которое вы используете в C) и для некоторых других операций, а именно:

• сложение и вычитание
• побитовое И, ИЛИ, XOR, NOT
• Отрицание
• сдвиг влево
• сравнение для равенства

x86 не предлагает отдельные подписанные/неподписанные версии для них, поскольку в этом нет никакой разницы.

Но для некоторых операций существует разница, например:

• деление (idiv vs div)
• остаток (также idiv vs div)
• правый сдвиг (sar vs shr) (но остерегайтесь подписанного сдвига справа в C)
• для сравнения больше/меньше, чем

Но последний является особенным, x86 не имеет отдельных версий для подписанных и неподписанных, либо он имеет одну операцию (cmp, которая на самом деле просто неразрушающая sub), которая делает это одновременно, и дает несколько результатов (затронуты несколько бит в "флажках" ). Более поздние инструкции, которые фактически используют эти флаги (ветки, условные перемещения, setcc), затем выбирают, какие флаги им нужны. Так, например,

cmp a, b
jg somewhere

Пойдет somewhere, если a "подписано больше" b.

cmp a, b
jb somewhere

Пошел бы somewhere, если a "без знака ниже" b.

См. Assembly - JG/JNLE/JL/JNGE после CMP для получения дополнительных сведений о флажках и ветвях.

Это не будет формальным доказательством того, что подписанное и беззнаковое умножение одно и то же, я просто попытаюсь дать вам представление о том, почему они должны быть одинаковыми.

Рассмотрим 4-битные целые числа. Вес их отдельных битов составляет от lsb до msb, 1, 2, 4 и -8. Когда вы умножаете два из этих чисел, вы можете разложить один из них на 4 части, соответствующие его битам, например:

0011 (decompose this one to keep it interesting)
0010
---- *
0010 (from the bit with weight 1)
0100 (from the bit with weight 2, so shifted left 1)
---- +
0110

2 * 3 = 6, поэтому все проверяется. Это просто регулярное многократное умножение, которое большинство людей учит в школе, только двоичное, что делает его намного проще, поскольку вам не нужно умножаться на десятичную цифру, вам нужно только умножить на 0 или 1 и сдвинуть.

В любом случае, теперь возьмите отрицательное число. Вес знакового бита равен -8, поэтому в какой-то момент вы сделаете частичный продукт -8 * something. Умножение на 8 сдвигается налево на 3, поэтому прежний lsb теперь является msb, а все остальные бит равны 0. Теперь, если вы отрицаете это (это было -8 в конце концов, а не 8), ничего не происходит. Очевидно, что Zero неизменен, но так же, как и 8, и вообще число с только набором msb:

-1000 = ~1000 + 1 = 0111 + 1 = 1000

Итак, вы сделали то же самое, что и сделали бы, если бы вес msb был 8 (как в случае без знака) вместо -8.

Ответ 2

Большинство современных процессоров поддерживают арифметику со знаком и без знака. Для тех арифметических, которые не поддерживаются, нам нужно эмулировать арифметику.

Цитата из этого ответа для архитектуры X86

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

Что я подразумеваю под "родной поддержкой"? В основном я имею в виду, что есть набор инструкций для неподписанных номеров и другой набор, который вы используете для подписанных номеров. Беззнаковые числа могут сидеть в одном и том же регистрируется как подписанный номер, и действительно, вы можете смешивать подписанные и неподписанные инструкции, не беспокоясь о процессоре. Это до компилятор (или программист сборки), чтобы отслеживать, является ли число подписанный или нет, и используйте соответствующие инструкции.

Во-первых, два номера дополнений обладают свойством, что добавление и вычитание является таким же, как для чисел без знака. Он не делает разница в том, являются ли цифры положительными или отрицательными. (Так вы просто продолжайте и ДОБАВЛЯЙТЕ и ПОДНИМИТЕ ваши номера без беспокойства.)

Различия начинают показывать, когда дело доходит до сравнений. x86 имеет простой способ их дифференцирования: выше/ниже указывает на неподписанное сравнение и больше/меньше, чем указывает сопоставленное сравнение. (Например. JAE означает "Перейти, если выше или равно" и без знака.)

Существует также два набора инструкций умножения и деления обрабатывать подписанные и беззнаковые целые числа.

Наконец: если вы хотите проверить, скажем, переполнение, вы сделали бы это иначе для подписанных и для чисел без знака.

Ответ 3

Небольшое дополнение для cmp и sub. Мы знаем, что cmp считается неразрушающим sub, поэтому давайте сосредоточимся на sub.

Когда x86 cpu выполняет команду sub, например,

sub eax, ebx

Как cpu знает, подписаны ли значения eax или ebx или unsigned? Например, рассмотрим 4-битное число ширины в двух дополнениях:

eax: 0b0001
ebx: 0b1111

В любом подписанном или без знака значение eax будет интерпретироваться как 1(dec), что отлично.

Однако, если ebx без знака, он будет интерпретироваться как 15(dec), результат будет:

ebx:15(dec) - eax: 1(dec) = 14(dec) = 0b1110 (two complement)

Если ebx подписан, то результаты будут:

ebx: -1(dec) - eax: 1(dec) = -2(dec) = 0b1110 (two complement)

Несмотря на то, что для подписанных или без знака кодировка их результатов в двух дополнениях одинакова: 0b1110.

Но один положительный: 14 (dec), другой отрицательный: -2 (dec), а затем возвращается наш вопрос: как процессор сообщает, к какому?

Ответ: CPU будет оценивать оба: от http://x86.renejeschke.de/html/file_module_x86_id_308.html

Он оценивает результат как для целочисленных операндов с подписью, так и без знака и устанавливает флагов OF и CF для указания переполнения в подписанном или неподписанном результате соответственно. Флаг SF указывает знак подписанного результата.

В этом конкретном примере, когда cpu видит результат: 0b1110, он установит флаг SF в 1, потому что он -2(dec), если 0b1110 интерпретируется как отрицательное число.

Тогда это зависит от следующих инструкций, если им нужно использовать флаг SF или просто игнорировать его.