gcc/double-int.c

   1 /* Operations with long integers.
   2    Copyright (C) 2006, 2007, 2009, 2010 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it
   7 under the terms of the GNU General Public License as published by the
   8 Free Software Foundation; either version 3, or (at your option) any
   9 later version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT
  12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "tm.h"
  24 #include "tree.h"
  25
  26 /* Returns mask for PREC bits.  */
  27
  28 double_int
  29 double_int_mask (unsigned prec)
  30 {
  31   unsigned HOST_WIDE_INT m;
  32   double_int mask;
  33
  34   if (prec > HOST_BITS_PER_WIDE_INT)
  35     {
  36       prec -= HOST_BITS_PER_WIDE_INT;
  37       m = ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1;
  38       mask.high = (HOST_WIDE_INT) m;
  39       mask.low = ALL_ONES;
  40     }
  41   else
  42     {
  43       mask.high = 0;
  44       mask.low = ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1;
  45     }
  46
  47   return mask;
  48 }
  49
  50 /* Clears the bits of CST over the precision PREC.  If UNS is false, the bits
  51    outside of the precision are set to the sign bit (i.e., the PREC-th one),
  52    otherwise they are set to zero.
  53
  54    This corresponds to returning the value represented by PREC lowermost bits
  55    of CST, with the given signedness.  */
  56
  57 double_int
  58 double_int_ext (double_int cst, unsigned prec, bool uns)
  59 {
  60   if (uns)
  61     return double_int_zext (cst, prec);
  62   else
  63     return double_int_sext (cst, prec);
  64 }
  65
  66 /* The same as double_int_ext with UNS = true.  */
  67
  68 double_int
  69 double_int_zext (double_int cst, unsigned prec)
  70 {
  71   double_int mask = double_int_mask (prec);
  72   double_int r;
  73
  74   r.low = cst.low & mask.low;
  75   r.high = cst.high & mask.high;
  76
  77   return r;
  78 }
  79
  80 /* The same as double_int_ext with UNS = false.  */
  81
  82 double_int
  83 double_int_sext (double_int cst, unsigned prec)
  84 {
  85   double_int mask = double_int_mask (prec);
  86   double_int r;
  87   unsigned HOST_WIDE_INT snum;
  88
  89   if (prec <= HOST_BITS_PER_WIDE_INT)
  90     snum = cst.low;
  91   else
  92     {
  93       prec -= HOST_BITS_PER_WIDE_INT;
  94       snum = (unsigned HOST_WIDE_INT) cst.high;
  95     }
  96   if (((snum >> (prec - 1)) & 1) == 1)
  97     {
  98       r.low = cst.low | ~mask.low;
  99       r.high = cst.high | ~mask.high;
 100     }
 101   else
 102     {
 103       r.low = cst.low & mask.low;
 104       r.high = cst.high & mask.high;
 105     }
 106
 107   return r;
 108 }
 109
 110 /* Constructs long integer from tree CST.  The extra bits over the precision of
 111    the number are filled with sign bit if CST is signed, and with zeros if it
 112    is unsigned.  */
 113
 114 double_int
 115 tree_to_double_int (const_tree cst)
 116 {
 117   /* We do not need to call double_int_restrict here to ensure the semantics as
 118      described, as this is the default one for trees.  */
 119   return TREE_INT_CST (cst);
 120 }
 121
 122 /* Returns true if CST fits in unsigned HOST_WIDE_INT.  */
 123
 124 bool
 125 double_int_fits_in_uhwi_p (double_int cst)
 126 {
 127   return cst.high == 0;
 128 }
 129
 130 /* Returns true if CST fits in signed HOST_WIDE_INT.  */
 131
 132 bool
 133 double_int_fits_in_shwi_p (double_int cst)
 134 {
 135   if (cst.high == 0)
 136     return (HOST_WIDE_INT) cst.low >= 0;
 137   else if (cst.high == -1)
 138     return (HOST_WIDE_INT) cst.low < 0;
 139   else
 140     return false;
 141 }
 142
 143 /* Returns true if CST fits in HOST_WIDE_INT if UNS is false, or in
 144    unsigned HOST_WIDE_INT if UNS is true.  */
 145
 146 bool
 147 double_int_fits_in_hwi_p (double_int cst, bool uns)
 148 {
 149   if (uns)
 150     return double_int_fits_in_uhwi_p (cst);
 151   else
 152     return double_int_fits_in_shwi_p (cst);
 153 }
 154
 155 /* Returns value of CST as a signed number.  CST must satisfy
 156    double_int_fits_in_shwi_p.  */
 157
 158 HOST_WIDE_INT
 159 double_int_to_shwi (double_int cst)
 160 {
 161   return (HOST_WIDE_INT) cst.low;
 162 }
 163
 164 /* Returns value of CST as an unsigned number.  CST must satisfy
 165    double_int_fits_in_uhwi_p.  */
 166
 167 unsigned HOST_WIDE_INT
 168 double_int_to_uhwi (double_int cst)
 169 {
 170   return cst.low;
 171 }
 172
 173 /* Returns A * B.  */
 174
 175 double_int
 176 double_int_mul (double_int a, double_int b)
 177 {
 178   double_int ret;
 179   mul_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
 180   return ret;
 181 }
 182
 183 /* Returns A + B.  */
 184
 185 double_int
 186 double_int_add (double_int a, double_int b)
 187 {
 188   double_int ret;
 189   add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
 190   return ret;
 191 }
 192
 193 /* Returns -A.  */
 194
 195 double_int
 196 double_int_neg (double_int a)
 197 {
 198   double_int ret;
 199   neg_double (a.low, a.high, &ret.low, &ret.high);
 200   return ret;
 201 }
 202
 203 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
 204    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
 205    must be included before tree.h.  The remainder after the division is
 206    stored to MOD.  */
 207
 208 double_int
 209 double_int_divmod (double_int a, double_int b, bool uns, unsigned code,
 210                    double_int *mod)
 211 {
 212   double_int ret;
 213
 214   div_and_round_double ((enum tree_code) code, uns, a.low, a.high,
 215                         b.low, b.high, &ret.low, &ret.high,
 216                         &mod->low, &mod->high);
 217   return ret;
 218 }
 219
 220 /* The same as double_int_divmod with UNS = false.  */
 221
 222 double_int
 223 double_int_sdivmod (double_int a, double_int b, unsigned code, double_int *mod)
 224 {
 225   return double_int_divmod (a, b, false, code, mod);
 226 }
 227
 228 /* The same as double_int_divmod with UNS = true.  */
 229
 230 double_int
 231 double_int_udivmod (double_int a, double_int b, unsigned code, double_int *mod)
 232 {
 233   return double_int_divmod (a, b, true, code, mod);
 234 }
 235
 236 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
 237    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
 238    must be included before tree.h.  */
 239
 240 double_int
 241 double_int_div (double_int a, double_int b, bool uns, unsigned code)
 242 {
 243   double_int mod;
 244
 245   return double_int_divmod (a, b, uns, code, &mod);
 246 }
 247
 248 /* The same as double_int_div with UNS = false.  */
 249
 250 double_int
 251 double_int_sdiv (double_int a, double_int b, unsigned code)
 252 {
 253   return double_int_div (a, b, false, code);
 254 }
 255
 256 /* The same as double_int_div with UNS = true.  */
 257
 258 double_int
 259 double_int_udiv (double_int a, double_int b, unsigned code)
 260 {
 261   return double_int_div (a, b, true, code);
 262 }
 263
 264 /* Returns A % B (computed as unsigned depending on UNS, and rounded as
 265    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
 266    must be included before tree.h.  */
 267
 268 double_int
 269 double_int_mod (double_int a, double_int b, bool uns, unsigned code)
 270 {
 271   double_int mod;
 272
 273   double_int_divmod (a, b, uns, code, &mod);
 274   return mod;
 275 }
 276
 277 /* The same as double_int_mod with UNS = false.  */
 278
 279 double_int
 280 double_int_smod (double_int a, double_int b, unsigned code)
 281 {
 282   return double_int_mod (a, b, false, code);
 283 }
 284
 285 /* The same as double_int_mod with UNS = true.  */
 286
 287 double_int
 288 double_int_umod (double_int a, double_int b, unsigned code)
 289 {
 290   return double_int_mod (a, b, true, code);
 291 }
 292
 293 /* Shift A left by COUNT places keeping only PREC bits of result.  Shift
 294    right if COUNT is negative.  ARITH true specifies arithmetic shifting;
 295    otherwise use logical shift.  */
 296
 297 double_int
 298 double_int_lshift (double_int a, HOST_WIDE_INT count, unsigned int prec, bool arith)
 299 {
 300   double_int ret;
 301   lshift_double (a.low, a.high, count, prec, &ret.low, &ret.high, arith);
 302   return ret;
 303 }
 304
 305 /* Shift A rigth by COUNT places keeping only PREC bits of result.  Shift
 306    left if COUNT is negative.  ARITH true specifies arithmetic shifting;
 307    otherwise use logical shift.  */
 308
 309 double_int
 310 double_int_rshift (double_int a, HOST_WIDE_INT count, unsigned int prec, bool arith)
 311 {
 312   double_int ret;
 313   rshift_double (a.low, a.high, count, prec, &ret.low, &ret.high, arith);
 314   return ret;
 315 }
 316
 317 /* Constructs tree in type TYPE from with value given by CST.  Signedness of CST
 318    is assumed to be the same as the signedness of TYPE.  */
 319
 320 tree
 321 double_int_to_tree (tree type, double_int cst)
 322 {
 323   cst = double_int_ext (cst, TYPE_PRECISION (type), TYPE_UNSIGNED (type));
 324
 325   return build_int_cst_wide (type, cst.low, cst.high);
 326 }
 327
 328 /* Returns true if CST fits into range of TYPE.  Signedness of CST is assumed
 329    to be the same as the signedness of TYPE.  */
 330
 331 bool
 332 double_int_fits_to_tree_p (const_tree type, double_int cst)
 333 {
 334   double_int ext = double_int_ext (cst,
 335                                    TYPE_PRECISION (type),
 336                                    TYPE_UNSIGNED (type));
 337
 338   return double_int_equal_p (cst, ext);
 339 }
 340
 341 /* Returns -1 if A < B, 0 if A == B and 1 if A > B.  Signedness of the
 342    comparison is given by UNS.  */
 343
 344 int
 345 double_int_cmp (double_int a, double_int b, bool uns)
 346 {
 347   if (uns)
 348     return double_int_ucmp (a, b);
 349   else
 350     return double_int_scmp (a, b);
 351 }
 352
 353 /* Compares two unsigned values A and B.  Returns -1 if A < B, 0 if A == B,
 354    and 1 if A > B.  */
 355
 356 int
 357 double_int_ucmp (double_int a, double_int b)
 358 {
 359   if ((unsigned HOST_WIDE_INT) a.high < (unsigned HOST_WIDE_INT) b.high)
 360     return -1;
 361   if ((unsigned HOST_WIDE_INT) a.high > (unsigned HOST_WIDE_INT) b.high)
 362     return 1;
 363   if (a.low < b.low)
 364     return -1;
 365   if (a.low > b.low)
 366     return 1;
 367
 368   return 0;
 369 }
 370
 371 /* Compares two signed values A and B.  Returns -1 if A < B, 0 if A == B,
 372    and 1 if A > B.  */
 373
 374 int
 375 double_int_scmp (double_int a, double_int b)
 376 {
 377   if (a.high < b.high)
 378     return -1;
 379   if (a.high > b.high)
 380     return 1;
 381   if (a.low < b.low)
 382     return -1;
 383   if (a.low > b.low)
 384     return 1;
 385
 386   return 0;
 387 }
 388
 389 /* Splits last digit of *CST (taken as unsigned) in BASE and returns it.  */
 390
 391 static unsigned
 392 double_int_split_digit (double_int *cst, unsigned base)
 393 {
 394   unsigned HOST_WIDE_INT resl, reml;
 395   HOST_WIDE_INT resh, remh;
 396
 397   div_and_round_double (FLOOR_DIV_EXPR, true, cst->low, cst->high, base, 0,
 398                         &resl, &resh, &reml, &remh);
 399   cst->high = resh;
 400   cst->low = resl;
 401
 402   return reml;
 403 }
 404
 405 /* Dumps CST to FILE.  If UNS is true, CST is considered to be unsigned,
 406    otherwise it is signed.  */
 407
 408 void
 409 dump_double_int (FILE *file, double_int cst, bool uns)
 410 {
 411   unsigned digits[100], n;
 412   int i;
 413
 414   if (double_int_zero_p (cst))
 415     {
 416       fprintf (file, "0");
 417       return;
 418     }
 419
 420   if (!uns && double_int_negative_p (cst))
 421     {
 422       fprintf (file, "-");
 423       cst = double_int_neg (cst);
 424     }
 425
 426   for (n = 0; !double_int_zero_p (cst); n++)
 427     digits[n] = double_int_split_digit (&cst, 10);
 428   for (i = n - 1; i >= 0; i--)
 429     fprintf (file, "%u", digits[i]);
 430 }
 431
 432
 433 /* Sets RESULT to VAL, taken unsigned if UNS is true and as signed
 434    otherwise.  */
 435
 436 void
 437 mpz_set_double_int (mpz_t result, double_int val, bool uns)
 438 {
 439   bool negate = false;
 440   unsigned HOST_WIDE_INT vp[2];
 441
 442   if (!uns && double_int_negative_p (val))
 443     {
 444       negate = true;
 445       val = double_int_neg (val);
 446     }
 447
 448   vp[0] = val.low;
 449   vp[1] = (unsigned HOST_WIDE_INT) val.high;
 450   mpz_import (result, 2, -1, sizeof (HOST_WIDE_INT), 0, 0, vp);
 451
 452   if (negate)
 453     mpz_neg (result, result);
 454 }
 455
 456 /* Returns VAL converted to TYPE.  If WRAP is true, then out-of-range
 457    values of VAL will be wrapped; otherwise, they will be set to the
 458    appropriate minimum or maximum TYPE bound.  */
 459
 460 double_int
 461 mpz_get_double_int (const_tree type, mpz_t val, bool wrap)
 462 {
 463   unsigned HOST_WIDE_INT *vp;
 464   size_t count, numb;
 465   double_int res;
 466
 467   if (!wrap)
 468     {
 469       mpz_t min, max;
 470
 471       mpz_init (min);
 472       mpz_init (max);
 473       get_type_static_bounds (type, min, max);
 474
 475       if (mpz_cmp (val, min) < 0)
 476         mpz_set (val, min);
 477       else if (mpz_cmp (val, max) > 0)
 478         mpz_set (val, max);
 479
 480       mpz_clear (min);
 481       mpz_clear (max);
 482     }
 483
 484   /* Determine the number of unsigned HOST_WIDE_INT that are required
 485      for representing the value.  The code to calculate count is
 486      extracted from the GMP manual, section "Integer Import and Export":
 487      http://gmplib.org/manual/Integer-Import-and-Export.html  */
 488   numb = 8*sizeof(HOST_WIDE_INT);
 489   count = (mpz_sizeinbase (val, 2) + numb-1) / numb;
 490   if (count < 2)
 491     count = 2;
 492   vp = (unsigned HOST_WIDE_INT *) alloca (count * sizeof(HOST_WIDE_INT));
 493
 494   vp[0] = 0;
 495   vp[1] = 0;
 496   mpz_export (vp, &count, -1, sizeof (HOST_WIDE_INT), 0, 0, val);
 497
 498   gcc_assert (wrap || count <= 2);
 499
 500   res.low = vp[0];
 501   res.high = (HOST_WIDE_INT) vp[1];
 502
 503   res = double_int_ext (res, TYPE_PRECISION (type), TYPE_UNSIGNED (type));
 504   if (mpz_sgn (val) < 0)
 505     res = double_int_neg (res);
 506
 507   return res;
 508 }