1 /* Operations with very long integers.
2 Copyright (C) 2012-2015 Free Software Foundation, Inc.
3 Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
30 #include "double-int.h"
39 #define HOST_BITS_PER_HALF_WIDE_INT 32
40 #if HOST_BITS_PER_HALF_WIDE_INT == HOST_BITS_PER_LONG
41 # define HOST_HALF_WIDE_INT long
42 #elif HOST_BITS_PER_HALF_WIDE_INT == HOST_BITS_PER_INT
43 # define HOST_HALF_WIDE_INT int
45 #error Please add support for HOST_HALF_WIDE_INT
48 #define W_TYPE_SIZE HOST_BITS_PER_WIDE_INT
49 /* Do not include longlong.h when compiler is clang-based. See PR61146. */
50 #if GCC_VERSION >= 3000 && (W_TYPE_SIZE == 32 || defined (__SIZEOF_INT128__)) && !defined(__clang__)
51 typedef unsigned HOST_HALF_WIDE_INT UHWtype
;
52 typedef unsigned HOST_WIDE_INT UWtype
;
53 typedef unsigned int UQItype
__attribute__ ((mode (QI
)));
54 typedef unsigned int USItype
__attribute__ ((mode (SI
)));
55 typedef unsigned int UDItype
__attribute__ ((mode (DI
)));
57 typedef unsigned int UDWtype
__attribute__ ((mode (DI
)));
59 typedef unsigned int UDWtype
__attribute__ ((mode (TI
)));
64 static const HOST_WIDE_INT zeros
[WIDE_INT_MAX_ELTS
] = {};
70 /* Quantities to deal with values that hold half of a wide int. Used
71 in multiply and divide. */
72 #define HALF_INT_MASK (((HOST_WIDE_INT) 1 << HOST_BITS_PER_HALF_WIDE_INT) - 1)
74 #define BLOCK_OF(TARGET) ((TARGET) / HOST_BITS_PER_WIDE_INT)
75 #define BLOCKS_NEEDED(PREC) \
76 (PREC ? (((PREC) + HOST_BITS_PER_WIDE_INT - 1) / HOST_BITS_PER_WIDE_INT) : 1)
77 #define SIGN_MASK(X) ((HOST_WIDE_INT) (X) < 0 ? -1 : 0)
79 /* Return the value a VAL[I] if I < LEN, otherwise, return 0 or -1
80 based on the top existing bit of VAL. */
82 static unsigned HOST_WIDE_INT
83 safe_uhwi (const HOST_WIDE_INT
*val
, unsigned int len
, unsigned int i
)
85 return i
< len
? val
[i
] : val
[len
- 1] < 0 ? (HOST_WIDE_INT
) -1 : 0;
88 /* Convert the integer in VAL to canonical form, returning its new length.
89 LEN is the number of blocks currently in VAL and PRECISION is the number
90 of bits in the integer it represents.
92 This function only changes the representation, not the value. */
94 canonize (HOST_WIDE_INT
*val
, unsigned int len
, unsigned int precision
)
96 unsigned int blocks_needed
= BLOCKS_NEEDED (precision
);
100 if (len
> blocks_needed
)
107 if (len
* HOST_BITS_PER_WIDE_INT
> precision
)
108 val
[len
- 1] = top
= sext_hwi (top
, precision
% HOST_BITS_PER_WIDE_INT
);
109 if (top
!= 0 && top
!= (HOST_WIDE_INT
)-1)
112 /* At this point we know that the top is either 0 or -1. Find the
113 first block that is not a copy of this. */
114 for (i
= len
- 2; i
>= 0; i
--)
116 HOST_WIDE_INT x
= val
[i
];
119 if (SIGN_MASK (x
) == top
)
122 /* We need an extra block because the top bit block i does
123 not match the extension. */
128 /* The number is 0 or -1. */
133 * Conversion routines in and out of wide_int.
136 /* Copy XLEN elements from XVAL to VAL. If NEED_CANON, canonize the
137 result for an integer with precision PRECISION. Return the length
138 of VAL (after any canonization. */
140 wi::from_array (HOST_WIDE_INT
*val
, const HOST_WIDE_INT
*xval
,
141 unsigned int xlen
, unsigned int precision
, bool need_canon
)
143 for (unsigned i
= 0; i
< xlen
; i
++)
145 return need_canon
? canonize (val
, xlen
, precision
) : xlen
;
148 /* Construct a wide int from a buffer of length LEN. BUFFER will be
149 read according to byte endianess and word endianess of the target.
150 Only the lower BUFFER_LEN bytes of the result are set; the remaining
151 high bytes are cleared. */
153 wi::from_buffer (const unsigned char *buffer
, unsigned int buffer_len
)
155 unsigned int precision
= buffer_len
* BITS_PER_UNIT
;
156 wide_int result
= wide_int::create (precision
);
157 unsigned int words
= buffer_len
/ UNITS_PER_WORD
;
159 /* We have to clear all the bits ourself, as we merely or in values
161 unsigned int len
= BLOCKS_NEEDED (precision
);
162 HOST_WIDE_INT
*val
= result
.write_val ();
163 for (unsigned int i
= 0; i
< len
; ++i
)
166 for (unsigned int byte
= 0; byte
< buffer_len
; byte
++)
170 unsigned int bitpos
= byte
* BITS_PER_UNIT
;
171 unsigned HOST_WIDE_INT value
;
173 if (buffer_len
> UNITS_PER_WORD
)
175 unsigned int word
= byte
/ UNITS_PER_WORD
;
177 if (WORDS_BIG_ENDIAN
)
178 word
= (words
- 1) - word
;
180 offset
= word
* UNITS_PER_WORD
;
182 if (BYTES_BIG_ENDIAN
)
183 offset
+= (UNITS_PER_WORD
- 1) - (byte
% UNITS_PER_WORD
);
185 offset
+= byte
% UNITS_PER_WORD
;
188 offset
= BYTES_BIG_ENDIAN
? (buffer_len
- 1) - byte
: byte
;
190 value
= (unsigned HOST_WIDE_INT
) buffer
[offset
];
192 index
= bitpos
/ HOST_BITS_PER_WIDE_INT
;
193 val
[index
] |= value
<< (bitpos
% HOST_BITS_PER_WIDE_INT
);
196 result
.set_len (canonize (val
, len
, precision
));
201 /* Sets RESULT from X, the sign is taken according to SGN. */
203 wi::to_mpz (const wide_int_ref
&x
, mpz_t result
, signop sgn
)
205 int len
= x
.get_len ();
206 const HOST_WIDE_INT
*v
= x
.get_val ();
207 int excess
= len
* HOST_BITS_PER_WIDE_INT
- x
.get_precision ();
209 if (wi::neg_p (x
, sgn
))
211 /* We use ones complement to avoid -x80..0 edge case that -
213 HOST_WIDE_INT
*t
= XALLOCAVEC (HOST_WIDE_INT
, len
);
214 for (int i
= 0; i
< len
; i
++)
217 t
[len
- 1] = (unsigned HOST_WIDE_INT
) t
[len
- 1] << excess
>> excess
;
218 mpz_import (result
, len
, -1, sizeof (HOST_WIDE_INT
), 0, 0, t
);
219 mpz_com (result
, result
);
223 HOST_WIDE_INT
*t
= XALLOCAVEC (HOST_WIDE_INT
, len
);
224 for (int i
= 0; i
< len
- 1; i
++)
226 t
[len
- 1] = (unsigned HOST_WIDE_INT
) v
[len
- 1] << excess
>> excess
;
227 mpz_import (result
, len
, -1, sizeof (HOST_WIDE_INT
), 0, 0, t
);
230 mpz_import (result
, len
, -1, sizeof (HOST_WIDE_INT
), 0, 0, v
);
233 /* Returns X converted to TYPE. If WRAP is true, then out-of-range
234 values of VAL will be wrapped; otherwise, they will be set to the
235 appropriate minimum or maximum TYPE bound. */
237 wi::from_mpz (const_tree type
, mpz_t x
, bool wrap
)
240 unsigned int prec
= TYPE_PRECISION (type
);
241 wide_int res
= wide_int::create (prec
);
249 get_type_static_bounds (type
, min
, max
);
251 if (mpz_cmp (x
, min
) < 0)
253 else if (mpz_cmp (x
, max
) > 0)
260 /* Determine the number of unsigned HOST_WIDE_INTs that are required
261 for representing the absolute value. The code to calculate count is
262 extracted from the GMP manual, section "Integer Import and Export":
263 http://gmplib.org/manual/Integer-Import-and-Export.html */
264 numb
= CHAR_BIT
* sizeof (HOST_WIDE_INT
);
265 count
= (mpz_sizeinbase (x
, 2) + numb
- 1) / numb
;
266 HOST_WIDE_INT
*val
= res
.write_val ();
267 /* Read the absolute value.
269 Write directly to the wide_int storage if possible, otherwise leave
270 GMP to allocate the memory for us. It might be slightly more efficient
271 to use mpz_tdiv_r_2exp for the latter case, but the situation is
272 pathological and it seems safer to operate on the original mpz value
274 void *valres
= mpz_export (count
<= WIDE_INT_MAX_ELTS
? val
: 0,
275 &count
, -1, sizeof (HOST_WIDE_INT
), 0, 0, x
);
281 count
= MIN (count
, BLOCKS_NEEDED (prec
));
284 memcpy (val
, valres
, count
* sizeof (HOST_WIDE_INT
));
287 /* Zero-extend the absolute value to PREC bits. */
288 if (count
< BLOCKS_NEEDED (prec
) && val
[count
- 1] < 0)
291 count
= canonize (val
, count
, prec
);
301 * Largest and smallest values in a mode.
304 /* Return the largest SGNed number that is representable in PRECISION bits.
306 TODO: There is still code from the double_int era that trys to
307 make up for the fact that double int's could not represent the
308 min and max values of all types. This code should be removed
309 because the min and max values can always be represented in
310 wide_ints and int-csts. */
312 wi::max_value (unsigned int precision
, signop sgn
)
314 gcc_checking_assert (precision
!= 0);
316 /* The unsigned max is just all ones. */
317 return shwi (-1, precision
);
319 /* The signed max is all ones except the top bit. This must be
320 explicitly represented. */
321 return mask (precision
- 1, false, precision
);
324 /* Return the largest SGNed number that is representable in PRECISION bits. */
326 wi::min_value (unsigned int precision
, signop sgn
)
328 gcc_checking_assert (precision
!= 0);
330 return uhwi (0, precision
);
332 /* The signed min is all zeros except the top bit. This must be
333 explicitly represented. */
334 return wi::set_bit_in_zero (precision
- 1, precision
);
341 /* Convert the number represented by XVAL, XLEN and XPRECISION, which has
342 signedness SGN, to an integer that has PRECISION bits. Store the blocks
343 in VAL and return the number of blocks used.
345 This function can handle both extension (PRECISION > XPRECISION)
346 and truncation (PRECISION < XPRECISION). */
348 wi::force_to_size (HOST_WIDE_INT
*val
, const HOST_WIDE_INT
*xval
,
349 unsigned int xlen
, unsigned int xprecision
,
350 unsigned int precision
, signop sgn
)
352 unsigned int blocks_needed
= BLOCKS_NEEDED (precision
);
353 unsigned int len
= blocks_needed
< xlen
? blocks_needed
: xlen
;
354 for (unsigned i
= 0; i
< len
; i
++)
357 if (precision
> xprecision
)
359 unsigned int small_xprecision
= xprecision
% HOST_BITS_PER_WIDE_INT
;
364 if (small_xprecision
&& len
== BLOCKS_NEEDED (xprecision
))
365 val
[len
- 1] = zext_hwi (val
[len
- 1], small_xprecision
);
366 else if (val
[len
- 1] < 0)
368 while (len
< BLOCKS_NEEDED (xprecision
))
370 if (small_xprecision
)
371 val
[len
- 1] = zext_hwi (val
[len
- 1], small_xprecision
);
378 if (small_xprecision
&& len
== BLOCKS_NEEDED (xprecision
))
379 val
[len
- 1] = sext_hwi (val
[len
- 1], small_xprecision
);
382 len
= canonize (val
, len
, precision
);
387 /* This function hides the fact that we cannot rely on the bits beyond
388 the precision. This issue comes up in the relational comparisions
389 where we do allow comparisons of values of different precisions. */
390 static inline HOST_WIDE_INT
391 selt (const HOST_WIDE_INT
*a
, unsigned int len
,
392 unsigned int blocks_needed
, unsigned int small_prec
,
393 unsigned int index
, signop sgn
)
398 else if (index
< blocks_needed
|| sgn
== SIGNED
)
399 /* Signed or within the precision. */
400 val
= SIGN_MASK (a
[len
- 1]);
402 /* Unsigned extension beyond the precision. */
405 if (small_prec
&& index
== blocks_needed
- 1)
406 return (sgn
== SIGNED
407 ? sext_hwi (val
, small_prec
)
408 : zext_hwi (val
, small_prec
));
413 /* Find the highest bit represented in a wide int. This will in
414 general have the same value as the sign bit. */
415 static inline HOST_WIDE_INT
416 top_bit_of (const HOST_WIDE_INT
*a
, unsigned int len
, unsigned int prec
)
418 int excess
= len
* HOST_BITS_PER_WIDE_INT
- prec
;
419 unsigned HOST_WIDE_INT val
= a
[len
- 1];
422 return val
>> (HOST_BITS_PER_WIDE_INT
- 1);
426 * Comparisons, note that only equality is an operator. The other
427 * comparisons cannot be operators since they are inherently signed or
428 * unsigned and C++ has no such operators.
431 /* Return true if OP0 == OP1. */
433 wi::eq_p_large (const HOST_WIDE_INT
*op0
, unsigned int op0len
,
434 const HOST_WIDE_INT
*op1
, unsigned int op1len
,
438 unsigned int small_prec
= prec
& (HOST_BITS_PER_WIDE_INT
- 1);
440 if (op0len
!= op1len
)
443 if (op0len
== BLOCKS_NEEDED (prec
) && small_prec
)
445 /* It does not matter if we zext or sext here, we just have to
446 do both the same way. */
447 if (zext_hwi (op0
[l0
], small_prec
) != zext_hwi (op1
[l0
], small_prec
))
453 if (op0
[l0
] != op1
[l0
])
461 /* Return true if OP0 < OP1 using signed comparisons. */
463 wi::lts_p_large (const HOST_WIDE_INT
*op0
, unsigned int op0len
,
464 unsigned int precision
,
465 const HOST_WIDE_INT
*op1
, unsigned int op1len
)
467 HOST_WIDE_INT s0
, s1
;
468 unsigned HOST_WIDE_INT u0
, u1
;
469 unsigned int blocks_needed
= BLOCKS_NEEDED (precision
);
470 unsigned int small_prec
= precision
& (HOST_BITS_PER_WIDE_INT
- 1);
471 int l
= MAX (op0len
- 1, op1len
- 1);
473 /* Only the top block is compared as signed. The rest are unsigned
475 s0
= selt (op0
, op0len
, blocks_needed
, small_prec
, l
, SIGNED
);
476 s1
= selt (op1
, op1len
, blocks_needed
, small_prec
, l
, SIGNED
);
485 u0
= selt (op0
, op0len
, blocks_needed
, small_prec
, l
, SIGNED
);
486 u1
= selt (op1
, op1len
, blocks_needed
, small_prec
, l
, SIGNED
);
498 /* Returns -1 if OP0 < OP1, 0 if OP0 == OP1 and 1 if OP0 > OP1 using
501 wi::cmps_large (const HOST_WIDE_INT
*op0
, unsigned int op0len
,
502 unsigned int precision
,
503 const HOST_WIDE_INT
*op1
, unsigned int op1len
)
505 HOST_WIDE_INT s0
, s1
;
506 unsigned HOST_WIDE_INT u0
, u1
;
507 unsigned int blocks_needed
= BLOCKS_NEEDED (precision
);
508 unsigned int small_prec
= precision
& (HOST_BITS_PER_WIDE_INT
- 1);
509 int l
= MAX (op0len
- 1, op1len
- 1);
511 /* Only the top block is compared as signed. The rest are unsigned
513 s0
= selt (op0
, op0len
, blocks_needed
, small_prec
, l
, SIGNED
);
514 s1
= selt (op1
, op1len
, blocks_needed
, small_prec
, l
, SIGNED
);
523 u0
= selt (op0
, op0len
, blocks_needed
, small_prec
, l
, SIGNED
);
524 u1
= selt (op1
, op1len
, blocks_needed
, small_prec
, l
, SIGNED
);
536 /* Return true if OP0 < OP1 using unsigned comparisons. */
538 wi::ltu_p_large (const HOST_WIDE_INT
*op0
, unsigned int op0len
,
539 unsigned int precision
,
540 const HOST_WIDE_INT
*op1
, unsigned int op1len
)
542 unsigned HOST_WIDE_INT x0
;
543 unsigned HOST_WIDE_INT x1
;
544 unsigned int blocks_needed
= BLOCKS_NEEDED (precision
);
545 unsigned int small_prec
= precision
& (HOST_BITS_PER_WIDE_INT
- 1);
546 int l
= MAX (op0len
- 1, op1len
- 1);
550 x0
= selt (op0
, op0len
, blocks_needed
, small_prec
, l
, UNSIGNED
);
551 x1
= selt (op1
, op1len
, blocks_needed
, small_prec
, l
, UNSIGNED
);
562 /* Returns -1 if OP0 < OP1, 0 if OP0 == OP1 and 1 if OP0 > OP1 using
563 unsigned compares. */
565 wi::cmpu_large (const HOST_WIDE_INT
*op0
, unsigned int op0len
,
566 unsigned int precision
,
567 const HOST_WIDE_INT
*op1
, unsigned int op1len
)
569 unsigned HOST_WIDE_INT x0
;
570 unsigned HOST_WIDE_INT x1
;
571 unsigned int blocks_needed
= BLOCKS_NEEDED (precision
);
572 unsigned int small_prec
= precision
& (HOST_BITS_PER_WIDE_INT
- 1);
573 int l
= MAX (op0len
- 1, op1len
- 1);
577 x0
= selt (op0
, op0len
, blocks_needed
, small_prec
, l
, UNSIGNED
);
578 x1
= selt (op1
, op1len
, blocks_needed
, small_prec
, l
, UNSIGNED
);
593 /* Sign-extend the number represented by XVAL and XLEN into VAL,
594 starting at OFFSET. Return the number of blocks in VAL. Both XVAL
595 and VAL have PRECISION bits. */
597 wi::sext_large (HOST_WIDE_INT
*val
, const HOST_WIDE_INT
*xval
,
598 unsigned int xlen
, unsigned int precision
, unsigned int offset
)
600 unsigned int len
= offset
/ HOST_BITS_PER_WIDE_INT
;
601 /* Extending beyond the precision is a no-op. If we have only stored
602 OFFSET bits or fewer, the rest are already signs. */
603 if (offset
>= precision
|| len
>= xlen
)
605 for (unsigned i
= 0; i
< xlen
; ++i
)
609 unsigned int suboffset
= offset
% HOST_BITS_PER_WIDE_INT
;
610 for (unsigned int i
= 0; i
< len
; i
++)
614 val
[len
] = sext_hwi (xval
[len
], suboffset
);
617 return canonize (val
, len
, precision
);
620 /* Zero-extend the number represented by XVAL and XLEN into VAL,
621 starting at OFFSET. Return the number of blocks in VAL. Both XVAL
622 and VAL have PRECISION bits. */
624 wi::zext_large (HOST_WIDE_INT
*val
, const HOST_WIDE_INT
*xval
,
625 unsigned int xlen
, unsigned int precision
, unsigned int offset
)
627 unsigned int len
= offset
/ HOST_BITS_PER_WIDE_INT
;
628 /* Extending beyond the precision is a no-op. If we have only stored
629 OFFSET bits or fewer, and the upper stored bit is zero, then there
631 if (offset
>= precision
|| (len
>= xlen
&& xval
[xlen
- 1] >= 0))
633 for (unsigned i
= 0; i
< xlen
; ++i
)
637 unsigned int suboffset
= offset
% HOST_BITS_PER_WIDE_INT
;
638 for (unsigned int i
= 0; i
< len
; i
++)
639 val
[i
] = i
< xlen
? xval
[i
] : -1;
641 val
[len
] = zext_hwi (len
< xlen
? xval
[len
] : -1, suboffset
);
644 return canonize (val
, len
+ 1, precision
);
648 * Masking, inserting, shifting, rotating.
651 /* Insert WIDTH bits from Y into X starting at START. */
653 wi::insert (const wide_int
&x
, const wide_int
&y
, unsigned int start
,
660 unsigned int precision
= x
.get_precision ();
661 if (start
>= precision
)
664 gcc_checking_assert (precision
>= width
);
666 if (start
+ width
>= precision
)
667 width
= precision
- start
;
669 mask
= wi::shifted_mask (start
, width
, false, precision
);
670 tmp
= wi::lshift (wide_int::from (y
, precision
, UNSIGNED
), start
);
673 tmp
= wi::bit_and_not (x
, mask
);
674 result
= result
| tmp
;
679 /* Copy the number represented by XVAL and XLEN into VAL, setting bit BIT.
680 Return the number of blocks in VAL. Both XVAL and VAL have PRECISION
683 wi::set_bit_large (HOST_WIDE_INT
*val
, const HOST_WIDE_INT
*xval
,
684 unsigned int xlen
, unsigned int precision
, unsigned int bit
)
686 unsigned int block
= bit
/ HOST_BITS_PER_WIDE_INT
;
687 unsigned int subbit
= bit
% HOST_BITS_PER_WIDE_INT
;
689 if (block
+ 1 >= xlen
)
691 /* The operation either affects the last current block or needs
693 unsigned int len
= block
+ 1;
694 for (unsigned int i
= 0; i
< len
; i
++)
695 val
[i
] = safe_uhwi (xval
, xlen
, i
);
696 val
[block
] |= (unsigned HOST_WIDE_INT
) 1 << subbit
;
698 /* If the bit we just set is at the msb of the block, make sure
699 that any higher bits are zeros. */
700 if (bit
+ 1 < precision
&& subbit
== HOST_BITS_PER_WIDE_INT
- 1)
706 for (unsigned int i
= 0; i
< xlen
; i
++)
708 val
[block
] |= (unsigned HOST_WIDE_INT
) 1 << subbit
;
709 return canonize (val
, xlen
, precision
);
715 wide_int_storage::bswap () const
717 wide_int result
= wide_int::create (precision
);
719 unsigned int len
= BLOCKS_NEEDED (precision
);
720 unsigned int xlen
= get_len ();
721 const HOST_WIDE_INT
*xval
= get_val ();
722 HOST_WIDE_INT
*val
= result
.write_val ();
724 /* This is not a well defined operation if the precision is not a
726 gcc_assert ((precision
& 0x7) == 0);
728 for (i
= 0; i
< len
; i
++)
731 /* Only swap the bytes that are not the padding. */
732 for (s
= 0; s
< precision
; s
+= 8)
734 unsigned int d
= precision
- s
- 8;
735 unsigned HOST_WIDE_INT byte
;
737 unsigned int block
= s
/ HOST_BITS_PER_WIDE_INT
;
738 unsigned int offset
= s
& (HOST_BITS_PER_WIDE_INT
- 1);
740 byte
= (safe_uhwi (xval
, xlen
, block
) >> offset
) & 0xff;
742 block
= d
/ HOST_BITS_PER_WIDE_INT
;
743 offset
= d
& (HOST_BITS_PER_WIDE_INT
- 1);
745 val
[block
] |= byte
<< offset
;
748 result
.set_len (canonize (val
, len
, precision
));
752 /* Fill VAL with a mask where the lower WIDTH bits are ones and the bits
753 above that up to PREC are zeros. The result is inverted if NEGATE
754 is true. Return the number of blocks in VAL. */
756 wi::mask (HOST_WIDE_INT
*val
, unsigned int width
, bool negate
,
761 val
[0] = negate
? 0 : -1;
766 val
[0] = negate
? -1 : 0;
771 while (i
< width
/ HOST_BITS_PER_WIDE_INT
)
772 val
[i
++] = negate
? 0 : -1;
774 unsigned int shift
= width
& (HOST_BITS_PER_WIDE_INT
- 1);
777 HOST_WIDE_INT last
= ((unsigned HOST_WIDE_INT
) 1 << shift
) - 1;
778 val
[i
++] = negate
? ~last
: last
;
781 val
[i
++] = negate
? -1 : 0;
786 /* Fill VAL with a mask where the lower START bits are zeros, the next WIDTH
787 bits are ones, and the bits above that up to PREC are zeros. The result
788 is inverted if NEGATE is true. Return the number of blocks in VAL. */
790 wi::shifted_mask (HOST_WIDE_INT
*val
, unsigned int start
, unsigned int width
,
791 bool negate
, unsigned int prec
)
793 if (start
>= prec
|| width
== 0)
795 val
[0] = negate
? -1 : 0;
799 if (width
> prec
- start
)
800 width
= prec
- start
;
801 unsigned int end
= start
+ width
;
804 while (i
< start
/ HOST_BITS_PER_WIDE_INT
)
805 val
[i
++] = negate
? -1 : 0;
807 unsigned int shift
= start
& (HOST_BITS_PER_WIDE_INT
- 1);
810 HOST_WIDE_INT block
= ((unsigned HOST_WIDE_INT
) 1 << shift
) - 1;
812 if (shift
< HOST_BITS_PER_WIDE_INT
)
815 block
= ((unsigned HOST_WIDE_INT
) 1 << shift
) - block
- 1;
816 val
[i
++] = negate
? ~block
: block
;
821 val
[i
++] = negate
? block
: ~block
;
824 while (i
< end
/ HOST_BITS_PER_WIDE_INT
)
826 val
[i
++] = negate
? 0 : -1;
828 shift
= end
& (HOST_BITS_PER_WIDE_INT
- 1);
832 HOST_WIDE_INT block
= ((unsigned HOST_WIDE_INT
) 1 << shift
) - 1;
833 val
[i
++] = negate
? ~block
: block
;
836 val
[i
++] = negate
? -1 : 0;
842 * logical operations.
845 /* Set VAL to OP0 & OP1. Return the number of blocks used. */
847 wi::and_large (HOST_WIDE_INT
*val
, const HOST_WIDE_INT
*op0
,
848 unsigned int op0len
, const HOST_WIDE_INT
*op1
,
849 unsigned int op1len
, unsigned int prec
)
853 bool need_canon
= true;
855 unsigned int len
= MAX (op0len
, op1len
);
858 HOST_WIDE_INT op1mask
= -top_bit_of (op1
, op1len
, prec
);
876 HOST_WIDE_INT op0mask
= -top_bit_of (op0
, op0len
, prec
);
892 val
[l0
] = op0
[l0
] & op1
[l0
];
897 len
= canonize (val
, len
, prec
);
902 /* Set VAL to OP0 & ~OP1. Return the number of blocks used. */
904 wi::and_not_large (HOST_WIDE_INT
*val
, const HOST_WIDE_INT
*op0
,
905 unsigned int op0len
, const HOST_WIDE_INT
*op1
,
906 unsigned int op1len
, unsigned int prec
)
911 bool need_canon
= true;
913 unsigned int len
= MAX (op0len
, op1len
);
916 HOST_WIDE_INT op1mask
= -top_bit_of (op1
, op1len
, prec
);
934 HOST_WIDE_INT op0mask
= -top_bit_of (op0
, op0len
, prec
);
950 val
[l0
] = op0
[l0
] & ~op1
[l0
];
955 len
= canonize (val
, len
, prec
);
960 /* Set VAL to OP0 | OP1. Return the number of blocks used. */
962 wi::or_large (HOST_WIDE_INT
*val
, const HOST_WIDE_INT
*op0
,
963 unsigned int op0len
, const HOST_WIDE_INT
*op1
,
964 unsigned int op1len
, unsigned int prec
)
969 bool need_canon
= true;
971 unsigned int len
= MAX (op0len
, op1len
);
974 HOST_WIDE_INT op1mask
= -top_bit_of (op1
, op1len
, prec
);
992 HOST_WIDE_INT op0mask
= -top_bit_of (op0
, op0len
, prec
);
1008 val
[l0
] = op0
[l0
] | op1
[l0
];
1013 len
= canonize (val
, len
, prec
);
1018 /* Set VAL to OP0 | ~OP1. Return the number of blocks used. */
1020 wi::or_not_large (HOST_WIDE_INT
*val
, const HOST_WIDE_INT
*op0
,
1021 unsigned int op0len
, const HOST_WIDE_INT
*op1
,
1022 unsigned int op1len
, unsigned int prec
)
1025 int l0
= op0len
- 1;
1026 int l1
= op1len
- 1;
1027 bool need_canon
= true;
1029 unsigned int len
= MAX (op0len
, op1len
);
1032 HOST_WIDE_INT op1mask
= -top_bit_of (op1
, op1len
, prec
);
1050 HOST_WIDE_INT op0mask
= -top_bit_of (op0
, op0len
, prec
);
1066 val
[l0
] = op0
[l0
] | ~op1
[l0
];
1071 len
= canonize (val
, len
, prec
);
1076 /* Set VAL to OP0 ^ OP1. Return the number of blocks used. */
1078 wi::xor_large (HOST_WIDE_INT
*val
, const HOST_WIDE_INT
*op0
,
1079 unsigned int op0len
, const HOST_WIDE_INT
*op1
,
1080 unsigned int op1len
, unsigned int prec
)
1083 int l0
= op0len
- 1;
1084 int l1
= op1len
- 1;
1086 unsigned int len
= MAX (op0len
, op1len
);
1089 HOST_WIDE_INT op1mask
= -top_bit_of (op1
, op1len
, prec
);
1092 val
[l0
] = op0
[l0
] ^ op1mask
;
1099 HOST_WIDE_INT op0mask
= -top_bit_of (op0
, op0len
, prec
);
1102 val
[l1
] = op0mask
^ op1
[l1
];
1109 val
[l0
] = op0
[l0
] ^ op1
[l0
];
1113 return canonize (val
, len
, prec
);
1120 /* Set VAL to OP0 + OP1. If OVERFLOW is nonnull, record in *OVERFLOW
1121 whether the result overflows when OP0 and OP1 are treated as having
1122 signedness SGN. Return the number of blocks in VAL. */
1124 wi::add_large (HOST_WIDE_INT
*val
, const HOST_WIDE_INT
*op0
,
1125 unsigned int op0len
, const HOST_WIDE_INT
*op1
,
1126 unsigned int op1len
, unsigned int prec
,
1127 signop sgn
, bool *overflow
)
1129 unsigned HOST_WIDE_INT o0
= 0;
1130 unsigned HOST_WIDE_INT o1
= 0;
1131 unsigned HOST_WIDE_INT x
= 0;
1132 unsigned HOST_WIDE_INT carry
= 0;
1133 unsigned HOST_WIDE_INT old_carry
= 0;
1134 unsigned HOST_WIDE_INT mask0
, mask1
;
1137 unsigned int len
= MAX (op0len
, op1len
);
1138 mask0
= -top_bit_of (op0
, op0len
, prec
);
1139 mask1
= -top_bit_of (op1
, op1len
, prec
);
1140 /* Add all of the explicitly defined elements. */
1142 for (i
= 0; i
< len
; i
++)
1144 o0
= i
< op0len
? (unsigned HOST_WIDE_INT
) op0
[i
] : mask0
;
1145 o1
= i
< op1len
? (unsigned HOST_WIDE_INT
) op1
[i
] : mask1
;
1146 x
= o0
+ o1
+ carry
;
1149 carry
= carry
== 0 ? x
< o0
: x
<= o0
;
1152 if (len
* HOST_BITS_PER_WIDE_INT
< prec
)
1154 val
[len
] = mask0
+ mask1
+ carry
;
1161 unsigned int shift
= -prec
% HOST_BITS_PER_WIDE_INT
;
1164 unsigned HOST_WIDE_INT x
= (val
[len
- 1] ^ o0
) & (val
[len
- 1] ^ o1
);
1165 *overflow
= (HOST_WIDE_INT
) (x
<< shift
) < 0;
1169 /* Put the MSB of X and O0 and in the top of the HWI. */
1173 *overflow
= (x
<= o0
);
1175 *overflow
= (x
< o0
);
1179 return canonize (val
, len
, prec
);
1182 /* Subroutines of the multiplication and division operations. Unpack
1183 the first IN_LEN HOST_WIDE_INTs in INPUT into 2 * IN_LEN
1184 HOST_HALF_WIDE_INTs of RESULT. The rest of RESULT is filled by
1185 uncompressing the top bit of INPUT[IN_LEN - 1]. */
1187 wi_unpack (unsigned HOST_HALF_WIDE_INT
*result
, const HOST_WIDE_INT
*input
,
1188 unsigned int in_len
, unsigned int out_len
,
1189 unsigned int prec
, signop sgn
)
1193 unsigned int small_prec
= prec
& (HOST_BITS_PER_WIDE_INT
- 1);
1194 unsigned int blocks_needed
= BLOCKS_NEEDED (prec
);
1199 mask
= -top_bit_of ((const HOST_WIDE_INT
*) input
, in_len
, prec
);
1200 mask
&= HALF_INT_MASK
;
1205 for (i
= 0; i
< blocks_needed
- 1; i
++)
1207 HOST_WIDE_INT x
= safe_uhwi (input
, in_len
, i
);
1209 result
[j
++] = x
>> HOST_BITS_PER_HALF_WIDE_INT
;
1212 HOST_WIDE_INT x
= safe_uhwi (input
, in_len
, i
);
1216 x
= sext_hwi (x
, small_prec
);
1218 x
= zext_hwi (x
, small_prec
);
1221 result
[j
++] = x
>> HOST_BITS_PER_HALF_WIDE_INT
;
1223 /* Smear the sign bit. */
1228 /* The inverse of wi_unpack. IN_LEN is the number of input
1229 blocks and PRECISION is the precision of the result. Return the
1230 number of blocks in the canonicalized result. */
1232 wi_pack (HOST_WIDE_INT
*result
,
1233 const unsigned HOST_HALF_WIDE_INT
*input
,
1234 unsigned int in_len
, unsigned int precision
)
1238 unsigned int blocks_needed
= BLOCKS_NEEDED (precision
);
1240 while (i
+ 1 < in_len
)
1242 result
[j
++] = ((unsigned HOST_WIDE_INT
) input
[i
]
1243 | ((unsigned HOST_WIDE_INT
) input
[i
+ 1]
1244 << HOST_BITS_PER_HALF_WIDE_INT
));
1248 /* Handle the case where in_len is odd. For this we zero extend. */
1250 result
[j
++] = (unsigned HOST_WIDE_INT
) input
[i
];
1251 else if (j
< blocks_needed
)
1253 return canonize (result
, j
, precision
);
1256 /* Multiply Op1 by Op2. If HIGH is set, only the upper half of the
1259 If HIGH is not set, throw away the upper half after the check is
1260 made to see if it overflows. Unfortunately there is no better way
1261 to check for overflow than to do this. If OVERFLOW is nonnull,
1262 record in *OVERFLOW whether the result overflowed. SGN controls
1263 the signedness and is used to check overflow or if HIGH is set. */
1265 wi::mul_internal (HOST_WIDE_INT
*val
, const HOST_WIDE_INT
*op1val
,
1266 unsigned int op1len
, const HOST_WIDE_INT
*op2val
,
1267 unsigned int op2len
, unsigned int prec
, signop sgn
,
1268 bool *overflow
, bool high
)
1270 unsigned HOST_WIDE_INT o0
, o1
, k
, t
;
1273 unsigned int blocks_needed
= BLOCKS_NEEDED (prec
);
1274 unsigned int half_blocks_needed
= blocks_needed
* 2;
1275 /* The sizes here are scaled to support a 2x largest mode by 2x
1276 largest mode yielding a 4x largest mode result. This is what is
1279 unsigned HOST_HALF_WIDE_INT
1280 u
[4 * MAX_BITSIZE_MODE_ANY_INT
/ HOST_BITS_PER_HALF_WIDE_INT
];
1281 unsigned HOST_HALF_WIDE_INT
1282 v
[4 * MAX_BITSIZE_MODE_ANY_INT
/ HOST_BITS_PER_HALF_WIDE_INT
];
1283 /* The '2' in 'R' is because we are internally doing a full
1285 unsigned HOST_HALF_WIDE_INT
1286 r
[2 * 4 * MAX_BITSIZE_MODE_ANY_INT
/ HOST_BITS_PER_HALF_WIDE_INT
];
1287 HOST_WIDE_INT mask
= ((HOST_WIDE_INT
)1 << HOST_BITS_PER_HALF_WIDE_INT
) - 1;
1289 /* If the top level routine did not really pass in an overflow, then
1290 just make sure that we never attempt to set it. */
1291 bool needs_overflow
= (overflow
!= 0);
1295 wide_int_ref op1
= wi::storage_ref (op1val
, op1len
, prec
);
1296 wide_int_ref op2
= wi::storage_ref (op2val
, op2len
, prec
);
1298 /* This is a surprisingly common case, so do it first. */
1299 if (op1
== 0 || op2
== 0)
1306 if (sgn
== UNSIGNED
)
1308 /* If the inputs are single HWIs and the output has room for at
1309 least two HWIs, we can use umul_ppmm directly. */
1310 if (prec
>= HOST_BITS_PER_WIDE_INT
* 2
1311 && wi::fits_uhwi_p (op1
)
1312 && wi::fits_uhwi_p (op2
))
1314 /* This case never overflows. */
1320 umul_ppmm (val
[1], val
[0], op1
.ulow (), op2
.ulow ());
1321 if (val
[1] < 0 && prec
> HOST_BITS_PER_WIDE_INT
* 2)
1326 return 1 + (val
[1] != 0 || val
[0] < 0);
1328 /* Likewise if the output is a full single HWI, except that the
1329 upper HWI of the result is only used for determining overflow.
1330 (We handle this case inline when overflow isn't needed.) */
1331 else if (prec
== HOST_BITS_PER_WIDE_INT
)
1333 unsigned HOST_WIDE_INT upper
;
1334 umul_ppmm (upper
, val
[0], op1
.ulow (), op2
.ulow ());
1336 *overflow
= (upper
!= 0);
1344 /* Handle multiplications by 1. */
1349 val
[0] = wi::neg_p (op2
, sgn
) ? -1 : 0;
1352 for (i
= 0; i
< op2len
; i
++)
1360 val
[0] = wi::neg_p (op1
, sgn
) ? -1 : 0;
1363 for (i
= 0; i
< op1len
; i
++)
1368 /* If we need to check for overflow, we can only do half wide
1369 multiplies quickly because we need to look at the top bits to
1370 check for the overflow. */
1371 if ((high
|| needs_overflow
)
1372 && (prec
<= HOST_BITS_PER_HALF_WIDE_INT
))
1374 unsigned HOST_WIDE_INT r
;
1378 o0
= op1
.to_shwi ();
1379 o1
= op2
.to_shwi ();
1383 o0
= op1
.to_uhwi ();
1384 o1
= op2
.to_uhwi ();
1392 if ((HOST_WIDE_INT
) r
!= sext_hwi (r
, prec
))
1397 if ((r
>> prec
) != 0)
1401 val
[0] = high
? r
>> prec
: r
;
1405 /* We do unsigned mul and then correct it. */
1406 wi_unpack (u
, op1val
, op1len
, half_blocks_needed
, prec
, SIGNED
);
1407 wi_unpack (v
, op2val
, op2len
, half_blocks_needed
, prec
, SIGNED
);
1409 /* The 2 is for a full mult. */
1410 memset (r
, 0, half_blocks_needed
* 2
1411 * HOST_BITS_PER_HALF_WIDE_INT
/ CHAR_BIT
);
1413 for (j
= 0; j
< half_blocks_needed
; j
++)
1416 for (i
= 0; i
< half_blocks_needed
; i
++)
1418 t
= ((unsigned HOST_WIDE_INT
)u
[i
] * (unsigned HOST_WIDE_INT
)v
[j
]
1420 r
[i
+ j
] = t
& HALF_INT_MASK
;
1421 k
= t
>> HOST_BITS_PER_HALF_WIDE_INT
;
1423 r
[j
+ half_blocks_needed
] = k
;
1426 /* We did unsigned math above. For signed we must adjust the
1427 product (assuming we need to see that). */
1428 if (sgn
== SIGNED
&& (high
|| needs_overflow
))
1430 unsigned HOST_WIDE_INT b
;
1431 if (wi::neg_p (op1
))
1434 for (i
= 0; i
< half_blocks_needed
; i
++)
1436 t
= (unsigned HOST_WIDE_INT
)r
[i
+ half_blocks_needed
]
1437 - (unsigned HOST_WIDE_INT
)v
[i
] - b
;
1438 r
[i
+ half_blocks_needed
] = t
& HALF_INT_MASK
;
1439 b
= t
>> (HOST_BITS_PER_WIDE_INT
- 1);
1442 if (wi::neg_p (op2
))
1445 for (i
= 0; i
< half_blocks_needed
; i
++)
1447 t
= (unsigned HOST_WIDE_INT
)r
[i
+ half_blocks_needed
]
1448 - (unsigned HOST_WIDE_INT
)u
[i
] - b
;
1449 r
[i
+ half_blocks_needed
] = t
& HALF_INT_MASK
;
1450 b
= t
>> (HOST_BITS_PER_WIDE_INT
- 1);
1459 /* For unsigned, overflow is true if any of the top bits are set.
1460 For signed, overflow is true if any of the top bits are not equal
1462 if (sgn
== UNSIGNED
)
1466 top
= r
[(half_blocks_needed
) - 1];
1467 top
= SIGN_MASK (top
<< (HOST_BITS_PER_WIDE_INT
/ 2));
1471 for (i
= half_blocks_needed
; i
< half_blocks_needed
* 2; i
++)
1472 if (((HOST_WIDE_INT
)(r
[i
] & mask
)) != top
)
1476 int r_offset
= high
? half_blocks_needed
: 0;
1477 return wi_pack (val
, &r
[r_offset
], half_blocks_needed
, prec
);
1480 /* Compute the population count of X. */
1482 wi::popcount (const wide_int_ref
&x
)
1487 /* The high order block is special if it is the last block and the
1488 precision is not an even multiple of HOST_BITS_PER_WIDE_INT. We
1489 have to clear out any ones above the precision before doing
1490 popcount on this block. */
1491 count
= x
.precision
- x
.len
* HOST_BITS_PER_WIDE_INT
;
1492 unsigned int stop
= x
.len
;
1495 count
= popcount_hwi (x
.uhigh () << -count
);
1500 if (x
.sign_mask () >= 0)
1504 for (i
= 0; i
< stop
; ++i
)
1505 count
+= popcount_hwi (x
.val
[i
]);
1510 /* Set VAL to OP0 - OP1. If OVERFLOW is nonnull, record in *OVERFLOW
1511 whether the result overflows when OP0 and OP1 are treated as having
1512 signedness SGN. Return the number of blocks in VAL. */
1514 wi::sub_large (HOST_WIDE_INT
*val
, const HOST_WIDE_INT
*op0
,
1515 unsigned int op0len
, const HOST_WIDE_INT
*op1
,
1516 unsigned int op1len
, unsigned int prec
,
1517 signop sgn
, bool *overflow
)
1519 unsigned HOST_WIDE_INT o0
= 0;
1520 unsigned HOST_WIDE_INT o1
= 0;
1521 unsigned HOST_WIDE_INT x
= 0;
1522 /* We implement subtraction as an in place negate and add. Negation
1523 is just inversion and add 1, so we can do the add of 1 by just
1524 starting the borrow in of the first element at 1. */
1525 unsigned HOST_WIDE_INT borrow
= 0;
1526 unsigned HOST_WIDE_INT old_borrow
= 0;
1528 unsigned HOST_WIDE_INT mask0
, mask1
;
1531 unsigned int len
= MAX (op0len
, op1len
);
1532 mask0
= -top_bit_of (op0
, op0len
, prec
);
1533 mask1
= -top_bit_of (op1
, op1len
, prec
);
1535 /* Subtract all of the explicitly defined elements. */
1536 for (i
= 0; i
< len
; i
++)
1538 o0
= i
< op0len
? (unsigned HOST_WIDE_INT
)op0
[i
] : mask0
;
1539 o1
= i
< op1len
? (unsigned HOST_WIDE_INT
)op1
[i
] : mask1
;
1540 x
= o0
- o1
- borrow
;
1542 old_borrow
= borrow
;
1543 borrow
= borrow
== 0 ? o0
< o1
: o0
<= o1
;
1546 if (len
* HOST_BITS_PER_WIDE_INT
< prec
)
1548 val
[len
] = mask0
- mask1
- borrow
;
1555 unsigned int shift
= -prec
% HOST_BITS_PER_WIDE_INT
;
1558 unsigned HOST_WIDE_INT x
= (o0
^ o1
) & (val
[len
- 1] ^ o0
);
1559 *overflow
= (HOST_WIDE_INT
) (x
<< shift
) < 0;
1563 /* Put the MSB of X and O0 and in the top of the HWI. */
1567 *overflow
= (x
>= o0
);
1569 *overflow
= (x
> o0
);
1573 return canonize (val
, len
, prec
);
1581 /* Compute B_QUOTIENT and B_REMAINDER from B_DIVIDEND/B_DIVISOR. The
1582 algorithm is a small modification of the algorithm in Hacker's
1583 Delight by Warren, which itself is a small modification of Knuth's
1584 algorithm. M is the number of significant elements of U however
1585 there needs to be at least one extra element of B_DIVIDEND
1586 allocated, N is the number of elements of B_DIVISOR. */
1588 divmod_internal_2 (unsigned HOST_HALF_WIDE_INT
*b_quotient
,
1589 unsigned HOST_HALF_WIDE_INT
*b_remainder
,
1590 unsigned HOST_HALF_WIDE_INT
*b_dividend
,
1591 unsigned HOST_HALF_WIDE_INT
*b_divisor
,
1594 /* The "digits" are a HOST_HALF_WIDE_INT which the size of half of a
1595 HOST_WIDE_INT and stored in the lower bits of each word. This
1596 algorithm should work properly on both 32 and 64 bit
1598 unsigned HOST_WIDE_INT b
1599 = (unsigned HOST_WIDE_INT
)1 << HOST_BITS_PER_HALF_WIDE_INT
;
1600 unsigned HOST_WIDE_INT qhat
; /* Estimate of quotient digit. */
1601 unsigned HOST_WIDE_INT rhat
; /* A remainder. */
1602 unsigned HOST_WIDE_INT p
; /* Product of two digits. */
1606 /* Single digit divisor. */
1610 for (j
= m
- 1; j
>= 0; j
--)
1612 b_quotient
[j
] = (k
* b
+ b_dividend
[j
])/b_divisor
[0];
1613 k
= ((k
* b
+ b_dividend
[j
])
1614 - ((unsigned HOST_WIDE_INT
)b_quotient
[j
]
1615 * (unsigned HOST_WIDE_INT
)b_divisor
[0]));
1621 s
= clz_hwi (b_divisor
[n
-1]) - HOST_BITS_PER_HALF_WIDE_INT
; /* CHECK clz */
1625 /* Normalize B_DIVIDEND and B_DIVISOR. Unlike the published
1626 algorithm, we can overwrite b_dividend and b_divisor, so we do
1628 for (i
= n
- 1; i
> 0; i
--)
1629 b_divisor
[i
] = (b_divisor
[i
] << s
)
1630 | (b_divisor
[i
-1] >> (HOST_BITS_PER_HALF_WIDE_INT
- s
));
1631 b_divisor
[0] = b_divisor
[0] << s
;
1633 b_dividend
[m
] = b_dividend
[m
-1] >> (HOST_BITS_PER_HALF_WIDE_INT
- s
);
1634 for (i
= m
- 1; i
> 0; i
--)
1635 b_dividend
[i
] = (b_dividend
[i
] << s
)
1636 | (b_dividend
[i
-1] >> (HOST_BITS_PER_HALF_WIDE_INT
- s
));
1637 b_dividend
[0] = b_dividend
[0] << s
;
1641 for (j
= m
- n
; j
>= 0; j
--)
1643 qhat
= (b_dividend
[j
+n
] * b
+ b_dividend
[j
+n
-1]) / b_divisor
[n
-1];
1644 rhat
= (b_dividend
[j
+n
] * b
+ b_dividend
[j
+n
-1]) - qhat
* b_divisor
[n
-1];
1646 if (qhat
>= b
|| qhat
* b_divisor
[n
-2] > b
* rhat
+ b_dividend
[j
+n
-2])
1649 rhat
+= b_divisor
[n
-1];
1654 /* Multiply and subtract. */
1656 for (i
= 0; i
< n
; i
++)
1658 p
= qhat
* b_divisor
[i
];
1659 t
= b_dividend
[i
+j
] - k
- (p
& HALF_INT_MASK
);
1660 b_dividend
[i
+ j
] = t
;
1661 k
= ((p
>> HOST_BITS_PER_HALF_WIDE_INT
)
1662 - (t
>> HOST_BITS_PER_HALF_WIDE_INT
));
1664 t
= b_dividend
[j
+n
] - k
;
1665 b_dividend
[j
+n
] = t
;
1667 b_quotient
[j
] = qhat
;
1672 for (i
= 0; i
< n
; i
++)
1674 t
= (HOST_WIDE_INT
)b_dividend
[i
+j
] + b_divisor
[i
] + k
;
1675 b_dividend
[i
+j
] = t
;
1676 k
= t
>> HOST_BITS_PER_HALF_WIDE_INT
;
1678 b_dividend
[j
+n
] += k
;
1682 for (i
= 0; i
< n
; i
++)
1683 b_remainder
[i
] = (b_dividend
[i
] >> s
)
1684 | (b_dividend
[i
+1] << (HOST_BITS_PER_HALF_WIDE_INT
- s
));
1686 for (i
= 0; i
< n
; i
++)
1687 b_remainder
[i
] = b_dividend
[i
];
1691 /* Divide DIVIDEND by DIVISOR, which have signedness SGN, and truncate
1692 the result. If QUOTIENT is nonnull, store the value of the quotient
1693 there and return the number of blocks in it. The return value is
1694 not defined otherwise. If REMAINDER is nonnull, store the value
1695 of the remainder there and store the number of blocks in
1696 *REMAINDER_LEN. If OFLOW is not null, store in *OFLOW whether
1697 the division overflowed. */
1699 wi::divmod_internal (HOST_WIDE_INT
*quotient
, unsigned int *remainder_len
,
1700 HOST_WIDE_INT
*remainder
,
1701 const HOST_WIDE_INT
*dividend_val
,
1702 unsigned int dividend_len
, unsigned int dividend_prec
,
1703 const HOST_WIDE_INT
*divisor_val
, unsigned int divisor_len
,
1704 unsigned int divisor_prec
, signop sgn
,
1707 unsigned int dividend_blocks_needed
= 2 * BLOCKS_NEEDED (dividend_prec
);
1708 unsigned int divisor_blocks_needed
= 2 * BLOCKS_NEEDED (divisor_prec
);
1709 unsigned HOST_HALF_WIDE_INT
1710 b_quotient
[4 * MAX_BITSIZE_MODE_ANY_INT
/ HOST_BITS_PER_HALF_WIDE_INT
];
1711 unsigned HOST_HALF_WIDE_INT
1712 b_remainder
[4 * MAX_BITSIZE_MODE_ANY_INT
/ HOST_BITS_PER_HALF_WIDE_INT
];
1713 unsigned HOST_HALF_WIDE_INT
1714 b_dividend
[(4 * MAX_BITSIZE_MODE_ANY_INT
/ HOST_BITS_PER_HALF_WIDE_INT
) + 1];
1715 unsigned HOST_HALF_WIDE_INT
1716 b_divisor
[4 * MAX_BITSIZE_MODE_ANY_INT
/ HOST_BITS_PER_HALF_WIDE_INT
];
1718 bool dividend_neg
= false;
1719 bool divisor_neg
= false;
1720 bool overflow
= false;
1721 wide_int neg_dividend
, neg_divisor
;
1723 wide_int_ref dividend
= wi::storage_ref (dividend_val
, dividend_len
,
1725 wide_int_ref divisor
= wi::storage_ref (divisor_val
, divisor_len
,
1730 /* The smallest signed number / -1 causes overflow. The dividend_len
1731 check is for speed rather than correctness. */
1733 && dividend_len
== BLOCKS_NEEDED (dividend_prec
)
1735 && wi::only_sign_bit_p (dividend
))
1738 /* Handle the overflow cases. Viewed as unsigned value, the quotient of
1739 (signed min / -1) has the same representation as the orignal dividend.
1740 We have traditionally made division by zero act as division by one,
1741 so there too we use the original dividend. */
1752 for (unsigned int i
= 0; i
< dividend_len
; ++i
)
1753 quotient
[i
] = dividend_val
[i
];
1754 return dividend_len
;
1760 /* Do it on the host if you can. */
1762 && wi::fits_shwi_p (dividend
)
1763 && wi::fits_shwi_p (divisor
))
1765 HOST_WIDE_INT o0
= dividend
.to_shwi ();
1766 HOST_WIDE_INT o1
= divisor
.to_shwi ();
1768 if (o0
== HOST_WIDE_INT_MIN
&& o1
== -1)
1770 gcc_checking_assert (dividend_prec
> HOST_BITS_PER_WIDE_INT
);
1773 quotient
[0] = HOST_WIDE_INT_MIN
;
1786 quotient
[0] = o0
/ o1
;
1789 remainder
[0] = o0
% o1
;
1797 && wi::fits_uhwi_p (dividend
)
1798 && wi::fits_uhwi_p (divisor
))
1800 unsigned HOST_WIDE_INT o0
= dividend
.to_uhwi ();
1801 unsigned HOST_WIDE_INT o1
= divisor
.to_uhwi ();
1802 unsigned int quotient_len
= 1;
1806 quotient
[0] = o0
/ o1
;
1808 && (HOST_WIDE_INT
) o0
< 0
1809 && dividend_prec
> HOST_BITS_PER_WIDE_INT
)
1817 remainder
[0] = o0
% o1
;
1818 if ((HOST_WIDE_INT
) remainder
[0] < 0
1819 && dividend_prec
> HOST_BITS_PER_WIDE_INT
)
1827 return quotient_len
;
1830 /* Make the divisor and dividend positive and remember what we
1834 if (wi::neg_p (dividend
))
1836 neg_dividend
= -dividend
;
1837 dividend
= neg_dividend
;
1838 dividend_neg
= true;
1840 if (wi::neg_p (divisor
))
1842 neg_divisor
= -divisor
;
1843 divisor
= neg_divisor
;
1848 wi_unpack (b_dividend
, dividend
.get_val (), dividend
.get_len (),
1849 dividend_blocks_needed
, dividend_prec
, sgn
);
1850 wi_unpack (b_divisor
, divisor
.get_val (), divisor
.get_len (),
1851 divisor_blocks_needed
, divisor_prec
, sgn
);
1853 m
= dividend_blocks_needed
;
1855 while (m
> 1 && b_dividend
[m
- 1] == 0)
1858 n
= divisor_blocks_needed
;
1859 while (n
> 1 && b_divisor
[n
- 1] == 0)
1862 memset (b_quotient
, 0, sizeof (b_quotient
));
1864 divmod_internal_2 (b_quotient
, b_remainder
, b_dividend
, b_divisor
, m
, n
);
1866 unsigned int quotient_len
= 0;
1869 quotient_len
= wi_pack (quotient
, b_quotient
, m
, dividend_prec
);
1870 /* The quotient is neg if exactly one of the divisor or dividend is
1872 if (dividend_neg
!= divisor_neg
)
1873 quotient_len
= wi::sub_large (quotient
, zeros
, 1, quotient
,
1874 quotient_len
, dividend_prec
,
1880 *remainder_len
= wi_pack (remainder
, b_remainder
, n
, dividend_prec
);
1881 /* The remainder is always the same sign as the dividend. */
1883 *remainder_len
= wi::sub_large (remainder
, zeros
, 1, remainder
,
1884 *remainder_len
, dividend_prec
,
1888 return quotient_len
;
1892 * Shifting, rotating and extraction.
1895 /* Left shift XVAL by SHIFT and store the result in VAL. Return the
1896 number of blocks in VAL. Both XVAL and VAL have PRECISION bits. */
1898 wi::lshift_large (HOST_WIDE_INT
*val
, const HOST_WIDE_INT
*xval
,
1899 unsigned int xlen
, unsigned int precision
,
1902 /* Split the shift into a whole-block shift and a subblock shift. */
1903 unsigned int skip
= shift
/ HOST_BITS_PER_WIDE_INT
;
1904 unsigned int small_shift
= shift
% HOST_BITS_PER_WIDE_INT
;
1906 /* The whole-block shift fills with zeros. */
1907 unsigned int len
= BLOCKS_NEEDED (precision
);
1908 for (unsigned int i
= 0; i
< skip
; ++i
)
1911 /* It's easier to handle the simple block case specially. */
1912 if (small_shift
== 0)
1913 for (unsigned int i
= skip
; i
< len
; ++i
)
1914 val
[i
] = safe_uhwi (xval
, xlen
, i
- skip
);
1917 /* The first unfilled output block is a left shift of the first
1918 block in XVAL. The other output blocks contain bits from two
1919 consecutive input blocks. */
1920 unsigned HOST_WIDE_INT carry
= 0;
1921 for (unsigned int i
= skip
; i
< len
; ++i
)
1923 unsigned HOST_WIDE_INT x
= safe_uhwi (xval
, xlen
, i
- skip
);
1924 val
[i
] = (x
<< small_shift
) | carry
;
1925 carry
= x
>> (-small_shift
% HOST_BITS_PER_WIDE_INT
);
1928 return canonize (val
, len
, precision
);
1931 /* Right shift XVAL by SHIFT and store the result in VAL. Return the
1932 number of blocks in VAL. The input has XPRECISION bits and the
1933 output has XPRECISION - SHIFT bits. */
1935 rshift_large_common (HOST_WIDE_INT
*val
, const HOST_WIDE_INT
*xval
,
1936 unsigned int xlen
, unsigned int xprecision
,
1939 /* Split the shift into a whole-block shift and a subblock shift. */
1940 unsigned int skip
= shift
/ HOST_BITS_PER_WIDE_INT
;
1941 unsigned int small_shift
= shift
% HOST_BITS_PER_WIDE_INT
;
1943 /* Work out how many blocks are needed to store the significant bits
1944 (excluding the upper zeros or signs). */
1945 unsigned int len
= BLOCKS_NEEDED (xprecision
- shift
);
1947 /* It's easier to handle the simple block case specially. */
1948 if (small_shift
== 0)
1949 for (unsigned int i
= 0; i
< len
; ++i
)
1950 val
[i
] = safe_uhwi (xval
, xlen
, i
+ skip
);
1953 /* Each output block but the last is a combination of two input blocks.
1954 The last block is a right shift of the last block in XVAL. */
1955 unsigned HOST_WIDE_INT curr
= safe_uhwi (xval
, xlen
, skip
);
1956 for (unsigned int i
= 0; i
< len
; ++i
)
1958 val
[i
] = curr
>> small_shift
;
1959 curr
= safe_uhwi (xval
, xlen
, i
+ skip
+ 1);
1960 val
[i
] |= curr
<< (-small_shift
% HOST_BITS_PER_WIDE_INT
);
1966 /* Logically right shift XVAL by SHIFT and store the result in VAL.
1967 Return the number of blocks in VAL. XVAL has XPRECISION bits and
1968 VAL has PRECISION bits. */
1970 wi::lrshift_large (HOST_WIDE_INT
*val
, const HOST_WIDE_INT
*xval
,
1971 unsigned int xlen
, unsigned int xprecision
,
1972 unsigned int precision
, unsigned int shift
)
1974 unsigned int len
= rshift_large_common (val
, xval
, xlen
, xprecision
, shift
);
1976 /* The value we just created has precision XPRECISION - SHIFT.
1977 Zero-extend it to wider precisions. */
1978 if (precision
> xprecision
- shift
)
1980 unsigned int small_prec
= (xprecision
- shift
) % HOST_BITS_PER_WIDE_INT
;
1982 val
[len
- 1] = zext_hwi (val
[len
- 1], small_prec
);
1983 else if (val
[len
- 1] < 0)
1985 /* Add a new block with a zero. */
1990 return canonize (val
, len
, precision
);
1993 /* Arithmetically right shift XVAL by SHIFT and store the result in VAL.
1994 Return the number of blocks in VAL. XVAL has XPRECISION bits and
1995 VAL has PRECISION bits. */
1997 wi::arshift_large (HOST_WIDE_INT
*val
, const HOST_WIDE_INT
*xval
,
1998 unsigned int xlen
, unsigned int xprecision
,
1999 unsigned int precision
, unsigned int shift
)
2001 unsigned int len
= rshift_large_common (val
, xval
, xlen
, xprecision
, shift
);
2003 /* The value we just created has precision XPRECISION - SHIFT.
2004 Sign-extend it to wider types. */
2005 if (precision
> xprecision
- shift
)
2007 unsigned int small_prec
= (xprecision
- shift
) % HOST_BITS_PER_WIDE_INT
;
2009 val
[len
- 1] = sext_hwi (val
[len
- 1], small_prec
);
2011 return canonize (val
, len
, precision
);
2014 /* Return the number of leading (upper) zeros in X. */
2016 wi::clz (const wide_int_ref
&x
)
2018 /* Calculate how many bits there above the highest represented block. */
2019 int count
= x
.precision
- x
.len
* HOST_BITS_PER_WIDE_INT
;
2021 unsigned HOST_WIDE_INT high
= x
.uhigh ();
2023 /* The upper -COUNT bits of HIGH are not part of the value.
2025 high
= (high
<< -count
) >> -count
;
2026 else if (x
.sign_mask () < 0)
2027 /* The upper bit is set, so there are no leading zeros. */
2030 /* We don't need to look below HIGH. Either HIGH is nonzero,
2031 or the top bit of the block below is nonzero; clz_hwi is
2032 HOST_BITS_PER_WIDE_INT in the latter case. */
2033 return count
+ clz_hwi (high
);
2036 /* Return the number of redundant sign bits in X. (That is, the number
2037 of bits immediately below the sign bit that have the same value as
2040 wi::clrsb (const wide_int_ref
&x
)
2042 /* Calculate how many bits there above the highest represented block. */
2043 int count
= x
.precision
- x
.len
* HOST_BITS_PER_WIDE_INT
;
2045 unsigned HOST_WIDE_INT high
= x
.uhigh ();
2046 unsigned HOST_WIDE_INT mask
= -1;
2049 /* The upper -COUNT bits of HIGH are not part of the value.
2050 Clear them from both MASK and HIGH. */
2055 /* If the top bit is 1, count the number of leading 1s. If the top
2056 bit is zero, count the number of leading zeros. */
2057 if (high
> mask
/ 2)
2060 /* There are no sign bits below the top block, so we don't need to look
2061 beyond HIGH. Note that clz_hwi is HOST_BITS_PER_WIDE_INT when
2063 return count
+ clz_hwi (high
) - 1;
2066 /* Return the number of trailing (lower) zeros in X. */
2068 wi::ctz (const wide_int_ref
&x
)
2070 if (x
.len
== 1 && x
.ulow () == 0)
2073 /* Having dealt with the zero case, there must be a block with a
2074 nonzero bit. We don't care about the bits above the first 1. */
2076 while (x
.val
[i
] == 0)
2078 return i
* HOST_BITS_PER_WIDE_INT
+ ctz_hwi (x
.val
[i
]);
2081 /* If X is an exact power of 2, return the base-2 logarithm, otherwise
2084 wi::exact_log2 (const wide_int_ref
&x
)
2086 /* Reject cases where there are implicit -1 blocks above HIGH. */
2087 if (x
.len
* HOST_BITS_PER_WIDE_INT
< x
.precision
&& x
.sign_mask () < 0)
2090 /* Set CRUX to the index of the entry that should be nonzero.
2091 If the top block is zero then the next lowest block (if any)
2092 must have the high bit set. */
2093 unsigned int crux
= x
.len
- 1;
2094 if (crux
> 0 && x
.val
[crux
] == 0)
2097 /* Check that all lower blocks are zero. */
2098 for (unsigned int i
= 0; i
< crux
; ++i
)
2102 /* Get a zero-extended form of block CRUX. */
2103 unsigned HOST_WIDE_INT hwi
= x
.val
[crux
];
2104 if ((crux
+ 1) * HOST_BITS_PER_WIDE_INT
> x
.precision
)
2105 hwi
= zext_hwi (hwi
, x
.precision
% HOST_BITS_PER_WIDE_INT
);
2107 /* Now it's down to whether HWI is a power of 2. */
2108 int res
= ::exact_log2 (hwi
);
2110 res
+= crux
* HOST_BITS_PER_WIDE_INT
;
2114 /* Return the base-2 logarithm of X, rounding down. Return -1 if X is 0. */
2116 wi::floor_log2 (const wide_int_ref
&x
)
2118 return x
.precision
- 1 - clz (x
);
2121 /* Return the index of the first (lowest) set bit in X, counting from 1.
2122 Return 0 if X is 0. */
2124 wi::ffs (const wide_int_ref
&x
)
2126 return eq_p (x
, 0) ? 0 : ctz (x
) + 1;
2129 /* Return true if sign-extending X to have precision PRECISION would give
2130 the minimum signed value at that precision. */
2132 wi::only_sign_bit_p (const wide_int_ref
&x
, unsigned int precision
)
2134 return ctz (x
) + 1 == int (precision
);
2137 /* Return true if X represents the minimum signed value. */
2139 wi::only_sign_bit_p (const wide_int_ref
&x
)
2141 return only_sign_bit_p (x
, x
.precision
);
2145 * Private utilities.
2148 void gt_ggc_mx (widest_int
*) { }
2149 void gt_pch_nx (widest_int
*, void (*) (void *, void *), void *) { }
2150 void gt_pch_nx (widest_int
*) { }
2152 template void wide_int::dump () const;
2153 template void generic_wide_int
<wide_int_ref_storage
<false> >::dump () const;
2154 template void generic_wide_int
<wide_int_ref_storage
<true> >::dump () const;
2155 template void offset_int::dump () const;
2156 template void widest_int::dump () const;