]>
Commit | Line | Data |
---|---|---|
99748102 | 1 | /* Operations with long integers. |
fbd26352 | 2 | Copyright (C) 2006-2019 Free Software Foundation, Inc. |
48e1416a | 3 | |
99748102 | 4 | This file is part of GCC. |
48e1416a | 5 | |
99748102 | 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 | |
8c4c00c1 | 8 | Free Software Foundation; either version 3, or (at your option) any |
99748102 | 9 | later version. |
48e1416a | 10 | |
99748102 | 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. | |
48e1416a | 15 | |
99748102 | 16 | You should have received a copy of the GNU General Public License |
8c4c00c1 | 17 | along with GCC; see the file COPYING3. If not see |
18 | <http://www.gnu.org/licenses/>. */ | |
99748102 | 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 | |
4562961a | 46 | numbers with precision higher than HOST_WIDE_INT). It might be less |
99748102 | 47 | confusing to have them both signed or both unsigned. */ |
48 | ||
cf8f0e63 | 49 | struct double_int |
99748102 | 50 | { |
2b15d2ba | 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 | ||
eb7e53de | 58 | static double_int from_uhwi (unsigned HOST_WIDE_INT cst); |
59 | static double_int from_shwi (HOST_WIDE_INT cst); | |
d67b7119 | 60 | static double_int from_pair (HOST_WIDE_INT high, unsigned HOST_WIDE_INT low); |
2b15d2ba | 61 | |
52cd005d | 62 | /* Construct from a fuffer of length LEN. BUFFER will be read according |
d0abd9e0 | 63 | to byte endianness and word endianness. */ |
52cd005d | 64 | static double_int from_buffer (const unsigned char *buffer, int len); |
65 | ||
2b15d2ba | 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); | |
cf8f0e63 | 81 | double_int &operator &= (double_int); |
82 | double_int &operator ^= (double_int); | |
83 | double_int &operator |= (double_int); | |
2b15d2ba | 84 | |
85 | /* The following functions are non-mutating operations. */ | |
86 | ||
87 | /* Conversion functions. */ | |
88 | ||
eb7e53de | 89 | HOST_WIDE_INT to_shwi () const; |
90 | unsigned HOST_WIDE_INT to_uhwi () const; | |
2b15d2ba | 91 | |
92 | /* Conversion query functions. */ | |
93 | ||
eb7e53de | 94 | bool fits_uhwi () const; |
95 | bool fits_shwi () const; | |
96 | bool fits_hwi (bool uns) const; | |
2b15d2ba | 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 | ||
d67b7119 | 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 | ||
2b15d2ba | 113 | double_int set_bit (unsigned) const; |
cf8f0e63 | 114 | double_int mul_with_sign (double_int, bool unsigned_p, bool *overflow) const; |
d67b7119 | 115 | double_int wide_mul_with_sign (double_int, bool unsigned_p, |
116 | double_int *higher, bool *overflow) const; | |
cf8f0e63 | 117 | double_int add_with_sign (double_int, bool unsigned_p, bool *overflow) const; |
d67b7119 | 118 | double_int sub_with_overflow (double_int, bool *overflow) const; |
119 | double_int neg_with_overflow (bool *overflow) const; | |
2b15d2ba | 120 | |
cf8f0e63 | 121 | double_int operator * (double_int) const; |
122 | double_int operator + (double_int) const; | |
123 | double_int operator - (double_int) const; | |
2b15d2ba | 124 | double_int operator - () const; |
125 | double_int operator ~ () const; | |
cf8f0e63 | 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; | |
2b15d2ba | 130 | |
9a8b9e26 | 131 | double_int lshift (HOST_WIDE_INT count) const; |
2b15d2ba | 132 | double_int lshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const; |
75aefb7b | 133 | double_int rshift (HOST_WIDE_INT count) const; |
2b15d2ba | 134 | double_int rshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const; |
135 | double_int alshift (HOST_WIDE_INT count, unsigned int prec) const; | |
136 | double_int arshift (HOST_WIDE_INT count, unsigned int prec) const; | |
137 | double_int llshift (HOST_WIDE_INT count, unsigned int prec) const; | |
138 | double_int lrshift (HOST_WIDE_INT count, unsigned int prec) const; | |
139 | double_int lrotate (HOST_WIDE_INT count, unsigned int prec) const; | |
140 | double_int rrotate (HOST_WIDE_INT count, unsigned int prec) const; | |
141 | ||
142 | /* You must ensure that double_int::ext is called on the operands | |
143 | of the following operations, if the precision of the numbers | |
144 | is less than HOST_BITS_PER_DOUBLE_INT bits. */ | |
d67b7119 | 145 | |
2b15d2ba | 146 | double_int div (double_int, bool, unsigned) const; |
147 | double_int sdiv (double_int, unsigned) const; | |
148 | double_int udiv (double_int, unsigned) const; | |
149 | double_int mod (double_int, bool, unsigned) const; | |
150 | double_int smod (double_int, unsigned) const; | |
151 | double_int umod (double_int, unsigned) const; | |
d67b7119 | 152 | double_int divmod_with_overflow (double_int, bool, unsigned, |
153 | double_int *, bool *) const; | |
2b15d2ba | 154 | double_int divmod (double_int, bool, unsigned, double_int *) const; |
155 | double_int sdivmod (double_int, unsigned, double_int *) const; | |
156 | double_int udivmod (double_int, unsigned, double_int *) const; | |
157 | ||
158 | /* Precision control functions. */ | |
159 | ||
160 | double_int ext (unsigned prec, bool uns) const; | |
161 | double_int zext (unsigned prec) const; | |
162 | double_int sext (unsigned prec) const; | |
163 | ||
164 | /* Comparative functions. */ | |
165 | ||
166 | bool is_zero () const; | |
167 | bool is_one () const; | |
168 | bool is_minus_one () const; | |
169 | bool is_negative () const; | |
170 | ||
171 | int cmp (double_int b, bool uns) const; | |
172 | int ucmp (double_int b) const; | |
173 | int scmp (double_int b) const; | |
174 | ||
175 | bool ult (double_int b) const; | |
cf8f0e63 | 176 | bool ule (double_int b) const; |
2b15d2ba | 177 | bool ugt (double_int b) const; |
178 | bool slt (double_int b) const; | |
cf8f0e63 | 179 | bool sle (double_int b) const; |
2b15d2ba | 180 | bool sgt (double_int b) const; |
181 | ||
182 | double_int max (double_int b, bool uns); | |
183 | double_int smax (double_int b); | |
184 | double_int umax (double_int b); | |
185 | ||
186 | double_int min (double_int b, bool uns); | |
187 | double_int smin (double_int b); | |
188 | double_int umin (double_int b); | |
189 | ||
190 | bool operator == (double_int cst2) const; | |
191 | bool operator != (double_int cst2) const; | |
192 | ||
a04e8d62 | 193 | /* Please migrate away from using these member variables publicly. */ |
2b15d2ba | 194 | |
99748102 | 195 | unsigned HOST_WIDE_INT low; |
196 | HOST_WIDE_INT high; | |
2b15d2ba | 197 | |
cf8f0e63 | 198 | }; |
99748102 | 199 | |
41283922 | 200 | #define HOST_BITS_PER_DOUBLE_INT (2 * HOST_BITS_PER_WIDE_INT) |
201 | ||
99748102 | 202 | /* Constructors and conversions. */ |
203 | ||
99748102 | 204 | /* Constructs double_int from integer CST. The bits over the precision of |
205 | HOST_WIDE_INT are filled with the sign bit. */ | |
206 | ||
cf8f0e63 | 207 | inline double_int |
208 | double_int::from_shwi (HOST_WIDE_INT cst) | |
99748102 | 209 | { |
210 | double_int r; | |
99748102 | 211 | r.low = (unsigned HOST_WIDE_INT) cst; |
212 | r.high = cst < 0 ? -1 : 0; | |
99748102 | 213 | return r; |
214 | } | |
215 | ||
216 | /* Some useful constants. */ | |
2b15d2ba | 217 | /* FIXME(crowl): Maybe remove after converting callers? |
218 | The problem is that a named constant would not be as optimizable, | |
219 | while the functional syntax is more verbose. */ | |
99748102 | 220 | |
eb7e53de | 221 | #define double_int_minus_one (double_int::from_shwi (-1)) |
222 | #define double_int_zero (double_int::from_shwi (0)) | |
223 | #define double_int_one (double_int::from_shwi (1)) | |
224 | #define double_int_two (double_int::from_shwi (2)) | |
225 | #define double_int_ten (double_int::from_shwi (10)) | |
99748102 | 226 | |
227 | /* Constructs double_int from unsigned integer CST. The bits over the | |
228 | precision of HOST_WIDE_INT are filled with zeros. */ | |
229 | ||
cf8f0e63 | 230 | inline double_int |
231 | double_int::from_uhwi (unsigned HOST_WIDE_INT cst) | |
99748102 | 232 | { |
233 | double_int r; | |
99748102 | 234 | r.low = cst; |
235 | r.high = 0; | |
99748102 | 236 | return r; |
237 | } | |
238 | ||
d67b7119 | 239 | inline double_int |
240 | double_int::from_pair (HOST_WIDE_INT high, unsigned HOST_WIDE_INT low) | |
2b15d2ba | 241 | { |
d67b7119 | 242 | double_int r; |
243 | r.low = low; | |
244 | r.high = high; | |
245 | return r; | |
2b15d2ba | 246 | } |
247 | ||
248 | inline double_int & | |
249 | double_int::operator ++ () | |
250 | { | |
251 | *this += double_int_one; | |
252 | return *this; | |
253 | } | |
254 | ||
255 | inline double_int & | |
256 | double_int::operator -- () | |
257 | { | |
258 | *this -= double_int_one; | |
259 | return *this; | |
260 | } | |
261 | ||
cf8f0e63 | 262 | inline double_int & |
263 | double_int::operator &= (double_int b) | |
264 | { | |
265 | *this = *this & b; | |
266 | return *this; | |
267 | } | |
268 | ||
269 | inline double_int & | |
270 | double_int::operator ^= (double_int b) | |
271 | { | |
272 | *this = *this ^ b; | |
273 | return *this; | |
274 | } | |
275 | ||
276 | inline double_int & | |
277 | double_int::operator |= (double_int b) | |
278 | { | |
279 | *this = *this | b; | |
280 | return *this; | |
281 | } | |
282 | ||
90739616 | 283 | /* Returns value of CST as a signed number. CST must satisfy |
2b15d2ba | 284 | double_int::fits_signed. */ |
90739616 | 285 | |
2b15d2ba | 286 | inline HOST_WIDE_INT |
eb7e53de | 287 | double_int::to_shwi () const |
2b15d2ba | 288 | { |
289 | return (HOST_WIDE_INT) low; | |
290 | } | |
291 | ||
90739616 | 292 | /* Returns value of CST as an unsigned number. CST must satisfy |
2b15d2ba | 293 | double_int::fits_unsigned. */ |
294 | ||
295 | inline unsigned HOST_WIDE_INT | |
eb7e53de | 296 | double_int::to_uhwi () const |
2b15d2ba | 297 | { |
298 | return low; | |
299 | } | |
90739616 | 300 | |
90739616 | 301 | /* Returns true if CST fits in unsigned HOST_WIDE_INT. */ |
302 | ||
2b15d2ba | 303 | inline bool |
eb7e53de | 304 | double_int::fits_uhwi () const |
2b15d2ba | 305 | { |
306 | return high == 0; | |
307 | } | |
308 | ||
41283922 | 309 | /* Logical operations. */ |
c5083e8b | 310 | |
311 | /* Returns ~A. */ | |
312 | ||
2b15d2ba | 313 | inline double_int |
314 | double_int::operator ~ () const | |
315 | { | |
316 | double_int result; | |
317 | result.low = ~low; | |
318 | result.high = ~high; | |
319 | return result; | |
320 | } | |
321 | ||
c5083e8b | 322 | /* Returns A | B. */ |
323 | ||
2b15d2ba | 324 | inline double_int |
325 | double_int::operator | (double_int b) const | |
326 | { | |
327 | double_int result; | |
328 | result.low = low | b.low; | |
329 | result.high = high | b.high; | |
330 | return result; | |
331 | } | |
332 | ||
d817d01d | 333 | /* Returns A & B. */ |
334 | ||
2b15d2ba | 335 | inline double_int |
336 | double_int::operator & (double_int b) const | |
337 | { | |
338 | double_int result; | |
339 | result.low = low & b.low; | |
340 | result.high = high & b.high; | |
341 | return result; | |
342 | } | |
343 | ||
4e948a99 | 344 | /* Returns A & ~B. */ |
345 | ||
2b15d2ba | 346 | inline double_int |
347 | double_int::and_not (double_int b) const | |
348 | { | |
349 | double_int result; | |
350 | result.low = low & ~b.low; | |
351 | result.high = high & ~b.high; | |
352 | return result; | |
353 | } | |
354 | ||
90739616 | 355 | /* Returns A ^ B. */ |
356 | ||
2b15d2ba | 357 | inline double_int |
358 | double_int::operator ^ (double_int b) const | |
359 | { | |
360 | double_int result; | |
361 | result.low = low ^ b.low; | |
362 | result.high = high ^ b.high; | |
363 | return result; | |
364 | } | |
365 | ||
99748102 | 366 | void dump_double_int (FILE *, double_int, bool); |
367 | ||
7097b942 | 368 | #define ALL_ONES HOST_WIDE_INT_M1U |
99748102 | 369 | |
370 | /* The operands of the following comparison functions must be processed | |
371 | with double_int_ext, if their precision is less than | |
24cd46a7 | 372 | HOST_BITS_PER_DOUBLE_INT bits. */ |
99748102 | 373 | |
374 | /* Returns true if CST is zero. */ | |
375 | ||
2b15d2ba | 376 | inline bool |
377 | double_int::is_zero () const | |
378 | { | |
379 | return low == 0 && high == 0; | |
380 | } | |
381 | ||
99748102 | 382 | /* Returns true if CST is one. */ |
383 | ||
2b15d2ba | 384 | inline bool |
385 | double_int::is_one () const | |
386 | { | |
387 | return low == 1 && high == 0; | |
388 | } | |
389 | ||
99748102 | 390 | /* Returns true if CST is minus one. */ |
391 | ||
2b15d2ba | 392 | inline bool |
393 | double_int::is_minus_one () const | |
394 | { | |
395 | return low == ALL_ONES && high == -1; | |
396 | } | |
397 | ||
2b15d2ba | 398 | /* Returns true if CST is negative. */ |
399 | ||
400 | inline bool | |
401 | double_int::is_negative () const | |
402 | { | |
403 | return high < 0; | |
99748102 | 404 | } |
405 | ||
406 | /* Returns true if CST1 == CST2. */ | |
407 | ||
2b15d2ba | 408 | inline bool |
409 | double_int::operator == (double_int cst2) const | |
410 | { | |
411 | return low == cst2.low && high == cst2.high; | |
412 | } | |
413 | ||
2b15d2ba | 414 | /* Returns true if CST1 != CST2. */ |
415 | ||
416 | inline bool | |
417 | double_int::operator != (double_int cst2) const | |
418 | { | |
419 | return low != cst2.low || high != cst2.high; | |
99748102 | 420 | } |
421 | ||
45105ae2 | 422 | /* Return number of set bits of CST. */ |
423 | ||
2b15d2ba | 424 | inline int |
425 | double_int::popcount () const | |
426 | { | |
427 | return popcount_hwi (high) + popcount_hwi (low); | |
428 | } | |
429 | ||
b2afff2d | 430 | |
e506f1d4 | 431 | #ifndef GENERATOR_FILE |
612a17fc | 432 | /* Conversion to and from GMP integer representations. */ |
433 | ||
434 | void mpz_set_double_int (mpz_t, double_int, bool); | |
1f1872fd | 435 | double_int mpz_get_double_int (const_tree, mpz_t, bool); |
e506f1d4 | 436 | #endif |
612a17fc | 437 | |
796b6678 | 438 | namespace wi |
439 | { | |
440 | template <> | |
441 | struct int_traits <double_int> | |
442 | { | |
443 | static const enum precision_type precision_type = CONST_PRECISION; | |
444 | static const bool host_dependent_precision = true; | |
445 | static const unsigned int precision = HOST_BITS_PER_DOUBLE_INT; | |
446 | static unsigned int get_precision (const double_int &); | |
447 | static wi::storage_ref decompose (HOST_WIDE_INT *, unsigned int, | |
448 | const double_int &); | |
449 | }; | |
450 | } | |
451 | ||
452 | inline unsigned int | |
453 | wi::int_traits <double_int>::get_precision (const double_int &) | |
454 | { | |
455 | return precision; | |
456 | } | |
457 | ||
458 | inline wi::storage_ref | |
459 | wi::int_traits <double_int>::decompose (HOST_WIDE_INT *scratch, unsigned int p, | |
460 | const double_int &x) | |
461 | { | |
462 | gcc_checking_assert (precision == p); | |
463 | scratch[0] = x.low; | |
464 | if ((x.high == 0 && scratch[0] >= 0) || (x.high == -1 && scratch[0] < 0)) | |
465 | return wi::storage_ref (scratch, 1, precision); | |
466 | scratch[1] = x.high; | |
467 | return wi::storage_ref (scratch, 2, precision); | |
468 | } | |
469 | ||
99748102 | 470 | #endif /* DOUBLE_INT_H */ |