Branch data Line data Source code
1 : : /* Operations with long integers.
2 : : Copyright (C) 2006-2024 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 : 31 : double_int::from_shwi (HOST_WIDE_INT cst)
209 : : {
210 : 31 : double_int r;
211 : 2206876 : r.low = (unsigned HOST_WIDE_INT) cst;
212 : 2206876 : r.high = cst < 0 ? -1 : 0;
213 : 31 : 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 : 0 : double_int::operator -- ()
257 : : {
258 : 0 : *this -= double_int_one;
259 : 0 : 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 : 0 : double_int::fits_uhwi () const
305 : : {
306 : 0 : 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 : 0 : double_int::operator | (double_int b) const
326 : : {
327 : 0 : double_int result;
328 : 0 : result.low = low | b.low;
329 : 0 : result.high = high | b.high;
330 : 0 : 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 : 0 : double_int::is_zero () const
378 : : {
379 : 0 : 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 : 0 : double_int::is_negative () const
402 : : {
403 : 0 : return high < 0;
404 : : }
405 : :
406 : : /* Returns true if CST1 == CST2. */
407 : :
408 : : inline bool
409 : 0 : double_int::operator == (double_int cst2) const
410 : : {
411 : 0 : return low == cst2.low && high == cst2.high;
412 : : }
413 : :
414 : : /* Returns true if CST1 != CST2. */
415 : :
416 : : inline bool
417 : 0 : double_int::operator != (double_int cst2) const
418 : : {
419 : 0 : 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 = 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 : 7283905 : wi::int_traits <double_int>::decompose (HOST_WIDE_INT *scratch, unsigned int p,
461 : : const double_int &x)
462 : : {
463 : 7283905 : gcc_checking_assert (precision == p);
464 : 7283905 : scratch[0] = x.low;
465 : 7283905 : if ((x.high == 0 && scratch[0] >= 0) || (x.high == -1 && scratch[0] < 0))
466 : 7266666 : return wi::storage_ref (scratch, 1, precision);
467 : 17239 : scratch[1] = x.high;
468 : 17239 : return wi::storage_ref (scratch, 2, precision);
469 : : }
470 : :
471 : : #endif /* DOUBLE_INT_H */
|
