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"
  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.  */
 722
 723 double_int
 724 double_int_add (double_int a, double_int b)
 725 {
 726   double_int ret;
 727   add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
 728   return ret;
 729 }
 730
 731 /* Returns A - B.  */
 732
 733 double_int
 734 double_int_sub (double_int a, double_int b)
 735 {
 736   double_int ret;
 737   neg_double (b.low, b.high, &b.low, &b.high);
 738   add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
 739   return ret;
 740 }
 741
 742 /* Returns -A.  */
 743
 744 double_int
 745 double_int_neg (double_int a)
 746 {
 747   double_int ret;
 748   neg_double (a.low, a.high, &ret.low, &ret.high);
 749   return ret;
 750 }
 751
 752 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
 753    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
 754    must be included before tree.h.  The remainder after the division is
 755    stored to MOD.  */
 756
 757 double_int
 758 double_int_divmod (double_int a, double_int b, bool uns, unsigned code,
 759                    double_int *mod)
 760 {
 761   double_int ret;
 762
 763   div_and_round_double (code, uns, a.low, a.high,
 764                         b.low, b.high, &ret.low, &ret.high,
 765                         &mod->low, &mod->high);
 766   return ret;
 767 }
 768
 769 /* The same as double_int_divmod with UNS = false.  */
 770
 771 double_int
 772 double_int_sdivmod (double_int a, double_int b, unsigned code, double_int *mod)
 773 {
 774   return double_int_divmod (a, b, false, code, mod);
 775 }
 776
 777 /* The same as double_int_divmod with UNS = true.  */
 778
 779 double_int
 780 double_int_udivmod (double_int a, double_int b, unsigned code, double_int *mod)
 781 {
 782   return double_int_divmod (a, b, true, code, mod);
 783 }
 784
 785 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
 786    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
 787    must be included before tree.h.  */
 788
 789 double_int
 790 double_int_div (double_int a, double_int b, bool uns, unsigned code)
 791 {
 792   double_int mod;
 793
 794   return double_int_divmod (a, b, uns, code, &mod);
 795 }
 796
 797 /* The same as double_int_div with UNS = false.  */
 798
 799 double_int
 800 double_int_sdiv (double_int a, double_int b, unsigned code)
 801 {
 802   return double_int_div (a, b, false, code);
 803 }
 804
 805 /* The same as double_int_div with UNS = true.  */
 806
 807 double_int
 808 double_int_udiv (double_int a, double_int b, unsigned code)
 809 {
 810   return double_int_div (a, b, true, code);
 811 }
 812
 813 /* Returns A % B (computed as unsigned depending on UNS, and rounded as
 814    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
 815    must be included before tree.h.  */
 816
 817 double_int
 818 double_int_mod (double_int a, double_int b, bool uns, unsigned code)
 819 {
 820   double_int mod;
 821
 822   double_int_divmod (a, b, uns, code, &mod);
 823   return mod;
 824 }
 825
 826 /* The same as double_int_mod with UNS = false.  */
 827
 828 double_int
 829 double_int_smod (double_int a, double_int b, unsigned code)
 830 {
 831   return double_int_mod (a, b, false, code);
 832 }
 833
 834 /* The same as double_int_mod with UNS = true.  */
 835
 836 double_int
 837 double_int_umod (double_int a, double_int b, unsigned code)
 838 {
 839   return double_int_mod (a, b, true, code);
 840 }
 841
 842 /* Set BITPOS bit in A.  */
 843 double_int
 844 double_int_setbit (double_int a, unsigned bitpos)
 845 {
 846   if (bitpos < HOST_BITS_PER_WIDE_INT)
 847     a.low |= (unsigned HOST_WIDE_INT) 1 << bitpos;
 848   else
 849     a.high |= (HOST_WIDE_INT) 1 <<  (bitpos - HOST_BITS_PER_WIDE_INT);
 850
 851   return a;
 852 }
 853
 854 /* Count trailing zeros in A.  */
 855 int
 856 double_int_ctz (double_int a)
 857 {
 858   unsigned HOST_WIDE_INT w = a.low ? a.low : (unsigned HOST_WIDE_INT) a.high;
 859   unsigned bits = a.low ? 0 : HOST_BITS_PER_WIDE_INT;
 860   if (!w)
 861     return HOST_BITS_PER_DOUBLE_INT;
 862   bits += ctz_hwi (w);
 863   return bits;
 864 }
 865
 866 /* Shift A left by COUNT places keeping only PREC bits of result.  Shift
 867    right if COUNT is negative.  ARITH true specifies arithmetic shifting;
 868    otherwise use logical shift.  */
 869
 870 double_int
 871 double_int_lshift (double_int a, HOST_WIDE_INT count, unsigned int prec, bool arith)
 872 {
 873   double_int ret;
 874   lshift_double (a.low, a.high, count, prec, &ret.low, &ret.high, arith);
 875   return ret;
 876 }
 877
 878 /* Shift A rigth by COUNT places keeping only PREC bits of result.  Shift
 879    left if COUNT is negative.  ARITH true specifies arithmetic shifting;
 880    otherwise use logical shift.  */
 881
 882 double_int
 883 double_int_rshift (double_int a, HOST_WIDE_INT count, unsigned int prec, bool arith)
 884 {
 885   double_int ret;
 886   rshift_double (a.low, a.high, count, prec, &ret.low, &ret.high, arith);
 887   return ret;
 888 }
 889
 890 /* Rotate  A left by COUNT places keeping only PREC bits of result.
 891    Rotate right if COUNT is negative.  */
 892
 893 double_int
 894 double_int_lrotate (double_int a, HOST_WIDE_INT count, unsigned int prec)
 895 {
 896   double_int t1, t2;
 897
 898   count %= prec;
 899   if (count < 0)
 900     count += prec;
 901
 902   t1 = double_int_lshift (a, count, prec, false);
 903   t2 = double_int_rshift (a, prec - count, prec, false);
 904
 905   return double_int_ior (t1, t2);
 906 }
 907
 908 /* Rotate A rigth by COUNT places keeping only PREC bits of result.
 909    Rotate right if COUNT is negative.  */
 910
 911 double_int
 912 double_int_rrotate (double_int a, HOST_WIDE_INT count, unsigned int prec)
 913 {
 914   double_int t1, t2;
 915
 916   count %= prec;
 917   if (count < 0)
 918     count += prec;
 919
 920   t1 = double_int_rshift (a, count, prec, false);
 921   t2 = double_int_lshift (a, prec - count, prec, false);
 922
 923   return double_int_ior (t1, t2);
 924 }
 925
 926 /* Returns -1 if A < B, 0 if A == B and 1 if A > B.  Signedness of the
 927    comparison is given by UNS.  */
 928
 929 int
 930 double_int_cmp (double_int a, double_int b, bool uns)
 931 {
 932   if (uns)
 933     return double_int_ucmp (a, b);
 934   else
 935     return double_int_scmp (a, b);
 936 }
 937
 938 /* Compares two unsigned values A and B.  Returns -1 if A < B, 0 if A == B,
 939    and 1 if A > B.  */
 940
 941 int
 942 double_int_ucmp (double_int a, double_int b)
 943 {
 944   if ((unsigned HOST_WIDE_INT) a.high < (unsigned HOST_WIDE_INT) b.high)
 945     return -1;
 946   if ((unsigned HOST_WIDE_INT) a.high > (unsigned HOST_WIDE_INT) b.high)
 947     return 1;
 948   if (a.low < b.low)
 949     return -1;
 950   if (a.low > b.low)
 951     return 1;
 952
 953   return 0;
 954 }
 955
 956 /* Compares two signed values A and B.  Returns -1 if A < B, 0 if A == B,
 957    and 1 if A > B.  */
 958
 959 int
 960 double_int_scmp (double_int a, double_int b)
 961 {
 962   if (a.high < b.high)
 963     return -1;
 964   if (a.high > b.high)
 965     return 1;
 966   if (a.low < b.low)
 967     return -1;
 968   if (a.low > b.low)
 969     return 1;
 970
 971   return 0;
 972 }
 973
 974 /* Compares two values A and B.  Returns max value.  Signedness of the
 975    comparison is given by UNS.  */
 976
 977 double_int
 978 double_int_max (double_int a, double_int b, bool uns)
 979 {
 980   return (double_int_cmp (a, b, uns) == 1) ? a : b;
 981 }
 982
 983 /* Compares two signed values A and B.  Returns max value.  */
 984
 985 double_int double_int_smax (double_int a, double_int b)
 986 {
 987   return (double_int_scmp (a, b) == 1) ? a : b;
 988 }
 989
 990 /* Compares two unsigned values A and B.  Returns max value.  */
 991
 992 double_int double_int_umax (double_int a, double_int b)
 993 {
 994   return (double_int_ucmp (a, b) == 1) ? a : b;
 995 }
 996
 997 /* Compares two values A and B.  Returns mix value.  Signedness of the
 998    comparison is given by UNS.  */
 999
1000 double_int double_int_min (double_int a, double_int b, bool uns)
1001 {
1002   return (double_int_cmp (a, b, uns) == -1) ? a : b;
1003 }
1004
1005 /* Compares two signed values A and B.  Returns min value.  */
1006
1007 double_int double_int_smin (double_int a, double_int b)
1008 {
1009   return (double_int_scmp (a, b) == -1) ? a : b;
1010 }
1011
1012 /* Compares two unsigned values A and B.  Returns min value.  */
1013
1014 double_int double_int_umin (double_int a, double_int b)
1015 {
1016   return (double_int_ucmp (a, b) == -1) ? a : b;
1017 }
1018
1019 /* Splits last digit of *CST (taken as unsigned) in BASE and returns it.  */
1020
1021 static unsigned
1022 double_int_split_digit (double_int *cst, unsigned base)
1023 {
1024   unsigned HOST_WIDE_INT resl, reml;
1025   HOST_WIDE_INT resh, remh;
1026
1027   div_and_round_double (FLOOR_DIV_EXPR, true, cst->low, cst->high, base, 0,
1028                         &resl, &resh, &reml, &remh);
1029   cst->high = resh;
1030   cst->low = resl;
1031
1032   return reml;
1033 }
1034
1035 /* Dumps CST to FILE.  If UNS is true, CST is considered to be unsigned,
1036    otherwise it is signed.  */
1037
1038 void
1039 dump_double_int (FILE *file, double_int cst, bool uns)
1040 {
1041   unsigned digits[100], n;
1042   int i;
1043
1044   if (double_int_zero_p (cst))
1045     {
1046       fprintf (file, "0");
1047       return;
1048     }
1049
1050   if (!uns && double_int_negative_p (cst))
1051     {
1052       fprintf (file, "-");
1053       cst = double_int_neg (cst);
1054     }
1055
1056   for (n = 0; !double_int_zero_p (cst); n++)
1057     digits[n] = double_int_split_digit (&cst, 10);
1058   for (i = n - 1; i >= 0; i--)
1059     fprintf (file, "%u", digits[i]);
1060 }
1061
1062
1063 /* Sets RESULT to VAL, taken unsigned if UNS is true and as signed
1064    otherwise.  */
1065
1066 void
1067 mpz_set_double_int (mpz_t result, double_int val, bool uns)
1068 {
1069   bool negate = false;
1070   unsigned HOST_WIDE_INT vp[2];
1071
1072   if (!uns && double_int_negative_p (val))
1073     {
1074       negate = true;
1075       val = double_int_neg (val);
1076     }
1077
1078   vp[0] = val.low;
1079   vp[1] = (unsigned HOST_WIDE_INT) val.high;
1080   mpz_import (result, 2, -1, sizeof (HOST_WIDE_INT), 0, 0, vp);
1081
1082   if (negate)
1083     mpz_neg (result, result);
1084 }
1085
1086 /* Returns VAL converted to TYPE.  If WRAP is true, then out-of-range
1087    values of VAL will be wrapped; otherwise, they will be set to the
1088    appropriate minimum or maximum TYPE bound.  */
1089
1090 double_int
1091 mpz_get_double_int (const_tree type, mpz_t val, bool wrap)
1092 {
1093   unsigned HOST_WIDE_INT *vp;
1094   size_t count, numb;
1095   double_int res;
1096
1097   if (!wrap)
1098     {
1099       mpz_t min, max;
1100
1101       mpz_init (min);
1102       mpz_init (max);
1103       get_type_static_bounds (type, min, max);
1104
1105       if (mpz_cmp (val, min) < 0)
1106         mpz_set (val, min);
1107       else if (mpz_cmp (val, max) > 0)
1108         mpz_set (val, max);
1109
1110       mpz_clear (min);
1111       mpz_clear (max);
1112     }
1113
1114   /* Determine the number of unsigned HOST_WIDE_INT that are required
1115      for representing the value.  The code to calculate count is
1116      extracted from the GMP manual, section "Integer Import and Export":
1117      http://gmplib.org/manual/Integer-Import-and-Export.html  */
1118   numb = 8*sizeof(HOST_WIDE_INT);
1119   count = (mpz_sizeinbase (val, 2) + numb-1) / numb;
1120   if (count < 2)
1121     count = 2;
1122   vp = (unsigned HOST_WIDE_INT *) alloca (count * sizeof(HOST_WIDE_INT));
1123
1124   vp[0] = 0;
1125   vp[1] = 0;
1126   mpz_export (vp, &count, -1, sizeof (HOST_WIDE_INT), 0, 0, val);
1127
1128   gcc_assert (wrap || count <= 2);
1129
1130   res.low = vp[0];
1131   res.high = (HOST_WIDE_INT) vp[1];
1132
1133   res = double_int_ext (res, TYPE_PRECISION (type), TYPE_UNSIGNED (type));
1134   if (mpz_sgn (val) < 0)
1135     res = double_int_neg (res);
1136
1137   return res;
1138 }