assembly 如何在汇编中进行64位的64位除法？

f87krz0w  于 2023-05-29  发布在  其他
关注(0)|答案(3)|浏览(157)

如何在x86汇编中实现64位乘64位除法？
我已经使用.386指令启用了扩展寄存器。

assembly

3条答案

按热度按时间
z4bn682m

z4bn682m1#

滥用x87

FILD QWORD [SI]
FIDIV QWORD [BX]
FISTP QWORD [DI]

正如Peter Cordes提到的，在默认的FP舍入模式下，它舍入到最近，绑定到偶数。SSE 3中引入的FISTTP允许截断，因此其行为类似于IDIV指令。
它有两个舍入步骤，但由于x87保留64位，除数最多为263-1，增加或减少被除数会使商的变化大于eps。因此，它的行为就像第一步是准确的。

赞(0）分享  回复(0）举报  2023-05-29
zf9nrax1

zf9nrax12#

EDX：EAX中的64位值除以ECX：EBX中的64位值的无符号除法

在32位x86 CPU上，the div instruction可以将EDX：EAX中的32位值除以任何32位值。如果我们保持被除数扩展（EDX）中的值小于32位除数，我们甚至可以在EDX：EAX中（成功地）划分大于32位的值。
因此，如果我们希望能够将 * 任何 * 64位值除以 * 任何 * 其他64位值，我们需要为此编写代码。这个答案将使用名为Division by Partial Quotients aka Chunking的技术。

建议的算法不会击败内部div指令

即使你使用的是64位数据类型，实践告诉我，（通用）程序中的大多数除法仍然可以只使用内置的div指令。这就是为什么我在代码中添加了一个检测机制来检查ECX：EBX中的除数是否小于4GB（因此适合EBX），以及EDX中被除数的扩展是否小于EBX中的除数。如果满足这些条件，并且我们没有尝试除以零，那么普通的div指令就会完成这项工作，而且速度也更快。由于某种原因（如学校）使用div是不允许的，那么只需删除前缀代码即可。

算法描述

代码试图尽快摆脱特殊情况：

  • 如果除数为零，我们退出，进位标志设置为（i）。
  • 如果被除数为零，我们退出，商和余数都设置为零（ii）。
  • 如果被除数小于除数，则我们退出，商为零，余数等于被除数（iii）。
  • .BSR*（BitScanReverse）子例程使用the bsr instruction查找被除数和除数中为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
        test    ebx, ebx
        jz      .STC            ; Division by 0
        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
.STC:   stc
        ret
; - - - - - - - - - - - - - - -
; 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:   bsr     esi, edx
        jnz     @f
        bsr     esi, eax        ; -> ZF
        ret
@@:     add     esi, 32         ; -> ESI=[32,63] ZF=0
        ret
; ------------------------------

举例说明：34 / 5

被除数34是00100010 b，除数5是00000101 b。
它将产生商00000110 b（6）和余数00000100 b（4）。
二进制表示法当然还有56个0位！

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
我们现在将恢复加法 * 加40* 与进一步减法 * 减20* 组合成单个加法 * 加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

在代码中：

; ------------------------------
; Non-restoring
; IN (edx:eax,ecx:ebx) OUT (edx:eax,ecx:ebx,CF)
uDiv:   test    ecx, ecx
        jnz     .uDiv
        cmp     edx, ebx
        jnb     .uDiv
        test    ebx, ebx
        jz      .STC            ; Division by 0
        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
.STC:   stc
        ret
; - - - - - - - - - - - - - - -
; 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:   bsr     esi, edx
        jnz     @f
        bsr     esi, eax        ; -> ZF
        ret
@@:     add     esi, 32         ; -> ESI=[32,63] ZF=0
        ret
; ------------------------------

EDX：EAX中的64位值除以ECX：EBX中的64位值的带符号除法

最简单的方法是围绕我们上面讨论的无符号除法编写wrapper：

  • 如果一个输入是负的，我们就把它变成正的，我们记得这样做。
    • 负数 * 值8000'0000' 0000 '0000 h除以-1不能产生大于最大有符号整数7 FFF' FFFF 'FFFF'FFFFh（.c:）的 * 正数 * 值8000'0000'0000'0000 h。
  • 商的符号是被除数和除数的符号的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
        test    esi, 1
        jz      .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位数字，请查看此转换算法。

赞(0）分享  回复(0）举报  2023-05-29
6ovsh4lw

6ovsh4lw3#

x86知道一个64 × 32位的除法，其中余数和商的结果为32位，如下所示

POP     EBX      ;DIVISOR
POP     EDX      ;MSW OF DIVIDEND
POP     EAX      ;LSW OF DIVIDEND
DIV     EBX      ;64/32 BIT DIVIDE
PUSH    EDX      ; remainder
PUSH    EAX      ; quotient

你不想除以一个不适合32位的64位数，因为你会失去10位的精度，最低限度。
如果你坚持下去，你可以从中组成一个64/64的除法，然后分析你是否真的喜欢它。
如果你知道如何将一个2位数的十进制数除以一个2位数的十进制数（长除法），你可以使用上面的方法来完成将一个2位数的2^32基数除以一个2位数的2^32基数。这是留给读者的练习。

赞(0）分享  回复(0）举报  2023-05-29
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备2022004421号-2 NULL123 https://www.null123.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com