Использование 2x idiv имеет фундаментальную проблему : нам нужно 2-е деление, чтобы получить младшую половину частного, которая является беззнаковой и может быть любой от 0 до 0xffff.
Только старшее слово многословного целого содержит бит знака, все биты ниже которого имеют положительное значение-место.Коэффициент idiv равен -2^15 .. 2^15-1, а не 0 .. 65535.Да, idiv может выдавать все необходимые значения, но не из входных данных, которые мы можем получить из простых исправлений результатов первого деления.Например, 0:ffff / 1 приведет к исключению #DE с idiv, поскольку частное не помещается в знаковое 16-разрядное целое число.
Таким образом, инструкция второго деления имеет , равную div, с использованием абсолютного значения делителя и соответствующей старшей половины.(div требует, чтобы оба его входа были без знака, так что остаток со знаком от первого idiv также мог бы быть проблемой.)
Возможно все еще возможно использовать idiv для первого деления, но только с исправлениями для его результатов до div, поверх которого все еще приходится принимать абсолютное значение делителя и первого остатка для подачи без знака div.Это интересная возможность, но на практике сэкономить и повторно применить знаки вокруг неподписанного деления будет дешевле.
Как указывает @Martin, первое деление +1 / -1 с наивным idiv дает неправильноевысокий половинный коэффициент (0 / -1 = 0, а не -1) и неправильный ввод для 2-го деления (0% -1 = 0, а не -1).ТОДО: выяснить, какие исправления на самом деле понадобятся.Может быть, просто условное + -1, но мы знаем, что величина остатка не может быть больше делителя, потому что high_half < divisor необходимо и достаточно для div, чтобы не ошибаться.
Ваш -131,076/ 2 = -2 (возможно по совпадению) только на 1 в половине его результата:
это должно быть 0xfffefffe = -2: -2, а не -1: -2.
Оптимизированная версия функции @ rkhb с встроенным DIV32.
Мы записываем входные знаки, а затем делаем беззнаковые деления на абсолютные значения, а потом восстанавливаем знак.(Если знак остатка не нужен, мы можем упростить; частный знак зависит только от xor dividend,divisor)
Или, если дивиденд достаточно мал, мы можем использовать один idiv,Однако мы должны избегать случая переполнения -2^15 / -1, поэтому быстрая проверка DX, являющегося расширением знака AX, не только пропускает некоторые безопасные случаи (с большими делителями), но и пробует этот небезопасный случай.Если встречаются небольшие числа (как в большинстве компьютерных программ), этот быстрый тест, основанный на cwd, все еще может быть хорошей идеей, с другим тестом после вычисления абсолютного значения.
Ветви дешевы-ish на 286, поэтому я в основном сохранил ветвление вместо использования abs().(например, для одного регистра: с помощью cdq (или sar reg,15) / xor / sub, подобные компиляторы составляют , основываясь на идентичности дополнения 2, равной -x = ~x + 1).И mov / neg / cmovl, конечно, недоступен до семейства P6.Если вам нужно совместить с 286, но в основном заботиться о производительности на современных процессорах, вы можете сделать другой выбор.Но оказывается, что 32-разрядная АБС без ответвлений имеет меньший размер кода, чем ветвление.Тем не менее, это, вероятно, медленнее, чем ветвление для положительных входных данных, где некоторые инструкции были бы пропущены. Ассемблер 8086 делит 32-битное число на 16-битное число имеет интересную идею создания целых чисел 0 / -1 как для делителя, так и для делителя, а затем для последующего повторного применения знаков вы можете XOR их вместе и использоватьтот же битовый хак XOR / SUB 2, чтобы подписать результаты или нет.
Стиль: локальные метки (внутри функции) с префиксом @@.Я думаю, что это нормально для TASM, как локальные метки NASM .label.
; signed 32/16 => 32-bit division, using 32/16 => 16-bit division as the building block
; clobbers: CX, SI
IDIV32 PROC ; DX:AX / BX = DX/AX rem BX
;global IDIV32_16 ; for testing with NASM under Linux
;IDIV32_16:
; 99 / 5 = 19 rem 4
; 99 / -5 = -19 rem 4
; -99 / 5 = -19 rem -4
; -99 / -5 = 19 rem -4
mov cx, dx ; save high half before destroying it
;;; Check for simple case
cwd ; sign-extend AX into DX:AX
cmp cx, dx ; was it already correctly sign-extended?
jne @@dividend_32bit
; BUG: bx=-1 AX=0x8000 overflows with #DE
; also, this check rejects larger dividends with larger divisors
idiv bx
mov bx, dx
cwd
ret
;;; Full slow case: divide CX:AX by BX
@@dividend_32bit:
mov si, ax ; save low half
mov ax, cx ; high half to AX for first div
; CH holds dividend sign
mov cl, bh ; CL holds divisor sign
;;; absolute value of inputs
; dividend in AX:SI
cwd ; 0 or -1
xor si, dx ; flip all the bits (or not)
xor ax, dx
sub si, dx ; 2's complement identity: -x = ~x - (-1)
sbb ax, dx ; AX:SI = abs(dividend)
test bx, bx ; abs(divisor)
jnl @@abs_divisor
neg bx
@@abs_divisor:
;;; Unsigned division of absolute values
xor dx, dx
div bx ; high half / divisor
; dx = remainder = high half for next division
xchg ax, si
div bx
;;; absolute result: rem=DX quot=SI:AX
mov bx, dx
mov dx, si
;;; Then apply signs to the unsigned results
test cx,cx ; remainder gets sign of dividend
jns @@remainder_nonnegative
neg bx
@@remainder_nonnegative:
xor cl, ch ; quotient is negative if opposite signs
jns @@quotient_nonnegative
neg dx
neg ax ; subtract DX:AX from 0
sbb dx, 0 ; with carry
@@quotient_nonnegative:
ret
IDIV32 ENDP
Оптимизации:
более простое сохранение знака и тестирование знака с использованием встроенного в x86 флага знака, установленного из MSB результата, и скачок js, если SF == 1.Предотвращает смещение знака вниз до 8-битного регистра.Тестирование на одинаковые знаки может быть выполнено с помощью xor / jns, потому что одни и те же знаки «отменят» и оставят SF = 0 независимо от того, было ли это оба-0 или оба-1.(Как правило, XOR может использоваться для сравнения на равенство, но обычно это полезно только для побитовых случаев, когда вам важен один бит, но не другие).
Избегайте записи CH с помощьюсамо по себе, в интересах современных процессоров Intel, которые делают частичное переименование регистров для этого случая.Эта функция никогда не переименовывается в CH отдельно от остальной части ECX.(На более старых процессорах, таких как 286, нет недостатка в mov cx,dx против mov ch,dh).Мы также избегаем чтения 8-ю частичных регистров (например, test cx,cx вместо test ch,ch), потому что это имеет большую задержку на современных процессорах семейства Intel Sandybridge.( Как именно выполняют частичные регистры на Haswell / Skylake? Запись AL, кажется, ложно зависит от RAX, а AH несовместима ).В семействе P6 при записи неполных 8 регистров частичного имени их переименовывают отдельно от полного регистра, поэтому, вероятно, лучше всего просто читать 8-битные частичные регистры после записи любого.
Конечно, на современных процессорах 16-битные регистры, такие как cx , являются частичными регистрами, даже в 16-битном режиме (поскольку там доступны 32-битные регистры), поэтому даже mov cx,dx имеет ложную зависимость от старого значения ECX.
На 386 +
Очевидно, на 386+, где доступны 32-битные регистры / размер операнда , вы должны использоватьчто даже в 16-битном режиме:
;; i386 version
;; inputs: DX:AX / BX
shl edx, 16
mov dx, ax ; pack DX:AX into EDX
mov eax, edx
movsx ebx, bx ; sign-extend the inputs to 32 bit EBX
cdq ; and 64-bit EDX:EAX
idiv ebx
; results: quotient in EAX, remainder in EDX
mov ebx, edx ; remainder -> bx
mov edx, eax
sar edx, 16 ; extract high half of quotient to DX
;; result: quotient= DX:AX, remainder = BX
Это может #DE из BX = 0 или при переполнении из DX: AX = -2 ^ 31 и BX = -1 (LONG_MIN/-1)
Жгут тестов:
Оболочка NASM для вызова из 32-битного режима
%if __BITS__ = 32
global IDIV32
IDIV32:
push esi
push ebx
push edi ; not actually clobbered in this version
movzx eax, word [esp+4 + 12]
movzx edx, word [esp+6 + 12]
movzx ebx, word [esp+8 + 12]
call IDIV32_16
shl edx, 16
mov dx, ax
mov eax, edx
movsx edx, bx ; pack outputs into EDX:EAX "int64_t"
pop edi
pop ebx
pop esi
ret
%endif
C программа, скомпилировать как 32-битную и связать с asm:
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <limits.h>
// returns quotient in the low half, remainder in the high half (sign extended)
int64_t IDIV32(int32_t dxax, int16_t bx);
static int test(int a, short b) {
// printf("\ntest %d / %d\n", a, b);
int64_t result = IDIV32(a,b);
int testrem = result>>32;
int testquot = result;
if (b==0 || (a==INT_MIN && b==-1)) {
printf("successfully called with inputs which overflow in C\n"
"%d/%d gave us %d rem %d\n",
a,b, testquot, testrem);
return 1;
}
int goodquot = a/b, goodrem = a%b;
if (goodquot != testquot || goodrem != testrem) {
printf("%d/%d = %d rem %d\t but we got %d rem %d\n",
a,b, goodquot, goodrem, testquot, testrem);
printf("%08x/%04hx = %08x rem %04hx\t but we got %08x rem %04hx\n"
"%s quotient, %s remainder\n",
a,b, goodquot, goodrem, testquot, testrem,
goodquot == testquot ? "good" : "bad",
goodrem == testrem ? "good" : "bad");
return 0;
}
return 1;
}
int main(int argc, char*argv[])
{
int a=1234, b=1;
if(argc>=2) a = strtoll(argv[1], NULL, 0); // 0x80000000 becomes INT_MIN instead of saturating to INT_MAX in 32-bit conversion
if(argc>=3) b = strtoll(argv[2], NULL, 0);
test(a, b);
test(a, -b);
test(-a, b);
test(-a, -b);
if(argc>=4) {
int step=strtoll(argv[3], NULL, 0);
while ( (a+=step) >= 0x7ffe) { // don't loop through the single-idiv fast path
// printf("testing %d / %d\n", a,b);
test(a, b);
test(-a, -b);
test(a, -b);
test(-a, b);
}
return 0;
}
}
(Это небрежно между int и int32_t, потому что я забочусь только о том, чтобы он работал на x86 Linux, где тот же тип.)
Компилировать с
nasm -felf32 div32-16.asm &&
gcc -g -m32 -Wall -O3 -march=native -fno-pie -no-pie div32-test.c div32-16.o
Запустите с ./a.out 131076 -2 -1, чтобы проверить все дивиденды от этого до 0x7ffe (шаг = -1) с делителем = -2.(Для всех комбинаций -a / -b, a / -b и т. Д.)
Я не делал вложенных циклов для частного и делителя;Вы можете сделать это с оболочкой.Я также не делал ничего умного для тестирования некоторых дивидендов вокруг максимума и некоторых в нижней части диапазона.