gcc/double-int.c

   1 /* Operations with long integers.
   2    Copyright (C) 2006, 2007, 2009, 2010 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it
   7 under the terms of the GNU General Public License as published by the
   8 Free Software Foundation; either version 3, or (at your option) any
   9 later version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT
  12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "tm.h"                 /* For SHIFT_COUNT_TRUNCATED.  */
  24 #include "tree.h"
  25 #include "toplev.h"
  26
  27 /* We know that A1 + B1 = SUM1, using 2's complement arithmetic and ignoring
  28    overflow.  Suppose A, B and SUM have the same respective signs as A1, B1,
  29    and SUM1.  Then this yields nonzero if overflow occurred during the
  30    addition.
  31
  32    Overflow occurs if A and B have the same sign, but A and SUM differ in
  33    sign.  Use `^' to test whether signs differ, and `< 0' to isolate the
  34    sign.  */
  35 #define OVERFLOW_SUM_SIGN(a, b, sum) ((~((a) ^ (b)) & ((a) ^ (sum))) < 0)
  36
  37 /* To do constant folding on INTEGER_CST nodes requires two-word arithmetic.
  38    We do that by representing the two-word integer in 4 words, with only
  39    HOST_BITS_PER_WIDE_INT / 2 bits stored in each word, as a positive
  40    number.  The value of the word is LOWPART + HIGHPART * BASE.  */
  41
  42 #define LOWPART(x) \
  43   ((x) & (((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)) - 1))
  44 #define HIGHPART(x) \
  45   ((unsigned HOST_WIDE_INT) (x) >> HOST_BITS_PER_WIDE_INT / 2)
  46 #define BASE ((unsigned HOST_WIDE_INT) 1 << HOST_BITS_PER_WIDE_INT / 2)
  47
  48 /* Unpack a two-word integer into 4 words.
  49    LOW and HI are the integer, as two `HOST_WIDE_INT' pieces.
  50    WORDS points to the array of HOST_WIDE_INTs.  */
  51
  52 static void
  53 encode (HOST_WIDE_INT *words, unsigned HOST_WIDE_INT low, HOST_WIDE_INT hi)
  54 {
  55   words[0] = LOWPART (low);
  56   words[1] = HIGHPART (low);
  57   words[2] = LOWPART (hi);
  58   words[3] = HIGHPART (hi);
  59 }
  60
  61 /* Pack an array of 4 words into a two-word integer.
  62    WORDS points to the array of words.
  63    The integer is stored into *LOW and *HI as two `HOST_WIDE_INT' pieces.  */
  64
  65 static void
  66 decode (HOST_WIDE_INT *words, unsigned HOST_WIDE_INT *low,
  67         HOST_WIDE_INT *hi)
  68 {
  69   *low = words[0] + words[1] * BASE;
  70   *hi = words[2] + words[3] * BASE;
  71 }
  72
  73 /* Add two doubleword integers with doubleword result.
  74    Return nonzero if the operation overflows according to UNSIGNED_P.
  75    Each argument is given as two `HOST_WIDE_INT' pieces.
  76    One argument is L1 and H1; the other, L2 and H2.
  77    The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
  78
  79 int
  80 add_double_with_sign (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
  81                       unsigned HOST_WIDE_INT l2, HOST_WIDE_INT h2,
  82                       unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv,
  83                       bool unsigned_p)
  84 {
  85   unsigned HOST_WIDE_INT l;
  86   HOST_WIDE_INT h;
  87
  88   l = l1 + l2;
  89   h = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) h1
  90                        + (unsigned HOST_WIDE_INT) h2
  91                        + (l < l1));
  92
  93   *lv = l;
  94   *hv = h;
  95
  96   if (unsigned_p)
  97     return ((unsigned HOST_WIDE_INT) h < (unsigned HOST_WIDE_INT) h1
  98             || (h == h1
  99                 && l < l1));
 100   else
 101     return OVERFLOW_SUM_SIGN (h1, h2, h);
 102 }
 103
 104 /* Negate a doubleword integer with doubleword result.
 105    Return nonzero if the operation overflows, assuming it's signed.
 106    The argument is given as two `HOST_WIDE_INT' pieces in L1 and H1.
 107    The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 108
 109 int
 110 neg_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
 111             unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv)
 112 {
 113   if (l1 == 0)
 114     {
 115       *lv = 0;
 116       *hv = - h1;
 117       return (*hv & h1) < 0;
 118     }
 119   else
 120     {
 121       *lv = -l1;
 122       *hv = ~h1;
 123       return 0;
 124     }
 125 }
 126
 127 /* Multiply two doubleword integers with doubleword result.
 128    Return nonzero if the operation overflows according to UNSIGNED_P.
 129    Each argument is given as two `HOST_WIDE_INT' pieces.
 130    One argument is L1 and H1; the other, L2 and H2.
 131    The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 132
 133 int
 134 mul_double_with_sign (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
 135                       unsigned HOST_WIDE_INT l2, HOST_WIDE_INT h2,
 136                       unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv,
 137                       bool unsigned_p)
 138 {
 139   HOST_WIDE_INT arg1[4];
 140   HOST_WIDE_INT arg2[4];
 141   HOST_WIDE_INT prod[4 * 2];
 142   unsigned HOST_WIDE_INT carry;
 143   int i, j, k;
 144   unsigned HOST_WIDE_INT toplow, neglow;
 145   HOST_WIDE_INT tophigh, neghigh;
 146
 147   encode (arg1, l1, h1);
 148   encode (arg2, l2, h2);
 149
 150   memset (prod, 0, sizeof prod);
 151
 152   for (i = 0; i < 4; i++)
 153     {
 154       carry = 0;
 155       for (j = 0; j < 4; j++)
 156         {
 157           k = i + j;
 158           /* This product is <= 0xFFFE0001, the sum <= 0xFFFF0000.  */
 159           carry += arg1[i] * arg2[j];
 160           /* Since prod[p] < 0xFFFF, this sum <= 0xFFFFFFFF.  */
 161           carry += prod[k];
 162           prod[k] = LOWPART (carry);
 163           carry = HIGHPART (carry);
 164         }
 165       prod[i + 4] = carry;
 166     }
 167
 168   decode (prod, lv, hv);
 169   decode (prod + 4, &toplow, &tophigh);
 170
 171   /* Unsigned overflow is immediate.  */
 172   if (unsigned_p)
 173     return (toplow | tophigh) != 0;
 174
 175   /* Check for signed overflow by calculating the signed representation of the
 176      top half of the result; it should agree with the low half's sign bit.  */
 177   if (h1 < 0)
 178     {
 179       neg_double (l2, h2, &neglow, &neghigh);
 180       add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
 181     }
 182   if (h2 < 0)
 183     {
 184       neg_double (l1, h1, &neglow, &neghigh);
 185       add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
 186     }
 187   return (*hv < 0 ? ~(toplow & tophigh) : toplow | tophigh) != 0;
 188 }
 189
 190 /* Shift the doubleword integer in L1, H1 left by COUNT places
 191    keeping only PREC bits of result.
 192    Shift right if COUNT is negative.
 193    ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
 194    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 195
 196 void
 197 lshift_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
 198                HOST_WIDE_INT count, unsigned int prec,
 199                unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv, bool arith)
 200 {
 201   unsigned HOST_WIDE_INT signmask;
 202
 203   if (count < 0)
 204     {
 205       rshift_double (l1, h1, -count, prec, lv, hv, arith);
 206       return;
 207     }
 208
 209   if (SHIFT_COUNT_TRUNCATED)
 210     count %= prec;
 211
 212   if (count >= 2 * HOST_BITS_PER_WIDE_INT)
 213     {
 214       /* Shifting by the host word size is undefined according to the
 215          ANSI standard, so we must handle this as a special case.  */
 216       *hv = 0;
 217       *lv = 0;
 218     }
 219   else if (count >= HOST_BITS_PER_WIDE_INT)
 220     {
 221       *hv = l1 << (count - HOST_BITS_PER_WIDE_INT);
 222       *lv = 0;
 223     }
 224   else
 225     {
 226       *hv = (((unsigned HOST_WIDE_INT) h1 << count)
 227              | (l1 >> (HOST_BITS_PER_WIDE_INT - count - 1) >> 1));
 228       *lv = l1 << count;
 229     }
 230
 231   /* Sign extend all bits that are beyond the precision.  */
 232
 233   signmask = -((prec > HOST_BITS_PER_WIDE_INT
 234                 ? ((unsigned HOST_WIDE_INT) *hv
 235                    >> (prec - HOST_BITS_PER_WIDE_INT - 1))
 236                 : (*lv >> (prec - 1))) & 1);
 237
 238   if (prec >= 2 * HOST_BITS_PER_WIDE_INT)
 239     ;
 240   else if (prec >= HOST_BITS_PER_WIDE_INT)
 241     {
 242       *hv &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
 243       *hv |= signmask << (prec - HOST_BITS_PER_WIDE_INT);
 244     }
 245   else
 246     {
 247       *hv = signmask;
 248       *lv &= ~((unsigned HOST_WIDE_INT) (-1) << prec);
 249       *lv |= signmask << prec;
 250     }
 251 }
 252
 253 /* Shift the doubleword integer in L1, H1 right by COUNT places
 254    keeping only PREC bits of result.  Shift left if COUNT is negative.
 255    ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
 256    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 257
 258 void
 259 rshift_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
 260                HOST_WIDE_INT count, unsigned int prec,
 261                unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv,
 262                bool arith)
 263 {
 264   unsigned HOST_WIDE_INT signmask;
 265
 266   if (count < 0)
 267     {
 268       lshift_double (l1, h1, -count, prec, lv, hv, arith);
 269       return;
 270     }
 271
 272   signmask = (arith
 273               ? -((unsigned HOST_WIDE_INT) h1 >> (HOST_BITS_PER_WIDE_INT - 1))
 274               : 0);
 275
 276   if (SHIFT_COUNT_TRUNCATED)
 277     count %= prec;
 278
 279   if (count >= 2 * HOST_BITS_PER_WIDE_INT)
 280     {
 281       /* Shifting by the host word size is undefined according to the
 282          ANSI standard, so we must handle this as a special case.  */
 283       *hv = 0;
 284       *lv = 0;
 285     }
 286   else if (count >= HOST_BITS_PER_WIDE_INT)
 287     {
 288       *hv = 0;
 289       *lv = (unsigned HOST_WIDE_INT) h1 >> (count - HOST_BITS_PER_WIDE_INT);
 290     }
 291   else
 292     {
 293       *hv = (unsigned HOST_WIDE_INT) h1 >> count;
 294       *lv = ((l1 >> count)
 295              | ((unsigned HOST_WIDE_INT) h1
 296                 << (HOST_BITS_PER_WIDE_INT - count - 1) << 1));
 297     }
 298
 299   /* Zero / sign extend all bits that are beyond the precision.  */
 300
 301   if (count >= (HOST_WIDE_INT)prec)
 302     {
 303       *hv = signmask;
 304       *lv = signmask;
 305     }
 306   else if ((prec - count) >= 2 * HOST_BITS_PER_WIDE_INT)
 307     ;
 308   else if ((prec - count) >= HOST_BITS_PER_WIDE_INT)
 309     {
 310       *hv &= ~((HOST_WIDE_INT) (-1) << (prec - count - HOST_BITS_PER_WIDE_INT));
 311       *hv |= signmask << (prec - count - HOST_BITS_PER_WIDE_INT);
 312     }
 313   else
 314     {
 315       *hv = signmask;
 316       *lv &= ~((unsigned HOST_WIDE_INT) (-1) << (prec - count));
 317       *lv |= signmask << (prec - count);
 318     }
 319 }
 320
 321 /* Divide doubleword integer LNUM, HNUM by doubleword integer LDEN, HDEN
 322    for a quotient (stored in *LQUO, *HQUO) and remainder (in *LREM, *HREM).
 323    CODE is a tree code for a kind of division, one of
 324    TRUNC_DIV_EXPR, FLOOR_DIV_EXPR, CEIL_DIV_EXPR, ROUND_DIV_EXPR
 325    or EXACT_DIV_EXPR
 326    It controls how the quotient is rounded to an integer.
 327    Return nonzero if the operation overflows.
 328    UNS nonzero says do unsigned division.  */
 329
 330 int
 331 div_and_round_double (unsigned code, int uns,
 332                       /* num == numerator == dividend */
 333                       unsigned HOST_WIDE_INT lnum_orig,
 334                       HOST_WIDE_INT hnum_orig,
 335                       /* den == denominator == divisor */
 336                       unsigned HOST_WIDE_INT lden_orig,
 337                       HOST_WIDE_INT hden_orig,
 338                       unsigned HOST_WIDE_INT *lquo,
 339                       HOST_WIDE_INT *hquo, unsigned HOST_WIDE_INT *lrem,
 340                       HOST_WIDE_INT *hrem)
 341 {
 342   int quo_neg = 0;
 343   HOST_WIDE_INT num[4 + 1];     /* extra element for scaling.  */
 344   HOST_WIDE_INT den[4], quo[4];
 345   int i, j;
 346   unsigned HOST_WIDE_INT work;
 347   unsigned HOST_WIDE_INT carry = 0;
 348   unsigned HOST_WIDE_INT lnum = lnum_orig;
 349   HOST_WIDE_INT hnum = hnum_orig;
 350   unsigned HOST_WIDE_INT lden = lden_orig;
 351   HOST_WIDE_INT hden = hden_orig;
 352   int overflow = 0;
 353
 354   if (hden == 0 && lden == 0)
 355     overflow = 1, lden = 1;
 356
 357   /* Calculate quotient sign and convert operands to unsigned.  */
 358   if (!uns)
 359     {
 360       if (hnum < 0)
 361         {
 362           quo_neg = ~ quo_neg;
 363           /* (minimum integer) / (-1) is the only overflow case.  */
 364           if (neg_double (lnum, hnum, &lnum, &hnum)
 365               && ((HOST_WIDE_INT) lden & hden) == -1)
 366             overflow = 1;
 367         }
 368       if (hden < 0)
 369         {
 370           quo_neg = ~ quo_neg;
 371           neg_double (lden, hden, &lden, &hden);
 372         }
 373     }
 374
 375   if (hnum == 0 && hden == 0)
 376     {                           /* single precision */
 377       *hquo = *hrem = 0;
 378       /* This unsigned division rounds toward zero.  */
 379       *lquo = lnum / lden;
 380       goto finish_up;
 381     }
 382
 383   if (hnum == 0)
 384     {                           /* trivial case: dividend < divisor */
 385       /* hden != 0 already checked.  */
 386       *hquo = *lquo = 0;
 387       *hrem = hnum;
 388       *lrem = lnum;
 389       goto finish_up;
 390     }
 391
 392   memset (quo, 0, sizeof quo);
 393
 394   memset (num, 0, sizeof num);  /* to zero 9th element */
 395   memset (den, 0, sizeof den);
 396
 397   encode (num, lnum, hnum);
 398   encode (den, lden, hden);
 399
 400   /* Special code for when the divisor < BASE.  */
 401   if (hden == 0 && lden < (unsigned HOST_WIDE_INT) BASE)
 402     {
 403       /* hnum != 0 already checked.  */
 404       for (i = 4 - 1; i >= 0; i--)
 405         {
 406           work = num[i] + carry * BASE;
 407           quo[i] = work / lden;
 408           carry = work % lden;
 409         }
 410     }
 411   else
 412     {
 413       /* Full double precision division,
 414          with thanks to Don Knuth's "Seminumerical Algorithms".  */
 415       int num_hi_sig, den_hi_sig;
 416       unsigned HOST_WIDE_INT quo_est, scale;
 417
 418       /* Find the highest nonzero divisor digit.  */
 419       for (i = 4 - 1;; i--)
 420         if (den[i] != 0)
 421           {
 422             den_hi_sig = i;
 423             break;
 424           }
 425
 426       /* Insure that the first digit of the divisor is at least BASE/2.
 427          This is required by the quotient digit estimation algorithm.  */
 428
 429       scale = BASE / (den[den_hi_sig] + 1);
 430       if (scale > 1)
 431         {               /* scale divisor and dividend */
 432           carry = 0;
 433           for (i = 0; i <= 4 - 1; i++)
 434             {
 435               work = (num[i] * scale) + carry;
 436               num[i] = LOWPART (work);
 437               carry = HIGHPART (work);
 438             }
 439
 440           num[4] = carry;
 441           carry = 0;
 442           for (i = 0; i <= 4 - 1; i++)
 443             {
 444               work = (den[i] * scale) + carry;
 445               den[i] = LOWPART (work);
 446               carry = HIGHPART (work);
 447               if (den[i] != 0) den_hi_sig = i;
 448             }
 449         }
 450
 451       num_hi_sig = 4;
 452
 453       /* Main loop */
 454       for (i = num_hi_sig - den_hi_sig - 1; i >= 0; i--)
 455         {
 456           /* Guess the next quotient digit, quo_est, by dividing the first
 457              two remaining dividend digits by the high order quotient digit.
 458              quo_est is never low and is at most 2 high.  */
 459           unsigned HOST_WIDE_INT tmp;
 460
 461           num_hi_sig = i + den_hi_sig + 1;
 462           work = num[num_hi_sig] * BASE + num[num_hi_sig - 1];
 463           if (num[num_hi_sig] != den[den_hi_sig])
 464             quo_est = work / den[den_hi_sig];
 465           else
 466             quo_est = BASE - 1;
 467
 468           /* Refine quo_est so it's usually correct, and at most one high.  */
 469           tmp = work - quo_est * den[den_hi_sig];
 470           if (tmp < BASE
 471               && (den[den_hi_sig - 1] * quo_est
 472                   > (tmp * BASE + num[num_hi_sig - 2])))
 473             quo_est--;
 474
 475           /* Try QUO_EST as the quotient digit, by multiplying the
 476              divisor by QUO_EST and subtracting from the remaining dividend.
 477              Keep in mind that QUO_EST is the I - 1st digit.  */
 478
 479           carry = 0;
 480           for (j = 0; j <= den_hi_sig; j++)
 481             {
 482               work = quo_est * den[j] + carry;
 483               carry = HIGHPART (work);
 484               work = num[i + j] - LOWPART (work);
 485               num[i + j] = LOWPART (work);
 486               carry += HIGHPART (work) != 0;
 487             }
 488
 489           /* If quo_est was high by one, then num[i] went negative and
 490              we need to correct things.  */
 491           if (num[num_hi_sig] < (HOST_WIDE_INT) carry)
 492             {
 493               quo_est--;
 494               carry = 0;                /* add divisor back in */
 495               for (j = 0; j <= den_hi_sig; j++)
 496                 {
 497                   work = num[i + j] + den[j] + carry;
 498                   carry = HIGHPART (work);
 499                   num[i + j] = LOWPART (work);
 500                 }
 501
 502               num [num_hi_sig] += carry;
 503             }
 504
 505           /* Store the quotient digit.  */
 506           quo[i] = quo_est;
 507         }
 508     }
 509
 510   decode (quo, lquo, hquo);
 511
 512  finish_up:
 513   /* If result is negative, make it so.  */
 514   if (quo_neg)
 515     neg_double (*lquo, *hquo, lquo, hquo);
 516
 517   /* Compute trial remainder:  rem = num - (quo * den)  */
 518   mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
 519   neg_double (*lrem, *hrem, lrem, hrem);
 520   add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
 521
 522   switch (code)
 523     {
 524     case TRUNC_DIV_EXPR:
 525     case TRUNC_MOD_EXPR:        /* round toward zero */
 526     case EXACT_DIV_EXPR:        /* for this one, it shouldn't matter */
 527       return overflow;
 528
 529     case FLOOR_DIV_EXPR:
 530     case FLOOR_MOD_EXPR:        /* round toward negative infinity */
 531       if (quo_neg && (*lrem != 0 || *hrem != 0))   /* ratio < 0 && rem != 0 */
 532         {
 533           /* quo = quo - 1;  */
 534           add_double (*lquo, *hquo, (HOST_WIDE_INT) -1, (HOST_WIDE_INT)  -1,
 535                       lquo, hquo);
 536         }
 537       else
 538         return overflow;
 539       break;
 540
 541     case CEIL_DIV_EXPR:
 542     case CEIL_MOD_EXPR:         /* round toward positive infinity */
 543       if (!quo_neg && (*lrem != 0 || *hrem != 0))  /* ratio > 0 && rem != 0 */
 544         {
 545           add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
 546                       lquo, hquo);
 547         }
 548       else
 549         return overflow;
 550       break;
 551
 552     case ROUND_DIV_EXPR:
 553     case ROUND_MOD_EXPR:        /* round to closest integer */
 554       {
 555         unsigned HOST_WIDE_INT labs_rem = *lrem;
 556         HOST_WIDE_INT habs_rem = *hrem;
 557         unsigned HOST_WIDE_INT labs_den = lden, ltwice;
 558         HOST_WIDE_INT habs_den = hden, htwice;
 559
 560         /* Get absolute values.  */
 561         if (*hrem < 0)
 562           neg_double (*lrem, *hrem, &labs_rem, &habs_rem);
 563         if (hden < 0)
 564           neg_double (lden, hden, &labs_den, &habs_den);
 565
 566         /* If (2 * abs (lrem) >= abs (lden)), adjust the quotient.  */
 567         mul_double ((HOST_WIDE_INT) 2, (HOST_WIDE_INT) 0,
 568                     labs_rem, habs_rem, &ltwice, &htwice);
 569
 570         if (((unsigned HOST_WIDE_INT) habs_den
 571              < (unsigned HOST_WIDE_INT) htwice)
 572             || (((unsigned HOST_WIDE_INT) habs_den
 573                  == (unsigned HOST_WIDE_INT) htwice)
 574                 && (labs_den <= ltwice)))
 575           {
 576             if (*hquo < 0)
 577               /* quo = quo - 1;  */
 578               add_double (*lquo, *hquo,
 579                           (HOST_WIDE_INT) -1, (HOST_WIDE_INT) -1, lquo, hquo);
 580             else
 581               /* quo = quo + 1; */
 582               add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
 583                           lquo, hquo);
 584           }
 585         else
 586           return overflow;
 587       }
 588       break;
 589
 590     default:
 591       gcc_unreachable ();
 592     }
 593
 594   /* Compute true remainder:  rem = num - (quo * den)  */
 595   mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
 596   neg_double (*lrem, *hrem, lrem, hrem);
 597   add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
 598   return overflow;
 599 }
 600
 601
 602 /* Returns mask for PREC bits.  */
 603
 604 double_int
 605 double_int_mask (unsigned prec)
 606 {
 607   unsigned HOST_WIDE_INT m;
 608   double_int mask;
 609
 610   if (prec > HOST_BITS_PER_WIDE_INT)
 611     {
 612       prec -= HOST_BITS_PER_WIDE_INT;
 613       m = ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1;
 614       mask.high = (HOST_WIDE_INT) m;
 615       mask.low = ALL_ONES;
 616     }
 617   else
 618     {
 619       mask.high = 0;
 620       mask.low = ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1;
 621     }
 622
 623   return mask;
 624 }
 625
 626 /* Clears the bits of CST over the precision PREC.  If UNS is false, the bits
 627    outside of the precision are set to the sign bit (i.e., the PREC-th one),
 628    otherwise they are set to zero.
 629
 630    This corresponds to returning the value represented by PREC lowermost bits
 631    of CST, with the given signedness.  */
 632
 633 double_int
 634 double_int_ext (double_int cst, unsigned prec, bool uns)
 635 {
 636   if (uns)
 637     return double_int_zext (cst, prec);
 638   else
 639     return double_int_sext (cst, prec);
 640 }
 641
 642 /* The same as double_int_ext with UNS = true.  */
 643
 644 double_int
 645 double_int_zext (double_int cst, unsigned prec)
 646 {
 647   double_int mask = double_int_mask (prec);
 648   double_int r;
 649
 650   r.low = cst.low & mask.low;
 651   r.high = cst.high & mask.high;
 652
 653   return r;
 654 }
 655
 656 /* The same as double_int_ext with UNS = false.  */
 657
 658 double_int
 659 double_int_sext (double_int cst, unsigned prec)
 660 {
 661   double_int mask = double_int_mask (prec);
 662   double_int r;
 663   unsigned HOST_WIDE_INT snum;
 664
 665   if (prec <= HOST_BITS_PER_WIDE_INT)
 666     snum = cst.low;
 667   else
 668     {
 669       prec -= HOST_BITS_PER_WIDE_INT;
 670       snum = (unsigned HOST_WIDE_INT) cst.high;
 671     }
 672   if (((snum >> (prec - 1)) & 1) == 1)
 673     {
 674       r.low = cst.low | ~mask.low;
 675       r.high = cst.high | ~mask.high;
 676     }
 677   else
 678     {
 679       r.low = cst.low & mask.low;
 680       r.high = cst.high & mask.high;
 681     }
 682
 683   return r;
 684 }
 685
 686 /* Returns true if CST fits in signed HOST_WIDE_INT.  */
 687
 688 bool
 689 double_int_fits_in_shwi_p (double_int cst)
 690 {
 691   if (cst.high == 0)
 692     return (HOST_WIDE_INT) cst.low >= 0;
 693   else if (cst.high == -1)
 694     return (HOST_WIDE_INT) cst.low < 0;
 695   else
 696     return false;
 697 }
 698
 699 /* Returns true if CST fits in HOST_WIDE_INT if UNS is false, or in
 700    unsigned HOST_WIDE_INT if UNS is true.  */
 701
 702 bool
 703 double_int_fits_in_hwi_p (double_int cst, bool uns)
 704 {
 705   if (uns)
 706     return double_int_fits_in_uhwi_p (cst);
 707   else
 708     return double_int_fits_in_shwi_p (cst);
 709 }
 710
 711 /* Returns A * B.  */
 712
 713 double_int
 714 double_int_mul (double_int a, double_int b)
 715 {
 716   double_int ret;
 717   mul_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
 718   return ret;
 719 }
 720
 721 /* Returns A * B. If the operation overflows according to UNSIGNED_P,
 722    *OVERFLOW is set to nonzero.  */
 723
 724 double_int
 725 double_int_mul_with_sign (double_int a, double_int b,
 726                           bool unsigned_p, int *overflow)
 727 {
 728   double_int ret;
 729   *overflow = mul_double_with_sign (a.low, a.high, b.low, b.high,
 730                                     &ret.low, &ret.high, unsigned_p);
 731   return ret;
 732 }
 733
 734 /* Returns A + B.  */
 735
 736 double_int
 737 double_int_add (double_int a, double_int b)
 738 {
 739   double_int ret;
 740   add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
 741   return ret;
 742 }
 743
 744 /* Returns A - B.  */
 745
 746 double_int
 747 double_int_sub (double_int a, double_int b)
 748 {
 749   double_int ret;
 750   neg_double (b.low, b.high, &b.low, &b.high);
 751   add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
 752   return ret;
 753 }
 754
 755 /* Returns -A.  */
 756
 757 double_int
 758 double_int_neg (double_int a)
 759 {
 760   double_int ret;
 761   neg_double (a.low, a.high, &ret.low, &ret.high);
 762   return ret;
 763 }
 764
 765 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
 766    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
 767    must be included before tree.h.  The remainder after the division is
 768    stored to MOD.  */
 769
 770 double_int
 771 double_int_divmod (double_int a, double_int b, bool uns, unsigned code,
 772                    double_int *mod)
 773 {
 774   double_int ret;
 775
 776   div_and_round_double (code, uns, a.low, a.high,
 777                         b.low, b.high, &ret.low, &ret.high,
 778                         &mod->low, &mod->high);
 779   return ret;
 780 }
 781
 782 /* The same as double_int_divmod with UNS = false.  */
 783
 784 double_int
 785 double_int_sdivmod (double_int a, double_int b, unsigned code, double_int *mod)
 786 {
 787   return double_int_divmod (a, b, false, code, mod);
 788 }
 789
 790 /* The same as double_int_divmod with UNS = true.  */
 791
 792 double_int
 793 double_int_udivmod (double_int a, double_int b, unsigned code, double_int *mod)
 794 {
 795   return double_int_divmod (a, b, true, code, mod);
 796 }
 797
 798 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
 799    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
 800    must be included before tree.h.  */
 801
 802 double_int
 803 double_int_div (double_int a, double_int b, bool uns, unsigned code)
 804 {
 805   double_int mod;
 806
 807   return double_int_divmod (a, b, uns, code, &mod);
 808 }
 809
 810 /* The same as double_int_div with UNS = false.  */
 811
 812 double_int
 813 double_int_sdiv (double_int a, double_int b, unsigned code)
 814 {
 815   return double_int_div (a, b, false, code);
 816 }
 817
 818 /* The same as double_int_div with UNS = true.  */
 819
 820 double_int
 821 double_int_udiv (double_int a, double_int b, unsigned code)
 822 {
 823   return double_int_div (a, b, true, code);
 824 }
 825
 826 /* Returns A % B (computed as unsigned depending on UNS, and rounded as
 827    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
 828    must be included before tree.h.  */
 829
 830 double_int
 831 double_int_mod (double_int a, double_int b, bool uns, unsigned code)
 832 {
 833   double_int mod;
 834
 835   double_int_divmod (a, b, uns, code, &mod);
 836   return mod;
 837 }
 838
 839 /* The same as double_int_mod with UNS = false.  */
 840
 841 double_int
 842 double_int_smod (double_int a, double_int b, unsigned code)
 843 {
 844   return double_int_mod (a, b, false, code);
 845 }
 846
 847 /* The same as double_int_mod with UNS = true.  */
 848
 849 double_int
 850 double_int_umod (double_int a, double_int b, unsigned code)
 851 {
 852   return double_int_mod (a, b, true, code);
 853 }
 854
 855 /* Set BITPOS bit in A.  */
 856 double_int
 857 double_int_setbit (double_int a, unsigned bitpos)
 858 {
 859   if (bitpos < HOST_BITS_PER_WIDE_INT)
 860     a.low |= (unsigned HOST_WIDE_INT) 1 << bitpos;
 861   else
 862     a.high |= (HOST_WIDE_INT) 1 <<  (bitpos - HOST_BITS_PER_WIDE_INT);
 863
 864   return a;
 865 }
 866
 867 /* Count trailing zeros in A.  */
 868 int
 869 double_int_ctz (double_int a)
 870 {
 871   unsigned HOST_WIDE_INT w = a.low ? a.low : (unsigned HOST_WIDE_INT) a.high;
 872   unsigned bits = a.low ? 0 : HOST_BITS_PER_WIDE_INT;
 873   if (!w)
 874     return HOST_BITS_PER_DOUBLE_INT;
 875   bits += ctz_hwi (w);
 876   return bits;
 877 }
 878
 879 /* Shift A left by COUNT places keeping only PREC bits of result.  Shift
 880    right if COUNT is negative.  ARITH true specifies arithmetic shifting;
 881    otherwise use logical shift.  */
 882
 883 double_int
 884 double_int_lshift (double_int a, HOST_WIDE_INT count, unsigned int prec, bool arith)
 885 {
 886   double_int ret;
 887   lshift_double (a.low, a.high, count, prec, &ret.low, &ret.high, arith);
 888   return ret;
 889 }
 890
 891 /* Shift A rigth by COUNT places keeping only PREC bits of result.  Shift
 892    left if COUNT is negative.  ARITH true specifies arithmetic shifting;
 893    otherwise use logical shift.  */
 894
 895 double_int
 896 double_int_rshift (double_int a, HOST_WIDE_INT count, unsigned int prec, bool arith)
 897 {
 898   double_int ret;
 899   rshift_double (a.low, a.high, count, prec, &ret.low, &ret.high, arith);
 900   return ret;
 901 }
 902
 903 /* Rotate  A left by COUNT places keeping only PREC bits of result.
 904    Rotate right if COUNT is negative.  */
 905
 906 double_int
 907 double_int_lrotate (double_int a, HOST_WIDE_INT count, unsigned int prec)
 908 {
 909   double_int t1, t2;
 910
 911   count %= prec;
 912   if (count < 0)
 913     count += prec;
 914
 915   t1 = double_int_lshift (a, count, prec, false);
 916   t2 = double_int_rshift (a, prec - count, prec, false);
 917
 918   return double_int_ior (t1, t2);
 919 }
 920
 921 /* Rotate A rigth by COUNT places keeping only PREC bits of result.
 922    Rotate right if COUNT is negative.  */
 923
 924 double_int
 925 double_int_rrotate (double_int a, HOST_WIDE_INT count, unsigned int prec)
 926 {
 927   double_int t1, t2;
 928
 929   count %= prec;
 930   if (count < 0)
 931     count += prec;
 932
 933   t1 = double_int_rshift (a, count, prec, false);
 934   t2 = double_int_lshift (a, prec - count, prec, false);
 935
 936   return double_int_ior (t1, t2);
 937 }
 938
 939 /* Returns -1 if A < B, 0 if A == B and 1 if A > B.  Signedness of the
 940    comparison is given by UNS.  */
 941
 942 int
 943 double_int_cmp (double_int a, double_int b, bool uns)
 944 {
 945   if (uns)
 946     return double_int_ucmp (a, b);
 947   else
 948     return double_int_scmp (a, b);
 949 }
 950
 951 /* Compares two unsigned values A and B.  Returns -1 if A < B, 0 if A == B,
 952    and 1 if A > B.  */
 953
 954 int
 955 double_int_ucmp (double_int a, double_int b)
 956 {
 957   if ((unsigned HOST_WIDE_INT) a.high < (unsigned HOST_WIDE_INT) b.high)
 958     return -1;
 959   if ((unsigned HOST_WIDE_INT) a.high > (unsigned HOST_WIDE_INT) b.high)
 960     return 1;
 961   if (a.low < b.low)
 962     return -1;
 963   if (a.low > b.low)
 964     return 1;
 965
 966   return 0;
 967 }
 968
 969 /* Compares two signed values A and B.  Returns -1 if A < B, 0 if A == B,
 970    and 1 if A > B.  */
 971
 972 int
 973 double_int_scmp (double_int a, double_int b)
 974 {
 975   if (a.high < b.high)
 976     return -1;
 977   if (a.high > b.high)
 978     return 1;
 979   if (a.low < b.low)
 980     return -1;
 981   if (a.low > b.low)
 982     return 1;
 983
 984   return 0;
 985 }
 986
 987 /* Compares two values A and B.  Returns max value.  Signedness of the
 988    comparison is given by UNS.  */
 989
 990 double_int
 991 double_int_max (double_int a, double_int b, bool uns)
 992 {
 993   return (double_int_cmp (a, b, uns) == 1) ? a : b;
 994 }
 995
 996 /* Compares two signed values A and B.  Returns max value.  */
 997
 998 double_int double_int_smax (double_int a, double_int b)
 999 {
1000   return (double_int_scmp (a, b) == 1) ? a : b;
1001 }
1002
1003 /* Compares two unsigned values A and B.  Returns max value.  */
1004
1005 double_int double_int_umax (double_int a, double_int b)
1006 {
1007   return (double_int_ucmp (a, b) == 1) ? a : b;
1008 }
1009
1010 /* Compares two values A and B.  Returns mix value.  Signedness of the
1011    comparison is given by UNS.  */
1012
1013 double_int double_int_min (double_int a, double_int b, bool uns)
1014 {
1015   return (double_int_cmp (a, b, uns) == -1) ? a : b;
1016 }
1017
1018 /* Compares two signed values A and B.  Returns min value.  */
1019
1020 double_int double_int_smin (double_int a, double_int b)
1021 {
1022   return (double_int_scmp (a, b) == -1) ? a : b;
1023 }
1024
1025 /* Compares two unsigned values A and B.  Returns min value.  */
1026
1027 double_int double_int_umin (double_int a, double_int b)
1028 {
1029   return (double_int_ucmp (a, b) == -1) ? a : b;
1030 }
1031
1032 /* Splits last digit of *CST (taken as unsigned) in BASE and returns it.  */
1033
1034 static unsigned
1035 double_int_split_digit (double_int *cst, unsigned base)
1036 {
1037   unsigned HOST_WIDE_INT resl, reml;
1038   HOST_WIDE_INT resh, remh;
1039
1040   div_and_round_double (FLOOR_DIV_EXPR, true, cst->low, cst->high, base, 0,
1041                         &resl, &resh, &reml, &remh);
1042   cst->high = resh;
1043   cst->low = resl;
1044
1045   return reml;
1046 }
1047
1048 /* Dumps CST to FILE.  If UNS is true, CST is considered to be unsigned,
1049    otherwise it is signed.  */
1050
1051 void
1052 dump_double_int (FILE *file, double_int cst, bool uns)
1053 {
1054   unsigned digits[100], n;
1055   int i;
1056
1057   if (double_int_zero_p (cst))
1058     {
1059       fprintf (file, "0");
1060       return;
1061     }
1062
1063   if (!uns && double_int_negative_p (cst))
1064     {
1065       fprintf (file, "-");
1066       cst = double_int_neg (cst);
1067     }
1068
1069   for (n = 0; !double_int_zero_p (cst); n++)
1070     digits[n] = double_int_split_digit (&cst, 10);
1071   for (i = n - 1; i >= 0; i--)
1072     fprintf (file, "%u", digits[i]);
1073 }
1074
1075
1076 /* Sets RESULT to VAL, taken unsigned if UNS is true and as signed
1077    otherwise.  */
1078
1079 void
1080 mpz_set_double_int (mpz_t result, double_int val, bool uns)
1081 {
1082   bool negate = false;
1083   unsigned HOST_WIDE_INT vp[2];
1084
1085   if (!uns && double_int_negative_p (val))
1086     {
1087       negate = true;
1088       val = double_int_neg (val);
1089     }
1090
1091   vp[0] = val.low;
1092   vp[1] = (unsigned HOST_WIDE_INT) val.high;
1093   mpz_import (result, 2, -1, sizeof (HOST_WIDE_INT), 0, 0, vp);
1094
1095   if (negate)
1096     mpz_neg (result, result);
1097 }
1098
1099 /* Returns VAL converted to TYPE.  If WRAP is true, then out-of-range
1100    values of VAL will be wrapped; otherwise, they will be set to the
1101    appropriate minimum or maximum TYPE bound.  */
1102
1103 double_int
1104 mpz_get_double_int (const_tree type, mpz_t val, bool wrap)
1105 {
1106   unsigned HOST_WIDE_INT *vp;
1107   size_t count, numb;
1108   double_int res;
1109
1110   if (!wrap)
1111     {
1112       mpz_t min, max;
1113
1114       mpz_init (min);
1115       mpz_init (max);
1116       get_type_static_bounds (type, min, max);
1117
1118       if (mpz_cmp (val, min) < 0)
1119         mpz_set (val, min);
1120       else if (mpz_cmp (val, max) > 0)
1121         mpz_set (val, max);
1122
1123       mpz_clear (min);
1124       mpz_clear (max);
1125     }
1126
1127   /* Determine the number of unsigned HOST_WIDE_INT that are required
1128      for representing the value.  The code to calculate count is
1129      extracted from the GMP manual, section "Integer Import and Export":
1130      http://gmplib.org/manual/Integer-Import-and-Export.html  */
1131   numb = 8*sizeof(HOST_WIDE_INT);
1132   count = (mpz_sizeinbase (val, 2) + numb-1) / numb;
1133   if (count < 2)
1134     count = 2;
1135   vp = (unsigned HOST_WIDE_INT *) alloca (count * sizeof(HOST_WIDE_INT));
1136
1137   vp[0] = 0;
1138   vp[1] = 0;
1139   mpz_export (vp, &count, -1, sizeof (HOST_WIDE_INT), 0, 0, val);
1140
1141   gcc_assert (wrap || count <= 2);
1142
1143   res.low = vp[0];
1144   res.high = (HOST_WIDE_INT) vp[1];
1145
1146   res = double_int_ext (res, TYPE_PRECISION (type), TYPE_UNSIGNED (type));
1147   if (mpz_sgn (val) < 0)
1148     res = double_int_neg (res);
1149
1150   return res;
1151 }