1 // SPDX-License-Identifier: GPL-2.0+
2 /*
3 * This file is part of GNU CC.
4 */
5
6 typedef unsigned int UWtype;
7 typedef unsigned int UHWtype;
8 typedef unsigned long long UDWtype;
9 #define W_TYPE_SIZE 32
10
11 typedef unsigned char UQItype;
12 typedef long SItype;
13 typedef unsigned long USItype;
14 typedef long long DItype;
15 typedef unsigned long long DSItype;
16
17 #include "longlong.h"
18
19
20 typedef int word_type;
21 typedef long Wtype;
22 typedef long long DWtype;
23
24 struct DWstruct { Wtype low, high;};
25
26 typedef union
27 {
28 struct DWstruct s;
29 DWtype ll;
30 } DWunion;
31
32 #define BITS_PER_UNIT 8
33
34 UDWtype
35 __udivmoddi4 (UDWtype n, UDWtype d, UDWtype *rp);
36
37 const UQItype __clz_tab[256] =
38 {
39 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
40 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
41 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
42 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
43 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
44 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
45 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
46 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8
47 };
48
49
50 DWtype
__ashldi3(DWtype u,word_type b)51 __ashldi3 (DWtype u, word_type b)
52 {
53 if (b == 0)
54 return u;
55
56 const DWunion uu = {.ll = u};
57 const word_type bm = (sizeof (Wtype) * BITS_PER_UNIT) - b;
58 DWunion w;
59
60 if (bm <= 0)
61 {
62 w.s.low = 0;
63 w.s.high = (UWtype) uu.s.low << -bm;
64 }
65 else
66 {
67 const UWtype carries = (UWtype) uu.s.low >> bm;
68
69 w.s.low = (UWtype) uu.s.low << b;
70 w.s.high = ((UWtype) uu.s.high << b) | carries;
71 }
72
73 return w.ll;
74 }
75
76 DWtype
__ashrdi3(DWtype u,word_type b)77 __ashrdi3 (DWtype u, word_type b)
78 {
79 if (b == 0)
80 return u;
81
82 const DWunion uu = {.ll = u};
83 const word_type bm = (sizeof (Wtype) * BITS_PER_UNIT) - b;
84 DWunion w;
85
86 if (bm <= 0)
87 {
88 /* w.s.high = 1..1 or 0..0 */
89 w.s.high = uu.s.high >> (sizeof (Wtype) * BITS_PER_UNIT - 1);
90 w.s.low = uu.s.high >> -bm;
91 }
92 else
93 {
94 const UWtype carries = (UWtype) uu.s.high << bm;
95
96 w.s.high = uu.s.high >> b;
97 w.s.low = ((UWtype) uu.s.low >> b) | carries;
98 }
99
100 return w.ll;
101 }
102
103 DWtype
__lshrdi3(DWtype u,word_type b)104 __lshrdi3 (DWtype u, word_type b)
105 {
106 if (b == 0)
107 return u;
108
109 const DWunion uu = {.ll = u};
110 const word_type bm = (sizeof (Wtype) * BITS_PER_UNIT) - b;
111 DWunion w;
112
113 if (bm <= 0)
114 {
115 w.s.high = 0;
116 w.s.low = (UWtype) uu.s.high >> -bm;
117 }
118 else
119 {
120 const UWtype carries = (UWtype) uu.s.high << bm;
121
122 w.s.high = (UWtype) uu.s.high >> b;
123 w.s.low = ((UWtype) uu.s.low >> b) | carries;
124 }
125
126 return w.ll;
127 }
128
129 word_type
__cmpdi2(DWtype a,DWtype b)130 __cmpdi2 (DWtype a, DWtype b)
131 {
132 const DWunion au = {.ll = a};
133 const DWunion bu = {.ll = b};
134
135 if (au.s.high < bu.s.high)
136 return 0;
137 else if (au.s.high > bu.s.high)
138 return 2;
139 if ((UWtype) au.s.low < (UWtype) bu.s.low)
140 return 0;
141 else if ((UWtype) au.s.low > (UWtype) bu.s.low)
142 return 2;
143 return 1;
144 }
145
146 UDWtype
__udivmoddi4(UDWtype n,UDWtype d,UDWtype * rp)147 __udivmoddi4 (UDWtype n, UDWtype d, UDWtype *rp)
148 {
149 const DWunion nn = {.ll = n};
150 const DWunion dd = {.ll = d};
151 DWunion rr;
152 UWtype d0, d1, n0, n1, n2;
153 UWtype q0, q1;
154 UWtype b, bm;
155
156 d0 = dd.s.low;
157 d1 = dd.s.high;
158 n0 = nn.s.low;
159 n1 = nn.s.high;
160
161 #if !UDIV_NEEDS_NORMALIZATION
162 if (d1 == 0)
163 {
164 if (d0 > n1)
165 {
166 /* 0q = nn / 0D */
167
168 udiv_qrnnd (q0, n0, n1, n0, d0);
169 q1 = 0;
170
171 /* Remainder in n0. */
172 }
173 else
174 {
175 /* qq = NN / 0d */
176
177 if (d0 == 0)
178 d0 = 1 / d0; /* Divide intentionally by zero. */
179
180 udiv_qrnnd (q1, n1, 0, n1, d0);
181 udiv_qrnnd (q0, n0, n1, n0, d0);
182
183 /* Remainder in n0. */
184 }
185
186 if (rp != 0)
187 {
188 rr.s.low = n0;
189 rr.s.high = 0;
190 *rp = rr.ll;
191 }
192 }
193
194 #else /* UDIV_NEEDS_NORMALIZATION */
195
196 if (d1 == 0)
197 {
198 if (d0 > n1)
199 {
200 /* 0q = nn / 0D */
201
202 count_leading_zeros (bm, d0);
203
204 if (bm != 0)
205 {
206 /* Normalize, i.e. make the most significant bit of the
207 denominator set. */
208
209 d0 = d0 << bm;
210 n1 = (n1 << bm) | (n0 >> (W_TYPE_SIZE - bm));
211 n0 = n0 << bm;
212 }
213
214 udiv_qrnnd (q0, n0, n1, n0, d0);
215 q1 = 0;
216
217 /* Remainder in n0 >> bm. */
218 }
219 else
220 {
221 /* qq = NN / 0d */
222
223 if (d0 == 0)
224 d0 = 1 / d0; /* Divide intentionally by zero. */
225
226 count_leading_zeros (bm, d0);
227
228 if (bm == 0)
229 {
230 /* From (n1 >= d0) /\ (the most significant bit of d0 is set),
231 conclude (the most significant bit of n1 is set) /\ (the
232 leading quotient digit q1 = 1).
233
234 This special case is necessary, not an optimization.
235 (Shifts counts of W_TYPE_SIZE are undefined.) */
236
237 n1 -= d0;
238 q1 = 1;
239 }
240 else
241 {
242 /* Normalize. */
243
244 b = W_TYPE_SIZE - bm;
245
246 d0 = d0 << bm;
247 n2 = n1 >> b;
248 n1 = (n1 << bm) | (n0 >> b);
249 n0 = n0 << bm;
250
251 udiv_qrnnd (q1, n1, n2, n1, d0);
252 }
253
254 /* n1 != d0... */
255
256 udiv_qrnnd (q0, n0, n1, n0, d0);
257
258 /* Remainder in n0 >> bm. */
259 }
260
261 if (rp != 0)
262 {
263 rr.s.low = n0 >> bm;
264 rr.s.high = 0;
265 *rp = rr.ll;
266 }
267 }
268 #endif /* UDIV_NEEDS_NORMALIZATION */
269
270 else
271 {
272 if (d1 > n1)
273 {
274 /* 00 = nn / DD */
275
276 q0 = 0;
277 q1 = 0;
278
279 /* Remainder in n1n0. */
280 if (rp != 0)
281 {
282 rr.s.low = n0;
283 rr.s.high = n1;
284 *rp = rr.ll;
285 }
286 }
287 else
288 {
289 /* 0q = NN / dd */
290
291 count_leading_zeros (bm, d1);
292 if (bm == 0)
293 {
294 /* From (n1 >= d1) /\ (the most significant bit of d1 is set),
295 conclude (the most significant bit of n1 is set) /\ (the
296 quotient digit q0 = 0 or 1).
297
298 This special case is necessary, not an optimization. */
299
300 /* The condition on the next line takes advantage of that
301 n1 >= d1 (true due to program flow). */
302 if (n1 > d1 || n0 >= d0)
303 {
304 q0 = 1;
305 sub_ddmmss (n1, n0, n1, n0, d1, d0);
306 }
307 else
308 q0 = 0;
309
310 q1 = 0;
311
312 if (rp != 0)
313 {
314 rr.s.low = n0;
315 rr.s.high = n1;
316 *rp = rr.ll;
317 }
318 }
319 else
320 {
321 UWtype m1, m0;
322 /* Normalize. */
323
324 b = W_TYPE_SIZE - bm;
325
326 d1 = (d1 << bm) | (d0 >> b);
327 d0 = d0 << bm;
328 n2 = n1 >> b;
329 n1 = (n1 << bm) | (n0 >> b);
330 n0 = n0 << bm;
331
332 udiv_qrnnd (q0, n1, n2, n1, d1);
333 umul_ppmm (m1, m0, q0, d0);
334
335 if (m1 > n1 || (m1 == n1 && m0 > n0))
336 {
337 q0--;
338 sub_ddmmss (m1, m0, m1, m0, d1, d0);
339 }
340
341 q1 = 0;
342
343 /* Remainder in (n1n0 - m1m0) >> bm. */
344 if (rp != 0)
345 {
346 sub_ddmmss (n1, n0, n1, n0, m1, m0);
347 rr.s.low = (n1 << b) | (n0 >> bm);
348 rr.s.high = n1 >> bm;
349 *rp = rr.ll;
350 }
351 }
352 }
353 }
354
355 const DWunion ww = {{.low = q0, .high = q1}};
356 return ww.ll;
357 }
358
359 DWtype
__divdi3(DWtype u,DWtype v)360 __divdi3 (DWtype u, DWtype v)
361 {
362 word_type c = 0;
363 DWunion uu = {.ll = u};
364 DWunion vv = {.ll = v};
365 DWtype w;
366
367 if (uu.s.high < 0)
368 c = ~c,
369 uu.ll = -uu.ll;
370 if (vv.s.high < 0)
371 c = ~c,
372 vv.ll = -vv.ll;
373
374 w = __udivmoddi4 (uu.ll, vv.ll, (UDWtype *) 0);
375 if (c)
376 w = -w;
377
378 return w;
379 }
380
381 DWtype
__negdi2(DWtype u)382 __negdi2 (DWtype u)
383 {
384 const DWunion uu = {.ll = u};
385 const DWunion w = { {.low = -uu.s.low,
386 .high = -uu.s.high - ((UWtype) -uu.s.low > 0) } };
387
388 return w.ll;
389 }
390
391
392 DWtype
__muldi3(DWtype u,DWtype v)393 __muldi3 (DWtype u, DWtype v)
394 {
395 const DWunion uu = {.ll = u};
396 const DWunion vv = {.ll = v};
397 DWunion w = {.ll = __umulsidi3 (uu.s.low, vv.s.low)};
398
399 w.s.high += ((UWtype) uu.s.low * (UWtype) vv.s.high
400 + (UWtype) uu.s.high * (UWtype) vv.s.low);
401
402 return w.ll;
403 }
404
405 DWtype
__moddi3(DWtype u,DWtype v)406 __moddi3 (DWtype u, DWtype v)
407 {
408 word_type c = 0;
409 DWunion uu = {.ll = u};
410 DWunion vv = {.ll = v};
411 DWtype w;
412
413 if (uu.s.high < 0)
414 c = ~c,
415 uu.ll = -uu.ll;
416 if (vv.s.high < 0)
417 vv.ll = -vv.ll;
418
419 (void) __udivmoddi4 (uu.ll, vv.ll, (UDWtype*)&w);
420 if (c)
421 w = -w;
422
423 return w;
424 }
425
426 word_type
__ucmpdi2(DWtype a,DWtype b)427 __ucmpdi2 (DWtype a, DWtype b)
428 {
429 const DWunion au = {.ll = a};
430 const DWunion bu = {.ll = b};
431
432 if ((UWtype) au.s.high < (UWtype) bu.s.high)
433 return 0;
434 else if ((UWtype) au.s.high > (UWtype) bu.s.high)
435 return 2;
436 if ((UWtype) au.s.low < (UWtype) bu.s.low)
437 return 0;
438 else if ((UWtype) au.s.low > (UWtype) bu.s.low)
439 return 2;
440 return 1;
441 }
442
443
444 UDWtype
__udivdi3(UDWtype n,UDWtype d)445 __udivdi3 (UDWtype n, UDWtype d)
446 {
447 return __udivmoddi4 (n, d, (UDWtype *) 0);
448 }
449
450 UDWtype
__umoddi3(UDWtype u,UDWtype v)451 __umoddi3 (UDWtype u, UDWtype v)
452 {
453 UDWtype w;
454 (void) __udivmoddi4 (u, v, &w);
455
456 return w;
457 }
458
459 static USItype
udivmodsi4(USItype num,USItype den,word_type modwanted)460 udivmodsi4(USItype num, USItype den, word_type modwanted)
461 {
462 USItype bit = 1;
463 USItype res = 0;
464
465 while (den < num && bit && !(den & (1L<<31)))
466 {
467 den <<=1;
468 bit <<=1;
469 }
470 while (bit)
471 {
472 if (num >= den)
473 {
474 num -= den;
475 res |= bit;
476 }
477 bit >>=1;
478 den >>=1;
479 }
480 if (modwanted) return num;
481 return res;
482 }
483
484 SItype
__divsi3(SItype a,SItype b)485 __divsi3 (SItype a, SItype b)
486 {
487 word_type neg = 0;
488 SItype res;
489
490 if (a < 0)
491 {
492 a = -a;
493 neg = !neg;
494 }
495
496 if (b < 0)
497 {
498 b = -b;
499 neg = !neg;
500 }
501
502 res = udivmodsi4 (a, b, 0);
503
504 if (neg)
505 res = -res;
506
507 return res;
508 }
509
510
511 SItype
__udivsi3(SItype a,SItype b)512 __udivsi3 (SItype a, SItype b)
513 {
514 return udivmodsi4 (a, b, 0);
515 }
516
517
518 SItype
__modsi3(SItype a,SItype b)519 __modsi3 (SItype a, SItype b)
520 {
521 word_type neg = 0;
522 SItype res;
523
524 if (a < 0)
525 {
526 a = -a;
527 neg = 1;
528 }
529
530 if (b < 0)
531 b = -b;
532
533 res = udivmodsi4 (a, b, 1);
534
535 if (neg)
536 res = -res;
537
538 return res;
539 }
540
541 SItype
__mulsi3(SItype a,SItype b)542 __mulsi3 (SItype a, SItype b)
543 {
544 SItype res = 0;
545 USItype cnt = a;
546
547 while (cnt)
548 {
549 if (cnt & 1)
550 {
551 res += b;
552 }
553 b <<= 1;
554 cnt >>= 1;
555 }
556
557 return res;
558 }
559
560 SItype
__umodsi3(SItype a,SItype b)561 __umodsi3 (SItype a, SItype b)
562
563 {
564 return udivmodsi4 (a, b, 1);
565 }
566
567 int
__gcc_bcmp(const unsigned char * s1,const unsigned char * s2,unsigned long size)568 __gcc_bcmp (const unsigned char *s1, const unsigned char *s2, unsigned long size)
569 {
570 while (size > 0)
571 {
572 const unsigned char c1 = *s1++, c2 = *s2++;
573 if (c1 != c2)
574 return c1 - c2;
575 size--;
576 }
577 return 0;
578 }
579