Wie kann ich eine 64-Bit-Division mit einer 32-Bit-Divisionsanweisung durchführen?

Question

Dies ist (AFAIK) eine spezifische Frage innerhalb this general topic.

Hier ist die Situation:

Ich habe ein Embedded-System (eine Videospielkonsole), basierend auf einem 32-Bit-RISC-Mikrocontroller (eine Variante von NEC V810). Ich möchte eine Festkomma-Mathematikbibliothek schreiben. Ich lese this article, aber der begleitende Quellcode ist in 386 Assembly geschrieben, so dass es weder direkt verwendbar noch leicht modifizierbar ist.

Der V810 hat eingebaute Ganzzahl Multiplizieren/Dividieren, aber ich möchte das 18.14 Format verwenden, das im obigen Artikel erwähnt wird. Dies erfordert das Unterteilen eines 64-Bit-Int durch einen 32-Bit-Int, und der V810 macht nur (32-Bit/32-Bit-Division mit Vorzeichen oder Vorzeichen) (was einen 32-Bit-Quotienten und einen 32-Bit-Rest erzeugt).

Also meine Frage ist: Wie simuliere ich eine 64-Bit/32-Bit-Division mit einer 32-Bit/32-Bit-Division (um die Vorverschiebung der Dividende zu ermöglichen)? Oder, um das Problem von einem anderen Weg aus zu betrachten, was ist der beste Weg, um einen 18,14-Fixpunkt durch einen anderen unter Verwendung von 32-Bit-Arithmetik/Logik-Standardoperationen zu teilen? ("am besten" bedeutet am schnellsten, am kleinsten oder an beiden).

Algebra, (V810) Assembly und Pseudo-Code sind alle in Ordnung. Ich werde den Code von C anrufen.

Vielen Dank im Voraus!

EDIT: Irgendwie habe ich verpasst this question ... Allerdings wird es noch einige Änderungen benötigen, um super-effizient zu sein (es muss schneller sein als das Floating-Point div von der v810 zur Verfügung gestellt, obwohl es bereits sein kann .. .), also fühlen Sie sich frei, meine Arbeit für mich im Austausch für Reputationspunkte zu machen;) (und Kredit in meiner Bibliotheksdokumentation natürlich).

Answer 1

GCC hat eine solche Routine für viele Prozessoren namens _divdi3 (normalerweise unter Verwendung eines gemeinsamen divmod-Aufrufs implementiert). Here's one. Einige Unix-Kernel haben auch eine Implementierung, z. FreeBSD.

Answer 2

Wenn Ihre Dividende ist unsigned 64 Bits, Ihre Teiler 32 Bits ohne Vorzeichen sind, ist die Architektur i386 (x86), die div Montageanleitung Ihnen mit etwas 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 Zeile oben mit __udivdi3 kompiliert nicht für Sie, verwenden Sie die __div64_32-Funktion aus dem Linux-Kernel: https://github.com/torvalds/linux/blob/master/lib/div64.c