1 /* Operations with long integers.
2 Copyright (C) 2006, 2007, 2009, 2010 Free Software Foundation, Inc.
4 This file is part of GCC.
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
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
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/>. */
22 #include "coretypes.h"
26 /* Returns mask for PREC bits. */
29 double_int_mask (unsigned prec)
31 unsigned HOST_WIDE_INT m;
34 if (prec > HOST_BITS_PER_WIDE_INT)
36 prec -= HOST_BITS_PER_WIDE_INT;
37 m = ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1;
38 mask.high = (HOST_WIDE_INT) m;
44 mask.low = ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1;
50 /* Clears the bits of CST over the precision PREC. If UNS is false, the bits
51 outside of the precision are set to the sign bit (i.e., the PREC-th one),
52 otherwise they are set to zero.
54 This corresponds to returning the value represented by PREC lowermost bits
55 of CST, with the given signedness. */
58 double_int_ext (double_int cst, unsigned prec, bool uns)
61 return double_int_zext (cst, prec);
63 return double_int_sext (cst, prec);
66 /* The same as double_int_ext with UNS = true. */
69 double_int_zext (double_int cst, unsigned prec)
71 double_int mask = double_int_mask (prec);
74 r.low = cst.low & mask.low;
75 r.high = cst.high & mask.high;
80 /* The same as double_int_ext with UNS = false. */
83 double_int_sext (double_int cst, unsigned prec)
85 double_int mask = double_int_mask (prec);
87 unsigned HOST_WIDE_INT snum;
89 if (prec <= HOST_BITS_PER_WIDE_INT)
93 prec -= HOST_BITS_PER_WIDE_INT;
94 snum = (unsigned HOST_WIDE_INT) cst.high;
96 if (((snum >> (prec - 1)) & 1) == 1)
98 r.low = cst.low | ~mask.low;
99 r.high = cst.high | ~mask.high;
103 r.low = cst.low & mask.low;
104 r.high = cst.high & mask.high;
110 /* Constructs long integer from tree CST. The extra bits over the precision of
111 the number are filled with sign bit if CST is signed, and with zeros if it
115 tree_to_double_int (const_tree cst)
117 /* We do not need to call double_int_restrict here to ensure the semantics as
118 described, as this is the default one for trees. */
119 return TREE_INT_CST (cst);
122 /* Returns true if CST fits in unsigned HOST_WIDE_INT. */
125 double_int_fits_in_uhwi_p (double_int cst)
127 return cst.high == 0;
130 /* Returns true if CST fits in signed HOST_WIDE_INT. */
133 double_int_fits_in_shwi_p (double_int cst)
136 return (HOST_WIDE_INT) cst.low >= 0;
137 else if (cst.high == -1)
138 return (HOST_WIDE_INT) cst.low < 0;
143 /* Returns true if CST fits in HOST_WIDE_INT if UNS is false, or in
144 unsigned HOST_WIDE_INT if UNS is true. */
147 double_int_fits_in_hwi_p (double_int cst, bool uns)
150 return double_int_fits_in_uhwi_p (cst);
152 return double_int_fits_in_shwi_p (cst);
155 /* Returns value of CST as a signed number. CST must satisfy
156 double_int_fits_in_shwi_p. */
159 double_int_to_shwi (double_int cst)
161 return (HOST_WIDE_INT) cst.low;
164 /* Returns value of CST as an unsigned number. CST must satisfy
165 double_int_fits_in_uhwi_p. */
167 unsigned HOST_WIDE_INT
168 double_int_to_uhwi (double_int cst)
176 double_int_mul (double_int a, double_int b)
179 mul_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
186 double_int_add (double_int a, double_int b)
189 add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
196 double_int_neg (double_int a)
199 neg_double (a.low, a.high, &ret.low, &ret.high);
203 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
204 specified by CODE). CODE is enum tree_code in fact, but double_int.h
205 must be included before tree.h. The remainder after the division is
209 double_int_divmod (double_int a, double_int b, bool uns, unsigned code,
214 div_and_round_double ((enum tree_code) code, uns, a.low, a.high,
215 b.low, b.high, &ret.low, &ret.high,
216 &mod->low, &mod->high);
220 /* The same as double_int_divmod with UNS = false. */
223 double_int_sdivmod (double_int a, double_int b, unsigned code, double_int *mod)
225 return double_int_divmod (a, b, false, code, mod);
228 /* The same as double_int_divmod with UNS = true. */
231 double_int_udivmod (double_int a, double_int b, unsigned code, double_int *mod)
233 return double_int_divmod (a, b, true, code, mod);
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. */
241 double_int_div (double_int a, double_int b, bool uns, unsigned code)
245 return double_int_divmod (a, b, uns, code, &mod);
248 /* The same as double_int_div with UNS = false. */
251 double_int_sdiv (double_int a, double_int b, unsigned code)
253 return double_int_div (a, b, false, code);
256 /* The same as double_int_div with UNS = true. */
259 double_int_udiv (double_int a, double_int b, unsigned code)
261 return double_int_div (a, b, true, code);
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. */
269 double_int_mod (double_int a, double_int b, bool uns, unsigned code)
273 double_int_divmod (a, b, uns, code, &mod);
277 /* The same as double_int_mod with UNS = false. */
280 double_int_smod (double_int a, double_int b, unsigned code)
282 return double_int_mod (a, b, false, code);
285 /* The same as double_int_mod with UNS = true. */
288 double_int_umod (double_int a, double_int b, unsigned code)
290 return double_int_mod (a, b, true, code);
293 /* Shift A left by COUNT places keeping only PREC bits of result. Shift
294 right if COUNT is negative. ARITH true specifies arithmetic shifting;
295 otherwise use logical shift. */
298 double_int_lshift (double_int a, HOST_WIDE_INT count, unsigned int prec, bool arith)
301 lshift_double (a.low, a.high, count, prec, &ret.low, &ret.high, arith);
305 /* Shift A rigth by COUNT places keeping only PREC bits of result. Shift
306 left if COUNT is negative. ARITH true specifies arithmetic shifting;
307 otherwise use logical shift. */
310 double_int_rshift (double_int a, HOST_WIDE_INT count, unsigned int prec, bool arith)
313 rshift_double (a.low, a.high, count, prec, &ret.low, &ret.high, arith);
317 /* Constructs tree in type TYPE from with value given by CST. Signedness of CST
318 is assumed to be the same as the signedness of TYPE. */
321 double_int_to_tree (tree type, double_int cst)
323 cst = double_int_ext (cst, TYPE_PRECISION (type), TYPE_UNSIGNED (type));
325 return build_int_cst_wide (type, cst.low, cst.high);
328 /* Returns true if CST fits into range of TYPE. Signedness of CST is assumed
329 to be the same as the signedness of TYPE. */
332 double_int_fits_to_tree_p (const_tree type, double_int cst)
334 double_int ext = double_int_ext (cst,
335 TYPE_PRECISION (type),
336 TYPE_UNSIGNED (type));
338 return double_int_equal_p (cst, ext);
341 /* Returns -1 if A < B, 0 if A == B and 1 if A > B. Signedness of the
342 comparison is given by UNS. */
345 double_int_cmp (double_int a, double_int b, bool uns)
348 return double_int_ucmp (a, b);
350 return double_int_scmp (a, b);
353 /* Compares two unsigned values A and B. Returns -1 if A < B, 0 if A == B,
357 double_int_ucmp (double_int a, double_int b)
359 if ((unsigned HOST_WIDE_INT) a.high < (unsigned HOST_WIDE_INT) b.high)
361 if ((unsigned HOST_WIDE_INT) a.high > (unsigned HOST_WIDE_INT) b.high)
371 /* Compares two signed values A and B. Returns -1 if A < B, 0 if A == B,
375 double_int_scmp (double_int a, double_int b)
389 /* Splits last digit of *CST (taken as unsigned) in BASE and returns it. */
392 double_int_split_digit (double_int *cst, unsigned base)
394 unsigned HOST_WIDE_INT resl, reml;
395 HOST_WIDE_INT resh, remh;
397 div_and_round_double (FLOOR_DIV_EXPR, true, cst->low, cst->high, base, 0,
398 &resl, &resh, &reml, &remh);
405 /* Dumps CST to FILE. If UNS is true, CST is considered to be unsigned,
406 otherwise it is signed. */
409 dump_double_int (FILE *file, double_int cst, bool uns)
411 unsigned digits[100], n;
414 if (double_int_zero_p (cst))
420 if (!uns && double_int_negative_p (cst))
423 cst = double_int_neg (cst);
426 for (n = 0; !double_int_zero_p (cst); n++)
427 digits[n] = double_int_split_digit (&cst, 10);
428 for (i = n - 1; i >= 0; i--)
429 fprintf (file, "%u", digits[i]);
433 /* Sets RESULT to VAL, taken unsigned if UNS is true and as signed
437 mpz_set_double_int (mpz_t result, double_int val, bool uns)
440 unsigned HOST_WIDE_INT vp[2];
442 if (!uns && double_int_negative_p (val))
445 val = double_int_neg (val);
449 vp[1] = (unsigned HOST_WIDE_INT) val.high;
450 mpz_import (result, 2, -1, sizeof (HOST_WIDE_INT), 0, 0, vp);
453 mpz_neg (result, result);
456 /* Returns VAL converted to TYPE. If WRAP is true, then out-of-range
457 values of VAL will be wrapped; otherwise, they will be set to the
458 appropriate minimum or maximum TYPE bound. */
461 mpz_get_double_int (const_tree type, mpz_t val, bool wrap)
463 unsigned HOST_WIDE_INT *vp;
473 get_type_static_bounds (type, min, max);
475 if (mpz_cmp (val, min) < 0)
477 else if (mpz_cmp (val, max) > 0)
484 /* Determine the number of unsigned HOST_WIDE_INT that are required
485 for representing the value. The code to calculate count is
486 extracted from the GMP manual, section "Integer Import and Export":
487 http://gmplib.org/manual/Integer-Import-and-Export.html */
488 numb = 8*sizeof(HOST_WIDE_INT);
489 count = (mpz_sizeinbase (val, 2) + numb-1) / numb;
492 vp = (unsigned HOST_WIDE_INT *) alloca (count * sizeof(HOST_WIDE_INT));
496 mpz_export (vp, &count, -1, sizeof (HOST_WIDE_INT), 0, 0, val);
498 gcc_assert (wrap || count <= 2);
501 res.high = (HOST_WIDE_INT) vp[1];
503 res = double_int_ext (res, TYPE_PRECISION (type), TYPE_UNSIGNED (type));
504 if (mpz_sgn (val) < 0)
505 res = double_int_neg (res);