如何使用 32 位除法指令执行 64 位除法？

Question

这是（AFAIK）这个一般主题。

情况是这样的：

我有一个基于 32 位 RISC 微控制器（NEC V810 的变体）的嵌入式系统（视频游戏控制台）。我想写一个定点数学库。我读了这篇文章，但是附带的源代码是用386汇编编写的，所以它是既不能直接使用，也不能轻易修改。

V810内置了整数乘法/除法，但我想使用上面文章中提到的18.14格式。这需要将 64 位 int 除以 32 位 int，而 V810 仅执行（有符号或无符号）32 位/32 位除法（产生 32 位商和 32 位余数）。

所以，我的问题是：如何用 32 位/32 位除法模拟 64 位/32 位除法（以允许被除数的预移位）？或者，从另一个角度看问题，使用标准 32 位算术/逻辑运算将 18.14 定点除以另一个定点的最佳方法是什么？ （“最佳”意味着最快、最小或两者兼而有之）。

代数、（V810）汇编和伪代码都可以。我将从 C 调用代码。

提前致谢！

编辑：不知何故，我错过了这个问题...但是，它仍然需要一些修改才能变得超级高效（它必须比 v810 提供的浮点 div 更快，尽管它可能已经是......），所以请随意为我做我的工作，以换取声誉点；）（当然，还有我的图书馆文档中的信用点）。

Answer 1

GCC 为许多处理器提供了这样的例程，名为 _divdi3（通常使用通用的 divmod 调用来实现）。 这是一个。一些 Unix 内核也有一个实现，例如 FreeBSD。

Answer 2

如果您的被除数是无符号 64 位，除数是无符号 32 位，架构是 i386 (x86)，则 div 汇编指令可以帮助您进行一些准备：

#include <stdint.h>
/* Returns *a % b, and sets *a = *a_old / b; */
uint32_t UInt64DivAndGetMod(uint64_t *a, uint32_t b) {
#ifdef __i386__  /* u64 / u32 division with little i386 machine code. */
  uint32_t upper = ((uint32_t*)a)[1], r;
  ((uint32_t*)a)[1] = 0;
  if (upper >= b) {   
    ((uint32_t*)a)[1] = upper / b;
    upper %= b;
  }
  __asm__("divl %2" : "=a" (((uint32_t*)a)[0]), "=d" (r) :
      "rm" (b), "0" (((uint32_t*)a)[0]), "1" (upper));
  return r;
#else
  const uint64_t q = *a / b;  /* Calls __udivdi3 in libgcc. */
  const uint32_t r = *a - b * q;  /* `r = *a % b' would use __umoddi3. */
  *a = q;
  return r;
#endif
}

如果上面的行带有 __udivdi3 无法为您编译，请使用 Linux 内核中的 __div64_32 函数：https://github.com/torvalds/linux/blob/master/lib/div64.c