1/* Operations with long integers.
2   Copyright (C) 2006 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 2, 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 COPYING.  If not, write to the Free
18Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
1902110-1301, USA.  */
20
21#include "config.h"
22#include "system.h"
23#include "coretypes.h"
24#include "tm.h"
25#include "tree.h"
26
27/* Returns mask for PREC bits.  */
28
29static inline double_int
30double_int_mask (unsigned prec)
31{
32  unsigned HOST_WIDE_INT m;
33  double_int mask;
34
35  if (prec > HOST_BITS_PER_WIDE_INT)
36    {
37      prec -= HOST_BITS_PER_WIDE_INT;
38      m = ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1;
39      mask.high = (HOST_WIDE_INT) m;
40      mask.low = ALL_ONES;
41    }
42  else
43    {
44      mask.high = 0;
45      mask.low = ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1;
46    }
47
48  return mask;
49}
50
51/* Clears the bits of CST over the precision PREC.  If UNS is false, the bits
52   outside of the precision are set to the sign bit (i.e., the PREC-th one),
53   otherwise they are set to zero.
54
55   This corresponds to returning the value represented by PREC lowermost bits
56   of CST, with the given signedness.  */
57
58double_int
59double_int_ext (double_int cst, unsigned prec, bool uns)
60{
61  if (uns)
62    return double_int_zext (cst, prec);
63  else
64    return double_int_sext (cst, prec);
65}
66
67/* The same as double_int_ext with UNS = true.  */
68
69double_int
70double_int_zext (double_int cst, unsigned prec)
71{
72  double_int mask = double_int_mask (prec);
73  double_int r;
74
75  r.low = cst.low & mask.low;
76  r.high = cst.high & mask.high;
77
78  return r;
79}
80
81/* The same as double_int_ext with UNS = false.  */
82
83double_int
84double_int_sext (double_int cst, unsigned prec)
85{
86  double_int mask = double_int_mask (prec);
87  double_int r;
88  unsigned HOST_WIDE_INT snum;
89
90  if (prec <= HOST_BITS_PER_WIDE_INT)
91    snum = cst.low;
92  else
93    {
94      prec -= HOST_BITS_PER_WIDE_INT;
95      snum = (unsigned HOST_WIDE_INT) cst.high;
96    }
97  if (((snum >> (prec - 1)) & 1) == 1)
98    {
99      r.low = cst.low | ~mask.low;
100      r.high = cst.high | ~mask.high;
101    }
102  else
103    {
104      r.low = cst.low & mask.low;
105      r.high = cst.high & mask.high;
106    }
107
108  return r;
109}
110
111/* Constructs long integer from tree CST.  The extra bits over the precision of
112   the number are filled with sign bit if CST is signed, and with zeros if it
113   is unsigned.  */
114
115double_int
116tree_to_double_int (tree cst)
117{
118  /* We do not need to call double_int_restrict here to ensure the semantics as
119     described, as this is the default one for trees.  */
120  return TREE_INT_CST (cst);
121}
122
123/* Returns true if CST fits in unsigned HOST_WIDE_INT.  */
124
125bool
126double_int_fits_in_uhwi_p (double_int cst)
127{
128  return cst.high == 0;
129}
130
131/* Returns true if CST fits in signed HOST_WIDE_INT.  */
132
133bool
134double_int_fits_in_shwi_p (double_int cst)
135{
136  if (cst.high == 0)
137    return (HOST_WIDE_INT) cst.low >= 0;
138  else if (cst.high == -1)
139    return (HOST_WIDE_INT) cst.low < 0;
140  else
141    return false;
142}
143
144/* Returns true if CST fits in HOST_WIDE_INT if UNS is false, or in
145   unsigned HOST_WIDE_INT if UNS is true.  */
146
147bool
148double_int_fits_in_hwi_p (double_int cst, bool uns)
149{
150  if (uns)
151    return double_int_fits_in_uhwi_p (cst);
152  else
153    return double_int_fits_in_shwi_p (cst);
154}
155
156/* Returns value of CST as a signed number.  CST must satisfy
157   double_int_fits_in_shwi_p.  */
158
159HOST_WIDE_INT
160double_int_to_shwi (double_int cst)
161{
162  return (HOST_WIDE_INT) cst.low;
163}
164
165/* Returns value of CST as an unsigned number.  CST must satisfy
166   double_int_fits_in_uhwi_p.  */
167
168unsigned HOST_WIDE_INT
169double_int_to_uhwi (double_int cst)
170{
171  return cst.low;
172}
173
174/* Returns A * B.  */
175
176double_int
177double_int_mul (double_int a, double_int b)
178{
179  double_int ret;
180  mul_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
181  return ret;
182}
183
184/* Returns A + B.  */
185
186double_int
187double_int_add (double_int a, double_int b)
188{
189  double_int ret;
190  add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
191  return ret;
192}
193
194/* Returns -A.  */
195
196double_int
197double_int_neg (double_int a)
198{
199  double_int ret;
200  neg_double (a.low, a.high, &ret.low, &ret.high);
201  return ret;
202}
203
204/* Returns A / B (computed as unsigned depending on UNS, and rounded as
205   specified by CODE).  CODE is enum tree_code in fact, but double_int.h
206   must be included before tree.h.  The remainder after the division is
207   stored to MOD.  */
208
209double_int
210double_int_divmod (double_int a, double_int b, bool uns, unsigned code,
211		   double_int *mod)
212{
213  double_int ret;
214
215  div_and_round_double (code, uns, a.low, a.high, b.low, b.high,
216			&ret.low, &ret.high, &mod->low, &mod->high);
217  return ret;
218}
219
220/* The same as double_int_divmod with UNS = false.  */
221
222double_int
223double_int_sdivmod (double_int a, double_int b, unsigned code, double_int *mod)
224{
225  return double_int_divmod (a, b, false, code, mod);
226}
227
228/* The same as double_int_divmod with UNS = true.  */
229
230double_int
231double_int_udivmod (double_int a, double_int b, unsigned code, double_int *mod)
232{
233  return double_int_divmod (a, b, true, code, mod);
234}
235
236/* Returns A / B (computed as unsigned depending on UNS, and rounded as
237   specified by CODE).  CODE is enum tree_code in fact, but double_int.h
238   must be included before tree.h.  */
239
240double_int
241double_int_div (double_int a, double_int b, bool uns, unsigned code)
242{
243  double_int mod;
244
245  return double_int_divmod (a, b, uns, code, &mod);
246}
247
248/* The same as double_int_div with UNS = false.  */
249
250double_int
251double_int_sdiv (double_int a, double_int b, unsigned code)
252{
253  return double_int_div (a, b, false, code);
254}
255
256/* The same as double_int_div with UNS = true.  */
257
258double_int
259double_int_udiv (double_int a, double_int b, unsigned code)
260{
261  return double_int_div (a, b, true, code);
262}
263
264/* Returns A % B (computed as unsigned depending on UNS, and rounded as
265   specified by CODE).  CODE is enum tree_code in fact, but double_int.h
266   must be included before tree.h.  */
267
268double_int
269double_int_mod (double_int a, double_int b, bool uns, unsigned code)
270{
271  double_int mod;
272
273  double_int_divmod (a, b, uns, code, &mod);
274  return mod;
275}
276
277/* The same as double_int_mod with UNS = false.  */
278
279double_int
280double_int_smod (double_int a, double_int b, unsigned code)
281{
282  return double_int_mod (a, b, false, code);
283}
284
285/* The same as double_int_mod with UNS = true.  */
286
287double_int
288double_int_umod (double_int a, double_int b, unsigned code)
289{
290  return double_int_mod (a, b, true, code);
291}
292
293/* Constructs tree in type TYPE from with value given by CST.  */
294
295tree
296double_int_to_tree (tree type, double_int cst)
297{
298  cst = double_int_ext (cst, TYPE_PRECISION (type), TYPE_UNSIGNED (type));
299
300  return build_int_cst_wide (type, cst.low, cst.high);
301}
302
303/* Returns true if CST is negative.  Of course, CST is considered to
304   be signed.  */
305
306bool
307double_int_negative_p (double_int cst)
308{
309  return cst.high < 0;
310}
311
312/* Returns -1 if A < B, 0 if A == B and 1 if A > B.  Signedness of the
313   comparison is given by UNS.  */
314
315int
316double_int_cmp (double_int a, double_int b, bool uns)
317{
318  if (uns)
319    return double_int_ucmp (a, b);
320  else
321    return double_int_scmp (a, b);
322}
323
324/* Compares two unsigned values A and B.  Returns -1 if A < B, 0 if A == B,
325   and 1 if A > B.  */
326
327int
328double_int_ucmp (double_int a, double_int b)
329{
330  if ((unsigned HOST_WIDE_INT) a.high < (unsigned HOST_WIDE_INT) b.high)
331    return -1;
332  if ((unsigned HOST_WIDE_INT) a.high > (unsigned HOST_WIDE_INT) b.high)
333    return 1;
334  if (a.low < b.low)
335    return -1;
336  if (a.low > b.low)
337    return 1;
338
339  return 0;
340}
341
342/* Compares two signed values A and B.  Returns -1 if A < B, 0 if A == B,
343   and 1 if A > B.  */
344
345int
346double_int_scmp (double_int a, double_int b)
347{
348  if (a.high < b.high)
349    return -1;
350  if (a.high > b.high)
351    return 1;
352  if ((HOST_WIDE_INT) a.low < (HOST_WIDE_INT) b.low)
353    return -1;
354  if ((HOST_WIDE_INT) a.low > (HOST_WIDE_INT) b.low)
355    return 1;
356
357  return 0;
358}
359
360/* Splits last digit of *CST (taken as unsigned) in BASE and returns it.  */
361
362static unsigned
363double_int_split_digit (double_int *cst, unsigned base)
364{
365  unsigned HOST_WIDE_INT resl, reml;
366  HOST_WIDE_INT resh, remh;
367
368  div_and_round_double (FLOOR_DIV_EXPR, true, cst->low, cst->high, base, 0,
369			&resl, &resh, &reml, &remh);
370  cst->high = resh;
371  cst->low = resl;
372
373  return reml;
374}
375
376/* Dumps CST to FILE.  If UNS is true, CST is considered to be unsigned,
377   otherwise it is signed.  */
378
379void
380dump_double_int (FILE *file, double_int cst, bool uns)
381{
382  unsigned digits[100], n;
383  int i;
384
385  if (double_int_zero_p (cst))
386    {
387      fprintf (file, "0");
388      return;
389    }
390
391  if (!uns && double_int_negative_p (cst))
392    {
393      fprintf (file, "-");
394      cst = double_int_neg (cst);
395    }
396
397  for (n = 0; !double_int_zero_p (cst); n++)
398    digits[n] = double_int_split_digit (&cst, 10);
399  for (i = n - 1; i >= 0; i--)
400    fprintf (file, "%u", digits[i]);
401}
402