1 | /* Operations with long integers. |
2 | Copyright (C) 2006-2023 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 (x: high) + popcount_hwi (x: 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 = INL_CONST_PRECISION; |
444 | static const bool host_dependent_precision = true; |
445 | static const bool needs_write_val_arg = false; |
446 | static const unsigned int precision = HOST_BITS_PER_DOUBLE_INT; |
447 | static unsigned int get_precision (const double_int &); |
448 | static wi::storage_ref decompose (HOST_WIDE_INT *, unsigned int, |
449 | const double_int &); |
450 | }; |
451 | } |
452 | |
453 | inline unsigned int |
454 | wi::int_traits <double_int>::get_precision (const double_int &) |
455 | { |
456 | return precision; |
457 | } |
458 | |
459 | inline wi::storage_ref |
460 | wi::int_traits <double_int>::decompose (HOST_WIDE_INT *scratch, unsigned int p, |
461 | const double_int &x) |
462 | { |
463 | gcc_checking_assert (precision == p); |
464 | scratch[0] = x.low; |
465 | if ((x.high == 0 && scratch[0] >= 0) || (x.high == -1 && scratch[0] < 0)) |
466 | return wi::storage_ref (scratch, 1, precision); |
467 | scratch[1] = x.high; |
468 | return wi::storage_ref (scratch, 2, precision); |
469 | } |
470 | |
471 | #endif /* DOUBLE_INT_H */ |
472 | |