xref: /openbmc/u-boot/arch/nios2/lib/libgcc.c (revision 1bad5e14)
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
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
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
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
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
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
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
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
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
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
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
445 __udivdi3 (UDWtype n, UDWtype d)
446 {
447   return __udivmoddi4 (n, d, (UDWtype *) 0);
448 }
449 
450 UDWtype
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
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
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
512 __udivsi3 (SItype a, SItype b)
513 {
514   return udivmodsi4 (a, b, 0);
515 }
516 
517 
518 SItype
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
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
561 __umodsi3 (SItype a, SItype b)
562 
563 {
564   return udivmodsi4 (a, b, 1);
565 }
566 
567 int
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