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