1/* Operations with long integers.
2   Copyright (C) 2006-2020 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it
7under the terms of the GNU General Public License as published by the
8Free Software Foundation; either version 3, or (at your option) any
9later version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT
12ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along 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
49struct 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
207inline double_int
208double_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
230inline double_int
231double_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
239inline double_int
240double_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
248inline double_int &
249double_int::operator ++ ()
250{
251  *this += double_int_one;
252  return *this;
253}
254
255inline double_int &
256double_int::operator -- ()
257{
258  *this -= double_int_one;
259  return *this;
260}
261
262inline double_int &
263double_int::operator &= (double_int b)
264{
265  *this = *this & b;
266  return *this;
267}
268
269inline double_int &
270double_int::operator ^= (double_int b)
271{
272  *this = *this ^ b;
273  return *this;
274}
275
276inline double_int &
277double_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
286inline HOST_WIDE_INT
287double_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
295inline unsigned HOST_WIDE_INT
296double_int::to_uhwi () const
297{
298  return low;
299}
300
301/* Returns true if CST fits in unsigned HOST_WIDE_INT.  */
302
303inline bool
304double_int::fits_uhwi () const
305{
306  return high == 0;
307}
308
309/* Logical operations.  */
310
311/* Returns ~A.  */
312
313inline double_int
314double_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
324inline double_int
325double_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
335inline double_int
336double_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
346inline double_int
347double_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
357inline double_int
358double_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
366void 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
376inline bool
377double_int::is_zero () const
378{
379  return low == 0 && high == 0;
380}
381
382/* Returns true if CST is one.  */
383
384inline bool
385double_int::is_one () const
386{
387  return low == 1 && high == 0;
388}
389
390/* Returns true if CST is minus one.  */
391
392inline bool
393double_int::is_minus_one () const
394{
395  return low == ALL_ONES && high == -1;
396}
397
398/* Returns true if CST is negative.  */
399
400inline bool
401double_int::is_negative () const
402{
403  return high < 0;
404}
405
406/* Returns true if CST1 == CST2.  */
407
408inline bool
409double_int::operator == (double_int cst2) const
410{
411  return low == cst2.low && high == cst2.high;
412}
413
414/* Returns true if CST1 != CST2.  */
415
416inline bool
417double_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
424inline int
425double_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
434void mpz_set_double_int (mpz_t, double_int, bool);
435double_int mpz_get_double_int (const_tree, mpz_t, bool);
436#endif
437
438namespace 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
452inline unsigned int
453wi::int_traits <double_int>::get_precision (const double_int &)
454{
455  return precision;
456}
457
458inline wi::storage_ref
459wi::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 */
471