Jak mogę wykonać podział 64-bitowy za pomocą 32-bitowej instrukcji dzielenia?

Question

To jest (AFAIK) konkretne pytanie w ciągu this general topic.

Oto sytuacja:

mam wbudowany system (konsola do gier wideo) w oparciu o 32-bitowy mikrokontroler RISC (wariant NEC V810). Chcę napisać bibliotekę matematyki o ustalonym punkcie. Przeczytałem this article, ale towarzyszący mu kod źródłowy jest zapisany w 386 zestawie, więc nie można go bezpośrednio używać ani łatwo modyfikować.

Urządzenie V810 ma wbudowaną liczbę całkowitą/dzielenie, ale chcę użyć formatu 18.14 wymienionego w powyższym artykule. Wymaga to podzielenia 64-bitowego int przez 32-bitowy int, a V810 wykonuje tylko (podpisany lub niepodpisany) podział 32-bitowy/32-bitowy (który wytwarza 32-bitowy iloraz i 32-bitową resztę).

Moje pytanie brzmi: w jaki sposób mogę zasymulować 64-bitowy/32-bitowy podział na 32-bitowy/32-bitowy (aby umożliwić wcześniejsze przesunięcie dywidendy)? Lub, aby spojrzeć na problem z innej strony, jaki jest najlepszy sposób na podzielenie stałego punktu 18.14 przez inny za pomocą standardowych 32-bitowych operacji arytmetyczno-logicznych? ("najlepszy" oznacza najszybszy, najmniejszy lub oba).

Algebra, (V810) montaż i pseudokodowanie są w porządku. Będę dzwonił do kodu z C.

Z góry dziękuję!

EDYCJA: Jakoś mi brakowało this question ... Jednak nadal będzie potrzebował jakiejś modyfikacji, aby być super wydajnym (musi być szybszy niż div zmiennoprzecinkowy dostarczony przez v810, chociaż może już być .. .), więc zapraszam do wykonania mojej pracy za mnie w zamian za punkty reputacji;) (i oczywiście w mojej bibliotece).

Answer 1

GCC ma taką procedurę dla wielu procesorów, nazwaną _divdi3 (zwykle implementowaną za pomocą wspólnego wywołania divmod). Here's one. Niektóre jądra Uniksa również mają implementację, np. FreeBSD.

Answer 2

Jeśli dywidenda jest niepodpisane 64 bity, Twój dzielnik jest niepodpisane 32 bity, architektura jest i386 (x86), instrukcja div zespół może pomóc w niektórych preparatu:

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

Jeśli linia powyżej __udivdi3 nie kompiluje się dla ciebie, użyj funkcji __div64_32 z jądra Linux: https://github.com/torvalds/linux/blob/master/lib/div64.c