Какие целочисленные операции дополнения 2 можно использовать без обнуления старших битов на входах, если требуется только младшая часть результата?

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

Это особенно характерно для x86-64 (он же AMD64) по разным причинам 1, некоторые из которых присутствуют в других ISA.

Я буду использовать 64-битный x86 в качестве примера, но намерение состоит в том, чтобы спросить о / обсудить дополнения и двоичную арифметику без знака в целом, так как все современные процессоры используют это. (Обратите внимание, что C и C++ не гарантируют дополнения до двух 4, и что переполнение со знаком является неопределенным поведением.)

В качестве примера рассмотрим простую функцию, которая может компилироваться в LEA инструкция 2. (В x86-64 SysV (Linux) ABI 3 первые две функции находятся в rdi а также rsi, с возвратом в rax, int это 32-битный тип.)

; int intfunc(int a, int b) { return a + b*4 + 3; }
intfunc:
    lea  eax,  [edi + esi*4 + 3]  ; the obvious choice, but gcc can do better
    ret

gcc знает, что сложение, даже целых чисел со знаком минус, переносится только справа налево, поэтому старшие биты входных данных не могут влиять на то, что входит в eax, Таким образом, он сохраняет байт инструкции и использует lea eax, [rdi + rsi*4 + 3]

Какие другие операции обладают этим свойством младших битов результата, не зависящих от старших битов входов?

И почему это работает?

Сноски

1 Почему это часто встречается для x86-64: x86-64 имеет инструкции переменной длины, где дополнительный байт префикса изменяет размер операнда (с 32 до 64 или 16), поэтому сохранение байта часто возможно в инструкциях, которые в противном случае выполняется с той же скоростью. Он также имеет ложные зависимости (AMD/P4/Silvermont) при записи младших 8b или 16b регистра (или остановку при последующем чтении полного регистра (Intel pre-IvB)): по историческим причинам, запись только в суб 32b - регистрирует ноль остальную часть регистра 64b. Почти вся арифметика и логика могут использоваться на младших 8, 16 или 32-битных, а также на полных 64-битных регистрах общего назначения. Целочисленные векторные инструкции также довольно неортогональны, с некоторыми операциями, недоступными для некоторых размеров элементов.

Кроме того, в отличие от x86-32, ABI передает аргументы функции в регистрах, и старшие биты не должны быть нулевыми для узких типов.

2 LEA: Как и другие инструкции, размер операнда по умолчанию LEA составляет 32 бита, но размер адреса по умолчанию - 64 бита. Байт префикса размера операнда (0x66 или же REX.W) может сделать размер выходного операнда 16 или 64 бита. Байт префикса размера адреса (0x67) может уменьшить размер адреса до 32 бит (в 64-битном режиме) или 16 бит (в 32-битном режиме). Так что в 64-битном режиме lea eax, [edx+esi] занимает на один байт больше, чем lea eax, [rdx+rsi],

Можно сделать lea rax, [edx+esi], но адрес все еще вычисляется только с 32 битами (перенос не устанавливает бит 32 rax). Вы получаете идентичные результаты с lea eax, [rdx+rsi], что на два байта короче. Таким образом, префикс размера адреса никогда не используется с LEA, как предостерегают комментарии в выводе разборки от отличного дизассемблера Agner Fog'а objconv.

3 x86 ABI: вызывающая сторона не должна обнулять (или расширять знак) верхнюю часть 64-битных регистров, используемых для передачи или возврата меньших типов по значению. Вызывающий объект, который хотел использовать возвращаемое значение в качестве индекса массива, должен был бы расширить его (с помощью movzx rax, eax или специальная инструкция для eax cdqe, (не путать с cdq, который подписывает-расширяет eax в edx:eax например, чтобы настроить для idiv.))

Это означает, что функция возвращает unsigned int может вычислить его возвращаемое значение в 64-битном временном в rax и не требуют mov eax, eax обнулить верхние биты rax, Это конструктивное решение работает в большинстве случаев: часто вызывающему абоненту не нужны никакие дополнительные инструкции, чтобы игнорировать неопределенные биты в верхней половине rax,

4 С и С ++

C и C++ специально не требуют двоичных двоичных чисел со знаком, дополняющих друг друга (за исключением C++ std::atomic типы). Допускаются также дополнение и знак / величина, поэтому для полностью переносимого C эти приемы полезны только при unsigned типы. Очевидно, что для знаковых операций установленный знаковый бит в представлении знак / величина означает, что, например, другие биты вычитаются, а не добавляются. Я не проработал логику для своего дополнения

Тем не менее, бит-хаки, которые работают только с дополнением до двух, широко распространены, потому что на практике никто больше не заботится ни о чем другом. Многие вещи, которые работают с дополнением до двух, должны также работать с дополнением до одного, поскольку знаковый бит по-прежнему не меняет интерпретацию других битов: он просто имеет значение - (2 N -1) (вместо 2 N). Представление знака / величины не имеет этого свойства: значение места каждого бита является положительным или отрицательным в зависимости от знакового бита.

Также обратите внимание, что компиляторы C могут предполагать, что переполнение со знаком никогда не происходит, потому что это неопределенное поведение. Так, например, компиляторы могут и предполагают, (x+1) < x всегда ложно. Это делает обнаружение переполнения со знаком довольно неудобным в C. Обратите внимание, что разница между беззнаковым переносом (переносом) и переполнением со знаком.

Источник

1 ответ

Решение

Широкие операции, которые можно использовать с мусором в старших битах:

  • побитовая логика
  • сдвиг влево (включая *scale в [reg1 + reg2*scale + disp])
  • сложение / вычитание (и, таким образом, LEA Инструкции: префикс размера адреса никогда не нужен. Просто используйте нужный размер операнда для усечения при необходимости.)

  • Низкая половина умножения. например, 16b x 16b -> 16b можно сделать с 32b x 32b -> 32b. Вы можете избежать остановок LCP (и проблем с частичной регистрацией) от imul r16, r/m16, imm16 используя 32-битный imul r32, r/m32, imm32 а затем чтение только 16 младших результатов. (Будьте осторожны с более широкими ссылками на память при использовании m32 версия, правда.)

    Как указано в руководстве Intel Insn Ref, 2 и 3 формы операндов imul безопасны для использования на целых числах без знака. Знаковые биты входов не влияют на N битов результата в N x N -> N немного умножить.)

  • 2 х (т.е. сдвиг на x): Работает, по крайней мере, на x86, где число сдвигов маскируется, а не насыщается, вплоть до ширины операции, так что мусор ecx или даже старшие биты cl не влияет на количество смен. Также относится к сменам без флага BMI2 (shlx и т. д.), но не для векторных сдвигов (pslld xmm, xmm/m128 и т. д., которые насыщают счет). Интеллектуальные компиляторы оптимизируют маскировку числа сдвигов, обеспечивая безопасную идиому для поворотов в C (без неопределенного поведения).

Очевидно, что флаги типа carry/overflow / sign / zero будут зависеть от мусора в старших битах более широкой операции. В сдвигах x86 последний бит сдвинут в флаг переноса, так что это даже влияет на сдвиги.

Операции, которые нельзя использовать с мусором в старших битах:

  • сдвиг вправо

  • полное умножение: например, для 16b x 16b -> 32b, убедитесь, что верхние 16 входов расширены нулями или знаками перед выполнением 32b x 32b -> 32b imul, Или используйте 16-битный один операнд mul или же imul неудобно поставить результат в dx:ax, (Выбор команды со знаком и без знака будет влиять на верхние 16b так же, как расширение до нуля или знака перед 32b imul.)

  • адресация памяти ([rsi + rax]): знак или расширение нуля по мере необходимости. Здесь нет [rsi + eax] режим адресации.

  • деление и остаток

  • log2 (то есть позиция старшего установленного бита)
  • конечный отсчет нуля (если только вы не знаете, что где-то в нужной части есть установленный бит, или просто проверьте результат, превышающий N, поскольку вы не нашли проверку.)

Дополнение Two, как и unsigned base 2, представляет собой систему стоимости-места. MSB для неподписанного base2 имеет значение места 2 N-1 в числе N битов (например, 2 31). В дополнении 2 MSB имеет значение -2 N-1 (и, таким образом, работает как знаковый бит). Статья в Википедии объясняет многие другие способы понимания дополнения 2 и отрицания числа без знака base2.

Ключевым моментом является то, что установленный бит знака не меняет интерпретацию других битов. Сложение и вычитание работают точно так же, как и для unsigned base2, и разница между подписанным и unsigned отличается только от интерпретации результата. (например, переполнение со знаком происходит, когда есть перенос в, но не из знакового бита.)

Кроме того, перенос распространяется только от LSB к MSB (справа налево). Вычитание одинаково: независимо от того, есть ли что-либо в старших битах для заимствования, младшие биты заимствуют это. Если это вызывает переполнение или перенос, будут затронуты только старшие биты. например:

 0x801F
-0x9123
-------
 0xeefc

Младшие 8 бит, 0xFC, не зависит от того, что они позаимствовали. Они "оборачиваются" и передают заем в верхнюю восьмерку.

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

поскольку LEA используется только сложение (и сдвиг влево), использование размера адреса по умолчанию всегда хорошо. Задержка усечения, пока размер операнда не вступает в игру для результата, всегда в порядке.

(Исключение: 16-битный код может использовать префикс размера адреса для выполнения 32-битной математики. В 32- или 64-битном коде префикс размера адреса уменьшает ширину, а не увеличивается.)

Умножение можно рассматривать как повторное сложение или как смещение и сложение. Нижняя половина не подвержена влиянию верхних битов. В этом 4-битном примере я выписал все битовые продукты, которые суммируются в младшие 2 результирующих бита. Только младшие 2 бита любого источника вовлечены. Понятно, что это работает в целом: частичные продукты сдвигаются перед сложением, поэтому старшие биты в источнике никогда не влияют на младшие биты в результате в целом.

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

    *Warning*: This diagram is probably slightly bogus.


       ABCD   A has a place value of -2^3 = -8
     * abcd   a has a place value of -2^3 = -8
     ------
   RRRRrrrr

   AAAAABCD * d  sign-extended partial products
 + AAAABCD  * c
 + AAABCD   * b
 - AABCD    * a  (a * A = +2^6, since the negatives cancel)
  ----------
          D*d
         ^
         C*d+D*c

Выполнение умножения со знаком вместо умножения без знака все равно дает тот же результат в младшей половине (младшие 4 бита в этом примере). Расширение знака частичных произведений происходит только в верхней половине результата.

Это объяснение не очень полное (и, возможно, даже содержит ошибки), но есть убедительные доказательства того, что оно верно и безопасно для использования в производственном коде:

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

  • Проектное решение Intel ввести только 2 и 3 формы операндов imul не mul,

Очевидно, что побитовые двоичные логические операции (и / или /xor/not) обрабатывают каждый бит независимо: результат для позиции бита зависит только от входного значения в этой позиции бита. Сдвиги битов также довольно очевидны.

Источник
Другие вопросы по тегам