arch/nios2/lib/libgcc.c

   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 }