gcc/double-int.h

   1 /* Operations with long integers.
   2    Copyright (C) 2006, 2007, 2008, 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 #ifndef DOUBLE_INT_H
  21 #define DOUBLE_INT_H
  22
  23 /* A large integer is currently represented as a pair of HOST_WIDE_INTs.
  24    It therefore represents a number with precision of
  25    2 * HOST_BITS_PER_WIDE_INT bits (it is however possible that the
  26    internal representation will change, if numbers with greater precision
  27    are needed, so the users should not rely on it).  The representation does
  28    not contain any information about signedness of the represented value, so
  29    it can be used to represent both signed and unsigned numbers.  For
  30    operations where the results depend on signedness (division, comparisons),
  31    it must be specified separately.  For each such operation, there are three
  32    versions of the function -- double_int_op, that takes an extra UNS argument
  33    giving the signedness of the values, and double_int_sop and double_int_uop
  34    that stand for its specializations for signed and unsigned values.
  35
  36    You may also represent with numbers in smaller precision using double_int.
  37    You however need to use double_int_ext (that fills in the bits of the
  38    number over the prescribed precision with zeros or with the sign bit) before
  39    operations that do not perform arithmetics modulo 2^precision (comparisons,
  40    division), and possibly before storing the results, if you want to keep
  41    them in some canonical form).  In general, the signedness of double_int_ext
  42    should match the signedness of the operation.
  43
  44    ??? The components of double_int differ in signedness mostly for
  45    historical reasons (they replace an older structure used to represent
  46    numbers with precision higher than HOST_WIDE_INT).  It might be less
  47    confusing to have them both signed or both unsigned.  */
  48
  49 struct double_int
  50 {
  51   /* Normally, we would define constructors to create instances.
  52      Two things prevent us from doing so.
  53      First, defining a constructor makes the class non-POD in C++03,
  54      and we certainly want double_int to be a POD.
  55      Second, the GCC conding conventions prefer explicit conversion,
  56      and explicit conversion operators are not available until C++11.  */
  57
  58   static double_int from_uhwi (unsigned HOST_WIDE_INT cst);
  59   static double_int from_shwi (HOST_WIDE_INT cst);
  60   static double_int from_pair (HOST_WIDE_INT high, unsigned HOST_WIDE_INT low);
  61
  62   /* No copy assignment operator or destructor to keep the type a POD.  */
  63
  64   /* There are some special value-creation static member functions.  */
  65
  66   static double_int mask (unsigned prec);
  67   static double_int max_value (unsigned int prec, bool uns);
  68   static double_int min_value (unsigned int prec, bool uns);
  69
  70   /* The following functions are mutating operations.  */
  71
  72   double_int &operator ++ (); // prefix
  73   double_int &operator -- (); // prefix
  74   double_int &operator *= (double_int);
  75   double_int &operator += (double_int);
  76   double_int &operator -= (double_int);
  77   double_int &operator &= (double_int);
  78   double_int &operator ^= (double_int);
  79   double_int &operator |= (double_int);
  80
  81   /* The following functions are non-mutating operations.  */
  82
  83   /* Conversion functions.  */
  84
  85   HOST_WIDE_INT to_shwi () const;
  86   unsigned HOST_WIDE_INT to_uhwi () const;
  87
  88   /* Conversion query functions.  */
  89
  90   bool fits_uhwi () const;
  91   bool fits_shwi () const;
  92   bool fits_hwi (bool uns) const;
  93
  94   /* Attribute query functions.  */
  95
  96   int trailing_zeros () const;
  97   int popcount () const;
  98
  99   /* Arithmetic query operations.  */
 100
 101   bool multiple_of (double_int, bool, double_int *) const;
 102
 103   /* Arithmetic operation functions.  */
 104
 105   /* The following operations perform arithmetics modulo 2^precision, so you
 106      do not need to call .ext between them, even if you are representing
 107      numbers with precision less than HOST_BITS_PER_DOUBLE_INT bits.  */
 108
 109   double_int set_bit (unsigned) const;
 110   double_int mul_with_sign (double_int, bool unsigned_p, bool *overflow) const;
 111   double_int wide_mul_with_sign (double_int, bool unsigned_p,
 112                                  double_int *higher, bool *overflow) const;
 113   double_int add_with_sign (double_int, bool unsigned_p, bool *overflow) const;
 114   double_int sub_with_overflow (double_int, bool *overflow) const;
 115   double_int neg_with_overflow (bool *overflow) const;
 116
 117   double_int operator * (double_int) const;
 118   double_int operator + (double_int) const;
 119   double_int operator - (double_int) const;
 120   double_int operator - () const;
 121   double_int operator ~ () const;
 122   double_int operator & (double_int) const;
 123   double_int operator | (double_int) const;
 124   double_int operator ^ (double_int) const;
 125   double_int and_not (double_int) const;
 126
 127   double_int lshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const;
 128   double_int rshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const;
 129   double_int alshift (HOST_WIDE_INT count, unsigned int prec) const;
 130   double_int arshift (HOST_WIDE_INT count, unsigned int prec) const;
 131   double_int llshift (HOST_WIDE_INT count, unsigned int prec) const;
 132   double_int lrshift (HOST_WIDE_INT count, unsigned int prec) const;
 133   double_int lrotate (HOST_WIDE_INT count, unsigned int prec) const;
 134   double_int rrotate (HOST_WIDE_INT count, unsigned int prec) const;
 135
 136   /* You must ensure that double_int::ext is called on the operands
 137      of the following operations, if the precision of the numbers
 138      is less than HOST_BITS_PER_DOUBLE_INT bits.  */
 139
 140   double_int div (double_int, bool, unsigned) const;
 141   double_int sdiv (double_int, unsigned) const;
 142   double_int udiv (double_int, unsigned) const;
 143   double_int mod (double_int, bool, unsigned) const;
 144   double_int smod (double_int, unsigned) const;
 145   double_int umod (double_int, unsigned) const;
 146   double_int divmod_with_overflow (double_int, bool, unsigned,
 147                                    double_int *, bool *) const;
 148   double_int divmod (double_int, bool, unsigned, double_int *) const;
 149   double_int sdivmod (double_int, unsigned, double_int *) const;
 150   double_int udivmod (double_int, unsigned, double_int *) const;
 151
 152   /* Precision control functions.  */
 153
 154   double_int ext (unsigned prec, bool uns) const;
 155   double_int zext (unsigned prec) const;
 156   double_int sext (unsigned prec) const;
 157
 158   /* Comparative functions.  */
 159
 160   bool is_zero () const;
 161   bool is_one () const;
 162   bool is_minus_one () const;
 163   bool is_negative () const;
 164
 165   int cmp (double_int b, bool uns) const;
 166   int ucmp (double_int b) const;
 167   int scmp (double_int b) const;
 168
 169   bool ult (double_int b) const;
 170   bool ule (double_int b) const;
 171   bool ugt (double_int b) const;
 172   bool slt (double_int b) const;
 173   bool sle (double_int b) const;
 174   bool sgt (double_int b) const;
 175
 176   double_int max (double_int b, bool uns);
 177   double_int smax (double_int b);
 178   double_int umax (double_int b);
 179
 180   double_int min (double_int b, bool uns);
 181   double_int smin (double_int b);
 182   double_int umin (double_int b);
 183
 184   bool operator == (double_int cst2) const;
 185   bool operator != (double_int cst2) const;
 186
 187   /* Please migrate away from using these member variables publically.  */
 188
 189   unsigned HOST_WIDE_INT low;
 190   HOST_WIDE_INT high;
 191
 192 };
 193
 194 #define HOST_BITS_PER_DOUBLE_INT (2 * HOST_BITS_PER_WIDE_INT)
 195
 196 /* Constructors and conversions.  */
 197
 198 /* Constructs double_int from integer CST.  The bits over the precision of
 199    HOST_WIDE_INT are filled with the sign bit.  */
 200
 201 inline double_int
 202 double_int::from_shwi (HOST_WIDE_INT cst)
 203 {
 204   double_int r;
 205   r.low = (unsigned HOST_WIDE_INT) cst;
 206   r.high = cst < 0 ? -1 : 0;
 207   return r;
 208 }
 209
 210 /* Some useful constants.  */
 211 /* FIXME(crowl): Maybe remove after converting callers?
 212    The problem is that a named constant would not be as optimizable,
 213    while the functional syntax is more verbose.  */
 214
 215 #define double_int_minus_one (double_int::from_shwi (-1))
 216 #define double_int_zero (double_int::from_shwi (0))
 217 #define double_int_one (double_int::from_shwi (1))
 218 #define double_int_two (double_int::from_shwi (2))
 219 #define double_int_ten (double_int::from_shwi (10))
 220
 221 /* Constructs double_int from unsigned integer CST.  The bits over the
 222    precision of HOST_WIDE_INT are filled with zeros.  */
 223
 224 inline double_int
 225 double_int::from_uhwi (unsigned HOST_WIDE_INT cst)
 226 {
 227   double_int r;
 228   r.low = cst;
 229   r.high = 0;
 230   return r;
 231 }
 232
 233 inline double_int
 234 double_int::from_pair (HOST_WIDE_INT high, unsigned HOST_WIDE_INT low)
 235 {
 236   double_int r;
 237   r.low = low;
 238   r.high = high;
 239   return r;
 240 }
 241
 242 inline double_int &
 243 double_int::operator ++ ()
 244 {
 245   *this += double_int_one;
 246   return *this;
 247 }
 248
 249 inline double_int &
 250 double_int::operator -- ()
 251 {
 252   *this -= double_int_one;
 253   return *this;
 254 }
 255
 256 inline double_int &
 257 double_int::operator *= (double_int b)
 258 {
 259   *this = *this * b;
 260   return *this;
 261 }
 262
 263 inline double_int &
 264 double_int::operator += (double_int b)
 265 {
 266   *this = *this + b;
 267   return *this;
 268 }
 269
 270 inline double_int &
 271 double_int::operator -= (double_int b)
 272 {
 273   *this = *this - b;
 274   return *this;
 275 }
 276
 277 inline double_int &
 278 double_int::operator &= (double_int b)
 279 {
 280   *this = *this & b;
 281   return *this;
 282 }
 283
 284 inline double_int &
 285 double_int::operator ^= (double_int b)
 286 {
 287   *this = *this ^ b;
 288   return *this;
 289 }
 290
 291 inline double_int &
 292 double_int::operator |= (double_int b)
 293 {
 294   *this = *this | b;
 295   return *this;
 296 }
 297
 298 /* Returns value of CST as a signed number.  CST must satisfy
 299    double_int::fits_signed.  */
 300
 301 inline HOST_WIDE_INT
 302 double_int::to_shwi () const
 303 {
 304   return (HOST_WIDE_INT) low;
 305 }
 306
 307 /* Returns value of CST as an unsigned number.  CST must satisfy
 308    double_int::fits_unsigned.  */
 309
 310 inline unsigned HOST_WIDE_INT
 311 double_int::to_uhwi () const
 312 {
 313   return low;
 314 }
 315
 316 /* Returns true if CST fits in unsigned HOST_WIDE_INT.  */
 317
 318 inline bool
 319 double_int::fits_uhwi () const
 320 {
 321   return high == 0;
 322 }
 323
 324 /* Logical operations.  */
 325
 326 /* Returns ~A.  */
 327
 328 inline double_int
 329 double_int::operator ~ () const
 330 {
 331   double_int result;
 332   result.low = ~low;
 333   result.high = ~high;
 334   return result;
 335 }
 336
 337 /* Returns A | B.  */
 338
 339 inline double_int
 340 double_int::operator | (double_int b) const
 341 {
 342   double_int result;
 343   result.low = low | b.low;
 344   result.high = high | b.high;
 345   return result;
 346 }
 347
 348 /* Returns A & B.  */
 349
 350 inline double_int
 351 double_int::operator & (double_int b) const
 352 {
 353   double_int result;
 354   result.low = low & b.low;
 355   result.high = high & b.high;
 356   return result;
 357 }
 358
 359 /* Returns A & ~B.  */
 360
 361 inline double_int
 362 double_int::and_not (double_int b) const
 363 {
 364   double_int result;
 365   result.low = low & ~b.low;
 366   result.high = high & ~b.high;
 367   return result;
 368 }
 369
 370 /* Returns A ^ B.  */
 371
 372 inline double_int
 373 double_int::operator ^ (double_int b) const
 374 {
 375   double_int result;
 376   result.low = low ^ b.low;
 377   result.high = high ^ b.high;
 378   return result;
 379 }
 380
 381 void dump_double_int (FILE *, double_int, bool);
 382
 383 #define ALL_ONES (~((unsigned HOST_WIDE_INT) 0))
 384
 385 /* The operands of the following comparison functions must be processed
 386    with double_int_ext, if their precision is less than
 387    HOST_BITS_PER_DOUBLE_INT bits.  */
 388
 389 /* Returns true if CST is zero.  */
 390
 391 inline bool
 392 double_int::is_zero () const
 393 {
 394   return low == 0 && high == 0;
 395 }
 396
 397 /* Returns true if CST is one.  */
 398
 399 inline bool
 400 double_int::is_one () const
 401 {
 402   return low == 1 && high == 0;
 403 }
 404
 405 /* Returns true if CST is minus one.  */
 406
 407 inline bool
 408 double_int::is_minus_one () const
 409 {
 410   return low == ALL_ONES && high == -1;
 411 }
 412
 413 /* Returns true if CST is negative.  */
 414
 415 inline bool
 416 double_int::is_negative () const
 417 {
 418   return high < 0;
 419 }
 420
 421 /* Returns true if CST1 == CST2.  */
 422
 423 inline bool
 424 double_int::operator == (double_int cst2) const
 425 {
 426   return low == cst2.low && high == cst2.high;
 427 }
 428
 429 /* Returns true if CST1 != CST2.  */
 430
 431 inline bool
 432 double_int::operator != (double_int cst2) const
 433 {
 434   return low != cst2.low || high != cst2.high;
 435 }
 436
 437 /* Return number of set bits of CST.  */
 438
 439 inline int
 440 double_int::popcount () const
 441 {
 442   return popcount_hwi (high) + popcount_hwi (low);
 443 }
 444
 445
 446 #ifndef GENERATOR_FILE
 447 /* Conversion to and from GMP integer representations.  */
 448
 449 void mpz_set_double_int (mpz_t, double_int, bool);
 450 double_int mpz_get_double_int (const_tree, mpz_t, bool);
 451 #endif
 452
 453 #endif /* DOUBLE_INT_H */