arch/nios2/lib/libgcc.c

   1 /*
   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
  20 typedef unsigned int UWtype;
  21 typedef unsigned int UHWtype;
  22 typedef unsigned long long UDWtype;
  23 #define W_TYPE_SIZE 32
  24
  25 typedef unsigned char UQItype;
  26 typedef long SItype;
  27 typedef unsigned long USItype;
  28 typedef long long DItype;
  29 typedef unsigned long long DSItype;
  30
  31 #include "longlong.h"
  32
  33
  34 typedef int word_type;
  35 typedef long Wtype;
  36 typedef long long DWtype;
  37
  38 struct DWstruct { Wtype low, high;};
  39
  40 typedef union
  41 {
  42   struct DWstruct s;
  43   DWtype ll;
  44 } DWunion;
  45
  46 #define BITS_PER_UNIT 8
  47
  48 UDWtype
  49 __udivmoddi4 (UDWtype n, UDWtype d, UDWtype *rp);
  50
  51 const 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
  64 DWtype
  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
  90 DWtype
  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
 117 DWtype
 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
 143 word_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
 160 UDWtype
 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
 373 DWtype
 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
 395 DWtype
 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
 406 DWtype
 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
 419 DWtype
 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
 440 word_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
 458 UDWtype
 459 __udivdi3 (UDWtype n, UDWtype d)
 460 {
 461   return __udivmoddi4 (n, d, (UDWtype *) 0);
 462 }
 463
 464 UDWtype
 465 __umoddi3 (UDWtype u, UDWtype v)
 466 {
 467   UDWtype w;
 468   (void) __udivmoddi4 (u, v, &w);
 469
 470   return w;
 471 }
 472
 473 static USItype
 474 udivmodsi4(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
 498 SItype
 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
 525 SItype
 526 __udivsi3 (SItype a, SItype b)
 527 {
 528   return udivmodsi4 (a, b, 0);
 529 }
 530
 531
 532 SItype
 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
 555 SItype
 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
 574 SItype
 575 __umodsi3 (SItype a, SItype b)
 576
 577 {
 578   return udivmodsi4 (a, b, 1);
 579 }
 580
 581 int
 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 }