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