xref: /openbmc/u-boot/arch/nios2/lib/libgcc.c (revision 29b103c7) 
1 /*
2  * This file is part of GNU CC.
3  *
4  * SPDX-License-Identifier:	GPL-2.0+
5  */
6 
7 typedef unsigned int UWtype;
8 typedef unsigned int UHWtype;
9 typedef unsigned long long UDWtype;
10 #define W_TYPE_SIZE 32
11 
12 typedef unsigned char UQItype;
13 typedef long SItype;
14 typedef unsigned long USItype;
15 typedef long long DItype;
16 typedef unsigned long long DSItype;
17 
18 #include "longlong.h"
19 
20 
21 typedef int word_type;
22 typedef long Wtype;
23 typedef long long DWtype;
24 
25 struct DWstruct { Wtype low, high;};
26 
27 typedef union
28 {
29   struct DWstruct s;
30   DWtype ll;
31 } DWunion;
32 
33 #define BITS_PER_UNIT 8
34 
35 UDWtype
36 __udivmoddi4 (UDWtype n, UDWtype d, UDWtype *rp);
37 
38 const 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 
51 DWtype
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 
77 DWtype
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 
104 DWtype
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 
130 word_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 
147 UDWtype
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 
360 DWtype
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 
382 DWtype
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 
393 DWtype
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 
406 DWtype
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 
427 word_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 
445 UDWtype
446 __udivdi3 (UDWtype n, UDWtype d)
447 {
448   return __udivmoddi4 (n, d, (UDWtype *) 0);
449 }
450 
451 UDWtype
452 __umoddi3 (UDWtype u, UDWtype v)
453 {
454   UDWtype w;
455   (void) __udivmoddi4 (u, v, &w);
456 
457   return w;
458 }
459 
460 static USItype
461 udivmodsi4(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 
485 SItype
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 
512 SItype
513 __udivsi3 (SItype a, SItype b)
514 {
515   return udivmodsi4 (a, b, 0);
516 }
517 
518 
519 SItype
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 
542 SItype
543 __mulsi3 (SItype a, SItype b)
544 {
545   SItype res = 0;
546   USItype cnt = a;
547 
548   while (cnt)
549     {
550       if (cnt & 1)
551 	{
552 	  res += b;
553 	}
554       b <<= 1;
555       cnt >>= 1;
556     }
557 
558   return res;
559 }
560 
561 SItype
562 __umodsi3 (SItype a, SItype b)
563 
564 {
565   return udivmodsi4 (a, b, 1);
566 }
567 
568 int
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 }
580