gcc/double-int.c

   1 /* Operations with long integers.
   2    Copyright (C) 2006, 2007, 2009, 2010, 2012 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 >= HOST_BITS_PER_DOUBLE_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) >= HOST_BITS_PER_DOUBLE_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 >= HOST_BITS_PER_DOUBLE_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 >= HOST_BITS_PER_DOUBLE_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 /* Returns a maximum value for signed or unsigned integer
 620    of precision PREC.  */
 621
 622 double_int
 623 double_int_max_value (unsigned int prec, bool uns)
 624 {
 625   return double_int_mask (prec - (uns ? 0 : 1));
 626 }
 627
 628 /* Returns a minimum value for signed or unsigned integer
 629    of precision PREC.  */
 630
 631 double_int
 632 double_int_min_value (unsigned int prec, bool uns)
 633 {
 634   if (uns)
 635     return double_int_zero;
 636   return double_int_lshift (double_int_one, prec - 1, prec, false);
 637 }
 638
 639 /* Clears the bits of CST over the precision PREC.  If UNS is false, the bits
 640    outside of the precision are set to the sign bit (i.e., the PREC-th one),
 641    otherwise they are set to zero.
 642
 643    This corresponds to returning the value represented by PREC lowermost bits
 644    of CST, with the given signedness.  */
 645
 646 double_int
 647 double_int_ext (double_int cst, unsigned prec, bool uns)
 648 {
 649   if (uns)
 650     return double_int_zext (cst, prec);
 651   else
 652     return double_int_sext (cst, prec);
 653 }
 654
 655 /* The same as double_int_ext with UNS = true.  */
 656
 657 double_int
 658 double_int_zext (double_int cst, unsigned prec)
 659 {
 660   double_int mask = double_int_mask (prec);
 661   double_int r;
 662
 663   r.low = cst.low & mask.low;
 664   r.high = cst.high & mask.high;
 665
 666   return r;
 667 }
 668
 669 /* The same as double_int_ext with UNS = false.  */
 670
 671 double_int
 672 double_int_sext (double_int cst, unsigned prec)
 673 {
 674   double_int mask = double_int_mask (prec);
 675   double_int r;
 676   unsigned HOST_WIDE_INT snum;
 677
 678   if (prec <= HOST_BITS_PER_WIDE_INT)
 679     snum = cst.low;
 680   else
 681     {
 682       prec -= HOST_BITS_PER_WIDE_INT;
 683       snum = (unsigned HOST_WIDE_INT) cst.high;
 684     }
 685   if (((snum >> (prec - 1)) & 1) == 1)
 686     {
 687       r.low = cst.low | ~mask.low;
 688       r.high = cst.high | ~mask.high;
 689     }
 690   else
 691     {
 692       r.low = cst.low & mask.low;
 693       r.high = cst.high & mask.high;
 694     }
 695
 696   return r;
 697 }
 698
 699 /* Returns true if CST fits in signed HOST_WIDE_INT.  */
 700
 701 bool
 702 double_int_fits_in_shwi_p (double_int cst)
 703 {
 704   if (cst.high == 0)
 705     return (HOST_WIDE_INT) cst.low >= 0;
 706   else if (cst.high == -1)
 707     return (HOST_WIDE_INT) cst.low < 0;
 708   else
 709     return false;
 710 }
 711
 712 /* Returns true if CST fits in HOST_WIDE_INT if UNS is false, or in
 713    unsigned HOST_WIDE_INT if UNS is true.  */
 714
 715 bool
 716 double_int_fits_in_hwi_p (double_int cst, bool uns)
 717 {
 718   if (uns)
 719     return double_int_fits_in_uhwi_p (cst);
 720   else
 721     return double_int_fits_in_shwi_p (cst);
 722 }
 723
 724 /* Returns A * B.  */
 725
 726 double_int
 727 double_int_mul (double_int a, double_int b)
 728 {
 729   double_int ret;
 730   mul_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
 731   return ret;
 732 }
 733
 734 /* Returns A * B. If the operation overflows according to UNSIGNED_P,
 735    *OVERFLOW is set to nonzero.  */
 736
 737 double_int
 738 double_int_mul_with_sign (double_int a, double_int b,
 739                           bool unsigned_p, int *overflow)
 740 {
 741   double_int ret;
 742   *overflow = mul_double_with_sign (a.low, a.high, b.low, b.high,
 743                                     &ret.low, &ret.high, unsigned_p);
 744   return ret;
 745 }
 746
 747 /* Returns A + B.  */
 748
 749 double_int
 750 double_int_add (double_int a, double_int b)
 751 {
 752   double_int ret;
 753   add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
 754   return ret;
 755 }
 756
 757 /* Returns A - B.  */
 758
 759 double_int
 760 double_int_sub (double_int a, double_int b)
 761 {
 762   double_int ret;
 763   neg_double (b.low, b.high, &b.low, &b.high);
 764   add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
 765   return ret;
 766 }
 767
 768 /* Returns -A.  */
 769
 770 double_int
 771 double_int_neg (double_int a)
 772 {
 773   double_int ret;
 774   neg_double (a.low, a.high, &ret.low, &ret.high);
 775   return ret;
 776 }
 777
 778 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
 779    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
 780    must be included before tree.h.  The remainder after the division is
 781    stored to MOD.  */
 782
 783 double_int
 784 double_int_divmod (double_int a, double_int b, bool uns, unsigned code,
 785                    double_int *mod)
 786 {
 787   double_int ret;
 788
 789   div_and_round_double (code, uns, a.low, a.high,
 790                         b.low, b.high, &ret.low, &ret.high,
 791                         &mod->low, &mod->high);
 792   return ret;
 793 }
 794
 795 /* The same as double_int_divmod with UNS = false.  */
 796
 797 double_int
 798 double_int_sdivmod (double_int a, double_int b, unsigned code, double_int *mod)
 799 {
 800   return double_int_divmod (a, b, false, code, mod);
 801 }
 802
 803 /* The same as double_int_divmod with UNS = true.  */
 804
 805 double_int
 806 double_int_udivmod (double_int a, double_int b, unsigned code, double_int *mod)
 807 {
 808   return double_int_divmod (a, b, true, code, mod);
 809 }
 810
 811 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
 812    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
 813    must be included before tree.h.  */
 814
 815 double_int
 816 double_int_div (double_int a, double_int b, bool uns, unsigned code)
 817 {
 818   double_int mod;
 819
 820   return double_int_divmod (a, b, uns, code, &mod);
 821 }
 822
 823 /* The same as double_int_div with UNS = false.  */
 824
 825 double_int
 826 double_int_sdiv (double_int a, double_int b, unsigned code)
 827 {
 828   return double_int_div (a, b, false, code);
 829 }
 830
 831 /* The same as double_int_div with UNS = true.  */
 832
 833 double_int
 834 double_int_udiv (double_int a, double_int b, unsigned code)
 835 {
 836   return double_int_div (a, b, true, code);
 837 }
 838
 839 /* Returns A % B (computed as unsigned depending on UNS, and rounded as
 840    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
 841    must be included before tree.h.  */
 842
 843 double_int
 844 double_int_mod (double_int a, double_int b, bool uns, unsigned code)
 845 {
 846   double_int mod;
 847
 848   double_int_divmod (a, b, uns, code, &mod);
 849   return mod;
 850 }
 851
 852 /* The same as double_int_mod with UNS = false.  */
 853
 854 double_int
 855 double_int_smod (double_int a, double_int b, unsigned code)
 856 {
 857   return double_int_mod (a, b, false, code);
 858 }
 859
 860 /* The same as double_int_mod with UNS = true.  */
 861
 862 double_int
 863 double_int_umod (double_int a, double_int b, unsigned code)
 864 {
 865   return double_int_mod (a, b, true, code);
 866 }
 867
 868 /* Return TRUE iff PRODUCT is an integral multiple of FACTOR, and return
 869    the multiple in *MULTIPLE.  Otherwise return FALSE and leave *MULTIPLE
 870    unchanged.  */
 871
 872 bool
 873 double_int_multiple_of (double_int product, double_int factor,
 874                         bool unsigned_p, double_int *multiple)
 875 {
 876   double_int remainder;
 877   double_int quotient = double_int_divmod (product, factor, unsigned_p,
 878                                            TRUNC_DIV_EXPR, &remainder);
 879   if (double_int_zero_p (remainder))
 880     {
 881       *multiple = quotient;
 882       return true;
 883     }
 884
 885   return false;
 886 }
 887
 888 /* Set BITPOS bit in A.  */
 889 double_int
 890 double_int_setbit (double_int a, unsigned bitpos)
 891 {
 892   if (bitpos < HOST_BITS_PER_WIDE_INT)
 893     a.low |= (unsigned HOST_WIDE_INT) 1 << bitpos;
 894   else
 895     a.high |= (HOST_WIDE_INT) 1 <<  (bitpos - HOST_BITS_PER_WIDE_INT);
 896
 897   return a;
 898 }
 899
 900 /* Count trailing zeros in A.  */
 901 int
 902 double_int_ctz (double_int a)
 903 {
 904   unsigned HOST_WIDE_INT w = a.low ? a.low : (unsigned HOST_WIDE_INT) a.high;
 905   unsigned bits = a.low ? 0 : HOST_BITS_PER_WIDE_INT;
 906   if (!w)
 907     return HOST_BITS_PER_DOUBLE_INT;
 908   bits += ctz_hwi (w);
 909   return bits;
 910 }
 911
 912 /* Shift A left by COUNT places keeping only PREC bits of result.  Shift
 913    right if COUNT is negative.  ARITH true specifies arithmetic shifting;
 914    otherwise use logical shift.  */
 915
 916 double_int
 917 double_int_lshift (double_int a, HOST_WIDE_INT count, unsigned int prec, bool arith)
 918 {
 919   double_int ret;
 920   lshift_double (a.low, a.high, count, prec, &ret.low, &ret.high, arith);
 921   return ret;
 922 }
 923
 924 /* Shift A rigth by COUNT places keeping only PREC bits of result.  Shift
 925    left if COUNT is negative.  ARITH true specifies arithmetic shifting;
 926    otherwise use logical shift.  */
 927
 928 double_int
 929 double_int_rshift (double_int a, HOST_WIDE_INT count, unsigned int prec, bool arith)
 930 {
 931   double_int ret;
 932   lshift_double (a.low, a.high, -count, prec, &ret.low, &ret.high, arith);
 933   return ret;
 934 }
 935
 936 /* Rotate  A left by COUNT places keeping only PREC bits of result.
 937    Rotate right if COUNT is negative.  */
 938
 939 double_int
 940 double_int_lrotate (double_int a, HOST_WIDE_INT count, unsigned int prec)
 941 {
 942   double_int t1, t2;
 943
 944   count %= prec;
 945   if (count < 0)
 946     count += prec;
 947
 948   t1 = double_int_lshift (a, count, prec, false);
 949   t2 = double_int_rshift (a, prec - count, prec, false);
 950
 951   return double_int_ior (t1, t2);
 952 }
 953
 954 /* Rotate A rigth by COUNT places keeping only PREC bits of result.
 955    Rotate right if COUNT is negative.  */
 956
 957 double_int
 958 double_int_rrotate (double_int a, HOST_WIDE_INT count, unsigned int prec)
 959 {
 960   double_int t1, t2;
 961
 962   count %= prec;
 963   if (count < 0)
 964     count += prec;
 965
 966   t1 = double_int_rshift (a, count, prec, false);
 967   t2 = double_int_lshift (a, prec - count, prec, false);
 968
 969   return double_int_ior (t1, t2);
 970 }
 971
 972 /* Returns -1 if A < B, 0 if A == B and 1 if A > B.  Signedness of the
 973    comparison is given by UNS.  */
 974
 975 int
 976 double_int_cmp (double_int a, double_int b, bool uns)
 977 {
 978   if (uns)
 979     return double_int_ucmp (a, b);
 980   else
 981     return double_int_scmp (a, b);
 982 }
 983
 984 /* Compares two unsigned values A and B.  Returns -1 if A < B, 0 if A == B,
 985    and 1 if A > B.  */
 986
 987 int
 988 double_int_ucmp (double_int a, double_int b)
 989 {
 990   if ((unsigned HOST_WIDE_INT) a.high < (unsigned HOST_WIDE_INT) b.high)
 991     return -1;
 992   if ((unsigned HOST_WIDE_INT) a.high > (unsigned HOST_WIDE_INT) b.high)
 993     return 1;
 994   if (a.low < b.low)
 995     return -1;
 996   if (a.low > b.low)
 997     return 1;
 998
 999   return 0;
1000 }
1001
1002 /* Compares two signed values A and B.  Returns -1 if A < B, 0 if A == B,
1003    and 1 if A > B.  */
1004
1005 int
1006 double_int_scmp (double_int a, double_int b)
1007 {
1008   if (a.high < b.high)
1009     return -1;
1010   if (a.high > b.high)
1011     return 1;
1012   if (a.low < b.low)
1013     return -1;
1014   if (a.low > b.low)
1015     return 1;
1016
1017   return 0;
1018 }
1019
1020 /* Compares two values A and B.  Returns max value.  Signedness of the
1021    comparison is given by UNS.  */
1022
1023 double_int
1024 double_int_max (double_int a, double_int b, bool uns)
1025 {
1026   return (double_int_cmp (a, b, uns) == 1) ? a : b;
1027 }
1028
1029 /* Compares two signed values A and B.  Returns max value.  */
1030
1031 double_int double_int_smax (double_int a, double_int b)
1032 {
1033   return (double_int_scmp (a, b) == 1) ? a : b;
1034 }
1035
1036 /* Compares two unsigned values A and B.  Returns max value.  */
1037
1038 double_int double_int_umax (double_int a, double_int b)
1039 {
1040   return (double_int_ucmp (a, b) == 1) ? a : b;
1041 }
1042
1043 /* Compares two values A and B.  Returns mix value.  Signedness of the
1044    comparison is given by UNS.  */
1045
1046 double_int double_int_min (double_int a, double_int b, bool uns)
1047 {
1048   return (double_int_cmp (a, b, uns) == -1) ? a : b;
1049 }
1050
1051 /* Compares two signed values A and B.  Returns min value.  */
1052
1053 double_int double_int_smin (double_int a, double_int b)
1054 {
1055   return (double_int_scmp (a, b) == -1) ? a : b;
1056 }
1057
1058 /* Compares two unsigned values A and B.  Returns min value.  */
1059
1060 double_int double_int_umin (double_int a, double_int b)
1061 {
1062   return (double_int_ucmp (a, b) == -1) ? a : b;
1063 }
1064
1065 /* Splits last digit of *CST (taken as unsigned) in BASE and returns it.  */
1066
1067 static unsigned
1068 double_int_split_digit (double_int *cst, unsigned base)
1069 {
1070   unsigned HOST_WIDE_INT resl, reml;
1071   HOST_WIDE_INT resh, remh;
1072
1073   div_and_round_double (FLOOR_DIV_EXPR, true, cst->low, cst->high, base, 0,
1074                         &resl, &resh, &reml, &remh);
1075   cst->high = resh;
1076   cst->low = resl;
1077
1078   return reml;
1079 }
1080
1081 /* Dumps CST to FILE.  If UNS is true, CST is considered to be unsigned,
1082    otherwise it is signed.  */
1083
1084 void
1085 dump_double_int (FILE *file, double_int cst, bool uns)
1086 {
1087   unsigned digits[100], n;
1088   int i;
1089
1090   if (double_int_zero_p (cst))
1091     {
1092       fprintf (file, "0");
1093       return;
1094     }
1095
1096   if (!uns && double_int_negative_p (cst))
1097     {
1098       fprintf (file, "-");
1099       cst = double_int_neg (cst);
1100     }
1101
1102   for (n = 0; !double_int_zero_p (cst); n++)
1103     digits[n] = double_int_split_digit (&cst, 10);
1104   for (i = n - 1; i >= 0; i--)
1105     fprintf (file, "%u", digits[i]);
1106 }
1107
1108
1109 /* Sets RESULT to VAL, taken unsigned if UNS is true and as signed
1110    otherwise.  */
1111
1112 void
1113 mpz_set_double_int (mpz_t result, double_int val, bool uns)
1114 {
1115   bool negate = false;
1116   unsigned HOST_WIDE_INT vp[2];
1117
1118   if (!uns && double_int_negative_p (val))
1119     {
1120       negate = true;
1121       val = double_int_neg (val);
1122     }
1123
1124   vp[0] = val.low;
1125   vp[1] = (unsigned HOST_WIDE_INT) val.high;
1126   mpz_import (result, 2, -1, sizeof (HOST_WIDE_INT), 0, 0, vp);
1127
1128   if (negate)
1129     mpz_neg (result, result);
1130 }
1131
1132 /* Returns VAL converted to TYPE.  If WRAP is true, then out-of-range
1133    values of VAL will be wrapped; otherwise, they will be set to the
1134    appropriate minimum or maximum TYPE bound.  */
1135
1136 double_int
1137 mpz_get_double_int (const_tree type, mpz_t val, bool wrap)
1138 {
1139   unsigned HOST_WIDE_INT *vp;
1140   size_t count, numb;
1141   double_int res;
1142
1143   if (!wrap)
1144     {
1145       mpz_t min, max;
1146
1147       mpz_init (min);
1148       mpz_init (max);
1149       get_type_static_bounds (type, min, max);
1150
1151       if (mpz_cmp (val, min) < 0)
1152         mpz_set (val, min);
1153       else if (mpz_cmp (val, max) > 0)
1154         mpz_set (val, max);
1155
1156       mpz_clear (min);
1157       mpz_clear (max);
1158     }
1159
1160   /* Determine the number of unsigned HOST_WIDE_INT that are required
1161      for representing the value.  The code to calculate count is
1162      extracted from the GMP manual, section "Integer Import and Export":
1163      http://gmplib.org/manual/Integer-Import-and-Export.html  */
1164   numb = 8*sizeof(HOST_WIDE_INT);
1165   count = (mpz_sizeinbase (val, 2) + numb-1) / numb;
1166   if (count < 2)
1167     count = 2;
1168   vp = (unsigned HOST_WIDE_INT *) alloca (count * sizeof(HOST_WIDE_INT));
1169
1170   vp[0] = 0;
1171   vp[1] = 0;
1172   mpz_export (vp, &count, -1, sizeof (HOST_WIDE_INT), 0, 0, val);
1173
1174   gcc_assert (wrap || count <= 2);
1175
1176   res.low = vp[0];
1177   res.high = (HOST_WIDE_INT) vp[1];
1178
1179   res = double_int_ext (res, TYPE_PRECISION (type), TYPE_UNSIGNED (type));
1180   if (mpz_sgn (val) < 0)
1181     res = double_int_neg (res);
1182
1183   return res;
1184 }