171abb752SPaolo Bonzini #include <stdint.h> 20b2d3dafSPaolo Bonzini 30b2d3dafSPaolo Bonzini extern uint64_t __udivmoddi4(uint64_t num, uint64_t den, uint64_t *p_rem); 4*a8a79dacSPaolo Bonzini extern int64_t __divmoddi4(int64_t num, int64_t den, int64_t *p_rem); 50b2d3dafSPaolo Bonzini extern int64_t __moddi3(int64_t num, int64_t den); 60b2d3dafSPaolo Bonzini extern int64_t __divdi3(int64_t num, int64_t den); 70b2d3dafSPaolo Bonzini extern uint64_t __udivdi3(uint64_t num, uint64_t den); 80b2d3dafSPaolo Bonzini extern uint64_t __umoddi3(uint64_t num, uint64_t den); 90b2d3dafSPaolo Bonzini 100b2d3dafSPaolo Bonzini uint64_t __udivmoddi4(uint64_t num, uint64_t den, uint64_t *p_rem) 110b2d3dafSPaolo Bonzini { 120b2d3dafSPaolo Bonzini uint64_t quot = 0; 130b2d3dafSPaolo Bonzini 140b2d3dafSPaolo Bonzini /* Trigger a division by zero at run time (trick taken from iPXE). */ 15*a8a79dacSPaolo Bonzini if (den == 0) { 16*a8a79dacSPaolo Bonzini if (p_rem) 17*a8a79dacSPaolo Bonzini *p_rem = 0; 180b2d3dafSPaolo Bonzini return 1/((unsigned)den); 19*a8a79dacSPaolo Bonzini } 200b2d3dafSPaolo Bonzini 210b2d3dafSPaolo Bonzini if (num >= den) { 220b2d3dafSPaolo Bonzini /* Align den to num to avoid wasting time on leftmost zero bits. */ 230b2d3dafSPaolo Bonzini int n = __builtin_clzll(den) - __builtin_clzll(num); 240b2d3dafSPaolo Bonzini den <<= n; 250b2d3dafSPaolo Bonzini 260b2d3dafSPaolo Bonzini do { 270b2d3dafSPaolo Bonzini quot <<= 1; 280b2d3dafSPaolo Bonzini if (num >= den) { 290b2d3dafSPaolo Bonzini num -= den; 300b2d3dafSPaolo Bonzini quot |= 1; 310b2d3dafSPaolo Bonzini } 320b2d3dafSPaolo Bonzini den >>= 1; 330b2d3dafSPaolo Bonzini } while (n--); 340b2d3dafSPaolo Bonzini } 350b2d3dafSPaolo Bonzini 360b2d3dafSPaolo Bonzini if (p_rem) 370b2d3dafSPaolo Bonzini *p_rem = num; 380b2d3dafSPaolo Bonzini 390b2d3dafSPaolo Bonzini return quot; 400b2d3dafSPaolo Bonzini } 410b2d3dafSPaolo Bonzini 42*a8a79dacSPaolo Bonzini int64_t __divmoddi4(int64_t num, int64_t den, int64_t *p_rem) 430b2d3dafSPaolo Bonzini { 44*a8a79dacSPaolo Bonzini int32_t nmask = num < 0 ? -1 : 0; 45*a8a79dacSPaolo Bonzini int32_t qmask = (num ^ den) < 0 ? -1 : 0; 46*a8a79dacSPaolo Bonzini uint64_t quot; 470b2d3dafSPaolo Bonzini 480b2d3dafSPaolo Bonzini /* Compute absolute values and do an unsigned division. */ 49*a8a79dacSPaolo Bonzini num = (num + nmask) ^ nmask; 500b2d3dafSPaolo Bonzini if (den < 0) 510b2d3dafSPaolo Bonzini den = -den; 520b2d3dafSPaolo Bonzini 53*a8a79dacSPaolo Bonzini /* Copy sign of num^den into quotient, sign of num into remainder. */ 54*a8a79dacSPaolo Bonzini quot = (__udivmoddi4(num, den, (uint64_t *)p_rem) + qmask) ^ qmask; 55*a8a79dacSPaolo Bonzini if (p_rem) 56*a8a79dacSPaolo Bonzini *p_rem = (*p_rem + nmask) ^ nmask; 57*a8a79dacSPaolo Bonzini return quot; 58*a8a79dacSPaolo Bonzini } 59*a8a79dacSPaolo Bonzini 60*a8a79dacSPaolo Bonzini int64_t __moddi3(int64_t num, int64_t den) 61*a8a79dacSPaolo Bonzini { 62*a8a79dacSPaolo Bonzini int64_t rem; 63*a8a79dacSPaolo Bonzini __divmoddi4(num, den, &rem); 64*a8a79dacSPaolo Bonzini return rem; 650b2d3dafSPaolo Bonzini } 660b2d3dafSPaolo Bonzini 670b2d3dafSPaolo Bonzini int64_t __divdi3(int64_t num, int64_t den) 680b2d3dafSPaolo Bonzini { 69*a8a79dacSPaolo Bonzini int64_t rem; 70*a8a79dacSPaolo Bonzini return __divmoddi4(num, den, &rem); 710b2d3dafSPaolo Bonzini } 720b2d3dafSPaolo Bonzini 730b2d3dafSPaolo Bonzini uint64_t __udivdi3(uint64_t num, uint64_t den) 740b2d3dafSPaolo Bonzini { 750b2d3dafSPaolo Bonzini uint64_t rem; 760b2d3dafSPaolo Bonzini return __udivmoddi4(num, den, &rem); 770b2d3dafSPaolo Bonzini } 780b2d3dafSPaolo Bonzini 790b2d3dafSPaolo Bonzini uint64_t __umoddi3(uint64_t num, uint64_t den) 800b2d3dafSPaolo Bonzini { 810b2d3dafSPaolo Bonzini uint64_t rem; 820b2d3dafSPaolo Bonzini __udivmoddi4(num, den, &rem); 830b2d3dafSPaolo Bonzini return rem; 840b2d3dafSPaolo Bonzini } 850b2d3dafSPaolo Bonzini 860b2d3dafSPaolo Bonzini #ifdef TEST 870b2d3dafSPaolo Bonzini #include <assert.h> 880b2d3dafSPaolo Bonzini #define UTEST(a, b, q, r) assert(__udivdi3(a, b) == q && __umoddi3(a, b) == r) 890b2d3dafSPaolo Bonzini #define STEST(a, b, q, r) assert(__divdi3(a, b) == q && __moddi3(a, b) == r) 900b2d3dafSPaolo Bonzini int main() 910b2d3dafSPaolo Bonzini { 920b2d3dafSPaolo Bonzini UTEST(1, 1, 1, 0); 930b2d3dafSPaolo Bonzini UTEST(2, 2, 1, 0); 940b2d3dafSPaolo Bonzini UTEST(5, 3, 1, 2); 950b2d3dafSPaolo Bonzini UTEST(10, 3, 3, 1); 960b2d3dafSPaolo Bonzini UTEST(120, 3, 40, 0); 970b2d3dafSPaolo Bonzini UTEST(120, 1, 120, 0); 980b2d3dafSPaolo Bonzini UTEST(0x7FFFFFFFFFFFFFFFULL, 17, 0x787878787878787, 8); 990b2d3dafSPaolo Bonzini UTEST(0x7FFFFFFFFFFFFFFFULL, 0x787878787878787, 17, 8); 1000b2d3dafSPaolo Bonzini UTEST(0x8000000000000001ULL, 17, 0x787878787878787, 10); 1010b2d3dafSPaolo Bonzini UTEST(0x8000000000000001ULL, 0x787878787878787, 17, 10); 1020b2d3dafSPaolo Bonzini UTEST(0, 5, 0, 0); 1030b2d3dafSPaolo Bonzini 1040b2d3dafSPaolo Bonzini STEST(0x7FFFFFFFFFFFFFFFULL, 17, 0x787878787878787, 8); 1050b2d3dafSPaolo Bonzini STEST(0x7FFFFFFFFFFFFFFFULL, -17, -0x787878787878787, 8); 1060b2d3dafSPaolo Bonzini STEST(-0x7FFFFFFFFFFFFFFFULL, 17, -0x787878787878787, -8); 1070b2d3dafSPaolo Bonzini STEST(-0x7FFFFFFFFFFFFFFFULL, -17, 0x787878787878787, -8); 1080b2d3dafSPaolo Bonzini STEST(33, 5, 6, 3); 1090b2d3dafSPaolo Bonzini STEST(33, -5, -6, 3); 1100b2d3dafSPaolo Bonzini STEST(-33, 5, -6, -3); 1110b2d3dafSPaolo Bonzini STEST(-33, -5, 6, -3); 1120b2d3dafSPaolo Bonzini } 1130b2d3dafSPaolo Bonzini #endif 114