gcc/double-int.c

   1 /* Operations with long integers.
   2    Copyright (C) 2006, 2007 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 (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 (code, uns, a.low, a.high, b.low, b.high,
 215                         &ret.low, &ret.high, &mod->low, &mod->high);
 216   return ret;
 217 }
 218
 219 /* The same as double_int_divmod with UNS = false.  */
 220
 221 double_int
 222 double_int_sdivmod (double_int a, double_int b, unsigned code, double_int *mod)
 223 {
 224   return double_int_divmod (a, b, false, code, mod);
 225 }
 226
 227 /* The same as double_int_divmod with UNS = true.  */
 228
 229 double_int
 230 double_int_udivmod (double_int a, double_int b, unsigned code, double_int *mod)
 231 {
 232   return double_int_divmod (a, b, true, code, mod);
 233 }
 234
 235 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
 236    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
 237    must be included before tree.h.  */
 238
 239 double_int
 240 double_int_div (double_int a, double_int b, bool uns, unsigned code)
 241 {
 242   double_int mod;
 243
 244   return double_int_divmod (a, b, uns, code, &mod);
 245 }
 246
 247 /* The same as double_int_div with UNS = false.  */
 248
 249 double_int
 250 double_int_sdiv (double_int a, double_int b, unsigned code)
 251 {
 252   return double_int_div (a, b, false, code);
 253 }
 254
 255 /* The same as double_int_div with UNS = true.  */
 256
 257 double_int
 258 double_int_udiv (double_int a, double_int b, unsigned code)
 259 {
 260   return double_int_div (a, b, true, code);
 261 }
 262
 263 /* Returns A % B (computed as unsigned depending on UNS, and rounded as
 264    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
 265    must be included before tree.h.  */
 266
 267 double_int
 268 double_int_mod (double_int a, double_int b, bool uns, unsigned code)
 269 {
 270   double_int mod;
 271
 272   double_int_divmod (a, b, uns, code, &mod);
 273   return mod;
 274 }
 275
 276 /* The same as double_int_mod with UNS = false.  */
 277
 278 double_int
 279 double_int_smod (double_int a, double_int b, unsigned code)
 280 {
 281   return double_int_mod (a, b, false, code);
 282 }
 283
 284 /* The same as double_int_mod with UNS = true.  */
 285
 286 double_int
 287 double_int_umod (double_int a, double_int b, unsigned code)
 288 {
 289   return double_int_mod (a, b, true, code);
 290 }
 291
 292 /* Constructs tree in type TYPE from with value given by CST.  Signedness of CST
 293    is assumed to be the same as the signedness of TYPE.  */
 294
 295 tree
 296 double_int_to_tree (tree type, double_int cst)
 297 {
 298   cst = double_int_ext (cst, TYPE_PRECISION (type), TYPE_UNSIGNED (type));
 299
 300   return build_int_cst_wide (type, cst.low, cst.high);
 301 }
 302
 303 /* Returns true if CST fits into range of TYPE.  Signedness of CST is assumed
 304    to be the same as the signedness of TYPE.  */
 305
 306 bool
 307 double_int_fits_to_tree_p (tree type, double_int cst)
 308 {
 309   double_int ext = double_int_ext (cst,
 310                                    TYPE_PRECISION (type),
 311                                    TYPE_UNSIGNED (type));
 312
 313   return double_int_equal_p (cst, ext);
 314 }
 315
 316 /* Returns true if CST is negative.  Of course, CST is considered to
 317    be signed.  */
 318
 319 bool
 320 double_int_negative_p (double_int cst)
 321 {
 322   return cst.high < 0;
 323 }
 324
 325 /* Returns -1 if A < B, 0 if A == B and 1 if A > B.  Signedness of the
 326    comparison is given by UNS.  */
 327
 328 int
 329 double_int_cmp (double_int a, double_int b, bool uns)
 330 {
 331   if (uns)
 332     return double_int_ucmp (a, b);
 333   else
 334     return double_int_scmp (a, b);
 335 }
 336
 337 /* Compares two unsigned values A and B.  Returns -1 if A < B, 0 if A == B,
 338    and 1 if A > B.  */
 339
 340 int
 341 double_int_ucmp (double_int a, double_int b)
 342 {
 343   if ((unsigned HOST_WIDE_INT) a.high < (unsigned HOST_WIDE_INT) b.high)
 344     return -1;
 345   if ((unsigned HOST_WIDE_INT) a.high > (unsigned HOST_WIDE_INT) b.high)
 346     return 1;
 347   if (a.low < b.low)
 348     return -1;
 349   if (a.low > b.low)
 350     return 1;
 351
 352   return 0;
 353 }
 354
 355 /* Compares two signed values A and B.  Returns -1 if A < B, 0 if A == B,
 356    and 1 if A > B.  */
 357
 358 int
 359 double_int_scmp (double_int a, double_int b)
 360 {
 361   if (a.high < b.high)
 362     return -1;
 363   if (a.high > b.high)
 364     return 1;
 365   if ((HOST_WIDE_INT) a.low < (HOST_WIDE_INT) b.low)
 366     return -1;
 367   if ((HOST_WIDE_INT) a.low > (HOST_WIDE_INT) b.low)
 368     return 1;
 369
 370   return 0;
 371 }
 372
 373 /* Splits last digit of *CST (taken as unsigned) in BASE and returns it.  */
 374
 375 static unsigned
 376 double_int_split_digit (double_int *cst, unsigned base)
 377 {
 378   unsigned HOST_WIDE_INT resl, reml;
 379   HOST_WIDE_INT resh, remh;
 380
 381   div_and_round_double (FLOOR_DIV_EXPR, true, cst->low, cst->high, base, 0,
 382                         &resl, &resh, &reml, &remh);
 383   cst->high = resh;
 384   cst->low = resl;
 385
 386   return reml;
 387 }
 388
 389 /* Dumps CST to FILE.  If UNS is true, CST is considered to be unsigned,
 390    otherwise it is signed.  */
 391
 392 void
 393 dump_double_int (FILE *file, double_int cst, bool uns)
 394 {
 395   unsigned digits[100], n;
 396   int i;
 397
 398   if (double_int_zero_p (cst))
 399     {
 400       fprintf (file, "0");
 401       return;
 402     }
 403
 404   if (!uns && double_int_negative_p (cst))
 405     {
 406       fprintf (file, "-");
 407       cst = double_int_neg (cst);
 408     }
 409
 410   for (n = 0; !double_int_zero_p (cst); n++)
 411     digits[n] = double_int_split_digit (&cst, 10);
 412   for (i = n - 1; i >= 0; i--)
 413     fprintf (file, "%u", digits[i]);
 414 }
 415
 416
 417 /* Sets RESULT to VAL, taken unsigned if UNS is true and as signed
 418    otherwise.  */
 419
 420 void
 421 mpz_set_double_int (mpz_t result, double_int val, bool uns)
 422 {
 423   bool negate = false;
 424   unsigned HOST_WIDE_INT vp[2];
 425
 426   if (!uns && double_int_negative_p (val))
 427     {
 428       negate = true;
 429       val = double_int_neg (val);
 430     }
 431
 432   vp[0] = val.low;
 433   vp[1] = (unsigned HOST_WIDE_INT) val.high;
 434   mpz_import (result, 2, -1, sizeof (HOST_WIDE_INT), 0, 0, vp);
 435
 436   if (negate)
 437     mpz_neg (result, result);
 438 }
 439
 440 /* Returns VAL converted to TYPE.  If WRAP is true, then out-of-range
 441    values of VAL will be wrapped; otherwise, they will be set to the
 442    appropriate minimum or maximum TYPE bound.  */
 443
 444 double_int
 445 mpz_get_double_int (tree type, mpz_t val, bool wrap)
 446 {
 447   unsigned HOST_WIDE_INT *vp;
 448   size_t count, numb;
 449   double_int res;
 450
 451   if (!wrap)
 452     {
 453       mpz_t min, max;
 454
 455       mpz_init (min);
 456       mpz_init (max);
 457       get_type_static_bounds (type, min, max);
 458
 459       if (mpz_cmp (val, min) < 0)
 460         mpz_set (val, min);
 461       else if (mpz_cmp (val, max) > 0)
 462         mpz_set (val, max);
 463
 464       mpz_clear (min);
 465       mpz_clear (max);
 466     }
 467
 468   /* Determine the number of unsigned HOST_WIDE_INT that are required
 469      for representing the value.  The code to calculate count is
 470      extracted from the GMP manual, section "Integer Import and Export":
 471      http://gmplib.org/manual/Integer-Import-and-Export.html  */
 472   numb = 8*sizeof(HOST_WIDE_INT);
 473   count = (mpz_sizeinbase (val, 2) + numb-1) / numb;
 474   if (count < 2)
 475     count = 2;
 476   vp = (unsigned HOST_WIDE_INT *) alloca (count * sizeof(HOST_WIDE_INT));
 477
 478   vp[0] = 0;
 479   vp[1] = 0;
 480   mpz_export (vp, &count, -1, sizeof (HOST_WIDE_INT), 0, 0, val);
 481
 482   gcc_assert (wrap || count <= 2);
 483
 484   res.low = vp[0];
 485   res.high = (HOST_WIDE_INT) vp[1];
 486
 487   res = double_int_ext (res, TYPE_PRECISION (type), TYPE_UNSIGNED (type));
 488   if (mpz_sgn (val) < 0)
 489     res = double_int_neg (res);
 490
 491   return res;
 492 }