1*71abb752SPaolo Bonzini #include <stdint.h> 20b2d3dafSPaolo Bonzini 30b2d3dafSPaolo Bonzini extern uint64_t __udivmoddi4(uint64_t num, uint64_t den, uint64_t *p_rem); 40b2d3dafSPaolo Bonzini extern int64_t __moddi3(int64_t num, int64_t den); 50b2d3dafSPaolo Bonzini extern int64_t __divdi3(int64_t num, int64_t den); 60b2d3dafSPaolo Bonzini extern uint64_t __udivdi3(uint64_t num, uint64_t den); 70b2d3dafSPaolo Bonzini extern uint64_t __umoddi3(uint64_t num, uint64_t den); 80b2d3dafSPaolo Bonzini 90b2d3dafSPaolo Bonzini uint64_t __udivmoddi4(uint64_t num, uint64_t den, uint64_t *p_rem) 100b2d3dafSPaolo Bonzini { 110b2d3dafSPaolo Bonzini uint64_t quot = 0; 120b2d3dafSPaolo Bonzini 130b2d3dafSPaolo Bonzini /* Trigger a division by zero at run time (trick taken from iPXE). */ 140b2d3dafSPaolo Bonzini if (den == 0) 150b2d3dafSPaolo Bonzini return 1/((unsigned)den); 160b2d3dafSPaolo Bonzini 170b2d3dafSPaolo Bonzini if (num >= den) { 180b2d3dafSPaolo Bonzini /* Align den to num to avoid wasting time on leftmost zero bits. */ 190b2d3dafSPaolo Bonzini int n = __builtin_clzll(den) - __builtin_clzll(num); 200b2d3dafSPaolo Bonzini den <<= n; 210b2d3dafSPaolo Bonzini 220b2d3dafSPaolo Bonzini do { 230b2d3dafSPaolo Bonzini quot <<= 1; 240b2d3dafSPaolo Bonzini if (num >= den) { 250b2d3dafSPaolo Bonzini num -= den; 260b2d3dafSPaolo Bonzini quot |= 1; 270b2d3dafSPaolo Bonzini } 280b2d3dafSPaolo Bonzini den >>= 1; 290b2d3dafSPaolo Bonzini } while (n--); 300b2d3dafSPaolo Bonzini } 310b2d3dafSPaolo Bonzini 320b2d3dafSPaolo Bonzini if (p_rem) 330b2d3dafSPaolo Bonzini *p_rem = num; 340b2d3dafSPaolo Bonzini 350b2d3dafSPaolo Bonzini return quot; 360b2d3dafSPaolo Bonzini } 370b2d3dafSPaolo Bonzini 380b2d3dafSPaolo Bonzini int64_t __moddi3(int64_t num, int64_t den) 390b2d3dafSPaolo Bonzini { 400b2d3dafSPaolo Bonzini uint64_t mask = num < 0 ? -1 : 0; 410b2d3dafSPaolo Bonzini 420b2d3dafSPaolo Bonzini /* Compute absolute values and do an unsigned division. */ 430b2d3dafSPaolo Bonzini num = (num + mask) ^ mask; 440b2d3dafSPaolo Bonzini if (den < 0) 450b2d3dafSPaolo Bonzini den = -den; 460b2d3dafSPaolo Bonzini 470b2d3dafSPaolo Bonzini /* Copy sign of num into result. */ 480b2d3dafSPaolo Bonzini return (__umoddi3(num, den) + mask) ^ mask; 490b2d3dafSPaolo Bonzini } 500b2d3dafSPaolo Bonzini 510b2d3dafSPaolo Bonzini int64_t __divdi3(int64_t num, int64_t den) 520b2d3dafSPaolo Bonzini { 530b2d3dafSPaolo Bonzini uint64_t mask = (num ^ den) < 0 ? -1 : 0; 540b2d3dafSPaolo Bonzini 550b2d3dafSPaolo Bonzini /* Compute absolute values and do an unsigned division. */ 560b2d3dafSPaolo Bonzini if (num < 0) 570b2d3dafSPaolo Bonzini num = -num; 580b2d3dafSPaolo Bonzini if (den < 0) 590b2d3dafSPaolo Bonzini den = -den; 600b2d3dafSPaolo Bonzini 610b2d3dafSPaolo Bonzini /* Copy sign of num^den into result. */ 620b2d3dafSPaolo Bonzini return (__udivdi3(num, den) + mask) ^ mask; 630b2d3dafSPaolo Bonzini } 640b2d3dafSPaolo Bonzini 650b2d3dafSPaolo Bonzini uint64_t __udivdi3(uint64_t num, uint64_t den) 660b2d3dafSPaolo Bonzini { 670b2d3dafSPaolo Bonzini uint64_t rem; 680b2d3dafSPaolo Bonzini return __udivmoddi4(num, den, &rem); 690b2d3dafSPaolo Bonzini } 700b2d3dafSPaolo Bonzini 710b2d3dafSPaolo Bonzini uint64_t __umoddi3(uint64_t num, uint64_t den) 720b2d3dafSPaolo Bonzini { 730b2d3dafSPaolo Bonzini uint64_t rem; 740b2d3dafSPaolo Bonzini __udivmoddi4(num, den, &rem); 750b2d3dafSPaolo Bonzini return rem; 760b2d3dafSPaolo Bonzini } 770b2d3dafSPaolo Bonzini 780b2d3dafSPaolo Bonzini #ifdef TEST 790b2d3dafSPaolo Bonzini #include <assert.h> 800b2d3dafSPaolo Bonzini #define UTEST(a, b, q, r) assert(__udivdi3(a, b) == q && __umoddi3(a, b) == r) 810b2d3dafSPaolo Bonzini #define STEST(a, b, q, r) assert(__divdi3(a, b) == q && __moddi3(a, b) == r) 820b2d3dafSPaolo Bonzini int main() 830b2d3dafSPaolo Bonzini { 840b2d3dafSPaolo Bonzini UTEST(1, 1, 1, 0); 850b2d3dafSPaolo Bonzini UTEST(2, 2, 1, 0); 860b2d3dafSPaolo Bonzini UTEST(5, 3, 1, 2); 870b2d3dafSPaolo Bonzini UTEST(10, 3, 3, 1); 880b2d3dafSPaolo Bonzini UTEST(120, 3, 40, 0); 890b2d3dafSPaolo Bonzini UTEST(120, 1, 120, 0); 900b2d3dafSPaolo Bonzini UTEST(0x7FFFFFFFFFFFFFFFULL, 17, 0x787878787878787, 8); 910b2d3dafSPaolo Bonzini UTEST(0x7FFFFFFFFFFFFFFFULL, 0x787878787878787, 17, 8); 920b2d3dafSPaolo Bonzini UTEST(0x8000000000000001ULL, 17, 0x787878787878787, 10); 930b2d3dafSPaolo Bonzini UTEST(0x8000000000000001ULL, 0x787878787878787, 17, 10); 940b2d3dafSPaolo Bonzini UTEST(0, 5, 0, 0); 950b2d3dafSPaolo Bonzini 960b2d3dafSPaolo Bonzini STEST(0x7FFFFFFFFFFFFFFFULL, 17, 0x787878787878787, 8); 970b2d3dafSPaolo Bonzini STEST(0x7FFFFFFFFFFFFFFFULL, -17, -0x787878787878787, 8); 980b2d3dafSPaolo Bonzini STEST(-0x7FFFFFFFFFFFFFFFULL, 17, -0x787878787878787, -8); 990b2d3dafSPaolo Bonzini STEST(-0x7FFFFFFFFFFFFFFFULL, -17, 0x787878787878787, -8); 1000b2d3dafSPaolo Bonzini STEST(33, 5, 6, 3); 1010b2d3dafSPaolo Bonzini STEST(33, -5, -6, 3); 1020b2d3dafSPaolo Bonzini STEST(-33, 5, -6, -3); 1030b2d3dafSPaolo Bonzini STEST(-33, -5, 6, -3); 1040b2d3dafSPaolo Bonzini } 1050b2d3dafSPaolo Bonzini #endif 106