Line data Source code
1 : /* Operations with very long integers.
2 : Copyright (C) 2012-2026 Free Software Foundation, Inc.
3 : Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
4 :
5 : This file is part of GCC.
6 :
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
10 : later version.
11 :
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
15 : for more details.
16 :
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/>. */
20 :
21 : #include "config.h"
22 : #include "system.h"
23 : #include "coretypes.h"
24 : #include "tm.h"
25 : #include "tree.h"
26 : #include "selftest.h"
27 :
28 :
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
34 : #else
35 : #error Please add support for HOST_HALF_WIDE_INT
36 : #endif
37 :
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)));
46 : #if W_TYPE_SIZE == 32
47 : typedef unsigned int UDWtype __attribute__ ((mode (DI)));
48 : #else
49 : typedef unsigned int UDWtype __attribute__ ((mode (TI)));
50 : #endif
51 : #include "longlong.h"
52 : #endif
53 :
54 : static const HOST_WIDE_INT zeros[1] = {};
55 :
56 : /*
57 : * Internal utilities.
58 : */
59 :
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)
63 :
64 : #define BLOCK_OF(TARGET) ((TARGET) / HOST_BITS_PER_WIDE_INT)
65 : #define BLOCKS_NEEDED(PREC) (PREC ? CEIL (PREC, HOST_BITS_PER_WIDE_INT) : 1)
66 : #define SIGN_MASK(X) ((HOST_WIDE_INT) (X) < 0 ? -1 : 0)
67 :
68 : /* Return the value a VAL[I] if I < LEN, otherwise, return 0 or -1
69 : based on the top existing bit of VAL. */
70 :
71 : static unsigned HOST_WIDE_INT
72 4381985034 : safe_uhwi (const HOST_WIDE_INT *val, unsigned int len, unsigned int i)
73 : {
74 4381985034 : return i < len ? val[i] : val[len - 1] < 0 ? HOST_WIDE_INT_M1 : 0;
75 : }
76 :
77 : /* Convert the integer in VAL to canonical form, returning its new length.
78 : LEN is the number of blocks currently in VAL and PRECISION is the number
79 : of bits in the integer it represents.
80 :
81 : This function only changes the representation, not the value. */
82 : static unsigned int
83 22163132353 : canonize (HOST_WIDE_INT *val, unsigned int len, unsigned int precision)
84 : {
85 22163132353 : unsigned int blocks_needed = BLOCKS_NEEDED (precision);
86 22163132353 : HOST_WIDE_INT top;
87 22163132353 : int i;
88 :
89 22163132353 : if (len > blocks_needed)
90 : len = blocks_needed;
91 :
92 22163132353 : if (len == 1)
93 : return 1;
94 :
95 2734293094 : top = val[len - 1];
96 2734293094 : if (len * HOST_BITS_PER_WIDE_INT > precision)
97 371159 : val[len - 1] = top = sext_hwi (top, precision % HOST_BITS_PER_WIDE_INT);
98 2734293094 : if (top != 0 && top != HOST_WIDE_INT_M1)
99 : return len;
100 :
101 : /* At this point we know that the top is either 0 or -1. Find the
102 : first block that is not a copy of this. */
103 3900514208 : for (i = len - 2; i >= 0; i--)
104 : {
105 3041312146 : HOST_WIDE_INT x = val[i];
106 3041312146 : if (x != top)
107 : {
108 3221345378 : if (SIGN_MASK (x) == top)
109 1407667844 : return i + 1;
110 :
111 : /* We need an extra block because the top bit block i does
112 : not match the extension. */
113 424348160 : return i + 2;
114 : }
115 : }
116 :
117 : /* The number is 0 or -1. */
118 : return 1;
119 : }
120 :
121 : /* VAL[0] is the unsigned result of an operation. Canonize it by adding
122 : another 0 block if needed, and return number of blocks needed. */
123 :
124 : static inline unsigned int
125 856436953 : canonize_uhwi (HOST_WIDE_INT *val, unsigned int precision)
126 : {
127 1121873 : if (val[0] < 0 && precision > HOST_BITS_PER_WIDE_INT)
128 : {
129 25723 : val[1] = 0;
130 25723 : return 2;
131 : }
132 : return 1;
133 : }
134 :
135 : /*
136 : * Conversion routines in and out of wide_int.
137 : */
138 :
139 : /* Copy XLEN elements from XVAL to VAL. If NEED_CANON, canonize the
140 : result for an integer with precision PRECISION. Return the length
141 : of VAL (after any canonization). */
142 : unsigned int
143 201079071 : wi::from_array (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
144 : unsigned int xlen, unsigned int precision, bool need_canon)
145 : {
146 798599854 : for (unsigned i = 0; i < xlen; i++)
147 597520783 : val[i] = xval[i];
148 201079071 : return need_canon ? canonize (val, xlen, precision) : xlen;
149 : }
150 :
151 : /* Construct a wide int from a buffer of length LEN. BUFFER will be
152 : read according to byte endianness and word endianness of the target.
153 : Only the lower BUFFER_LEN bytes of the result are set; the remaining
154 : high bytes are cleared. */
155 : wide_int
156 2873416 : wi::from_buffer (const unsigned char *buffer, unsigned int buffer_len)
157 : {
158 2873416 : unsigned int precision = buffer_len * BITS_PER_UNIT;
159 2873416 : wide_int result = wide_int::create (precision);
160 2873416 : unsigned int words = buffer_len / UNITS_PER_WORD;
161 :
162 : /* We have to clear all the bits ourself, as we merely or in values
163 : below. */
164 2873416 : unsigned int len = BLOCKS_NEEDED (precision);
165 2873416 : HOST_WIDE_INT *val = result.write_val (0);
166 5755884 : for (unsigned int i = 0; i < len; ++i)
167 2882468 : val[i] = 0;
168 :
169 18300780 : for (unsigned int byte = 0; byte < buffer_len; byte++)
170 : {
171 15427364 : unsigned int offset;
172 15427364 : unsigned int index;
173 15427364 : unsigned int bitpos = byte * BITS_PER_UNIT;
174 15427364 : unsigned HOST_WIDE_INT value;
175 :
176 15427364 : if (buffer_len > UNITS_PER_WORD)
177 : {
178 15427364 : unsigned int word = byte / UNITS_PER_WORD;
179 :
180 15427364 : if (WORDS_BIG_ENDIAN)
181 : word = (words - 1) - word;
182 :
183 15427364 : offset = word * UNITS_PER_WORD;
184 :
185 15427364 : if (BYTES_BIG_ENDIAN)
186 : offset += (UNITS_PER_WORD - 1) - (byte % UNITS_PER_WORD);
187 : else
188 15427364 : offset += byte % UNITS_PER_WORD;
189 : }
190 : else
191 : offset = BYTES_BIG_ENDIAN ? (buffer_len - 1) - byte : byte;
192 :
193 15427364 : value = (unsigned HOST_WIDE_INT) buffer[offset];
194 :
195 15427364 : index = bitpos / HOST_BITS_PER_WIDE_INT;
196 15427364 : val[index] |= value << (bitpos % HOST_BITS_PER_WIDE_INT);
197 : }
198 :
199 2873416 : result.set_len (canonize (val, len, precision));
200 :
201 2873416 : return result;
202 : }
203 :
204 : /* Sets RESULT from X, the sign is taken according to SGN. */
205 : void
206 127963183 : wi::to_mpz (const wide_int_ref &x, mpz_t result, signop sgn)
207 : {
208 127963183 : int len = x.get_len ();
209 127963183 : const HOST_WIDE_INT *v = x.get_val ();
210 127963183 : int excess = len * HOST_BITS_PER_WIDE_INT - x.get_precision ();
211 :
212 127963183 : if (wi::neg_p (x, sgn))
213 : {
214 : /* We use ones complement to avoid -x80..0 edge case that -
215 : won't work on. */
216 10635207 : HOST_WIDE_INT *t = XALLOCAVEC (HOST_WIDE_INT, len);
217 21284558 : for (int i = 0; i < len; i++)
218 10649351 : t[i] = ~v[i];
219 10635207 : if (excess > 0)
220 5178172 : t[len - 1] = (unsigned HOST_WIDE_INT) t[len - 1] << excess >> excess;
221 10635207 : mpz_import (result, len, -1, sizeof (HOST_WIDE_INT), 0, 0, t);
222 10635207 : mpz_com (result, result);
223 : }
224 117327976 : else if (excess > 0)
225 : {
226 68860301 : HOST_WIDE_INT *t = XALLOCAVEC (HOST_WIDE_INT, len);
227 68861141 : for (int i = 0; i < len - 1; i++)
228 840 : t[i] = v[i];
229 68860301 : t[len - 1] = (unsigned HOST_WIDE_INT) v[len - 1] << excess >> excess;
230 68860301 : mpz_import (result, len, -1, sizeof (HOST_WIDE_INT), 0, 0, t);
231 : }
232 48467675 : else if (excess < 0 && wi::neg_p (x))
233 : {
234 16694 : int extra = CEIL (-excess, HOST_BITS_PER_WIDE_INT);
235 16694 : HOST_WIDE_INT *t = XALLOCAVEC (HOST_WIDE_INT, len + extra);
236 33388 : for (int i = 0; i < len; i++)
237 16694 : t[i] = v[i];
238 35869 : for (int i = 0; i < extra; i++)
239 19175 : t[len + i] = -1;
240 16694 : excess = (-excess) % HOST_BITS_PER_WIDE_INT;
241 16694 : if (excess)
242 141 : t[len + extra - 1] = (HOST_WIDE_INT_1U << excess) - 1;
243 16694 : mpz_import (result, len + extra, -1, sizeof (HOST_WIDE_INT), 0, 0, t);
244 : }
245 : else
246 48450981 : mpz_import (result, len, -1, sizeof (HOST_WIDE_INT), 0, 0, v);
247 127963183 : }
248 :
249 : /* Returns X converted to TYPE. If WRAP is true, then out-of-range
250 : values of VAL will be wrapped; otherwise, they will be set to the
251 : appropriate minimum or maximum TYPE bound. */
252 : wide_int
253 15139065 : wi::from_mpz (const_tree type, mpz_t x, bool wrap)
254 : {
255 15139065 : size_t count, numb;
256 15139065 : unsigned int prec = TYPE_PRECISION (type);
257 15139065 : wide_int res = wide_int::create (prec);
258 :
259 15139065 : if (!wrap)
260 : {
261 12778489 : mpz_t min, max;
262 :
263 12778489 : mpz_init (min);
264 12778489 : mpz_init (max);
265 12778489 : get_type_static_bounds (type, min, max);
266 :
267 12778489 : if (mpz_cmp (x, min) < 0)
268 152 : mpz_set (x, min);
269 12778337 : else if (mpz_cmp (x, max) > 0)
270 257 : mpz_set (x, max);
271 :
272 12778489 : mpz_clear (min);
273 12778489 : mpz_clear (max);
274 : }
275 :
276 : /* Determine the number of unsigned HOST_WIDE_INTs that are required
277 : for representing the absolute value. The code to calculate count is
278 : extracted from the GMP manual, section "Integer Import and Export":
279 : http://gmplib.org/manual/Integer-Import-and-Export.html */
280 15139065 : numb = CHAR_BIT * sizeof (HOST_WIDE_INT);
281 15139065 : count = CEIL (mpz_sizeinbase (x, 2), numb);
282 15139065 : HOST_WIDE_INT *val = res.write_val (0);
283 : /* Read the absolute value.
284 :
285 : Write directly to the wide_int storage if possible, otherwise leave
286 : GMP to allocate the memory for us. It might be slightly more efficient
287 : to use mpz_tdiv_r_2exp for the latter case, but the situation is
288 : pathological and it seems safer to operate on the original mpz value
289 : in all cases. */
290 15139099 : void *valres = mpz_export (count <= WIDE_INT_MAX_INL_ELTS ? val : 0,
291 : &count, -1, sizeof (HOST_WIDE_INT), 0, 0, x);
292 15139065 : if (count < 1)
293 : {
294 231213 : val[0] = 0;
295 231213 : count = 1;
296 : }
297 15139065 : count = MIN (count, BLOCKS_NEEDED (prec));
298 15139065 : if (valres != val)
299 : {
300 34 : memcpy (val, valres, count * sizeof (HOST_WIDE_INT));
301 34 : free (valres);
302 : }
303 : /* Zero-extend the absolute value to PREC bits. */
304 15139065 : if (count < BLOCKS_NEEDED (prec) && val[count - 1] < 0)
305 1663 : val[count++] = 0;
306 : else
307 15137402 : count = canonize (val, count, prec);
308 15139065 : res.set_len (count);
309 :
310 15139065 : if (mpz_sgn (x) < 0)
311 93847 : res = -res;
312 :
313 15139065 : return res;
314 : }
315 :
316 : /*
317 : * Largest and smallest values in a mode.
318 : */
319 :
320 : /* Return the largest SGNed number that is representable in PRECISION bits.
321 :
322 : TODO: There is still code from the double_int era that tries to
323 : make up for the fact that double int's could not represent the
324 : min and max values of all types. This code should be removed
325 : because the min and max values can always be represented in
326 : wide_ints and int-csts. */
327 : wide_int
328 5524589562 : wi::max_value (unsigned int precision, signop sgn)
329 : {
330 5524589562 : gcc_checking_assert (precision != 0);
331 5524589562 : if (sgn == UNSIGNED)
332 : /* The unsigned max is just all ones. */
333 4163315507 : return shwi (-1, precision);
334 : else
335 : /* The signed max is all ones except the top bit. This must be
336 : explicitly represented. */
337 1361274055 : return mask (precision - 1, false, precision);
338 : }
339 :
340 : /* Return the largest SGNed number that is representable in PRECISION bits. */
341 : wide_int
342 6687266001 : wi::min_value (unsigned int precision, signop sgn)
343 : {
344 6687266001 : gcc_checking_assert (precision != 0);
345 6687266001 : if (sgn == UNSIGNED)
346 3953472928 : return uhwi (0, precision);
347 : else
348 : /* The signed min is all zeros except the top bit. This must be
349 : explicitly represented. */
350 2733793073 : return wi::set_bit_in_zero (precision - 1, precision);
351 : }
352 :
353 : /*
354 : * Public utilities.
355 : */
356 :
357 : /* Convert the number represented by XVAL, XLEN and XPRECISION, which has
358 : signedness SGN, to an integer that has PRECISION bits. Store the blocks
359 : in VAL and return the number of blocks used.
360 :
361 : This function can handle both extension (PRECISION > XPRECISION)
362 : and truncation (PRECISION < XPRECISION). */
363 : unsigned int
364 19304967468 : wi::force_to_size (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
365 : unsigned int xlen, unsigned int xprecision,
366 : unsigned int precision, signop sgn)
367 : {
368 19304967468 : unsigned int blocks_needed = BLOCKS_NEEDED (precision);
369 19304967468 : unsigned int len = blocks_needed < xlen ? blocks_needed : xlen;
370 38622093806 : for (unsigned i = 0; i < len; i++)
371 19317126338 : val[i] = xval[i];
372 :
373 19304967468 : if (precision > xprecision)
374 : {
375 4947051286 : unsigned int small_xprecision = xprecision % HOST_BITS_PER_WIDE_INT;
376 :
377 : /* Expanding. */
378 4947051286 : if (sgn == UNSIGNED)
379 : {
380 2182471039 : if (small_xprecision && len == BLOCKS_NEEDED (xprecision))
381 987481377 : val[len - 1] = zext_hwi (val[len - 1], small_xprecision);
382 1194989662 : else if (val[len - 1] < 0)
383 : {
384 172425226 : while (len < BLOCKS_NEEDED (xprecision))
385 1209048 : val[len++] = -1;
386 171216178 : if (small_xprecision)
387 29246 : val[len - 1] = zext_hwi (val[len - 1], small_xprecision);
388 : else
389 171186932 : val[len++] = 0;
390 : }
391 : }
392 : else
393 : {
394 2764580247 : if (small_xprecision && len == BLOCKS_NEEDED (xprecision))
395 1077165597 : val[len - 1] = sext_hwi (val[len - 1], small_xprecision);
396 : }
397 : }
398 19304967468 : len = canonize (val, len, precision);
399 :
400 19304967468 : return len;
401 : }
402 :
403 : /* This function hides the fact that we cannot rely on the bits beyond
404 : the precision. This issue comes up in the relational comparisons
405 : where we do allow comparisons of values of different precisions. */
406 : static inline HOST_WIDE_INT
407 276810152 : selt (const HOST_WIDE_INT *a, unsigned int len,
408 : unsigned int blocks_needed, unsigned int small_prec,
409 : unsigned int index, signop sgn)
410 : {
411 276810152 : HOST_WIDE_INT val;
412 276810152 : if (index < len)
413 221287738 : val = a[index];
414 55522414 : else if (index < blocks_needed || sgn == SIGNED)
415 : /* Signed or within the precision. */
416 55522414 : val = SIGN_MASK (a[len - 1]);
417 : else
418 : /* Unsigned extension beyond the precision. */
419 : val = 0;
420 :
421 276810152 : if (small_prec && index == blocks_needed - 1)
422 1423458 : return (sgn == SIGNED
423 1423458 : ? sext_hwi (val, small_prec)
424 292072 : : zext_hwi (val, small_prec));
425 : else
426 : return val;
427 : }
428 :
429 : /* Find the highest bit represented in a wide int. This will in
430 : general have the same value as the sign bit. */
431 : static inline HOST_WIDE_INT
432 648067076 : top_bit_of (const HOST_WIDE_INT *a, unsigned int len, unsigned int prec)
433 : {
434 648067076 : int excess = len * HOST_BITS_PER_WIDE_INT - prec;
435 648067076 : unsigned HOST_WIDE_INT val = a[len - 1];
436 648067076 : if (excess > 0)
437 39764 : val <<= excess;
438 648067076 : return val >> (HOST_BITS_PER_WIDE_INT - 1);
439 : }
440 :
441 : /*
442 : * Comparisons, note that only equality is an operator. The other
443 : * comparisons cannot be operators since they are inherently signed or
444 : * unsigned and C++ has no such operators.
445 : */
446 :
447 : /* Return true if OP0 == OP1. */
448 : bool
449 2254930 : wi::eq_p_large (const HOST_WIDE_INT *op0, unsigned int op0len,
450 : const HOST_WIDE_INT *op1, unsigned int op1len,
451 : unsigned int prec)
452 : {
453 2254930 : int l0 = op0len - 1;
454 2254930 : unsigned int small_prec = prec & (HOST_BITS_PER_WIDE_INT - 1);
455 :
456 2254930 : if (op0len != op1len)
457 : return false;
458 :
459 1219596 : if (op0len == BLOCKS_NEEDED (prec) && small_prec)
460 : {
461 : /* It does not matter if we zext or sext here, we just have to
462 : do both the same way. */
463 59022 : if (zext_hwi (op0 [l0], small_prec) != zext_hwi (op1 [l0], small_prec))
464 : return false;
465 54462 : l0--;
466 : }
467 :
468 3754801 : while (l0 >= 0)
469 2572980 : if (op0[l0] != op1[l0])
470 : return false;
471 : else
472 2539765 : l0--;
473 :
474 : return true;
475 : }
476 :
477 : /* Return true if OP0 < OP1 using signed comparisons. */
478 : bool
479 26923671 : wi::lts_p_large (const HOST_WIDE_INT *op0, unsigned int op0len,
480 : unsigned int precision,
481 : const HOST_WIDE_INT *op1, unsigned int op1len)
482 : {
483 26923671 : HOST_WIDE_INT s0, s1;
484 26923671 : unsigned HOST_WIDE_INT u0, u1;
485 26923671 : unsigned int blocks_needed = BLOCKS_NEEDED (precision);
486 26923671 : unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
487 26923671 : int l = MAX (op0len - 1, op1len - 1);
488 :
489 : /* Only the top block is compared as signed. The rest are unsigned
490 : comparisons. */
491 26923671 : s0 = selt (op0, op0len, blocks_needed, small_prec, l, SIGNED);
492 26923671 : s1 = selt (op1, op1len, blocks_needed, small_prec, l, SIGNED);
493 26923671 : if (s0 < s1)
494 : return true;
495 25934891 : if (s0 > s1)
496 : return false;
497 :
498 22798179 : l--;
499 29646529 : while (l >= 0)
500 : {
501 23365429 : u0 = selt (op0, op0len, blocks_needed, small_prec, l, SIGNED);
502 23365429 : u1 = selt (op1, op1len, blocks_needed, small_prec, l, SIGNED);
503 :
504 23365429 : if (u0 < u1)
505 : return true;
506 8402574 : if (u0 > u1)
507 : return false;
508 6848350 : l--;
509 : }
510 :
511 : return false;
512 : }
513 :
514 : /* Returns -1 if OP0 < OP1, 0 if OP0 == OP1 and 1 if OP0 > OP1 using
515 : signed compares. */
516 : int
517 2850299 : wi::cmps_large (const HOST_WIDE_INT *op0, unsigned int op0len,
518 : unsigned int precision,
519 : const HOST_WIDE_INT *op1, unsigned int op1len)
520 : {
521 2850299 : HOST_WIDE_INT s0, s1;
522 2850299 : unsigned HOST_WIDE_INT u0, u1;
523 2850299 : unsigned int blocks_needed = BLOCKS_NEEDED (precision);
524 2850299 : unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
525 2850299 : int l = MAX (op0len - 1, op1len - 1);
526 :
527 : /* Only the top block is compared as signed. The rest are unsigned
528 : comparisons. */
529 2850299 : s0 = selt (op0, op0len, blocks_needed, small_prec, l, SIGNED);
530 2850299 : s1 = selt (op1, op1len, blocks_needed, small_prec, l, SIGNED);
531 2850299 : if (s0 < s1)
532 : return -1;
533 1401137 : if (s0 > s1)
534 : return 1;
535 :
536 1274787 : l--;
537 2075961 : while (l >= 0)
538 : {
539 1515954 : u0 = selt (op0, op0len, blocks_needed, small_prec, l, SIGNED);
540 1515954 : u1 = selt (op1, op1len, blocks_needed, small_prec, l, SIGNED);
541 :
542 1515954 : if (u0 < u1)
543 : return -1;
544 845356 : if (u0 > u1)
545 : return 1;
546 801174 : l--;
547 : }
548 :
549 : return 0;
550 : }
551 :
552 : /* Return true if OP0 < OP1 using unsigned comparisons. */
553 : bool
554 43403994 : wi::ltu_p_large (const HOST_WIDE_INT *op0, unsigned int op0len,
555 : unsigned int precision,
556 : const HOST_WIDE_INT *op1, unsigned int op1len)
557 : {
558 43403994 : unsigned HOST_WIDE_INT x0;
559 43403994 : unsigned HOST_WIDE_INT x1;
560 43403994 : unsigned int blocks_needed = BLOCKS_NEEDED (precision);
561 43403994 : unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
562 43403994 : int l = MAX (op0len - 1, op1len - 1);
563 :
564 66315875 : while (l >= 0)
565 : {
566 63899855 : x0 = selt (op0, op0len, blocks_needed, small_prec, l, UNSIGNED);
567 63899855 : x1 = selt (op1, op1len, blocks_needed, small_prec, l, UNSIGNED);
568 63899855 : if (x0 < x1)
569 : return true;
570 52423413 : if (x0 > x1)
571 : return false;
572 22911881 : l--;
573 : }
574 :
575 : return false;
576 : }
577 :
578 : /* Returns -1 if OP0 < OP1, 0 if OP0 == OP1 and 1 if OP0 > OP1 using
579 : unsigned compares. */
580 : int
581 11564444 : wi::cmpu_large (const HOST_WIDE_INT *op0, unsigned int op0len,
582 : unsigned int precision,
583 : const HOST_WIDE_INT *op1, unsigned int op1len)
584 : {
585 11564444 : unsigned HOST_WIDE_INT x0;
586 11564444 : unsigned HOST_WIDE_INT x1;
587 11564444 : unsigned int blocks_needed = BLOCKS_NEEDED (precision);
588 11564444 : unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
589 11564444 : int l = MAX (op0len - 1, op1len - 1);
590 :
591 20666943 : while (l >= 0)
592 : {
593 19849868 : x0 = selt (op0, op0len, blocks_needed, small_prec, l, UNSIGNED);
594 19849868 : x1 = selt (op1, op1len, blocks_needed, small_prec, l, UNSIGNED);
595 19849868 : if (x0 < x1)
596 : return -1;
597 10729125 : if (x0 > x1)
598 : return 1;
599 9102499 : l--;
600 : }
601 :
602 : return 0;
603 : }
604 :
605 : /*
606 : * Extension.
607 : */
608 :
609 : /* Sign-extend the number represented by XVAL and XLEN into VAL,
610 : starting at OFFSET. Return the number of blocks in VAL. Both XVAL
611 : and VAL have PRECISION bits. */
612 : unsigned int
613 5390842 : wi::sext_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
614 : unsigned int xlen, unsigned int precision, unsigned int offset)
615 : {
616 5390842 : unsigned int len = offset / HOST_BITS_PER_WIDE_INT;
617 : /* Extending beyond the precision is a no-op. If we have only stored
618 : OFFSET bits or fewer, the rest are already signs. */
619 5390842 : if (offset >= precision || len >= xlen)
620 : {
621 178681832 : for (unsigned i = 0; i < xlen; ++i)
622 173636873 : val[i] = xval[i];
623 : return xlen;
624 : }
625 345883 : unsigned int suboffset = offset % HOST_BITS_PER_WIDE_INT;
626 1525474 : for (unsigned int i = 0; i < len; i++)
627 1179591 : val[i] = xval[i];
628 345883 : if (suboffset > 0)
629 : {
630 25681 : val[len] = sext_hwi (xval[len], suboffset);
631 25681 : len += 1;
632 : }
633 345883 : return canonize (val, len, precision);
634 : }
635 :
636 : /* Zero-extend the number represented by XVAL and XLEN into VAL,
637 : starting at OFFSET. Return the number of blocks in VAL. Both XVAL
638 : and VAL have PRECISION bits. */
639 : unsigned int
640 761082013 : wi::zext_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
641 : unsigned int xlen, unsigned int precision, unsigned int offset)
642 : {
643 761082013 : unsigned int len = offset / HOST_BITS_PER_WIDE_INT;
644 : /* Extending beyond the precision is a no-op. If we have only stored
645 : OFFSET bits or fewer, and the upper stored bit is zero, then there
646 : is nothing to do. */
647 761082013 : if (offset >= precision || (len >= xlen && xval[xlen - 1] >= 0))
648 : {
649 1240366483 : for (unsigned i = 0; i < xlen; ++i)
650 620506952 : val[i] = xval[i];
651 : return xlen;
652 : }
653 141222482 : unsigned int suboffset = offset % HOST_BITS_PER_WIDE_INT;
654 283823177 : for (unsigned int i = 0; i < len; i++)
655 142600695 : val[i] = i < xlen ? xval[i] : -1;
656 141222482 : if (suboffset > 0)
657 38476 : val[len] = zext_hwi (len < xlen ? xval[len] : -1, suboffset);
658 : else
659 141184006 : val[len] = 0;
660 141222482 : return canonize (val, len + 1, precision);
661 : }
662 :
663 : /*
664 : * Masking, inserting, shifting, rotating.
665 : */
666 :
667 : /* Insert WIDTH bits from Y into X starting at START. */
668 : wide_int
669 367760 : wi::insert (const wide_int &x, const wide_int &y, unsigned int start,
670 : unsigned int width)
671 : {
672 367760 : wide_int result;
673 367760 : wide_int mask;
674 367760 : wide_int tmp;
675 :
676 367760 : unsigned int precision = x.get_precision ();
677 367760 : if (start >= precision)
678 0 : return x;
679 :
680 367760 : gcc_checking_assert (precision >= width);
681 :
682 367760 : if (start + width >= precision)
683 143533 : width = precision - start;
684 :
685 367760 : mask = wi::shifted_mask (start, width, false, precision);
686 367760 : tmp = wi::lshift (wide_int::from (y, precision, UNSIGNED), start);
687 367760 : result = tmp & mask;
688 :
689 367760 : tmp = wi::bit_and_not (x, mask);
690 367760 : result = result | tmp;
691 :
692 367760 : return result;
693 367760 : }
694 :
695 : /* Copy the number represented by XVAL and XLEN into VAL, setting bit BIT.
696 : Return the number of blocks in VAL. Both XVAL and VAL have PRECISION
697 : bits. */
698 : unsigned int
699 89 : wi::set_bit_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
700 : unsigned int xlen, unsigned int precision, unsigned int bit)
701 : {
702 89 : unsigned int block = bit / HOST_BITS_PER_WIDE_INT;
703 89 : unsigned int subbit = bit % HOST_BITS_PER_WIDE_INT;
704 :
705 89 : if (block + 1 >= xlen)
706 : {
707 : /* The operation either affects the last current block or needs
708 : a new block. */
709 39 : unsigned int len = block + 1;
710 39 : for (unsigned int i = 0; i < len; i++)
711 52 : val[i] = safe_uhwi (xval, xlen, i);
712 13 : val[block] |= HOST_WIDE_INT_1U << subbit;
713 :
714 : /* If the bit we just set is at the msb of the block, make sure
715 : that any higher bits are zeros. */
716 13 : if (bit + 1 < precision && subbit == HOST_BITS_PER_WIDE_INT - 1)
717 : {
718 0 : val[len++] = 0;
719 0 : return len;
720 : }
721 13 : return canonize (val, len, precision);
722 : }
723 : else
724 : {
725 380 : for (unsigned int i = 0; i < xlen; i++)
726 304 : val[i] = xval[i];
727 76 : val[block] |= HOST_WIDE_INT_1U << subbit;
728 76 : return canonize (val, xlen, precision);
729 : }
730 : }
731 :
732 : /* Byte swap the integer represented by XVAL and XLEN into VAL. Return
733 : the number of blocks in VAL. Both XVAL and VAL have PRECISION bits. */
734 : unsigned int
735 7503 : wi::bswap_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
736 : unsigned int xlen, unsigned int precision)
737 : {
738 7503 : unsigned int s, len = BLOCKS_NEEDED (precision);
739 :
740 : /* This is not a well defined operation if the precision is not a
741 : multiple of 8. */
742 7503 : gcc_assert ((precision & 0x7) == 0);
743 :
744 7503 : memset (val, 0, sizeof (unsigned HOST_WIDE_INT) * len);
745 :
746 : /* Only swap the bytes that are not the padding. */
747 47308 : for (s = 0; s < precision; s += 8)
748 : {
749 39805 : unsigned int d = precision - s - 8;
750 39805 : unsigned HOST_WIDE_INT byte;
751 :
752 39805 : unsigned int block = s / HOST_BITS_PER_WIDE_INT;
753 39805 : unsigned int offset = s & (HOST_BITS_PER_WIDE_INT - 1);
754 :
755 39805 : byte = (safe_uhwi (xval, xlen, block) >> offset) & 0xff;
756 :
757 39805 : block = d / HOST_BITS_PER_WIDE_INT;
758 39805 : offset = d & (HOST_BITS_PER_WIDE_INT - 1);
759 :
760 39805 : val[block] |= byte << offset;
761 : }
762 :
763 7503 : return canonize (val, len, precision);
764 : }
765 :
766 : /* Bitreverse the integer represented by XVAL and XLEN into VAL. Return
767 : the number of blocks in VAL. Both XVAL and VAL have PRECISION bits. */
768 : unsigned int
769 135 : wi::bitreverse_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
770 : unsigned int xlen, unsigned int precision)
771 : {
772 135 : unsigned int s, len = BLOCKS_NEEDED (precision);
773 :
774 135 : memset (val, 0, sizeof (unsigned HOST_WIDE_INT) * len);
775 :
776 9473 : for (s = 0; s < precision; s++)
777 : {
778 9338 : unsigned int block = s / HOST_BITS_PER_WIDE_INT;
779 9338 : unsigned int offset = s & (HOST_BITS_PER_WIDE_INT - 1);
780 18676 : if (((safe_uhwi (xval, xlen, block) >> offset) & 1) != 0)
781 : {
782 3164 : unsigned int d = (precision - 1) - s;
783 3164 : block = d / HOST_BITS_PER_WIDE_INT;
784 3164 : offset = d & (HOST_BITS_PER_WIDE_INT - 1);
785 3164 : val[block] |= HOST_WIDE_INT_1U << offset;
786 : }
787 : }
788 :
789 135 : return canonize (val, len, precision);
790 : }
791 :
792 : /* Fill VAL with a mask where the lower WIDTH bits are ones and the bits
793 : above that up to PREC are zeros. The result is inverted if NEGATE
794 : is true. Return the number of blocks in VAL. */
795 : unsigned int
796 2531202278 : wi::mask (HOST_WIDE_INT *val, unsigned int width, bool negate,
797 : unsigned int prec)
798 : {
799 2531202278 : if (width >= prec)
800 : {
801 493289002 : val[0] = negate ? 0 : -1;
802 493289002 : return 1;
803 : }
804 2037913276 : else if (width == 0)
805 : {
806 11827395 : val[0] = negate ? -1 : 0;
807 11827395 : return 1;
808 : }
809 :
810 : unsigned int i = 0;
811 2359773522 : while (i < width / HOST_BITS_PER_WIDE_INT)
812 667129008 : val[i++] = negate ? 0 : -1;
813 :
814 2026085881 : unsigned int shift = width & (HOST_BITS_PER_WIDE_INT - 1);
815 2026085881 : if (shift != 0)
816 : {
817 2006600144 : HOST_WIDE_INT last = (HOST_WIDE_INT_1U << shift) - 1;
818 2006600144 : val[i++] = negate ? ~last : last;
819 : }
820 : else
821 38738402 : val[i++] = negate ? -1 : 0;
822 :
823 : return i;
824 : }
825 :
826 : /* Fill VAL with a mask where the lower START bits are zeros, the next WIDTH
827 : bits are ones, and the bits above that up to PREC are zeros. The result
828 : is inverted if NEGATE is true. Return the number of blocks in VAL. */
829 : unsigned int
830 2751902958 : wi::shifted_mask (HOST_WIDE_INT *val, unsigned int start, unsigned int width,
831 : bool negate, unsigned int prec)
832 : {
833 2751902958 : if (start >= prec || width == 0)
834 : {
835 2 : val[0] = negate ? -1 : 0;
836 2 : return 1;
837 : }
838 :
839 2751902956 : if (width > prec - start)
840 : width = prec - start;
841 2751902956 : unsigned int end = start + width;
842 :
843 2751902956 : unsigned int i = 0;
844 3510381862 : while (i < start / HOST_BITS_PER_WIDE_INT)
845 1516957810 : val[i++] = negate ? -1 : 0;
846 :
847 2751902956 : unsigned int shift = start & (HOST_BITS_PER_WIDE_INT - 1);
848 2751902956 : if (shift)
849 : {
850 2750619720 : HOST_WIDE_INT block = (HOST_WIDE_INT_1U << shift) - 1;
851 2750619720 : shift += width;
852 2750619720 : if (shift < HOST_BITS_PER_WIDE_INT)
853 : {
854 : /* case 000111000 */
855 1461489658 : block = (HOST_WIDE_INT_1U << shift) - block - 1;
856 1461489658 : val[i++] = negate ? ~block : block;
857 1461489658 : return i;
858 : }
859 : else
860 : /* ...111000 */
861 1289130062 : val[i++] = negate ? block : ~block;
862 : }
863 :
864 1290413298 : if (end >= prec)
865 : {
866 1289142972 : if (!shift)
867 283328 : val[i++] = negate ? 0 : -1;
868 : return i;
869 : }
870 :
871 1453326 : while (i < end / HOST_BITS_PER_WIDE_INT)
872 : /* 1111111 */
873 192946 : val[i++] = negate ? 0 : -1;
874 :
875 1270326 : shift = end & (HOST_BITS_PER_WIDE_INT - 1);
876 1270326 : if (shift != 0)
877 : {
878 : /* 000011111 */
879 954830 : HOST_WIDE_INT block = (HOST_WIDE_INT_1U << shift) - 1;
880 954830 : val[i++] = negate ? ~block : block;
881 : }
882 : else
883 459949 : val[i++] = negate ? -1 : 0;
884 :
885 : return i;
886 : }
887 :
888 : /*
889 : * logical operations.
890 : */
891 :
892 : /* Set VAL to OP0 & OP1. Return the number of blocks used. */
893 : unsigned int
894 30695357 : wi::and_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
895 : unsigned int op0len, const HOST_WIDE_INT *op1,
896 : unsigned int op1len, unsigned int prec)
897 : {
898 30695357 : int l0 = op0len - 1;
899 30695357 : int l1 = op1len - 1;
900 30695357 : bool need_canon = true;
901 :
902 30695357 : unsigned int len = MAX (op0len, op1len);
903 30695357 : if (l0 > l1)
904 : {
905 13661212 : HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec);
906 13661212 : if (op1mask == 0)
907 : {
908 30695357 : l0 = l1;
909 30695357 : len = l1 + 1;
910 : }
911 : else
912 : {
913 132094 : need_canon = false;
914 132094 : while (l0 > l1)
915 : {
916 66539 : val[l0] = op0[l0];
917 66539 : l0--;
918 : }
919 : }
920 : }
921 17034145 : else if (l1 > l0)
922 : {
923 7678812 : HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec);
924 7678812 : if (op0mask == 0)
925 : len = l0 + 1;
926 : else
927 : {
928 874216 : need_canon = false;
929 874216 : while (l1 > l0)
930 : {
931 458971 : val[l1] = op1[l1];
932 458971 : l1--;
933 : }
934 : }
935 : }
936 :
937 70970489 : while (l0 >= 0)
938 : {
939 40275132 : val[l0] = op0[l0] & op1[l0];
940 40275132 : l0--;
941 : }
942 :
943 30695357 : if (need_canon)
944 30214557 : len = canonize (val, len, prec);
945 :
946 30695357 : return len;
947 : }
948 :
949 : /* Set VAL to OP0 & ~OP1. Return the number of blocks used. */
950 : unsigned int
951 92032910 : wi::and_not_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
952 : unsigned int op0len, const HOST_WIDE_INT *op1,
953 : unsigned int op1len, unsigned int prec)
954 : {
955 92032910 : wide_int result;
956 92032910 : int l0 = op0len - 1;
957 92032910 : int l1 = op1len - 1;
958 92032910 : bool need_canon = true;
959 :
960 92032910 : unsigned int len = MAX (op0len, op1len);
961 92032910 : if (l0 > l1)
962 : {
963 13876943 : HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec);
964 13876943 : if (op1mask != 0)
965 : {
966 92032910 : l0 = l1;
967 92032910 : len = l1 + 1;
968 : }
969 : else
970 : {
971 27192081 : need_canon = false;
972 27192081 : while (l0 > l1)
973 : {
974 13646842 : val[l0] = op0[l0];
975 13646842 : l0--;
976 : }
977 : }
978 : }
979 78155967 : else if (l1 > l0)
980 : {
981 76891686 : HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec);
982 76891686 : if (op0mask == 0)
983 : len = l0 + 1;
984 : else
985 : {
986 131300 : need_canon = false;
987 131300 : while (l1 > l0)
988 : {
989 66837 : val[l1] = ~op1[l1];
990 66837 : l1--;
991 : }
992 : }
993 : }
994 :
995 185464835 : while (l0 >= 0)
996 : {
997 93431925 : val[l0] = op0[l0] & ~op1[l0];
998 93431925 : l0--;
999 : }
1000 :
1001 92032910 : if (need_canon)
1002 78423208 : len = canonize (val, len, prec);
1003 :
1004 92032910 : return len;
1005 92032910 : }
1006 :
1007 : /* Set VAL to OP0 | OP1. Return the number of blocks used. */
1008 : unsigned int
1009 178036133 : wi::or_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
1010 : unsigned int op0len, const HOST_WIDE_INT *op1,
1011 : unsigned int op1len, unsigned int prec)
1012 : {
1013 178036133 : wide_int result;
1014 178036133 : int l0 = op0len - 1;
1015 178036133 : int l1 = op1len - 1;
1016 178036133 : bool need_canon = true;
1017 :
1018 178036133 : unsigned int len = MAX (op0len, op1len);
1019 178036133 : if (l0 > l1)
1020 : {
1021 64241255 : HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec);
1022 64241255 : if (op1mask != 0)
1023 : {
1024 178036133 : l0 = l1;
1025 178036133 : len = l1 + 1;
1026 : }
1027 : else
1028 : {
1029 228702283 : need_canon = false;
1030 228702283 : while (l0 > l1)
1031 : {
1032 164836902 : val[l0] = op0[l0];
1033 164836902 : l0--;
1034 : }
1035 : }
1036 : }
1037 113794878 : else if (l1 > l0)
1038 : {
1039 65112113 : HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec);
1040 65112113 : if (op0mask != 0)
1041 : len = l0 + 1;
1042 : else
1043 : {
1044 290118316 : need_canon = false;
1045 290118316 : while (l1 > l0)
1046 : {
1047 228915838 : val[l1] = op1[l1];
1048 228915838 : l1--;
1049 : }
1050 : }
1051 : }
1052 :
1053 572686148 : while (l0 >= 0)
1054 : {
1055 394650015 : val[l0] = op0[l0] | op1[l0];
1056 394650015 : l0--;
1057 : }
1058 :
1059 178036133 : if (need_canon)
1060 52968274 : len = canonize (val, len, prec);
1061 :
1062 178036133 : return len;
1063 178036133 : }
1064 :
1065 : /* Set VAL to OP0 | ~OP1. Return the number of blocks used. */
1066 : unsigned int
1067 0 : wi::or_not_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
1068 : unsigned int op0len, const HOST_WIDE_INT *op1,
1069 : unsigned int op1len, unsigned int prec)
1070 : {
1071 0 : wide_int result;
1072 0 : int l0 = op0len - 1;
1073 0 : int l1 = op1len - 1;
1074 0 : bool need_canon = true;
1075 :
1076 0 : unsigned int len = MAX (op0len, op1len);
1077 0 : if (l0 > l1)
1078 : {
1079 0 : HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec);
1080 0 : if (op1mask == 0)
1081 : {
1082 0 : l0 = l1;
1083 0 : len = l1 + 1;
1084 : }
1085 : else
1086 : {
1087 0 : need_canon = false;
1088 0 : while (l0 > l1)
1089 : {
1090 0 : val[l0] = op0[l0];
1091 0 : l0--;
1092 : }
1093 : }
1094 : }
1095 0 : else if (l1 > l0)
1096 : {
1097 0 : HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec);
1098 0 : if (op0mask != 0)
1099 : len = l0 + 1;
1100 : else
1101 : {
1102 0 : need_canon = false;
1103 0 : while (l1 > l0)
1104 : {
1105 0 : val[l1] = ~op1[l1];
1106 0 : l1--;
1107 : }
1108 : }
1109 : }
1110 :
1111 0 : while (l0 >= 0)
1112 : {
1113 0 : val[l0] = op0[l0] | ~op1[l0];
1114 0 : l0--;
1115 : }
1116 :
1117 0 : if (need_canon)
1118 0 : len = canonize (val, len, prec);
1119 :
1120 0 : return len;
1121 0 : }
1122 :
1123 : /* Set VAL to OP0 ^ OP1. Return the number of blocks used. */
1124 : unsigned int
1125 36287387 : wi::xor_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
1126 : unsigned int op0len, const HOST_WIDE_INT *op1,
1127 : unsigned int op1len, unsigned int prec)
1128 : {
1129 36287387 : wide_int result;
1130 36287387 : int l0 = op0len - 1;
1131 36287387 : int l1 = op1len - 1;
1132 :
1133 36287387 : unsigned int len = MAX (op0len, op1len);
1134 36287387 : if (l0 > l1)
1135 : {
1136 8166710 : HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec);
1137 16451401 : while (l0 > l1)
1138 : {
1139 8284691 : val[l0] = op0[l0] ^ op1mask;
1140 8284691 : l0--;
1141 : }
1142 : }
1143 :
1144 36287387 : if (l1 > l0)
1145 : {
1146 22498921 : HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec);
1147 112145693 : while (l1 > l0)
1148 : {
1149 89646772 : val[l1] = op0mask ^ op1[l1];
1150 89646772 : l1--;
1151 : }
1152 : }
1153 :
1154 145767577 : while (l0 >= 0)
1155 : {
1156 109480190 : val[l0] = op0[l0] ^ op1[l0];
1157 109480190 : l0--;
1158 : }
1159 :
1160 36287387 : return canonize (val, len, prec);
1161 36287387 : }
1162 :
1163 : /*
1164 : * math
1165 : */
1166 :
1167 : /* Set VAL to OP0 + OP1. If OVERFLOW is nonnull, record in *OVERFLOW
1168 : whether the result overflows when OP0 and OP1 are treated as having
1169 : signedness SGN. Return the number of blocks in VAL. */
1170 : unsigned int
1171 132618743 : wi::add_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
1172 : unsigned int op0len, const HOST_WIDE_INT *op1,
1173 : unsigned int op1len, unsigned int prec,
1174 : signop sgn, wi::overflow_type *overflow)
1175 : {
1176 132618743 : unsigned HOST_WIDE_INT o0 = 0;
1177 132618743 : unsigned HOST_WIDE_INT o1 = 0;
1178 132618743 : unsigned HOST_WIDE_INT x = 0;
1179 132618743 : unsigned HOST_WIDE_INT carry = 0;
1180 132618743 : unsigned HOST_WIDE_INT old_carry = 0;
1181 132618743 : unsigned HOST_WIDE_INT mask0, mask1;
1182 132618743 : unsigned int i;
1183 :
1184 132618743 : unsigned int len = MAX (op0len, op1len);
1185 132618743 : mask0 = -top_bit_of (op0, op0len, prec);
1186 132618743 : mask1 = -top_bit_of (op1, op1len, prec);
1187 : /* Add all of the explicitly defined elements. */
1188 :
1189 411339573 : for (i = 0; i < len; i++)
1190 : {
1191 278720830 : o0 = i < op0len ? (unsigned HOST_WIDE_INT) op0[i] : mask0;
1192 278720830 : o1 = i < op1len ? (unsigned HOST_WIDE_INT) op1[i] : mask1;
1193 278720830 : x = o0 + o1 + carry;
1194 278720830 : val[i] = x;
1195 278720830 : old_carry = carry;
1196 278720830 : carry = carry == 0 ? x < o0 : x <= o0;
1197 : }
1198 :
1199 132618743 : if (len * HOST_BITS_PER_WIDE_INT < prec)
1200 : {
1201 127629934 : val[len] = mask0 + mask1 + carry;
1202 127629934 : len++;
1203 127629934 : if (overflow)
1204 58912375 : *overflow
1205 117764110 : = (sgn == UNSIGNED && carry) ? wi::OVF_OVERFLOW : wi::OVF_NONE;
1206 : }
1207 4988809 : else if (overflow)
1208 : {
1209 474334 : unsigned int shift = -prec % HOST_BITS_PER_WIDE_INT;
1210 474334 : if (sgn == SIGNED)
1211 : {
1212 190067 : unsigned HOST_WIDE_INT x = (val[len - 1] ^ o0) & (val[len - 1] ^ o1);
1213 190067 : if ((HOST_WIDE_INT) (x << shift) < 0)
1214 : {
1215 19490 : if (o0 > (unsigned HOST_WIDE_INT) val[len - 1])
1216 8676 : *overflow = wi::OVF_UNDERFLOW;
1217 10814 : else if (o0 < (unsigned HOST_WIDE_INT) val[len - 1])
1218 10814 : *overflow = wi::OVF_OVERFLOW;
1219 : else
1220 0 : *overflow = wi::OVF_NONE;
1221 : }
1222 : else
1223 170577 : *overflow = wi::OVF_NONE;
1224 : }
1225 : else
1226 : {
1227 : /* Put the MSB of X and O0 and in the top of the HWI. */
1228 284267 : x <<= shift;
1229 284267 : o0 <<= shift;
1230 284267 : if (old_carry)
1231 161088 : *overflow = (x <= o0) ? wi::OVF_OVERFLOW : wi::OVF_NONE;
1232 : else
1233 395932 : *overflow = (x < o0) ? wi::OVF_OVERFLOW : wi::OVF_NONE;
1234 : }
1235 : }
1236 :
1237 132618743 : return canonize (val, len, prec);
1238 : }
1239 :
1240 : /* Subroutines of the multiplication and division operations. Unpack
1241 : the first IN_LEN HOST_WIDE_INTs in INPUT into 2 * IN_LEN
1242 : HOST_HALF_WIDE_INTs of RESULT. The rest of RESULT is filled by
1243 : uncompressing the top bit of INPUT[IN_LEN - 1]. */
1244 : static void
1245 73564680 : wi_unpack (unsigned HOST_HALF_WIDE_INT *result, const HOST_WIDE_INT *input,
1246 : unsigned int in_len, unsigned int out_len,
1247 : unsigned int prec, signop sgn)
1248 : {
1249 73564680 : unsigned int i;
1250 73564680 : unsigned int j = 0;
1251 73564680 : unsigned int small_prec = prec & (HOST_BITS_PER_WIDE_INT - 1);
1252 73564680 : unsigned int blocks_needed = BLOCKS_NEEDED (prec);
1253 73564680 : HOST_WIDE_INT mask;
1254 :
1255 73564680 : if (sgn == SIGNED)
1256 : {
1257 0 : mask = -top_bit_of ((const HOST_WIDE_INT *) input, in_len, prec);
1258 0 : mask &= HALF_INT_MASK;
1259 : }
1260 : else
1261 : mask = 0;
1262 :
1263 159733584 : for (i = 0; i < blocks_needed - 1; i++)
1264 : {
1265 86168904 : HOST_WIDE_INT x = safe_uhwi (input, in_len, i);
1266 86168904 : result[j++] = x;
1267 86168904 : result[j++] = x >> HOST_BITS_PER_HALF_WIDE_INT;
1268 : }
1269 :
1270 73564680 : HOST_WIDE_INT x = safe_uhwi (input, in_len, i);
1271 73564680 : if (small_prec)
1272 : {
1273 33642 : if (sgn == SIGNED)
1274 0 : x = sext_hwi (x, small_prec);
1275 : else
1276 33642 : x = zext_hwi (x, small_prec);
1277 : }
1278 73564680 : result[j++] = x;
1279 73564680 : result[j++] = x >> HOST_BITS_PER_HALF_WIDE_INT;
1280 :
1281 : /* Smear the sign bit. */
1282 73564680 : while (j < out_len)
1283 0 : result[j++] = mask;
1284 73564680 : }
1285 :
1286 : /* The inverse of wi_unpack. IN_LEN is the number of input
1287 : blocks and PRECISION is the precision of the result. Return the
1288 : number of blocks in the canonicalized result. */
1289 : static unsigned int
1290 39118658 : wi_pack (HOST_WIDE_INT *result,
1291 : const unsigned HOST_HALF_WIDE_INT *input,
1292 : unsigned int in_len, unsigned int precision)
1293 : {
1294 39118658 : unsigned int i = 0;
1295 39118658 : unsigned int j = 0;
1296 39118658 : unsigned int blocks_needed = BLOCKS_NEEDED (precision);
1297 :
1298 119500903 : while (i + 1 < in_len)
1299 : {
1300 80382245 : result[j++] = ((unsigned HOST_WIDE_INT) input[i]
1301 80382245 : | ((unsigned HOST_WIDE_INT) input[i + 1]
1302 80382245 : << HOST_BITS_PER_HALF_WIDE_INT));
1303 80382245 : i += 2;
1304 : }
1305 :
1306 : /* Handle the case where in_len is odd. For this we zero extend. */
1307 39118658 : if (in_len & 1)
1308 2955527 : result[j++] = (unsigned HOST_WIDE_INT) input[i];
1309 36163131 : else if (j < blocks_needed)
1310 1842832 : result[j++] = 0;
1311 39118658 : return canonize (result, j, precision);
1312 : }
1313 :
1314 : /* Multiply Op1 by Op2. If HIGH is set, only the upper half of the
1315 : result is returned.
1316 :
1317 : If HIGH is not set, throw away the upper half after the check is
1318 : made to see if it overflows. Unfortunately there is no better way
1319 : to check for overflow than to do this. If OVERFLOW is nonnull,
1320 : record in *OVERFLOW whether the result overflowed. SGN controls
1321 : the signedness and is used to check overflow or if HIGH is set.
1322 :
1323 : NOTE: Overflow type for signed overflow is not yet implemented. */
1324 : unsigned int
1325 1644068698 : wi::mul_internal (HOST_WIDE_INT *val, const HOST_WIDE_INT *op1val,
1326 : unsigned int op1len, const HOST_WIDE_INT *op2val,
1327 : unsigned int op2len, unsigned int prec, signop sgn,
1328 : wi::overflow_type *overflow, bool high)
1329 : {
1330 1644068698 : unsigned HOST_WIDE_INT o0, o1, k, t;
1331 1644068698 : unsigned int i;
1332 1644068698 : unsigned int j;
1333 :
1334 : /* If the top level routine did not really pass in an overflow, then
1335 : just make sure that we never attempt to set it. */
1336 1644068698 : bool needs_overflow = (overflow != 0);
1337 1644068698 : if (needs_overflow)
1338 480085048 : *overflow = wi::OVF_NONE;
1339 :
1340 1644068698 : wide_int_ref op1 = wi::storage_ref (op1val, op1len, prec);
1341 1644068698 : wide_int_ref op2 = wi::storage_ref (op2val, op2len, prec);
1342 :
1343 : /* This is a surprisingly common case, so do it first. */
1344 1644068698 : if (op1 == 0 || op2 == 0)
1345 : {
1346 660919158 : val[0] = 0;
1347 660919158 : return 1;
1348 : }
1349 :
1350 : #ifdef umul_ppmm
1351 983149540 : if (sgn == UNSIGNED)
1352 : {
1353 : /* If the inputs are single HWIs and the output has room for at
1354 : least two HWIs, we can use umul_ppmm directly. */
1355 955114959 : if (prec >= HOST_BITS_PER_WIDE_INT * 2
1356 887901374 : && wi::fits_uhwi_p (op1)
1357 1808748343 : && wi::fits_uhwi_p (op2))
1358 : {
1359 : /* This case never overflows. */
1360 852416083 : if (high)
1361 : {
1362 0 : val[0] = 0;
1363 0 : return 1;
1364 : }
1365 852416083 : umul_ppmm (val[1], val[0], op1.ulow (), op2.ulow ());
1366 852416083 : if (val[1] < 0 && prec > HOST_BITS_PER_WIDE_INT * 2)
1367 : {
1368 208402 : val[2] = 0;
1369 208402 : return 3;
1370 : }
1371 865190262 : return 1 + (val[1] != 0 || val[0] < 0);
1372 : }
1373 : /* Likewise if the output is a full single HWI, except that the
1374 : upper HWI of the result is only used for determining overflow.
1375 : (We handle this case inline when overflow isn't needed.) */
1376 102698876 : else if (prec == HOST_BITS_PER_WIDE_INT)
1377 : {
1378 56723999 : unsigned HOST_WIDE_INT upper;
1379 56723999 : umul_ppmm (upper, val[0], op1.ulow (), op2.ulow ());
1380 56723999 : if (needs_overflow)
1381 : /* Unsigned overflow can only be +OVERFLOW. */
1382 110441556 : *overflow = (upper != 0) ? wi::OVF_OVERFLOW : wi::OVF_NONE;
1383 56723999 : if (high)
1384 0 : val[0] = upper;
1385 : return 1;
1386 : }
1387 : }
1388 : #endif
1389 :
1390 : /* Handle multiplications by 1. */
1391 74009458 : if (op1 == 1)
1392 : {
1393 8966212 : if (high)
1394 : {
1395 241 : val[0] = wi::neg_p (op2, sgn) ? -1 : 0;
1396 241 : return 1;
1397 : }
1398 17949504 : for (i = 0; i < op2len; i++)
1399 8983533 : val[i] = op2val[i];
1400 : return op2len;
1401 : }
1402 65043246 : if (op2 == 1)
1403 : {
1404 17810343 : if (high)
1405 : {
1406 0 : val[0] = wi::neg_p (op1, sgn) ? -1 : 0;
1407 0 : return 1;
1408 : }
1409 35718480 : for (i = 0; i < op1len; i++)
1410 17908137 : val[i] = op1val[i];
1411 : return op1len;
1412 : }
1413 :
1414 : /* If we need to check for overflow, we can only do half wide
1415 : multiplies quickly because we need to look at the top bits to
1416 : check for the overflow. */
1417 47232903 : if ((high || needs_overflow)
1418 26195468 : && (prec <= HOST_BITS_PER_HALF_WIDE_INT))
1419 : {
1420 13001630 : unsigned HOST_WIDE_INT r;
1421 :
1422 13001630 : if (sgn == SIGNED)
1423 : {
1424 6087605 : o0 = op1.to_shwi ();
1425 6087605 : o1 = op2.to_shwi ();
1426 : }
1427 : else
1428 : {
1429 6914025 : o0 = op1.to_uhwi ();
1430 6914025 : o1 = op2.to_uhwi ();
1431 : }
1432 :
1433 13001630 : r = o0 * o1;
1434 13001630 : if (needs_overflow)
1435 : {
1436 12996724 : if (sgn == SIGNED)
1437 : {
1438 6083400 : if ((HOST_WIDE_INT) r != sext_hwi (r, prec))
1439 : /* FIXME: Signed overflow type is not implemented yet. */
1440 2423810 : *overflow = OVF_UNKNOWN;
1441 : }
1442 : else
1443 : {
1444 6913324 : if ((r >> prec) != 0)
1445 : /* Unsigned overflow can only be +OVERFLOW. */
1446 4458335 : *overflow = OVF_OVERFLOW;
1447 : }
1448 : }
1449 13001630 : val[0] = high ? r >> prec : r;
1450 13001630 : return 1;
1451 : }
1452 :
1453 : /* The sizes here are scaled to support a 2x WIDE_INT_MAX_INL_PRECISION by 2x
1454 : WIDE_INT_MAX_INL_PRECISION yielding a 4x WIDE_INT_MAX_INL_PRECISION
1455 : result. */
1456 :
1457 13193838 : unsigned HOST_HALF_WIDE_INT
1458 : ubuf[4 * WIDE_INT_MAX_INL_PRECISION / HOST_BITS_PER_HALF_WIDE_INT];
1459 13193838 : unsigned HOST_HALF_WIDE_INT
1460 : vbuf[4 * WIDE_INT_MAX_INL_PRECISION / HOST_BITS_PER_HALF_WIDE_INT];
1461 : /* The '2' in 'R' is because we are internally doing a full
1462 : multiply. */
1463 13193838 : unsigned HOST_HALF_WIDE_INT
1464 : rbuf[2 * 4 * WIDE_INT_MAX_INL_PRECISION / HOST_BITS_PER_HALF_WIDE_INT];
1465 47425105 : const HOST_WIDE_INT mask
1466 : = (HOST_WIDE_INT_1 << HOST_BITS_PER_HALF_WIDE_INT) - 1;
1467 47425105 : unsigned HOST_HALF_WIDE_INT *u = ubuf;
1468 47425105 : unsigned HOST_HALF_WIDE_INT *v = vbuf;
1469 47425105 : unsigned HOST_HALF_WIDE_INT *r = rbuf;
1470 :
1471 13193838 : if (!high)
1472 34231267 : prec = MIN ((op1len + op2len + 1) * HOST_BITS_PER_WIDE_INT, prec);
1473 34231273 : unsigned int blocks_needed = BLOCKS_NEEDED (prec);
1474 34231273 : unsigned int half_blocks_needed = blocks_needed * 2;
1475 34231273 : if (UNLIKELY (prec > WIDE_INT_MAX_INL_PRECISION))
1476 : {
1477 30510 : unsigned HOST_HALF_WIDE_INT *buf
1478 30510 : = XALLOCAVEC (unsigned HOST_HALF_WIDE_INT, 4 * half_blocks_needed);
1479 30510 : u = buf;
1480 30510 : v = u + half_blocks_needed;
1481 30510 : r = v + half_blocks_needed;
1482 : }
1483 :
1484 : /* We do unsigned mul and then correct it. */
1485 34231273 : wi_unpack (u, op1val, op1len, half_blocks_needed, prec, UNSIGNED);
1486 34231273 : wi_unpack (v, op2val, op2len, half_blocks_needed, prec, UNSIGNED);
1487 :
1488 : /* The 2 is for a full mult. */
1489 34231273 : memset (r, 0, half_blocks_needed * 2
1490 34231273 : * HOST_BITS_PER_HALF_WIDE_INT / CHAR_BIT);
1491 :
1492 186129515 : for (j = 0; j < half_blocks_needed; j++)
1493 : {
1494 : k = 0;
1495 11544962246 : for (i = 0; i < half_blocks_needed; i++)
1496 : {
1497 11393064004 : t = ((unsigned HOST_WIDE_INT)u[i] * (unsigned HOST_WIDE_INT)v[j]
1498 11393064004 : + r[i + j] + k);
1499 11393064004 : r[i + j] = t & HALF_INT_MASK;
1500 11393064004 : k = t >> HOST_BITS_PER_HALF_WIDE_INT;
1501 : }
1502 151898242 : r[j + half_blocks_needed] = k;
1503 : }
1504 :
1505 34231273 : unsigned int shift;
1506 34231273 : if ((high || needs_overflow) && (shift = prec % HOST_BITS_PER_WIDE_INT) != 0)
1507 : {
1508 : /* The high or needs_overflow code assumes that the high bits
1509 : only appear from r[half_blocks_needed] up to
1510 : r[half_blocks_needed * 2 - 1]. If prec is not a multiple
1511 : of HOST_BITS_PER_WIDE_INT, shift the bits above prec up
1512 : to make that code simple. */
1513 2944 : if (shift == HOST_BITS_PER_HALF_WIDE_INT)
1514 4 : memmove (&r[half_blocks_needed], &r[half_blocks_needed - 1],
1515 4 : sizeof (r[0]) * half_blocks_needed);
1516 : else
1517 : {
1518 2940 : unsigned int skip = shift < HOST_BITS_PER_HALF_WIDE_INT;
1519 2940 : if (!skip)
1520 2548 : shift -= HOST_BITS_PER_HALF_WIDE_INT;
1521 91774 : for (i = 2 * half_blocks_needed - 1; i >= half_blocks_needed; i--)
1522 88834 : r[i] = ((r[i - skip] << (-shift % HOST_BITS_PER_HALF_WIDE_INT))
1523 88834 : | (r[i - skip - 1] >> shift));
1524 : }
1525 : }
1526 :
1527 : /* We did unsigned math above. For signed we must adjust the
1528 : product (assuming we need to see that). */
1529 34231273 : if (sgn == SIGNED && (high || needs_overflow))
1530 : {
1531 13096388 : unsigned HOST_WIDE_INT b;
1532 13096388 : if (wi::neg_p (op1))
1533 : {
1534 : b = 0;
1535 19631174 : for (i = 0; i < half_blocks_needed; i++)
1536 : {
1537 13157500 : t = (unsigned HOST_WIDE_INT)r[i + half_blocks_needed]
1538 13157500 : - (unsigned HOST_WIDE_INT)v[i] - b;
1539 13157500 : r[i + half_blocks_needed] = t & HALF_INT_MASK;
1540 13157500 : b = t >> (HOST_BITS_PER_WIDE_INT - 1);
1541 : }
1542 : }
1543 13096388 : if (wi::neg_p (op2))
1544 : {
1545 : b = 0;
1546 5491105 : for (i = 0; i < half_blocks_needed; i++)
1547 : {
1548 3681238 : t = (unsigned HOST_WIDE_INT)r[i + half_blocks_needed]
1549 3681238 : - (unsigned HOST_WIDE_INT)u[i] - b;
1550 3681238 : r[i + half_blocks_needed] = t & HALF_INT_MASK;
1551 3681238 : b = t >> (HOST_BITS_PER_WIDE_INT - 1);
1552 : }
1553 : }
1554 : }
1555 :
1556 34231273 : if (needs_overflow)
1557 : {
1558 13193832 : HOST_WIDE_INT top;
1559 :
1560 : /* For unsigned, overflow is true if any of the top bits are set.
1561 : For signed, overflow is true if any of the top bits are not equal
1562 : to the sign bit. */
1563 13193832 : if (sgn == UNSIGNED)
1564 : top = 0;
1565 : else
1566 : {
1567 13096382 : top = r[half_blocks_needed - 1
1568 13096382 : - ((-prec % HOST_BITS_PER_WIDE_INT)
1569 13096382 : >= HOST_BITS_PER_HALF_WIDE_INT)];
1570 13096382 : top = SIGN_MASK (((unsigned HOST_WIDE_INT) top)
1571 : << (HOST_BITS_PER_WIDE_INT / 2
1572 : + (-prec % HOST_BITS_PER_HALF_WIDE_INT)));
1573 13096382 : top &= mask;
1574 : }
1575 :
1576 13193832 : unsigned int end = half_blocks_needed * 2;
1577 13193832 : shift = prec % HOST_BITS_PER_WIDE_INT;
1578 13193832 : if (shift)
1579 : {
1580 : /* For overflow checking only look at the first prec bits
1581 : starting with r[half_blocks_needed]. */
1582 2944 : if (shift <= HOST_BITS_PER_HALF_WIDE_INT)
1583 396 : --end;
1584 2944 : shift %= HOST_BITS_PER_HALF_WIDE_INT;
1585 2944 : if (shift)
1586 : {
1587 2940 : if (top)
1588 1292 : r[end - 1] |= ((~(unsigned HOST_HALF_WIDE_INT) 0) << shift);
1589 : else
1590 1648 : r[end - 1] &= (((unsigned HOST_HALF_WIDE_INT) 1) << shift) - 1;
1591 : }
1592 : }
1593 49405182 : for (i = half_blocks_needed; i < end; i++)
1594 36211350 : if (((HOST_WIDE_INT)(r[i] & mask)) != top)
1595 : /* FIXME: Signed overflow type is not implemented yet. */
1596 17576069 : *overflow = (sgn == UNSIGNED) ? wi::OVF_OVERFLOW : wi::OVF_UNKNOWN;
1597 : }
1598 :
1599 34231273 : int r_offset = high ? half_blocks_needed : 0;
1600 34231273 : return wi_pack (val, &r[r_offset], half_blocks_needed, prec);
1601 : }
1602 :
1603 : /* Compute the population count of X. */
1604 : int
1605 147108522 : wi::popcount (const wide_int_ref &x)
1606 : {
1607 147108522 : unsigned int i;
1608 147108522 : int count;
1609 :
1610 : /* The high order block is special if it is the last block and the
1611 : precision is not an even multiple of HOST_BITS_PER_WIDE_INT. We
1612 : have to clear out any ones above the precision before doing
1613 : popcount on this block. */
1614 147108522 : count = x.precision - x.len * HOST_BITS_PER_WIDE_INT;
1615 147108522 : unsigned int stop = x.len;
1616 147108522 : if (count < 0)
1617 : {
1618 62483466 : count = popcount_hwi (x.uhigh () << -count);
1619 62483466 : stop -= 1;
1620 : }
1621 : else
1622 : {
1623 84625056 : if (x.sign_mask () >= 0)
1624 70017721 : count = 0;
1625 : }
1626 :
1627 232376509 : for (i = 0; i < stop; ++i)
1628 85267987 : count += popcount_hwi (x.val[i]);
1629 :
1630 147108522 : return count;
1631 : }
1632 :
1633 : /* Set VAL to OP0 - OP1. If OVERFLOW is nonnull, record in *OVERFLOW
1634 : whether the result overflows when OP0 and OP1 are treated as having
1635 : signedness SGN. Return the number of blocks in VAL. */
1636 : unsigned int
1637 55350969 : wi::sub_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
1638 : unsigned int op0len, const HOST_WIDE_INT *op1,
1639 : unsigned int op1len, unsigned int prec,
1640 : signop sgn, wi::overflow_type *overflow)
1641 : {
1642 55350969 : unsigned HOST_WIDE_INT o0 = 0;
1643 55350969 : unsigned HOST_WIDE_INT o1 = 0;
1644 55350969 : unsigned HOST_WIDE_INT x = 0;
1645 : /* We implement subtraction as an in place negate and add. Negation
1646 : is just inversion and add 1, so we can do the add of 1 by just
1647 : starting the borrow in of the first element at 1. */
1648 55350969 : unsigned HOST_WIDE_INT borrow = 0;
1649 55350969 : unsigned HOST_WIDE_INT old_borrow = 0;
1650 :
1651 55350969 : unsigned HOST_WIDE_INT mask0, mask1;
1652 55350969 : unsigned int i;
1653 :
1654 55350969 : unsigned int len = MAX (op0len, op1len);
1655 55350969 : mask0 = -top_bit_of (op0, op0len, prec);
1656 55350969 : mask1 = -top_bit_of (op1, op1len, prec);
1657 :
1658 : /* Subtract all of the explicitly defined elements. */
1659 166163368 : for (i = 0; i < len; i++)
1660 : {
1661 110812399 : o0 = i < op0len ? (unsigned HOST_WIDE_INT)op0[i] : mask0;
1662 110812399 : o1 = i < op1len ? (unsigned HOST_WIDE_INT)op1[i] : mask1;
1663 110812399 : x = o0 - o1 - borrow;
1664 110812399 : val[i] = x;
1665 110812399 : old_borrow = borrow;
1666 110812399 : borrow = borrow == 0 ? o0 < o1 : o0 <= o1;
1667 : }
1668 :
1669 55350969 : if (len * HOST_BITS_PER_WIDE_INT < prec)
1670 : {
1671 52142271 : val[len] = mask0 - mask1 - borrow;
1672 52142271 : len++;
1673 52142271 : if (overflow)
1674 1470558 : *overflow = (sgn == UNSIGNED && borrow) ? OVF_UNDERFLOW : OVF_NONE;
1675 : }
1676 3208698 : else if (overflow)
1677 : {
1678 336777 : unsigned int shift = -prec % HOST_BITS_PER_WIDE_INT;
1679 336777 : if (sgn == SIGNED)
1680 : {
1681 247678 : unsigned HOST_WIDE_INT x = (o0 ^ o1) & (val[len - 1] ^ o0);
1682 247678 : if ((HOST_WIDE_INT) (x << shift) < 0)
1683 : {
1684 6717 : if (o0 > o1)
1685 2709 : *overflow = OVF_UNDERFLOW;
1686 4008 : else if (o0 < o1)
1687 4008 : *overflow = OVF_OVERFLOW;
1688 : else
1689 0 : *overflow = OVF_NONE;
1690 : }
1691 : else
1692 240961 : *overflow = OVF_NONE;
1693 : }
1694 : else
1695 : {
1696 : /* Put the MSB of X and O0 and in the top of the HWI. */
1697 89099 : x <<= shift;
1698 89099 : o0 <<= shift;
1699 89099 : if (old_borrow)
1700 108258 : *overflow = (x >= o0) ? OVF_UNDERFLOW : OVF_NONE;
1701 : else
1702 53413 : *overflow = (x > o0) ? OVF_UNDERFLOW : OVF_NONE;
1703 : }
1704 : }
1705 :
1706 55350969 : return canonize (val, len, prec);
1707 : }
1708 :
1709 :
1710 : /*
1711 : * Division and Mod
1712 : */
1713 :
1714 : /* Compute B_QUOTIENT and B_REMAINDER from B_DIVIDEND/B_DIVISOR. The
1715 : algorithm is a small modification of the algorithm in Hacker's
1716 : Delight by Warren, which itself is a small modification of Knuth's
1717 : algorithm. M is the number of significant elements of U however
1718 : there needs to be at least one extra element of B_DIVIDEND
1719 : allocated, N is the number of elements of B_DIVISOR.
1720 : Return new value for N. */
1721 : static int
1722 2551067 : divmod_internal_2 (unsigned HOST_HALF_WIDE_INT *b_quotient,
1723 : unsigned HOST_HALF_WIDE_INT *b_remainder,
1724 : unsigned HOST_HALF_WIDE_INT *b_dividend,
1725 : unsigned HOST_HALF_WIDE_INT *b_divisor,
1726 : int m, int n)
1727 : {
1728 : /* The "digits" are a HOST_HALF_WIDE_INT which the size of half of a
1729 : HOST_WIDE_INT and stored in the lower bits of each word. This
1730 : algorithm should work properly on both 32 and 64 bit
1731 : machines. */
1732 2551067 : unsigned HOST_WIDE_INT b = HOST_WIDE_INT_1U << HOST_BITS_PER_HALF_WIDE_INT;
1733 2551067 : unsigned HOST_WIDE_INT qhat; /* Estimate of quotient digit. */
1734 2551067 : unsigned HOST_WIDE_INT rhat; /* A remainder. */
1735 2551067 : unsigned HOST_WIDE_INT p; /* Product of two digits. */
1736 2551067 : HOST_WIDE_INT t, k;
1737 2551067 : int i, j, s;
1738 :
1739 : /* Single digit divisor. */
1740 2551067 : if (n == 1)
1741 : {
1742 750216 : k = 0;
1743 3082054 : for (j = m - 1; j >= 0; j--)
1744 : {
1745 2331838 : b_quotient[j] = (k * b + b_dividend[j])/b_divisor[0];
1746 2331838 : k = ((k * b + b_dividend[j])
1747 2331838 : - ((unsigned HOST_WIDE_INT)b_quotient[j]
1748 2331838 : * (unsigned HOST_WIDE_INT)b_divisor[0]));
1749 : }
1750 750216 : b_remainder[0] = k;
1751 750216 : return 1;
1752 : }
1753 :
1754 1800851 : s = clz_hwi (b_divisor[n-1]) - HOST_BITS_PER_HALF_WIDE_INT; /* CHECK clz */
1755 :
1756 1800851 : if (s)
1757 : {
1758 : /* Normalize B_DIVIDEND and B_DIVISOR. Unlike the published
1759 : algorithm, we can overwrite b_dividend and b_divisor, so we do
1760 : that. */
1761 3656789 : for (i = n - 1; i > 0; i--)
1762 1860398 : b_divisor[i] = (b_divisor[i] << s)
1763 1860398 : | (b_divisor[i-1] >> (HOST_BITS_PER_HALF_WIDE_INT - s));
1764 1796391 : b_divisor[0] = b_divisor[0] << s;
1765 :
1766 1796391 : b_dividend[m] = b_dividend[m-1] >> (HOST_BITS_PER_HALF_WIDE_INT - s);
1767 5446004 : for (i = m - 1; i > 0; i--)
1768 3649613 : b_dividend[i] = (b_dividend[i] << s)
1769 3649613 : | (b_dividend[i-1] >> (HOST_BITS_PER_HALF_WIDE_INT - s));
1770 1796391 : b_dividend[0] = b_dividend[0] << s;
1771 : }
1772 :
1773 : /* Main loop. */
1774 5399834 : for (j = m - n; j >= 0; j--)
1775 : {
1776 3598983 : qhat = (b_dividend[j+n] * b + b_dividend[j+n-1]) / b_divisor[n-1];
1777 3598983 : rhat = (b_dividend[j+n] * b + b_dividend[j+n-1]) - qhat * b_divisor[n-1];
1778 3613892 : again:
1779 3613892 : if (qhat >= b || qhat * b_divisor[n-2] > b * rhat + b_dividend[j+n-2])
1780 : {
1781 17740 : qhat -= 1;
1782 17740 : rhat += b_divisor[n-1];
1783 17740 : if (rhat < b)
1784 14909 : goto again;
1785 : }
1786 :
1787 : /* Multiply and subtract. */
1788 3598983 : k = 0;
1789 10949332 : for (i = 0; i < n; i++)
1790 : {
1791 7350349 : p = qhat * b_divisor[i];
1792 7350349 : t = b_dividend[i+j] - k - (p & HALF_INT_MASK);
1793 7350349 : b_dividend[i + j] = t;
1794 7350349 : k = ((p >> HOST_BITS_PER_HALF_WIDE_INT)
1795 7350349 : - (t >> HOST_BITS_PER_HALF_WIDE_INT));
1796 : }
1797 3598983 : t = b_dividend[j+n] - k;
1798 3598983 : b_dividend[j+n] = t;
1799 :
1800 3598983 : b_quotient[j] = qhat;
1801 3598983 : if (t < 0)
1802 : {
1803 7776 : b_quotient[j] -= 1;
1804 7776 : k = 0;
1805 64418 : for (i = 0; i < n; i++)
1806 : {
1807 56642 : t = (HOST_WIDE_INT)b_dividend[i+j] + b_divisor[i] + k;
1808 56642 : b_dividend[i+j] = t;
1809 56642 : k = t >> HOST_BITS_PER_HALF_WIDE_INT;
1810 : }
1811 7776 : b_dividend[j+n] += k;
1812 : }
1813 : }
1814 : /* If N > M, the main loop was skipped, quotient will be 0 and
1815 : we can't copy more than M half-limbs into the remainder, as they
1816 : aren't present in b_dividend (which has . */
1817 1800851 : n = MIN (n, m);
1818 1800851 : if (s)
1819 5442882 : for (i = 0; i < n; i++)
1820 3646491 : b_remainder[i] = (b_dividend[i] >> s)
1821 3646491 : | (b_dividend[i+1] << (HOST_BITS_PER_HALF_WIDE_INT - s));
1822 : else
1823 16973 : for (i = 0; i < n; i++)
1824 12513 : b_remainder[i] = b_dividend[i];
1825 : return n;
1826 : }
1827 :
1828 :
1829 : /* Divide DIVIDEND by DIVISOR, which have signedness SGN, and truncate
1830 : the result. If QUOTIENT is nonnull, store the value of the quotient
1831 : there and return the number of blocks in it. The return value is
1832 : not defined otherwise. If REMAINDER is nonnull, store the value
1833 : of the remainder there and store the number of blocks in
1834 : *REMAINDER_LEN. If OFLOW is not null, store in *OFLOW whether
1835 : the division overflowed. */
1836 : unsigned int
1837 673806942 : wi::divmod_internal (HOST_WIDE_INT *quotient, unsigned int *remainder_len,
1838 : HOST_WIDE_INT *remainder,
1839 : const HOST_WIDE_INT *dividend_val,
1840 : unsigned int dividend_len, unsigned int dividend_prec,
1841 : const HOST_WIDE_INT *divisor_val, unsigned int divisor_len,
1842 : unsigned int divisor_prec, signop sgn,
1843 : wi::overflow_type *oflow)
1844 : {
1845 673806942 : unsigned int m, n;
1846 673806942 : bool dividend_neg = false;
1847 673806942 : bool divisor_neg = false;
1848 673806942 : bool overflow = false;
1849 673806942 : wide_int neg_dividend, neg_divisor;
1850 :
1851 673806942 : wide_int_ref dividend = wi::storage_ref (dividend_val, dividend_len,
1852 673806942 : dividend_prec);
1853 673806942 : wide_int_ref divisor = wi::storage_ref (divisor_val, divisor_len,
1854 673806942 : divisor_prec);
1855 673806942 : if (divisor == 0)
1856 : overflow = true;
1857 :
1858 : /* The smallest signed number / -1 causes overflow. The dividend_len
1859 : check is for speed rather than correctness. */
1860 673806942 : if (sgn == SIGNED
1861 56115095 : && dividend_len == BLOCKS_NEEDED (dividend_prec)
1862 22155178 : && divisor == -1
1863 674642246 : && wi::only_sign_bit_p (dividend))
1864 211904 : overflow = true;
1865 :
1866 : /* Handle the overflow cases. Viewed as unsigned value, the quotient of
1867 : (signed min / -1) has the same representation as the original dividend.
1868 : We have traditionally made division by zero act as division by one,
1869 : so there too we use the original dividend. */
1870 673806942 : if (overflow)
1871 : {
1872 214162 : if (remainder)
1873 : {
1874 3592 : *remainder_len = 1;
1875 3592 : remainder[0] = 0;
1876 : }
1877 214162 : if (oflow)
1878 214056 : *oflow = OVF_OVERFLOW;
1879 214162 : if (quotient)
1880 427355 : for (unsigned int i = 0; i < dividend_len; ++i)
1881 214434 : quotient[i] = dividend_val[i];
1882 : return dividend_len;
1883 : }
1884 :
1885 673592780 : if (oflow)
1886 619835372 : *oflow = OVF_NONE;
1887 :
1888 : /* Do it on the host if you can. */
1889 673592780 : if (sgn == SIGNED
1890 55901116 : && wi::fits_shwi_p (dividend)
1891 729391235 : && wi::fits_shwi_p (divisor))
1892 : {
1893 55798002 : HOST_WIDE_INT o0 = dividend.to_shwi ();
1894 55798002 : HOST_WIDE_INT o1 = divisor.to_shwi ();
1895 :
1896 55798002 : if (o0 == HOST_WIDE_INT_MIN && o1 == -1)
1897 : {
1898 0 : gcc_checking_assert (dividend_prec > HOST_BITS_PER_WIDE_INT);
1899 0 : if (quotient)
1900 : {
1901 0 : quotient[0] = HOST_WIDE_INT_MIN;
1902 0 : quotient[1] = 0;
1903 : }
1904 0 : if (remainder)
1905 : {
1906 0 : remainder[0] = 0;
1907 0 : *remainder_len = 1;
1908 : }
1909 : return 2;
1910 : }
1911 : else
1912 : {
1913 55798002 : if (quotient)
1914 34067460 : quotient[0] = o0 / o1;
1915 55798002 : if (remainder)
1916 : {
1917 22436422 : remainder[0] = o0 % o1;
1918 22436422 : *remainder_len = 1;
1919 : }
1920 : return 1;
1921 : }
1922 : }
1923 :
1924 617794778 : if (sgn == UNSIGNED
1925 617691664 : && wi::fits_uhwi_p (dividend)
1926 1233042414 : && wi::fits_uhwi_p (divisor))
1927 : {
1928 615243711 : unsigned HOST_WIDE_INT o0 = dividend.to_uhwi ();
1929 615243711 : unsigned HOST_WIDE_INT o1 = divisor.to_uhwi ();
1930 615243711 : unsigned int quotient_len = 1;
1931 :
1932 615243711 : if (quotient)
1933 : {
1934 604686880 : quotient[0] = o0 / o1;
1935 604686880 : quotient_len = canonize_uhwi (quotient, dividend_prec);
1936 : }
1937 615243711 : if (remainder)
1938 : {
1939 251750073 : remainder[0] = o0 % o1;
1940 251750940 : *remainder_len = canonize_uhwi (remainder, dividend_prec);
1941 : }
1942 : return quotient_len;
1943 : }
1944 :
1945 : /* Make the divisor and dividend positive and remember what we
1946 : did. */
1947 2551067 : if (sgn == SIGNED)
1948 : {
1949 103114 : if (wi::neg_p (dividend))
1950 : {
1951 13521 : neg_dividend = -dividend;
1952 13521 : dividend = neg_dividend;
1953 13521 : dividend_neg = true;
1954 : }
1955 103114 : if (wi::neg_p (divisor))
1956 : {
1957 4261 : neg_divisor = -divisor;
1958 4261 : divisor = neg_divisor;
1959 4261 : divisor_neg = true;
1960 : }
1961 : }
1962 :
1963 : unsigned HOST_HALF_WIDE_INT
1964 : b_quotient_buf[4 * WIDE_INT_MAX_INL_PRECISION
1965 : / HOST_BITS_PER_HALF_WIDE_INT];
1966 : unsigned HOST_HALF_WIDE_INT
1967 : b_remainder_buf[4 * WIDE_INT_MAX_INL_PRECISION
1968 : / HOST_BITS_PER_HALF_WIDE_INT];
1969 : unsigned HOST_HALF_WIDE_INT
1970 : b_dividend_buf[(4 * WIDE_INT_MAX_INL_PRECISION
1971 : / HOST_BITS_PER_HALF_WIDE_INT) + 1];
1972 : unsigned HOST_HALF_WIDE_INT
1973 : b_divisor_buf[4 * WIDE_INT_MAX_INL_PRECISION
1974 : / HOST_BITS_PER_HALF_WIDE_INT];
1975 4947439 : unsigned HOST_HALF_WIDE_INT *b_quotient = b_quotient_buf;
1976 4947439 : unsigned HOST_HALF_WIDE_INT *b_remainder = b_remainder_buf;
1977 4947439 : unsigned HOST_HALF_WIDE_INT *b_dividend = b_dividend_buf;
1978 4947439 : unsigned HOST_HALF_WIDE_INT *b_divisor = b_divisor_buf;
1979 :
1980 2447953 : if (sgn == SIGNED || dividend_val[dividend_len - 1] >= 0)
1981 2499486 : dividend_prec = MIN ((dividend_len + 1) * HOST_BITS_PER_WIDE_INT,
1982 : dividend_prec);
1983 2551067 : if (sgn == SIGNED || divisor_val[divisor_len - 1] >= 0)
1984 2548891 : divisor_prec = MIN (divisor_len * HOST_BITS_PER_WIDE_INT, divisor_prec);
1985 2551067 : unsigned int dividend_blocks_needed = 2 * BLOCKS_NEEDED (dividend_prec);
1986 2551067 : unsigned int divisor_blocks_needed = 2 * BLOCKS_NEEDED (divisor_prec);
1987 2551067 : if (UNLIKELY (dividend_prec > WIDE_INT_MAX_INL_PRECISION)
1988 2550367 : || UNLIKELY (divisor_prec > WIDE_INT_MAX_INL_PRECISION))
1989 : {
1990 773 : unsigned HOST_HALF_WIDE_INT *buf
1991 773 : = XALLOCAVEC (unsigned HOST_HALF_WIDE_INT,
1992 : 3 * dividend_blocks_needed + 1
1993 : + divisor_blocks_needed);
1994 773 : b_quotient = buf;
1995 773 : b_remainder = b_quotient + dividend_blocks_needed;
1996 773 : b_dividend = b_remainder + dividend_blocks_needed;
1997 773 : b_divisor = b_dividend + dividend_blocks_needed + 1;
1998 773 : memset (b_quotient, 0,
1999 : dividend_blocks_needed * sizeof (HOST_HALF_WIDE_INT));
2000 : }
2001 2551067 : wi_unpack (b_dividend, dividend.get_val (), dividend.get_len (),
2002 : dividend_blocks_needed, dividend_prec, UNSIGNED);
2003 2551067 : wi_unpack (b_divisor, divisor.get_val (), divisor.get_len (),
2004 : divisor_blocks_needed, divisor_prec, UNSIGNED);
2005 :
2006 2551067 : m = dividend_blocks_needed;
2007 2551067 : b_dividend[m] = 0;
2008 5228772 : while (m > 1 && b_dividend[m - 1] == 0)
2009 : m--;
2010 :
2011 : n = divisor_blocks_needed;
2012 3311793 : while (n > 1 && b_divisor[n - 1] == 0)
2013 : n--;
2014 :
2015 2551067 : if (b_quotient == b_quotient_buf)
2016 2550294 : memset (b_quotient_buf, 0, sizeof (b_quotient_buf));
2017 :
2018 2551067 : n = divmod_internal_2 (b_quotient, b_remainder, b_dividend, b_divisor, m, n);
2019 :
2020 2551067 : unsigned int quotient_len = 0;
2021 2551067 : if (quotient)
2022 : {
2023 2489161 : quotient_len = wi_pack (quotient, b_quotient, m, dividend_prec);
2024 : /* The quotient is neg if exactly one of the divisor or dividend is
2025 : neg. */
2026 2489161 : if (dividend_neg != divisor_neg)
2027 12457 : quotient_len = wi::sub_large (quotient, zeros, 1, quotient,
2028 : quotient_len, dividend_prec,
2029 : UNSIGNED, 0);
2030 : }
2031 :
2032 2551067 : if (remainder)
2033 : {
2034 2398224 : *remainder_len = wi_pack (remainder, b_remainder, n, dividend_prec);
2035 : /* The remainder is always the same sign as the dividend. */
2036 2398224 : if (dividend_neg)
2037 2083 : *remainder_len = wi::sub_large (remainder, zeros, 1, remainder,
2038 : *remainder_len, dividend_prec,
2039 : UNSIGNED, 0);
2040 : }
2041 :
2042 : return quotient_len;
2043 673806942 : }
2044 :
2045 : /*
2046 : * Shifting, rotating and extraction.
2047 : */
2048 :
2049 : /* Left shift XVAL by SHIFT and store the result in VAL. Return the
2050 : number of blocks in VAL. Both XVAL and VAL have PRECISION bits. */
2051 : unsigned int
2052 1901884919 : wi::lshift_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
2053 : unsigned int xlen, unsigned int precision,
2054 : unsigned int shift)
2055 : {
2056 : /* Split the shift into a whole-block shift and a subblock shift. */
2057 1901884919 : unsigned int skip = shift / HOST_BITS_PER_WIDE_INT;
2058 1901884919 : unsigned int small_shift = shift % HOST_BITS_PER_WIDE_INT;
2059 :
2060 : /* The whole-block shift fills with zeros. */
2061 1901884919 : unsigned int len = BLOCKS_NEEDED (precision);
2062 1901884919 : len = MIN (xlen + skip + 1, len);
2063 1903862644 : for (unsigned int i = 0; i < skip; ++i)
2064 1977725 : val[i] = 0;
2065 :
2066 : /* It's easier to handle the simple block case specially. */
2067 1901884919 : if (small_shift == 0)
2068 52880208 : for (unsigned int i = skip; i < len; ++i)
2069 93175252 : val[i] = safe_uhwi (xval, xlen, i - skip);
2070 : else
2071 : {
2072 : /* The first unfilled output block is a left shift of the first
2073 : block in XVAL. The other output blocks contain bits from two
2074 : consecutive input blocks. */
2075 : unsigned HOST_WIDE_INT carry = 0;
2076 5728501344 : for (unsigned int i = skip; i < len; ++i)
2077 : {
2078 3832909007 : unsigned HOST_WIDE_INT x = safe_uhwi (xval, xlen, i - skip);
2079 3832909007 : val[i] = (x << small_shift) | carry;
2080 3832909007 : carry = x >> (-small_shift % HOST_BITS_PER_WIDE_INT);
2081 : }
2082 : }
2083 1901884919 : return canonize (val, len, precision);
2084 : }
2085 :
2086 : /* Right shift XVAL by SHIFT and store the result in VAL. LEN is the
2087 : number of blocks in VAL. The input has XPRECISION bits and the
2088 : output has XPRECISION - SHIFT bits. */
2089 : static void
2090 170889401 : rshift_large_common (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
2091 : unsigned int xlen, unsigned int shift, unsigned int len)
2092 : {
2093 : /* Split the shift into a whole-block shift and a subblock shift. */
2094 170889401 : unsigned int skip = shift / HOST_BITS_PER_WIDE_INT;
2095 170889401 : unsigned int small_shift = shift % HOST_BITS_PER_WIDE_INT;
2096 :
2097 : /* It's easier to handle the simple block case specially. */
2098 170889401 : if (small_shift == 0)
2099 2769112 : for (unsigned int i = 0; i < len; ++i)
2100 3197148 : val[i] = safe_uhwi (xval, xlen, i + skip);
2101 : else
2102 : {
2103 : /* Each output block but the last is a combination of two input blocks.
2104 : The last block is a right shift of the last block in XVAL. */
2105 169718863 : unsigned HOST_WIDE_INT curr = safe_uhwi (xval, xlen, skip);
2106 341107074 : for (unsigned int i = 0; i < len; ++i)
2107 : {
2108 171388211 : val[i] = curr >> small_shift;
2109 171388211 : curr = safe_uhwi (xval, xlen, i + skip + 1);
2110 171388211 : val[i] |= curr << (-small_shift % HOST_BITS_PER_WIDE_INT);
2111 : }
2112 : }
2113 170889401 : }
2114 :
2115 : /* Logically right shift XVAL by SHIFT and store the result in VAL.
2116 : Return the number of blocks in VAL. XVAL has XPRECISION bits and
2117 : VAL has PRECISION bits. */
2118 : unsigned int
2119 2682577 : wi::lrshift_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
2120 : unsigned int xlen, unsigned int xprecision,
2121 : unsigned int precision, unsigned int shift)
2122 : {
2123 : /* Work out how many blocks are needed to store the significant bits
2124 : (excluding the upper zeros or signs). */
2125 2682577 : unsigned int blocks_needed = BLOCKS_NEEDED (xprecision - shift);
2126 2682577 : unsigned int len = blocks_needed;
2127 2682577 : if (len > xlen && xval[xlen - 1] >= 0)
2128 2682577 : len = xlen;
2129 :
2130 2682577 : rshift_large_common (val, xval, xlen, shift, len);
2131 :
2132 : /* The value we just created has precision XPRECISION - SHIFT.
2133 : Zero-extend it to wider precisions. */
2134 2682577 : if (precision > xprecision - shift && len == blocks_needed)
2135 : {
2136 633478 : unsigned int small_prec = (xprecision - shift) % HOST_BITS_PER_WIDE_INT;
2137 633478 : if (small_prec)
2138 49651 : val[len - 1] = zext_hwi (val[len - 1], small_prec);
2139 583827 : else if (val[len - 1] < 0)
2140 : {
2141 : /* Add a new block with a zero. */
2142 257210 : val[len++] = 0;
2143 257210 : return len;
2144 : }
2145 : }
2146 2425367 : return canonize (val, len, precision);
2147 : }
2148 :
2149 : /* Arithmetically right shift XVAL by SHIFT and store the result in VAL.
2150 : Return the number of blocks in VAL. XVAL has XPRECISION bits and
2151 : VAL has PRECISION bits. */
2152 : unsigned int
2153 168206824 : wi::arshift_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
2154 : unsigned int xlen, unsigned int xprecision,
2155 : unsigned int precision, unsigned int shift)
2156 : {
2157 : /* Work out how many blocks are needed to store the significant bits
2158 : (excluding the upper zeros or signs). */
2159 168206824 : unsigned int blocks_needed = BLOCKS_NEEDED (xprecision - shift);
2160 168206824 : unsigned int len = MIN (xlen, blocks_needed);
2161 :
2162 168206824 : rshift_large_common (val, xval, xlen, shift, len);
2163 :
2164 : /* The value we just created has precision XPRECISION - SHIFT.
2165 : Sign-extend it to wider types. */
2166 168206824 : if (precision > xprecision - shift && len == blocks_needed)
2167 : {
2168 43076 : unsigned int small_prec = (xprecision - shift) % HOST_BITS_PER_WIDE_INT;
2169 43076 : if (small_prec)
2170 5934 : val[len - 1] = sext_hwi (val[len - 1], small_prec);
2171 : }
2172 168206824 : return canonize (val, len, precision);
2173 : }
2174 :
2175 : /* Return the number of leading (upper) zeros in X. */
2176 : int
2177 1080668093 : wi::clz (const wide_int_ref &x)
2178 : {
2179 1080668093 : if (x.sign_mask () < 0)
2180 : /* The upper bit is set, so there are no leading zeros. */
2181 : return 0;
2182 :
2183 : /* Calculate how many bits there above the highest represented block. */
2184 620790408 : int count = x.precision - x.len * HOST_BITS_PER_WIDE_INT;
2185 :
2186 620790408 : unsigned HOST_WIDE_INT high = x.uhigh ();
2187 620790408 : if (count < 0)
2188 : /* The upper -COUNT bits of HIGH are not part of the value.
2189 : Clear them out. */
2190 263151629 : high = (high << -count) >> -count;
2191 :
2192 : /* We don't need to look below HIGH. Either HIGH is nonzero,
2193 : or the top bit of the block below is nonzero; clz_hwi is
2194 : HOST_BITS_PER_WIDE_INT in the latter case. */
2195 1237920720 : return count + clz_hwi (high);
2196 : }
2197 :
2198 : /* Return the number of redundant sign bits in X. (That is, the number
2199 : of bits immediately below the sign bit that have the same value as
2200 : the sign bit.) */
2201 : int
2202 39648228 : wi::clrsb (const wide_int_ref &x)
2203 : {
2204 : /* Calculate how many bits there above the highest represented block. */
2205 39648228 : int count = x.precision - x.len * HOST_BITS_PER_WIDE_INT;
2206 :
2207 39648228 : unsigned HOST_WIDE_INT high = x.uhigh ();
2208 39648228 : unsigned HOST_WIDE_INT mask = -1;
2209 39648228 : if (count < 0)
2210 : {
2211 : /* The upper -COUNT bits of HIGH are not part of the value.
2212 : Clear them from both MASK and HIGH. */
2213 2061675 : mask >>= -count;
2214 2061675 : high &= mask;
2215 : }
2216 :
2217 : /* If the top bit is 1, count the number of leading 1s. If the top
2218 : bit is zero, count the number of leading zeros. */
2219 39648228 : if (high > mask / 2)
2220 1496507 : high ^= mask;
2221 :
2222 : /* There are no sign bits below the top block, so we don't need to look
2223 : beyond HIGH. Note that clz_hwi is HOST_BITS_PER_WIDE_INT when
2224 : HIGH is 0. */
2225 39648228 : return count + clz_hwi (high) - 1;
2226 : }
2227 :
2228 : /* Return the number of trailing (lower) zeros in X. */
2229 : int
2230 509905178 : wi::ctz (const wide_int_ref &x)
2231 : {
2232 509905178 : if (x.len == 1 && x.ulow () == 0)
2233 44152653 : return x.precision;
2234 :
2235 : /* Having dealt with the zero case, there must be a block with a
2236 : nonzero bit. We don't care about the bits above the first 1. */
2237 : unsigned int i = 0;
2238 465937829 : while (x.val[i] == 0)
2239 185304 : ++i;
2240 465752525 : return i * HOST_BITS_PER_WIDE_INT + ctz_hwi (x.val[i]);
2241 : }
2242 :
2243 : /* If X is an exact power of 2, return the base-2 logarithm, otherwise
2244 : return -1. */
2245 : int
2246 17483670 : wi::exact_log2 (const wide_int_ref &x)
2247 : {
2248 : /* Reject cases where there are implicit -1 blocks above HIGH. */
2249 17483670 : if (x.len * HOST_BITS_PER_WIDE_INT < x.precision && x.sign_mask () < 0)
2250 : return -1;
2251 :
2252 : /* Set CRUX to the index of the entry that should be nonzero.
2253 : If the top block is zero then the next lowest block (if any)
2254 : must have the high bit set. */
2255 17477934 : unsigned int crux = x.len - 1;
2256 17477934 : if (crux > 0 && x.val[crux] == 0)
2257 23714 : crux -= 1;
2258 :
2259 : /* Check that all lower blocks are zero. */
2260 17478746 : for (unsigned int i = 0; i < crux; ++i)
2261 1870 : if (x.val[i] != 0)
2262 : return -1;
2263 :
2264 : /* Get a zero-extended form of block CRUX. */
2265 17476876 : unsigned HOST_WIDE_INT hwi = x.val[crux];
2266 17476876 : if ((crux + 1) * HOST_BITS_PER_WIDE_INT > x.precision)
2267 4011876 : hwi = zext_hwi (hwi, x.precision % HOST_BITS_PER_WIDE_INT);
2268 :
2269 : /* Now it's down to whether HWI is a power of 2. */
2270 17476876 : int res = ::exact_log2 (hwi);
2271 10613810 : if (res >= 0)
2272 10613810 : res += crux * HOST_BITS_PER_WIDE_INT;
2273 : return res;
2274 : }
2275 :
2276 : /* Return the base-2 logarithm of X, rounding down. Return -1 if X is 0. */
2277 : int
2278 10765902 : wi::floor_log2 (const wide_int_ref &x)
2279 : {
2280 10765902 : return x.precision - 1 - clz (x);
2281 : }
2282 :
2283 : /* Return the index of the first (lowest) set bit in X, counting from 1.
2284 : Return 0 if X is 0. */
2285 : int
2286 491 : wi::ffs (const wide_int_ref &x)
2287 : {
2288 491 : return eq_p (x, 0) ? 0 : ctz (x) + 1;
2289 : }
2290 :
2291 : /* Return true if sign-extending X to have precision PRECISION would give
2292 : the minimum signed value at that precision. */
2293 : bool
2294 37280223 : wi::only_sign_bit_p (const wide_int_ref &x, unsigned int precision)
2295 : {
2296 37280223 : return ctz (x) + 1 == int (precision);
2297 : }
2298 :
2299 : /* Return true if X represents the minimum signed value. */
2300 : bool
2301 35220076 : wi::only_sign_bit_p (const wide_int_ref &x)
2302 : {
2303 35220076 : return only_sign_bit_p (x, x.precision);
2304 : }
2305 :
2306 : /* Return VAL if VAL has no bits set outside MASK. Otherwise round VAL
2307 : down to the previous value that has no bits set outside MASK.
2308 : This rounding wraps for signed values if VAL is negative and
2309 : the top bit of MASK is clear.
2310 :
2311 : For example, round_down_for_mask (6, 0xf1) would give 1 and
2312 : round_down_for_mask (24, 0xf1) would give 17. */
2313 :
2314 : wide_int
2315 17997030 : wi::round_down_for_mask (const wide_int &val, const wide_int &mask)
2316 : {
2317 : /* Get the bits in VAL that are outside the mask. */
2318 17997030 : wide_int extra_bits = wi::bit_and_not (val, mask);
2319 17997030 : if (extra_bits == 0)
2320 17971283 : return val;
2321 :
2322 : /* Get a mask that includes the top bit in EXTRA_BITS and is all 1s
2323 : below that bit. */
2324 25747 : unsigned int precision = val.get_precision ();
2325 25747 : wide_int lower_mask = wi::mask (precision - wi::clz (extra_bits),
2326 25747 : false, precision);
2327 :
2328 : /* Clear the bits that aren't in MASK, but ensure that all bits
2329 : in MASK below the top cleared bit are set. */
2330 25747 : return (val & mask) | (mask & lower_mask);
2331 25747 : }
2332 :
2333 : /* Return VAL if VAL has no bits set outside MASK. Otherwise round VAL
2334 : up to the next value that has no bits set outside MASK. The rounding
2335 : wraps if there are no suitable values greater than VAL.
2336 :
2337 : For example, round_up_for_mask (6, 0xf1) would give 16 and
2338 : round_up_for_mask (24, 0xf1) would give 32. */
2339 :
2340 : wide_int
2341 18490543 : wi::round_up_for_mask (const wide_int &val, const wide_int &mask)
2342 : {
2343 : /* Get the bits in VAL that are outside the mask. */
2344 18490543 : wide_int extra_bits = wi::bit_and_not (val, mask);
2345 18490543 : if (extra_bits == 0)
2346 18486237 : return val;
2347 :
2348 : /* Get a mask that is all 1s above the top bit in EXTRA_BITS. */
2349 4306 : unsigned int precision = val.get_precision ();
2350 4306 : wide_int upper_mask = wi::mask (precision - wi::clz (extra_bits),
2351 4306 : true, precision);
2352 :
2353 : /* Get the bits of the mask that are above the top bit in EXTRA_BITS. */
2354 4306 : upper_mask &= mask;
2355 :
2356 : /* Conceptually we need to:
2357 :
2358 : - clear bits of VAL outside UPPER_MASK
2359 : - add the lowest bit in UPPER_MASK to VAL (or add 0 if UPPER_MASK is 0)
2360 : - propagate the carry through the bits of VAL in UPPER_MASK
2361 :
2362 : If (~VAL & UPPER_MASK) is nonzero, the carry eventually
2363 : reaches that bit and the process leaves all lower bits clear.
2364 : If (~VAL & UPPER_MASK) is zero then the result is also zero. */
2365 4306 : wide_int tmp = wi::bit_and_not (upper_mask, val);
2366 :
2367 4306 : return (val | tmp) & -tmp;
2368 4306 : }
2369 :
2370 : /* Compute the modular multiplicative inverse of A modulo B
2371 : using extended Euclid's algorithm. Assumes A and B are coprime,
2372 : and that A and B have the same precision. */
2373 : wide_int
2374 4650 : wi::mod_inv (const wide_int &a, const wide_int &b)
2375 : {
2376 : /* Verify the assumption. */
2377 4650 : gcc_checking_assert (wi::eq_p (wi::gcd (a, b), 1));
2378 :
2379 4650 : unsigned int p = a.get_precision () + 1;
2380 4650 : gcc_checking_assert (b.get_precision () + 1 == p);
2381 4650 : wide_int c = wide_int::from (a, p, UNSIGNED);
2382 4650 : wide_int d = wide_int::from (b, p, UNSIGNED);
2383 4650 : wide_int x0 = wide_int::from (0, p, UNSIGNED);
2384 4650 : wide_int x1 = wide_int::from (1, p, UNSIGNED);
2385 :
2386 4650 : if (wi::eq_p (b, 1))
2387 0 : return wide_int::from (1, p, UNSIGNED);
2388 :
2389 22947 : while (wi::gt_p (c, 1, UNSIGNED))
2390 : {
2391 18297 : wide_int t = d;
2392 18297 : wide_int q = wi::divmod_trunc (c, d, UNSIGNED, &d);
2393 18297 : c = t;
2394 18297 : wide_int s = x0;
2395 18297 : x0 = wi::sub (x1, wi::mul (q, x0));
2396 18297 : x1 = s;
2397 18297 : }
2398 4650 : if (wi::lt_p (x1, 0, SIGNED))
2399 4169 : x1 += d;
2400 4650 : return x1;
2401 4650 : }
2402 :
2403 : /*
2404 : * Private utilities.
2405 : */
2406 :
2407 0 : void gt_ggc_mx (widest_int *) { }
2408 0 : void gt_pch_nx (widest_int *, void (*) (void *, void *), void *) { }
2409 0 : void gt_pch_nx (widest_int *) { }
2410 :
2411 : template void wide_int::dump () const;
2412 : template void generic_wide_int <wide_int_ref_storage <false> >::dump () const;
2413 : template void generic_wide_int <wide_int_ref_storage <true> >::dump () const;
2414 : template void offset_int::dump () const;
2415 : template void widest_int::dump () const;
2416 :
2417 : /* We could add all the above ::dump variants here, but wide_int and
2418 : widest_int should handle the common cases. Besides, you can always
2419 : call the dump method directly. */
2420 :
2421 : DEBUG_FUNCTION void
2422 0 : debug (const wide_int &ref)
2423 : {
2424 0 : ref.dump ();
2425 0 : }
2426 :
2427 : DEBUG_FUNCTION void
2428 0 : debug (const wide_int *ptr)
2429 : {
2430 0 : if (ptr)
2431 0 : debug (*ptr);
2432 : else
2433 0 : fprintf (stderr, "<nil>\n");
2434 0 : }
2435 :
2436 : DEBUG_FUNCTION void
2437 0 : debug (const widest_int &ref)
2438 : {
2439 0 : ref.dump ();
2440 0 : }
2441 :
2442 : DEBUG_FUNCTION void
2443 0 : debug (const widest_int *ptr)
2444 : {
2445 0 : if (ptr)
2446 0 : debug (*ptr);
2447 : else
2448 0 : fprintf (stderr, "<nil>\n");
2449 0 : }
2450 :
2451 : #if CHECKING_P
2452 :
2453 : namespace selftest {
2454 :
2455 : /* Selftests for wide ints. We run these multiple times, once per type. */
2456 :
2457 : /* Helper function for building a test value. */
2458 :
2459 : template <class VALUE_TYPE>
2460 : static VALUE_TYPE
2461 : from_int (int i);
2462 :
2463 : /* Specializations of the fixture for each wide-int type. */
2464 :
2465 : /* Specialization for VALUE_TYPE == wide_int. */
2466 :
2467 : template <>
2468 : wide_int
2469 20 : from_int (int i)
2470 : {
2471 20 : return wi::shwi (i, 32);
2472 : }
2473 :
2474 : /* Specialization for VALUE_TYPE == offset_int. */
2475 :
2476 : template <>
2477 : offset_int
2478 20 : from_int (int i)
2479 : {
2480 0 : return offset_int (i);
2481 : }
2482 :
2483 : /* Specialization for VALUE_TYPE == widest_int. */
2484 :
2485 : template <>
2486 : widest_int
2487 28 : from_int (int i)
2488 : {
2489 0 : return widest_int (i);
2490 : }
2491 :
2492 : /* Verify that print_dec (WI, ..., SGN) gives the expected string
2493 : representation (using base 10). */
2494 :
2495 : static void
2496 132 : assert_deceq (const char *expected, const wide_int_ref &wi, signop sgn)
2497 : {
2498 132 : char buf[WIDE_INT_PRINT_BUFFER_SIZE], *p = buf;
2499 132 : unsigned len;
2500 132 : if (print_dec_buf_size (wi, sgn, &len))
2501 0 : p = XALLOCAVEC (char, len);
2502 132 : print_dec (wi, p, sgn);
2503 132 : ASSERT_STREQ (expected, p);
2504 132 : }
2505 :
2506 : /* Likewise for base 16. */
2507 :
2508 : static void
2509 72 : assert_hexeq (const char *expected, const wide_int_ref &wi)
2510 : {
2511 72 : char buf[WIDE_INT_PRINT_BUFFER_SIZE], *p = buf;
2512 72 : unsigned len;
2513 72 : if (print_hex_buf_size (wi, &len))
2514 0 : p = XALLOCAVEC (char, len);
2515 72 : print_hex (wi, p);
2516 72 : ASSERT_STREQ (expected, p);
2517 72 : }
2518 :
2519 : /* Test cases. */
2520 :
2521 : /* Verify that print_dec and print_hex work for VALUE_TYPE. */
2522 :
2523 : template <class VALUE_TYPE>
2524 : static void
2525 12 : test_printing ()
2526 : {
2527 12 : VALUE_TYPE a = from_int<VALUE_TYPE> (42);
2528 12 : assert_deceq ("42", a, SIGNED);
2529 12 : assert_hexeq ("0x2a", a);
2530 12 : assert_hexeq ("0x1fffffffffffffffff", wi::shwi (-1, 69));
2531 12 : assert_hexeq ("0xffffffffffffffff", wi::mask (64, false, 69));
2532 12 : assert_hexeq ("0xffffffffffffffff", wi::mask <widest_int> (64, false));
2533 : if (WIDE_INT_MAX_INL_PRECISION > 128)
2534 : {
2535 12 : assert_hexeq ("0x20000000000000000fffffffffffffffe",
2536 24 : wi::lshift (1, 129) + wi::lshift (1, 64) - 2);
2537 12 : assert_hexeq ("0x200000000000004000123456789abcdef",
2538 24 : wi::lshift (1, 129) + wi::lshift (1, 74)
2539 44 : + wi::lshift (0x1234567, 32) + 0x89abcdef);
2540 : }
2541 12 : }
2542 :
2543 : /* Verify that various operations work correctly for VALUE_TYPE,
2544 : unary and binary, using both function syntax, and
2545 : overloaded-operators. */
2546 :
2547 : template <class VALUE_TYPE>
2548 : static void
2549 12 : test_ops ()
2550 : {
2551 12 : VALUE_TYPE a = from_int<VALUE_TYPE> (7);
2552 12 : VALUE_TYPE b = from_int<VALUE_TYPE> (3);
2553 :
2554 : /* Using functions. */
2555 12 : assert_deceq ("-7", wi::neg (a), SIGNED);
2556 12 : assert_deceq ("10", wi::add (a, b), SIGNED);
2557 12 : assert_deceq ("4", wi::sub (a, b), SIGNED);
2558 12 : assert_deceq ("-4", wi::sub (b, a), SIGNED);
2559 12 : assert_deceq ("21", wi::mul (a, b), SIGNED);
2560 :
2561 : /* Using operators. */
2562 12 : assert_deceq ("-7", -a, SIGNED);
2563 12 : assert_deceq ("10", a + b, SIGNED);
2564 12 : assert_deceq ("4", a - b, SIGNED);
2565 12 : assert_deceq ("-4", b - a, SIGNED);
2566 12 : assert_deceq ("21", a * b, SIGNED);
2567 12 : }
2568 :
2569 : /* Verify that various comparisons work correctly for VALUE_TYPE. */
2570 :
2571 : template <class VALUE_TYPE>
2572 : static void
2573 12 : test_comparisons ()
2574 : {
2575 12 : VALUE_TYPE a = from_int<VALUE_TYPE> (7);
2576 12 : VALUE_TYPE b = from_int<VALUE_TYPE> (3);
2577 :
2578 : /* == */
2579 12 : ASSERT_TRUE (wi::eq_p (a, a));
2580 12 : ASSERT_FALSE (wi::eq_p (a, b));
2581 :
2582 : /* != */
2583 12 : ASSERT_TRUE (wi::ne_p (a, b));
2584 12 : ASSERT_FALSE (wi::ne_p (a, a));
2585 :
2586 : /* < */
2587 12 : ASSERT_FALSE (wi::lts_p (a, a));
2588 12 : ASSERT_FALSE (wi::lts_p (a, b));
2589 12 : ASSERT_TRUE (wi::lts_p (b, a));
2590 :
2591 : /* <= */
2592 12 : ASSERT_TRUE (wi::les_p (a, a));
2593 12 : ASSERT_FALSE (wi::les_p (a, b));
2594 12 : ASSERT_TRUE (wi::les_p (b, a));
2595 :
2596 : /* > */
2597 12 : ASSERT_FALSE (wi::gts_p (a, a));
2598 12 : ASSERT_TRUE (wi::gts_p (a, b));
2599 12 : ASSERT_FALSE (wi::gts_p (b, a));
2600 :
2601 : /* >= */
2602 12 : ASSERT_TRUE (wi::ges_p (a, a));
2603 12 : ASSERT_TRUE (wi::ges_p (a, b));
2604 12 : ASSERT_FALSE (wi::ges_p (b, a));
2605 :
2606 : /* comparison */
2607 12 : ASSERT_EQ (-1, wi::cmps (b, a));
2608 12 : ASSERT_EQ (0, wi::cmps (a, a));
2609 12 : ASSERT_EQ (1, wi::cmps (a, b));
2610 12 : }
2611 :
2612 : /* Run all of the selftests, using the given VALUE_TYPE. */
2613 :
2614 : template <class VALUE_TYPE>
2615 12 : static void run_all_wide_int_tests ()
2616 : {
2617 12 : test_printing <VALUE_TYPE> ();
2618 12 : test_ops <VALUE_TYPE> ();
2619 12 : test_comparisons <VALUE_TYPE> ();
2620 12 : }
2621 :
2622 : /* Test overflow conditions. */
2623 :
2624 : static void
2625 4 : test_overflow ()
2626 : {
2627 4 : static int precs[] = { 31, 32, 33, 63, 64, 65, 127, 128 };
2628 4 : static int offsets[] = { 16, 1, 0 };
2629 36 : for (unsigned int i = 0; i < ARRAY_SIZE (precs); ++i)
2630 128 : for (unsigned int j = 0; j < ARRAY_SIZE (offsets); ++j)
2631 : {
2632 96 : int prec = precs[i];
2633 96 : int offset = offsets[j];
2634 96 : wi::overflow_type overflow;
2635 96 : wide_int sum, diff;
2636 :
2637 192 : sum = wi::add (wi::max_value (prec, UNSIGNED) - offset, 1,
2638 96 : UNSIGNED, &overflow);
2639 96 : ASSERT_EQ (sum, -offset);
2640 96 : ASSERT_EQ (overflow != wi::OVF_NONE, offset == 0);
2641 :
2642 192 : sum = wi::add (1, wi::max_value (prec, UNSIGNED) - offset,
2643 96 : UNSIGNED, &overflow);
2644 96 : ASSERT_EQ (sum, -offset);
2645 96 : ASSERT_EQ (overflow != wi::OVF_NONE, offset == 0);
2646 :
2647 192 : diff = wi::sub (wi::max_value (prec, UNSIGNED) - offset,
2648 96 : wi::max_value (prec, UNSIGNED),
2649 96 : UNSIGNED, &overflow);
2650 96 : ASSERT_EQ (diff, -offset);
2651 96 : ASSERT_EQ (overflow != wi::OVF_NONE, offset != 0);
2652 :
2653 192 : diff = wi::sub (wi::max_value (prec, UNSIGNED) - offset,
2654 192 : wi::max_value (prec, UNSIGNED) - 1,
2655 96 : UNSIGNED, &overflow);
2656 96 : ASSERT_EQ (diff, 1 - offset);
2657 96 : ASSERT_EQ (overflow != wi::OVF_NONE, offset > 1);
2658 96 : }
2659 4 : }
2660 :
2661 : /* Test the round_{down,up}_for_mask functions. */
2662 :
2663 : static void
2664 4 : test_round_for_mask ()
2665 : {
2666 4 : unsigned int prec = 18;
2667 4 : ASSERT_EQ (17, wi::round_down_for_mask (wi::shwi (17, prec),
2668 : wi::shwi (0xf1, prec)));
2669 4 : ASSERT_EQ (17, wi::round_up_for_mask (wi::shwi (17, prec),
2670 : wi::shwi (0xf1, prec)));
2671 :
2672 4 : ASSERT_EQ (1, wi::round_down_for_mask (wi::shwi (6, prec),
2673 : wi::shwi (0xf1, prec)));
2674 4 : ASSERT_EQ (16, wi::round_up_for_mask (wi::shwi (6, prec),
2675 : wi::shwi (0xf1, prec)));
2676 :
2677 4 : ASSERT_EQ (17, wi::round_down_for_mask (wi::shwi (24, prec),
2678 : wi::shwi (0xf1, prec)));
2679 4 : ASSERT_EQ (32, wi::round_up_for_mask (wi::shwi (24, prec),
2680 : wi::shwi (0xf1, prec)));
2681 :
2682 4 : ASSERT_EQ (0x011, wi::round_down_for_mask (wi::shwi (0x22, prec),
2683 : wi::shwi (0x111, prec)));
2684 4 : ASSERT_EQ (0x100, wi::round_up_for_mask (wi::shwi (0x22, prec),
2685 : wi::shwi (0x111, prec)));
2686 :
2687 4 : ASSERT_EQ (100, wi::round_down_for_mask (wi::shwi (101, prec),
2688 : wi::shwi (0xfc, prec)));
2689 4 : ASSERT_EQ (104, wi::round_up_for_mask (wi::shwi (101, prec),
2690 : wi::shwi (0xfc, prec)));
2691 :
2692 4 : ASSERT_EQ (0x2bc, wi::round_down_for_mask (wi::shwi (0x2c2, prec),
2693 : wi::shwi (0xabc, prec)));
2694 4 : ASSERT_EQ (0x800, wi::round_up_for_mask (wi::shwi (0x2c2, prec),
2695 : wi::shwi (0xabc, prec)));
2696 :
2697 4 : ASSERT_EQ (0xabc, wi::round_down_for_mask (wi::shwi (0xabd, prec),
2698 : wi::shwi (0xabc, prec)));
2699 4 : ASSERT_EQ (0, wi::round_up_for_mask (wi::shwi (0xabd, prec),
2700 : wi::shwi (0xabc, prec)));
2701 :
2702 4 : ASSERT_EQ (0xabc, wi::round_down_for_mask (wi::shwi (0x1000, prec),
2703 : wi::shwi (0xabc, prec)));
2704 4 : ASSERT_EQ (0, wi::round_up_for_mask (wi::shwi (0x1000, prec),
2705 : wi::shwi (0xabc, prec)));
2706 4 : }
2707 :
2708 : /* Run all of the selftests within this file, for all value types. */
2709 :
2710 : void
2711 4 : wide_int_cc_tests ()
2712 : {
2713 4 : run_all_wide_int_tests <wide_int> ();
2714 4 : run_all_wide_int_tests <offset_int> ();
2715 4 : run_all_wide_int_tests <widest_int> ();
2716 4 : test_overflow ();
2717 4 : test_round_for_mask ();
2718 4 : ASSERT_EQ (wi::mask (128, false, 128),
2719 : wi::shifted_mask (0, 128, false, 128));
2720 4 : ASSERT_EQ (wi::mask (128, true, 128),
2721 : wi::shifted_mask (0, 128, true, 128));
2722 4 : ASSERT_EQ (wi::multiple_of_p (from_int <widest_int> (1),
2723 : from_int <widest_int> (-128), UNSIGNED),
2724 : false);
2725 4 : }
2726 :
2727 : } // namespace selftest
2728 : #endif /* CHECKING_P */
|
