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
__clzsi2(uint32_t num)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
__clzdi2(uint64_t num)25 int __clzdi2(uint64_t num)
26 {
27 return num >> 32 ? __clzsi2(num >> 32) : __clzsi2(num) + 32;
28 }
29 #endif
30
__udivmoddi4(uint64_t num,uint64_t den,uint64_t * p_rem)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
__divmoddi4(int64_t num,int64_t den,int64_t * p_rem)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
__moddi3(int64_t num,int64_t den)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
__divdi3(int64_t num,int64_t den)88 int64_t __divdi3(int64_t num, int64_t den)
89 {
90 int64_t rem;
91 return __divmoddi4(num, den, &rem);
92 }
93
__udivdi3(uint64_t num,uint64_t den)94 uint64_t __udivdi3(uint64_t num, uint64_t den)
95 {
96 uint64_t rem;
97 return __udivmoddi4(num, den, &rem);
98 }
99
__umoddi3(uint64_t num,uint64_t den)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)
main()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