1
#include <base/types.h>
2
3
#if defined(__has_attribute)
4
#if __has_attribute(weak)
5
#define WEAK_ATTR __attribute__((weak))
6
#endif7
#endif8
#ifndef WEAK_ATTR
9
#define WEAK_ATTR
10
#endif11
12
static u32 _umul32(u32 lhs, u32 rhs) {
13
u32 result = 0;
14
15
while (rhs) {
16
if (rhs & 1U) {
17
result += lhs;
18
}19
20
lhs <<= 1;
21
rhs >>= 1;
22
}23
24
return result;
25
}26
27
static u64 _umul64(u64 lhs, u64 rhs) {
28
u64 result = 0;
29
30
while (rhs) {
31
if (rhs & 1ULL) {
32
result += lhs;
33
}34
35
lhs <<= 1;
36
rhs >>= 1;
37
}38
39
return result;
40
}41
42
#if defined(__SIZEOF_INT128__)
43
static void _umul128_64(u64 lhs, u64 rhs, u64 *hi_out, u64 *lo_out) {
44
u64 lhs_lo = (u32)lhs;
45
u64 lhs_hi = lhs >> 32;
46
u64 rhs_lo = (u32)rhs;
47
u64 rhs_hi = rhs >> 32;
48
49
u64 p0 = _umul64(lhs_lo, rhs_lo);
50
u64 p1 = _umul64(lhs_lo, rhs_hi);
51
u64 p2 = _umul64(lhs_hi, rhs_lo);
52
u64 p3 = _umul64(lhs_hi, rhs_hi);
53
54
u64 carry = (p0 >> 32) + (u32)p1 + (u32)p2;
55
u64 lo = (p0 & 0xffffffffULL) | (carry << 32);
56
u64 hi = p3 + (p1 >> 32) + (p2 >> 32) + (carry >> 32);
57
58
if (hi_out) {
59
*hi_out = hi;
60
}61
62
if (lo_out) {
63
*lo_out = lo;
64
}65
}66
#endif67
68
static u32 _udivmod32(u32 num, u32 den, u32 *rem_out) {
69
if (!den) {
70
if (rem_out) {
71
*rem_out = 0;
72
}73
74
return 0;
75
}76
77
u32 quot = 0;
78
u32 rem = 0;
79
80
for (int bit = 31; bit >= 0; bit--) {
81
rem = (rem << 1) | ((num >> bit) & 1U);
82
83
if (rem >= den) {
84
rem -= den;
85
quot |= (1U << bit);
86
}87
}88
89
if (rem_out) {
90
*rem_out = rem;
91
}92
93
return quot;
94
}95
96
WEAK_ATTR u32 __mulsi3(u32 lhs, u32 rhs) {
97
return _umul32(lhs, rhs);
98
}99
100
WEAK_ATTR u64 __muldi3(u64 lhs, u64 rhs) {
101
return _umul64(lhs, rhs);
102
}103
104
#if defined(__SIZEOF_INT128__)
105
WEAK_ATTR __int128 __multi3(__int128 lhs, __int128 rhs) {
106
union {
107
unsigned __int128 value;
108
struct {
109
u64 lo;110
u64 hi;111
} parts;
112
} a = { .value = (unsigned __int128)lhs }, b = { .value = (unsigned __int128)rhs }, result = { .value = 0 };
113
114
u64 lo_hi = 0;
115
u64 lo_lo = 0;
116
_umul128_64(a.parts.lo, b.parts.lo, &lo_hi, &lo_lo);
117
118
result.parts.lo = lo_lo;
119
result.parts.hi = lo_hi + _umul64(a.parts.lo, b.parts.hi) + _umul64(a.parts.hi, b.parts.lo);
120
121
return (__int128)result.value;
122
}123
#endif124
125
WEAK_ATTR u32 __udivsi3(u32 num, u32 den) {
126
return _udivmod32(num, den, 0);
127
}128
129
WEAK_ATTR u32 __umodsi3(u32 num, u32 den) {
130
u32 rem = 0;
131
_udivmod32(num, den, &rem);
132
return rem;
133
}134
135
WEAK_ATTR i32 __divsi3(i32 num, i32 den) {
136
int neg = 0;
137
u32 unum = (u32)num;
138
u32 uden = (u32)den;
139
140
if (num < 0) {
141
neg ^= 1;
142
unum = 0U - unum;
143
}144
145
if (den < 0) {
146
neg ^= 1;
147
uden = 0U - uden;
148
}149
150
u32 quot = _udivmod32(unum, uden, 0);
151
return neg ? (i32)(0U - quot) : (i32)quot;
152
}153
154
WEAK_ATTR i32 __modsi3(i32 num, i32 den) {
155
u32 rem = 0;
156
u32 unum = (u32)num;
157
u32 uden = (u32)den;
158
159
if (num < 0) {
160
unum = 0U - unum;
161
}162
163
if (den < 0) {
164
uden = 0U - uden;
165
}166
167
_udivmod32(unum, uden, &rem);
168
return num < 0 ? (i32)(0U - rem) : (i32)rem;
169
}170
171
WEAK_ATTR u64 __ashldi3(u64 value, u32 shift) {
172
if (shift >= 64U) {
173
return 0;
174
}175
176
while (shift--) {
177
value <<= 1;
178
}179
180
return value;
181
}182
183
WEAK_ATTR u64 __lshrdi3(u64 value, u32 shift) {
184
if (shift >= 64U) {
185
return 0;
186
}187
188
while (shift--) {
189
value >>= 1;
190
}191
192
return value;
193
}194
195
WEAK_ATTR i64 __ashrdi3(i64 value, u32 shift) {
196
if (shift >= 64U) {
197
return value < 0 ? -1 : 0;
198
}199
200
while (shift--) {
201
value >>= 1;
202
}203
204
return value;
205
}206
207
WEAK_ATTR i32 __ucmpdi2(u64 lhs, u64 rhs) {
208
if (lhs < rhs) {
209
return 0;
210
}211
212
if (lhs > rhs) {
213
return 2;
214
}215
216
return 1;
217
}218
219
WEAK_ATTR i32 __cmpdi2(i64 lhs, i64 rhs) {
220
if (lhs < rhs) {
221
return 0;
222
}223
224
if (lhs > rhs) {
225
return 2;
226
}227
228
return 1;
229
}