2012-09-04 Janus Weil <janus@gcc.gnu.org>
[official-gcc.git] / gcc / double-int.c
blob3a22d15f08cd72390c7cb72ee80665e709f86d6b
1 /* Operations with long integers.
2 Copyright (C) 2006, 2007, 2009, 2010, 2012 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
9 later version.
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.
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/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h" /* For SHIFT_COUNT_TRUNCATED. */
24 #include "tree.h"
26 /* We know that A1 + B1 = SUM1, using 2's complement arithmetic and ignoring
27 overflow. Suppose A, B and SUM have the same respective signs as A1, B1,
28 and SUM1. Then this yields nonzero if overflow occurred during the
29 addition.
31 Overflow occurs if A and B have the same sign, but A and SUM differ in
32 sign. Use `^' to test whether signs differ, and `< 0' to isolate the
33 sign. */
34 #define OVERFLOW_SUM_SIGN(a, b, sum) ((~((a) ^ (b)) & ((a) ^ (sum))) < 0)
36 /* To do constant folding on INTEGER_CST nodes requires two-word arithmetic.
37 We do that by representing the two-word integer in 4 words, with only
38 HOST_BITS_PER_WIDE_INT / 2 bits stored in each word, as a positive
39 number. The value of the word is LOWPART + HIGHPART * BASE. */
41 #define LOWPART(x) \
42 ((x) & (((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)) - 1))
43 #define HIGHPART(x) \
44 ((unsigned HOST_WIDE_INT) (x) >> HOST_BITS_PER_WIDE_INT / 2)
45 #define BASE ((unsigned HOST_WIDE_INT) 1 << HOST_BITS_PER_WIDE_INT / 2)
47 /* Unpack a two-word integer into 4 words.
48 LOW and HI are the integer, as two `HOST_WIDE_INT' pieces.
49 WORDS points to the array of HOST_WIDE_INTs. */
51 static void
52 encode (HOST_WIDE_INT *words, unsigned HOST_WIDE_INT low, HOST_WIDE_INT hi)
54 words[0] = LOWPART (low);
55 words[1] = HIGHPART (low);
56 words[2] = LOWPART (hi);
57 words[3] = HIGHPART (hi);
60 /* Pack an array of 4 words into a two-word integer.
61 WORDS points to the array of words.
62 The integer is stored into *LOW and *HI as two `HOST_WIDE_INT' pieces. */
64 static void
65 decode (HOST_WIDE_INT *words, unsigned HOST_WIDE_INT *low,
66 HOST_WIDE_INT *hi)
68 *low = words[0] + words[1] * BASE;
69 *hi = words[2] + words[3] * BASE;
72 /* Add two doubleword integers with doubleword result.
73 Return nonzero if the operation overflows according to UNSIGNED_P.
74 Each argument is given as two `HOST_WIDE_INT' pieces.
75 One argument is L1 and H1; the other, L2 and H2.
76 The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV. */
78 int
79 add_double_with_sign (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
80 unsigned HOST_WIDE_INT l2, HOST_WIDE_INT h2,
81 unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv,
82 bool unsigned_p)
84 unsigned HOST_WIDE_INT l;
85 HOST_WIDE_INT h;
87 l = l1 + l2;
88 h = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) h1
89 + (unsigned HOST_WIDE_INT) h2
90 + (l < l1));
92 *lv = l;
93 *hv = h;
95 if (unsigned_p)
96 return ((unsigned HOST_WIDE_INT) h < (unsigned HOST_WIDE_INT) h1
97 || (h == h1
98 && l < l1));
99 else
100 return OVERFLOW_SUM_SIGN (h1, h2, h);
103 /* Negate a doubleword integer with doubleword result.
104 Return nonzero if the operation overflows, assuming it's signed.
105 The argument is given as two `HOST_WIDE_INT' pieces in L1 and H1.
106 The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV. */
109 neg_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
110 unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv)
112 if (l1 == 0)
114 *lv = 0;
115 *hv = - h1;
116 return (*hv & h1) < 0;
118 else
120 *lv = -l1;
121 *hv = ~h1;
122 return 0;
126 /* Multiply two doubleword integers with doubleword result.
127 Return nonzero if the operation overflows according to UNSIGNED_P.
128 Each argument is given as two `HOST_WIDE_INT' pieces.
129 One argument is L1 and H1; the other, L2 and H2.
130 The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV. */
133 mul_double_with_sign (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
134 unsigned HOST_WIDE_INT l2, HOST_WIDE_INT h2,
135 unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv,
136 bool unsigned_p)
138 unsigned HOST_WIDE_INT toplow;
139 HOST_WIDE_INT tophigh;
141 return mul_double_wide_with_sign (l1, h1, l2, h2,
142 lv, hv, &toplow, &tophigh,
143 unsigned_p);
147 mul_double_wide_with_sign (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
148 unsigned HOST_WIDE_INT l2, HOST_WIDE_INT h2,
149 unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv,
150 unsigned HOST_WIDE_INT *lw, HOST_WIDE_INT *hw,
151 bool unsigned_p)
153 HOST_WIDE_INT arg1[4];
154 HOST_WIDE_INT arg2[4];
155 HOST_WIDE_INT prod[4 * 2];
156 unsigned HOST_WIDE_INT carry;
157 int i, j, k;
158 unsigned HOST_WIDE_INT neglow;
159 HOST_WIDE_INT neghigh;
161 encode (arg1, l1, h1);
162 encode (arg2, l2, h2);
164 memset (prod, 0, sizeof prod);
166 for (i = 0; i < 4; i++)
168 carry = 0;
169 for (j = 0; j < 4; j++)
171 k = i + j;
172 /* This product is <= 0xFFFE0001, the sum <= 0xFFFF0000. */
173 carry += (unsigned HOST_WIDE_INT) arg1[i] * arg2[j];
174 /* Since prod[p] < 0xFFFF, this sum <= 0xFFFFFFFF. */
175 carry += prod[k];
176 prod[k] = LOWPART (carry);
177 carry = HIGHPART (carry);
179 prod[i + 4] = carry;
182 decode (prod, lv, hv);
183 decode (prod + 4, lw, hw);
185 /* Unsigned overflow is immediate. */
186 if (unsigned_p)
187 return (*lw | *hw) != 0;
189 /* Check for signed overflow by calculating the signed representation of the
190 top half of the result; it should agree with the low half's sign bit. */
191 if (h1 < 0)
193 neg_double (l2, h2, &neglow, &neghigh);
194 add_double (neglow, neghigh, *lw, *hw, lw, hw);
196 if (h2 < 0)
198 neg_double (l1, h1, &neglow, &neghigh);
199 add_double (neglow, neghigh, *lw, *hw, lw, hw);
201 return (*hv < 0 ? ~(*lw & *hw) : *lw | *hw) != 0;
204 /* Shift the doubleword integer in L1, H1 right by COUNT places
205 keeping only PREC bits of result. ARITH nonzero specifies
206 arithmetic shifting; otherwise use logical shift.
207 Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV. */
209 static void
210 rshift_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
211 unsigned HOST_WIDE_INT count, unsigned int prec,
212 unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv,
213 bool arith)
215 unsigned HOST_WIDE_INT signmask;
217 signmask = (arith
218 ? -((unsigned HOST_WIDE_INT) h1 >> (HOST_BITS_PER_WIDE_INT - 1))
219 : 0);
221 if (SHIFT_COUNT_TRUNCATED)
222 count %= prec;
224 if (count >= HOST_BITS_PER_DOUBLE_INT)
226 /* Shifting by the host word size is undefined according to the
227 ANSI standard, so we must handle this as a special case. */
228 *hv = 0;
229 *lv = 0;
231 else if (count >= HOST_BITS_PER_WIDE_INT)
233 *hv = 0;
234 *lv = (unsigned HOST_WIDE_INT) h1 >> (count - HOST_BITS_PER_WIDE_INT);
236 else
238 *hv = (unsigned HOST_WIDE_INT) h1 >> count;
239 *lv = ((l1 >> count)
240 | ((unsigned HOST_WIDE_INT) h1
241 << (HOST_BITS_PER_WIDE_INT - count - 1) << 1));
244 /* Zero / sign extend all bits that are beyond the precision. */
246 if (count >= prec)
248 *hv = signmask;
249 *lv = signmask;
251 else if ((prec - count) >= HOST_BITS_PER_DOUBLE_INT)
253 else if ((prec - count) >= HOST_BITS_PER_WIDE_INT)
255 *hv &= ~((HOST_WIDE_INT) (-1) << (prec - count - HOST_BITS_PER_WIDE_INT));
256 *hv |= signmask << (prec - count - HOST_BITS_PER_WIDE_INT);
258 else
260 *hv = signmask;
261 *lv &= ~((unsigned HOST_WIDE_INT) (-1) << (prec - count));
262 *lv |= signmask << (prec - count);
266 /* Shift the doubleword integer in L1, H1 left by COUNT places
267 keeping only PREC bits of result.
268 Shift right if COUNT is negative.
269 ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
270 Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV. */
272 void
273 lshift_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
274 HOST_WIDE_INT count, unsigned int prec,
275 unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv, bool arith)
277 unsigned HOST_WIDE_INT signmask;
279 if (count < 0)
281 rshift_double (l1, h1, absu_hwi (count), prec, lv, hv, arith);
282 return;
285 if (SHIFT_COUNT_TRUNCATED)
286 count %= prec;
288 if (count >= HOST_BITS_PER_DOUBLE_INT)
290 /* Shifting by the host word size is undefined according to the
291 ANSI standard, so we must handle this as a special case. */
292 *hv = 0;
293 *lv = 0;
295 else if (count >= HOST_BITS_PER_WIDE_INT)
297 *hv = l1 << (count - HOST_BITS_PER_WIDE_INT);
298 *lv = 0;
300 else
302 *hv = (((unsigned HOST_WIDE_INT) h1 << count)
303 | (l1 >> (HOST_BITS_PER_WIDE_INT - count - 1) >> 1));
304 *lv = l1 << count;
307 /* Sign extend all bits that are beyond the precision. */
309 signmask = -((prec > HOST_BITS_PER_WIDE_INT
310 ? ((unsigned HOST_WIDE_INT) *hv
311 >> (prec - HOST_BITS_PER_WIDE_INT - 1))
312 : (*lv >> (prec - 1))) & 1);
314 if (prec >= HOST_BITS_PER_DOUBLE_INT)
316 else if (prec >= HOST_BITS_PER_WIDE_INT)
318 *hv &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
319 *hv |= signmask << (prec - HOST_BITS_PER_WIDE_INT);
321 else
323 *hv = signmask;
324 *lv &= ~((unsigned HOST_WIDE_INT) (-1) << prec);
325 *lv |= signmask << prec;
329 /* Divide doubleword integer LNUM, HNUM by doubleword integer LDEN, HDEN
330 for a quotient (stored in *LQUO, *HQUO) and remainder (in *LREM, *HREM).
331 CODE is a tree code for a kind of division, one of
332 TRUNC_DIV_EXPR, FLOOR_DIV_EXPR, CEIL_DIV_EXPR, ROUND_DIV_EXPR
333 or EXACT_DIV_EXPR
334 It controls how the quotient is rounded to an integer.
335 Return nonzero if the operation overflows.
336 UNS nonzero says do unsigned division. */
339 div_and_round_double (unsigned code, int uns,
340 /* num == numerator == dividend */
341 unsigned HOST_WIDE_INT lnum_orig,
342 HOST_WIDE_INT hnum_orig,
343 /* den == denominator == divisor */
344 unsigned HOST_WIDE_INT lden_orig,
345 HOST_WIDE_INT hden_orig,
346 unsigned HOST_WIDE_INT *lquo,
347 HOST_WIDE_INT *hquo, unsigned HOST_WIDE_INT *lrem,
348 HOST_WIDE_INT *hrem)
350 int quo_neg = 0;
351 HOST_WIDE_INT num[4 + 1]; /* extra element for scaling. */
352 HOST_WIDE_INT den[4], quo[4];
353 int i, j;
354 unsigned HOST_WIDE_INT work;
355 unsigned HOST_WIDE_INT carry = 0;
356 unsigned HOST_WIDE_INT lnum = lnum_orig;
357 HOST_WIDE_INT hnum = hnum_orig;
358 unsigned HOST_WIDE_INT lden = lden_orig;
359 HOST_WIDE_INT hden = hden_orig;
360 int overflow = 0;
362 if (hden == 0 && lden == 0)
363 overflow = 1, lden = 1;
365 /* Calculate quotient sign and convert operands to unsigned. */
366 if (!uns)
368 if (hnum < 0)
370 quo_neg = ~ quo_neg;
371 /* (minimum integer) / (-1) is the only overflow case. */
372 if (neg_double (lnum, hnum, &lnum, &hnum)
373 && ((HOST_WIDE_INT) lden & hden) == -1)
374 overflow = 1;
376 if (hden < 0)
378 quo_neg = ~ quo_neg;
379 neg_double (lden, hden, &lden, &hden);
383 if (hnum == 0 && hden == 0)
384 { /* single precision */
385 *hquo = *hrem = 0;
386 /* This unsigned division rounds toward zero. */
387 *lquo = lnum / lden;
388 goto finish_up;
391 if (hnum == 0)
392 { /* trivial case: dividend < divisor */
393 /* hden != 0 already checked. */
394 *hquo = *lquo = 0;
395 *hrem = hnum;
396 *lrem = lnum;
397 goto finish_up;
400 memset (quo, 0, sizeof quo);
402 memset (num, 0, sizeof num); /* to zero 9th element */
403 memset (den, 0, sizeof den);
405 encode (num, lnum, hnum);
406 encode (den, lden, hden);
408 /* Special code for when the divisor < BASE. */
409 if (hden == 0 && lden < (unsigned HOST_WIDE_INT) BASE)
411 /* hnum != 0 already checked. */
412 for (i = 4 - 1; i >= 0; i--)
414 work = num[i] + carry * BASE;
415 quo[i] = work / lden;
416 carry = work % lden;
419 else
421 /* Full double precision division,
422 with thanks to Don Knuth's "Seminumerical Algorithms". */
423 int num_hi_sig, den_hi_sig;
424 unsigned HOST_WIDE_INT quo_est, scale;
426 /* Find the highest nonzero divisor digit. */
427 for (i = 4 - 1;; i--)
428 if (den[i] != 0)
430 den_hi_sig = i;
431 break;
434 /* Insure that the first digit of the divisor is at least BASE/2.
435 This is required by the quotient digit estimation algorithm. */
437 scale = BASE / (den[den_hi_sig] + 1);
438 if (scale > 1)
439 { /* scale divisor and dividend */
440 carry = 0;
441 for (i = 0; i <= 4 - 1; i++)
443 work = (num[i] * scale) + carry;
444 num[i] = LOWPART (work);
445 carry = HIGHPART (work);
448 num[4] = carry;
449 carry = 0;
450 for (i = 0; i <= 4 - 1; i++)
452 work = (den[i] * scale) + carry;
453 den[i] = LOWPART (work);
454 carry = HIGHPART (work);
455 if (den[i] != 0) den_hi_sig = i;
459 num_hi_sig = 4;
461 /* Main loop */
462 for (i = num_hi_sig - den_hi_sig - 1; i >= 0; i--)
464 /* Guess the next quotient digit, quo_est, by dividing the first
465 two remaining dividend digits by the high order quotient digit.
466 quo_est is never low and is at most 2 high. */
467 unsigned HOST_WIDE_INT tmp;
469 num_hi_sig = i + den_hi_sig + 1;
470 work = num[num_hi_sig] * BASE + num[num_hi_sig - 1];
471 if (num[num_hi_sig] != den[den_hi_sig])
472 quo_est = work / den[den_hi_sig];
473 else
474 quo_est = BASE - 1;
476 /* Refine quo_est so it's usually correct, and at most one high. */
477 tmp = work - quo_est * den[den_hi_sig];
478 if (tmp < BASE
479 && (den[den_hi_sig - 1] * quo_est
480 > (tmp * BASE + num[num_hi_sig - 2])))
481 quo_est--;
483 /* Try QUO_EST as the quotient digit, by multiplying the
484 divisor by QUO_EST and subtracting from the remaining dividend.
485 Keep in mind that QUO_EST is the I - 1st digit. */
487 carry = 0;
488 for (j = 0; j <= den_hi_sig; j++)
490 work = quo_est * den[j] + carry;
491 carry = HIGHPART (work);
492 work = num[i + j] - LOWPART (work);
493 num[i + j] = LOWPART (work);
494 carry += HIGHPART (work) != 0;
497 /* If quo_est was high by one, then num[i] went negative and
498 we need to correct things. */
499 if (num[num_hi_sig] < (HOST_WIDE_INT) carry)
501 quo_est--;
502 carry = 0; /* add divisor back in */
503 for (j = 0; j <= den_hi_sig; j++)
505 work = num[i + j] + den[j] + carry;
506 carry = HIGHPART (work);
507 num[i + j] = LOWPART (work);
510 num [num_hi_sig] += carry;
513 /* Store the quotient digit. */
514 quo[i] = quo_est;
518 decode (quo, lquo, hquo);
520 finish_up:
521 /* If result is negative, make it so. */
522 if (quo_neg)
523 neg_double (*lquo, *hquo, lquo, hquo);
525 /* Compute trial remainder: rem = num - (quo * den) */
526 mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
527 neg_double (*lrem, *hrem, lrem, hrem);
528 add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
530 switch (code)
532 case TRUNC_DIV_EXPR:
533 case TRUNC_MOD_EXPR: /* round toward zero */
534 case EXACT_DIV_EXPR: /* for this one, it shouldn't matter */
535 return overflow;
537 case FLOOR_DIV_EXPR:
538 case FLOOR_MOD_EXPR: /* round toward negative infinity */
539 if (quo_neg && (*lrem != 0 || *hrem != 0)) /* ratio < 0 && rem != 0 */
541 /* quo = quo - 1; */
542 add_double (*lquo, *hquo, (HOST_WIDE_INT) -1, (HOST_WIDE_INT) -1,
543 lquo, hquo);
545 else
546 return overflow;
547 break;
549 case CEIL_DIV_EXPR:
550 case CEIL_MOD_EXPR: /* round toward positive infinity */
551 if (!quo_neg && (*lrem != 0 || *hrem != 0)) /* ratio > 0 && rem != 0 */
553 add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
554 lquo, hquo);
556 else
557 return overflow;
558 break;
560 case ROUND_DIV_EXPR:
561 case ROUND_MOD_EXPR: /* round to closest integer */
563 unsigned HOST_WIDE_INT labs_rem = *lrem;
564 HOST_WIDE_INT habs_rem = *hrem;
565 unsigned HOST_WIDE_INT labs_den = lden, ltwice;
566 HOST_WIDE_INT habs_den = hden, htwice;
568 /* Get absolute values. */
569 if (*hrem < 0)
570 neg_double (*lrem, *hrem, &labs_rem, &habs_rem);
571 if (hden < 0)
572 neg_double (lden, hden, &labs_den, &habs_den);
574 /* If (2 * abs (lrem) >= abs (lden)), adjust the quotient. */
575 mul_double ((HOST_WIDE_INT) 2, (HOST_WIDE_INT) 0,
576 labs_rem, habs_rem, &ltwice, &htwice);
578 if (((unsigned HOST_WIDE_INT) habs_den
579 < (unsigned HOST_WIDE_INT) htwice)
580 || (((unsigned HOST_WIDE_INT) habs_den
581 == (unsigned HOST_WIDE_INT) htwice)
582 && (labs_den <= ltwice)))
584 if (*hquo < 0)
585 /* quo = quo - 1; */
586 add_double (*lquo, *hquo,
587 (HOST_WIDE_INT) -1, (HOST_WIDE_INT) -1, lquo, hquo);
588 else
589 /* quo = quo + 1; */
590 add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
591 lquo, hquo);
593 else
594 return overflow;
596 break;
598 default:
599 gcc_unreachable ();
602 /* Compute true remainder: rem = num - (quo * den) */
603 mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
604 neg_double (*lrem, *hrem, lrem, hrem);
605 add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
606 return overflow;
610 /* Returns mask for PREC bits. */
612 double_int
613 double_int::mask (unsigned prec)
615 unsigned HOST_WIDE_INT m;
616 double_int mask;
618 if (prec > HOST_BITS_PER_WIDE_INT)
620 prec -= HOST_BITS_PER_WIDE_INT;
621 m = ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1;
622 mask.high = (HOST_WIDE_INT) m;
623 mask.low = ALL_ONES;
625 else
627 mask.high = 0;
628 mask.low = prec ? ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1 : 0;
631 return mask;
634 /* Returns a maximum value for signed or unsigned integer
635 of precision PREC. */
637 double_int
638 double_int::max_value (unsigned int prec, bool uns)
640 return double_int::mask (prec - (uns ? 0 : 1));
643 /* Returns a minimum value for signed or unsigned integer
644 of precision PREC. */
646 double_int
647 double_int::min_value (unsigned int prec, bool uns)
649 if (uns)
650 return double_int_zero;
651 return double_int_one.lshift (prec - 1, prec, false);
654 /* Clears the bits of CST over the precision PREC. If UNS is false, the bits
655 outside of the precision are set to the sign bit (i.e., the PREC-th one),
656 otherwise they are set to zero.
658 This corresponds to returning the value represented by PREC lowermost bits
659 of CST, with the given signedness. */
661 double_int
662 double_int::ext (unsigned prec, bool uns) const
664 if (uns)
665 return this->zext (prec);
666 else
667 return this->sext (prec);
670 /* The same as double_int::ext with UNS = true. */
672 double_int
673 double_int::zext (unsigned prec) const
675 const double_int &cst = *this;
676 double_int mask = double_int::mask (prec);
677 double_int r;
679 r.low = cst.low & mask.low;
680 r.high = cst.high & mask.high;
682 return r;
685 /* The same as double_int::ext with UNS = false. */
687 double_int
688 double_int::sext (unsigned prec) const
690 const double_int &cst = *this;
691 double_int mask = double_int::mask (prec);
692 double_int r;
693 unsigned HOST_WIDE_INT snum;
695 if (prec <= HOST_BITS_PER_WIDE_INT)
696 snum = cst.low;
697 else
699 prec -= HOST_BITS_PER_WIDE_INT;
700 snum = (unsigned HOST_WIDE_INT) cst.high;
702 if (((snum >> (prec - 1)) & 1) == 1)
704 r.low = cst.low | ~mask.low;
705 r.high = cst.high | ~mask.high;
707 else
709 r.low = cst.low & mask.low;
710 r.high = cst.high & mask.high;
713 return r;
716 /* Returns true if CST fits in signed HOST_WIDE_INT. */
718 bool
719 double_int::fits_shwi () const
721 const double_int &cst = *this;
722 if (cst.high == 0)
723 return (HOST_WIDE_INT) cst.low >= 0;
724 else if (cst.high == -1)
725 return (HOST_WIDE_INT) cst.low < 0;
726 else
727 return false;
730 /* Returns true if CST fits in HOST_WIDE_INT if UNS is false, or in
731 unsigned HOST_WIDE_INT if UNS is true. */
733 bool
734 double_int::fits_hwi (bool uns) const
736 if (uns)
737 return this->fits_uhwi ();
738 else
739 return this->fits_shwi ();
742 /* Returns A * B. */
744 double_int
745 double_int::operator * (double_int b) const
747 const double_int &a = *this;
748 double_int ret;
749 mul_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
750 return ret;
753 /* Returns A * B. If the operation overflows according to UNSIGNED_P,
754 *OVERFLOW is set to nonzero. */
756 double_int
757 double_int::mul_with_sign (double_int b, bool unsigned_p, int *overflow) const
759 const double_int &a = *this;
760 double_int ret;
761 *overflow = mul_double_with_sign (a.low, a.high, b.low, b.high,
762 &ret.low, &ret.high, unsigned_p);
763 return ret;
766 /* Returns A + B. */
768 double_int
769 double_int::operator + (double_int b) const
771 const double_int &a = *this;
772 double_int ret;
773 add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
774 return ret;
777 /* Returns A - B. */
779 double_int
780 double_int::operator - (double_int b) const
782 const double_int &a = *this;
783 double_int ret;
784 neg_double (b.low, b.high, &b.low, &b.high);
785 add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
786 return ret;
789 /* Returns -A. */
791 double_int
792 double_int::operator - () const
794 const double_int &a = *this;
795 double_int ret;
796 neg_double (a.low, a.high, &ret.low, &ret.high);
797 return ret;
800 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
801 specified by CODE). CODE is enum tree_code in fact, but double_int.h
802 must be included before tree.h. The remainder after the division is
803 stored to MOD. */
805 double_int
806 double_int::divmod (double_int b, bool uns, unsigned code,
807 double_int *mod) const
809 const double_int &a = *this;
810 double_int ret;
812 div_and_round_double (code, uns, a.low, a.high,
813 b.low, b.high, &ret.low, &ret.high,
814 &mod->low, &mod->high);
815 return ret;
818 /* The same as double_int::divmod with UNS = false. */
820 double_int
821 double_int::sdivmod (double_int b, unsigned code, double_int *mod) const
823 return this->divmod (b, false, code, mod);
826 /* The same as double_int::divmod with UNS = true. */
828 double_int
829 double_int::udivmod (double_int b, unsigned code, double_int *mod) const
831 return this->divmod (b, true, code, mod);
834 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
835 specified by CODE). CODE is enum tree_code in fact, but double_int.h
836 must be included before tree.h. */
838 double_int
839 double_int::div (double_int b, bool uns, unsigned code) const
841 double_int mod;
843 return this->divmod (b, uns, code, &mod);
846 /* The same as double_int::div with UNS = false. */
848 double_int
849 double_int::sdiv (double_int b, unsigned code) const
851 return this->div (b, false, code);
854 /* The same as double_int::div with UNS = true. */
856 double_int
857 double_int::udiv (double_int b, unsigned code) const
859 return this->div (b, true, code);
862 /* Returns A % B (computed as unsigned depending on UNS, and rounded as
863 specified by CODE). CODE is enum tree_code in fact, but double_int.h
864 must be included before tree.h. */
866 double_int
867 double_int::mod (double_int b, bool uns, unsigned code) const
869 double_int mod;
871 this->divmod (b, uns, code, &mod);
872 return mod;
875 /* The same as double_int::mod with UNS = false. */
877 double_int
878 double_int::smod (double_int b, unsigned code) const
880 return this->mod (b, false, code);
883 /* The same as double_int::mod with UNS = true. */
885 double_int
886 double_int::umod (double_int b, unsigned code) const
888 return this->mod (b, true, code);
891 /* Return TRUE iff PRODUCT is an integral multiple of FACTOR, and return
892 the multiple in *MULTIPLE. Otherwise return FALSE and leave *MULTIPLE
893 unchanged. */
895 bool
896 double_int::multiple_of (double_int factor,
897 bool unsigned_p, double_int *multiple) const
899 double_int remainder;
900 double_int quotient = this->divmod (factor, unsigned_p,
901 TRUNC_DIV_EXPR, &remainder);
902 if (remainder.is_zero ())
904 *multiple = quotient;
905 return true;
908 return false;
911 /* Set BITPOS bit in A. */
912 double_int
913 double_int::set_bit (unsigned bitpos) const
915 double_int a = *this;
916 if (bitpos < HOST_BITS_PER_WIDE_INT)
917 a.low |= (unsigned HOST_WIDE_INT) 1 << bitpos;
918 else
919 a.high |= (HOST_WIDE_INT) 1 << (bitpos - HOST_BITS_PER_WIDE_INT);
921 return a;
924 /* Count trailing zeros in A. */
926 double_int::trailing_zeros () const
928 const double_int &a = *this;
929 unsigned HOST_WIDE_INT w = a.low ? a.low : (unsigned HOST_WIDE_INT) a.high;
930 unsigned bits = a.low ? 0 : HOST_BITS_PER_WIDE_INT;
931 if (!w)
932 return HOST_BITS_PER_DOUBLE_INT;
933 bits += ctz_hwi (w);
934 return bits;
937 /* Shift A left by COUNT places keeping only PREC bits of result. Shift
938 right if COUNT is negative. ARITH true specifies arithmetic shifting;
939 otherwise use logical shift. */
941 double_int
942 double_int::lshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const
944 const double_int &a = *this;
945 double_int ret;
946 lshift_double (a.low, a.high, count, prec, &ret.low, &ret.high, arith);
947 return ret;
950 /* Shift A right by COUNT places keeping only PREC bits of result. Shift
951 left if COUNT is negative. ARITH true specifies arithmetic shifting;
952 otherwise use logical shift. */
954 double_int
955 double_int::rshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const
957 const double_int &a = *this;
958 double_int ret;
959 lshift_double (a.low, a.high, -count, prec, &ret.low, &ret.high, arith);
960 return ret;
963 /* Arithmetic shift A left by COUNT places keeping only PREC bits of result.
964 Shift right if COUNT is negative. */
966 double_int
967 double_int::alshift (HOST_WIDE_INT count, unsigned int prec) const
969 double_int r;
970 lshift_double (low, high, count, prec, &r.low, &r.high, true);
971 return r;
974 /* Arithmetic shift A right by COUNT places keeping only PREC bits of result.
975 Shift left if COUNT is negative. */
977 double_int
978 double_int::arshift (HOST_WIDE_INT count, unsigned int prec) const
980 double_int r;
981 lshift_double (low, high, -count, prec, &r.low, &r.high, true);
982 return r;
985 /* Logical shift A left by COUNT places keeping only PREC bits of result.
986 Shift right if COUNT is negative. */
988 double_int
989 double_int::llshift (HOST_WIDE_INT count, unsigned int prec) const
991 double_int r;
992 lshift_double (low, high, count, prec, &r.low, &r.high, false);
993 return r;
996 /* Logical shift A right by COUNT places keeping only PREC bits of result.
997 Shift left if COUNT is negative. */
999 double_int
1000 double_int::lrshift (HOST_WIDE_INT count, unsigned int prec) const
1002 double_int r;
1003 lshift_double (low, high, -count, prec, &r.low, &r.high, false);
1004 return r;
1007 /* Rotate A left by COUNT places keeping only PREC bits of result.
1008 Rotate right if COUNT is negative. */
1010 double_int
1011 double_int::lrotate (HOST_WIDE_INT count, unsigned int prec) const
1013 double_int t1, t2;
1015 count %= prec;
1016 if (count < 0)
1017 count += prec;
1019 t1 = this->lshift (count, prec, false);
1020 t2 = this->rshift (prec - count, prec, false);
1022 return t1 | t2;
1025 /* Rotate A rigth by COUNT places keeping only PREC bits of result.
1026 Rotate right if COUNT is negative. */
1028 double_int
1029 double_int::rrotate (HOST_WIDE_INT count, unsigned int prec) const
1031 double_int t1, t2;
1033 count %= prec;
1034 if (count < 0)
1035 count += prec;
1037 t1 = this->rshift (count, prec, false);
1038 t2 = this->lshift (prec - count, prec, false);
1040 return t1 | t2;
1043 /* Returns -1 if A < B, 0 if A == B and 1 if A > B. Signedness of the
1044 comparison is given by UNS. */
1047 double_int::cmp (double_int b, bool uns) const
1049 if (uns)
1050 return this->ucmp (b);
1051 else
1052 return this->scmp (b);
1055 /* Compares two unsigned values A and B. Returns -1 if A < B, 0 if A == B,
1056 and 1 if A > B. */
1059 double_int::ucmp (double_int b) const
1061 const double_int &a = *this;
1062 if ((unsigned HOST_WIDE_INT) a.high < (unsigned HOST_WIDE_INT) b.high)
1063 return -1;
1064 if ((unsigned HOST_WIDE_INT) a.high > (unsigned HOST_WIDE_INT) b.high)
1065 return 1;
1066 if (a.low < b.low)
1067 return -1;
1068 if (a.low > b.low)
1069 return 1;
1071 return 0;
1074 /* Compares two signed values A and B. Returns -1 if A < B, 0 if A == B,
1075 and 1 if A > B. */
1078 double_int::scmp (double_int b) const
1080 const double_int &a = *this;
1081 if (a.high < b.high)
1082 return -1;
1083 if (a.high > b.high)
1084 return 1;
1085 if (a.low < b.low)
1086 return -1;
1087 if (a.low > b.low)
1088 return 1;
1090 return 0;
1093 /* Compares two unsigned values A and B for less-than. */
1095 bool
1096 double_int::ult (double_int b) const
1098 if ((unsigned HOST_WIDE_INT) high < (unsigned HOST_WIDE_INT) b.high)
1099 return true;
1100 if ((unsigned HOST_WIDE_INT) high > (unsigned HOST_WIDE_INT) b.high)
1101 return false;
1102 if (low < b.low)
1103 return true;
1104 return false;
1107 /* Compares two unsigned values A and B for greater-than. */
1109 bool
1110 double_int::ugt (double_int b) const
1112 if ((unsigned HOST_WIDE_INT) high > (unsigned HOST_WIDE_INT) b.high)
1113 return true;
1114 if ((unsigned HOST_WIDE_INT) high < (unsigned HOST_WIDE_INT) b.high)
1115 return false;
1116 if (low > b.low)
1117 return true;
1118 return false;
1121 /* Compares two signed values A and B for less-than. */
1123 bool
1124 double_int::slt (double_int b) const
1126 if (high < b.high)
1127 return true;
1128 if (high > b.high)
1129 return false;
1130 if (low < b.low)
1131 return true;
1132 return false;
1135 /* Compares two signed values A and B for greater-than. */
1137 bool
1138 double_int::sgt (double_int b) const
1140 if (high > b.high)
1141 return true;
1142 if (high < b.high)
1143 return false;
1144 if (low > b.low)
1145 return true;
1146 return false;
1150 /* Compares two values A and B. Returns max value. Signedness of the
1151 comparison is given by UNS. */
1153 double_int
1154 double_int::max (double_int b, bool uns)
1156 return (this->cmp (b, uns) == 1) ? *this : b;
1159 /* Compares two signed values A and B. Returns max value. */
1161 double_int
1162 double_int::smax (double_int b)
1164 return (this->scmp (b) == 1) ? *this : b;
1167 /* Compares two unsigned values A and B. Returns max value. */
1169 double_int
1170 double_int::umax (double_int b)
1172 return (this->ucmp (b) == 1) ? *this : b;
1175 /* Compares two values A and B. Returns mix value. Signedness of the
1176 comparison is given by UNS. */
1178 double_int
1179 double_int::min (double_int b, bool uns)
1181 return (this->cmp (b, uns) == -1) ? *this : b;
1184 /* Compares two signed values A and B. Returns min value. */
1186 double_int
1187 double_int::smin (double_int b)
1189 return (this->scmp (b) == -1) ? *this : b;
1192 /* Compares two unsigned values A and B. Returns min value. */
1194 double_int
1195 double_int::umin (double_int b)
1197 return (this->ucmp (b) == -1) ? *this : b;
1200 /* Splits last digit of *CST (taken as unsigned) in BASE and returns it. */
1202 static unsigned
1203 double_int_split_digit (double_int *cst, unsigned base)
1205 unsigned HOST_WIDE_INT resl, reml;
1206 HOST_WIDE_INT resh, remh;
1208 div_and_round_double (FLOOR_DIV_EXPR, true, cst->low, cst->high, base, 0,
1209 &resl, &resh, &reml, &remh);
1210 cst->high = resh;
1211 cst->low = resl;
1213 return reml;
1216 /* Dumps CST to FILE. If UNS is true, CST is considered to be unsigned,
1217 otherwise it is signed. */
1219 void
1220 dump_double_int (FILE *file, double_int cst, bool uns)
1222 unsigned digits[100], n;
1223 int i;
1225 if (cst.is_zero ())
1227 fprintf (file, "0");
1228 return;
1231 if (!uns && cst.is_negative ())
1233 fprintf (file, "-");
1234 cst = -cst;
1237 for (n = 0; !cst.is_zero (); n++)
1238 digits[n] = double_int_split_digit (&cst, 10);
1239 for (i = n - 1; i >= 0; i--)
1240 fprintf (file, "%u", digits[i]);
1244 /* Sets RESULT to VAL, taken unsigned if UNS is true and as signed
1245 otherwise. */
1247 void
1248 mpz_set_double_int (mpz_t result, double_int val, bool uns)
1250 bool negate = false;
1251 unsigned HOST_WIDE_INT vp[2];
1253 if (!uns && val.is_negative ())
1255 negate = true;
1256 val = -val;
1259 vp[0] = val.low;
1260 vp[1] = (unsigned HOST_WIDE_INT) val.high;
1261 mpz_import (result, 2, -1, sizeof (HOST_WIDE_INT), 0, 0, vp);
1263 if (negate)
1264 mpz_neg (result, result);
1267 /* Returns VAL converted to TYPE. If WRAP is true, then out-of-range
1268 values of VAL will be wrapped; otherwise, they will be set to the
1269 appropriate minimum or maximum TYPE bound. */
1271 double_int
1272 mpz_get_double_int (const_tree type, mpz_t val, bool wrap)
1274 unsigned HOST_WIDE_INT *vp;
1275 size_t count, numb;
1276 double_int res;
1278 if (!wrap)
1280 mpz_t min, max;
1282 mpz_init (min);
1283 mpz_init (max);
1284 get_type_static_bounds (type, min, max);
1286 if (mpz_cmp (val, min) < 0)
1287 mpz_set (val, min);
1288 else if (mpz_cmp (val, max) > 0)
1289 mpz_set (val, max);
1291 mpz_clear (min);
1292 mpz_clear (max);
1295 /* Determine the number of unsigned HOST_WIDE_INT that are required
1296 for representing the value. The code to calculate count is
1297 extracted from the GMP manual, section "Integer Import and Export":
1298 http://gmplib.org/manual/Integer-Import-and-Export.html */
1299 numb = 8*sizeof(HOST_WIDE_INT);
1300 count = (mpz_sizeinbase (val, 2) + numb-1) / numb;
1301 if (count < 2)
1302 count = 2;
1303 vp = (unsigned HOST_WIDE_INT *) alloca (count * sizeof(HOST_WIDE_INT));
1305 vp[0] = 0;
1306 vp[1] = 0;
1307 mpz_export (vp, &count, -1, sizeof (HOST_WIDE_INT), 0, 0, val);
1309 gcc_assert (wrap || count <= 2);
1311 res.low = vp[0];
1312 res.high = (HOST_WIDE_INT) vp[1];
1314 res = res.ext (TYPE_PRECISION (type), TYPE_UNSIGNED (type));
1315 if (mpz_sgn (val) < 0)
1316 res = -res;
1318 return res;