| /* Operations with long integers. |
| Copyright (C) 2006-2017 Free Software Foundation, Inc. |
| |
| This file is part of GCC. |
| |
| GCC is free software; you can redistribute it and/or modify it |
| under the terms of the GNU General Public License as published by the |
| Free Software Foundation; either version 3, or (at your option) any |
| later version. |
| |
| GCC is distributed in the hope that it will be useful, but WITHOUT |
| ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with GCC; see the file COPYING3. If not see |
| <http://www.gnu.org/licenses/>. */ |
| |
| #ifndef DOUBLE_INT_H |
| #define DOUBLE_INT_H |
| |
| /* A large integer is currently represented as a pair of HOST_WIDE_INTs. |
| It therefore represents a number with precision of |
| 2 * HOST_BITS_PER_WIDE_INT bits (it is however possible that the |
| internal representation will change, if numbers with greater precision |
| are needed, so the users should not rely on it). The representation does |
| not contain any information about signedness of the represented value, so |
| it can be used to represent both signed and unsigned numbers. For |
| operations where the results depend on signedness (division, comparisons), |
| it must be specified separately. For each such operation, there are three |
| versions of the function -- double_int_op, that takes an extra UNS argument |
| giving the signedness of the values, and double_int_sop and double_int_uop |
| that stand for its specializations for signed and unsigned values. |
| |
| You may also represent with numbers in smaller precision using double_int. |
| You however need to use double_int_ext (that fills in the bits of the |
| number over the prescribed precision with zeros or with the sign bit) before |
| operations that do not perform arithmetics modulo 2^precision (comparisons, |
| division), and possibly before storing the results, if you want to keep |
| them in some canonical form). In general, the signedness of double_int_ext |
| should match the signedness of the operation. |
| |
| ??? The components of double_int differ in signedness mostly for |
| historical reasons (they replace an older structure used to represent |
| numbers with precision higher than HOST_WIDE_INT). It might be less |
| confusing to have them both signed or both unsigned. */ |
| |
| struct double_int |
| { |
| /* Normally, we would define constructors to create instances. |
| Two things prevent us from doing so. |
| First, defining a constructor makes the class non-POD in C++03, |
| and we certainly want double_int to be a POD. |
| Second, the GCC conding conventions prefer explicit conversion, |
| and explicit conversion operators are not available until C++11. */ |
| |
| static double_int from_uhwi (unsigned HOST_WIDE_INT cst); |
| static double_int from_shwi (HOST_WIDE_INT cst); |
| static double_int from_pair (HOST_WIDE_INT high, unsigned HOST_WIDE_INT low); |
| |
| /* Construct from a fuffer of length LEN. BUFFER will be read according |
| to byte endianness and word endianness. */ |
| static double_int from_buffer (const unsigned char *buffer, int len); |
| |
| /* No copy assignment operator or destructor to keep the type a POD. */ |
| |
| /* There are some special value-creation static member functions. */ |
| |
| static double_int mask (unsigned prec); |
| static double_int max_value (unsigned int prec, bool uns); |
| static double_int min_value (unsigned int prec, bool uns); |
| |
| /* The following functions are mutating operations. */ |
| |
| double_int &operator ++ (); // prefix |
| double_int &operator -- (); // prefix |
| double_int &operator *= (double_int); |
| double_int &operator += (double_int); |
| double_int &operator -= (double_int); |
| double_int &operator &= (double_int); |
| double_int &operator ^= (double_int); |
| double_int &operator |= (double_int); |
| |
| /* The following functions are non-mutating operations. */ |
| |
| /* Conversion functions. */ |
| |
| HOST_WIDE_INT to_shwi () const; |
| unsigned HOST_WIDE_INT to_uhwi () const; |
| |
| /* Conversion query functions. */ |
| |
| bool fits_uhwi () const; |
| bool fits_shwi () const; |
| bool fits_hwi (bool uns) const; |
| |
| /* Attribute query functions. */ |
| |
| int trailing_zeros () const; |
| int popcount () const; |
| |
| /* Arithmetic query operations. */ |
| |
| bool multiple_of (double_int, bool, double_int *) const; |
| |
| /* Arithmetic operation functions. */ |
| |
| /* The following operations perform arithmetics modulo 2^precision, so you |
| do not need to call .ext between them, even if you are representing |
| numbers with precision less than HOST_BITS_PER_DOUBLE_INT bits. */ |
| |
| double_int set_bit (unsigned) const; |
| double_int mul_with_sign (double_int, bool unsigned_p, bool *overflow) const; |
| double_int wide_mul_with_sign (double_int, bool unsigned_p, |
| double_int *higher, bool *overflow) const; |
| double_int add_with_sign (double_int, bool unsigned_p, bool *overflow) const; |
| double_int sub_with_overflow (double_int, bool *overflow) const; |
| double_int neg_with_overflow (bool *overflow) const; |
| |
| double_int operator * (double_int) const; |
| double_int operator + (double_int) const; |
| double_int operator - (double_int) const; |
| double_int operator - () const; |
| double_int operator ~ () const; |
| double_int operator & (double_int) const; |
| double_int operator | (double_int) const; |
| double_int operator ^ (double_int) const; |
| double_int and_not (double_int) const; |
| |
| double_int lshift (HOST_WIDE_INT count) const; |
| double_int lshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const; |
| double_int rshift (HOST_WIDE_INT count) const; |
| double_int rshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const; |
| double_int alshift (HOST_WIDE_INT count, unsigned int prec) const; |
| double_int arshift (HOST_WIDE_INT count, unsigned int prec) const; |
| double_int llshift (HOST_WIDE_INT count, unsigned int prec) const; |
| double_int lrshift (HOST_WIDE_INT count, unsigned int prec) const; |
| double_int lrotate (HOST_WIDE_INT count, unsigned int prec) const; |
| double_int rrotate (HOST_WIDE_INT count, unsigned int prec) const; |
| |
| /* You must ensure that double_int::ext is called on the operands |
| of the following operations, if the precision of the numbers |
| is less than HOST_BITS_PER_DOUBLE_INT bits. */ |
| |
| double_int div (double_int, bool, unsigned) const; |
| double_int sdiv (double_int, unsigned) const; |
| double_int udiv (double_int, unsigned) const; |
| double_int mod (double_int, bool, unsigned) const; |
| double_int smod (double_int, unsigned) const; |
| double_int umod (double_int, unsigned) const; |
| double_int divmod_with_overflow (double_int, bool, unsigned, |
| double_int *, bool *) const; |
| double_int divmod (double_int, bool, unsigned, double_int *) const; |
| double_int sdivmod (double_int, unsigned, double_int *) const; |
| double_int udivmod (double_int, unsigned, double_int *) const; |
| |
| /* Precision control functions. */ |
| |
| double_int ext (unsigned prec, bool uns) const; |
| double_int zext (unsigned prec) const; |
| double_int sext (unsigned prec) const; |
| |
| /* Comparative functions. */ |
| |
| bool is_zero () const; |
| bool is_one () const; |
| bool is_minus_one () const; |
| bool is_negative () const; |
| |
| int cmp (double_int b, bool uns) const; |
| int ucmp (double_int b) const; |
| int scmp (double_int b) const; |
| |
| bool ult (double_int b) const; |
| bool ule (double_int b) const; |
| bool ugt (double_int b) const; |
| bool slt (double_int b) const; |
| bool sle (double_int b) const; |
| bool sgt (double_int b) const; |
| |
| double_int max (double_int b, bool uns); |
| double_int smax (double_int b); |
| double_int umax (double_int b); |
| |
| double_int min (double_int b, bool uns); |
| double_int smin (double_int b); |
| double_int umin (double_int b); |
| |
| bool operator == (double_int cst2) const; |
| bool operator != (double_int cst2) const; |
| |
| /* Please migrate away from using these member variables publicly. */ |
| |
| unsigned HOST_WIDE_INT low; |
| HOST_WIDE_INT high; |
| |
| }; |
| |
| #define HOST_BITS_PER_DOUBLE_INT (2 * HOST_BITS_PER_WIDE_INT) |
| |
| /* Constructors and conversions. */ |
| |
| /* Constructs double_int from integer CST. The bits over the precision of |
| HOST_WIDE_INT are filled with the sign bit. */ |
| |
| inline double_int |
| double_int::from_shwi (HOST_WIDE_INT cst) |
| { |
| double_int r; |
| r.low = (unsigned HOST_WIDE_INT) cst; |
| r.high = cst < 0 ? -1 : 0; |
| return r; |
| } |
| |
| /* Some useful constants. */ |
| /* FIXME(crowl): Maybe remove after converting callers? |
| The problem is that a named constant would not be as optimizable, |
| while the functional syntax is more verbose. */ |
| |
| #define double_int_minus_one (double_int::from_shwi (-1)) |
| #define double_int_zero (double_int::from_shwi (0)) |
| #define double_int_one (double_int::from_shwi (1)) |
| #define double_int_two (double_int::from_shwi (2)) |
| #define double_int_ten (double_int::from_shwi (10)) |
| |
| /* Constructs double_int from unsigned integer CST. The bits over the |
| precision of HOST_WIDE_INT are filled with zeros. */ |
| |
| inline double_int |
| double_int::from_uhwi (unsigned HOST_WIDE_INT cst) |
| { |
| double_int r; |
| r.low = cst; |
| r.high = 0; |
| return r; |
| } |
| |
| inline double_int |
| double_int::from_pair (HOST_WIDE_INT high, unsigned HOST_WIDE_INT low) |
| { |
| double_int r; |
| r.low = low; |
| r.high = high; |
| return r; |
| } |
| |
| inline double_int & |
| double_int::operator ++ () |
| { |
| *this += double_int_one; |
| return *this; |
| } |
| |
| inline double_int & |
| double_int::operator -- () |
| { |
| *this -= double_int_one; |
| return *this; |
| } |
| |
| inline double_int & |
| double_int::operator &= (double_int b) |
| { |
| *this = *this & b; |
| return *this; |
| } |
| |
| inline double_int & |
| double_int::operator ^= (double_int b) |
| { |
| *this = *this ^ b; |
| return *this; |
| } |
| |
| inline double_int & |
| double_int::operator |= (double_int b) |
| { |
| *this = *this | b; |
| return *this; |
| } |
| |
| /* Returns value of CST as a signed number. CST must satisfy |
| double_int::fits_signed. */ |
| |
| inline HOST_WIDE_INT |
| double_int::to_shwi () const |
| { |
| return (HOST_WIDE_INT) low; |
| } |
| |
| /* Returns value of CST as an unsigned number. CST must satisfy |
| double_int::fits_unsigned. */ |
| |
| inline unsigned HOST_WIDE_INT |
| double_int::to_uhwi () const |
| { |
| return low; |
| } |
| |
| /* Returns true if CST fits in unsigned HOST_WIDE_INT. */ |
| |
| inline bool |
| double_int::fits_uhwi () const |
| { |
| return high == 0; |
| } |
| |
| /* Logical operations. */ |
| |
| /* Returns ~A. */ |
| |
| inline double_int |
| double_int::operator ~ () const |
| { |
| double_int result; |
| result.low = ~low; |
| result.high = ~high; |
| return result; |
| } |
| |
| /* Returns A | B. */ |
| |
| inline double_int |
| double_int::operator | (double_int b) const |
| { |
| double_int result; |
| result.low = low | b.low; |
| result.high = high | b.high; |
| return result; |
| } |
| |
| /* Returns A & B. */ |
| |
| inline double_int |
| double_int::operator & (double_int b) const |
| { |
| double_int result; |
| result.low = low & b.low; |
| result.high = high & b.high; |
| return result; |
| } |
| |
| /* Returns A & ~B. */ |
| |
| inline double_int |
| double_int::and_not (double_int b) const |
| { |
| double_int result; |
| result.low = low & ~b.low; |
| result.high = high & ~b.high; |
| return result; |
| } |
| |
| /* Returns A ^ B. */ |
| |
| inline double_int |
| double_int::operator ^ (double_int b) const |
| { |
| double_int result; |
| result.low = low ^ b.low; |
| result.high = high ^ b.high; |
| return result; |
| } |
| |
| void dump_double_int (FILE *, double_int, bool); |
| |
| #define ALL_ONES HOST_WIDE_INT_M1U |
| |
| /* The operands of the following comparison functions must be processed |
| with double_int_ext, if their precision is less than |
| HOST_BITS_PER_DOUBLE_INT bits. */ |
| |
| /* Returns true if CST is zero. */ |
| |
| inline bool |
| double_int::is_zero () const |
| { |
| return low == 0 && high == 0; |
| } |
| |
| /* Returns true if CST is one. */ |
| |
| inline bool |
| double_int::is_one () const |
| { |
| return low == 1 && high == 0; |
| } |
| |
| /* Returns true if CST is minus one. */ |
| |
| inline bool |
| double_int::is_minus_one () const |
| { |
| return low == ALL_ONES && high == -1; |
| } |
| |
| /* Returns true if CST is negative. */ |
| |
| inline bool |
| double_int::is_negative () const |
| { |
| return high < 0; |
| } |
| |
| /* Returns true if CST1 == CST2. */ |
| |
| inline bool |
| double_int::operator == (double_int cst2) const |
| { |
| return low == cst2.low && high == cst2.high; |
| } |
| |
| /* Returns true if CST1 != CST2. */ |
| |
| inline bool |
| double_int::operator != (double_int cst2) const |
| { |
| return low != cst2.low || high != cst2.high; |
| } |
| |
| /* Return number of set bits of CST. */ |
| |
| inline int |
| double_int::popcount () const |
| { |
| return popcount_hwi (high) + popcount_hwi (low); |
| } |
| |
| |
| #ifndef GENERATOR_FILE |
| /* Conversion to and from GMP integer representations. */ |
| |
| void mpz_set_double_int (mpz_t, double_int, bool); |
| double_int mpz_get_double_int (const_tree, mpz_t, bool); |
| #endif |
| |
| namespace wi |
| { |
| template <> |
| struct int_traits <double_int> |
| { |
| static const enum precision_type precision_type = CONST_PRECISION; |
| static const bool host_dependent_precision = true; |
| static const unsigned int precision = HOST_BITS_PER_DOUBLE_INT; |
| static unsigned int get_precision (const double_int &); |
| static wi::storage_ref decompose (HOST_WIDE_INT *, unsigned int, |
| const double_int &); |
| }; |
| } |
| |
| inline unsigned int |
| wi::int_traits <double_int>::get_precision (const double_int &) |
| { |
| return precision; |
| } |
| |
| inline wi::storage_ref |
| wi::int_traits <double_int>::decompose (HOST_WIDE_INT *scratch, unsigned int p, |
| const double_int &x) |
| { |
| gcc_checking_assert (precision == p); |
| scratch[0] = x.low; |
| if ((x.high == 0 && scratch[0] >= 0) || (x.high == -1 && scratch[0] < 0)) |
| return wi::storage_ref (scratch, 1, precision); |
| scratch[1] = x.high; |
| return wi::storage_ref (scratch, 2, precision); |
| } |
| |
| #endif /* DOUBLE_INT_H */ |