]>
Commit | Line | Data |
---|---|---|
1 | /* Operations with long integers. | |
2 | Copyright (C) 2006-2020 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 endianness and word endianness. */ | |
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) const; | |
132 | double_int lshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const; | |
133 | double_int rshift (HOST_WIDE_INT count) const; | |
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. */ | |
145 | ||
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; | |
152 | double_int divmod_with_overflow (double_int, bool, unsigned, | |
153 | double_int *, bool *) const; | |
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; | |
176 | bool ule (double_int b) const; | |
177 | bool ugt (double_int b) const; | |
178 | bool slt (double_int b) const; | |
179 | bool sle (double_int b) const; | |
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 | ||
193 | /* Please migrate away from using these member variables publicly. */ | |
194 | ||
195 | unsigned HOST_WIDE_INT low; | |
196 | HOST_WIDE_INT high; | |
197 | ||
198 | }; | |
199 | ||
200 | #define HOST_BITS_PER_DOUBLE_INT (2 * HOST_BITS_PER_WIDE_INT) | |
201 | ||
202 | /* Constructors and conversions. */ | |
203 | ||
204 | /* Constructs double_int from integer CST. The bits over the precision of | |
205 | HOST_WIDE_INT are filled with the sign bit. */ | |
206 | ||
207 | inline double_int | |
208 | double_int::from_shwi (HOST_WIDE_INT cst) | |
209 | { | |
210 | double_int r; | |
211 | r.low = (unsigned HOST_WIDE_INT) cst; | |
212 | r.high = cst < 0 ? -1 : 0; | |
213 | return r; | |
214 | } | |
215 | ||
216 | /* Some useful constants. */ | |
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. */ | |
220 | ||
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)) | |
226 | ||
227 | /* Constructs double_int from unsigned integer CST. The bits over the | |
228 | precision of HOST_WIDE_INT are filled with zeros. */ | |
229 | ||
230 | inline double_int | |
231 | double_int::from_uhwi (unsigned HOST_WIDE_INT cst) | |
232 | { | |
233 | double_int r; | |
234 | r.low = cst; | |
235 | r.high = 0; | |
236 | return r; | |
237 | } | |
238 | ||
239 | inline double_int | |
240 | double_int::from_pair (HOST_WIDE_INT high, unsigned HOST_WIDE_INT low) | |
241 | { | |
242 | double_int r; | |
243 | r.low = low; | |
244 | r.high = high; | |
245 | return r; | |
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 | ||
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 | ||
283 | /* Returns value of CST as a signed number. CST must satisfy | |
284 | double_int::fits_signed. */ | |
285 | ||
286 | inline HOST_WIDE_INT | |
287 | double_int::to_shwi () const | |
288 | { | |
289 | return (HOST_WIDE_INT) low; | |
290 | } | |
291 | ||
292 | /* Returns value of CST as an unsigned number. CST must satisfy | |
293 | double_int::fits_unsigned. */ | |
294 | ||
295 | inline unsigned HOST_WIDE_INT | |
296 | double_int::to_uhwi () const | |
297 | { | |
298 | return low; | |
299 | } | |
300 | ||
301 | /* Returns true if CST fits in unsigned HOST_WIDE_INT. */ | |
302 | ||
303 | inline bool | |
304 | double_int::fits_uhwi () const | |
305 | { | |
306 | return high == 0; | |
307 | } | |
308 | ||
309 | /* Logical operations. */ | |
310 | ||
311 | /* Returns ~A. */ | |
312 | ||
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 | ||
322 | /* Returns A | B. */ | |
323 | ||
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 | ||
333 | /* Returns A & B. */ | |
334 | ||
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 | ||
344 | /* Returns A & ~B. */ | |
345 | ||
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 | ||
355 | /* Returns A ^ B. */ | |
356 | ||
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 | ||
366 | void dump_double_int (FILE *, double_int, bool); | |
367 | ||
368 | #define ALL_ONES HOST_WIDE_INT_M1U | |
369 | ||
370 | /* The operands of the following comparison functions must be processed | |
371 | with double_int_ext, if their precision is less than | |
372 | HOST_BITS_PER_DOUBLE_INT bits. */ | |
373 | ||
374 | /* Returns true if CST is zero. */ | |
375 | ||
376 | inline bool | |
377 | double_int::is_zero () const | |
378 | { | |
379 | return low == 0 && high == 0; | |
380 | } | |
381 | ||
382 | /* Returns true if CST is one. */ | |
383 | ||
384 | inline bool | |
385 | double_int::is_one () const | |
386 | { | |
387 | return low == 1 && high == 0; | |
388 | } | |
389 | ||
390 | /* Returns true if CST is minus one. */ | |
391 | ||
392 | inline bool | |
393 | double_int::is_minus_one () const | |
394 | { | |
395 | return low == ALL_ONES && high == -1; | |
396 | } | |
397 | ||
398 | /* Returns true if CST is negative. */ | |
399 | ||
400 | inline bool | |
401 | double_int::is_negative () const | |
402 | { | |
403 | return high < 0; | |
404 | } | |
405 | ||
406 | /* Returns true if CST1 == CST2. */ | |
407 | ||
408 | inline bool | |
409 | double_int::operator == (double_int cst2) const | |
410 | { | |
411 | return low == cst2.low && high == cst2.high; | |
412 | } | |
413 | ||
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; | |
420 | } | |
421 | ||
422 | /* Return number of set bits of CST. */ | |
423 | ||
424 | inline int | |
425 | double_int::popcount () const | |
426 | { | |
427 | return popcount_hwi (high) + popcount_hwi (low); | |
428 | } | |
429 | ||
430 | ||
431 | #ifndef GENERATOR_FILE | |
432 | /* Conversion to and from GMP integer representations. */ | |
433 | ||
434 | void mpz_set_double_int (mpz_t, double_int, bool); | |
435 | double_int mpz_get_double_int (const_tree, mpz_t, bool); | |
436 | #endif | |
437 | ||
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 | ||
470 | #endif /* DOUBLE_INT_H */ |