1*0b2d3dafSPaolo Bonzini #include <inttypes.h> 2*0b2d3dafSPaolo Bonzini 3*0b2d3dafSPaolo Bonzini extern uint64_t __udivmoddi4(uint64_t num, uint64_t den, uint64_t *p_rem); 4*0b2d3dafSPaolo Bonzini extern int64_t __moddi3(int64_t num, int64_t den); 5*0b2d3dafSPaolo Bonzini extern int64_t __divdi3(int64_t num, int64_t den); 6*0b2d3dafSPaolo Bonzini extern uint64_t __udivdi3(uint64_t num, uint64_t den); 7*0b2d3dafSPaolo Bonzini extern uint64_t __umoddi3(uint64_t num, uint64_t den); 8*0b2d3dafSPaolo Bonzini 9*0b2d3dafSPaolo Bonzini uint64_t __udivmoddi4(uint64_t num, uint64_t den, uint64_t *p_rem) 10*0b2d3dafSPaolo Bonzini { 11*0b2d3dafSPaolo Bonzini uint64_t quot = 0; 12*0b2d3dafSPaolo Bonzini 13*0b2d3dafSPaolo Bonzini /* Trigger a division by zero at run time (trick taken from iPXE). */ 14*0b2d3dafSPaolo Bonzini if (den == 0) 15*0b2d3dafSPaolo Bonzini return 1/((unsigned)den); 16*0b2d3dafSPaolo Bonzini 17*0b2d3dafSPaolo Bonzini if (num >= den) { 18*0b2d3dafSPaolo Bonzini /* Align den to num to avoid wasting time on leftmost zero bits. */ 19*0b2d3dafSPaolo Bonzini int n = __builtin_clzll(den) - __builtin_clzll(num); 20*0b2d3dafSPaolo Bonzini den <<= n; 21*0b2d3dafSPaolo Bonzini 22*0b2d3dafSPaolo Bonzini do { 23*0b2d3dafSPaolo Bonzini quot <<= 1; 24*0b2d3dafSPaolo Bonzini if (num >= den) { 25*0b2d3dafSPaolo Bonzini num -= den; 26*0b2d3dafSPaolo Bonzini quot |= 1; 27*0b2d3dafSPaolo Bonzini } 28*0b2d3dafSPaolo Bonzini den >>= 1; 29*0b2d3dafSPaolo Bonzini } while (n--); 30*0b2d3dafSPaolo Bonzini } 31*0b2d3dafSPaolo Bonzini 32*0b2d3dafSPaolo Bonzini if (p_rem) 33*0b2d3dafSPaolo Bonzini *p_rem = num; 34*0b2d3dafSPaolo Bonzini 35*0b2d3dafSPaolo Bonzini return quot; 36*0b2d3dafSPaolo Bonzini } 37*0b2d3dafSPaolo Bonzini 38*0b2d3dafSPaolo Bonzini int64_t __moddi3(int64_t num, int64_t den) 39*0b2d3dafSPaolo Bonzini { 40*0b2d3dafSPaolo Bonzini uint64_t mask = num < 0 ? -1 : 0; 41*0b2d3dafSPaolo Bonzini 42*0b2d3dafSPaolo Bonzini /* Compute absolute values and do an unsigned division. */ 43*0b2d3dafSPaolo Bonzini num = (num + mask) ^ mask; 44*0b2d3dafSPaolo Bonzini if (den < 0) 45*0b2d3dafSPaolo Bonzini den = -den; 46*0b2d3dafSPaolo Bonzini 47*0b2d3dafSPaolo Bonzini /* Copy sign of num into result. */ 48*0b2d3dafSPaolo Bonzini return (__umoddi3(num, den) + mask) ^ mask; 49*0b2d3dafSPaolo Bonzini } 50*0b2d3dafSPaolo Bonzini 51*0b2d3dafSPaolo Bonzini int64_t __divdi3(int64_t num, int64_t den) 52*0b2d3dafSPaolo Bonzini { 53*0b2d3dafSPaolo Bonzini uint64_t mask = (num ^ den) < 0 ? -1 : 0; 54*0b2d3dafSPaolo Bonzini 55*0b2d3dafSPaolo Bonzini /* Compute absolute values and do an unsigned division. */ 56*0b2d3dafSPaolo Bonzini if (num < 0) 57*0b2d3dafSPaolo Bonzini num = -num; 58*0b2d3dafSPaolo Bonzini if (den < 0) 59*0b2d3dafSPaolo Bonzini den = -den; 60*0b2d3dafSPaolo Bonzini 61*0b2d3dafSPaolo Bonzini /* Copy sign of num^den into result. */ 62*0b2d3dafSPaolo Bonzini return (__udivdi3(num, den) + mask) ^ mask; 63*0b2d3dafSPaolo Bonzini } 64*0b2d3dafSPaolo Bonzini 65*0b2d3dafSPaolo Bonzini uint64_t __udivdi3(uint64_t num, uint64_t den) 66*0b2d3dafSPaolo Bonzini { 67*0b2d3dafSPaolo Bonzini uint64_t rem; 68*0b2d3dafSPaolo Bonzini return __udivmoddi4(num, den, &rem); 69*0b2d3dafSPaolo Bonzini } 70*0b2d3dafSPaolo Bonzini 71*0b2d3dafSPaolo Bonzini uint64_t __umoddi3(uint64_t num, uint64_t den) 72*0b2d3dafSPaolo Bonzini { 73*0b2d3dafSPaolo Bonzini uint64_t rem; 74*0b2d3dafSPaolo Bonzini __udivmoddi4(num, den, &rem); 75*0b2d3dafSPaolo Bonzini return rem; 76*0b2d3dafSPaolo Bonzini } 77*0b2d3dafSPaolo Bonzini 78*0b2d3dafSPaolo Bonzini #ifdef TEST 79*0b2d3dafSPaolo Bonzini #include <assert.h> 80*0b2d3dafSPaolo Bonzini #define UTEST(a, b, q, r) assert(__udivdi3(a, b) == q && __umoddi3(a, b) == r) 81*0b2d3dafSPaolo Bonzini #define STEST(a, b, q, r) assert(__divdi3(a, b) == q && __moddi3(a, b) == r) 82*0b2d3dafSPaolo Bonzini int main() 83*0b2d3dafSPaolo Bonzini { 84*0b2d3dafSPaolo Bonzini UTEST(1, 1, 1, 0); 85*0b2d3dafSPaolo Bonzini UTEST(2, 2, 1, 0); 86*0b2d3dafSPaolo Bonzini UTEST(5, 3, 1, 2); 87*0b2d3dafSPaolo Bonzini UTEST(10, 3, 3, 1); 88*0b2d3dafSPaolo Bonzini UTEST(120, 3, 40, 0); 89*0b2d3dafSPaolo Bonzini UTEST(120, 1, 120, 0); 90*0b2d3dafSPaolo Bonzini UTEST(0x7FFFFFFFFFFFFFFFULL, 17, 0x787878787878787, 8); 91*0b2d3dafSPaolo Bonzini UTEST(0x7FFFFFFFFFFFFFFFULL, 0x787878787878787, 17, 8); 92*0b2d3dafSPaolo Bonzini UTEST(0x8000000000000001ULL, 17, 0x787878787878787, 10); 93*0b2d3dafSPaolo Bonzini UTEST(0x8000000000000001ULL, 0x787878787878787, 17, 10); 94*0b2d3dafSPaolo Bonzini UTEST(0, 5, 0, 0); 95*0b2d3dafSPaolo Bonzini 96*0b2d3dafSPaolo Bonzini STEST(0x7FFFFFFFFFFFFFFFULL, 17, 0x787878787878787, 8); 97*0b2d3dafSPaolo Bonzini STEST(0x7FFFFFFFFFFFFFFFULL, -17, -0x787878787878787, 8); 98*0b2d3dafSPaolo Bonzini STEST(-0x7FFFFFFFFFFFFFFFULL, 17, -0x787878787878787, -8); 99*0b2d3dafSPaolo Bonzini STEST(-0x7FFFFFFFFFFFFFFFULL, -17, 0x787878787878787, -8); 100*0b2d3dafSPaolo Bonzini STEST(33, 5, 6, 3); 101*0b2d3dafSPaolo Bonzini STEST(33, -5, -6, 3); 102*0b2d3dafSPaolo Bonzini STEST(-33, 5, -6, -3); 103*0b2d3dafSPaolo Bonzini STEST(-33, -5, 6, -3); 104*0b2d3dafSPaolo Bonzini } 105*0b2d3dafSPaolo Bonzini #endif 106