64位汇编除法

Question

我需要一种在x86汇编中轻松地将64位无符号整数进行除法的方法。我的数字保存在两个32位寄存器EDX：EAX中，我需要将结果放回到EDX：EAX中。因子为32位整数。请提供一些代码？

- Nick

---

仅作澄清，你的意思是使用还是不使用x64指令？也就是说，这只是将数据放入64位寄存器（例如RAX），执行64位除法，然后将它们分割成32位寄存器的问题，还是你正在尝试在32位处理器上模拟64位除法？ - WeirdlyCheezy

没有64位寄存器 - 我正在尝试在32位上模拟64位除法。 - Nick

如果是这样的话，听起来你基本上是在从零开始实现二进制除法。在我看来，这似乎有点宽泛了。你到目前为止尝试了什么？你卡在哪个更具体的部分了吗？ - WeirdlyCheezy

如果到明天没有其他人发布解决方案，我会看看我能否凑出一个解决方案。 - WeirdlyCheezy

@Brendan 我并没有暗示你可以将一个大的除法分成更小的部分（顺便说一句，如果被除数和除数的值允许，有些情况下确实可以这样做）。我只是建议对于更大的整数，可以重复使用相同的基本长除法算法（如链接答案中所实现的）。 - Alexey Frunze

Answer 1

如果我正确理解了您的问题（特别是“因子是32位整数”部分），您想将64位被除数除以32位除数，并得到64位商。

如果我的理解是正确的，那么在32位代码中实现这个功能其实很容易。

思路是将被除数的“两半”分别除以除数，并重复使用第一次除法的余数进行第二次除法。

以下是C代码示例：

#include <stdio.h>
#include <limits.h>

#define C_ASSERT(expr) extern char CAssertExtern[(expr)?1:-1]

#if UINT_MAX >= 0xFFFFFFFF
typedef unsigned int uint32;
#else
typedef unsigned long uint32;
#endif
typedef unsigned long long uint64;

typedef unsigned long ulong;

// Make sure uint32=32 bits and uint64=64 bits
C_ASSERT(sizeof(uint32) * CHAR_BIT == 32);
C_ASSERT(sizeof(uint64) * CHAR_BIT == 64);

int div64by32eq64(uint64* dividend, uint32 divisor)
{
  uint32 dividendHi = (uint32)(*dividend >> 32);
  uint32 dividendLo = (uint32)*dividend;
  uint32 quotientHi;
  uint32 quotientLo;

  if (divisor == 0)
    return 0;

  // This can be done as one 32-bit DIV, e.g. "div ecx"
  quotientHi = dividendHi / divisor;
  dividendHi = dividendHi % divisor;

  // This can be done as another 32-bit DIV, e.g. "div ecx"
  quotientLo = (uint32)((((uint64)dividendHi << 32) + dividendLo) / divisor);

  *dividend = ((uint64)quotientHi << 32) + quotientLo;

  return 1;
}

int main(void)
{
  static const struct
  {
    uint64 dividend;
    uint32 divisor;
  } testData[] =
  {
    { 1 , 0 },
    { 0xFFFFFFFFFFFFFFFFULL, 1 },
    { 0xFFFFFFFFFFFFFFFFULL, 2 },
    { 0xFFFFFFFF00000000ULL, 0xFFFFFFFFUL },
    { 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFUL },
  };
  int i;

  for (i = 0; i < sizeof(testData)/sizeof(testData[0]); i++)
  {
    uint64 dividend = testData[i].dividend;
    uint32 divisor = testData[i].divisor;

    printf("0x%016llX / 0x%08lX = ", dividend, (ulong)divisor);

    if (div64by32eq64(&dividend, divisor))
      printf("0x%016llX\n", dividend);
    else
      printf("division by 0 error\n");
  }

  return 0;
}

输出 (ideone)：

0x0000000000000001 / 0x00000000 = division by 0 error
0xFFFFFFFFFFFFFFFF / 0x00000001 = 0xFFFFFFFFFFFFFFFF
0xFFFFFFFFFFFFFFFF / 0x00000002 = 0x7FFFFFFFFFFFFFFF
0xFFFFFFFF00000000 / 0xFFFFFFFF = 0x0000000100000000
0xFFFFFFFFFFFFFFFF / 0xFFFFFFFF = 0x0000000100000001

现在是汇编中的等效除法代码（使用NASM语法），未检查除以0的情况：

; 64-bit dividend
mov edx, 0xFFFFFFFF
mov eax, 0xFFFFFFFF

; 32-bit divisor
mov ecx, 0xFFFFFFFF

push eax
mov eax, edx
xor edx, edx
div ecx ; get high 32 bits of quotient
xchg eax, [esp] ; store them on stack, get low 32 bits of dividend
div ecx ; get low 32 bits of quotient
pop edx ; 64-bit quotient in edx:eax now
; edx:eax should now be equal 0x0000000100000001

- Alexey Frunze

---

【已解决】.. 哇！成功了！谢谢，这正是我需要的 :) ... 感谢大家！ - Nick

唉...除非你真的想要总线锁定，否则请不要使用带有内存操作数的xchg。 - fuz

@roeland 如果商数不适合32位，即商数为0x100000000或更大，则在div指令中会发生除法溢出。为了发生这种情况，被除数的最高有效32位需要大于或等于除数。但是这32位保证小于除数，因为它们是通过相同除数的第一次除法得到的余数。因此，第二次除法总是产生适合32位的商数。没有溢出。 - Alexey Frunze

@AlexeyFrunze 好的，所以 div 的被除数输入是 64 位的？ - roeland

@roeland 这个已经在1986年的i80386文档中有记录了。 - Alexey Frunze

Answer 2

快速术语回顾：被除数/除数=商+余数/除数

首先检查除数是否为零（如果是，则中止）。

     test eax,eax
     jne .ok
     test edx,edx
     je .divisionByZero
.ok:

将除数向左移位，直到最高有效位被设置，同时记录您进行了多少次移位：

    xor ebp,ebp            ;ebp = bits shifted so far
    test edx,(1 << 31)
    jne .l2
.l1:
    shld edx,eax,1
    shl eax,1
    inc ebp
    test edx,(1 << 31)
    jne .l1
.l2:

将当前结果设为零：

    xor esi,esi
    xor edi,edi

现在将除数移回到其原始位置；同时从剩余的被除数中减去当前除数，并在当前除数小于当前被除数时，在结果中设置一位。

.nextBit:
    shld edi,esi,1
    shl esi,1

    cmp ecx,edx
    jb .doneBit
    ja .subtract
    cmp ebx,eax
    jb .doneBit

.subtract:
    sub ecx,edx
    sbb ebx,eax
    or esi,1

.doneBit:
    sub ebp,1
    jnc .nextBit

此时，EDX:EAX的值与之前相同，EDI:ESI是结果，ECX:EBX是余数。

警告：以上所有内容都没有经过测试。这只是一个示例/描述。

注意：如果数字是有符号的，则需要先从分子和除数中删除符号位；然后稍后在结果和余数中设置符号位（sign = numerator_sign XOR divisor_sign）。

- Brendan

Answer 3

使用div指令怎么样？

- Jens Björnhager

---

当然，但是如果您在两个寄存器中保存了一个长数字，您不能只使用一个或两个“div”。您需要一种方法来分割数字的一部分（EDX），数字的第二部分（EAX），将结果组合并将最终结果保存回EDX：EAX。我正在寻找这种方法。 - Nick