arch/nios2/lib/libgcc.c

   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 }