Wie kann ich eine 64-Bit-Division mit einem 32-Bit-Divisionsbefehl durchführen?

Question

Dies ist (AFAIK) eine spezifische Frage innerhalb dieses allgemeine Thema .

Die Situation ist wie folgt:

Ich habe ein eingebettetes System (eine Videospielkonsole), das auf einem 32-Bit-RISC-Mikrocontroller (einer Variante des V810 von NEC) basiert. Ich möchte eine Bibliothek für Festkomma-Mathematik schreiben. Ich lese dieser Artikel , aber der zugehörige Quellcode ist in 386-Assembler geschrieben, so dass er weder direkt verwendbar noch leicht veränderbar ist.

Der V810 hat eine eingebaute Integer-Multiplikations-/Divisionsfunktion, aber ich möchte das im obigen Artikel erwähnte 18.14-Format verwenden. Dazu muss ein 64-Bit-Int durch einen 32-Bit-Int geteilt werden, und der V810 kann nur (vorzeichenbehaftete oder vorzeichenlose) 32-Bit/32-Bit-Divisionen durchführen (was einen 32-Bit-Quotienten und einen 32-Bit-Rest ergibt).

Meine Frage ist also: Wie simuliere ich eine 64-Bit/32-Bit-Division mit einer 32-Bit/32-Bit-Division (um die Vorverschiebung des Dividenden zu ermöglichen)? Oder, um das Problem aus einem anderen Blickwinkel zu betrachten: Wie kann ich eine Festkommazahl von 18,14 am besten durch eine andere dividieren, indem ich standardmäßige 32-Bit-Arithmetik/Logikoperationen verwende? ("am besten" bedeutet am schnellsten, am kleinsten oder beides).

Algebra, (V810) Assembler und Pseudocode sind alle in Ordnung. Ich werde den Code von C aus aufrufen.

Vielen Dank im Voraus!

EDIT: Irgendwie habe ich etwas übersehen diese Frage ... Allerdings wird es noch einige Modifikationen benötigen, um super-effizient zu sein (es muss schneller sein als die Gleitkomma-Div des v810, obwohl es das vielleicht schon ist...), also zögern Sie nicht, meine Arbeit für mich im Austausch für Reputationspunkte zu tun ;) (und natürlich die Erwähnung in meiner Bibliotheksdokumentation).

Answer 1

GCC verfügt für viele Prozessoren über eine solche Routine mit dem Namen _divdi3 (die normalerweise mit einem gewöhnlichen divmod-Aufruf implementiert wird). Hier ist eine . Einige Unix-Kernel haben ebenfalls eine Implementierung, z. B. FreeBSD .

Answer 2

Wenn Ihr Dividend 64 Bit ohne Vorzeichen ist, Ihr Divisor 32 Bit ohne Vorzeichen ist, die Architektur i386 (x86) ist, ist die div Die Montageanleitung kann Ihnen bei der Vorbereitung helfen:

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

Wenn die obige Zeile mit __udivdi3 nicht kompiliert werden kann, verwenden Sie die __div64_32 Funktion aus dem Linux-Kernel: https://github.com/torvalds/linux/blob/master/lib/div64.c