1 /* Operations with very long integers.
2 Copyright (C) 2012-2022 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"
29 #define HOST_BITS_PER_HALF_WIDE_INT 32
30 #if HOST_BITS_PER_HALF_WIDE_INT == HOST_BITS_PER_LONG
31 # define HOST_HALF_WIDE_INT long
32 #elif HOST_BITS_PER_HALF_WIDE_INT == HOST_BITS_PER_INT
33 # define HOST_HALF_WIDE_INT int
35 #error Please add support for HOST_HALF_WIDE_INT
38 #define W_TYPE_SIZE HOST_BITS_PER_WIDE_INT
39 /* Do not include longlong.h when compiler is clang-based. See PR61146. */
40 #if GCC_VERSION >= 3000 && (W_TYPE_SIZE == 32 || defined (__SIZEOF_INT128__)) && !defined(__clang__)
41 typedef unsigned HOST_HALF_WIDE_INT UHWtype;
42 typedef unsigned HOST_WIDE_INT UWtype;
43 typedef unsigned int UQItype __attribute__ ((mode (QI)));
44 typedef unsigned int USItype __attribute__ ((mode (SI)));
45 typedef unsigned int UDItype __attribute__ ((mode (DI)));
47 typedef unsigned int UDWtype __attribute__ ((mode (DI)));
49 typedef unsigned int UDWtype __attribute__ ((mode (TI)));
54 static const HOST_WIDE_INT zeros[WIDE_INT_MAX_ELTS] = {};
60 /* Quantities to deal with values that hold half of a wide int. Used
61 in multiply and divide. */
62 #define HALF_INT_MASK ((HOST_WIDE_INT_1 << HOST_BITS_PER_HALF_WIDE_INT) - 1)
64 #define BLOCK_OF(TARGET) ((TARGET) / HOST_BITS_PER_WIDE_INT)
65 #define BLOCKS_NEEDED(PREC) \
66 (PREC ? (((PREC) + HOST_BITS_PER_WIDE_INT - 1) / HOST_BITS_PER_WIDE_INT) : 1)
67 #define SIGN_MASK(X) ((HOST_WIDE_INT) (X) < 0 ? -1 : 0)
69 /* Return the value a VAL[I] if I < LEN, otherwise, return 0 or -1
70 based on the top existing bit of VAL. */
72 static unsigned HOST_WIDE_INT
73 safe_uhwi (const HOST_WIDE_INT *val, unsigned int len, unsigned int i)
75 return i < len ? val[i] : val[len - 1] < 0 ? HOST_WIDE_INT_M1 : 0;
78 /* Convert the integer in VAL to canonical form, returning its new length.
79 LEN is the number of blocks currently in VAL and PRECISION is the number
80 of bits in the integer it represents.
82 This function only changes the representation, not the value. */
84 canonize (HOST_WIDE_INT *val, unsigned int len, unsigned int precision)
86 unsigned int blocks_needed = BLOCKS_NEEDED (precision);
90 if (len > blocks_needed)
97 if (len * HOST_BITS_PER_WIDE_INT > precision)
98 val[len - 1] = top = sext_hwi (top, precision % HOST_BITS_PER_WIDE_INT);
99 if (top != 0 && top != (HOST_WIDE_INT)-1)
102 /* At this point we know that the top is either 0 or -1. Find the
103 first block that is not a copy of this. */
104 for (i = len - 2; i >= 0; i--)
106 HOST_WIDE_INT x = val[i];
109 if (SIGN_MASK (x) == top)
112 /* We need an extra block because the top bit block i does
113 not match the extension. */
118 /* The number is 0 or -1. */
122 /* VAL[0] is the unsigned result of an operation. Canonize it by adding
123 another 0 block if needed, and return number of blocks needed. */
125 static inline unsigned int
126 canonize_uhwi (HOST_WIDE_INT *val, unsigned int precision)
128 if (val[0] < 0 && precision > HOST_BITS_PER_WIDE_INT)
137 * Conversion routines in and out of wide_int.
140 /* Copy XLEN elements from XVAL to VAL. If NEED_CANON, canonize the
141 result for an integer with precision PRECISION. Return the length
142 of VAL (after any canonization. */
144 wi::from_array (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
145 unsigned int xlen, unsigned int precision, bool need_canon)
147 for (unsigned i = 0; i < xlen; i++)
149 return need_canon ? canonize (val, xlen, precision) : xlen;
152 /* Construct a wide int from a buffer of length LEN. BUFFER will be
153 read according to byte endianness and word endianness of the target.
154 Only the lower BUFFER_LEN bytes of the result are set; the remaining
155 high bytes are cleared. */
157 wi::from_buffer (const unsigned char *buffer, unsigned int buffer_len)
159 unsigned int precision = buffer_len * BITS_PER_UNIT;
160 wide_int result = wide_int::create (precision);
161 unsigned int words = buffer_len / UNITS_PER_WORD;
163 /* We have to clear all the bits ourself, as we merely or in values
165 unsigned int len = BLOCKS_NEEDED (precision);
166 HOST_WIDE_INT *val = result.write_val ();
167 for (unsigned int i = 0; i < len; ++i)
170 for (unsigned int byte = 0; byte < buffer_len; byte++)
174 unsigned int bitpos = byte * BITS_PER_UNIT;
175 unsigned HOST_WIDE_INT value;
177 if (buffer_len > UNITS_PER_WORD)
179 unsigned int word = byte / UNITS_PER_WORD;
181 if (WORDS_BIG_ENDIAN)
182 word = (words - 1) - word;
184 offset = word * UNITS_PER_WORD;
186 if (BYTES_BIG_ENDIAN)
187 offset += (UNITS_PER_WORD - 1) - (byte % UNITS_PER_WORD);
189 offset += byte % UNITS_PER_WORD;
192 offset = BYTES_BIG_ENDIAN ? (buffer_len - 1) - byte : byte;
194 value = (unsigned HOST_WIDE_INT) buffer[offset];
196 index = bitpos / HOST_BITS_PER_WIDE_INT;
197 val[index] |= value << (bitpos % HOST_BITS_PER_WIDE_INT);
200 result.set_len (canonize (val, len, precision));
205 /* Sets RESULT from X, the sign is taken according to SGN. */
207 wi::to_mpz (const wide_int_ref &x, mpz_t result, signop sgn)
209 int len = x.get_len ();
210 const HOST_WIDE_INT *v = x.get_val ();
211 int excess = len * HOST_BITS_PER_WIDE_INT - x.get_precision ();
213 if (wi::neg_p (x, sgn))
215 /* We use ones complement to avoid -x80..0 edge case that -
217 HOST_WIDE_INT *t = XALLOCAVEC (HOST_WIDE_INT, len);
218 for (int i = 0; i < len; i++)
221 t[len - 1] = (unsigned HOST_WIDE_INT) t[len - 1] << excess >> excess;
222 mpz_import (result, len, -1, sizeof (HOST_WIDE_INT), 0, 0, t);
223 mpz_com (result, result);
227 HOST_WIDE_INT *t = XALLOCAVEC (HOST_WIDE_INT, len);
228 for (int i = 0; i < len - 1; i++)
230 t[len - 1] = (unsigned HOST_WIDE_INT) v[len - 1] << excess >> excess;
231 mpz_import (result, len, -1, sizeof (HOST_WIDE_INT), 0, 0, t);
233 else if (excess < 0 && wi::neg_p (x))
236 = (-excess + HOST_BITS_PER_WIDE_INT - 1) / HOST_BITS_PER_WIDE_INT;
237 HOST_WIDE_INT *t = XALLOCAVEC (HOST_WIDE_INT, len + extra);
238 for (int i = 0; i < len; i++)
240 for (int i = 0; i < extra; i++)
242 excess = (-excess) % HOST_BITS_PER_WIDE_INT;
244 t[len + extra - 1] = (HOST_WIDE_INT_1U << excess) - 1;
245 mpz_import (result, len + extra, -1, sizeof (HOST_WIDE_INT), 0, 0, t);
248 mpz_import (result, len, -1, sizeof (HOST_WIDE_INT), 0, 0, v);
251 /* Returns X converted to TYPE. If WRAP is true, then out-of-range
252 values of VAL will be wrapped; otherwise, they will be set to the
253 appropriate minimum or maximum TYPE bound. */
255 wi::from_mpz (const_tree type, mpz_t x, bool wrap)
258 unsigned int prec = TYPE_PRECISION (type);
259 wide_int res = wide_int::create (prec);
267 get_type_static_bounds (type, min, max);
269 if (mpz_cmp (x, min) < 0)
271 else if (mpz_cmp (x, max) > 0)
278 /* Determine the number of unsigned HOST_WIDE_INTs that are required
279 for representing the absolute value. The code to calculate count is
280 extracted from the GMP manual, section "Integer Import and Export":
281 http://gmplib.org/manual/Integer-Import-and-Export.html */
282 numb = CHAR_BIT * sizeof (HOST_WIDE_INT);
283 count = (mpz_sizeinbase (x, 2) + numb - 1) / numb;
284 HOST_WIDE_INT *val = res.write_val ();
285 /* Read the absolute value.
287 Write directly to the wide_int storage if possible, otherwise leave
288 GMP to allocate the memory for us. It might be slightly more efficient
289 to use mpz_tdiv_r_2exp for the latter case, but the situation is
290 pathological and it seems safer to operate on the original mpz value
292 void *valres = mpz_export (count <= WIDE_INT_MAX_ELTS ? val : 0,
293 &count, -1, sizeof (HOST_WIDE_INT), 0, 0, x);
299 count = MIN (count, BLOCKS_NEEDED (prec));
302 memcpy (val, valres, count * sizeof (HOST_WIDE_INT));
305 /* Zero-extend the absolute value to PREC bits. */
306 if (count < BLOCKS_NEEDED (prec) && val[count - 1] < 0)
309 count = canonize (val, count, prec);
319 * Largest and smallest values in a mode.
322 /* Return the largest SGNed number that is representable in PRECISION bits.
324 TODO: There is still code from the double_int era that trys to
325 make up for the fact that double int's could not represent the
326 min and max values of all types. This code should be removed
327 because the min and max values can always be represented in
328 wide_ints and int-csts. */
330 wi::max_value (unsigned int precision, signop sgn)
332 gcc_checking_assert (precision != 0);
334 /* The unsigned max is just all ones. */
335 return shwi (-1, precision);
337 /* The signed max is all ones except the top bit. This must be
338 explicitly represented. */
339 return mask (precision - 1, false, precision);
342 /* Return the largest SGNed number that is representable in PRECISION bits. */
344 wi::min_value (unsigned int precision, signop sgn)
346 gcc_checking_assert (precision != 0);
348 return uhwi (0, precision);
350 /* The signed min is all zeros except the top bit. This must be
351 explicitly represented. */
352 return wi::set_bit_in_zero (precision - 1, precision);
359 /* Convert the number represented by XVAL, XLEN and XPRECISION, which has
360 signedness SGN, to an integer that has PRECISION bits. Store the blocks
361 in VAL and return the number of blocks used.
363 This function can handle both extension (PRECISION > XPRECISION)
364 and truncation (PRECISION < XPRECISION). */
366 wi::force_to_size (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
367 unsigned int xlen, unsigned int xprecision,
368 unsigned int precision, signop sgn)
370 unsigned int blocks_needed = BLOCKS_NEEDED (precision);
371 unsigned int len = blocks_needed < xlen ? blocks_needed : xlen;
372 for (unsigned i = 0; i < len; i++)
375 if (precision > xprecision)
377 unsigned int small_xprecision = xprecision % HOST_BITS_PER_WIDE_INT;
382 if (small_xprecision && len == BLOCKS_NEEDED (xprecision))
383 val[len - 1] = zext_hwi (val[len - 1], small_xprecision);
384 else if (val[len - 1] < 0)
386 while (len < BLOCKS_NEEDED (xprecision))
388 if (small_xprecision)
389 val[len - 1] = zext_hwi (val[len - 1], small_xprecision);
396 if (small_xprecision && len == BLOCKS_NEEDED (xprecision))
397 val[len - 1] = sext_hwi (val[len - 1], small_xprecision);
400 len = canonize (val, len, precision);
405 /* This function hides the fact that we cannot rely on the bits beyond
406 the precision. This issue comes up in the relational comparisions
407 where we do allow comparisons of values of different precisions. */
408 static inline HOST_WIDE_INT
409 selt (const HOST_WIDE_INT *a, unsigned int len,
410 unsigned int blocks_needed, unsigned int small_prec,
411 unsigned int index, signop sgn)
416 else if (index < blocks_needed || sgn == SIGNED)
417 /* Signed or within the precision. */
418 val = SIGN_MASK (a[len - 1]);
420 /* Unsigned extension beyond the precision. */
423 if (small_prec && index == blocks_needed - 1)
424 return (sgn == SIGNED
425 ? sext_hwi (val, small_prec)
426 : zext_hwi (val, small_prec));
431 /* Find the highest bit represented in a wide int. This will in
432 general have the same value as the sign bit. */
433 static inline HOST_WIDE_INT
434 top_bit_of (const HOST_WIDE_INT *a, unsigned int len, unsigned int prec)
436 int excess = len * HOST_BITS_PER_WIDE_INT - prec;
437 unsigned HOST_WIDE_INT val = a[len - 1];
440 return val >> (HOST_BITS_PER_WIDE_INT - 1);
444 * Comparisons, note that only equality is an operator. The other
445 * comparisons cannot be operators since they are inherently signed or
446 * unsigned and C++ has no such operators.
449 /* Return true if OP0 == OP1. */
451 wi::eq_p_large (const HOST_WIDE_INT *op0, unsigned int op0len,
452 const HOST_WIDE_INT *op1, unsigned int op1len,
456 unsigned int small_prec = prec & (HOST_BITS_PER_WIDE_INT - 1);
458 if (op0len != op1len)
461 if (op0len == BLOCKS_NEEDED (prec) && small_prec)
463 /* It does not matter if we zext or sext here, we just have to
464 do both the same way. */
465 if (zext_hwi (op0 [l0], small_prec) != zext_hwi (op1 [l0], small_prec))
471 if (op0[l0] != op1[l0])
479 /* Return true if OP0 < OP1 using signed comparisons. */
481 wi::lts_p_large (const HOST_WIDE_INT *op0, unsigned int op0len,
482 unsigned int precision,
483 const HOST_WIDE_INT *op1, unsigned int op1len)
485 HOST_WIDE_INT s0, s1;
486 unsigned HOST_WIDE_INT u0, u1;
487 unsigned int blocks_needed = BLOCKS_NEEDED (precision);
488 unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
489 int l = MAX (op0len - 1, op1len - 1);
491 /* Only the top block is compared as signed. The rest are unsigned
493 s0 = selt (op0, op0len, blocks_needed, small_prec, l, SIGNED);
494 s1 = selt (op1, op1len, blocks_needed, small_prec, l, SIGNED);
503 u0 = selt (op0, op0len, blocks_needed, small_prec, l, SIGNED);
504 u1 = selt (op1, op1len, blocks_needed, small_prec, l, SIGNED);
516 /* Returns -1 if OP0 < OP1, 0 if OP0 == OP1 and 1 if OP0 > OP1 using
519 wi::cmps_large (const HOST_WIDE_INT *op0, unsigned int op0len,
520 unsigned int precision,
521 const HOST_WIDE_INT *op1, unsigned int op1len)
523 HOST_WIDE_INT s0, s1;
524 unsigned HOST_WIDE_INT u0, u1;
525 unsigned int blocks_needed = BLOCKS_NEEDED (precision);
526 unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
527 int l = MAX (op0len - 1, op1len - 1);
529 /* Only the top block is compared as signed. The rest are unsigned
531 s0 = selt (op0, op0len, blocks_needed, small_prec, l, SIGNED);
532 s1 = selt (op1, op1len, blocks_needed, small_prec, l, SIGNED);
541 u0 = selt (op0, op0len, blocks_needed, small_prec, l, SIGNED);
542 u1 = selt (op1, op1len, blocks_needed, small_prec, l, SIGNED);
554 /* Return true if OP0 < OP1 using unsigned comparisons. */
556 wi::ltu_p_large (const HOST_WIDE_INT *op0, unsigned int op0len,
557 unsigned int precision,
558 const HOST_WIDE_INT *op1, unsigned int op1len)
560 unsigned HOST_WIDE_INT x0;
561 unsigned HOST_WIDE_INT x1;
562 unsigned int blocks_needed = BLOCKS_NEEDED (precision);
563 unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
564 int l = MAX (op0len - 1, op1len - 1);
568 x0 = selt (op0, op0len, blocks_needed, small_prec, l, UNSIGNED);
569 x1 = selt (op1, op1len, blocks_needed, small_prec, l, UNSIGNED);
580 /* Returns -1 if OP0 < OP1, 0 if OP0 == OP1 and 1 if OP0 > OP1 using
581 unsigned compares. */
583 wi::cmpu_large (const HOST_WIDE_INT *op0, unsigned int op0len,
584 unsigned int precision,
585 const HOST_WIDE_INT *op1, unsigned int op1len)
587 unsigned HOST_WIDE_INT x0;
588 unsigned HOST_WIDE_INT x1;
589 unsigned int blocks_needed = BLOCKS_NEEDED (precision);
590 unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
591 int l = MAX (op0len - 1, op1len - 1);
595 x0 = selt (op0, op0len, blocks_needed, small_prec, l, UNSIGNED);
596 x1 = selt (op1, op1len, blocks_needed, small_prec, l, UNSIGNED);
611 /* Sign-extend the number represented by XVAL and XLEN into VAL,
612 starting at OFFSET. Return the number of blocks in VAL. Both XVAL
613 and VAL have PRECISION bits. */
615 wi::sext_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
616 unsigned int xlen, unsigned int precision, unsigned int offset)
618 unsigned int len = offset / HOST_BITS_PER_WIDE_INT;
619 /* Extending beyond the precision is a no-op. If we have only stored
620 OFFSET bits or fewer, the rest are already signs. */
621 if (offset >= precision || len >= xlen)
623 for (unsigned i = 0; i < xlen; ++i)
627 unsigned int suboffset = offset % HOST_BITS_PER_WIDE_INT;
628 for (unsigned int i = 0; i < len; i++)
632 val[len] = sext_hwi (xval[len], suboffset);
635 return canonize (val, len, precision);
638 /* Zero-extend the number represented by XVAL and XLEN into VAL,
639 starting at OFFSET. Return the number of blocks in VAL. Both XVAL
640 and VAL have PRECISION bits. */
642 wi::zext_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
643 unsigned int xlen, unsigned int precision, unsigned int offset)
645 unsigned int len = offset / HOST_BITS_PER_WIDE_INT;
646 /* Extending beyond the precision is a no-op. If we have only stored
647 OFFSET bits or fewer, and the upper stored bit is zero, then there
649 if (offset >= precision || (len >= xlen && xval[xlen - 1] >= 0))
651 for (unsigned i = 0; i < xlen; ++i)
655 unsigned int suboffset = offset % HOST_BITS_PER_WIDE_INT;
656 for (unsigned int i = 0; i < len; i++)
657 val[i] = i < xlen ? xval[i] : -1;
659 val[len] = zext_hwi (len < xlen ? xval[len] : -1, suboffset);
662 return canonize (val, len + 1, precision);
666 * Masking, inserting, shifting, rotating.
669 /* Insert WIDTH bits from Y into X starting at START. */
671 wi::insert (const wide_int &x, const wide_int &y, unsigned int start,
678 unsigned int precision = x.get_precision ();
679 if (start >= precision)
682 gcc_checking_assert (precision >= width);
684 if (start + width >= precision)
685 width = precision - start;
687 mask = wi::shifted_mask (start, width, false, precision);
688 tmp = wi::lshift (wide_int::from (y, precision, UNSIGNED), start);
691 tmp = wi::bit_and_not (x, mask);
692 result = result | tmp;
697 /* Copy the number represented by XVAL and XLEN into VAL, setting bit BIT.
698 Return the number of blocks in VAL. Both XVAL and VAL have PRECISION
701 wi::set_bit_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
702 unsigned int xlen, unsigned int precision, unsigned int bit)
704 unsigned int block = bit / HOST_BITS_PER_WIDE_INT;
705 unsigned int subbit = bit % HOST_BITS_PER_WIDE_INT;
707 if (block + 1 >= xlen)
709 /* The operation either affects the last current block or needs
711 unsigned int len = block + 1;
712 for (unsigned int i = 0; i < len; i++)
713 val[i] = safe_uhwi (xval, xlen, i);
714 val[block] |= HOST_WIDE_INT_1U << subbit;
716 /* If the bit we just set is at the msb of the block, make sure
717 that any higher bits are zeros. */
718 if (bit + 1 < precision && subbit == HOST_BITS_PER_WIDE_INT - 1)
723 return canonize (val, len, precision);
727 for (unsigned int i = 0; i < xlen; i++)
729 val[block] |= HOST_WIDE_INT_1U << subbit;
730 return canonize (val, xlen, precision);
736 wide_int_storage::bswap () const
738 wide_int result = wide_int::create (precision);
740 unsigned int len = BLOCKS_NEEDED (precision);
741 unsigned int xlen = get_len ();
742 const HOST_WIDE_INT *xval = get_val ();
743 HOST_WIDE_INT *val = result.write_val ();
745 /* This is not a well defined operation if the precision is not a
747 gcc_assert ((precision & 0x7) == 0);
749 for (i = 0; i < len; i++)
752 /* Only swap the bytes that are not the padding. */
753 for (s = 0; s < precision; s += 8)
755 unsigned int d = precision - s - 8;
756 unsigned HOST_WIDE_INT byte;
758 unsigned int block = s / HOST_BITS_PER_WIDE_INT;
759 unsigned int offset = s & (HOST_BITS_PER_WIDE_INT - 1);
761 byte = (safe_uhwi (xval, xlen, block) >> offset) & 0xff;
763 block = d / HOST_BITS_PER_WIDE_INT;
764 offset = d & (HOST_BITS_PER_WIDE_INT - 1);
766 val[block] |= byte << offset;
769 result.set_len (canonize (val, len, precision));
773 /* Fill VAL with a mask where the lower WIDTH bits are ones and the bits
774 above that up to PREC are zeros. The result is inverted if NEGATE
775 is true. Return the number of blocks in VAL. */
777 wi::mask (HOST_WIDE_INT *val, unsigned int width, bool negate,
782 val[0] = negate ? 0 : -1;
787 val[0] = negate ? -1 : 0;
792 while (i < width / HOST_BITS_PER_WIDE_INT)
793 val[i++] = negate ? 0 : -1;
795 unsigned int shift = width & (HOST_BITS_PER_WIDE_INT - 1);
798 HOST_WIDE_INT last = (HOST_WIDE_INT_1U << shift) - 1;
799 val[i++] = negate ? ~last : last;
802 val[i++] = negate ? -1 : 0;
807 /* Fill VAL with a mask where the lower START bits are zeros, the next WIDTH
808 bits are ones, and the bits above that up to PREC are zeros. The result
809 is inverted if NEGATE is true. Return the number of blocks in VAL. */
811 wi::shifted_mask (HOST_WIDE_INT *val, unsigned int start, unsigned int width,
812 bool negate, unsigned int prec)
814 if (start >= prec || width == 0)
816 val[0] = negate ? -1 : 0;
820 if (width > prec - start)
821 width = prec - start;
822 unsigned int end = start + width;
825 while (i < start / HOST_BITS_PER_WIDE_INT)
826 val[i++] = negate ? -1 : 0;
828 unsigned int shift = start & (HOST_BITS_PER_WIDE_INT - 1);
831 HOST_WIDE_INT block = (HOST_WIDE_INT_1U << shift) - 1;
833 if (shift < HOST_BITS_PER_WIDE_INT)
836 block = (HOST_WIDE_INT_1U << shift) - block - 1;
837 val[i++] = negate ? ~block : block;
842 val[i++] = negate ? block : ~block;
848 val[i++] = negate ? 0 : -1;
852 while (i < end / HOST_BITS_PER_WIDE_INT)
854 val[i++] = negate ? 0 : -1;
856 shift = end & (HOST_BITS_PER_WIDE_INT - 1);
860 HOST_WIDE_INT block = (HOST_WIDE_INT_1U << shift) - 1;
861 val[i++] = negate ? ~block : block;
864 val[i++] = negate ? -1 : 0;
870 * logical operations.
873 /* Set VAL to OP0 & OP1. Return the number of blocks used. */
875 wi::and_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
876 unsigned int op0len, const HOST_WIDE_INT *op1,
877 unsigned int op1len, unsigned int prec)
881 bool need_canon = true;
883 unsigned int len = MAX (op0len, op1len);
886 HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec);
904 HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec);
920 val[l0] = op0[l0] & op1[l0];
925 len = canonize (val, len, prec);
930 /* Set VAL to OP0 & ~OP1. Return the number of blocks used. */
932 wi::and_not_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
933 unsigned int op0len, const HOST_WIDE_INT *op1,
934 unsigned int op1len, unsigned int prec)
939 bool need_canon = true;
941 unsigned int len = MAX (op0len, op1len);
944 HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec);
962 HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec);
978 val[l0] = op0[l0] & ~op1[l0];
983 len = canonize (val, len, prec);
988 /* Set VAL to OP0 | OP1. Return the number of blocks used. */
990 wi::or_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
991 unsigned int op0len, const HOST_WIDE_INT *op1,
992 unsigned int op1len, unsigned int prec)
997 bool need_canon = true;
999 unsigned int len = MAX (op0len, op1len);
1002 HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec);
1020 HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec);
1036 val[l0] = op0[l0] | op1[l0];
1041 len = canonize (val, len, prec);
1046 /* Set VAL to OP0 | ~OP1. Return the number of blocks used. */
1048 wi::or_not_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
1049 unsigned int op0len, const HOST_WIDE_INT *op1,
1050 unsigned int op1len, unsigned int prec)
1053 int l0 = op0len - 1;
1054 int l1 = op1len - 1;
1055 bool need_canon = true;
1057 unsigned int len = MAX (op0len, op1len);
1060 HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec);
1078 HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec);
1094 val[l0] = op0[l0] | ~op1[l0];
1099 len = canonize (val, len, prec);
1104 /* Set VAL to OP0 ^ OP1. Return the number of blocks used. */
1106 wi::xor_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
1107 unsigned int op0len, const HOST_WIDE_INT *op1,
1108 unsigned int op1len, unsigned int prec)
1111 int l0 = op0len - 1;
1112 int l1 = op1len - 1;
1114 unsigned int len = MAX (op0len, op1len);
1117 HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec);
1120 val[l0] = op0[l0] ^ op1mask;
1127 HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec);
1130 val[l1] = op0mask ^ op1[l1];
1137 val[l0] = op0[l0] ^ op1[l0];
1141 return canonize (val, len, prec);
1148 /* Set VAL to OP0 + OP1. If OVERFLOW is nonnull, record in *OVERFLOW
1149 whether the result overflows when OP0 and OP1 are treated as having
1150 signedness SGN. Return the number of blocks in VAL. */
1152 wi::add_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
1153 unsigned int op0len, const HOST_WIDE_INT *op1,
1154 unsigned int op1len, unsigned int prec,
1155 signop sgn, wi::overflow_type *overflow)
1157 unsigned HOST_WIDE_INT o0 = 0;
1158 unsigned HOST_WIDE_INT o1 = 0;
1159 unsigned HOST_WIDE_INT x = 0;
1160 unsigned HOST_WIDE_INT carry = 0;
1161 unsigned HOST_WIDE_INT old_carry = 0;
1162 unsigned HOST_WIDE_INT mask0, mask1;
1165 unsigned int len = MAX (op0len, op1len);
1166 mask0 = -top_bit_of (op0, op0len, prec);
1167 mask1 = -top_bit_of (op1, op1len, prec);
1168 /* Add all of the explicitly defined elements. */
1170 for (i = 0; i < len; i++)
1172 o0 = i < op0len ? (unsigned HOST_WIDE_INT) op0[i] : mask0;
1173 o1 = i < op1len ? (unsigned HOST_WIDE_INT) op1[i] : mask1;
1174 x = o0 + o1 + carry;
1177 carry = carry == 0 ? x < o0 : x <= o0;
1180 if (len * HOST_BITS_PER_WIDE_INT < prec)
1182 val[len] = mask0 + mask1 + carry;
1186 = (sgn == UNSIGNED && carry) ? wi::OVF_OVERFLOW : wi::OVF_NONE;
1190 unsigned int shift = -prec % HOST_BITS_PER_WIDE_INT;
1193 unsigned HOST_WIDE_INT x = (val[len - 1] ^ o0) & (val[len - 1] ^ o1);
1194 if ((HOST_WIDE_INT) (x << shift) < 0)
1196 if (o0 > (unsigned HOST_WIDE_INT) val[len - 1])
1197 *overflow = wi::OVF_UNDERFLOW;
1198 else if (o0 < (unsigned HOST_WIDE_INT) val[len - 1])
1199 *overflow = wi::OVF_OVERFLOW;
1201 *overflow = wi::OVF_NONE;
1204 *overflow = wi::OVF_NONE;
1208 /* Put the MSB of X and O0 and in the top of the HWI. */
1212 *overflow = (x <= o0) ? wi::OVF_OVERFLOW : wi::OVF_NONE;
1214 *overflow = (x < o0) ? wi::OVF_OVERFLOW : wi::OVF_NONE;
1218 return canonize (val, len, prec);
1221 /* Subroutines of the multiplication and division operations. Unpack
1222 the first IN_LEN HOST_WIDE_INTs in INPUT into 2 * IN_LEN
1223 HOST_HALF_WIDE_INTs of RESULT. The rest of RESULT is filled by
1224 uncompressing the top bit of INPUT[IN_LEN - 1]. */
1226 wi_unpack (unsigned HOST_HALF_WIDE_INT *result, const HOST_WIDE_INT *input,
1227 unsigned int in_len, unsigned int out_len,
1228 unsigned int prec, signop sgn)
1232 unsigned int small_prec = prec & (HOST_BITS_PER_WIDE_INT - 1);
1233 unsigned int blocks_needed = BLOCKS_NEEDED (prec);
1238 mask = -top_bit_of ((const HOST_WIDE_INT *) input, in_len, prec);
1239 mask &= HALF_INT_MASK;
1244 for (i = 0; i < blocks_needed - 1; i++)
1246 HOST_WIDE_INT x = safe_uhwi (input, in_len, i);
1248 result[j++] = x >> HOST_BITS_PER_HALF_WIDE_INT;
1251 HOST_WIDE_INT x = safe_uhwi (input, in_len, i);
1255 x = sext_hwi (x, small_prec);
1257 x = zext_hwi (x, small_prec);
1260 result[j++] = x >> HOST_BITS_PER_HALF_WIDE_INT;
1262 /* Smear the sign bit. */
1267 /* The inverse of wi_unpack. IN_LEN is the number of input
1268 blocks and PRECISION is the precision of the result. Return the
1269 number of blocks in the canonicalized result. */
1271 wi_pack (HOST_WIDE_INT *result,
1272 const unsigned HOST_HALF_WIDE_INT *input,
1273 unsigned int in_len, unsigned int precision)
1277 unsigned int blocks_needed = BLOCKS_NEEDED (precision);
1279 while (i + 1 < in_len)
1281 result[j++] = ((unsigned HOST_WIDE_INT) input[i]
1282 | ((unsigned HOST_WIDE_INT) input[i + 1]
1283 << HOST_BITS_PER_HALF_WIDE_INT));
1287 /* Handle the case where in_len is odd. For this we zero extend. */
1289 result[j++] = (unsigned HOST_WIDE_INT) input[i];
1290 else if (j < blocks_needed)
1292 return canonize (result, j, precision);
1295 /* Multiply Op1 by Op2. If HIGH is set, only the upper half of the
1298 If HIGH is not set, throw away the upper half after the check is
1299 made to see if it overflows. Unfortunately there is no better way
1300 to check for overflow than to do this. If OVERFLOW is nonnull,
1301 record in *OVERFLOW whether the result overflowed. SGN controls
1302 the signedness and is used to check overflow or if HIGH is set.
1304 NOTE: Overflow type for signed overflow is not yet implemented. */
1306 wi::mul_internal (HOST_WIDE_INT *val, const HOST_WIDE_INT *op1val,
1307 unsigned int op1len, const HOST_WIDE_INT *op2val,
1308 unsigned int op2len, unsigned int prec, signop sgn,
1309 wi::overflow_type *overflow, bool high)
1311 unsigned HOST_WIDE_INT o0, o1, k, t;
1314 unsigned int blocks_needed = BLOCKS_NEEDED (prec);
1315 unsigned int half_blocks_needed = blocks_needed * 2;
1316 /* The sizes here are scaled to support a 2x largest mode by 2x
1317 largest mode yielding a 4x largest mode result. This is what is
1320 unsigned HOST_HALF_WIDE_INT
1321 u[4 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_HALF_WIDE_INT];
1322 unsigned HOST_HALF_WIDE_INT
1323 v[4 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_HALF_WIDE_INT];
1324 /* The '2' in 'R' is because we are internally doing a full
1326 unsigned HOST_HALF_WIDE_INT
1327 r[2 * 4 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_HALF_WIDE_INT];
1328 HOST_WIDE_INT mask = ((HOST_WIDE_INT)1 << HOST_BITS_PER_HALF_WIDE_INT) - 1;
1330 /* If the top level routine did not really pass in an overflow, then
1331 just make sure that we never attempt to set it. */
1332 bool needs_overflow = (overflow != 0);
1334 *overflow = wi::OVF_NONE;
1336 wide_int_ref op1 = wi::storage_ref (op1val, op1len, prec);
1337 wide_int_ref op2 = wi::storage_ref (op2val, op2len, prec);
1339 /* This is a surprisingly common case, so do it first. */
1340 if (op1 == 0 || op2 == 0)
1347 if (sgn == UNSIGNED)
1349 /* If the inputs are single HWIs and the output has room for at
1350 least two HWIs, we can use umul_ppmm directly. */
1351 if (prec >= HOST_BITS_PER_WIDE_INT * 2
1352 && wi::fits_uhwi_p (op1)
1353 && wi::fits_uhwi_p (op2))
1355 /* This case never overflows. */
1361 umul_ppmm (val[1], val[0], op1.ulow (), op2.ulow ());
1362 if (val[1] < 0 && prec > HOST_BITS_PER_WIDE_INT * 2)
1367 return 1 + (val[1] != 0 || val[0] < 0);
1369 /* Likewise if the output is a full single HWI, except that the
1370 upper HWI of the result is only used for determining overflow.
1371 (We handle this case inline when overflow isn't needed.) */
1372 else if (prec == HOST_BITS_PER_WIDE_INT)
1374 unsigned HOST_WIDE_INT upper;
1375 umul_ppmm (upper, val[0], op1.ulow (), op2.ulow ());
1377 /* Unsigned overflow can only be +OVERFLOW. */
1378 *overflow = (upper != 0) ? wi::OVF_OVERFLOW : wi::OVF_NONE;
1386 /* Handle multiplications by 1. */
1391 val[0] = wi::neg_p (op2, sgn) ? -1 : 0;
1394 for (i = 0; i < op2len; i++)
1402 val[0] = wi::neg_p (op1, sgn) ? -1 : 0;
1405 for (i = 0; i < op1len; i++)
1410 /* If we need to check for overflow, we can only do half wide
1411 multiplies quickly because we need to look at the top bits to
1412 check for the overflow. */
1413 if ((high || needs_overflow)
1414 && (prec <= HOST_BITS_PER_HALF_WIDE_INT))
1416 unsigned HOST_WIDE_INT r;
1420 o0 = op1.to_shwi ();
1421 o1 = op2.to_shwi ();
1425 o0 = op1.to_uhwi ();
1426 o1 = op2.to_uhwi ();
1434 if ((HOST_WIDE_INT) r != sext_hwi (r, prec))
1435 /* FIXME: Signed overflow type is not implemented yet. */
1436 *overflow = OVF_UNKNOWN;
1440 if ((r >> prec) != 0)
1441 /* Unsigned overflow can only be +OVERFLOW. */
1442 *overflow = OVF_OVERFLOW;
1445 val[0] = high ? r >> prec : r;
1449 /* We do unsigned mul and then correct it. */
1450 wi_unpack (u, op1val, op1len, half_blocks_needed, prec, SIGNED);
1451 wi_unpack (v, op2val, op2len, half_blocks_needed, prec, SIGNED);
1453 /* The 2 is for a full mult. */
1454 memset (r, 0, half_blocks_needed * 2
1455 * HOST_BITS_PER_HALF_WIDE_INT / CHAR_BIT);
1457 for (j = 0; j < half_blocks_needed; j++)
1460 for (i = 0; i < half_blocks_needed; i++)
1462 t = ((unsigned HOST_WIDE_INT)u[i] * (unsigned HOST_WIDE_INT)v[j]
1464 r[i + j] = t & HALF_INT_MASK;
1465 k = t >> HOST_BITS_PER_HALF_WIDE_INT;
1467 r[j + half_blocks_needed] = k;
1470 /* We did unsigned math above. For signed we must adjust the
1471 product (assuming we need to see that). */
1472 if (sgn == SIGNED && (high || needs_overflow))
1474 unsigned HOST_WIDE_INT b;
1475 if (wi::neg_p (op1))
1478 for (i = 0; i < half_blocks_needed; i++)
1480 t = (unsigned HOST_WIDE_INT)r[i + half_blocks_needed]
1481 - (unsigned HOST_WIDE_INT)v[i] - b;
1482 r[i + half_blocks_needed] = t & HALF_INT_MASK;
1483 b = t >> (HOST_BITS_PER_WIDE_INT - 1);
1486 if (wi::neg_p (op2))
1489 for (i = 0; i < half_blocks_needed; i++)
1491 t = (unsigned HOST_WIDE_INT)r[i + half_blocks_needed]
1492 - (unsigned HOST_WIDE_INT)u[i] - b;
1493 r[i + half_blocks_needed] = t & HALF_INT_MASK;
1494 b = t >> (HOST_BITS_PER_WIDE_INT - 1);
1503 /* For unsigned, overflow is true if any of the top bits are set.
1504 For signed, overflow is true if any of the top bits are not equal
1506 if (sgn == UNSIGNED)
1510 top = r[(half_blocks_needed) - 1];
1511 top = SIGN_MASK (top << (HOST_BITS_PER_WIDE_INT / 2));
1515 for (i = half_blocks_needed; i < half_blocks_needed * 2; i++)
1516 if (((HOST_WIDE_INT)(r[i] & mask)) != top)
1517 /* FIXME: Signed overflow type is not implemented yet. */
1518 *overflow = (sgn == UNSIGNED) ? wi::OVF_OVERFLOW : wi::OVF_UNKNOWN;
1521 int r_offset = high ? half_blocks_needed : 0;
1522 return wi_pack (val, &r[r_offset], half_blocks_needed, prec);
1525 /* Compute the population count of X. */
1527 wi::popcount (const wide_int_ref &x)
1532 /* The high order block is special if it is the last block and the
1533 precision is not an even multiple of HOST_BITS_PER_WIDE_INT. We
1534 have to clear out any ones above the precision before doing
1535 popcount on this block. */
1536 count = x.precision - x.len * HOST_BITS_PER_WIDE_INT;
1537 unsigned int stop = x.len;
1540 count = popcount_hwi (x.uhigh () << -count);
1545 if (x.sign_mask () >= 0)
1549 for (i = 0; i < stop; ++i)
1550 count += popcount_hwi (x.val[i]);
1555 /* Set VAL to OP0 - OP1. If OVERFLOW is nonnull, record in *OVERFLOW
1556 whether the result overflows when OP0 and OP1 are treated as having
1557 signedness SGN. Return the number of blocks in VAL. */
1559 wi::sub_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
1560 unsigned int op0len, const HOST_WIDE_INT *op1,
1561 unsigned int op1len, unsigned int prec,
1562 signop sgn, wi::overflow_type *overflow)
1564 unsigned HOST_WIDE_INT o0 = 0;
1565 unsigned HOST_WIDE_INT o1 = 0;
1566 unsigned HOST_WIDE_INT x = 0;
1567 /* We implement subtraction as an in place negate and add. Negation
1568 is just inversion and add 1, so we can do the add of 1 by just
1569 starting the borrow in of the first element at 1. */
1570 unsigned HOST_WIDE_INT borrow = 0;
1571 unsigned HOST_WIDE_INT old_borrow = 0;
1573 unsigned HOST_WIDE_INT mask0, mask1;
1576 unsigned int len = MAX (op0len, op1len);
1577 mask0 = -top_bit_of (op0, op0len, prec);
1578 mask1 = -top_bit_of (op1, op1len, prec);
1580 /* Subtract all of the explicitly defined elements. */
1581 for (i = 0; i < len; i++)
1583 o0 = i < op0len ? (unsigned HOST_WIDE_INT)op0[i] : mask0;
1584 o1 = i < op1len ? (unsigned HOST_WIDE_INT)op1[i] : mask1;
1585 x = o0 - o1 - borrow;
1587 old_borrow = borrow;
1588 borrow = borrow == 0 ? o0 < o1 : o0 <= o1;
1591 if (len * HOST_BITS_PER_WIDE_INT < prec)
1593 val[len] = mask0 - mask1 - borrow;
1596 *overflow = (sgn == UNSIGNED && borrow) ? OVF_UNDERFLOW : OVF_NONE;
1600 unsigned int shift = -prec % HOST_BITS_PER_WIDE_INT;
1603 unsigned HOST_WIDE_INT x = (o0 ^ o1) & (val[len - 1] ^ o0);
1604 if ((HOST_WIDE_INT) (x << shift) < 0)
1607 *overflow = OVF_UNDERFLOW;
1609 *overflow = OVF_OVERFLOW;
1611 *overflow = OVF_NONE;
1614 *overflow = OVF_NONE;
1618 /* Put the MSB of X and O0 and in the top of the HWI. */
1622 *overflow = (x >= o0) ? OVF_UNDERFLOW : OVF_NONE;
1624 *overflow = (x > o0) ? OVF_UNDERFLOW : OVF_NONE;
1628 return canonize (val, len, prec);
1636 /* Compute B_QUOTIENT and B_REMAINDER from B_DIVIDEND/B_DIVISOR. The
1637 algorithm is a small modification of the algorithm in Hacker's
1638 Delight by Warren, which itself is a small modification of Knuth's
1639 algorithm. M is the number of significant elements of U however
1640 there needs to be at least one extra element of B_DIVIDEND
1641 allocated, N is the number of elements of B_DIVISOR. */
1643 divmod_internal_2 (unsigned HOST_HALF_WIDE_INT *b_quotient,
1644 unsigned HOST_HALF_WIDE_INT *b_remainder,
1645 unsigned HOST_HALF_WIDE_INT *b_dividend,
1646 unsigned HOST_HALF_WIDE_INT *b_divisor,
1649 /* The "digits" are a HOST_HALF_WIDE_INT which the size of half of a
1650 HOST_WIDE_INT and stored in the lower bits of each word. This
1651 algorithm should work properly on both 32 and 64 bit
1653 unsigned HOST_WIDE_INT b
1654 = (unsigned HOST_WIDE_INT)1 << HOST_BITS_PER_HALF_WIDE_INT;
1655 unsigned HOST_WIDE_INT qhat; /* Estimate of quotient digit. */
1656 unsigned HOST_WIDE_INT rhat; /* A remainder. */
1657 unsigned HOST_WIDE_INT p; /* Product of two digits. */
1661 /* Single digit divisor. */
1665 for (j = m - 1; j >= 0; j--)
1667 b_quotient[j] = (k * b + b_dividend[j])/b_divisor[0];
1668 k = ((k * b + b_dividend[j])
1669 - ((unsigned HOST_WIDE_INT)b_quotient[j]
1670 * (unsigned HOST_WIDE_INT)b_divisor[0]));
1676 s = clz_hwi (b_divisor[n-1]) - HOST_BITS_PER_HALF_WIDE_INT; /* CHECK clz */
1680 /* Normalize B_DIVIDEND and B_DIVISOR. Unlike the published
1681 algorithm, we can overwrite b_dividend and b_divisor, so we do
1683 for (i = n - 1; i > 0; i--)
1684 b_divisor[i] = (b_divisor[i] << s)
1685 | (b_divisor[i-1] >> (HOST_BITS_PER_HALF_WIDE_INT - s));
1686 b_divisor[0] = b_divisor[0] << s;
1688 b_dividend[m] = b_dividend[m-1] >> (HOST_BITS_PER_HALF_WIDE_INT - s);
1689 for (i = m - 1; i > 0; i--)
1690 b_dividend[i] = (b_dividend[i] << s)
1691 | (b_dividend[i-1] >> (HOST_BITS_PER_HALF_WIDE_INT - s));
1692 b_dividend[0] = b_dividend[0] << s;
1696 for (j = m - n; j >= 0; j--)
1698 qhat = (b_dividend[j+n] * b + b_dividend[j+n-1]) / b_divisor[n-1];
1699 rhat = (b_dividend[j+n] * b + b_dividend[j+n-1]) - qhat * b_divisor[n-1];
1701 if (qhat >= b || qhat * b_divisor[n-2] > b * rhat + b_dividend[j+n-2])
1704 rhat += b_divisor[n-1];
1709 /* Multiply and subtract. */
1711 for (i = 0; i < n; i++)
1713 p = qhat * b_divisor[i];
1714 t = b_dividend[i+j] - k - (p & HALF_INT_MASK);
1715 b_dividend[i + j] = t;
1716 k = ((p >> HOST_BITS_PER_HALF_WIDE_INT)
1717 - (t >> HOST_BITS_PER_HALF_WIDE_INT));
1719 t = b_dividend[j+n] - k;
1720 b_dividend[j+n] = t;
1722 b_quotient[j] = qhat;
1727 for (i = 0; i < n; i++)
1729 t = (HOST_WIDE_INT)b_dividend[i+j] + b_divisor[i] + k;
1730 b_dividend[i+j] = t;
1731 k = t >> HOST_BITS_PER_HALF_WIDE_INT;
1733 b_dividend[j+n] += k;
1737 for (i = 0; i < n; i++)
1738 b_remainder[i] = (b_dividend[i] >> s)
1739 | (b_dividend[i+1] << (HOST_BITS_PER_HALF_WIDE_INT - s));
1741 for (i = 0; i < n; i++)
1742 b_remainder[i] = b_dividend[i];
1746 /* Divide DIVIDEND by DIVISOR, which have signedness SGN, and truncate
1747 the result. If QUOTIENT is nonnull, store the value of the quotient
1748 there and return the number of blocks in it. The return value is
1749 not defined otherwise. If REMAINDER is nonnull, store the value
1750 of the remainder there and store the number of blocks in
1751 *REMAINDER_LEN. If OFLOW is not null, store in *OFLOW whether
1752 the division overflowed. */
1754 wi::divmod_internal (HOST_WIDE_INT *quotient, unsigned int *remainder_len,
1755 HOST_WIDE_INT *remainder,
1756 const HOST_WIDE_INT *dividend_val,
1757 unsigned int dividend_len, unsigned int dividend_prec,
1758 const HOST_WIDE_INT *divisor_val, unsigned int divisor_len,
1759 unsigned int divisor_prec, signop sgn,
1760 wi::overflow_type *oflow)
1762 unsigned int dividend_blocks_needed = 2 * BLOCKS_NEEDED (dividend_prec);
1763 unsigned int divisor_blocks_needed = 2 * BLOCKS_NEEDED (divisor_prec);
1764 unsigned HOST_HALF_WIDE_INT
1765 b_quotient[4 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_HALF_WIDE_INT];
1766 unsigned HOST_HALF_WIDE_INT
1767 b_remainder[4 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_HALF_WIDE_INT];
1768 unsigned HOST_HALF_WIDE_INT
1769 b_dividend[(4 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_HALF_WIDE_INT) + 1];
1770 unsigned HOST_HALF_WIDE_INT
1771 b_divisor[4 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_HALF_WIDE_INT];
1773 bool dividend_neg = false;
1774 bool divisor_neg = false;
1775 bool overflow = false;
1776 wide_int neg_dividend, neg_divisor;
1778 wide_int_ref dividend = wi::storage_ref (dividend_val, dividend_len,
1780 wide_int_ref divisor = wi::storage_ref (divisor_val, divisor_len,
1785 /* The smallest signed number / -1 causes overflow. The dividend_len
1786 check is for speed rather than correctness. */
1788 && dividend_len == BLOCKS_NEEDED (dividend_prec)
1790 && wi::only_sign_bit_p (dividend))
1793 /* Handle the overflow cases. Viewed as unsigned value, the quotient of
1794 (signed min / -1) has the same representation as the orignal dividend.
1795 We have traditionally made division by zero act as division by one,
1796 so there too we use the original dividend. */
1805 *oflow = OVF_OVERFLOW;
1807 for (unsigned int i = 0; i < dividend_len; ++i)
1808 quotient[i] = dividend_val[i];
1809 return dividend_len;
1815 /* Do it on the host if you can. */
1817 && wi::fits_shwi_p (dividend)
1818 && wi::fits_shwi_p (divisor))
1820 HOST_WIDE_INT o0 = dividend.to_shwi ();
1821 HOST_WIDE_INT o1 = divisor.to_shwi ();
1823 if (o0 == HOST_WIDE_INT_MIN && o1 == -1)
1825 gcc_checking_assert (dividend_prec > HOST_BITS_PER_WIDE_INT);
1828 quotient[0] = HOST_WIDE_INT_MIN;
1841 quotient[0] = o0 / o1;
1844 remainder[0] = o0 % o1;
1852 && wi::fits_uhwi_p (dividend)
1853 && wi::fits_uhwi_p (divisor))
1855 unsigned HOST_WIDE_INT o0 = dividend.to_uhwi ();
1856 unsigned HOST_WIDE_INT o1 = divisor.to_uhwi ();
1857 unsigned int quotient_len = 1;
1861 quotient[0] = o0 / o1;
1862 quotient_len = canonize_uhwi (quotient, dividend_prec);
1866 remainder[0] = o0 % o1;
1867 *remainder_len = canonize_uhwi (remainder, dividend_prec);
1869 return quotient_len;
1872 /* Make the divisor and dividend positive and remember what we
1876 if (wi::neg_p (dividend))
1878 neg_dividend = -dividend;
1879 dividend = neg_dividend;
1880 dividend_neg = true;
1882 if (wi::neg_p (divisor))
1884 neg_divisor = -divisor;
1885 divisor = neg_divisor;
1890 wi_unpack (b_dividend, dividend.get_val (), dividend.get_len (),
1891 dividend_blocks_needed, dividend_prec, sgn);
1892 wi_unpack (b_divisor, divisor.get_val (), divisor.get_len (),
1893 divisor_blocks_needed, divisor_prec, sgn);
1895 m = dividend_blocks_needed;
1897 while (m > 1 && b_dividend[m - 1] == 0)
1900 n = divisor_blocks_needed;
1901 while (n > 1 && b_divisor[n - 1] == 0)
1904 memset (b_quotient, 0, sizeof (b_quotient));
1906 divmod_internal_2 (b_quotient, b_remainder, b_dividend, b_divisor, m, n);
1908 unsigned int quotient_len = 0;
1911 quotient_len = wi_pack (quotient, b_quotient, m, dividend_prec);
1912 /* The quotient is neg if exactly one of the divisor or dividend is
1914 if (dividend_neg != divisor_neg)
1915 quotient_len = wi::sub_large (quotient, zeros, 1, quotient,
1916 quotient_len, dividend_prec,
1922 *remainder_len = wi_pack (remainder, b_remainder, n, dividend_prec);
1923 /* The remainder is always the same sign as the dividend. */
1925 *remainder_len = wi::sub_large (remainder, zeros, 1, remainder,
1926 *remainder_len, dividend_prec,
1930 return quotient_len;
1934 * Shifting, rotating and extraction.
1937 /* Left shift XVAL by SHIFT and store the result in VAL. Return the
1938 number of blocks in VAL. Both XVAL and VAL have PRECISION bits. */
1940 wi::lshift_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
1941 unsigned int xlen, unsigned int precision,
1944 /* Split the shift into a whole-block shift and a subblock shift. */
1945 unsigned int skip = shift / HOST_BITS_PER_WIDE_INT;
1946 unsigned int small_shift = shift % HOST_BITS_PER_WIDE_INT;
1948 /* The whole-block shift fills with zeros. */
1949 unsigned int len = BLOCKS_NEEDED (precision);
1950 for (unsigned int i = 0; i < skip; ++i)
1953 /* It's easier to handle the simple block case specially. */
1954 if (small_shift == 0)
1955 for (unsigned int i = skip; i < len; ++i)
1956 val[i] = safe_uhwi (xval, xlen, i - skip);
1959 /* The first unfilled output block is a left shift of the first
1960 block in XVAL. The other output blocks contain bits from two
1961 consecutive input blocks. */
1962 unsigned HOST_WIDE_INT carry = 0;
1963 for (unsigned int i = skip; i < len; ++i)
1965 unsigned HOST_WIDE_INT x = safe_uhwi (xval, xlen, i - skip);
1966 val[i] = (x << small_shift) | carry;
1967 carry = x >> (-small_shift % HOST_BITS_PER_WIDE_INT);
1970 return canonize (val, len, precision);
1973 /* Right shift XVAL by SHIFT and store the result in VAL. Return the
1974 number of blocks in VAL. The input has XPRECISION bits and the
1975 output has XPRECISION - SHIFT bits. */
1977 rshift_large_common (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
1978 unsigned int xlen, unsigned int xprecision,
1981 /* Split the shift into a whole-block shift and a subblock shift. */
1982 unsigned int skip = shift / HOST_BITS_PER_WIDE_INT;
1983 unsigned int small_shift = shift % HOST_BITS_PER_WIDE_INT;
1985 /* Work out how many blocks are needed to store the significant bits
1986 (excluding the upper zeros or signs). */
1987 unsigned int len = BLOCKS_NEEDED (xprecision - shift);
1989 /* It's easier to handle the simple block case specially. */
1990 if (small_shift == 0)
1991 for (unsigned int i = 0; i < len; ++i)
1992 val[i] = safe_uhwi (xval, xlen, i + skip);
1995 /* Each output block but the last is a combination of two input blocks.
1996 The last block is a right shift of the last block in XVAL. */
1997 unsigned HOST_WIDE_INT curr = safe_uhwi (xval, xlen, skip);
1998 for (unsigned int i = 0; i < len; ++i)
2000 val[i] = curr >> small_shift;
2001 curr = safe_uhwi (xval, xlen, i + skip + 1);
2002 val[i] |= curr << (-small_shift % HOST_BITS_PER_WIDE_INT);
2008 /* Logically right shift XVAL by SHIFT and store the result in VAL.
2009 Return the number of blocks in VAL. XVAL has XPRECISION bits and
2010 VAL has PRECISION bits. */
2012 wi::lrshift_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
2013 unsigned int xlen, unsigned int xprecision,
2014 unsigned int precision, unsigned int shift)
2016 unsigned int len = rshift_large_common (val, xval, xlen, xprecision, shift);
2018 /* The value we just created has precision XPRECISION - SHIFT.
2019 Zero-extend it to wider precisions. */
2020 if (precision > xprecision - shift)
2022 unsigned int small_prec = (xprecision - shift) % HOST_BITS_PER_WIDE_INT;
2024 val[len - 1] = zext_hwi (val[len - 1], small_prec);
2025 else if (val[len - 1] < 0)
2027 /* Add a new block with a zero. */
2032 return canonize (val, len, precision);
2035 /* Arithmetically right shift XVAL by SHIFT and store the result in VAL.
2036 Return the number of blocks in VAL. XVAL has XPRECISION bits and
2037 VAL has PRECISION bits. */
2039 wi::arshift_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
2040 unsigned int xlen, unsigned int xprecision,
2041 unsigned int precision, unsigned int shift)
2043 unsigned int len = rshift_large_common (val, xval, xlen, xprecision, shift);
2045 /* The value we just created has precision XPRECISION - SHIFT.
2046 Sign-extend it to wider types. */
2047 if (precision > xprecision - shift)
2049 unsigned int small_prec = (xprecision - shift) % HOST_BITS_PER_WIDE_INT;
2051 val[len - 1] = sext_hwi (val[len - 1], small_prec);
2053 return canonize (val, len, precision);
2056 /* Return the number of leading (upper) zeros in X. */
2058 wi::clz (const wide_int_ref &x)
2060 if (x.sign_mask () < 0)
2061 /* The upper bit is set, so there are no leading zeros. */
2064 /* Calculate how many bits there above the highest represented block. */
2065 int count = x.precision - x.len * HOST_BITS_PER_WIDE_INT;
2067 unsigned HOST_WIDE_INT high = x.uhigh ();
2069 /* The upper -COUNT bits of HIGH are not part of the value.
2071 high = (high << -count) >> -count;
2073 /* We don't need to look below HIGH. Either HIGH is nonzero,
2074 or the top bit of the block below is nonzero; clz_hwi is
2075 HOST_BITS_PER_WIDE_INT in the latter case. */
2076 return count + clz_hwi (high);
2079 /* Return the number of redundant sign bits in X. (That is, the number
2080 of bits immediately below the sign bit that have the same value as
2083 wi::clrsb (const wide_int_ref &x)
2085 /* Calculate how many bits there above the highest represented block. */
2086 int count = x.precision - x.len * HOST_BITS_PER_WIDE_INT;
2088 unsigned HOST_WIDE_INT high = x.uhigh ();
2089 unsigned HOST_WIDE_INT mask = -1;
2092 /* The upper -COUNT bits of HIGH are not part of the value.
2093 Clear them from both MASK and HIGH. */
2098 /* If the top bit is 1, count the number of leading 1s. If the top
2099 bit is zero, count the number of leading zeros. */
2100 if (high > mask / 2)
2103 /* There are no sign bits below the top block, so we don't need to look
2104 beyond HIGH. Note that clz_hwi is HOST_BITS_PER_WIDE_INT when
2106 return count + clz_hwi (high) - 1;
2109 /* Return the number of trailing (lower) zeros in X. */
2111 wi::ctz (const wide_int_ref &x)
2113 if (x.len == 1 && x.ulow () == 0)
2116 /* Having dealt with the zero case, there must be a block with a
2117 nonzero bit. We don't care about the bits above the first 1. */
2119 while (x.val[i] == 0)
2121 return i * HOST_BITS_PER_WIDE_INT + ctz_hwi (x.val[i]);
2124 /* If X is an exact power of 2, return the base-2 logarithm, otherwise
2127 wi::exact_log2 (const wide_int_ref &x)
2129 /* Reject cases where there are implicit -1 blocks above HIGH. */
2130 if (x.len * HOST_BITS_PER_WIDE_INT < x.precision && x.sign_mask () < 0)
2133 /* Set CRUX to the index of the entry that should be nonzero.
2134 If the top block is zero then the next lowest block (if any)
2135 must have the high bit set. */
2136 unsigned int crux = x.len - 1;
2137 if (crux > 0 && x.val[crux] == 0)
2140 /* Check that all lower blocks are zero. */
2141 for (unsigned int i = 0; i < crux; ++i)
2145 /* Get a zero-extended form of block CRUX. */
2146 unsigned HOST_WIDE_INT hwi = x.val[crux];
2147 if ((crux + 1) * HOST_BITS_PER_WIDE_INT > x.precision)
2148 hwi = zext_hwi (hwi, x.precision % HOST_BITS_PER_WIDE_INT);
2150 /* Now it's down to whether HWI is a power of 2. */
2151 int res = ::exact_log2 (hwi);
2153 res += crux * HOST_BITS_PER_WIDE_INT;
2157 /* Return the base-2 logarithm of X, rounding down. Return -1 if X is 0. */
2159 wi::floor_log2 (const wide_int_ref &x)
2161 return x.precision - 1 - clz (x);
2164 /* Return the index of the first (lowest) set bit in X, counting from 1.
2165 Return 0 if X is 0. */
2167 wi::ffs (const wide_int_ref &x)
2169 return eq_p (x, 0) ? 0 : ctz (x) + 1;
2172 /* Return true if sign-extending X to have precision PRECISION would give
2173 the minimum signed value at that precision. */
2175 wi::only_sign_bit_p (const wide_int_ref &x, unsigned int precision)
2177 return ctz (x) + 1 == int (precision);
2180 /* Return true if X represents the minimum signed value. */
2182 wi::only_sign_bit_p (const wide_int_ref &x)
2184 return only_sign_bit_p (x, x.precision);
2187 /* Return VAL if VAL has no bits set outside MASK. Otherwise round VAL
2188 down to the previous value that has no bits set outside MASK.
2189 This rounding wraps for signed values if VAL is negative and
2190 the top bit of MASK is clear.
2192 For example, round_down_for_mask (6, 0xf1) would give 1 and
2193 round_down_for_mask (24, 0xf1) would give 17. */
2196 wi::round_down_for_mask (const wide_int &val, const wide_int &mask)
2198 /* Get the bits in VAL that are outside the mask. */
2199 wide_int extra_bits = wi::bit_and_not (val, mask);
2200 if (extra_bits == 0)
2203 /* Get a mask that includes the top bit in EXTRA_BITS and is all 1s
2205 unsigned int precision = val.get_precision ();
2206 wide_int lower_mask = wi::mask (precision - wi::clz (extra_bits),
2209 /* Clear the bits that aren't in MASK, but ensure that all bits
2210 in MASK below the top cleared bit are set. */
2211 return (val & mask) | (mask & lower_mask);
2214 /* Return VAL if VAL has no bits set outside MASK. Otherwise round VAL
2215 up to the next value that has no bits set outside MASK. The rounding
2216 wraps if there are no suitable values greater than VAL.
2218 For example, round_up_for_mask (6, 0xf1) would give 16 and
2219 round_up_for_mask (24, 0xf1) would give 32. */
2222 wi::round_up_for_mask (const wide_int &val, const wide_int &mask)
2224 /* Get the bits in VAL that are outside the mask. */
2225 wide_int extra_bits = wi::bit_and_not (val, mask);
2226 if (extra_bits == 0)
2229 /* Get a mask that is all 1s above the top bit in EXTRA_BITS. */
2230 unsigned int precision = val.get_precision ();
2231 wide_int upper_mask = wi::mask (precision - wi::clz (extra_bits),
2234 /* Get the bits of the mask that are above the top bit in EXTRA_BITS. */
2237 /* Conceptually we need to:
2239 - clear bits of VAL outside UPPER_MASK
2240 - add the lowest bit in UPPER_MASK to VAL (or add 0 if UPPER_MASK is 0)
2241 - propagate the carry through the bits of VAL in UPPER_MASK
2243 If (~VAL & UPPER_MASK) is nonzero, the carry eventually
2244 reaches that bit and the process leaves all lower bits clear.
2245 If (~VAL & UPPER_MASK) is zero then the result is also zero. */
2246 wide_int tmp = wi::bit_and_not (upper_mask, val);
2248 return (val | tmp) & -tmp;
2251 /* Compute the modular multiplicative inverse of A modulo B
2252 using extended Euclid's algorithm. Assumes A and B are coprime,
2253 and that A and B have the same precision. */
2255 wi::mod_inv (const wide_int &a, const wide_int &b)
2257 /* Verify the assumption. */
2258 gcc_checking_assert (wi::eq_p (wi::gcd (a, b), 1));
2260 unsigned int p = a.get_precision () + 1;
2261 gcc_checking_assert (b.get_precision () + 1 == p);
2262 wide_int c = wide_int::from (a, p, UNSIGNED);
2263 wide_int d = wide_int::from (b, p, UNSIGNED);
2264 wide_int x0 = wide_int::from (0, p, UNSIGNED);
2265 wide_int x1 = wide_int::from (1, p, UNSIGNED);
2267 if (wi::eq_p (b, 1))
2268 return wide_int::from (1, p, UNSIGNED);
2270 while (wi::gt_p (c, 1, UNSIGNED))
2273 wide_int q = wi::divmod_trunc (c, d, UNSIGNED, &d);
2276 x0 = wi::sub (x1, wi::mul (q, x0));
2279 if (wi::lt_p (x1, 0, SIGNED))
2285 * Private utilities.
2288 void gt_ggc_mx (widest_int *) { }
2289 void gt_pch_nx (widest_int *, void (*) (void *, void *), void *) { }
2290 void gt_pch_nx (widest_int *) { }
2292 template void wide_int::dump () const;
2293 template void generic_wide_int <wide_int_ref_storage <false> >::dump () const;
2294 template void generic_wide_int <wide_int_ref_storage <true> >::dump () const;
2295 template void offset_int::dump () const;
2296 template void widest_int::dump () const;
2298 /* We could add all the above ::dump variants here, but wide_int and
2299 widest_int should handle the common cases. Besides, you can always
2300 call the dump method directly. */
2303 debug (const wide_int &ref)
2309 debug (const wide_int *ptr)
2314 fprintf (stderr, "<nil>\n");
2318 debug (const widest_int &ref)
2324 debug (const widest_int *ptr)
2329 fprintf (stderr, "<nil>\n");
2334 namespace selftest {
2336 /* Selftests for wide ints. We run these multiple times, once per type. */
2338 /* Helper function for building a test value. */
2340 template <class VALUE_TYPE>
2344 /* Specializations of the fixture for each wide-int type. */
2346 /* Specialization for VALUE_TYPE == wide_int. */
2352 return wi::shwi (i, 32);
2355 /* Specialization for VALUE_TYPE == offset_int. */
2361 return offset_int (i);
2364 /* Specialization for VALUE_TYPE == widest_int. */
2370 return widest_int (i);
2373 /* Verify that print_dec (WI, ..., SGN) gives the expected string
2374 representation (using base 10). */
2377 assert_deceq (const char *expected, const wide_int_ref &wi, signop sgn)
2379 char buf[WIDE_INT_PRINT_BUFFER_SIZE];
2380 print_dec (wi, buf, sgn);
2381 ASSERT_STREQ (expected, buf);
2384 /* Likewise for base 16. */
2387 assert_hexeq (const char *expected, const wide_int_ref &wi)
2389 char buf[WIDE_INT_PRINT_BUFFER_SIZE];
2390 print_hex (wi, buf);
2391 ASSERT_STREQ (expected, buf);
2396 /* Verify that print_dec and print_hex work for VALUE_TYPE. */
2398 template <class VALUE_TYPE>
2402 VALUE_TYPE a = from_int<VALUE_TYPE> (42);
2403 assert_deceq ("42", a, SIGNED);
2404 assert_hexeq ("0x2a", a);
2405 assert_hexeq ("0x1fffffffffffffffff", wi::shwi (-1, 69));
2406 assert_hexeq ("0xffffffffffffffff", wi::mask (64, false, 69));
2407 assert_hexeq ("0xffffffffffffffff", wi::mask <widest_int> (64, false));
2408 if (WIDE_INT_MAX_PRECISION > 128)
2410 assert_hexeq ("0x20000000000000000fffffffffffffffe",
2411 wi::lshift (1, 129) + wi::lshift (1, 64) - 2);
2412 assert_hexeq ("0x200000000000004000123456789abcdef",
2413 wi::lshift (1, 129) + wi::lshift (1, 74)
2414 + wi::lshift (0x1234567, 32) + 0x89abcdef);
2418 /* Verify that various operations work correctly for VALUE_TYPE,
2419 unary and binary, using both function syntax, and
2420 overloaded-operators. */
2422 template <class VALUE_TYPE>
2426 VALUE_TYPE a = from_int<VALUE_TYPE> (7);
2427 VALUE_TYPE b = from_int<VALUE_TYPE> (3);
2429 /* Using functions. */
2430 assert_deceq ("-7", wi::neg (a), SIGNED);
2431 assert_deceq ("10", wi::add (a, b), SIGNED);
2432 assert_deceq ("4", wi::sub (a, b), SIGNED);
2433 assert_deceq ("-4", wi::sub (b, a), SIGNED);
2434 assert_deceq ("21", wi::mul (a, b), SIGNED);
2436 /* Using operators. */
2437 assert_deceq ("-7", -a, SIGNED);
2438 assert_deceq ("10", a + b, SIGNED);
2439 assert_deceq ("4", a - b, SIGNED);
2440 assert_deceq ("-4", b - a, SIGNED);
2441 assert_deceq ("21", a * b, SIGNED);
2444 /* Verify that various comparisons work correctly for VALUE_TYPE. */
2446 template <class VALUE_TYPE>
2450 VALUE_TYPE a = from_int<VALUE_TYPE> (7);
2451 VALUE_TYPE b = from_int<VALUE_TYPE> (3);
2454 ASSERT_TRUE (wi::eq_p (a, a));
2455 ASSERT_FALSE (wi::eq_p (a, b));
2458 ASSERT_TRUE (wi::ne_p (a, b));
2459 ASSERT_FALSE (wi::ne_p (a, a));
2462 ASSERT_FALSE (wi::lts_p (a, a));
2463 ASSERT_FALSE (wi::lts_p (a, b));
2464 ASSERT_TRUE (wi::lts_p (b, a));
2467 ASSERT_TRUE (wi::les_p (a, a));
2468 ASSERT_FALSE (wi::les_p (a, b));
2469 ASSERT_TRUE (wi::les_p (b, a));
2472 ASSERT_FALSE (wi::gts_p (a, a));
2473 ASSERT_TRUE (wi::gts_p (a, b));
2474 ASSERT_FALSE (wi::gts_p (b, a));
2477 ASSERT_TRUE (wi::ges_p (a, a));
2478 ASSERT_TRUE (wi::ges_p (a, b));
2479 ASSERT_FALSE (wi::ges_p (b, a));
2482 ASSERT_EQ (-1, wi::cmps (b, a));
2483 ASSERT_EQ (0, wi::cmps (a, a));
2484 ASSERT_EQ (1, wi::cmps (a, b));
2487 /* Run all of the selftests, using the given VALUE_TYPE. */
2489 template <class VALUE_TYPE>
2490 static void run_all_wide_int_tests ()
2492 test_printing <VALUE_TYPE> ();
2493 test_ops <VALUE_TYPE> ();
2494 test_comparisons <VALUE_TYPE> ();
2497 /* Test overflow conditions. */
2502 static int precs[] = { 31, 32, 33, 63, 64, 65, 127, 128 };
2503 static int offsets[] = { 16, 1, 0 };
2504 for (unsigned int i = 0; i < ARRAY_SIZE (precs); ++i)
2505 for (unsigned int j = 0; j < ARRAY_SIZE (offsets); ++j)
2507 int prec = precs[i];
2508 int offset = offsets[j];
2509 wi::overflow_type overflow;
2512 sum = wi::add (wi::max_value (prec, UNSIGNED) - offset, 1,
2513 UNSIGNED, &overflow);
2514 ASSERT_EQ (sum, -offset);
2515 ASSERT_EQ (overflow != wi::OVF_NONE, offset == 0);
2517 sum = wi::add (1, wi::max_value (prec, UNSIGNED) - offset,
2518 UNSIGNED, &overflow);
2519 ASSERT_EQ (sum, -offset);
2520 ASSERT_EQ (overflow != wi::OVF_NONE, offset == 0);
2522 diff = wi::sub (wi::max_value (prec, UNSIGNED) - offset,
2523 wi::max_value (prec, UNSIGNED),
2524 UNSIGNED, &overflow);
2525 ASSERT_EQ (diff, -offset);
2526 ASSERT_EQ (overflow != wi::OVF_NONE, offset != 0);
2528 diff = wi::sub (wi::max_value (prec, UNSIGNED) - offset,
2529 wi::max_value (prec, UNSIGNED) - 1,
2530 UNSIGNED, &overflow);
2531 ASSERT_EQ (diff, 1 - offset);
2532 ASSERT_EQ (overflow != wi::OVF_NONE, offset > 1);
2536 /* Test the round_{down,up}_for_mask functions. */
2539 test_round_for_mask ()
2541 unsigned int prec = 18;
2542 ASSERT_EQ (17, wi::round_down_for_mask (wi::shwi (17, prec),
2543 wi::shwi (0xf1, prec)));
2544 ASSERT_EQ (17, wi::round_up_for_mask (wi::shwi (17, prec),
2545 wi::shwi (0xf1, prec)));
2547 ASSERT_EQ (1, wi::round_down_for_mask (wi::shwi (6, prec),
2548 wi::shwi (0xf1, prec)));
2549 ASSERT_EQ (16, wi::round_up_for_mask (wi::shwi (6, prec),
2550 wi::shwi (0xf1, prec)));
2552 ASSERT_EQ (17, wi::round_down_for_mask (wi::shwi (24, prec),
2553 wi::shwi (0xf1, prec)));
2554 ASSERT_EQ (32, wi::round_up_for_mask (wi::shwi (24, prec),
2555 wi::shwi (0xf1, prec)));
2557 ASSERT_EQ (0x011, wi::round_down_for_mask (wi::shwi (0x22, prec),
2558 wi::shwi (0x111, prec)));
2559 ASSERT_EQ (0x100, wi::round_up_for_mask (wi::shwi (0x22, prec),
2560 wi::shwi (0x111, prec)));
2562 ASSERT_EQ (100, wi::round_down_for_mask (wi::shwi (101, prec),
2563 wi::shwi (0xfc, prec)));
2564 ASSERT_EQ (104, wi::round_up_for_mask (wi::shwi (101, prec),
2565 wi::shwi (0xfc, prec)));
2567 ASSERT_EQ (0x2bc, wi::round_down_for_mask (wi::shwi (0x2c2, prec),
2568 wi::shwi (0xabc, prec)));
2569 ASSERT_EQ (0x800, wi::round_up_for_mask (wi::shwi (0x2c2, prec),
2570 wi::shwi (0xabc, prec)));
2572 ASSERT_EQ (0xabc, wi::round_down_for_mask (wi::shwi (0xabd, prec),
2573 wi::shwi (0xabc, prec)));
2574 ASSERT_EQ (0, wi::round_up_for_mask (wi::shwi (0xabd, prec),
2575 wi::shwi (0xabc, prec)));
2577 ASSERT_EQ (0xabc, wi::round_down_for_mask (wi::shwi (0x1000, prec),
2578 wi::shwi (0xabc, prec)));
2579 ASSERT_EQ (0, wi::round_up_for_mask (wi::shwi (0x1000, prec),
2580 wi::shwi (0xabc, prec)));
2583 /* Run all of the selftests within this file, for all value types. */
2586 wide_int_cc_tests ()
2588 run_all_wide_int_tests <wide_int> ();
2589 run_all_wide_int_tests <offset_int> ();
2590 run_all_wide_int_tests <widest_int> ();
2592 test_round_for_mask ();
2593 ASSERT_EQ (wi::mask (128, false, 128),
2594 wi::shifted_mask (0, 128, false, 128));
2595 ASSERT_EQ (wi::mask (128, true, 128),
2596 wi::shifted_mask (0, 128, true, 128));
2599 } // namespace selftest
2600 #endif /* CHECKING_P */