1 /* Operations with long integers. 2 Copyright (C) 2006-2013 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 /* Construct from a fuffer of length LEN. BUFFER will be read according 63 to byte endianess and word endianess. */ 64 static double_int from_buffer (const unsigned char *buffer, int len); 65 66 /* No copy assignment operator or destructor to keep the type a POD. */ 67 68 /* There are some special value-creation static member functions. */ 69 70 static double_int mask (unsigned prec); 71 static double_int max_value (unsigned int prec, bool uns); 72 static double_int min_value (unsigned int prec, bool uns); 73 74 /* The following functions are mutating operations. */ 75 76 double_int &operator ++ (); // prefix 77 double_int &operator -- (); // prefix 78 double_int &operator *= (double_int); 79 double_int &operator += (double_int); 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 85 /* The following functions are non-mutating operations. */ 86 87 /* Conversion functions. */ 88 89 HOST_WIDE_INT to_shwi () const; 90 unsigned HOST_WIDE_INT to_uhwi () const; 91 92 /* Conversion query functions. */ 93 94 bool fits_uhwi () const; 95 bool fits_shwi () const; 96 bool fits_hwi (bool uns) const; 97 98 /* Attribute query functions. */ 99 100 int trailing_zeros () const; 101 int popcount () const; 102 103 /* Arithmetic query operations. */ 104 105 bool multiple_of (double_int, bool, double_int *) const; 106 107 /* Arithmetic operation functions. */ 108 109 /* The following operations perform arithmetics modulo 2^precision, so you 110 do not need to call .ext between them, even if you are representing 111 numbers with precision less than HOST_BITS_PER_DOUBLE_INT bits. */ 112 113 double_int set_bit (unsigned) const; 114 double_int mul_with_sign (double_int, bool unsigned_p, bool *overflow) const; 115 double_int wide_mul_with_sign (double_int, bool unsigned_p, 116 double_int *higher, bool *overflow) const; 117 double_int add_with_sign (double_int, bool unsigned_p, bool *overflow) const; 118 double_int sub_with_overflow (double_int, bool *overflow) const; 119 double_int neg_with_overflow (bool *overflow) const; 120 121 double_int operator * (double_int) const; 122 double_int operator + (double_int) const; 123 double_int operator - (double_int) const; 124 double_int operator - () const; 125 double_int operator ~ () const; 126 double_int operator & (double_int) const; 127 double_int operator | (double_int) const; 128 double_int operator ^ (double_int) const; 129 double_int and_not (double_int) const; 130 131 double_int lshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const; 132 double_int rshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const; 133 double_int alshift (HOST_WIDE_INT count, unsigned int prec) const; 134 double_int arshift (HOST_WIDE_INT count, unsigned int prec) const; 135 double_int llshift (HOST_WIDE_INT count, unsigned int prec) const; 136 double_int lrshift (HOST_WIDE_INT count, unsigned int prec) const; 137 double_int lrotate (HOST_WIDE_INT count, unsigned int prec) const; 138 double_int rrotate (HOST_WIDE_INT count, unsigned int prec) const; 139 140 /* You must ensure that double_int::ext is called on the operands 141 of the following operations, if the precision of the numbers 142 is less than HOST_BITS_PER_DOUBLE_INT bits. */ 143 144 double_int div (double_int, bool, unsigned) const; 145 double_int sdiv (double_int, unsigned) const; 146 double_int udiv (double_int, unsigned) const; 147 double_int mod (double_int, bool, unsigned) const; 148 double_int smod (double_int, unsigned) const; 149 double_int umod (double_int, unsigned) const; 150 double_int divmod_with_overflow (double_int, bool, unsigned, 151 double_int *, bool *) const; 152 double_int divmod (double_int, bool, unsigned, double_int *) const; 153 double_int sdivmod (double_int, unsigned, double_int *) const; 154 double_int udivmod (double_int, unsigned, double_int *) const; 155 156 /* Precision control functions. */ 157 158 double_int ext (unsigned prec, bool uns) const; 159 double_int zext (unsigned prec) const; 160 double_int sext (unsigned prec) const; 161 162 /* Comparative functions. */ 163 164 bool is_zero () const; 165 bool is_one () const; 166 bool is_minus_one () const; 167 bool is_negative () const; 168 169 int cmp (double_int b, bool uns) const; 170 int ucmp (double_int b) const; 171 int scmp (double_int b) const; 172 173 bool ult (double_int b) const; 174 bool ule (double_int b) const; 175 bool ugt (double_int b) const; 176 bool slt (double_int b) const; 177 bool sle (double_int b) const; 178 bool sgt (double_int b) const; 179 180 double_int max (double_int b, bool uns); 181 double_int smax (double_int b); 182 double_int umax (double_int b); 183 184 double_int min (double_int b, bool uns); 185 double_int smin (double_int b); 186 double_int umin (double_int b); 187 188 bool operator == (double_int cst2) const; 189 bool operator != (double_int cst2) const; 190 191 /* Please migrate away from using these member variables publically. */ 192 193 unsigned HOST_WIDE_INT low; 194 HOST_WIDE_INT high; 195 196 }; 197 198 #define HOST_BITS_PER_DOUBLE_INT (2 * HOST_BITS_PER_WIDE_INT) 199 200 /* Constructors and conversions. */ 201 202 /* Constructs double_int from integer CST. The bits over the precision of 203 HOST_WIDE_INT are filled with the sign bit. */ 204 205 inline double_int 206 double_int::from_shwi (HOST_WIDE_INT cst) 207 { 208 double_int r; 209 r.low = (unsigned HOST_WIDE_INT) cst; 210 r.high = cst < 0 ? -1 : 0; 211 return r; 212 } 213 214 /* Some useful constants. */ 215 /* FIXME(crowl): Maybe remove after converting callers? 216 The problem is that a named constant would not be as optimizable, 217 while the functional syntax is more verbose. */ 218 219 #define double_int_minus_one (double_int::from_shwi (-1)) 220 #define double_int_zero (double_int::from_shwi (0)) 221 #define double_int_one (double_int::from_shwi (1)) 222 #define double_int_two (double_int::from_shwi (2)) 223 #define double_int_ten (double_int::from_shwi (10)) 224 225 /* Constructs double_int from unsigned integer CST. The bits over the 226 precision of HOST_WIDE_INT are filled with zeros. */ 227 228 inline double_int 229 double_int::from_uhwi (unsigned HOST_WIDE_INT cst) 230 { 231 double_int r; 232 r.low = cst; 233 r.high = 0; 234 return r; 235 } 236 237 inline double_int 238 double_int::from_pair (HOST_WIDE_INT high, unsigned HOST_WIDE_INT low) 239 { 240 double_int r; 241 r.low = low; 242 r.high = high; 243 return r; 244 } 245 246 inline double_int & 247 double_int::operator ++ () 248 { 249 *this += double_int_one; 250 return *this; 251 } 252 253 inline double_int & 254 double_int::operator -- () 255 { 256 *this -= double_int_one; 257 return *this; 258 } 259 260 inline double_int & 261 double_int::operator *= (double_int b) 262 { 263 *this = *this * b; 264 return *this; 265 } 266 267 inline double_int & 268 double_int::operator += (double_int b) 269 { 270 *this = *this + b; 271 return *this; 272 } 273 274 inline double_int & 275 double_int::operator -= (double_int b) 276 { 277 *this = *this - b; 278 return *this; 279 } 280 281 inline double_int & 282 double_int::operator &= (double_int b) 283 { 284 *this = *this & b; 285 return *this; 286 } 287 288 inline double_int & 289 double_int::operator ^= (double_int b) 290 { 291 *this = *this ^ b; 292 return *this; 293 } 294 295 inline double_int & 296 double_int::operator |= (double_int b) 297 { 298 *this = *this | b; 299 return *this; 300 } 301 302 /* Returns value of CST as a signed number. CST must satisfy 303 double_int::fits_signed. */ 304 305 inline HOST_WIDE_INT 306 double_int::to_shwi () const 307 { 308 return (HOST_WIDE_INT) low; 309 } 310 311 /* Returns value of CST as an unsigned number. CST must satisfy 312 double_int::fits_unsigned. */ 313 314 inline unsigned HOST_WIDE_INT 315 double_int::to_uhwi () const 316 { 317 return low; 318 } 319 320 /* Returns true if CST fits in unsigned HOST_WIDE_INT. */ 321 322 inline bool 323 double_int::fits_uhwi () const 324 { 325 return high == 0; 326 } 327 328 /* Logical operations. */ 329 330 /* Returns ~A. */ 331 332 inline double_int 333 double_int::operator ~ () const 334 { 335 double_int result; 336 result.low = ~low; 337 result.high = ~high; 338 return result; 339 } 340 341 /* Returns A | B. */ 342 343 inline double_int 344 double_int::operator | (double_int b) const 345 { 346 double_int result; 347 result.low = low | b.low; 348 result.high = high | b.high; 349 return result; 350 } 351 352 /* Returns A & B. */ 353 354 inline double_int 355 double_int::operator & (double_int b) const 356 { 357 double_int result; 358 result.low = low & b.low; 359 result.high = high & b.high; 360 return result; 361 } 362 363 /* Returns A & ~B. */ 364 365 inline double_int 366 double_int::and_not (double_int b) const 367 { 368 double_int result; 369 result.low = low & ~b.low; 370 result.high = high & ~b.high; 371 return result; 372 } 373 374 /* Returns A ^ B. */ 375 376 inline double_int 377 double_int::operator ^ (double_int b) const 378 { 379 double_int result; 380 result.low = low ^ b.low; 381 result.high = high ^ b.high; 382 return result; 383 } 384 385 void dump_double_int (FILE *, double_int, bool); 386 387 #define ALL_ONES (~((unsigned HOST_WIDE_INT) 0)) 388 389 /* The operands of the following comparison functions must be processed 390 with double_int_ext, if their precision is less than 391 HOST_BITS_PER_DOUBLE_INT bits. */ 392 393 /* Returns true if CST is zero. */ 394 395 inline bool 396 double_int::is_zero () const 397 { 398 return low == 0 && high == 0; 399 } 400 401 /* Returns true if CST is one. */ 402 403 inline bool 404 double_int::is_one () const 405 { 406 return low == 1 && high == 0; 407 } 408 409 /* Returns true if CST is minus one. */ 410 411 inline bool 412 double_int::is_minus_one () const 413 { 414 return low == ALL_ONES && high == -1; 415 } 416 417 /* Returns true if CST is negative. */ 418 419 inline bool 420 double_int::is_negative () const 421 { 422 return high < 0; 423 } 424 425 /* Returns true if CST1 == CST2. */ 426 427 inline bool 428 double_int::operator == (double_int cst2) const 429 { 430 return low == cst2.low && high == cst2.high; 431 } 432 433 /* Returns true if CST1 != CST2. */ 434 435 inline bool 436 double_int::operator != (double_int cst2) const 437 { 438 return low != cst2.low || high != cst2.high; 439 } 440 441 /* Return number of set bits of CST. */ 442 443 inline int 444 double_int::popcount () const 445 { 446 return popcount_hwi (high) + popcount_hwi (low); 447 } 448 449 450 #ifndef GENERATOR_FILE 451 /* Conversion to and from GMP integer representations. */ 452 453 void mpz_set_double_int (mpz_t, double_int, bool); 454 double_int mpz_get_double_int (const_tree, mpz_t, bool); 455 #endif 456 457 #endif /* DOUBLE_INT_H */ 458
