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