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 : #if GCC_VERSION >= 3000 && (W_TYPE_SIZE == 32 || defined (__SIZEOF_INT128__))
40 : typedef unsigned HOST_HALF_WIDE_INT UHWtype;
41 : typedef unsigned HOST_WIDE_INT UWtype;
42 : typedef unsigned int UQItype __attribute__ ((mode (QI)));
43 : typedef unsigned int USItype __attribute__ ((mode (SI)));
44 : typedef unsigned int UDItype __attribute__ ((mode (DI)));
45 : #if W_TYPE_SIZE == 32
46 : typedef unsigned int UDWtype __attribute__ ((mode (DI)));
47 : #else
48 : typedef unsigned int UDWtype __attribute__ ((mode (TI)));
49 : #endif
50 : #include "longlong.h"
51 : #endif
52 :
53 : static const HOST_WIDE_INT zeros[1] = {};
54 :
55 : /*
56 : * Internal utilities.
57 : */
58 :
59 : /* Quantities to deal with values that hold half of a wide int. Used
60 : in multiply and divide. */
61 : #define HALF_INT_MASK ((HOST_WIDE_INT_1 << HOST_BITS_PER_HALF_WIDE_INT) - 1)
62 :
63 : #define BLOCK_OF(TARGET) ((TARGET) / HOST_BITS_PER_WIDE_INT)
64 : #define BLOCKS_NEEDED(PREC) (PREC ? CEIL (PREC, HOST_BITS_PER_WIDE_INT) : 1)
65 : #define SIGN_MASK(X) ((HOST_WIDE_INT) (X) < 0 ? -1 : 0)
66 :
67 : /* Return the value a VAL[I] if I < LEN, otherwise, return 0 or -1
68 : based on the top existing bit of VAL. */
69 :
70 : static unsigned HOST_WIDE_INT
71 4350488350 : safe_uhwi (const HOST_WIDE_INT *val, unsigned int len, unsigned int i)
72 : {
73 4350488350 : return i < len ? val[i] : val[len - 1] < 0 ? HOST_WIDE_INT_M1 : 0;
74 : }
75 :
76 : /* Convert the integer in VAL to canonical form, returning its new length.
77 : LEN is the number of blocks currently in VAL and PRECISION is the number
78 : of bits in the integer it represents.
79 :
80 : This function only changes the representation, not the value. */
81 : static unsigned int
82 22796990290 : canonize (HOST_WIDE_INT *val, unsigned int len, unsigned int precision)
83 : {
84 22796990290 : unsigned int blocks_needed = BLOCKS_NEEDED (precision);
85 22796990290 : HOST_WIDE_INT top;
86 22796990290 : int i;
87 :
88 22796990290 : if (len > blocks_needed)
89 : len = blocks_needed;
90 :
91 22796990290 : if (len == 1)
92 : return 1;
93 :
94 2830072746 : top = val[len - 1];
95 2830072746 : if (len * HOST_BITS_PER_WIDE_INT > precision)
96 389342 : val[len - 1] = top = sext_hwi (top, precision % HOST_BITS_PER_WIDE_INT);
97 2830072746 : if (top != 0 && top != HOST_WIDE_INT_M1)
98 : return len;
99 :
100 : /* At this point we know that the top is either 0 or -1. Find the
101 : first block that is not a copy of this. */
102 3985550258 : for (i = len - 2; i >= 0; i--)
103 : {
104 3157039537 : HOST_WIDE_INT x = val[i];
105 3157039537 : if (x != top)
106 : {
107 3366447088 : if (SIGN_MASK (x) == top)
108 1428425975 : return i + 1;
109 :
110 : /* We need an extra block because the top bit block i does
111 : not match the extension. */
112 524556539 : return i + 2;
113 : }
114 : }
115 :
116 : /* The number is 0 or -1. */
117 : return 1;
118 : }
119 :
120 : /* VAL[0] is the unsigned result of an operation. Canonize it by adding
121 : another 0 block if needed, and return number of blocks needed. */
122 :
123 : static inline unsigned int
124 849600130 : canonize_uhwi (HOST_WIDE_INT *val, unsigned int precision)
125 : {
126 1113786 : if (val[0] < 0 && precision > HOST_BITS_PER_WIDE_INT)
127 : {
128 25445 : val[1] = 0;
129 25445 : return 2;
130 : }
131 : return 1;
132 : }
133 :
134 : /*
135 : * Conversion routines in and out of wide_int.
136 : */
137 :
138 : /* Copy XLEN elements from XVAL to VAL. If NEED_CANON, canonize the
139 : result for an integer with precision PRECISION. Return the length
140 : of VAL (after any canonization). */
141 : unsigned int
142 201125953 : wi::from_array (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
143 : unsigned int xlen, unsigned int precision, bool need_canon)
144 : {
145 798602608 : for (unsigned i = 0; i < xlen; i++)
146 597476655 : val[i] = xval[i];
147 201125953 : return need_canon ? canonize (val, xlen, precision) : xlen;
148 : }
149 :
150 : /* Construct a wide int from a buffer of length LEN. BUFFER will be
151 : read according to byte endianness and word endianness of the target.
152 : Only the lower BUFFER_LEN bytes of the result are set; the remaining
153 : high bytes are cleared. */
154 : wide_int
155 2949352 : wi::from_buffer (const unsigned char *buffer, unsigned int buffer_len)
156 : {
157 2949352 : unsigned int precision = buffer_len * BITS_PER_UNIT;
158 2949352 : wide_int result = wide_int::create (precision);
159 2949352 : unsigned int words = buffer_len / UNITS_PER_WORD;
160 :
161 : /* We have to clear all the bits ourself, as we merely or in values
162 : below. */
163 2949352 : unsigned int len = BLOCKS_NEEDED (precision);
164 2949352 : HOST_WIDE_INT *val = result.write_val (0);
165 5908020 : for (unsigned int i = 0; i < len; ++i)
166 2958668 : val[i] = 0;
167 :
168 18933122 : for (unsigned int byte = 0; byte < buffer_len; byte++)
169 : {
170 15983770 : unsigned int offset;
171 15983770 : unsigned int index;
172 15983770 : unsigned int bitpos = byte * BITS_PER_UNIT;
173 15983770 : unsigned HOST_WIDE_INT value;
174 :
175 15983770 : if (buffer_len > UNITS_PER_WORD)
176 : {
177 15983770 : unsigned int word = byte / UNITS_PER_WORD;
178 :
179 15983770 : if (WORDS_BIG_ENDIAN)
180 : word = (words - 1) - word;
181 :
182 15983770 : offset = word * UNITS_PER_WORD;
183 :
184 15983770 : if (BYTES_BIG_ENDIAN)
185 : offset += (UNITS_PER_WORD - 1) - (byte % UNITS_PER_WORD);
186 : else
187 15983770 : offset += byte % UNITS_PER_WORD;
188 : }
189 : else
190 : offset = BYTES_BIG_ENDIAN ? (buffer_len - 1) - byte : byte;
191 :
192 15983770 : value = (unsigned HOST_WIDE_INT) buffer[offset];
193 :
194 15983770 : index = bitpos / HOST_BITS_PER_WIDE_INT;
195 15983770 : val[index] |= value << (bitpos % HOST_BITS_PER_WIDE_INT);
196 : }
197 :
198 2949352 : result.set_len (canonize (val, len, precision));
199 :
200 2949352 : return result;
201 : }
202 :
203 : /* Sets RESULT from X, the sign is taken according to SGN. */
204 : void
205 131176820 : wi::to_mpz (const wide_int_ref &x, mpz_t result, signop sgn)
206 : {
207 131176820 : int len = x.get_len ();
208 131176820 : const HOST_WIDE_INT *v = x.get_val ();
209 131176820 : int excess = len * HOST_BITS_PER_WIDE_INT - x.get_precision ();
210 :
211 131176820 : if (wi::neg_p (x, sgn))
212 : {
213 : /* We use ones complement to avoid -x80..0 edge case that -
214 : won't work on. */
215 10924108 : HOST_WIDE_INT *t = XALLOCAVEC (HOST_WIDE_INT, len);
216 21878269 : for (int i = 0; i < len; i++)
217 10954161 : t[i] = ~v[i];
218 10924108 : if (excess > 0)
219 5338320 : t[len - 1] = (unsigned HOST_WIDE_INT) t[len - 1] << excess >> excess;
220 10924108 : mpz_import (result, len, -1, sizeof (HOST_WIDE_INT), 0, 0, t);
221 10924108 : mpz_com (result, result);
222 : }
223 120252712 : else if (excess > 0)
224 : {
225 70036667 : HOST_WIDE_INT *t = XALLOCAVEC (HOST_WIDE_INT, len);
226 70037507 : for (int i = 0; i < len - 1; i++)
227 840 : t[i] = v[i];
228 70036667 : t[len - 1] = (unsigned HOST_WIDE_INT) v[len - 1] << excess >> excess;
229 70036667 : mpz_import (result, len, -1, sizeof (HOST_WIDE_INT), 0, 0, t);
230 : }
231 50216045 : else if (excess < 0 && wi::neg_p (x))
232 : {
233 36661 : int extra = CEIL (-excess, HOST_BITS_PER_WIDE_INT);
234 36661 : HOST_WIDE_INT *t = XALLOCAVEC (HOST_WIDE_INT, len + extra);
235 73322 : for (int i = 0; i < len; i++)
236 36661 : t[i] = v[i];
237 75803 : for (int i = 0; i < extra; i++)
238 39142 : t[len + i] = -1;
239 36661 : excess = (-excess) % HOST_BITS_PER_WIDE_INT;
240 36661 : if (excess)
241 141 : t[len + extra - 1] = (HOST_WIDE_INT_1U << excess) - 1;
242 36661 : mpz_import (result, len + extra, -1, sizeof (HOST_WIDE_INT), 0, 0, t);
243 : }
244 : else
245 50179384 : mpz_import (result, len, -1, sizeof (HOST_WIDE_INT), 0, 0, v);
246 131176820 : }
247 :
248 : /* Returns X converted to TYPE. If WRAP is true, then out-of-range
249 : values of VAL will be wrapped; otherwise, they will be set to the
250 : appropriate minimum or maximum TYPE bound. */
251 : wide_int
252 15540804 : wi::from_mpz (const_tree type, mpz_t x, bool wrap)
253 : {
254 15540804 : size_t count, numb;
255 15540804 : unsigned int prec = TYPE_PRECISION (type);
256 15540804 : wide_int res = wide_int::create (prec);
257 :
258 15540804 : if (!wrap)
259 : {
260 13010908 : mpz_t min, max;
261 :
262 13010908 : mpz_init (min);
263 13010908 : mpz_init (max);
264 13010908 : get_type_static_bounds (type, min, max);
265 :
266 13010908 : if (mpz_cmp (x, min) < 0)
267 224 : mpz_set (x, min);
268 13010684 : else if (mpz_cmp (x, max) > 0)
269 246 : mpz_set (x, max);
270 :
271 13010908 : mpz_clear (min);
272 13010908 : mpz_clear (max);
273 : }
274 :
275 : /* Determine the number of unsigned HOST_WIDE_INTs that are required
276 : for representing the absolute value. The code to calculate count is
277 : extracted from the GMP manual, section "Integer Import and Export":
278 : http://gmplib.org/manual/Integer-Import-and-Export.html */
279 15540804 : numb = CHAR_BIT * sizeof (HOST_WIDE_INT);
280 15540804 : count = CEIL (mpz_sizeinbase (x, 2), numb);
281 15540804 : HOST_WIDE_INT *val = res.write_val (0);
282 : /* Read the absolute value.
283 :
284 : Write directly to the wide_int storage if possible, otherwise leave
285 : GMP to allocate the memory for us. It might be slightly more efficient
286 : to use mpz_tdiv_r_2exp for the latter case, but the situation is
287 : pathological and it seems safer to operate on the original mpz value
288 : in all cases. */
289 15540838 : void *valres = mpz_export (count <= WIDE_INT_MAX_INL_ELTS ? val : 0,
290 : &count, -1, sizeof (HOST_WIDE_INT), 0, 0, x);
291 15540804 : if (count < 1)
292 : {
293 254644 : val[0] = 0;
294 254644 : count = 1;
295 : }
296 15540804 : count = MIN (count, BLOCKS_NEEDED (prec));
297 15540804 : if (valres != val)
298 : {
299 34 : memcpy (val, valres, count * sizeof (HOST_WIDE_INT));
300 34 : free (valres);
301 : }
302 : /* Zero-extend the absolute value to PREC bits. */
303 15540804 : if (count < BLOCKS_NEEDED (prec) && val[count - 1] < 0)
304 2453 : val[count++] = 0;
305 : else
306 15538351 : count = canonize (val, count, prec);
307 15540804 : res.set_len (count);
308 :
309 15540804 : if (mpz_sgn (x) < 0)
310 95907 : res = -res;
311 :
312 15540804 : return res;
313 : }
314 :
315 : /*
316 : * Largest and smallest values in a mode.
317 : */
318 :
319 : /* Return the largest SGNed number that is representable in PRECISION bits.
320 :
321 : TODO: There is still code from the double_int era that tries to
322 : make up for the fact that double int's could not represent the
323 : min and max values of all types. This code should be removed
324 : because the min and max values can always be represented in
325 : wide_ints and int-csts. */
326 : wide_int
327 6155824042 : wi::max_value (unsigned int precision, signop sgn)
328 : {
329 6155824042 : gcc_checking_assert (precision != 0);
330 6155824042 : if (sgn == UNSIGNED)
331 : /* The unsigned max is just all ones. */
332 4585373065 : return shwi (-1, precision);
333 : else
334 : /* The signed max is all ones except the top bit. This must be
335 : explicitly represented. */
336 1570450977 : return mask (precision - 1, false, precision);
337 : }
338 :
339 : /* Return the largest SGNed number that is representable in PRECISION bits. */
340 : wide_int
341 7669045304 : wi::min_value (unsigned int precision, signop sgn)
342 : {
343 7669045304 : gcc_checking_assert (precision != 0);
344 7669045304 : if (sgn == UNSIGNED)
345 4484497724 : return uhwi (0, precision);
346 : else
347 : /* The signed min is all zeros except the top bit. This must be
348 : explicitly represented. */
349 3184547580 : return wi::set_bit_in_zero (precision - 1, precision);
350 : }
351 :
352 : /*
353 : * Public utilities.
354 : */
355 :
356 : /* Convert the number represented by XVAL, XLEN and XPRECISION, which has
357 : signedness SGN, to an integer that has PRECISION bits. Store the blocks
358 : in VAL and return the number of blocks used.
359 :
360 : This function can handle both extension (PRECISION > XPRECISION)
361 : and truncation (PRECISION < XPRECISION). */
362 : unsigned int
363 19860540099 : wi::force_to_size (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
364 : unsigned int xlen, unsigned int xprecision,
365 : unsigned int precision, signop sgn)
366 : {
367 19860540099 : unsigned int blocks_needed = BLOCKS_NEEDED (precision);
368 19860540099 : unsigned int len = blocks_needed < xlen ? blocks_needed : xlen;
369 39737319268 : for (unsigned i = 0; i < len; i++)
370 19876779169 : val[i] = xval[i];
371 :
372 19860540099 : if (precision > xprecision)
373 : {
374 5395397346 : unsigned int small_xprecision = xprecision % HOST_BITS_PER_WIDE_INT;
375 :
376 : /* Expanding. */
377 5395397346 : if (sgn == UNSIGNED)
378 : {
379 2412464479 : if (small_xprecision && len == BLOCKS_NEEDED (xprecision))
380 1073113112 : val[len - 1] = zext_hwi (val[len - 1], small_xprecision);
381 1339351367 : else if (val[len - 1] < 0)
382 : {
383 212739931 : while (len < BLOCKS_NEEDED (xprecision))
384 1439757 : val[len++] = -1;
385 211300174 : if (small_xprecision)
386 34839 : val[len - 1] = zext_hwi (val[len - 1], small_xprecision);
387 : else
388 211265335 : val[len++] = 0;
389 : }
390 : }
391 : else
392 : {
393 2982932867 : if (small_xprecision && len == BLOCKS_NEEDED (xprecision))
394 1155806178 : val[len - 1] = sext_hwi (val[len - 1], small_xprecision);
395 : }
396 : }
397 19860540099 : len = canonize (val, len, precision);
398 :
399 19860540099 : return len;
400 : }
401 :
402 : /* This function hides the fact that we cannot rely on the bits beyond
403 : the precision. This issue comes up in the relational comparisons
404 : where we do allow comparisons of values of different precisions. */
405 : static inline HOST_WIDE_INT
406 341233838 : selt (const HOST_WIDE_INT *a, unsigned int len,
407 : unsigned int blocks_needed, unsigned int small_prec,
408 : unsigned int index, signop sgn)
409 : {
410 341233838 : HOST_WIDE_INT val;
411 341233838 : if (index < len)
412 274531732 : val = a[index];
413 66702106 : else if (index < blocks_needed || sgn == SIGNED)
414 : /* Signed or within the precision. */
415 66702106 : val = SIGN_MASK (a[len - 1]);
416 : else
417 : /* Unsigned extension beyond the precision. */
418 : val = 0;
419 :
420 341233838 : if (small_prec && index == blocks_needed - 1)
421 1299320 : return (sgn == SIGNED
422 1299320 : ? sext_hwi (val, small_prec)
423 169674 : : zext_hwi (val, small_prec));
424 : else
425 : return val;
426 : }
427 :
428 : /* Find the highest bit represented in a wide int. This will in
429 : general have the same value as the sign bit. */
430 : static inline HOST_WIDE_INT
431 748790245 : top_bit_of (const HOST_WIDE_INT *a, unsigned int len, unsigned int prec)
432 : {
433 748790245 : int excess = len * HOST_BITS_PER_WIDE_INT - prec;
434 748790245 : unsigned HOST_WIDE_INT val = a[len - 1];
435 748790245 : if (excess > 0)
436 43835 : val <<= excess;
437 748790245 : return val >> (HOST_BITS_PER_WIDE_INT - 1);
438 : }
439 :
440 : /*
441 : * Comparisons, note that only equality is an operator. The other
442 : * comparisons cannot be operators since they are inherently signed or
443 : * unsigned and C++ has no such operators.
444 : */
445 :
446 : /* Return true if OP0 == OP1. */
447 : bool
448 2358012 : wi::eq_p_large (const HOST_WIDE_INT *op0, unsigned int op0len,
449 : const HOST_WIDE_INT *op1, unsigned int op1len,
450 : unsigned int prec)
451 : {
452 2358012 : int l0 = op0len - 1;
453 2358012 : unsigned int small_prec = prec & (HOST_BITS_PER_WIDE_INT - 1);
454 :
455 2358012 : if (op0len != op1len)
456 : return false;
457 :
458 1236264 : if (op0len == BLOCKS_NEEDED (prec) && small_prec)
459 : {
460 : /* It does not matter if we zext or sext here, we just have to
461 : do both the same way. */
462 59197 : if (zext_hwi (op0 [l0], small_prec) != zext_hwi (op1 [l0], small_prec))
463 : return false;
464 54677 : l0--;
465 : }
466 :
467 3807909 : while (l0 >= 0)
468 2608913 : if (op0[l0] != op1[l0])
469 : return false;
470 : else
471 2576165 : l0--;
472 :
473 : return true;
474 : }
475 :
476 : /* Return true if OP0 < OP1 using signed comparisons. */
477 : bool
478 33114807 : wi::lts_p_large (const HOST_WIDE_INT *op0, unsigned int op0len,
479 : unsigned int precision,
480 : const HOST_WIDE_INT *op1, unsigned int op1len)
481 : {
482 33114807 : HOST_WIDE_INT s0, s1;
483 33114807 : unsigned HOST_WIDE_INT u0, u1;
484 33114807 : unsigned int blocks_needed = BLOCKS_NEEDED (precision);
485 33114807 : unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
486 33114807 : int l = MAX (op0len - 1, op1len - 1);
487 :
488 : /* Only the top block is compared as signed. The rest are unsigned
489 : comparisons. */
490 33114807 : s0 = selt (op0, op0len, blocks_needed, small_prec, l, SIGNED);
491 33114807 : s1 = selt (op1, op1len, blocks_needed, small_prec, l, SIGNED);
492 33114807 : if (s0 < s1)
493 : return true;
494 31747674 : if (s0 > s1)
495 : return false;
496 :
497 28026863 : l--;
498 36343675 : while (l >= 0)
499 : {
500 28802092 : u0 = selt (op0, op0len, blocks_needed, small_prec, l, SIGNED);
501 28802092 : u1 = selt (op1, op1len, blocks_needed, small_prec, l, SIGNED);
502 :
503 28802092 : if (u0 < u1)
504 : return true;
505 10784042 : if (u0 > u1)
506 : return false;
507 8316812 : l--;
508 : }
509 :
510 : return false;
511 : }
512 :
513 : /* Returns -1 if OP0 < OP1, 0 if OP0 == OP1 and 1 if OP0 > OP1 using
514 : signed compares. */
515 : int
516 3450629 : wi::cmps_large (const HOST_WIDE_INT *op0, unsigned int op0len,
517 : unsigned int precision,
518 : const HOST_WIDE_INT *op1, unsigned int op1len)
519 : {
520 3450629 : HOST_WIDE_INT s0, s1;
521 3450629 : unsigned HOST_WIDE_INT u0, u1;
522 3450629 : unsigned int blocks_needed = BLOCKS_NEEDED (precision);
523 3450629 : unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
524 3450629 : int l = MAX (op0len - 1, op1len - 1);
525 :
526 : /* Only the top block is compared as signed. The rest are unsigned
527 : comparisons. */
528 3450629 : s0 = selt (op0, op0len, blocks_needed, small_prec, l, SIGNED);
529 3450629 : s1 = selt (op1, op1len, blocks_needed, small_prec, l, SIGNED);
530 3450629 : if (s0 < s1)
531 : return -1;
532 1621090 : if (s0 > s1)
533 : return 1;
534 :
535 1497190 : l--;
536 2382097 : while (l >= 0)
537 : {
538 1730538 : u0 = selt (op0, op0len, blocks_needed, small_prec, l, SIGNED);
539 1730538 : u1 = selt (op1, op1len, blocks_needed, small_prec, l, SIGNED);
540 :
541 1730538 : if (u0 < u1)
542 : return -1;
543 897335 : if (u0 > u1)
544 : return 1;
545 884907 : l--;
546 : }
547 :
548 : return 0;
549 : }
550 :
551 : /* Return true if OP0 < OP1 using unsigned comparisons. */
552 : bool
553 51700337 : wi::ltu_p_large (const HOST_WIDE_INT *op0, unsigned int op0len,
554 : unsigned int precision,
555 : const HOST_WIDE_INT *op1, unsigned int op1len)
556 : {
557 51700337 : unsigned HOST_WIDE_INT x0;
558 51700337 : unsigned HOST_WIDE_INT x1;
559 51700337 : unsigned int blocks_needed = BLOCKS_NEEDED (precision);
560 51700337 : unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
561 51700337 : int l = MAX (op0len - 1, op1len - 1);
562 :
563 78369579 : while (l >= 0)
564 : {
565 75344083 : x0 = selt (op0, op0len, blocks_needed, small_prec, l, UNSIGNED);
566 75344083 : x1 = selt (op1, op1len, blocks_needed, small_prec, l, UNSIGNED);
567 75344083 : if (x0 < x1)
568 : return true;
569 60541333 : if (x0 > x1)
570 : return false;
571 26669242 : l--;
572 : }
573 :
574 : return false;
575 : }
576 :
577 : /* Returns -1 if OP0 < OP1, 0 if OP0 == OP1 and 1 if OP0 > OP1 using
578 : unsigned compares. */
579 : int
580 16996922 : wi::cmpu_large (const HOST_WIDE_INT *op0, unsigned int op0len,
581 : unsigned int precision,
582 : const HOST_WIDE_INT *op1, unsigned int op1len)
583 : {
584 16996922 : unsigned HOST_WIDE_INT x0;
585 16996922 : unsigned HOST_WIDE_INT x1;
586 16996922 : unsigned int blocks_needed = BLOCKS_NEEDED (precision);
587 16996922 : unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1);
588 16996922 : int l = MAX (op0len - 1, op1len - 1);
589 :
590 29250798 : while (l >= 0)
591 : {
592 28174770 : x0 = selt (op0, op0len, blocks_needed, small_prec, l, UNSIGNED);
593 28174770 : x1 = selt (op1, op1len, blocks_needed, small_prec, l, UNSIGNED);
594 28174770 : if (x0 < x1)
595 : return -1;
596 13919221 : if (x0 > x1)
597 : return 1;
598 12253876 : l--;
599 : }
600 :
601 : return 0;
602 : }
603 :
604 : /*
605 : * Extension.
606 : */
607 :
608 : /* Sign-extend the number represented by XVAL and XLEN into VAL,
609 : starting at OFFSET. Return the number of blocks in VAL. Both XVAL
610 : and VAL have PRECISION bits. */
611 : unsigned int
612 5880739 : wi::sext_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
613 : unsigned int xlen, unsigned int precision, unsigned int offset)
614 : {
615 5880739 : unsigned int len = offset / HOST_BITS_PER_WIDE_INT;
616 : /* Extending beyond the precision is a no-op. If we have only stored
617 : OFFSET bits or fewer, the rest are already signs. */
618 5880739 : if (offset >= precision || len >= xlen)
619 : {
620 179698393 : for (unsigned i = 0; i < xlen; ++i)
621 174179048 : val[i] = xval[i];
622 : return xlen;
623 : }
624 361394 : unsigned int suboffset = offset % HOST_BITS_PER_WIDE_INT;
625 1574339 : for (unsigned int i = 0; i < len; i++)
626 1212945 : val[i] = xval[i];
627 361394 : if (suboffset > 0)
628 : {
629 26441 : val[len] = sext_hwi (xval[len], suboffset);
630 26441 : len += 1;
631 : }
632 361394 : return canonize (val, len, precision);
633 : }
634 :
635 : /* Zero-extend the number represented by XVAL and XLEN into VAL,
636 : starting at OFFSET. Return the number of blocks in VAL. Both XVAL
637 : and VAL have PRECISION bits. */
638 : unsigned int
639 791174064 : wi::zext_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
640 : unsigned int xlen, unsigned int precision, unsigned int offset)
641 : {
642 791174064 : unsigned int len = offset / HOST_BITS_PER_WIDE_INT;
643 : /* Extending beyond the precision is a no-op. If we have only stored
644 : OFFSET bits or fewer, and the upper stored bit is zero, then there
645 : is nothing to do. */
646 791174064 : if (offset >= precision || (len >= xlen && xval[xlen - 1] >= 0))
647 : {
648 1256529737 : for (unsigned i = 0; i < xlen; ++i)
649 628705942 : val[i] = xval[i];
650 : return xlen;
651 : }
652 163350269 : unsigned int suboffset = offset % HOST_BITS_PER_WIDE_INT;
653 328599819 : for (unsigned int i = 0; i < len; i++)
654 165249550 : val[i] = i < xlen ? xval[i] : -1;
655 163350269 : if (suboffset > 0)
656 41104 : val[len] = zext_hwi (len < xlen ? xval[len] : -1, suboffset);
657 : else
658 163309165 : val[len] = 0;
659 163350269 : return canonize (val, len + 1, precision);
660 : }
661 :
662 : /*
663 : * Masking, inserting, shifting, rotating.
664 : */
665 :
666 : /* Insert WIDTH bits from Y into X starting at START. */
667 : wide_int
668 364763 : wi::insert (const wide_int &x, const wide_int &y, unsigned int start,
669 : unsigned int width)
670 : {
671 364763 : wide_int result;
672 364763 : wide_int mask;
673 364763 : wide_int tmp;
674 :
675 364763 : unsigned int precision = x.get_precision ();
676 364763 : if (start >= precision)
677 0 : return x;
678 :
679 364763 : gcc_checking_assert (precision >= width);
680 :
681 364763 : if (start + width >= precision)
682 141819 : width = precision - start;
683 :
684 364763 : mask = wi::shifted_mask (start, width, false, precision);
685 364763 : tmp = wi::lshift (wide_int::from (y, precision, UNSIGNED), start);
686 364763 : result = tmp & mask;
687 :
688 364763 : tmp = wi::bit_and_not (x, mask);
689 364763 : result = result | tmp;
690 :
691 364763 : return result;
692 364763 : }
693 :
694 : /* Copy the number represented by XVAL and XLEN into VAL, setting bit BIT.
695 : Return the number of blocks in VAL. Both XVAL and VAL have PRECISION
696 : bits. */
697 : unsigned int
698 88 : wi::set_bit_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
699 : unsigned int xlen, unsigned int precision, unsigned int bit)
700 : {
701 88 : unsigned int block = bit / HOST_BITS_PER_WIDE_INT;
702 88 : unsigned int subbit = bit % HOST_BITS_PER_WIDE_INT;
703 :
704 88 : if (block + 1 >= xlen)
705 : {
706 : /* The operation either affects the last current block or needs
707 : a new block. */
708 36 : unsigned int len = block + 1;
709 36 : for (unsigned int i = 0; i < len; i++)
710 48 : val[i] = safe_uhwi (xval, xlen, i);
711 12 : val[block] |= HOST_WIDE_INT_1U << subbit;
712 :
713 : /* If the bit we just set is at the msb of the block, make sure
714 : that any higher bits are zeros. */
715 12 : if (bit + 1 < precision && subbit == HOST_BITS_PER_WIDE_INT - 1)
716 : {
717 0 : val[len++] = 0;
718 0 : return len;
719 : }
720 12 : return canonize (val, len, precision);
721 : }
722 : else
723 : {
724 380 : for (unsigned int i = 0; i < xlen; i++)
725 304 : val[i] = xval[i];
726 76 : val[block] |= HOST_WIDE_INT_1U << subbit;
727 76 : return canonize (val, xlen, precision);
728 : }
729 : }
730 :
731 : /* Byte swap the integer represented by XVAL and XLEN into VAL. Return
732 : the number of blocks in VAL. Both XVAL and VAL have PRECISION bits. */
733 : unsigned int
734 7595 : wi::bswap_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
735 : unsigned int xlen, unsigned int precision)
736 : {
737 7595 : unsigned int s, len = BLOCKS_NEEDED (precision);
738 :
739 : /* This is not a well defined operation if the precision is not a
740 : multiple of 8. */
741 7595 : gcc_assert ((precision & 0x7) == 0);
742 :
743 7595 : memset (val, 0, sizeof (unsigned HOST_WIDE_INT) * len);
744 :
745 : /* Only swap the bytes that are not the padding. */
746 47964 : for (s = 0; s < precision; s += 8)
747 : {
748 40369 : unsigned int d = precision - s - 8;
749 40369 : unsigned HOST_WIDE_INT byte;
750 :
751 40369 : unsigned int block = s / HOST_BITS_PER_WIDE_INT;
752 40369 : unsigned int offset = s & (HOST_BITS_PER_WIDE_INT - 1);
753 :
754 40369 : byte = (safe_uhwi (xval, xlen, block) >> offset) & 0xff;
755 :
756 40369 : block = d / HOST_BITS_PER_WIDE_INT;
757 40369 : offset = d & (HOST_BITS_PER_WIDE_INT - 1);
758 :
759 40369 : val[block] |= byte << offset;
760 : }
761 :
762 7595 : return canonize (val, len, precision);
763 : }
764 :
765 : /* Bitreverse the integer represented by XVAL and XLEN into VAL. Return
766 : the number of blocks in VAL. Both XVAL and VAL have PRECISION bits. */
767 : unsigned int
768 213 : wi::bitreverse_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
769 : unsigned int xlen, unsigned int precision)
770 : {
771 213 : unsigned int s, len = BLOCKS_NEEDED (precision);
772 :
773 213 : memset (val, 0, sizeof (unsigned HOST_WIDE_INT) * len);
774 :
775 16247 : for (s = 0; s < precision; s++)
776 : {
777 16034 : unsigned int block = s / HOST_BITS_PER_WIDE_INT;
778 16034 : unsigned int offset = s & (HOST_BITS_PER_WIDE_INT - 1);
779 32068 : if (((safe_uhwi (xval, xlen, block) >> offset) & 1) != 0)
780 : {
781 3885 : unsigned int d = (precision - 1) - s;
782 3885 : block = d / HOST_BITS_PER_WIDE_INT;
783 3885 : offset = d & (HOST_BITS_PER_WIDE_INT - 1);
784 3885 : val[block] |= HOST_WIDE_INT_1U << offset;
785 : }
786 : }
787 :
788 213 : return canonize (val, len, precision);
789 : }
790 :
791 : /* Fill VAL with a mask where the lower WIDTH bits are ones and the bits
792 : above that up to PREC are zeros. The result is inverted if NEGATE
793 : is true. Return the number of blocks in VAL. */
794 : unsigned int
795 2906624744 : wi::mask (HOST_WIDE_INT *val, unsigned int width, bool negate,
796 : unsigned int prec)
797 : {
798 2906624744 : if (width >= prec)
799 : {
800 576768733 : val[0] = negate ? 0 : -1;
801 576768733 : return 1;
802 : }
803 2329856011 : else if (width == 0)
804 : {
805 11963735 : val[0] = negate ? -1 : 0;
806 11963735 : return 1;
807 : }
808 :
809 : unsigned int i = 0;
810 2656032438 : while (i < width / HOST_BITS_PER_WIDE_INT)
811 675841241 : val[i++] = negate ? 0 : -1;
812 :
813 2317892276 : unsigned int shift = width & (HOST_BITS_PER_WIDE_INT - 1);
814 2317892276 : if (shift != 0)
815 : {
816 2295909073 : HOST_WIDE_INT last = (HOST_WIDE_INT_1U << shift) - 1;
817 2295909073 : val[i++] = negate ? ~last : last;
818 : }
819 : else
820 43550071 : val[i++] = negate ? -1 : 0;
821 :
822 : return i;
823 : }
824 :
825 : /* Fill VAL with a mask where the lower START bits are zeros, the next WIDTH
826 : bits are ones, and the bits above that up to PREC are zeros. The result
827 : is inverted if NEGATE is true. Return the number of blocks in VAL. */
828 : unsigned int
829 3204219725 : wi::shifted_mask (HOST_WIDE_INT *val, unsigned int start, unsigned int width,
830 : bool negate, unsigned int prec)
831 : {
832 3204219725 : if (start >= prec || width == 0)
833 : {
834 2 : val[0] = negate ? -1 : 0;
835 2 : return 1;
836 : }
837 :
838 3204219723 : if (width > prec - start)
839 : width = prec - start;
840 3204219723 : unsigned int end = start + width;
841 :
842 3204219723 : unsigned int i = 0;
843 3965080003 : while (i < start / HOST_BITS_PER_WIDE_INT)
844 1521720558 : val[i++] = negate ? -1 : 0;
845 :
846 3204219723 : unsigned int shift = start & (HOST_BITS_PER_WIDE_INT - 1);
847 3204219723 : if (shift)
848 : {
849 3202740156 : HOST_WIDE_INT block = (HOST_WIDE_INT_1U << shift) - 1;
850 3202740156 : shift += width;
851 3202740156 : if (shift < HOST_BITS_PER_WIDE_INT)
852 : {
853 : /* case 000111000 */
854 1625749852 : block = (HOST_WIDE_INT_1U << shift) - block - 1;
855 1625749852 : val[i++] = negate ? ~block : block;
856 1625749852 : return i;
857 : }
858 : else
859 : /* ...111000 */
860 1576990304 : val[i++] = negate ? block : ~block;
861 : }
862 :
863 1578469871 : if (end >= prec)
864 : {
865 1577022495 : if (!shift)
866 329188 : val[i++] = negate ? 0 : -1;
867 : return i;
868 : }
869 :
870 1632493 : while (i < end / HOST_BITS_PER_WIDE_INT)
871 : /* 1111111 */
872 195283 : val[i++] = negate ? 0 : -1;
873 :
874 1447376 : shift = end & (HOST_BITS_PER_WIDE_INT - 1);
875 1447376 : if (shift != 0)
876 : {
877 : /* 000011111 */
878 1132577 : HOST_WIDE_INT block = (HOST_WIDE_INT_1U << shift) - 1;
879 1132577 : val[i++] = negate ? ~block : block;
880 : }
881 : else
882 456658 : val[i++] = negate ? -1 : 0;
883 :
884 : return i;
885 : }
886 :
887 : /*
888 : * logical operations.
889 : */
890 :
891 : /* Set VAL to OP0 & OP1. Return the number of blocks used. */
892 : unsigned int
893 45656148 : wi::and_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
894 : unsigned int op0len, const HOST_WIDE_INT *op1,
895 : unsigned int op1len, unsigned int prec)
896 : {
897 45656148 : int l0 = op0len - 1;
898 45656148 : int l1 = op1len - 1;
899 45656148 : bool need_canon = true;
900 :
901 45656148 : unsigned int len = MAX (op0len, op1len);
902 45656148 : if (l0 > l1)
903 : {
904 21016757 : HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec);
905 21016757 : if (op1mask == 0)
906 : {
907 45656148 : l0 = l1;
908 45656148 : len = l1 + 1;
909 : }
910 : else
911 : {
912 309020 : need_canon = false;
913 309020 : while (l0 > l1)
914 : {
915 155002 : val[l0] = op0[l0];
916 155002 : l0--;
917 : }
918 : }
919 : }
920 24639391 : else if (l1 > l0)
921 : {
922 9569529 : HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec);
923 9569529 : if (op0mask == 0)
924 : len = l0 + 1;
925 : else
926 : {
927 1385817 : need_canon = false;
928 1385817 : while (l1 > l0)
929 : {
930 715102 : val[l1] = op1[l1];
931 715102 : l1--;
932 : }
933 : }
934 : }
935 :
936 106606910 : while (l0 >= 0)
937 : {
938 60950762 : val[l0] = op0[l0] & op1[l0];
939 60950762 : l0--;
940 : }
941 :
942 45656148 : if (need_canon)
943 44831415 : len = canonize (val, len, prec);
944 :
945 45656148 : return len;
946 : }
947 :
948 : /* Set VAL to OP0 & ~OP1. Return the number of blocks used. */
949 : unsigned int
950 102670274 : wi::and_not_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
951 : unsigned int op0len, const HOST_WIDE_INT *op1,
952 : unsigned int op1len, unsigned int prec)
953 : {
954 102670274 : wide_int result;
955 102670274 : int l0 = op0len - 1;
956 102670274 : int l1 = op1len - 1;
957 102670274 : bool need_canon = true;
958 :
959 102670274 : unsigned int len = MAX (op0len, op1len);
960 102670274 : if (l0 > l1)
961 : {
962 14484496 : HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec);
963 14484496 : if (op1mask != 0)
964 : {
965 102670274 : l0 = l1;
966 102670274 : len = l1 + 1;
967 : }
968 : else
969 : {
970 28464629 : need_canon = false;
971 28464629 : while (l0 > l1)
972 : {
973 14322383 : val[l0] = op0[l0];
974 14322383 : l0--;
975 : }
976 : }
977 : }
978 88185778 : else if (l1 > l0)
979 : {
980 87024237 : HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec);
981 87024237 : if (op0mask == 0)
982 : len = l0 + 1;
983 : else
984 : {
985 141355 : need_canon = false;
986 141355 : while (l1 > l0)
987 : {
988 71980 : val[l1] = ~op1[l1];
989 71980 : l1--;
990 : }
991 : }
992 : }
993 :
994 206650064 : while (l0 >= 0)
995 : {
996 103979790 : val[l0] = op0[l0] & ~op1[l0];
997 103979790 : l0--;
998 : }
999 :
1000 102670274 : if (need_canon)
1001 88458653 : len = canonize (val, len, prec);
1002 :
1003 102670274 : return len;
1004 102670274 : }
1005 :
1006 : /* Set VAL to OP0 | OP1. Return the number of blocks used. */
1007 : unsigned int
1008 206951391 : wi::or_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
1009 : unsigned int op0len, const HOST_WIDE_INT *op1,
1010 : unsigned int op1len, unsigned int prec)
1011 : {
1012 206951391 : wide_int result;
1013 206951391 : int l0 = op0len - 1;
1014 206951391 : int l1 = op1len - 1;
1015 206951391 : bool need_canon = true;
1016 :
1017 206951391 : unsigned int len = MAX (op0len, op1len);
1018 206951391 : if (l0 > l1)
1019 : {
1020 70559906 : HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec);
1021 70559906 : if (op1mask != 0)
1022 : {
1023 206951391 : l0 = l1;
1024 206951391 : len = l1 + 1;
1025 : }
1026 : else
1027 : {
1028 241214560 : need_canon = false;
1029 241214560 : while (l0 > l1)
1030 : {
1031 171136843 : val[l0] = op0[l0];
1032 171136843 : l0--;
1033 : }
1034 : }
1035 : }
1036 136391485 : else if (l1 > l0)
1037 : {
1038 77893751 : HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec);
1039 77893751 : if (op0mask != 0)
1040 : len = l0 + 1;
1041 : else
1042 : {
1043 315164330 : need_canon = false;
1044 315164330 : while (l1 > l0)
1045 : {
1046 241508526 : val[l1] = op1[l1];
1047 241508526 : l1--;
1048 : }
1049 : }
1050 : }
1051 :
1052 640546240 : while (l0 >= 0)
1053 : {
1054 433594849 : val[l0] = op0[l0] | op1[l0];
1055 433594849 : l0--;
1056 : }
1057 :
1058 206951391 : if (need_canon)
1059 63217870 : len = canonize (val, len, prec);
1060 :
1061 206951391 : return len;
1062 206951391 : }
1063 :
1064 : /* Set VAL to OP0 | ~OP1. Return the number of blocks used. */
1065 : unsigned int
1066 0 : wi::or_not_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
1067 : unsigned int op0len, const HOST_WIDE_INT *op1,
1068 : unsigned int op1len, unsigned int prec)
1069 : {
1070 0 : wide_int result;
1071 0 : int l0 = op0len - 1;
1072 0 : int l1 = op1len - 1;
1073 0 : bool need_canon = true;
1074 :
1075 0 : unsigned int len = MAX (op0len, op1len);
1076 0 : if (l0 > l1)
1077 : {
1078 0 : HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec);
1079 0 : if (op1mask == 0)
1080 : {
1081 0 : l0 = l1;
1082 0 : len = l1 + 1;
1083 : }
1084 : else
1085 : {
1086 0 : need_canon = false;
1087 0 : while (l0 > l1)
1088 : {
1089 0 : val[l0] = op0[l0];
1090 0 : l0--;
1091 : }
1092 : }
1093 : }
1094 0 : else if (l1 > l0)
1095 : {
1096 0 : HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec);
1097 0 : if (op0mask != 0)
1098 : len = l0 + 1;
1099 : else
1100 : {
1101 0 : need_canon = false;
1102 0 : while (l1 > l0)
1103 : {
1104 0 : val[l1] = ~op1[l1];
1105 0 : l1--;
1106 : }
1107 : }
1108 : }
1109 :
1110 0 : while (l0 >= 0)
1111 : {
1112 0 : val[l0] = op0[l0] | ~op1[l0];
1113 0 : l0--;
1114 : }
1115 :
1116 0 : if (need_canon)
1117 0 : len = canonize (val, len, prec);
1118 :
1119 0 : return len;
1120 0 : }
1121 :
1122 : /* Set VAL to OP0 ^ OP1. Return the number of blocks used. */
1123 : unsigned int
1124 46115045 : wi::xor_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
1125 : unsigned int op0len, const HOST_WIDE_INT *op1,
1126 : unsigned int op1len, unsigned int prec)
1127 : {
1128 46115045 : wide_int result;
1129 46115045 : int l0 = op0len - 1;
1130 46115045 : int l1 = op1len - 1;
1131 :
1132 46115045 : unsigned int len = MAX (op0len, op1len);
1133 46115045 : if (l0 > l1)
1134 : {
1135 9897121 : HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec);
1136 19919570 : while (l0 > l1)
1137 : {
1138 10022449 : val[l0] = op0[l0] ^ op1mask;
1139 10022449 : l0--;
1140 : }
1141 : }
1142 :
1143 46115045 : if (l1 > l0)
1144 : {
1145 28135630 : HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec);
1146 123485382 : while (l1 > l0)
1147 : {
1148 95349752 : val[l1] = op0mask ^ op1[l1];
1149 95349752 : l1--;
1150 : }
1151 : }
1152 :
1153 168046677 : while (l0 >= 0)
1154 : {
1155 121931632 : val[l0] = op0[l0] ^ op1[l0];
1156 121931632 : l0--;
1157 : }
1158 :
1159 46115045 : return canonize (val, len, prec);
1160 46115045 : }
1161 :
1162 : /*
1163 : * math
1164 : */
1165 :
1166 : /* Set VAL to OP0 + OP1. If OVERFLOW is nonnull, record in *OVERFLOW
1167 : whether the result overflows when OP0 and OP1 are treated as having
1168 : signedness SGN. Return the number of blocks in VAL. */
1169 : unsigned int
1170 139957667 : wi::add_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
1171 : unsigned int op0len, const HOST_WIDE_INT *op1,
1172 : unsigned int op1len, unsigned int prec,
1173 : signop sgn, wi::overflow_type *overflow)
1174 : {
1175 139957667 : unsigned HOST_WIDE_INT o0 = 0;
1176 139957667 : unsigned HOST_WIDE_INT o1 = 0;
1177 139957667 : unsigned HOST_WIDE_INT x = 0;
1178 139957667 : unsigned HOST_WIDE_INT carry = 0;
1179 139957667 : unsigned HOST_WIDE_INT old_carry = 0;
1180 139957667 : unsigned HOST_WIDE_INT mask0, mask1;
1181 139957667 : unsigned int i;
1182 :
1183 139957667 : unsigned int len = MAX (op0len, op1len);
1184 139957667 : mask0 = -top_bit_of (op0, op0len, prec);
1185 139957667 : mask1 = -top_bit_of (op1, op1len, prec);
1186 : /* Add all of the explicitly defined elements. */
1187 :
1188 433489812 : for (i = 0; i < len; i++)
1189 : {
1190 293532145 : o0 = i < op0len ? (unsigned HOST_WIDE_INT) op0[i] : mask0;
1191 293532145 : o1 = i < op1len ? (unsigned HOST_WIDE_INT) op1[i] : mask1;
1192 293532145 : x = o0 + o1 + carry;
1193 293532145 : val[i] = x;
1194 293532145 : old_carry = carry;
1195 293532145 : carry = carry == 0 ? x < o0 : x <= o0;
1196 : }
1197 :
1198 139957667 : if (len * HOST_BITS_PER_WIDE_INT < prec)
1199 : {
1200 134211311 : val[len] = mask0 + mask1 + carry;
1201 134211311 : len++;
1202 134211311 : if (overflow)
1203 59296226 : *overflow
1204 118519028 : = (sgn == UNSIGNED && carry) ? wi::OVF_OVERFLOW : wi::OVF_NONE;
1205 : }
1206 5746356 : else if (overflow)
1207 : {
1208 1025306 : unsigned int shift = -prec % HOST_BITS_PER_WIDE_INT;
1209 1025306 : if (sgn == SIGNED)
1210 : {
1211 251814 : unsigned HOST_WIDE_INT x = (val[len - 1] ^ o0) & (val[len - 1] ^ o1);
1212 251814 : if ((HOST_WIDE_INT) (x << shift) < 0)
1213 : {
1214 39805 : if (o0 > (unsigned HOST_WIDE_INT) val[len - 1])
1215 12750 : *overflow = wi::OVF_UNDERFLOW;
1216 27055 : else if (o0 < (unsigned HOST_WIDE_INT) val[len - 1])
1217 27055 : *overflow = wi::OVF_OVERFLOW;
1218 : else
1219 0 : *overflow = wi::OVF_NONE;
1220 : }
1221 : else
1222 212009 : *overflow = wi::OVF_NONE;
1223 : }
1224 : else
1225 : {
1226 : /* Put the MSB of X and O0 and in the top of the HWI. */
1227 773492 : x <<= shift;
1228 773492 : o0 <<= shift;
1229 773492 : if (old_carry)
1230 347682 : *overflow = (x <= o0) ? wi::OVF_OVERFLOW : wi::OVF_NONE;
1231 : else
1232 1187032 : *overflow = (x < o0) ? wi::OVF_OVERFLOW : wi::OVF_NONE;
1233 : }
1234 : }
1235 :
1236 139957667 : return canonize (val, len, prec);
1237 : }
1238 :
1239 : /* Subroutines of the multiplication and division operations. Unpack
1240 : the first IN_LEN HOST_WIDE_INTs in INPUT into 2 * IN_LEN
1241 : HOST_HALF_WIDE_INTs of RESULT. The rest of RESULT is filled by
1242 : uncompressing the top bit of INPUT[IN_LEN - 1]. */
1243 : static void
1244 83784926 : wi_unpack (unsigned HOST_HALF_WIDE_INT *result, const HOST_WIDE_INT *input,
1245 : unsigned int in_len, unsigned int out_len,
1246 : unsigned int prec, signop sgn)
1247 : {
1248 83784926 : unsigned int i;
1249 83784926 : unsigned int j = 0;
1250 83784926 : unsigned int small_prec = prec & (HOST_BITS_PER_WIDE_INT - 1);
1251 83784926 : unsigned int blocks_needed = BLOCKS_NEEDED (prec);
1252 83784926 : HOST_WIDE_INT mask;
1253 :
1254 83784926 : if (sgn == SIGNED)
1255 : {
1256 0 : mask = -top_bit_of ((const HOST_WIDE_INT *) input, in_len, prec);
1257 0 : mask &= HALF_INT_MASK;
1258 : }
1259 : else
1260 : mask = 0;
1261 :
1262 171293103 : for (i = 0; i < blocks_needed - 1; i++)
1263 : {
1264 87508177 : HOST_WIDE_INT x = safe_uhwi (input, in_len, i);
1265 87508177 : result[j++] = x;
1266 87508177 : result[j++] = x >> HOST_BITS_PER_HALF_WIDE_INT;
1267 : }
1268 :
1269 83784926 : HOST_WIDE_INT x = safe_uhwi (input, in_len, i);
1270 83784926 : if (small_prec)
1271 : {
1272 29586 : if (sgn == SIGNED)
1273 0 : x = sext_hwi (x, small_prec);
1274 : else
1275 29586 : x = zext_hwi (x, small_prec);
1276 : }
1277 83784926 : result[j++] = x;
1278 83784926 : result[j++] = x >> HOST_BITS_PER_HALF_WIDE_INT;
1279 :
1280 : /* Smear the sign bit. */
1281 83784926 : while (j < out_len)
1282 0 : result[j++] = mask;
1283 83784926 : }
1284 :
1285 : /* The inverse of wi_unpack. IN_LEN is the number of input
1286 : blocks and PRECISION is the precision of the result. Return the
1287 : number of blocks in the canonicalized result. */
1288 : static unsigned int
1289 44369881 : wi_pack (HOST_WIDE_INT *result,
1290 : const unsigned HOST_HALF_WIDE_INT *input,
1291 : unsigned int in_len, unsigned int precision)
1292 : {
1293 44369881 : unsigned int i = 0;
1294 44369881 : unsigned int j = 0;
1295 44369881 : unsigned int blocks_needed = BLOCKS_NEEDED (precision);
1296 :
1297 130563638 : while (i + 1 < in_len)
1298 : {
1299 86193757 : result[j++] = ((unsigned HOST_WIDE_INT) input[i]
1300 86193757 : | ((unsigned HOST_WIDE_INT) input[i + 1]
1301 86193757 : << HOST_BITS_PER_HALF_WIDE_INT));
1302 86193757 : i += 2;
1303 : }
1304 :
1305 : /* Handle the case where in_len is odd. For this we zero extend. */
1306 44369881 : if (in_len & 1)
1307 3155185 : result[j++] = (unsigned HOST_WIDE_INT) input[i];
1308 41214696 : else if (j < blocks_needed)
1309 1939951 : result[j++] = 0;
1310 44369881 : return canonize (result, j, precision);
1311 : }
1312 :
1313 : /* Multiply Op1 by Op2. If HIGH is set, only the upper half of the
1314 : result is returned.
1315 :
1316 : If HIGH is not set, throw away the upper half after the check is
1317 : made to see if it overflows. Unfortunately there is no better way
1318 : to check for overflow than to do this. If OVERFLOW is nonnull,
1319 : record in *OVERFLOW whether the result overflowed. SGN controls
1320 : the signedness and is used to check overflow or if HIGH is set.
1321 :
1322 : NOTE: Overflow type for signed overflow is not yet implemented. */
1323 : unsigned int
1324 1614724608 : wi::mul_internal (HOST_WIDE_INT *val, const HOST_WIDE_INT *op1val,
1325 : unsigned int op1len, const HOST_WIDE_INT *op2val,
1326 : unsigned int op2len, unsigned int prec, signop sgn,
1327 : wi::overflow_type *overflow, bool high)
1328 : {
1329 1614724608 : unsigned HOST_WIDE_INT o0, o1, k, t;
1330 1614724608 : unsigned int i;
1331 1614724608 : unsigned int j;
1332 :
1333 : /* If the top level routine did not really pass in an overflow, then
1334 : just make sure that we never attempt to set it. */
1335 1614724608 : bool needs_overflow = (overflow != 0);
1336 1614724608 : if (needs_overflow)
1337 481741572 : *overflow = wi::OVF_NONE;
1338 :
1339 1614724608 : wide_int_ref op1 = wi::storage_ref (op1val, op1len, prec);
1340 1614724608 : wide_int_ref op2 = wi::storage_ref (op2val, op2len, prec);
1341 :
1342 : /* This is a surprisingly common case, so do it first. */
1343 1614724608 : if (op1 == 0 || op2 == 0)
1344 : {
1345 624381632 : val[0] = 0;
1346 624381632 : return 1;
1347 : }
1348 :
1349 : #ifdef umul_ppmm
1350 990342976 : if (sgn == UNSIGNED)
1351 : {
1352 : /* If the inputs are single HWIs and the output has room for at
1353 : least two HWIs, we can use umul_ppmm directly. */
1354 957527295 : if (prec >= HOST_BITS_PER_WIDE_INT * 2
1355 890172216 : && wi::fits_uhwi_p (op1)
1356 1813565045 : && wi::fits_uhwi_p (op2))
1357 : {
1358 : /* This case never overflows. */
1359 854619494 : if (high)
1360 : {
1361 0 : val[0] = 0;
1362 0 : return 1;
1363 : }
1364 854619494 : umul_ppmm (val[1], val[0], op1.ulow (), op2.ulow ());
1365 854619494 : if (val[1] < 0 && prec > HOST_BITS_PER_WIDE_INT * 2)
1366 : {
1367 210060 : val[2] = 0;
1368 210060 : return 3;
1369 : }
1370 868248675 : return 1 + (val[1] != 0 || val[0] < 0);
1371 : }
1372 : /* Likewise if the output is a full single HWI, except that the
1373 : upper HWI of the result is only used for determining overflow.
1374 : (We handle this case inline when overflow isn't needed.) */
1375 102907801 : else if (prec == HOST_BITS_PER_WIDE_INT)
1376 : {
1377 56777931 : unsigned HOST_WIDE_INT upper;
1378 56777931 : umul_ppmm (upper, val[0], op1.ulow (), op2.ulow ());
1379 56777931 : if (needs_overflow)
1380 : /* Unsigned overflow can only be +OVERFLOW. */
1381 110549819 : *overflow = (upper != 0) ? wi::OVF_OVERFLOW : wi::OVF_NONE;
1382 56777931 : if (high)
1383 28 : val[0] = upper;
1384 : return 1;
1385 : }
1386 : }
1387 : #endif
1388 :
1389 : /* Handle multiplications by 1. */
1390 78945551 : if (op1 == 1)
1391 : {
1392 9059909 : if (high)
1393 : {
1394 231 : val[0] = wi::neg_p (op2, sgn) ? -1 : 0;
1395 231 : return 1;
1396 : }
1397 18158506 : for (i = 0; i < op2len; i++)
1398 9098828 : val[i] = op2val[i];
1399 : return op2len;
1400 : }
1401 69885642 : if (op2 == 1)
1402 : {
1403 17444320 : if (high)
1404 : {
1405 0 : val[0] = wi::neg_p (op1, sgn) ? -1 : 0;
1406 0 : return 1;
1407 : }
1408 34986212 : for (i = 0; i < op1len; i++)
1409 17541892 : val[i] = op1val[i];
1410 : return op1len;
1411 : }
1412 :
1413 : /* If we need to check for overflow, we can only do half wide
1414 : multiplies quickly because we need to look at the top bits to
1415 : check for the overflow. */
1416 52441322 : if ((high || needs_overflow)
1417 31219789 : && (prec <= HOST_BITS_PER_HALF_WIDE_INT))
1418 : {
1419 13278670 : unsigned HOST_WIDE_INT r;
1420 :
1421 13278670 : if (sgn == SIGNED)
1422 : {
1423 6297967 : o0 = op1.to_shwi ();
1424 6297967 : o1 = op2.to_shwi ();
1425 : }
1426 : else
1427 : {
1428 6980703 : o0 = op1.to_uhwi ();
1429 6980703 : o1 = op2.to_uhwi ();
1430 : }
1431 :
1432 13278670 : r = o0 * o1;
1433 13278670 : if (needs_overflow)
1434 : {
1435 13273548 : if (sgn == SIGNED)
1436 : {
1437 6293510 : if ((HOST_WIDE_INT) r != sext_hwi (r, prec))
1438 : /* FIXME: Signed overflow type is not implemented yet. */
1439 2545487 : *overflow = OVF_UNKNOWN;
1440 : }
1441 : else
1442 : {
1443 6980038 : if ((r >> prec) != 0)
1444 : /* Unsigned overflow can only be +OVERFLOW. */
1445 4540406 : *overflow = OVF_OVERFLOW;
1446 : }
1447 : }
1448 13278670 : val[0] = high ? r >> prec : r;
1449 13278670 : return 1;
1450 : }
1451 :
1452 : /* The sizes here are scaled to support a 2x WIDE_INT_MAX_INL_PRECISION by 2x
1453 : WIDE_INT_MAX_INL_PRECISION yielding a 4x WIDE_INT_MAX_INL_PRECISION
1454 : result. */
1455 :
1456 17941119 : unsigned HOST_HALF_WIDE_INT
1457 : ubuf[4 * WIDE_INT_MAX_INL_PRECISION / HOST_BITS_PER_HALF_WIDE_INT];
1458 17941119 : unsigned HOST_HALF_WIDE_INT
1459 : vbuf[4 * WIDE_INT_MAX_INL_PRECISION / HOST_BITS_PER_HALF_WIDE_INT];
1460 : /* The '2' in 'R' is because we are internally doing a full
1461 : multiply. */
1462 17941119 : unsigned HOST_HALF_WIDE_INT
1463 : rbuf[2 * 4 * WIDE_INT_MAX_INL_PRECISION / HOST_BITS_PER_HALF_WIDE_INT];
1464 57103765 : const HOST_WIDE_INT mask
1465 : = (HOST_WIDE_INT_1 << HOST_BITS_PER_HALF_WIDE_INT) - 1;
1466 57103765 : unsigned HOST_HALF_WIDE_INT *u = ubuf;
1467 57103765 : unsigned HOST_HALF_WIDE_INT *v = vbuf;
1468 57103765 : unsigned HOST_HALF_WIDE_INT *r = rbuf;
1469 :
1470 17941119 : if (!high)
1471 39162646 : prec = MIN ((op1len + op2len + 1) * HOST_BITS_PER_WIDE_INT, prec);
1472 39162652 : unsigned int blocks_needed = BLOCKS_NEEDED (prec);
1473 39162652 : unsigned int half_blocks_needed = blocks_needed * 2;
1474 39162652 : if (UNLIKELY (prec > WIDE_INT_MAX_INL_PRECISION))
1475 : {
1476 30526 : unsigned HOST_HALF_WIDE_INT *buf
1477 30526 : = XALLOCAVEC (unsigned HOST_HALF_WIDE_INT, 4 * half_blocks_needed);
1478 30526 : u = buf;
1479 30526 : v = u + half_blocks_needed;
1480 30526 : r = v + half_blocks_needed;
1481 : }
1482 :
1483 : /* We do unsigned mul and then correct it. */
1484 39162652 : wi_unpack (u, op1val, op1len, half_blocks_needed, prec, UNSIGNED);
1485 39162652 : wi_unpack (v, op2val, op2len, half_blocks_needed, prec, UNSIGNED);
1486 :
1487 : /* The 2 is for a full mult. */
1488 39162652 : memset (r, 0, half_blocks_needed * 2
1489 39162652 : * HOST_BITS_PER_HALF_WIDE_INT / CHAR_BIT);
1490 :
1491 202083864 : for (j = 0; j < half_blocks_needed; j++)
1492 : {
1493 : k = 0;
1494 11589073860 : for (i = 0; i < half_blocks_needed; i++)
1495 : {
1496 11426152648 : t = ((unsigned HOST_WIDE_INT)u[i] * (unsigned HOST_WIDE_INT)v[j]
1497 11426152648 : + r[i + j] + k);
1498 11426152648 : r[i + j] = t & HALF_INT_MASK;
1499 11426152648 : k = t >> HOST_BITS_PER_HALF_WIDE_INT;
1500 : }
1501 162921212 : r[j + half_blocks_needed] = k;
1502 : }
1503 :
1504 39162652 : unsigned int shift;
1505 39162652 : if ((high || needs_overflow) && (shift = prec % HOST_BITS_PER_WIDE_INT) != 0)
1506 : {
1507 : /* The high or needs_overflow code assumes that the high bits
1508 : only appear from r[half_blocks_needed] up to
1509 : r[half_blocks_needed * 2 - 1]. If prec is not a multiple
1510 : of HOST_BITS_PER_WIDE_INT, shift the bits above prec up
1511 : to make that code simple. */
1512 2961 : if (shift == HOST_BITS_PER_HALF_WIDE_INT)
1513 4 : memmove (&r[half_blocks_needed], &r[half_blocks_needed - 1],
1514 4 : sizeof (r[0]) * half_blocks_needed);
1515 : else
1516 : {
1517 2957 : unsigned int skip = shift < HOST_BITS_PER_HALF_WIDE_INT;
1518 2957 : if (!skip)
1519 2564 : shift -= HOST_BITS_PER_HALF_WIDE_INT;
1520 92275 : for (i = 2 * half_blocks_needed - 1; i >= half_blocks_needed; i--)
1521 89318 : r[i] = ((r[i - skip] << (-shift % HOST_BITS_PER_HALF_WIDE_INT))
1522 89318 : | (r[i - skip - 1] >> shift));
1523 : }
1524 : }
1525 :
1526 : /* We did unsigned math above. For signed we must adjust the
1527 : product (assuming we need to see that). */
1528 39162652 : if (sgn == SIGNED && (high || needs_overflow))
1529 : {
1530 17853230 : unsigned HOST_WIDE_INT b;
1531 17853230 : if (wi::neg_p (op1))
1532 : {
1533 : b = 0;
1534 24732685 : for (i = 0; i < half_blocks_needed; i++)
1535 : {
1536 16547326 : t = (unsigned HOST_WIDE_INT)r[i + half_blocks_needed]
1537 16547326 : - (unsigned HOST_WIDE_INT)v[i] - b;
1538 16547326 : r[i + half_blocks_needed] = t & HALF_INT_MASK;
1539 16547326 : b = t >> (HOST_BITS_PER_WIDE_INT - 1);
1540 : }
1541 : }
1542 17853230 : if (wi::neg_p (op2))
1543 : {
1544 : b = 0;
1545 5807482 : for (i = 0; i < half_blocks_needed; i++)
1546 : {
1547 3892618 : t = (unsigned HOST_WIDE_INT)r[i + half_blocks_needed]
1548 3892618 : - (unsigned HOST_WIDE_INT)u[i] - b;
1549 3892618 : r[i + half_blocks_needed] = t & HALF_INT_MASK;
1550 3892618 : b = t >> (HOST_BITS_PER_WIDE_INT - 1);
1551 : }
1552 : }
1553 : }
1554 :
1555 39162652 : if (needs_overflow)
1556 : {
1557 17941113 : HOST_WIDE_INT top;
1558 :
1559 : /* For unsigned, overflow is true if any of the top bits are set.
1560 : For signed, overflow is true if any of the top bits are not equal
1561 : to the sign bit. */
1562 17941113 : if (sgn == UNSIGNED)
1563 : top = 0;
1564 : else
1565 : {
1566 17853224 : top = r[half_blocks_needed - 1
1567 17853224 : - ((-prec % HOST_BITS_PER_WIDE_INT)
1568 17853224 : >= HOST_BITS_PER_HALF_WIDE_INT)];
1569 17853224 : top = SIGN_MASK (((unsigned HOST_WIDE_INT) top)
1570 : << (HOST_BITS_PER_WIDE_INT / 2
1571 : + (-prec % HOST_BITS_PER_HALF_WIDE_INT)));
1572 17853224 : top &= mask;
1573 : }
1574 :
1575 17941113 : unsigned int end = half_blocks_needed * 2;
1576 17941113 : shift = prec % HOST_BITS_PER_WIDE_INT;
1577 17941113 : if (shift)
1578 : {
1579 : /* For overflow checking only look at the first prec bits
1580 : starting with r[half_blocks_needed]. */
1581 2961 : if (shift <= HOST_BITS_PER_HALF_WIDE_INT)
1582 397 : --end;
1583 2961 : shift %= HOST_BITS_PER_HALF_WIDE_INT;
1584 2961 : if (shift)
1585 : {
1586 2957 : if (top)
1587 1298 : r[end - 1] |= ((~(unsigned HOST_HALF_WIDE_INT) 0) << shift);
1588 : else
1589 1659 : r[end - 1] &= (((unsigned HOST_HALF_WIDE_INT) 1) << shift) - 1;
1590 : }
1591 : }
1592 63584418 : for (i = half_blocks_needed; i < end; i++)
1593 45643305 : if (((HOST_WIDE_INT)(r[i] & mask)) != top)
1594 : /* FIXME: Signed overflow type is not implemented yet. */
1595 18595736 : *overflow = (sgn == UNSIGNED) ? wi::OVF_OVERFLOW : wi::OVF_UNKNOWN;
1596 : }
1597 :
1598 39162652 : int r_offset = high ? half_blocks_needed : 0;
1599 39162652 : return wi_pack (val, &r[r_offset], half_blocks_needed, prec);
1600 : }
1601 :
1602 : /* Compute the population count of X. */
1603 : int
1604 172076426 : wi::popcount (const wide_int_ref &x)
1605 : {
1606 172076426 : unsigned int i;
1607 172076426 : int count;
1608 :
1609 : /* The high order block is special if it is the last block and the
1610 : precision is not an even multiple of HOST_BITS_PER_WIDE_INT. We
1611 : have to clear out any ones above the precision before doing
1612 : popcount on this block. */
1613 172076426 : count = x.precision - x.len * HOST_BITS_PER_WIDE_INT;
1614 172076426 : unsigned int stop = x.len;
1615 172076426 : if (count < 0)
1616 : {
1617 70481020 : count = popcount_hwi (x.uhigh () << -count);
1618 70481020 : stop -= 1;
1619 : }
1620 : else
1621 : {
1622 101595406 : if (x.sign_mask () >= 0)
1623 82591339 : count = 0;
1624 : }
1625 :
1626 274810674 : for (i = 0; i < stop; ++i)
1627 102734248 : count += popcount_hwi (x.val[i]);
1628 :
1629 172076426 : return count;
1630 : }
1631 :
1632 : /* Set VAL to OP0 - OP1. If OVERFLOW is nonnull, record in *OVERFLOW
1633 : whether the result overflows when OP0 and OP1 are treated as having
1634 : signedness SGN. Return the number of blocks in VAL. */
1635 : unsigned int
1636 75146742 : wi::sub_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0,
1637 : unsigned int op0len, const HOST_WIDE_INT *op1,
1638 : unsigned int op1len, unsigned int prec,
1639 : signop sgn, wi::overflow_type *overflow)
1640 : {
1641 75146742 : unsigned HOST_WIDE_INT o0 = 0;
1642 75146742 : unsigned HOST_WIDE_INT o1 = 0;
1643 75146742 : unsigned HOST_WIDE_INT x = 0;
1644 : /* We implement subtraction as an in place negate and add. Negation
1645 : is just inversion and add 1, so we can do the add of 1 by just
1646 : starting the borrow in of the first element at 1. */
1647 75146742 : unsigned HOST_WIDE_INT borrow = 0;
1648 75146742 : unsigned HOST_WIDE_INT old_borrow = 0;
1649 :
1650 75146742 : unsigned HOST_WIDE_INT mask0, mask1;
1651 75146742 : unsigned int i;
1652 :
1653 75146742 : unsigned int len = MAX (op0len, op1len);
1654 75146742 : mask0 = -top_bit_of (op0, op0len, prec);
1655 75146742 : mask1 = -top_bit_of (op1, op1len, prec);
1656 :
1657 : /* Subtract all of the explicitly defined elements. */
1658 225619925 : for (i = 0; i < len; i++)
1659 : {
1660 150473183 : o0 = i < op0len ? (unsigned HOST_WIDE_INT)op0[i] : mask0;
1661 150473183 : o1 = i < op1len ? (unsigned HOST_WIDE_INT)op1[i] : mask1;
1662 150473183 : x = o0 - o1 - borrow;
1663 150473183 : val[i] = x;
1664 150473183 : old_borrow = borrow;
1665 150473183 : borrow = borrow == 0 ? o0 < o1 : o0 <= o1;
1666 : }
1667 :
1668 75146742 : if (len * HOST_BITS_PER_WIDE_INT < prec)
1669 : {
1670 73500947 : val[len] = mask0 - mask1 - borrow;
1671 73500947 : len++;
1672 73500947 : if (overflow)
1673 1896396 : *overflow = (sgn == UNSIGNED && borrow) ? OVF_UNDERFLOW : OVF_NONE;
1674 : }
1675 1645795 : else if (overflow)
1676 : {
1677 427903 : unsigned int shift = -prec % HOST_BITS_PER_WIDE_INT;
1678 427903 : if (sgn == SIGNED)
1679 : {
1680 287214 : unsigned HOST_WIDE_INT x = (o0 ^ o1) & (val[len - 1] ^ o0);
1681 287214 : if ((HOST_WIDE_INT) (x << shift) < 0)
1682 : {
1683 35803 : if (o0 > o1)
1684 19527 : *overflow = OVF_UNDERFLOW;
1685 16276 : else if (o0 < o1)
1686 16276 : *overflow = OVF_OVERFLOW;
1687 : else
1688 0 : *overflow = OVF_NONE;
1689 : }
1690 : else
1691 251411 : *overflow = OVF_NONE;
1692 : }
1693 : else
1694 : {
1695 : /* Put the MSB of X and O0 and in the top of the HWI. */
1696 140689 : x <<= shift;
1697 140689 : o0 <<= shift;
1698 140689 : if (old_borrow)
1699 122975 : *overflow = (x >= o0) ? OVF_UNDERFLOW : OVF_NONE;
1700 : else
1701 133714 : *overflow = (x > o0) ? OVF_UNDERFLOW : OVF_NONE;
1702 : }
1703 : }
1704 :
1705 75146742 : return canonize (val, len, prec);
1706 : }
1707 :
1708 :
1709 : /*
1710 : * Division and Mod
1711 : */
1712 :
1713 : /* Compute B_QUOTIENT and B_REMAINDER from B_DIVIDEND/B_DIVISOR. The
1714 : algorithm is a small modification of the algorithm in Hacker's
1715 : Delight by Warren, which itself is a small modification of Knuth's
1716 : algorithm. M is the number of significant elements of U however
1717 : there needs to be at least one extra element of B_DIVIDEND
1718 : allocated, N is the number of elements of B_DIVISOR.
1719 : Return new value for N. */
1720 : static int
1721 2729811 : divmod_internal_2 (unsigned HOST_HALF_WIDE_INT *b_quotient,
1722 : unsigned HOST_HALF_WIDE_INT *b_remainder,
1723 : unsigned HOST_HALF_WIDE_INT *b_dividend,
1724 : unsigned HOST_HALF_WIDE_INT *b_divisor,
1725 : int m, int n)
1726 : {
1727 : /* The "digits" are a HOST_HALF_WIDE_INT which the size of half of a
1728 : HOST_WIDE_INT and stored in the lower bits of each word. This
1729 : algorithm should work properly on both 32 and 64 bit
1730 : machines. */
1731 2729811 : unsigned HOST_WIDE_INT b = HOST_WIDE_INT_1U << HOST_BITS_PER_HALF_WIDE_INT;
1732 2729811 : unsigned HOST_WIDE_INT qhat; /* Estimate of quotient digit. */
1733 2729811 : unsigned HOST_WIDE_INT rhat; /* A remainder. */
1734 2729811 : unsigned HOST_WIDE_INT p; /* Product of two digits. */
1735 2729811 : HOST_WIDE_INT t, k;
1736 2729811 : int i, j, s;
1737 :
1738 : /* Single digit divisor. */
1739 2729811 : if (n == 1)
1740 : {
1741 833773 : k = 0;
1742 3439895 : for (j = m - 1; j >= 0; j--)
1743 : {
1744 2606122 : b_quotient[j] = (k * b + b_dividend[j])/b_divisor[0];
1745 2606122 : k = ((k * b + b_dividend[j])
1746 2606122 : - ((unsigned HOST_WIDE_INT)b_quotient[j]
1747 2606122 : * (unsigned HOST_WIDE_INT)b_divisor[0]));
1748 : }
1749 833773 : b_remainder[0] = k;
1750 833773 : return 1;
1751 : }
1752 :
1753 1896038 : s = clz_hwi (b_divisor[n-1]) - HOST_BITS_PER_HALF_WIDE_INT; /* CHECK clz */
1754 :
1755 1896038 : if (s)
1756 : {
1757 : /* Normalize B_DIVIDEND and B_DIVISOR. Unlike the published
1758 : algorithm, we can overwrite b_dividend and b_divisor, so we do
1759 : that. */
1760 3847281 : for (i = n - 1; i > 0; i--)
1761 1955877 : b_divisor[i] = (b_divisor[i] << s)
1762 1955877 : | (b_divisor[i-1] >> (HOST_BITS_PER_HALF_WIDE_INT - s));
1763 1891404 : b_divisor[0] = b_divisor[0] << s;
1764 :
1765 1891404 : b_dividend[m] = b_dividend[m-1] >> (HOST_BITS_PER_HALF_WIDE_INT - s);
1766 5732563 : for (i = m - 1; i > 0; i--)
1767 3841159 : b_dividend[i] = (b_dividend[i] << s)
1768 3841159 : | (b_dividend[i-1] >> (HOST_BITS_PER_HALF_WIDE_INT - s));
1769 1891404 : b_dividend[0] = b_dividend[0] << s;
1770 : }
1771 :
1772 : /* Main loop. */
1773 5686620 : for (j = m - n; j >= 0; j--)
1774 : {
1775 3790582 : qhat = (b_dividend[j+n] * b + b_dividend[j+n-1]) / b_divisor[n-1];
1776 3790582 : rhat = (b_dividend[j+n] * b + b_dividend[j+n-1]) - qhat * b_divisor[n-1];
1777 3805365 : again:
1778 3805365 : if (qhat >= b || qhat * b_divisor[n-2] > b * rhat + b_dividend[j+n-2])
1779 : {
1780 17629 : qhat -= 1;
1781 17629 : rhat += b_divisor[n-1];
1782 17629 : if (rhat < b)
1783 14783 : goto again;
1784 : }
1785 :
1786 : /* Multiply and subtract. */
1787 3790582 : k = 0;
1788 11524119 : for (i = 0; i < n; i++)
1789 : {
1790 7733537 : p = qhat * b_divisor[i];
1791 7733537 : t = b_dividend[i+j] - k - (p & HALF_INT_MASK);
1792 7733537 : b_dividend[i + j] = t;
1793 7733537 : k = ((p >> HOST_BITS_PER_HALF_WIDE_INT)
1794 7733537 : - (t >> HOST_BITS_PER_HALF_WIDE_INT));
1795 : }
1796 3790582 : t = b_dividend[j+n] - k;
1797 3790582 : b_dividend[j+n] = t;
1798 :
1799 3790582 : b_quotient[j] = qhat;
1800 3790582 : if (t < 0)
1801 : {
1802 7774 : b_quotient[j] -= 1;
1803 7774 : k = 0;
1804 64408 : for (i = 0; i < n; i++)
1805 : {
1806 56634 : t = (HOST_WIDE_INT)b_dividend[i+j] + b_divisor[i] + k;
1807 56634 : b_dividend[i+j] = t;
1808 56634 : k = t >> HOST_BITS_PER_HALF_WIDE_INT;
1809 : }
1810 7774 : b_dividend[j+n] += k;
1811 : }
1812 : }
1813 : /* If N > M, the main loop was skipped, quotient will be 0 and
1814 : we can't copy more than M half-limbs into the remainder, as they
1815 : aren't present in b_dividend (which has . */
1816 1896038 : n = MIN (n, m);
1817 1896038 : if (s)
1818 5728656 : for (i = 0; i < n; i++)
1819 3837252 : b_remainder[i] = (b_dividend[i] >> s)
1820 3837252 : | (b_dividend[i+1] << (HOST_BITS_PER_HALF_WIDE_INT - s));
1821 : else
1822 17342 : for (i = 0; i < n; i++)
1823 12708 : b_remainder[i] = b_dividend[i];
1824 : return n;
1825 : }
1826 :
1827 :
1828 : /* Divide DIVIDEND by DIVISOR, which have signedness SGN, and truncate
1829 : the result. If QUOTIENT is nonnull, store the value of the quotient
1830 : there and return the number of blocks in it. The return value is
1831 : not defined otherwise. If REMAINDER is nonnull, store the value
1832 : of the remainder there and store the number of blocks in
1833 : *REMAINDER_LEN. If OFLOW is not null, store in *OFLOW whether
1834 : the division overflowed. */
1835 : unsigned int
1836 672434115 : wi::divmod_internal (HOST_WIDE_INT *quotient, unsigned int *remainder_len,
1837 : HOST_WIDE_INT *remainder,
1838 : const HOST_WIDE_INT *dividend_val,
1839 : unsigned int dividend_len, unsigned int dividend_prec,
1840 : const HOST_WIDE_INT *divisor_val, unsigned int divisor_len,
1841 : unsigned int divisor_prec, signop sgn,
1842 : wi::overflow_type *oflow)
1843 : {
1844 672434115 : unsigned int m, n;
1845 672434115 : bool dividend_neg = false;
1846 672434115 : bool divisor_neg = false;
1847 672434115 : bool overflow = false;
1848 672434115 : wide_int neg_dividend, neg_divisor;
1849 :
1850 672434115 : wide_int_ref dividend = wi::storage_ref (dividend_val, dividend_len,
1851 672434115 : dividend_prec);
1852 672434115 : wide_int_ref divisor = wi::storage_ref (divisor_val, divisor_len,
1853 672434115 : divisor_prec);
1854 672434115 : if (divisor == 0)
1855 : overflow = true;
1856 :
1857 : /* The smallest signed number / -1 causes overflow. The dividend_len
1858 : check is for speed rather than correctness. */
1859 672434115 : if (sgn == SIGNED
1860 59619883 : && dividend_len == BLOCKS_NEEDED (dividend_prec)
1861 25895745 : && divisor == -1
1862 673321225 : && wi::only_sign_bit_p (dividend))
1863 226289 : overflow = true;
1864 :
1865 : /* Handle the overflow cases. Viewed as unsigned value, the quotient of
1866 : (signed min / -1) has the same representation as the original dividend.
1867 : We have traditionally made division by zero act as division by one,
1868 : so there too we use the original dividend. */
1869 672434115 : if (overflow)
1870 : {
1871 229187 : if (remainder)
1872 : {
1873 4036 : *remainder_len = 1;
1874 4036 : remainder[0] = 0;
1875 : }
1876 229187 : if (oflow)
1877 224598 : *oflow = OVF_OVERFLOW;
1878 229187 : if (quotient)
1879 456701 : for (unsigned int i = 0; i < dividend_len; ++i)
1880 229129 : quotient[i] = dividend_val[i];
1881 : return dividend_len;
1882 : }
1883 :
1884 672204928 : if (oflow)
1885 617897331 : *oflow = OVF_NONE;
1886 :
1887 : /* Do it on the host if you can. */
1888 672204928 : if (sgn == SIGNED
1889 59390879 : && wi::fits_shwi_p (dividend)
1890 731475329 : && wi::fits_shwi_p (divisor))
1891 : {
1892 59269946 : HOST_WIDE_INT o0 = dividend.to_shwi ();
1893 59269946 : HOST_WIDE_INT o1 = divisor.to_shwi ();
1894 :
1895 59269946 : if (o0 == HOST_WIDE_INT_MIN && o1 == -1)
1896 : {
1897 0 : gcc_checking_assert (dividend_prec > HOST_BITS_PER_WIDE_INT);
1898 0 : if (quotient)
1899 : {
1900 0 : quotient[0] = HOST_WIDE_INT_MIN;
1901 0 : quotient[1] = 0;
1902 : }
1903 0 : if (remainder)
1904 : {
1905 0 : remainder[0] = 0;
1906 0 : *remainder_len = 1;
1907 : }
1908 : return 2;
1909 : }
1910 : else
1911 : {
1912 59269946 : if (quotient)
1913 37570832 : quotient[0] = o0 / o1;
1914 59269946 : if (remainder)
1915 : {
1916 22407172 : remainder[0] = o0 % o1;
1917 22407172 : *remainder_len = 1;
1918 : }
1919 : return 1;
1920 : }
1921 : }
1922 :
1923 612934982 : if (sgn == UNSIGNED
1924 612814049 : && wi::fits_uhwi_p (dividend)
1925 1223143465 : && wi::fits_uhwi_p (divisor))
1926 : {
1927 610205171 : unsigned HOST_WIDE_INT o0 = dividend.to_uhwi ();
1928 610205171 : unsigned HOST_WIDE_INT o1 = divisor.to_uhwi ();
1929 610205171 : unsigned int quotient_len = 1;
1930 :
1931 610205171 : if (quotient)
1932 : {
1933 599788889 : quotient[0] = o0 / o1;
1934 599788889 : quotient_len = canonize_uhwi (quotient, dividend_prec);
1935 : }
1936 610205171 : if (remainder)
1937 : {
1938 249811241 : remainder[0] = o0 % o1;
1939 249812103 : *remainder_len = canonize_uhwi (remainder, dividend_prec);
1940 : }
1941 : return quotient_len;
1942 : }
1943 :
1944 : /* Make the divisor and dividend positive and remember what we
1945 : did. */
1946 2729811 : if (sgn == SIGNED)
1947 : {
1948 120933 : if (wi::neg_p (dividend))
1949 : {
1950 24936 : neg_dividend = -dividend;
1951 24936 : dividend = neg_dividend;
1952 24936 : dividend_neg = true;
1953 : }
1954 120933 : if (wi::neg_p (divisor))
1955 : {
1956 4595 : neg_divisor = -divisor;
1957 4595 : divisor = neg_divisor;
1958 4595 : divisor_neg = true;
1959 : }
1960 : }
1961 :
1962 : unsigned HOST_HALF_WIDE_INT
1963 : b_quotient_buf[4 * WIDE_INT_MAX_INL_PRECISION
1964 : / HOST_BITS_PER_HALF_WIDE_INT];
1965 : unsigned HOST_HALF_WIDE_INT
1966 : b_remainder_buf[4 * WIDE_INT_MAX_INL_PRECISION
1967 : / HOST_BITS_PER_HALF_WIDE_INT];
1968 : unsigned HOST_HALF_WIDE_INT
1969 : b_dividend_buf[(4 * WIDE_INT_MAX_INL_PRECISION
1970 : / HOST_BITS_PER_HALF_WIDE_INT) + 1];
1971 : unsigned HOST_HALF_WIDE_INT
1972 : b_divisor_buf[4 * WIDE_INT_MAX_INL_PRECISION
1973 : / HOST_BITS_PER_HALF_WIDE_INT];
1974 5282131 : unsigned HOST_HALF_WIDE_INT *b_quotient = b_quotient_buf;
1975 5282131 : unsigned HOST_HALF_WIDE_INT *b_remainder = b_remainder_buf;
1976 5282131 : unsigned HOST_HALF_WIDE_INT *b_dividend = b_dividend_buf;
1977 5282131 : unsigned HOST_HALF_WIDE_INT *b_divisor = b_divisor_buf;
1978 :
1979 2608878 : if (sgn == SIGNED || dividend_val[dividend_len - 1] >= 0)
1980 2673253 : dividend_prec = MIN ((dividend_len + 1) * HOST_BITS_PER_WIDE_INT,
1981 : dividend_prec);
1982 2729811 : if (sgn == SIGNED || divisor_val[divisor_len - 1] >= 0)
1983 2727422 : divisor_prec = MIN (divisor_len * HOST_BITS_PER_WIDE_INT, divisor_prec);
1984 2729811 : unsigned int dividend_blocks_needed = 2 * BLOCKS_NEEDED (dividend_prec);
1985 2729811 : unsigned int divisor_blocks_needed = 2 * BLOCKS_NEEDED (divisor_prec);
1986 2729811 : if (UNLIKELY (dividend_prec > WIDE_INT_MAX_INL_PRECISION)
1987 2729104 : || UNLIKELY (divisor_prec > WIDE_INT_MAX_INL_PRECISION))
1988 : {
1989 824 : unsigned HOST_HALF_WIDE_INT *buf
1990 824 : = XALLOCAVEC (unsigned HOST_HALF_WIDE_INT,
1991 : 3 * dividend_blocks_needed + 1
1992 : + divisor_blocks_needed);
1993 824 : b_quotient = buf;
1994 824 : b_remainder = b_quotient + dividend_blocks_needed;
1995 824 : b_dividend = b_remainder + dividend_blocks_needed;
1996 824 : b_divisor = b_dividend + dividend_blocks_needed + 1;
1997 824 : memset (b_quotient, 0,
1998 : dividend_blocks_needed * sizeof (HOST_HALF_WIDE_INT));
1999 : }
2000 2729811 : wi_unpack (b_dividend, dividend.get_val (), dividend.get_len (),
2001 : dividend_blocks_needed, dividend_prec, UNSIGNED);
2002 2729811 : wi_unpack (b_divisor, divisor.get_val (), divisor.get_len (),
2003 : divisor_blocks_needed, divisor_prec, UNSIGNED);
2004 :
2005 2729811 : m = dividend_blocks_needed;
2006 2729811 : b_dividend[m] = 0;
2007 5562042 : while (m > 1 && b_dividend[m - 1] == 0)
2008 : m--;
2009 :
2010 : n = divisor_blocks_needed;
2011 3573366 : while (n > 1 && b_divisor[n - 1] == 0)
2012 : n--;
2013 :
2014 2729811 : if (b_quotient == b_quotient_buf)
2015 2728987 : memset (b_quotient_buf, 0, sizeof (b_quotient_buf));
2016 :
2017 2729811 : n = divmod_internal_2 (b_quotient, b_remainder, b_dividend, b_divisor, m, n);
2018 :
2019 2729811 : unsigned int quotient_len = 0;
2020 2729811 : if (quotient)
2021 : {
2022 2669040 : quotient_len = wi_pack (quotient, b_quotient, m, dividend_prec);
2023 : /* The quotient is neg if exactly one of the divisor or dividend is
2024 : neg. */
2025 2669040 : if (dividend_neg != divisor_neg)
2026 24071 : quotient_len = wi::sub_large (quotient, zeros, 1, quotient,
2027 : quotient_len, dividend_prec,
2028 : UNSIGNED, 0);
2029 : }
2030 :
2031 2729811 : if (remainder)
2032 : {
2033 2538189 : *remainder_len = wi_pack (remainder, b_remainder, n, dividend_prec);
2034 : /* The remainder is always the same sign as the dividend. */
2035 2538189 : if (dividend_neg)
2036 2116 : *remainder_len = wi::sub_large (remainder, zeros, 1, remainder,
2037 : *remainder_len, dividend_prec,
2038 : UNSIGNED, 0);
2039 : }
2040 :
2041 : return quotient_len;
2042 672434115 : }
2043 :
2044 : /*
2045 : * Shifting, rotating and extraction.
2046 : */
2047 :
2048 : /* Left shift XVAL by SHIFT and store the result in VAL. Return the
2049 : number of blocks in VAL. Both XVAL and VAL have PRECISION bits. */
2050 : unsigned int
2051 1878764496 : wi::lshift_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
2052 : unsigned int xlen, unsigned int precision,
2053 : unsigned int shift)
2054 : {
2055 : /* Split the shift into a whole-block shift and a subblock shift. */
2056 1878764496 : unsigned int skip = shift / HOST_BITS_PER_WIDE_INT;
2057 1878764496 : unsigned int small_shift = shift % HOST_BITS_PER_WIDE_INT;
2058 :
2059 : /* The whole-block shift fills with zeros. */
2060 1878764496 : unsigned int len = BLOCKS_NEEDED (precision);
2061 1878764496 : len = MIN (xlen + skip + 1, len);
2062 1881584713 : for (unsigned int i = 0; i < skip; ++i)
2063 2820217 : val[i] = 0;
2064 :
2065 : /* It's easier to handle the simple block case specially. */
2066 1878764496 : if (small_shift == 0)
2067 53944431 : for (unsigned int i = skip; i < len; ++i)
2068 94577340 : val[i] = safe_uhwi (xval, xlen, i - skip);
2069 : else
2070 : {
2071 : /* The first unfilled output block is a left shift of the first
2072 : block in XVAL. The other output blocks contain bits from two
2073 : consecutive input blocks. */
2074 : unsigned HOST_WIDE_INT carry = 0;
2075 5657377384 : for (unsigned int i = skip; i < len; ++i)
2076 : {
2077 3785268649 : unsigned HOST_WIDE_INT x = safe_uhwi (xval, xlen, i - skip);
2078 3785268649 : val[i] = (x << small_shift) | carry;
2079 3785268649 : carry = x >> (-small_shift % HOST_BITS_PER_WIDE_INT);
2080 : }
2081 : }
2082 1878764496 : return canonize (val, len, precision);
2083 : }
2084 :
2085 : /* Right shift XVAL by SHIFT and store the result in VAL. LEN is the
2086 : number of blocks in VAL. The input has XPRECISION bits and the
2087 : output has XPRECISION - SHIFT bits. */
2088 : static void
2089 172674681 : rshift_large_common (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
2090 : unsigned int xlen, unsigned int shift, unsigned int len)
2091 : {
2092 : /* Split the shift into a whole-block shift and a subblock shift. */
2093 172674681 : unsigned int skip = shift / HOST_BITS_PER_WIDE_INT;
2094 172674681 : unsigned int small_shift = shift % HOST_BITS_PER_WIDE_INT;
2095 :
2096 : /* It's easier to handle the simple block case specially. */
2097 172674681 : if (small_shift == 0)
2098 3811967 : for (unsigned int i = 0; i < len; ++i)
2099 4405596 : val[i] = safe_uhwi (xval, xlen, i + skip);
2100 : else
2101 : {
2102 : /* Each output block but the last is a combination of two input blocks.
2103 : The last block is a right shift of the last block in XVAL. */
2104 171065512 : unsigned HOST_WIDE_INT curr = safe_uhwi (xval, xlen, skip);
2105 344378703 : for (unsigned int i = 0; i < len; ++i)
2106 : {
2107 173313191 : val[i] = curr >> small_shift;
2108 173313191 : curr = safe_uhwi (xval, xlen, i + skip + 1);
2109 173313191 : val[i] |= curr << (-small_shift % HOST_BITS_PER_WIDE_INT);
2110 : }
2111 : }
2112 172674681 : }
2113 :
2114 : /* Logically right shift XVAL by SHIFT and store the result in VAL.
2115 : Return the number of blocks in VAL. XVAL has XPRECISION bits and
2116 : VAL has PRECISION bits. */
2117 : unsigned int
2118 3689559 : wi::lrshift_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
2119 : unsigned int xlen, unsigned int xprecision,
2120 : unsigned int precision, unsigned int shift)
2121 : {
2122 : /* Work out how many blocks are needed to store the significant bits
2123 : (excluding the upper zeros or signs). */
2124 3689559 : unsigned int blocks_needed = BLOCKS_NEEDED (xprecision - shift);
2125 3689559 : unsigned int len = blocks_needed;
2126 3689559 : if (len > xlen && xval[xlen - 1] >= 0)
2127 3689559 : len = xlen;
2128 :
2129 3689559 : rshift_large_common (val, xval, xlen, shift, len);
2130 :
2131 : /* The value we just created has precision XPRECISION - SHIFT.
2132 : Zero-extend it to wider precisions. */
2133 3689559 : if (precision > xprecision - shift && len == blocks_needed)
2134 : {
2135 888617 : unsigned int small_prec = (xprecision - shift) % HOST_BITS_PER_WIDE_INT;
2136 888617 : if (small_prec)
2137 56556 : val[len - 1] = zext_hwi (val[len - 1], small_prec);
2138 832061 : else if (val[len - 1] < 0)
2139 : {
2140 : /* Add a new block with a zero. */
2141 419472 : val[len++] = 0;
2142 419472 : return len;
2143 : }
2144 : }
2145 3270087 : return canonize (val, len, precision);
2146 : }
2147 :
2148 : /* Arithmetically right shift XVAL by SHIFT and store the result in VAL.
2149 : Return the number of blocks in VAL. XVAL has XPRECISION bits and
2150 : VAL has PRECISION bits. */
2151 : unsigned int
2152 168985122 : wi::arshift_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval,
2153 : unsigned int xlen, unsigned int xprecision,
2154 : unsigned int precision, unsigned int shift)
2155 : {
2156 : /* Work out how many blocks are needed to store the significant bits
2157 : (excluding the upper zeros or signs). */
2158 168985122 : unsigned int blocks_needed = BLOCKS_NEEDED (xprecision - shift);
2159 168985122 : unsigned int len = MIN (xlen, blocks_needed);
2160 :
2161 168985122 : rshift_large_common (val, xval, xlen, shift, len);
2162 :
2163 : /* The value we just created has precision XPRECISION - SHIFT.
2164 : Sign-extend it to wider types. */
2165 168985122 : if (precision > xprecision - shift && len == blocks_needed)
2166 : {
2167 51440 : unsigned int small_prec = (xprecision - shift) % HOST_BITS_PER_WIDE_INT;
2168 51440 : if (small_prec)
2169 5405 : val[len - 1] = sext_hwi (val[len - 1], small_prec);
2170 : }
2171 168985122 : return canonize (val, len, precision);
2172 : }
2173 :
2174 : /* Return the number of leading (upper) zeros in X. */
2175 : int
2176 1241188992 : wi::clz (const wide_int_ref &x)
2177 : {
2178 1241188992 : if (x.sign_mask () < 0)
2179 : /* The upper bit is set, so there are no leading zeros. */
2180 : return 0;
2181 :
2182 : /* Calculate how many bits there above the highest represented block. */
2183 699107264 : int count = x.precision - x.len * HOST_BITS_PER_WIDE_INT;
2184 :
2185 699107264 : unsigned HOST_WIDE_INT high = x.uhigh ();
2186 699107264 : if (count < 0)
2187 : /* The upper -COUNT bits of HIGH are not part of the value.
2188 : Clear them out. */
2189 289055470 : high = (high << -count) >> -count;
2190 :
2191 : /* We don't need to look below HIGH. Either HIGH is nonzero,
2192 : or the top bit of the block below is nonzero; clz_hwi is
2193 : HOST_BITS_PER_WIDE_INT in the latter case. */
2194 1393059822 : return count + clz_hwi (high);
2195 : }
2196 :
2197 : /* Return the number of redundant sign bits in X. (That is, the number
2198 : of bits immediately below the sign bit that have the same value as
2199 : the sign bit.) */
2200 : int
2201 40962345 : wi::clrsb (const wide_int_ref &x)
2202 : {
2203 : /* Calculate how many bits there above the highest represented block. */
2204 40962345 : int count = x.precision - x.len * HOST_BITS_PER_WIDE_INT;
2205 :
2206 40962345 : unsigned HOST_WIDE_INT high = x.uhigh ();
2207 40962345 : unsigned HOST_WIDE_INT mask = -1;
2208 40962345 : if (count < 0)
2209 : {
2210 : /* The upper -COUNT bits of HIGH are not part of the value.
2211 : Clear them from both MASK and HIGH. */
2212 2340007 : mask >>= -count;
2213 2340007 : high &= mask;
2214 : }
2215 :
2216 : /* If the top bit is 1, count the number of leading 1s. If the top
2217 : bit is zero, count the number of leading zeros. */
2218 40962345 : if (high > mask / 2)
2219 1703163 : high ^= mask;
2220 :
2221 : /* There are no sign bits below the top block, so we don't need to look
2222 : beyond HIGH. Note that clz_hwi is HOST_BITS_PER_WIDE_INT when
2223 : HIGH is 0. */
2224 40962345 : return count + clz_hwi (high) - 1;
2225 : }
2226 :
2227 : /* Return the number of trailing (lower) zeros in X. */
2228 : int
2229 592516391 : wi::ctz (const wide_int_ref &x)
2230 : {
2231 592516391 : if (x.len == 1 && x.ulow () == 0)
2232 46442596 : return x.precision;
2233 :
2234 : /* Having dealt with the zero case, there must be a block with a
2235 : nonzero bit. We don't care about the bits above the first 1. */
2236 : unsigned int i = 0;
2237 546613959 : while (x.val[i] == 0)
2238 540164 : ++i;
2239 546073795 : return i * HOST_BITS_PER_WIDE_INT + ctz_hwi (x.val[i]);
2240 : }
2241 :
2242 : /* If X is an exact power of 2, return the base-2 logarithm, otherwise
2243 : return -1. */
2244 : int
2245 18137946 : wi::exact_log2 (const wide_int_ref &x)
2246 : {
2247 : /* Reject cases where there are implicit -1 blocks above HIGH. */
2248 18137946 : if (x.len * HOST_BITS_PER_WIDE_INT < x.precision && x.sign_mask () < 0)
2249 : return -1;
2250 :
2251 : /* Set CRUX to the index of the entry that should be nonzero.
2252 : If the top block is zero then the next lowest block (if any)
2253 : must have the high bit set. */
2254 18131422 : unsigned int crux = x.len - 1;
2255 18131422 : if (crux > 0 && x.val[crux] == 0)
2256 24039 : crux -= 1;
2257 :
2258 : /* Check that all lower blocks are zero. */
2259 18132305 : for (unsigned int i = 0; i < crux; ++i)
2260 5680 : if (x.val[i] != 0)
2261 : return -1;
2262 :
2263 : /* Get a zero-extended form of block CRUX. */
2264 18126625 : unsigned HOST_WIDE_INT hwi = x.val[crux];
2265 18126625 : if ((crux + 1) * HOST_BITS_PER_WIDE_INT > x.precision)
2266 4282038 : hwi = zext_hwi (hwi, x.precision % HOST_BITS_PER_WIDE_INT);
2267 :
2268 : /* Now it's down to whether HWI is a power of 2. */
2269 18126625 : int res = ::exact_log2 (hwi);
2270 10715551 : if (res >= 0)
2271 10715551 : res += crux * HOST_BITS_PER_WIDE_INT;
2272 : return res;
2273 : }
2274 :
2275 : /* Return the base-2 logarithm of X, rounding down. Return -1 if X is 0. */
2276 : int
2277 11142350 : wi::floor_log2 (const wide_int_ref &x)
2278 : {
2279 11142350 : return x.precision - 1 - clz (x);
2280 : }
2281 :
2282 : /* Return the index of the first (lowest) set bit in X, counting from 1.
2283 : Return 0 if X is 0. */
2284 : int
2285 491 : wi::ffs (const wide_int_ref &x)
2286 : {
2287 491 : return eq_p (x, 0) ? 0 : ctz (x) + 1;
2288 : }
2289 :
2290 : /* Return true if sign-extending X to have precision PRECISION would give
2291 : the minimum signed value at that precision. */
2292 : bool
2293 37449210 : wi::only_sign_bit_p (const wide_int_ref &x, unsigned int precision)
2294 : {
2295 37449210 : return ctz (x) + 1 == int (precision);
2296 : }
2297 :
2298 : /* Return true if X represents the minimum signed value. */
2299 : bool
2300 35347638 : wi::only_sign_bit_p (const wide_int_ref &x)
2301 : {
2302 35347638 : return only_sign_bit_p (x, x.precision);
2303 : }
2304 :
2305 : /* Return VAL if VAL has no bits set outside MASK. Otherwise round VAL
2306 : down to the previous value that has no bits set outside MASK.
2307 : This rounding wraps for signed values if VAL is negative and
2308 : the top bit of MASK is clear.
2309 :
2310 : For example, round_down_for_mask (6, 0xf1) would give 1 and
2311 : round_down_for_mask (24, 0xf1) would give 17. */
2312 :
2313 : wide_int
2314 18469492 : wi::round_down_for_mask (const wide_int &val, const wide_int &mask)
2315 : {
2316 : /* Get the bits in VAL that are outside the mask. */
2317 18469492 : wide_int extra_bits = wi::bit_and_not (val, mask);
2318 18469492 : if (extra_bits == 0)
2319 18443611 : return val;
2320 :
2321 : /* Get a mask that includes the top bit in EXTRA_BITS and is all 1s
2322 : below that bit. */
2323 25881 : unsigned int precision = val.get_precision ();
2324 25881 : wide_int lower_mask = wi::mask (precision - wi::clz (extra_bits),
2325 25881 : false, precision);
2326 :
2327 : /* Clear the bits that aren't in MASK, but ensure that all bits
2328 : in MASK below the top cleared bit are set. */
2329 25881 : return (val & mask) | (mask & lower_mask);
2330 25881 : }
2331 :
2332 : /* Return VAL if VAL has no bits set outside MASK. Otherwise round VAL
2333 : up to the next value that has no bits set outside MASK. The rounding
2334 : wraps if there are no suitable values greater than VAL.
2335 :
2336 : For example, round_up_for_mask (6, 0xf1) would give 16 and
2337 : round_up_for_mask (24, 0xf1) would give 32. */
2338 :
2339 : wide_int
2340 18999868 : wi::round_up_for_mask (const wide_int &val, const wide_int &mask)
2341 : {
2342 : /* Get the bits in VAL that are outside the mask. */
2343 18999868 : wide_int extra_bits = wi::bit_and_not (val, mask);
2344 18999868 : if (extra_bits == 0)
2345 18995106 : return val;
2346 :
2347 : /* Get a mask that is all 1s above the top bit in EXTRA_BITS. */
2348 4762 : unsigned int precision = val.get_precision ();
2349 4762 : wide_int upper_mask = wi::mask (precision - wi::clz (extra_bits),
2350 4762 : true, precision);
2351 :
2352 : /* Get the bits of the mask that are above the top bit in EXTRA_BITS. */
2353 4762 : upper_mask &= mask;
2354 :
2355 : /* Conceptually we need to:
2356 :
2357 : - clear bits of VAL outside UPPER_MASK
2358 : - add the lowest bit in UPPER_MASK to VAL (or add 0 if UPPER_MASK is 0)
2359 : - propagate the carry through the bits of VAL in UPPER_MASK
2360 :
2361 : If (~VAL & UPPER_MASK) is nonzero, the carry eventually
2362 : reaches that bit and the process leaves all lower bits clear.
2363 : If (~VAL & UPPER_MASK) is zero then the result is also zero. */
2364 4762 : wide_int tmp = wi::bit_and_not (upper_mask, val);
2365 :
2366 4762 : return (val | tmp) & -tmp;
2367 4762 : }
2368 :
2369 : /* Compute the modular multiplicative inverse of A modulo B
2370 : using extended Euclid's algorithm. Assumes A and B are coprime,
2371 : and that A and B have the same precision. */
2372 : wide_int
2373 3840 : wi::mod_inv (const wide_int &a, const wide_int &b)
2374 : {
2375 : /* Verify the assumption. */
2376 3840 : gcc_checking_assert (wi::eq_p (wi::gcd (a, b), 1));
2377 :
2378 3840 : unsigned int p = a.get_precision () + 1;
2379 3840 : gcc_checking_assert (b.get_precision () + 1 == p);
2380 3840 : wide_int c = wide_int::from (a, p, UNSIGNED);
2381 3840 : wide_int d = wide_int::from (b, p, UNSIGNED);
2382 3840 : wide_int x0 = wide_int::from (0, p, UNSIGNED);
2383 3840 : wide_int x1 = wide_int::from (1, p, UNSIGNED);
2384 :
2385 3840 : if (wi::eq_p (b, 1))
2386 0 : return wide_int::from (1, p, UNSIGNED);
2387 :
2388 19676 : while (wi::gt_p (c, 1, UNSIGNED))
2389 : {
2390 15836 : wide_int t = d;
2391 15836 : wide_int q = wi::divmod_trunc (c, d, UNSIGNED, &d);
2392 15836 : c = t;
2393 15836 : wide_int s = x0;
2394 15836 : x0 = wi::sub (x1, wi::mul (q, x0));
2395 15836 : x1 = s;
2396 15836 : }
2397 3840 : if (wi::lt_p (x1, 0, SIGNED))
2398 3340 : x1 += d;
2399 3840 : return x1;
2400 3840 : }
2401 :
2402 : /* Return as many repetition of X.get_precision () bits from X
2403 : as fit into PREC. */
2404 : wide_int
2405 671 : wi::bit_repeat (const wide_int_ref &x, unsigned int prec)
2406 : {
2407 671 : unsigned int xprec = x.get_precision ();
2408 671 : if (xprec >= prec)
2409 0 : return wide_int::from (x, prec, UNSIGNED);
2410 671 : if (xprec <= HOST_BITS_PER_WIDE_INT && (HOST_BITS_PER_WIDE_INT % xprec) == 0)
2411 : {
2412 256 : unsigned HOST_WIDE_INT val = x.to_uhwi (xprec);
2413 1588 : while (xprec < HOST_BITS_PER_WIDE_INT)
2414 : {
2415 1076 : val |= val << xprec;
2416 1076 : xprec <<= 1;
2417 : }
2418 256 : wide_int ret = wide_int::create (prec);
2419 256 : HOST_WIDE_INT *v = ret.write_val (0);
2420 256 : unsigned int i = 0;
2421 532 : for (unsigned int p = 0; p < prec; p += HOST_BITS_PER_WIDE_INT)
2422 276 : v[i++] = val;
2423 256 : ret.set_len (i, false);
2424 256 : return ret;
2425 256 : }
2426 415 : wide_int ret = wide_int::from (x, prec, UNSIGNED), b;
2427 2626 : while (xprec < prec)
2428 : {
2429 1796 : ret |= (ret << xprec);
2430 1796 : xprec <<= 1;
2431 : }
2432 415 : return ret;
2433 415 : }
2434 :
2435 : /* Compute carry-less product of X and Y with precision PREC. */
2436 :
2437 : wide_int
2438 286 : wi::clmul (const wide_int_ref &x, const wide_int_ref &y, unsigned int prec)
2439 : {
2440 286 : wide_int a;
2441 286 : const wide_int_ref *b;
2442 286 : if (wi::popcount (x) >= wi::popcount (y))
2443 : {
2444 188 : a = wide_int::from (x, prec, UNSIGNED);
2445 188 : b = &y;
2446 : }
2447 : else
2448 : {
2449 98 : a = wide_int::from (y, prec, UNSIGNED);
2450 98 : b = &x;
2451 : }
2452 286 : unsigned int bprec = b->get_precision ();
2453 286 : wide_int r = wi::zero (prec);
2454 286 : unsigned int j = 0, k = 0;
2455 26500 : for (unsigned int i = 0; i < bprec; ++i)
2456 : {
2457 26214 : if (((((unsigned HOST_WIDE_INT) b->elt (k)) >> j) & 1) != 0)
2458 12555 : r ^= a << i;
2459 26214 : if (++j == HOST_BITS_PER_WIDE_INT)
2460 : {
2461 363 : j = 0;
2462 363 : ++k;
2463 : }
2464 : }
2465 286 : return r;
2466 286 : }
2467 :
2468 : /*
2469 : * Private utilities.
2470 : */
2471 :
2472 0 : void gt_ggc_mx (widest_int *) { }
2473 0 : void gt_pch_nx (widest_int *, void (*) (void *, void *), void *) { }
2474 0 : void gt_pch_nx (widest_int *) { }
2475 :
2476 : template void wide_int::dump () const;
2477 : template void generic_wide_int <wide_int_ref_storage <false> >::dump () const;
2478 : template void generic_wide_int <wide_int_ref_storage <true> >::dump () const;
2479 : template void offset_int::dump () const;
2480 : template void widest_int::dump () const;
2481 :
2482 : /* We could add all the above ::dump variants here, but wide_int and
2483 : widest_int should handle the common cases. Besides, you can always
2484 : call the dump method directly. */
2485 :
2486 : DEBUG_FUNCTION void
2487 0 : debug (const wide_int &ref)
2488 : {
2489 0 : ref.dump ();
2490 0 : }
2491 :
2492 : DEBUG_FUNCTION void
2493 0 : debug (const wide_int *ptr)
2494 : {
2495 0 : if (ptr)
2496 0 : debug (*ptr);
2497 : else
2498 0 : fprintf (stderr, "<nil>\n");
2499 0 : }
2500 :
2501 : DEBUG_FUNCTION void
2502 0 : debug (const widest_int &ref)
2503 : {
2504 0 : ref.dump ();
2505 0 : }
2506 :
2507 : DEBUG_FUNCTION void
2508 0 : debug (const widest_int *ptr)
2509 : {
2510 0 : if (ptr)
2511 0 : debug (*ptr);
2512 : else
2513 0 : fprintf (stderr, "<nil>\n");
2514 0 : }
2515 :
2516 : #if CHECKING_P
2517 :
2518 : namespace selftest {
2519 :
2520 : /* Selftests for wide ints. We run these multiple times, once per type. */
2521 :
2522 : /* Helper function for building a test value. */
2523 :
2524 : template <class VALUE_TYPE>
2525 : static VALUE_TYPE
2526 : from_int (int i);
2527 :
2528 : /* Specializations of the fixture for each wide-int type. */
2529 :
2530 : /* Specialization for VALUE_TYPE == wide_int. */
2531 :
2532 : template <>
2533 : wide_int
2534 20 : from_int (int i)
2535 : {
2536 20 : return wi::shwi (i, 32);
2537 : }
2538 :
2539 : /* Specialization for VALUE_TYPE == offset_int. */
2540 :
2541 : template <>
2542 : offset_int
2543 20 : from_int (int i)
2544 : {
2545 0 : return offset_int (i);
2546 : }
2547 :
2548 : /* Specialization for VALUE_TYPE == widest_int. */
2549 :
2550 : template <>
2551 : widest_int
2552 28 : from_int (int i)
2553 : {
2554 0 : return widest_int (i);
2555 : }
2556 :
2557 : /* Verify that print_dec (WI, ..., SGN) gives the expected string
2558 : representation (using base 10). */
2559 :
2560 : static void
2561 132 : assert_deceq (const char *expected, const wide_int_ref &wi, signop sgn)
2562 : {
2563 132 : char buf[WIDE_INT_PRINT_BUFFER_SIZE], *p = buf;
2564 132 : unsigned len;
2565 132 : if (print_dec_buf_size (wi, sgn, &len))
2566 0 : p = XALLOCAVEC (char, len);
2567 132 : print_dec (wi, p, sgn);
2568 132 : ASSERT_STREQ (expected, p);
2569 132 : }
2570 :
2571 : /* Likewise for base 16. */
2572 :
2573 : static void
2574 72 : assert_hexeq (const char *expected, const wide_int_ref &wi)
2575 : {
2576 72 : char buf[WIDE_INT_PRINT_BUFFER_SIZE], *p = buf;
2577 72 : unsigned len;
2578 72 : if (print_hex_buf_size (wi, &len))
2579 0 : p = XALLOCAVEC (char, len);
2580 72 : print_hex (wi, p);
2581 72 : ASSERT_STREQ (expected, p);
2582 72 : }
2583 :
2584 : /* Test cases. */
2585 :
2586 : /* Verify that print_dec and print_hex work for VALUE_TYPE. */
2587 :
2588 : template <class VALUE_TYPE>
2589 : static void
2590 12 : test_printing ()
2591 : {
2592 12 : VALUE_TYPE a = from_int<VALUE_TYPE> (42);
2593 12 : assert_deceq ("42", a, SIGNED);
2594 12 : assert_hexeq ("0x2a", a);
2595 12 : assert_hexeq ("0x1fffffffffffffffff", wi::shwi (-1, 69));
2596 12 : assert_hexeq ("0xffffffffffffffff", wi::mask (64, false, 69));
2597 12 : assert_hexeq ("0xffffffffffffffff", wi::mask <widest_int> (64, false));
2598 : if (WIDE_INT_MAX_INL_PRECISION > 128)
2599 : {
2600 12 : assert_hexeq ("0x20000000000000000fffffffffffffffe",
2601 24 : wi::lshift (1, 129) + wi::lshift (1, 64) - 2);
2602 12 : assert_hexeq ("0x200000000000004000123456789abcdef",
2603 24 : wi::lshift (1, 129) + wi::lshift (1, 74)
2604 44 : + wi::lshift (0x1234567, 32) + 0x89abcdef);
2605 : }
2606 12 : }
2607 :
2608 : /* Verify that various operations work correctly for VALUE_TYPE,
2609 : unary and binary, using both function syntax, and
2610 : overloaded-operators. */
2611 :
2612 : template <class VALUE_TYPE>
2613 : static void
2614 12 : test_ops ()
2615 : {
2616 12 : VALUE_TYPE a = from_int<VALUE_TYPE> (7);
2617 12 : VALUE_TYPE b = from_int<VALUE_TYPE> (3);
2618 :
2619 : /* Using functions. */
2620 12 : assert_deceq ("-7", wi::neg (a), SIGNED);
2621 12 : assert_deceq ("10", wi::add (a, b), SIGNED);
2622 12 : assert_deceq ("4", wi::sub (a, b), SIGNED);
2623 12 : assert_deceq ("-4", wi::sub (b, a), SIGNED);
2624 12 : assert_deceq ("21", wi::mul (a, b), SIGNED);
2625 :
2626 : /* Using operators. */
2627 12 : assert_deceq ("-7", -a, SIGNED);
2628 12 : assert_deceq ("10", a + b, SIGNED);
2629 12 : assert_deceq ("4", a - b, SIGNED);
2630 12 : assert_deceq ("-4", b - a, SIGNED);
2631 12 : assert_deceq ("21", a * b, SIGNED);
2632 12 : }
2633 :
2634 : /* Verify that various comparisons work correctly for VALUE_TYPE. */
2635 :
2636 : template <class VALUE_TYPE>
2637 : static void
2638 12 : test_comparisons ()
2639 : {
2640 12 : VALUE_TYPE a = from_int<VALUE_TYPE> (7);
2641 12 : VALUE_TYPE b = from_int<VALUE_TYPE> (3);
2642 :
2643 : /* == */
2644 12 : ASSERT_TRUE (wi::eq_p (a, a));
2645 12 : ASSERT_FALSE (wi::eq_p (a, b));
2646 :
2647 : /* != */
2648 12 : ASSERT_TRUE (wi::ne_p (a, b));
2649 12 : ASSERT_FALSE (wi::ne_p (a, a));
2650 :
2651 : /* < */
2652 12 : ASSERT_FALSE (wi::lts_p (a, a));
2653 12 : ASSERT_FALSE (wi::lts_p (a, b));
2654 12 : ASSERT_TRUE (wi::lts_p (b, a));
2655 :
2656 : /* <= */
2657 12 : ASSERT_TRUE (wi::les_p (a, a));
2658 12 : ASSERT_FALSE (wi::les_p (a, b));
2659 12 : ASSERT_TRUE (wi::les_p (b, a));
2660 :
2661 : /* > */
2662 12 : ASSERT_FALSE (wi::gts_p (a, a));
2663 12 : ASSERT_TRUE (wi::gts_p (a, b));
2664 12 : ASSERT_FALSE (wi::gts_p (b, a));
2665 :
2666 : /* >= */
2667 12 : ASSERT_TRUE (wi::ges_p (a, a));
2668 12 : ASSERT_TRUE (wi::ges_p (a, b));
2669 12 : ASSERT_FALSE (wi::ges_p (b, a));
2670 :
2671 : /* comparison */
2672 12 : ASSERT_EQ (-1, wi::cmps (b, a));
2673 12 : ASSERT_EQ (0, wi::cmps (a, a));
2674 12 : ASSERT_EQ (1, wi::cmps (a, b));
2675 12 : }
2676 :
2677 : /* Run all of the selftests, using the given VALUE_TYPE. */
2678 :
2679 : template <class VALUE_TYPE>
2680 12 : static void run_all_wide_int_tests ()
2681 : {
2682 12 : test_printing <VALUE_TYPE> ();
2683 12 : test_ops <VALUE_TYPE> ();
2684 12 : test_comparisons <VALUE_TYPE> ();
2685 12 : }
2686 :
2687 : /* Test overflow conditions. */
2688 :
2689 : static void
2690 4 : test_overflow ()
2691 : {
2692 4 : static int precs[] = { 31, 32, 33, 63, 64, 65, 127, 128 };
2693 4 : static int offsets[] = { 16, 1, 0 };
2694 36 : for (unsigned int i = 0; i < ARRAY_SIZE (precs); ++i)
2695 128 : for (unsigned int j = 0; j < ARRAY_SIZE (offsets); ++j)
2696 : {
2697 96 : int prec = precs[i];
2698 96 : int offset = offsets[j];
2699 96 : wi::overflow_type overflow;
2700 96 : wide_int sum, diff;
2701 :
2702 192 : sum = wi::add (wi::max_value (prec, UNSIGNED) - offset, 1,
2703 96 : UNSIGNED, &overflow);
2704 96 : ASSERT_EQ (sum, -offset);
2705 96 : ASSERT_EQ (overflow != wi::OVF_NONE, offset == 0);
2706 :
2707 192 : sum = wi::add (1, wi::max_value (prec, UNSIGNED) - offset,
2708 96 : UNSIGNED, &overflow);
2709 96 : ASSERT_EQ (sum, -offset);
2710 96 : ASSERT_EQ (overflow != wi::OVF_NONE, offset == 0);
2711 :
2712 192 : diff = wi::sub (wi::max_value (prec, UNSIGNED) - offset,
2713 96 : wi::max_value (prec, UNSIGNED),
2714 96 : UNSIGNED, &overflow);
2715 96 : ASSERT_EQ (diff, -offset);
2716 96 : ASSERT_EQ (overflow != wi::OVF_NONE, offset != 0);
2717 :
2718 192 : diff = wi::sub (wi::max_value (prec, UNSIGNED) - offset,
2719 192 : wi::max_value (prec, UNSIGNED) - 1,
2720 96 : UNSIGNED, &overflow);
2721 96 : ASSERT_EQ (diff, 1 - offset);
2722 96 : ASSERT_EQ (overflow != wi::OVF_NONE, offset > 1);
2723 96 : }
2724 4 : }
2725 :
2726 : /* Test the round_{down,up}_for_mask functions. */
2727 :
2728 : static void
2729 4 : test_round_for_mask ()
2730 : {
2731 4 : unsigned int prec = 18;
2732 4 : ASSERT_EQ (17, wi::round_down_for_mask (wi::shwi (17, prec),
2733 : wi::shwi (0xf1, prec)));
2734 4 : ASSERT_EQ (17, wi::round_up_for_mask (wi::shwi (17, prec),
2735 : wi::shwi (0xf1, prec)));
2736 :
2737 4 : ASSERT_EQ (1, wi::round_down_for_mask (wi::shwi (6, prec),
2738 : wi::shwi (0xf1, prec)));
2739 4 : ASSERT_EQ (16, wi::round_up_for_mask (wi::shwi (6, prec),
2740 : wi::shwi (0xf1, prec)));
2741 :
2742 4 : ASSERT_EQ (17, wi::round_down_for_mask (wi::shwi (24, prec),
2743 : wi::shwi (0xf1, prec)));
2744 4 : ASSERT_EQ (32, wi::round_up_for_mask (wi::shwi (24, prec),
2745 : wi::shwi (0xf1, prec)));
2746 :
2747 4 : ASSERT_EQ (0x011, wi::round_down_for_mask (wi::shwi (0x22, prec),
2748 : wi::shwi (0x111, prec)));
2749 4 : ASSERT_EQ (0x100, wi::round_up_for_mask (wi::shwi (0x22, prec),
2750 : wi::shwi (0x111, prec)));
2751 :
2752 4 : ASSERT_EQ (100, wi::round_down_for_mask (wi::shwi (101, prec),
2753 : wi::shwi (0xfc, prec)));
2754 4 : ASSERT_EQ (104, wi::round_up_for_mask (wi::shwi (101, prec),
2755 : wi::shwi (0xfc, prec)));
2756 :
2757 4 : ASSERT_EQ (0x2bc, wi::round_down_for_mask (wi::shwi (0x2c2, prec),
2758 : wi::shwi (0xabc, prec)));
2759 4 : ASSERT_EQ (0x800, wi::round_up_for_mask (wi::shwi (0x2c2, prec),
2760 : wi::shwi (0xabc, prec)));
2761 :
2762 4 : ASSERT_EQ (0xabc, wi::round_down_for_mask (wi::shwi (0xabd, prec),
2763 : wi::shwi (0xabc, prec)));
2764 4 : ASSERT_EQ (0, wi::round_up_for_mask (wi::shwi (0xabd, prec),
2765 : wi::shwi (0xabc, prec)));
2766 :
2767 4 : ASSERT_EQ (0xabc, wi::round_down_for_mask (wi::shwi (0x1000, prec),
2768 : wi::shwi (0xabc, prec)));
2769 4 : ASSERT_EQ (0, wi::round_up_for_mask (wi::shwi (0x1000, prec),
2770 : wi::shwi (0xabc, prec)));
2771 4 : }
2772 :
2773 : /* Run all of the selftests within this file, for all value types. */
2774 :
2775 : void
2776 4 : wide_int_cc_tests ()
2777 : {
2778 4 : run_all_wide_int_tests <wide_int> ();
2779 4 : run_all_wide_int_tests <offset_int> ();
2780 4 : run_all_wide_int_tests <widest_int> ();
2781 4 : test_overflow ();
2782 4 : test_round_for_mask ();
2783 4 : ASSERT_EQ (wi::mask (128, false, 128),
2784 : wi::shifted_mask (0, 128, false, 128));
2785 4 : ASSERT_EQ (wi::mask (128, true, 128),
2786 : wi::shifted_mask (0, 128, true, 128));
2787 4 : ASSERT_EQ (wi::multiple_of_p (from_int <widest_int> (1),
2788 : from_int <widest_int> (-128), UNSIGNED),
2789 : false);
2790 4 : }
2791 :
2792 : } // namespace selftest
2793 : #endif /* CHECKING_P */
|