EDX:EAX 中的 64 位值除以 ECX:EBX 中的 64 位值的无符号除法
在 32 位 x86 CPU 上，the div操作说明可以将 EDX:EAX 中的 32 位值除以任何 32 位值。如果我们保持被除数扩展 (EDX) 中的值小于 32 位除数，我们甚至可以（成功）除 EDX:EAX 中大于 32 位的值。
所以，如果我们想要能够划分any64 位值any其他 64 位值，我们需要为其编写代码。这个答案将使用一种名为除以部分商，又称为分块.
所提出的算法不会击败内部算法div操作说明
即使您使用 64 位数据类型，实践告诉我，（通用）程序中的大多数除法仍然可以仅使用内置的div操作说明。这就是为什么我在代码中添加了一个检测机制作为前缀，该机制检查 ECX:EBX 中的除数是否小于 4GB（因此适合 EBX），以及 EDX 中的除数扩展是否小于 EBX 中的除数。如果满足这些条件，则正常div指令可以完成这项工作，而且速度也更快。如果出于某种原因（例如学校）使用div不允许，那么只需删除前缀代码就可以了。
所描述的算法
代码试图尽快摆脱特殊情况：
- 如果除数为零，则退出并设置进位标志 (i)。
- 如果被除数为零，则退出时商和余数都设置为零 (ii)。
- 如果被除数小于除数，我们将以零商和等于被除数的余数退出 (iii)。
The .BSR(BitScanReverse)子程序使用the bsr操作说明查找被除数和除数中 ON 的最高位：
- 如果返回 SET 零标志，这只能发生在除数上，因为我们之前消除了零除数 (i)，我们得出结论，除数为零，然后退出 (ii)。
- 如果我们得到的被除数小于除数，我们就得出除法毫无意义的结论，然后退出 (iii)。
- 如果我们得到的被除数等于除数，我们就知道除数与被除数一致。无需换档。
- 如果我们得到的被除数大于除数，我们就开始将除数向左移动，使其与被除数对齐。
此时的除数已成为一系列试减中使用的第一个值：
- 对于每次成功的减法，我们都会在尝试构建的商中设置一个匹配位。换句话说：我们加上一个部分商。如果此时当前的股息变为零，我们就完成了，否则我们继续循环。
- 另一方面，如果减法失败，我们首先恢复当前被除数，然后再继续循环。
- 循环继续，将当前除数减半。一旦当前除数回到其原始值（并用于试减），我们就不应该再将其减半，而应将当前除数中剩下的部分视为最终余数。
; ------------------------------
; Restoring
; IN (edx:eax,ecx:ebx) OUT (edx:eax,ecx:ebx,CF)
uDiv: test ecx, ecx
jnz .uDiv
cmp edx, ebx
jnb .uDiv
div ebx ; EDX:EAX / EBX --> EAX Quotient, EDX Remainder
mov ebx, edx ; Remainder to ECX:EBX
xor edx, edx ; Quotient to EDX:EAX
ret ; CF=0
; - - - - - - - - - - - - - - -
; IN (edx:eax,ecx:ebx) OUT (edx:eax,ecx:ebx,CF)
.uDiv: push esi edi
mov esi, ebx
or esi, ecx
stc
jz .NOK ; (i) Division by 0
xor edi, edi
push edi edi ; (1) 64-bit Quotient under construction
call .BSR ; -> ESI ZF
jz .NIL ; (ii) Dividend is 0
mov edi, esi ; Save position highest set bit in Dividend
xchg ebx, eax ; -> ECX:EBX is Dividend, EDX:EAX is Divisor
xchg ecx, edx
call .BSR ; -> ESI ZF=0 (because we know Divisor <> 0)
sub edi, esi ; Delta between positions of highest set bits
jb .OK ; (iii) Small Dividend / Big Divisor
jz .d ; No shifting required
cmp edi, 32 ; Shift up Divisor so it aligns with Dividend
jb .a
xchg edx, eax ; Before EDX was 0
.a: xchg ecx, edi
shld edx, eax, cl ; CPU uses CL Mod 32
shl eax, cl
xchg ecx, edi
jmp .d
.b: add ebx, eax ; Restore Dividend after failed subtraction
adc ecx, edx
.c: dec edi
js .OK ; We're (back) at the original Divisor
shr edx, 1 ; Next try a smaller Divisor (/2)
rcr eax, 1
.d: sub ebx, eax ; Try subtracting Divisor from Dividend
sbb ecx, edx
jb .b ; Cannot
bts [esp], edi ; -(1)- Add partial quotient
mov esi, ebx ; Is Dividend reduced to zero ?
or esi, ecx
jnz .c ; Not yet
.NIL: xor ebx, ebx ; Zero Remainder
xor ecx, ecx
.OK: pop eax edx ; (1) EDX:EAX is Quotient, ECX:EBX is Remainder
clc
.NOK: pop edi esi
ret
; - - - - - - - - - - - - - - -
; IN (edx:eax) OUT (esi,ZF)
.BSR: xor esi, esi
test edx, edx
jnz @f
bsr esi, eax ; -> ESI=[0,31] ZF
ret
@@: bsr esi, edx ; -> ESI=[0,31] ZF=0
add esi, 32 ; -> ESI=[32,63] ZF=0
ret
; ------------------------------
例如：34 / 5
被除数 34 是 00100010b，除数 5 是 00000101b。
它将产生商 00000110b (6) 和余数 00000100b (4)。
当然，二进制表示法还多了 56 个零位！
Aligned
v
00100010 (34)
- 00101000 (40) Divisor << 3
--------
11111010 (-6) NOK ---------------> Quotient = 00000000
+ 00101000 (40) Restore
--------
00100010 (34)
- 00010100 (20) Divisor << 2
-------- \----------->-----------\
00001110 (14) OK ----------------> Quotient = 00000100
- 00001010 (10) Divisor << 1
-------- \----------->------------\
00000100 ( 4) OK ----------------> Quotient = 00000110
- 00000101 ( 5) Divisor << 0
--------
11111111 (-1) NOK ---------------> Quotient = 00000110 (6)
+ 00000101 ( 5) Restore
--------
00000100 ( 4) Remainder
一个优化
一个不错的改进是，在减法失败的情况下不必恢复股息。
与之前相同的示例：34 / 5
我们现在结合恢复添加plus 40进一步减法minus 20进入单一加法plus 20.
当然，最后，当不再进行减法时，我们仍然需要最后的恢复来获得余数。
Aligned
v
00100010 (34)
- 00101000 (40) Divisor << 3
--------
11111010 (-6) NOK ---------------> Quotient = 00000000
+ 00010100 (20) Divisor << 2
-------- \----------->-----------\
00001110 (14) OK ----------------> Quotient = 00000100
- 00001010 (10) Divisor << 1
-------- \----------->------------\
00000100 ( 4) OK ----------------> Quotient = 00000110
- 00000101 ( 5) Divisor << 0
--------
11111111 (-1) NOK ---------------> Quotient = 00000110 (6)
+ 00000101 ( 5) Restore
--------
00000100 ( 4) Remainder
In code:
; ------------------------------
; Non-restoring
; IN (edx:eax,ecx:ebx) OUT (edx:eax,ecx:ebx,CF)
uDiv: test ecx, ecx
jnz .uDiv
cmp edx, ebx
jnb .uDiv
div ebx ; EDX:EAX / EBX --> EAX Quotient, EDX Remainder
mov ebx, edx ; Remainder to ECX:EBX
xor edx, edx ; Quotient to EDX:EAX
ret ; CF=0
; - - - - - - - - - - - - - - -
; IN (edx:eax,ecx:ebx) OUT (edx:eax,ecx:ebx,CF)
.uDiv: push esi edi
mov esi, ebx
or esi, ecx
stc
jz .NOK ; (i) Division by 0
xor edi, edi
push edi edi ; (1) 64-bit Quotient under construction
call .BSR ; -> ESI ZF
jz .NIL ; (ii) Dividend is 0
mov edi, esi ; Save position highest set bit in Dividend
xchg ebx, eax ; -> ECX:EBX is Dividend, EDX:EAX is Divisor
xchg ecx, edx
call .BSR ; -> ESI ZF=0 (because we know Divisor <> 0)
sub edi, esi ; Delta between positions of highest set bits
jb .OK ; (iii) Small Dividend / Big Divisor
jz .d ; No shifting required
cmp edi, 32 ; Shift up Divisor so it aligns with Dividend
jb .a
xchg edx, eax ; Before EDX was 0
.a: xchg ecx, edi
shld edx, eax, cl ; CPU uses CL Mod 32
shl eax, cl
xchg ecx, edi
jmp .d
.OK_: add ebx, eax ; Final restore to obtain Remainder
adc ecx, edx
jmp .OK
ALIGN 16
.b: dec edi
js .OK_ ; We're (back) at the original Divisor
shr edx, 1 ; Next try a smaller Divisor (/2)
rcr eax, 1
add ebx, eax ; This ADD/ADC replaces the restoring
adc ecx, edx ; ADD/ADC followed by a further SUB/SBB
js .b
jmp .e
ALIGN 16
.c: dec edi
js .OK ; We're (back) at the original Divisor
shr edx, 1 ; Next try a smaller Divisor (/2)
rcr eax, 1
.d: sub ebx, eax ; Try subtracting Divisor from Dividend
sbb ecx, edx
jb .b ; Cannot
.e: bts [esp], edi ; -(1)- Add partial quotient
mov esi, ebx ; Is Dividend reduced to zero ?
or esi, ecx
jnz .c ; Not yet
.NIL: xor ebx, ebx ; Zero Remainder
xor ecx, ecx
.OK: pop eax edx ; (1) EDX:EAX is Quotient, ECX:EBX is Remainder
clc
.NOK: pop edi esi
ret
; - - - - - - - - - - - - - - -
; IN (edx:eax) OUT (esi,ZF)
.BSR: xor esi, esi
test edx, edx
jnz @f
bsr esi, eax ; -> ESI=[0,31] ZF
ret
@@: bsr esi, edx ; -> ESI=[0,31] ZF=0
add esi, 32 ; -> ESI=[32,63] ZF=0
ret
; ------------------------------
EDX:EAX 中的 64 位值除以 ECX:EBX 中的 64 位值有符号除法
最简单的方法是写一个wrapper围绕我们上面讨论的无符号除法：
- 如果输入是负数，我们会将其设为正数，并且我们会记住这样做。
- 划分negative值 8000'0000'0000'0000h 除 -1 不允许产生positive值 8000'0000'0000'0000h 大于最大有符号整数 7FFF'FFFF'FFFF'FFFFh (
.c:).
- 商的符号是被除数和除数的符号的 XOR，因此两次减 (-) 的结果是加 (+) (
.d:).
- 余数的符号与我们在股息上的符号相同（
.e:).
; ------------------------------
; IN (edx:eax,ecx:ebx) OUT (edx:eax,ecx:ebx,CF)
iDiv: push esi
xor esi, esi
test edx, edx ; Sgn(Num1)
jns .a
neg edx ; Abs(Num1)
neg eax
sbb edx, esi ; ESI=0
xor esi, 3 ; Bit 1 is for Remainder, bit 0 is for Quotient
.a: test ecx, ecx ; Sgn(Num2)
jns .b
neg ecx ; Abs(Num2)
neg ebx
sbb ecx, 0
xor esi, 1 ; Bit 0 is for Quotient
.b: call uDiv ; -> EDX:EAX ECX:EBX CF
jc .NOK ; 'Division by zero'
.c: test edx, edx
jns .d ; It's not 8000'0000'0000'0000h
cmp esi, 11b
jb .NOK ; Signed overflow
.d: shr esi, 1 ; Sign for Quotient
jnc .e
neg edx ; Neg(Quotient)
neg eax
sbb edx, 0
.e: shr esi, 1 ; Sign for Remainder
jnc .OK
neg ecx ; Neg(Remainder)
neg ebx
sbb ecx, esi ; ESI=0
.OK: clc
.NOK: pop esi
ret
; ------------------------------
看看这个转换算法如果您需要显示 EDX:EAX 中的 64 位数字。
