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