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