gcc/double-int.h

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