1#include <compiler/intrinsic.h>
2#include <console/panic.h>
3#include <types/types.h>
4
5#pragma GCC diagnostic ignored "-Wmissing-prototypes"
6
7typedef union {
8 uint128_t all;
9 struct {
10 uint64_t lo;
11 uint64_t hi;
12 } s;
13} u128_parts;
14
15static inline void mul64_wide(uint64_t a, uint64_t b, uint64_t *hi,
16 uint64_t *lo) {
17 uint64_t a_lo = (uint32_t) a, a_hi = a >> 32;
18 uint64_t b_lo = (uint32_t) b, b_hi = b >> 32;
19
20 uint64_t p0 = a_lo * b_lo;
21 uint64_t p1 = a_lo * b_hi;
22 uint64_t p2 = a_hi * b_lo;
23 uint64_t p3 = a_hi * b_hi;
24
25 uint64_t mid = (p0 >> 32) + (uint32_t) p1 + (uint32_t) p2;
26
27 *lo = (p0 & 0xFFFFFFFFULL) | (mid << 32);
28 *hi = p3 + (p1 >> 32) + (p2 >> 32) + (mid >> 32);
29}
30
31static inline int popcount64(uint64_t x) {
32 x = x - ((x >> 1) & 0x5555555555555555ULL);
33 x = (x & 0x3333333333333333ULL) + ((x >> 2) & 0x3333333333333333ULL);
34 x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
35 return (int) ((x * 0x0101010101010101ULL) >> 56);
36}
37
38uint128_t __ashlti3(uint128_t a, int b) {
39 u128_parts in = {.all = a}, out;
40
41 if (b == 0)
42 return a;
43
44 if (b >= 64) {
45 out.s.lo = 0;
46 out.s.hi = in.s.lo << (b - 64);
47 } else {
48 out.s.lo = in.s.lo << b;
49 out.s.hi = (in.s.hi << b) | (in.s.lo >> (64 - b));
50 }
51 return out.all;
52}
53
54uint128_t __lshrti3(uint128_t a, int b) {
55 u128_parts in = {.all = a}, out;
56
57 if (b == 0)
58 return a;
59
60 if (b >= 64) {
61 out.s.hi = 0;
62 out.s.lo = in.s.hi >> (b - 64);
63 } else {
64 out.s.hi = in.s.hi >> b;
65 out.s.lo = (in.s.lo >> b) | (in.s.hi << (64 - b));
66 }
67 return out.all;
68}
69
70int128_t __ashrti3(int128_t a, int b) {
71 u128_parts in = {.all = (uint128_t) a}, out;
72 uint64_t fill = (uint64_t) ((int64_t) in.s.hi >> 63);
73
74 if (b == 0)
75 return a;
76
77 if (b >= 64) {
78 out.s.hi = fill;
79 out.s.lo = (uint64_t) ((int64_t) in.s.hi >> (b - 64));
80 } else {
81 out.s.lo = (in.s.lo >> b) | (in.s.hi << (64 - b));
82 out.s.hi = (uint64_t) ((int64_t) in.s.hi >> b);
83 }
84 return (int128_t) out.all;
85}
86
87int128_t __negti2(int128_t a) {
88 u128_parts in = {.all = (uint128_t) a}, out;
89 out.s.lo = ~in.s.lo + 1;
90 out.s.hi = ~in.s.hi + (out.s.lo == 0 ? 1 : 0);
91 return (int128_t) out.all;
92}
93
94int128_t __multi3(int128_t a, int128_t b) {
95 u128_parts ap = {.all = (uint128_t) a}, bp = {.all = (uint128_t) b}, r;
96 uint64_t hi, lo;
97
98 mul64_wide(a: ap.s.lo, b: bp.s.lo, hi: &hi, lo: &lo);
99 r.s.lo = lo;
100 r.s.hi = hi + ap.s.lo * bp.s.hi + ap.s.hi * bp.s.lo;
101 return (int128_t) r.all;
102}
103
104uint128_t __udivmodti4(uint128_t n, uint128_t d, uint128_t *rem) {
105 u128_parts np = {.all = n}, dp = {.all = d};
106
107 if (d == 0)
108 panic("__udivmodti4: 128-bit divide by zero");
109
110 if (np.s.hi == 0 && dp.s.hi == 0) {
111 if (rem)
112 *rem = np.s.lo % dp.s.lo;
113 return np.s.lo / dp.s.lo;
114 }
115
116 if (n < d) {
117 if (rem)
118 *rem = n;
119 return 0;
120 }
121
122 uint128_t q = 0, r = 0;
123 int msb =
124 (np.s.hi != 0) ? (127 - ci_clzll(np.s.hi)) : (63 - ci_clzll(np.s.lo));
125
126 for (int i = msb; i >= 0; i--) {
127 r = (r << 1) | ((n >> i) & 1);
128 if (r >= d) {
129 r -= d;
130 q |= (uint128_t) 1 << i;
131 }
132 }
133
134 if (rem)
135 *rem = r;
136 return q;
137}
138
139uint128_t __udivti3(uint128_t a, uint128_t b) {
140 return __udivmodti4(n: a, d: b, rem: (uint128_t *) 0);
141}
142
143uint128_t __umodti3(uint128_t a, uint128_t b) {
144 uint128_t r;
145 __udivmodti4(n: a, d: b, rem: &r);
146 return r;
147}
148
149int128_t __divmodti4(int128_t a, int128_t b, int128_t *rem) {
150 int neg_q = (a < 0) ^ (b < 0);
151 int neg_r = (a < 0);
152 uint128_t ua = (a < 0) ? -(uint128_t) a : (uint128_t) a;
153 uint128_t ub = (b < 0) ? -(uint128_t) b : (uint128_t) b;
154 uint128_t ur;
155 uint128_t uq = __udivmodti4(n: ua, d: ub, rem: &ur);
156
157 if (rem)
158 *rem = neg_r ? -(int128_t) ur : (int128_t) ur;
159
160 return neg_q ? -(int128_t) uq : (int128_t) uq;
161}
162
163int128_t __divti3(int128_t a, int128_t b) {
164 return __divmodti4(a, b, rem: (int128_t *) 0);
165}
166
167int128_t __modti3(int128_t a, int128_t b) {
168 int128_t r;
169 __divmodti4(a, b, rem: &r);
170 return r;
171}
172
173int __cmpti2(int128_t a, int128_t b) {
174 if (a < b)
175 return 0;
176 if (a == b)
177 return 1;
178 return 2;
179}
180
181int __ucmpti2(uint128_t a, uint128_t b) {
182 if (a < b)
183 return 0;
184 if (a == b)
185 return 1;
186 return 2;
187}
188
189int __clzti2(uint128_t a) {
190 u128_parts p = {.all = a};
191 if (p.s.hi)
192 return ci_clzll(p.s.hi);
193 return 64 + ci_clzll(p.s.lo);
194}
195
196int __ctzti2(uint128_t a) {
197 u128_parts p = {.all = a};
198 if (p.s.lo)
199 return ci_ctzll(p.s.lo);
200 return 64 + ci_ctzll(p.s.hi);
201}
202
203int __ffsti2(int128_t a) {
204 u128_parts p = {.all = (uint128_t) a};
205 if (p.s.lo)
206 return ci_ctzll(p.s.lo) + 1;
207 if (p.s.hi)
208 return ci_ctzll(p.s.hi) + 65;
209 return 0;
210}
211
212/* GCC lowers __builtin_popcount* to these when it can't inline the expansion,
213 * so we'll need to implement these to use it */
214int __popcountsi2(uint32_t a) {
215 return popcount64(x: a);
216}
217
218int __popcountdi2(uint64_t a) {
219 return popcount64(x: a);
220}
221
222int __popcountti2(uint128_t a) {
223 u128_parts p = {.all = a};
224 return popcount64(x: p.s.lo) + popcount64(x: p.s.hi);
225}
226
227int __parityti2(uint128_t a) {
228 u128_parts p = {.all = a};
229 return popcount64(x: p.s.lo ^ p.s.hi) & 1;
230}
231
232int128_t __negvti2(int128_t a) {
233 if (a == INT128_MIN)
234 panic(OVERFLOW);
235 return __negti2(a);
236}
237
238int128_t __absvti2(int128_t a) {
239 if (a == INT128_MIN)
240 panic(OVERFLOW);
241 return a < 0 ? __negti2(a) : a;
242}
243
244int128_t __addvti3(int128_t a, int128_t b) {
245 int128_t r = (int128_t) ((uint128_t) a + (uint128_t) b);
246 if (((a ^ r) & (b ^ r)) < 0)
247 panic(OVERFLOW);
248 return r;
249}
250
251int128_t __subvti3(int128_t a, int128_t b) {
252 int128_t r = (int128_t) ((uint128_t) a - (uint128_t) b);
253 if (((a ^ b) & (a ^ r)) < 0)
254 panic(OVERFLOW);
255 return r;
256}
257
258int128_t __mulvti3(int128_t a, int128_t b) {
259 int128_t r = __multi3(a, b);
260 if (a != 0 && (r / a != b || (a == -1 && b == INT128_MIN)))
261 panic(OVERFLOW);
262 return r;
263}
264