我试图将一个32位有符号整数除以一个16位有符号整数,得到一个带符号的32位商和16位余数。
我的目标是没有fpu的286。
我已经编写过代码来执行32位无符号除法:
DIV32 PROC
;DIVIDES A 32-BIT VALUE BY A 16-BIT VALUE.
;ALTERS AX
;ALTERS BX
;ALTERS DX
;EXPECTS THE 32-BIT DIVIDEND IN DX:AX
;EXPECTS THE 16-BIT DIVISOR IN BX
;RETURNS THE 32-BIT QUOTIENT IN DX:AX
;RETURNS THE 16-BIT REMAINDER IN BX
push di
push si
mov di, ax ;di -> copy of LSW of given dividend
mov ax, dx ;ax -> MSW of given dividend
xor dx, dx ;dx:ax -> 0:MSW
div bx ;ax:dx -> ax=MSW of final quotient, dx=remainder
mov si, ax ;si -> MSW of final quotient
mov ax, di ;dx:ax -> dx=previous remainder, ax=LSW of given dividend
div bx ;ax:dx -> ax=LSW of final quotient, dx=final remainder
mov bx, dx ;bx -> final remainder
mov dx, si ;dx:ax -> final quotient
pop si
pop di
ret
DIV32 ENDP
到目前为止,我已经尝试做了显而易见的事情,只是通过XOR DX, DX
和CWD
与DIV
交换IDIV
来修改我现有的代码:
IDIV32 PROC
;DIVIDES A SIGNED 32-BIT VALUE BY A SIGNED 16-BIT VALUE.
;ALTERS AX
;ALTERS BX
;ALTERS DX
;EXPECTS THE SIGNED 32-BIT DIVIDEND IN DX:AX
;EXPECTS THE SIGNED 16-BIT DIVISOR IN BX
;RETURNS THE SIGNED 32-BIT QUOTIENT IN DX:AX
;RETURNS THE 16-BIT REMAINDER IN BX
push di
push si
mov di, ax ;di -> copy of LSW of given dividend
mov ax, dx ;ax -> MSW of given dividend
cwd ;dx:ax -> 0:MSW, or ffff:MSW
idiv bx ;ax:dx -> ax=MSW of final quotient, dx=remainder
mov si, ax ;si -> MSW of final quotient
mov ax, di ;dx:ax -> dx=previous remainder, ax=LSW of given dividend
idiv bx ;ax:dx -> ax=LSW of final quotient, dx=final remainder
mov bx, dx ;bx -> final remainder
mov dx, si ;dx:ax -> final quotient
pop si
pop di
ret
IDIV32 ENDP
这适用于某些计算,例如-654,328 / 2 = -327164(0xfff60408 / 2 = fffb0204)。但它不适用于某些输入,-131,076 / 2返回-2余数0的错误结果。除数为1或-1会导致除法错误,看起来不管红利。
我已经测试了许多不同的正面和负面红利和除数,试图找到某种正确和不正确结果的模式,我注意到它无法正确返回-65538的结果。
我有一种预感,我应该根据输入有条件地使用CWD
,但似乎XOR DX, DX
更频繁地返回不正确的结果。当除数和被除数都为正且商数小于0x7fffffff时,两者都可以工作。
我不知道任何将大的负数分成几部分并为IDIV准备它的算法。我会计算被除数和除数的绝对值,使用函数DIV32并最后根据存储的符号处理结果:
IDIV32 PROC ; DX:AX / BX = DX/AX rem BX
; 99 / 5 = 19 rem 4
; 99 / -5 = -19 rem 4
; -99 / 5 = -19 rem -4
; -99 / -5 = 19 rem -4
mov ch, dh ; Only the sign bit counts!
shr ch, 7 ; CH=1 means negative dividend
mov cl, bh ; Only the sign bit counts!
shr cl, 7 ; CL=1 means negative divisor
cmp ch, 1 ; DX:AX negative?
jne J1 ; No: Skip the next two lines
not dx ; Yes: Negate DX:AX
neg ax ; CY=0 -> AX was NULL
cmc
adc dx, 0 ; Adjust DX, if AX was NULL
J1:
cmp cl, 1 ; BX negative?
jne J2 ; No: Skip the next line
neg bx ; Yes: Negate BX
J2:
push cx ; Preserve CX
call DIV32
pop cx ; Restore CX
cmp ch, cl ; Had dividend and divisor the same sign?
je J3 ; Yes: Skip the next two lines
not dx
neg ax ; CY=0 -> AX was NULL
cmc
adc dx, 0 ; Adjust DX, if AX was NULL
J3:
cmp ch, 1 ; Was divisor negative?
jnz J4 ; No: Skip the next line
neg bx ; Negate remainder
J4:
ret
IDIV32 ENDP
您的算法无法简单地更改为签名。
我们以计算(+1)/( - 1)为例:
(+1)/( - 1)=( - 1),余数为0
在算法的第一步中,您将高位除以除数:
(+1)的高位为0,因此您正在计算:
0 /( - 1)= 0,余数为0
然而,整个32位除法的正确高位是0FFFFh,而不是0.并且第二次除法所需的提醒也是0FFFFh而不是0。
哦,所以第二个IDIV应该是DIV。好的,我明天醒来时会测试它。如果我让它工作,我会添加一个答案。
第一个分部已经没有产生你想要的结果。所以改变第二师不会有多大帮助......
除数为1或-1会导致除法错误,而不管红利如何。
只有当股息的第15位被设定时,我才会期待这一点:
在这些情况下,你要划分:
...但是,结果是带符号的16位值,因此必须在-8000h ... + 7FFFh范围内。
我刚刚在运行DOS的虚拟机中尝试了12345678h /(+ 1)和12345678h /( - 1):
未设置12345678h的第15位;两次我都没有得到除法错误。 (但除以-1时错误的结果!)
使用2x idiv
有一个基本问题:我们需要第二个除法产生商的低半部分,它是无符号的,可以是0到0xffff之间的任何值。
只有多字整数的最高字包含符号位,下面的所有位都具有正的位值。 idiv
的商范围是-2^15 .. 2^15-1
,而不是0 .. 65535
。是的,idiv
可以生成所有必需的值,但不能从我们从第一个分区结果的简单修正中获得的输入中获得。例如,0:ffff
/ 1
将导致与idiv
的#DE异常,因为商不符合带符号的16位整数。
因此,第二个除法指令必须是div
,使用除数的绝对值和适当的高半。 (div
要求它的两个输入都是无符号的,所以来自第一个idiv
的有符号余数也是一个问题。)
可能仍然可以使用idiv
作为第一个分区,但只有在div
之前使用其结果的修正,除了仍然必须取除数的绝对值和第一个余数来提供未签名的div
。这是一个有趣的可能性,但在实践中,保存并重新应用未签名部门的标志会更便宜。
正如@Martin所指出的那样,+1 / -1
与天真idiv
的第一个分区给出了错误的高半商(0 / -1 = 0而不是-1),而第二个分区的错误输入(0%-1 = 0,不是 - 1)。 TODO:弄清楚实际需要什么样的修正。也许只是一个条件+ -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
的这种快速测试仍然是一个好主意,在绝对值计算之后进行另一次测试。
分支在286上很便宜,所以我主要保留分支而不是使用无分支abs()
。 (例如,对于单个寄存器:使用cdq(或sar reg,15
)/ xor / sub,like compilers make,基于qzxswpoi的2的补码标识)。当然,在P6家族之前,-x = ~x + 1
/ mov
/ neg
不可用。如果您需要使用286,但主要关注现代CPU的性能,您可能会做出不同的选择。但事实证明,32位无分支ABS的代码大小比分支小。但是,对于正输入而言,它可能比分支更慢,其中一些指令将被跳过。 cmovl
有一个有趣的想法,即为被除数和除数创建0 / -1整数,然后为了以后重新应用这些符号,你可以将它们混合在一起,并使用相同的XOR / SUB 2的补码bithack对结果进行符号翻转。
样式:本地标签(在函数内)以Assembler 8086 divide 32 bit number in 16 bit number为前缀。我认为这对于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
跳转。避免将符号位向下移动到8位寄存器的底部。可以使用xor / jns对相同符号进行测试,因为相同的符号将“取消”并且SF = 0,无论它是-0还是两者都是1。 (一般来说,XOR可以用于比较相等,但它通常只对那些关心一位但不关心其他的按位情况有用)。js
与mov cx,dx
没有任何不利因素)。我们还避免读取高8位部分寄存器(例如mov ch,dh
而不是test cx,cx
),因为它在最近的英特尔Sandybridge系列CPU上具有更高的延迟。 (test ch,ch
)。在P6系列中,写入低8位部分寄存器会将它们与完整寄存器分开重命名,因此最好在写入之后读取8位部分寄存器。
当然,在现代CPU上,像How exactly do partial registers on Haswell/Skylake perform? Writing AL seems to have a false dependency on RAX, and AH is inconsistent这样的16位寄存器是部分寄存器,即使在16位模式下也是如此(因为那里有32位寄存器),所以即使cx
也错误地依赖于ECX的旧值。显然,在32位寄存器/操作数大小可用的386+上,即使在16位模式下也可以使用它:
mov cx,dx
这可以#DE从BX = 0,或从DX溢出:AX = -2 ^ 31和BX = -1(;; 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
)
NASM包装器从32位模式调用
LONG_MIN/-1
C程序,编译为32位并与asm链接:
%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
(这是#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
之间的草率,因为我只关心它在x86 Linux上运行,那里的类型相同。)
编译
int32_t
使用 nasm -felf32 div32-16.asm &&
gcc -g -m32 -Wall -O3 -march=native -fno-pie -no-pie div32-test.c div32-16.o
运行以测试从该值到0x7ffe的所有股息(step = -1),divisor = -2。 (对于./a.out 131076 -2 -1
,-a / -b
等的所有组合)
我没有为商和除数做嵌套循环;你可以用shell做到这一点。我也没有做任何聪明的事情来测试最大值附近的一些股息和一些接近底部的股息。
我重写了我的a / -b
程序,以便它否定一个负的被除数或除数为正/无符号形式,执行无符号除法,然后如果被除数XOR除数为真则否定商。
编辑:使用idiv32
和js
而不是测试80h的位掩码。不要再费力了。剩余部分应该分享股息的标志,但由于我并不真正需要余数,所以我不打算使程序更加复杂以正确处理它。
jns