math - paso - ¿Cómo puedo realizar una división de 64 bits con una instrucción de dividir de 32 bits?

divisiones de dos cifras faciles

Question

Esta es (AFAIK) una pregunta específica dentro de este tema general .

Aquí está la situación:

Tengo un sistema integrado (una consola de videojuegos) basado en un microcontrolador RISC de 32 bits (una variante del V810 de NEC). Quiero escribir una biblioteca matemática de punto fijo. Leí este artículo , pero el código fuente que lo acompaña está escrito en ensamblaje 386, por lo que no se puede usar directamente ni modificar fácilmente.

El V810 tiene un número entero integrado / dividir, pero quiero usar el formato 18.14 mencionado en el artículo anterior. Esto requiere dividir un int de 64 bits por un int de 32 bits, y el V810 solo tiene una división de 32 bits / 32 bits (firmada o no) (que produce un cociente de 32 bits y un resto de 32 bits).

Entonces, mi pregunta es: ¿cómo simulo una división de 64 bits / 32 bits con una de 32 bits / 32 bits (para permitir el pre-cambio del dividendo)? O, para ver el problema de otra manera, ¿cuál es la mejor manera de dividir un punto fijo de 18.14 por otro usando operaciones aritméticas / lógicas estándar de 32 bits? ("mejor" significa el más rápido, el más pequeño o ambos).

Algebra, (V810) assembly y pseudo-code están bien. Voy a llamar al código de C.

¡Gracias por adelantado!

EDITAR: De alguna manera me perdí esta pregunta ... Sin embargo, todavía necesitará algunas modificaciones para ser súper eficiente (tiene que ser más rápido que el div de coma flotante proporcionado por el v810, aunque puede que ya sea ...), así que siéntete libre de hacer mi trabajo por mí a cambio de puntos de reputación;) (y crédito en la documentación de mi biblioteca, por supuesto).

Answer 1

GCC tiene esa rutina para muchos procesadores, llamada _divdi3 (generalmente implementada usando una llamada divmod común). Aquí hay uno . Algunos núcleos de Unix también tienen una implementación, por ejemplo, FreeBSD .

Answer 2

Si su dividendo no tiene firma de 64 bits, su divisor no tiene firma de 32 bits, la arquitectura es i386 (x86), la instrucción de ensamblaje div puede ayudarlo con alguna preparación:

#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
}

Si la línea de arriba con __udivdi3 no compila para usted, use la función __div64_32 del kernel de Linux: https://github.com/torvalds/linux/blob/master/lib/div64.c