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