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