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

Question

Esto es (AFAIK) una pregunta específica dentro de this general topic.

Esta es la situación:

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

El V810 tiene un número entero integrado/división, 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).

El ensamblaje de álgebra, (V810) y el pseudocódigo están bien. Voy a llamar al código de C.

¡Gracias de antemano!

EDITAR: de alguna manera me perdí this question ... Sin embargo, todavía necesitará algunas modificaciones para ser súper eficiente (tiene que ser más rápido que el div punto flotante proporcionado por el v810, aunque ya puede ser .. .), 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 una rutina para muchos procesadores, llamada _divdi3 (generalmente implementada usando una llamada divmod común). Here's one. Algunos kernels de Unix también tienen una implementación, p. FreeBSD.

Answer 2

Si el dividendo es sin signo de 64 bits, el divisor es sin signo de 32 bits, la arquitectura es i386 (x86), la instrucción div montaje le puede ayudar con un poco de 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 anterior con __udivdi3 no compila para usted, utilice la función __div64_32 desde el núcleo de Linux: https://github.com/torvalds/linux/blob/master/lib/div64.c