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 #ifndef GENERATOR_FILE
  24 #include <gmp.h>
  25 #endif
  26
  27 /* A large integer is currently represented as a pair of HOST_WIDE_INTs.
  28    It therefore represents a number with precision of
  29    2 * HOST_BITS_PER_WIDE_INT bits (it is however possible that the
  30    internal representation will change, if numbers with greater precision
  31    are needed, so the users should not rely on it).  The representation does
  32    not contain any information about signedness of the represented value, so
  33    it can be used to represent both signed and unsigned numbers.  For
  34    operations where the results depend on signedness (division, comparisons),
  35    it must be specified separately.  For each such operation, there are three
  36    versions of the function -- double_int_op, that takes an extra UNS argument
  37    giving the signedness of the values, and double_int_sop and double_int_uop
  38    that stand for its specializations for signed and unsigned values.
  39
  40    You may also represent with numbers in smaller precision using double_int.
  41    You however need to use double_int_ext (that fills in the bits of the
  42    number over the prescribed precision with zeros or with the sign bit) before
  43    operations that do not perform arithmetics modulo 2^precision (comparisons,
  44    division), and possibly before storing the results, if you want to keep
  45    them in some canonical form).  In general, the signedness of double_int_ext
  46    should match the signedness of the operation.
  47
  48    ??? The components of double_int differ in signedness mostly for
  49    historical reasons (they replace an older structure used to represent
  50    numbers with precision higher than HOST_WIDE_INT).  It might be less
  51    confusing to have them both signed or both unsigned.  */
  52
  53 typedef struct
  54 {
  55   unsigned HOST_WIDE_INT low;
  56   HOST_WIDE_INT high;
  57 } double_int;
  58
  59 #define HOST_BITS_PER_DOUBLE_INT (2 * HOST_BITS_PER_WIDE_INT)
  60
  61 /* Constructors and conversions.  */
  62
  63 /* Constructs double_int from integer CST.  The bits over the precision of
  64    HOST_WIDE_INT are filled with the sign bit.  */
  65
  66 static inline double_int
  67 shwi_to_double_int (HOST_WIDE_INT cst)
  68 {
  69   double_int r;
  70
  71   r.low = (unsigned HOST_WIDE_INT) cst;
  72   r.high = cst < 0 ? -1 : 0;
  73
  74   return r;
  75 }
  76
  77 /* Some useful constants.  */
  78
  79 #define double_int_minus_one (shwi_to_double_int (-1))
  80 #define double_int_zero (shwi_to_double_int (0))
  81 #define double_int_one (shwi_to_double_int (1))
  82 #define double_int_two (shwi_to_double_int (2))
  83 #define double_int_ten (shwi_to_double_int (10))
  84
  85 /* Constructs double_int from unsigned integer CST.  The bits over the
  86    precision of HOST_WIDE_INT are filled with zeros.  */
  87
  88 static inline double_int
  89 uhwi_to_double_int (unsigned HOST_WIDE_INT cst)
  90 {
  91   double_int r;
  92
  93   r.low = cst;
  94   r.high = 0;
  95
  96   return r;
  97 }
  98
  99 /* Returns value of CST as a signed number.  CST must satisfy
 100    double_int_fits_in_shwi_p.  */
 101
 102 static inline HOST_WIDE_INT
 103 double_int_to_shwi (double_int cst)
 104 {
 105   return (HOST_WIDE_INT) cst.low;
 106 }
 107
 108 /* Returns value of CST as an unsigned number.  CST must satisfy
 109    double_int_fits_in_uhwi_p.  */
 110
 111 static inline unsigned HOST_WIDE_INT
 112 double_int_to_uhwi (double_int cst)
 113 {
 114   return cst.low;
 115 }
 116
 117 bool double_int_fits_in_hwi_p (double_int, bool);
 118 bool double_int_fits_in_shwi_p (double_int);
 119
 120 /* Returns true if CST fits in unsigned HOST_WIDE_INT.  */
 121
 122 static inline bool
 123 double_int_fits_in_uhwi_p (double_int cst)
 124 {
 125   return cst.high == 0;
 126 }
 127
 128 /* The following operations perform arithmetics modulo 2^precision,
 129    so you do not need to call double_int_ext between them, even if
 130    you are representing numbers with precision less than
 131    HOST_BITS_PER_DOUBLE_INT bits.  */
 132
 133 double_int double_int_mul (double_int, double_int);
 134 double_int double_int_mul_with_sign (double_int, double_int, bool, int *);
 135 double_int double_int_add (double_int, double_int);
 136 double_int double_int_sub (double_int, double_int);
 137 double_int double_int_neg (double_int);
 138
 139 /* You must ensure that double_int_ext is called on the operands
 140    of the following operations, if the precision of the numbers
 141    is less than HOST_BITS_PER_DOUBLE_INT bits.  */
 142 double_int double_int_div (double_int, double_int, bool, unsigned);
 143 double_int double_int_sdiv (double_int, double_int, unsigned);
 144 double_int double_int_udiv (double_int, double_int, unsigned);
 145 double_int double_int_mod (double_int, double_int, bool, unsigned);
 146 double_int double_int_smod (double_int, double_int, unsigned);
 147 double_int double_int_umod (double_int, double_int, unsigned);
 148 double_int double_int_divmod (double_int, double_int, bool, unsigned, double_int *);
 149 double_int double_int_sdivmod (double_int, double_int, unsigned, double_int *);
 150 double_int double_int_udivmod (double_int, double_int, unsigned, double_int *);
 151
 152 bool double_int_multiple_of (double_int, double_int, bool, double_int *);
 153
 154 double_int double_int_setbit (double_int, unsigned);
 155 int double_int_ctz (double_int);
 156
 157 /* Logical operations.  */
 158
 159 /* Returns ~A.  */
 160
 161 static inline double_int
 162 double_int_not (double_int a)
 163 {
 164   a.low = ~a.low;
 165   a.high = ~a.high;
 166   return a;
 167 }
 168
 169 /* Returns A | B.  */
 170
 171 static inline double_int
 172 double_int_ior (double_int a, double_int b)
 173 {
 174   a.low |= b.low;
 175   a.high |= b.high;
 176   return a;
 177 }
 178
 179 /* Returns A & B.  */
 180
 181 static inline double_int
 182 double_int_and (double_int a, double_int b)
 183 {
 184   a.low &= b.low;
 185   a.high &= b.high;
 186   return a;
 187 }
 188
 189 /* Returns A & ~B.  */
 190
 191 static inline double_int
 192 double_int_and_not (double_int a, double_int b)
 193 {
 194   a.low &= ~b.low;
 195   a.high &= ~b.high;
 196   return a;
 197 }
 198
 199 /* Returns A ^ B.  */
 200
 201 static inline double_int
 202 double_int_xor (double_int a, double_int b)
 203 {
 204   a.low ^= b.low;
 205   a.high ^= b.high;
 206   return a;
 207 }
 208
 209
 210 /* Shift operations.  */
 211 double_int double_int_lshift (double_int, HOST_WIDE_INT, unsigned int, bool);
 212 double_int double_int_rshift (double_int, HOST_WIDE_INT, unsigned int, bool);
 213 double_int double_int_lrotate (double_int, HOST_WIDE_INT, unsigned int);
 214 double_int double_int_rrotate (double_int, HOST_WIDE_INT, unsigned int);
 215
 216 /* Returns true if CST is negative.  Of course, CST is considered to
 217    be signed.  */
 218
 219 static inline bool
 220 double_int_negative_p (double_int cst)
 221 {
 222   return cst.high < 0;
 223 }
 224
 225 int double_int_cmp (double_int, double_int, bool);
 226 int double_int_scmp (double_int, double_int);
 227 int double_int_ucmp (double_int, double_int);
 228
 229 double_int double_int_max (double_int, double_int, bool);
 230 double_int double_int_smax (double_int, double_int);
 231 double_int double_int_umax (double_int, double_int);
 232
 233 double_int double_int_min (double_int, double_int, bool);
 234 double_int double_int_smin (double_int, double_int);
 235 double_int double_int_umin (double_int, double_int);
 236
 237 void dump_double_int (FILE *, double_int, bool);
 238
 239 /* Zero and sign extension of numbers in smaller precisions.  */
 240
 241 double_int double_int_ext (double_int, unsigned, bool);
 242 double_int double_int_sext (double_int, unsigned);
 243 double_int double_int_zext (double_int, unsigned);
 244 double_int double_int_mask (unsigned);
 245
 246 double_int double_int_max_value (unsigned int, bool);
 247 double_int double_int_min_value (unsigned int, bool);
 248
 249 #define ALL_ONES (~((unsigned HOST_WIDE_INT) 0))
 250
 251 /* The operands of the following comparison functions must be processed
 252    with double_int_ext, if their precision is less than
 253    HOST_BITS_PER_DOUBLE_INT bits.  */
 254
 255 /* Returns true if CST is zero.  */
 256
 257 static inline bool
 258 double_int_zero_p (double_int cst)
 259 {
 260   return cst.low == 0 && cst.high == 0;
 261 }
 262
 263 /* Returns true if CST is one.  */
 264
 265 static inline bool
 266 double_int_one_p (double_int cst)
 267 {
 268   return cst.low == 1 && cst.high == 0;
 269 }
 270
 271 /* Returns true if CST is minus one.  */
 272
 273 static inline bool
 274 double_int_minus_one_p (double_int cst)
 275 {
 276   return (cst.low == ALL_ONES && cst.high == -1);
 277 }
 278
 279 /* Returns true if CST1 == CST2.  */
 280
 281 static inline bool
 282 double_int_equal_p (double_int cst1, double_int cst2)
 283 {
 284   return cst1.low == cst2.low && cst1.high == cst2.high;
 285 }
 286
 287 /* Return number of set bits of CST.  */
 288
 289 static inline int
 290 double_int_popcount (double_int cst)
 291 {
 292   return popcount_hwi (cst.high) + popcount_hwi (cst.low);
 293 }
 294
 295
 296 /* Legacy interface with decomposed high/low parts.  */
 297
 298 extern int add_double_with_sign (unsigned HOST_WIDE_INT, HOST_WIDE_INT,
 299                                  unsigned HOST_WIDE_INT, HOST_WIDE_INT,
 300                                  unsigned HOST_WIDE_INT *, HOST_WIDE_INT *,
 301                                  bool);
 302 #define add_double(l1,h1,l2,h2,lv,hv) \
 303   add_double_with_sign (l1, h1, l2, h2, lv, hv, false)
 304 extern int neg_double (unsigned HOST_WIDE_INT, HOST_WIDE_INT,
 305                        unsigned HOST_WIDE_INT *, HOST_WIDE_INT *);
 306 extern int mul_double_with_sign (unsigned HOST_WIDE_INT, HOST_WIDE_INT,
 307                                  unsigned HOST_WIDE_INT, HOST_WIDE_INT,
 308                                  unsigned HOST_WIDE_INT *, HOST_WIDE_INT *,
 309                                  bool);
 310 #define mul_double(l1,h1,l2,h2,lv,hv) \
 311   mul_double_with_sign (l1, h1, l2, h2, lv, hv, false)
 312 extern void lshift_double (unsigned HOST_WIDE_INT, HOST_WIDE_INT,
 313                            HOST_WIDE_INT, unsigned int,
 314                            unsigned HOST_WIDE_INT *, HOST_WIDE_INT *, bool);
 315 extern int div_and_round_double (unsigned, int, unsigned HOST_WIDE_INT,
 316                                  HOST_WIDE_INT, unsigned HOST_WIDE_INT,
 317                                  HOST_WIDE_INT, unsigned HOST_WIDE_INT *,
 318                                  HOST_WIDE_INT *, unsigned HOST_WIDE_INT *,
 319                                  HOST_WIDE_INT *);
 320
 321
 322 #ifndef GENERATOR_FILE
 323 /* Conversion to and from GMP integer representations.  */
 324
 325 void mpz_set_double_int (mpz_t, double_int, bool);
 326 double_int mpz_get_double_int (const_tree, mpz_t, bool);
 327 #endif
 328
 329 #endif /* DOUBLE_INT_H */