Comment puis-je effectuer la division 64 bits avec une instruction de division 32 bits?

Question

Ceci est (AFAIK) une question spécifique dans ce général sujet .

Voici la situation:

J'ai un système embarqué (une console de jeu vidéo) basé sur un microcontrôleur RISC 32 bits (une variante du V810 NEC). Je veux écrire une bibliothèque de mathématiques à virgule fixe. J'ai lu cet article , mais le code source d'accompagnement est écrit dans l'assemblage 386, il est donc ni directement utilisables ni facilement modifiables.

Le V810 a intégré entier multiplier / diviser, mais je veux utiliser le format 18,14 mentionné dans l'article ci-dessus. Cela nécessite la division d'un int 64 bits par un int 32 bits, et le fait V810 seulement (signé ou non signé) 32 bits / division 32 bits (qui produit un quotient de 32 bits et un reste 32 bits).

Alors, ma question est: comment puis-je simuler un 64 bits / diviser 32 bits avec 32 bits / un 32 bits (pour permettre la pré-décalage du dividende)? Ou, pour regarder le problème d'une autre façon, quelle est la meilleure façon de diviser un 18,14 point fixe par un autre en utilisant des opérations arithmétique standard / logique 32 bits? ( "Meilleur" qui signifie le plus rapide, le plus petit, ou les deux).

Algèbre, (V810) ensemble, et pseudo-code sont tous très bien. Je vais demander le code de C.

Merci à l'avance!

EDIT: D'une certaine façon je manqué cette question .. . Cependant, il faudra encore besoin d'une certaine modification être super efficace (il doit être plus rapide que la div à virgule flottante fourni par le V810, mais il peut déjà être ...), alors ne hésitez pas à faire mon travail pour moi en échange de points de réputation;.) (et du crédit dans ma documentation bibliothèque, bien sûr)

Answer 1

GCC a une telle routine pour de nombreux processeurs, _divdi3 nommé (généralement mis en œuvre au moyen d'un appel divmod commun). Voici un . Certains noyaux Unix ont une mise en œuvre aussi, par exemple FreeBSD .

Answer 2

Si votre dividende est de 64 bits non signés, votre diviseur est 32 bits non signés, l'architecture est i386 (x86), l'instruction d'assemblage div peut vous aider avec une certaine préparation:

#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 ligne ci-dessus avec __udivdi3 ne compile pas pour vous, utilisez la fonction __div64_32 du noyau Linux: https://github.com/torvalds/linux/blob/master/lib/div64.c