1/* Operations with long integers.
2   Copyright (C) 2006-2015 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#include "wide-int.h"
24
25/* A large integer is currently represented as a pair of HOST_WIDE_INTs.
26   It therefore represents a number with precision of
27   2 * HOST_BITS_PER_WIDE_INT bits (it is however possible that the
28   internal representation will change, if numbers with greater precision
29   are needed, so the users should not rely on it).  The representation does
30   not contain any information about signedness of the represented value, so
31   it can be used to represent both signed and unsigned numbers.  For
32   operations where the results depend on signedness (division, comparisons),
33   it must be specified separately.  For each such operation, there are three
34   versions of the function -- double_int_op, that takes an extra UNS argument
35   giving the signedness of the values, and double_int_sop and double_int_uop
36   that stand for its specializations for signed and unsigned values.
37
38   You may also represent with numbers in smaller precision using double_int.
39   You however need to use double_int_ext (that fills in the bits of the
40   number over the prescribed precision with zeros or with the sign bit) before
41   operations that do not perform arithmetics modulo 2^precision (comparisons,
42   division), and possibly before storing the results, if you want to keep
43   them in some canonical form).  In general, the signedness of double_int_ext
44   should match the signedness of the operation.
45
46   ??? The components of double_int differ in signedness mostly for
47   historical reasons (they replace an older structure used to represent
48   numbers with precision higher than HOST_WIDE_INT).  It might be less
49   confusing to have them both signed or both unsigned.  */
50
51struct double_int
52{
53  /* Normally, we would define constructors to create instances.
54     Two things prevent us from doing so.
55     First, defining a constructor makes the class non-POD in C++03,
56     and we certainly want double_int to be a POD.
57     Second, the GCC conding conventions prefer explicit conversion,
58     and explicit conversion operators are not available until C++11.  */
59
60  static double_int from_uhwi (unsigned HOST_WIDE_INT cst);
61  static double_int from_shwi (HOST_WIDE_INT cst);
62  static double_int from_pair (HOST_WIDE_INT high, unsigned HOST_WIDE_INT low);
63
64  /* Construct from a fuffer of length LEN.  BUFFER will be read according
65     to byte endianess and word endianess.  */
66  static double_int from_buffer (const unsigned char *buffer, int len);
67
68  /* No copy assignment operator or destructor to keep the type a POD.  */
69
70  /* There are some special value-creation static member functions.  */
71
72  static double_int mask (unsigned prec);
73  static double_int max_value (unsigned int prec, bool uns);
74  static double_int min_value (unsigned int prec, bool uns);
75
76  /* The following functions are mutating operations.  */
77
78  double_int &operator ++ (); // prefix
79  double_int &operator -- (); // prefix
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  double_int &operator ^= (double_int);
85  double_int &operator |= (double_int);
86
87  /* The following functions are non-mutating operations.  */
88
89  /* Conversion functions.  */
90
91  HOST_WIDE_INT to_shwi () const;
92  unsigned HOST_WIDE_INT to_uhwi () const;
93
94  /* Conversion query functions.  */
95
96  bool fits_uhwi () const;
97  bool fits_shwi () const;
98  bool fits_hwi (bool uns) const;
99
100  /* Attribute query functions.  */
101
102  int trailing_zeros () const;
103  int popcount () const;
104
105  /* Arithmetic query operations.  */
106
107  bool multiple_of (double_int, bool, double_int *) const;
108
109  /* Arithmetic operation functions.  */
110
111  /* The following operations perform arithmetics modulo 2^precision, so you
112     do not need to call .ext between them, even if you are representing
113     numbers with precision less than HOST_BITS_PER_DOUBLE_INT bits.  */
114
115  double_int set_bit (unsigned) const;
116  double_int mul_with_sign (double_int, bool unsigned_p, bool *overflow) const;
117  double_int wide_mul_with_sign (double_int, bool unsigned_p,
118				 double_int *higher, bool *overflow) const;
119  double_int add_with_sign (double_int, bool unsigned_p, bool *overflow) const;
120  double_int sub_with_overflow (double_int, bool *overflow) const;
121  double_int neg_with_overflow (bool *overflow) const;
122
123  double_int operator * (double_int) const;
124  double_int operator + (double_int) const;
125  double_int operator - (double_int) const;
126  double_int operator - () const;
127  double_int operator ~ () const;
128  double_int operator & (double_int) const;
129  double_int operator | (double_int) const;
130  double_int operator ^ (double_int) const;
131  double_int and_not (double_int) const;
132
133  double_int lshift (HOST_WIDE_INT count) const;
134  double_int lshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const;
135  double_int rshift (HOST_WIDE_INT count) const;
136  double_int rshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const;
137  double_int alshift (HOST_WIDE_INT count, unsigned int prec) const;
138  double_int arshift (HOST_WIDE_INT count, unsigned int prec) const;
139  double_int llshift (HOST_WIDE_INT count, unsigned int prec) const;
140  double_int lrshift (HOST_WIDE_INT count, unsigned int prec) const;
141  double_int lrotate (HOST_WIDE_INT count, unsigned int prec) const;
142  double_int rrotate (HOST_WIDE_INT count, unsigned int prec) const;
143
144  /* You must ensure that double_int::ext is called on the operands
145     of the following operations, if the precision of the numbers
146     is less than HOST_BITS_PER_DOUBLE_INT bits.  */
147
148  double_int div (double_int, bool, unsigned) const;
149  double_int sdiv (double_int, unsigned) const;
150  double_int udiv (double_int, unsigned) const;
151  double_int mod (double_int, bool, unsigned) const;
152  double_int smod (double_int, unsigned) const;
153  double_int umod (double_int, unsigned) const;
154  double_int divmod_with_overflow (double_int, bool, unsigned,
155				   double_int *, bool *) const;
156  double_int divmod (double_int, bool, unsigned, double_int *) const;
157  double_int sdivmod (double_int, unsigned, double_int *) const;
158  double_int udivmod (double_int, unsigned, double_int *) const;
159
160  /* Precision control functions.  */
161
162  double_int ext (unsigned prec, bool uns) const;
163  double_int zext (unsigned prec) const;
164  double_int sext (unsigned prec) const;
165
166  /* Comparative functions.  */
167
168  bool is_zero () const;
169  bool is_one () const;
170  bool is_minus_one () const;
171  bool is_negative () const;
172
173  int cmp (double_int b, bool uns) const;
174  int ucmp (double_int b) const;
175  int scmp (double_int b) const;
176
177  bool ult (double_int b) const;
178  bool ule (double_int b) const;
179  bool ugt (double_int b) const;
180  bool slt (double_int b) const;
181  bool sle (double_int b) const;
182  bool sgt (double_int b) const;
183
184  double_int max (double_int b, bool uns);
185  double_int smax (double_int b);
186  double_int umax (double_int b);
187
188  double_int min (double_int b, bool uns);
189  double_int smin (double_int b);
190  double_int umin (double_int b);
191
192  bool operator == (double_int cst2) const;
193  bool operator != (double_int cst2) const;
194
195  /* Please migrate away from using these member variables publicly.  */
196
197  unsigned HOST_WIDE_INT low;
198  HOST_WIDE_INT high;
199
200};
201
202#define HOST_BITS_PER_DOUBLE_INT (2 * HOST_BITS_PER_WIDE_INT)
203
204/* Constructors and conversions.  */
205
206/* Constructs double_int from integer CST.  The bits over the precision of
207   HOST_WIDE_INT are filled with the sign bit.  */
208
209inline double_int
210double_int::from_shwi (HOST_WIDE_INT cst)
211{
212  double_int r;
213  r.low = (unsigned HOST_WIDE_INT) cst;
214  r.high = cst < 0 ? -1 : 0;
215  return r;
216}
217
218/* Some useful constants.  */
219/* FIXME(crowl): Maybe remove after converting callers?
220   The problem is that a named constant would not be as optimizable,
221   while the functional syntax is more verbose.  */
222
223#define double_int_minus_one (double_int::from_shwi (-1))
224#define double_int_zero (double_int::from_shwi (0))
225#define double_int_one (double_int::from_shwi (1))
226#define double_int_two (double_int::from_shwi (2))
227#define double_int_ten (double_int::from_shwi (10))
228
229/* Constructs double_int from unsigned integer CST.  The bits over the
230   precision of HOST_WIDE_INT are filled with zeros.  */
231
232inline double_int
233double_int::from_uhwi (unsigned HOST_WIDE_INT cst)
234{
235  double_int r;
236  r.low = cst;
237  r.high = 0;
238  return r;
239}
240
241inline double_int
242double_int::from_pair (HOST_WIDE_INT high, unsigned HOST_WIDE_INT low)
243{
244  double_int r;
245  r.low = low;
246  r.high = high;
247  return r;
248}
249
250inline double_int &
251double_int::operator ++ ()
252{
253  *this += double_int_one;
254  return *this;
255}
256
257inline double_int &
258double_int::operator -- ()
259{
260  *this -= double_int_one;
261  return *this;
262}
263
264inline double_int &
265double_int::operator &= (double_int b)
266{
267  *this = *this & b;
268  return *this;
269}
270
271inline double_int &
272double_int::operator ^= (double_int b)
273{
274  *this = *this ^ b;
275  return *this;
276}
277
278inline double_int &
279double_int::operator |= (double_int b)
280{
281  *this = *this | b;
282  return *this;
283}
284
285/* Returns value of CST as a signed number.  CST must satisfy
286   double_int::fits_signed.  */
287
288inline HOST_WIDE_INT
289double_int::to_shwi () const
290{
291  return (HOST_WIDE_INT) low;
292}
293
294/* Returns value of CST as an unsigned number.  CST must satisfy
295   double_int::fits_unsigned.  */
296
297inline unsigned HOST_WIDE_INT
298double_int::to_uhwi () const
299{
300  return low;
301}
302
303/* Returns true if CST fits in unsigned HOST_WIDE_INT.  */
304
305inline bool
306double_int::fits_uhwi () const
307{
308  return high == 0;
309}
310
311/* Logical operations.  */
312
313/* Returns ~A.  */
314
315inline double_int
316double_int::operator ~ () const
317{
318  double_int result;
319  result.low = ~low;
320  result.high = ~high;
321  return result;
322}
323
324/* Returns A | B.  */
325
326inline double_int
327double_int::operator | (double_int b) const
328{
329  double_int result;
330  result.low = low | b.low;
331  result.high = high | b.high;
332  return result;
333}
334
335/* Returns A & B.  */
336
337inline double_int
338double_int::operator & (double_int b) const
339{
340  double_int result;
341  result.low = low & b.low;
342  result.high = high & b.high;
343  return result;
344}
345
346/* Returns A & ~B.  */
347
348inline double_int
349double_int::and_not (double_int b) const
350{
351  double_int result;
352  result.low = low & ~b.low;
353  result.high = high & ~b.high;
354  return result;
355}
356
357/* Returns A ^ B.  */
358
359inline double_int
360double_int::operator ^ (double_int b) const
361{
362  double_int result;
363  result.low = low ^ b.low;
364  result.high = high ^ b.high;
365  return result;
366}
367
368void dump_double_int (FILE *, double_int, bool);
369
370#define ALL_ONES (~((unsigned HOST_WIDE_INT) 0))
371
372/* The operands of the following comparison functions must be processed
373   with double_int_ext, if their precision is less than
374   HOST_BITS_PER_DOUBLE_INT bits.  */
375
376/* Returns true if CST is zero.  */
377
378inline bool
379double_int::is_zero () const
380{
381  return low == 0 && high == 0;
382}
383
384/* Returns true if CST is one.  */
385
386inline bool
387double_int::is_one () const
388{
389  return low == 1 && high == 0;
390}
391
392/* Returns true if CST is minus one.  */
393
394inline bool
395double_int::is_minus_one () const
396{
397  return low == ALL_ONES && high == -1;
398}
399
400/* Returns true if CST is negative.  */
401
402inline bool
403double_int::is_negative () const
404{
405  return high < 0;
406}
407
408/* Returns true if CST1 == CST2.  */
409
410inline bool
411double_int::operator == (double_int cst2) const
412{
413  return low == cst2.low && high == cst2.high;
414}
415
416/* Returns true if CST1 != CST2.  */
417
418inline bool
419double_int::operator != (double_int cst2) const
420{
421  return low != cst2.low || high != cst2.high;
422}
423
424/* Return number of set bits of CST.  */
425
426inline int
427double_int::popcount () const
428{
429  return popcount_hwi (high) + popcount_hwi (low);
430}
431
432
433#ifndef GENERATOR_FILE
434/* Conversion to and from GMP integer representations.  */
435
436void mpz_set_double_int (mpz_t, double_int, bool);
437double_int mpz_get_double_int (const_tree, mpz_t, bool);
438#endif
439
440namespace wi
441{
442  template <>
443  struct int_traits <double_int>
444  {
445    static const enum precision_type precision_type = CONST_PRECISION;
446    static const bool host_dependent_precision = true;
447    static const unsigned int precision = HOST_BITS_PER_DOUBLE_INT;
448    static unsigned int get_precision (const double_int &);
449    static wi::storage_ref decompose (HOST_WIDE_INT *, unsigned int,
450				      const double_int &);
451  };
452}
453
454inline unsigned int
455wi::int_traits <double_int>::get_precision (const double_int &)
456{
457  return precision;
458}
459
460inline wi::storage_ref
461wi::int_traits <double_int>::decompose (HOST_WIDE_INT *scratch, unsigned int p,
462					const double_int &x)
463{
464  gcc_checking_assert (precision == p);
465  scratch[0] = x.low;
466  if ((x.high == 0 && scratch[0] >= 0) || (x.high == -1 && scratch[0] < 0))
467    return wi::storage_ref (scratch, 1, precision);
468  scratch[1] = x.high;
469  return wi::storage_ref (scratch, 2, precision);
470}
471
472#endif /* DOUBLE_INT_H */
473