1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
|
// SPDX-License-Identifier: GPL-2.0+
/*
* Copyright (C) 1989-2013 Free Software Foundation, Inc.
*/
#include "libgcc2.h"
DWtype
__ashldi3(DWtype u, shift_count_type b)
{
if (b == 0)
return u;
const DWunion uu = {.ll = u};
const shift_count_type bm = W_TYPE_SIZE - b;
DWunion w;
if (bm <= 0) {
w.s.low = 0;
w.s.high = (UWtype)uu.s.low << -bm;
} else {
const UWtype carries = (UWtype) uu.s.low >> bm;
w.s.low = (UWtype)uu.s.low << b;
w.s.high = ((UWtype)uu.s.high << b) | carries;
}
return w.ll;
}
DWtype
__ashrdi3(DWtype u, shift_count_type b)
{
if (b == 0)
return u;
const DWunion uu = {.ll = u};
const shift_count_type bm = W_TYPE_SIZE - b;
DWunion w;
if (bm <= 0) {
/* w.s.high = 1..1 or 0..0 */
w.s.high = uu.s.high >> (W_TYPE_SIZE - 1);
w.s.low = uu.s.high >> -bm;
} else {
const UWtype carries = (UWtype) uu.s.high << bm;
w.s.high = uu.s.high >> b;
w.s.low = ((UWtype)uu.s.low >> b) | carries;
}
return w.ll;
}
DWtype
__lshrdi3(DWtype u, shift_count_type b)
{
if (b == 0)
return u;
const DWunion uu = {.ll = u};
const shift_count_type bm = W_TYPE_SIZE - b;
DWunion w;
if (bm <= 0) {
w.s.high = 0;
w.s.low = (UWtype)uu.s.high >> -bm;
} else {
const UWtype carries = (UWtype)uu.s.high << bm;
w.s.high = (UWtype)uu.s.high >> b;
w.s.low = ((UWtype)uu.s.low >> b) | carries;
}
return w.ll;
}
unsigned long
udivmodsi4(unsigned long num, unsigned long den, int modwanted)
{
unsigned long bit = 1;
unsigned long res = 0;
while (den < num && bit && !(den & (1L<<31))) {
den <<= 1;
bit <<= 1;
}
while (bit) {
if (num >= den) {
num -= den;
res |= bit;
}
bit >>= 1;
den >>= 1;
}
if (modwanted)
return num;
return res;
}
long
__divsi3(long a, long b)
{
int neg = 0;
long res;
if (a < 0) {
a = -a;
neg = !neg;
}
if (b < 0) {
b = -b;
neg = !neg;
}
res = udivmodsi4(a, b, 0);
if (neg)
res = -res;
return res;
}
long
__modsi3(long a, long b)
{
int neg = 0;
long res;
if (a < 0) {
a = -a;
neg = 1;
}
if (b < 0)
b = -b;
res = udivmodsi4(a, b, 1);
if (neg)
res = -res;
return res;
}
long
__udivsi3(long a, long b)
{
return udivmodsi4(a, b, 0);
}
long
__umodsi3(long a, long b)
{
return udivmodsi4(a, b, 1);
}
UDWtype
__udivmoddi4(UDWtype n, UDWtype d, UDWtype *rp)
{
UDWtype q = 0, r = n, y = d;
UWtype lz1, lz2, i, k;
/*
* Implements align divisor shift dividend method. This algorithm
* aligns the divisor under the dividend and then perform number of
* test-subtract iterations which shift the dividend left. Number of
* iterations is k + 1 where k is the number of bit positions the
* divisor must be shifted left to align it under the dividend.
* quotient bits can be saved in the rightmost positions of the
* dividend as it shifts left on each test-subtract iteration.
*/
if (y <= r) {
lz1 = __builtin_clzll(d);
lz2 = __builtin_clzll(n);
k = lz1 - lz2;
y = (y << k);
/*
* Dividend can exceed 2 ^ (width - 1) - 1 but still be less
* than the aligned divisor. Normal iteration can drops the
* high order bit of the dividend. Therefore, first
* test-subtract iteration is a special case, saving its
* quotient bit in a separate location and not shifting
* the dividend.
*/
if (r >= y) {
r = r - y;
q = (1ULL << k);
}
if (k > 0) {
y = y >> 1;
/*
* k additional iterations where k regular test
* subtract shift dividend iterations are done.
*/
i = k;
do {
if (r >= y)
r = ((r - y) << 1) + 1;
else
r = (r << 1);
i = i - 1;
} while (i != 0);
/*
* First quotient bit is combined with the quotient
* bits resulting from the k regular iterations.
*/
q = q + r;
r = r >> k;
q = q - (r << k);
}
}
if (rp)
*rp = r;
return q;
}
UDWtype
__udivdi3(UDWtype n, UDWtype d)
{
return __udivmoddi4(n, d, (UDWtype *)0);
}
|
