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