]>
Commit | Line | Data |
---|---|---|
e913b5cd | 1 | /* Operations with very long integers. |
aad93da1 | 2 | Copyright (C) 2012-2017 Free Software Foundation, Inc. |
e913b5cd | 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" | |
e913b5cd | 25 | #include "tree.h" |
99b4f3a2 | 26 | #include "selftest.h" |
e913b5cd | 27 | |
f1714fa0 | 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 | ||
25b6c9eb | 38 | #define W_TYPE_SIZE HOST_BITS_PER_WIDE_INT |
fdfe65e2 | 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__) | |
25b6c9eb | 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))); | |
f7bd62a6 | 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 | |
25b6c9eb | 51 | #include "longlong.h" |
52 | #endif | |
53 | ||
796b6678 | 54 | static const HOST_WIDE_INT zeros[WIDE_INT_MAX_ELTS] = {}; |
e913b5cd | 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. */ | |
edc19fd0 | 62 | #define HALF_INT_MASK ((HOST_WIDE_INT_1 << HOST_BITS_PER_HALF_WIDE_INT) - 1) |
e913b5cd | 63 | |
64 | #define BLOCK_OF(TARGET) ((TARGET) / HOST_BITS_PER_WIDE_INT) | |
65 | #define BLOCKS_NEEDED(PREC) \ | |
66 | (PREC ? (((PREC) + HOST_BITS_PER_WIDE_INT - 1) / HOST_BITS_PER_WIDE_INT) : 1) | |
5b2cae25 | 67 | #define SIGN_MASK(X) ((HOST_WIDE_INT) (X) < 0 ? -1 : 0) |
e913b5cd | 68 | |
05363b4a | 69 | /* Return the value a VAL[I] if I < LEN, otherwise, return 0 or -1 |
70 | based on the top existing bit of VAL. */ | |
71 | ||
796b6678 | 72 | static unsigned HOST_WIDE_INT |
73 | safe_uhwi (const HOST_WIDE_INT *val, unsigned int len, unsigned int i) | |
e913b5cd | 74 | { |
edc19fd0 | 75 | return i < len ? val[i] : val[len - 1] < 0 ? HOST_WIDE_INT_M1 : 0; |
e913b5cd | 76 | } |
77 | ||
796b6678 | 78 | /* Convert the integer in VAL to canonical form, returning its new length. |
79 | LEN is the number of blocks currently in VAL and PRECISION is the number | |
80 | of bits in the integer it represents. | |
e913b5cd | 81 | |
796b6678 | 82 | This function only changes the representation, not the value. */ |
83 | static unsigned int | |
84 | canonize (HOST_WIDE_INT *val, unsigned int len, unsigned int precision) | |
e913b5cd | 85 | { |
796b6678 | 86 | unsigned int blocks_needed = BLOCKS_NEEDED (precision); |
87 | HOST_WIDE_INT top; | |
88 | int i; | |
e913b5cd | 89 | |
796b6678 | 90 | if (len > blocks_needed) |
91 | len = blocks_needed; | |
e913b5cd | 92 | |
796b6678 | 93 | if (len == 1) |
94 | return len; | |
e913b5cd | 95 | |
796b6678 | 96 | top = val[len - 1]; |
5b2cae25 | 97 | if (len * HOST_BITS_PER_WIDE_INT > precision) |
dae6a0c3 | 98 | val[len - 1] = top = sext_hwi (top, precision % HOST_BITS_PER_WIDE_INT); |
796b6678 | 99 | if (top != 0 && top != (HOST_WIDE_INT)-1) |
100 | return len; | |
e913b5cd | 101 | |
796b6678 | 102 | /* At this point we know that the top is either 0 or -1. Find the |
103 | first block that is not a copy of this. */ | |
104 | for (i = len - 2; i >= 0; i--) | |
e913b5cd | 105 | { |
796b6678 | 106 | HOST_WIDE_INT x = val[i]; |
107 | if (x != top) | |
e913b5cd | 108 | { |
796b6678 | 109 | if (SIGN_MASK (x) == top) |
110 | return i + 1; | |
111 | ||
112 | /* We need an extra block because the top bit block i does | |
113 | not match the extension. */ | |
114 | return i + 2; | |
e913b5cd | 115 | } |
116 | } | |
117 | ||
796b6678 | 118 | /* The number is 0 or -1. */ |
119 | return 1; | |
e913b5cd | 120 | } |
121 | ||
70bca70e | 122 | /* VAL[0] is the unsigned result of an operation. Canonize it by adding |
123 | another 0 block if needed, and return number of blocks needed. */ | |
124 | ||
125 | static inline unsigned int | |
126 | canonize_uhwi (HOST_WIDE_INT *val, unsigned int precision) | |
127 | { | |
128 | if (val[0] < 0 && precision > HOST_BITS_PER_WIDE_INT) | |
129 | { | |
130 | val[1] = 0; | |
131 | return 2; | |
132 | } | |
133 | return 1; | |
134 | } | |
135 | ||
796b6678 | 136 | /* |
9292279b | 137 | * Conversion routines in and out of wide_int. |
796b6678 | 138 | */ |
e913b5cd | 139 | |
796b6678 | 140 | /* Copy XLEN elements from XVAL to VAL. If NEED_CANON, canonize the |
141 | result for an integer with precision PRECISION. Return the length | |
142 | of VAL (after any canonization. */ | |
143 | unsigned int | |
144 | wi::from_array (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval, | |
145 | unsigned int xlen, unsigned int precision, bool need_canon) | |
146 | { | |
147 | for (unsigned i = 0; i < xlen; i++) | |
148 | val[i] = xval[i]; | |
149 | return need_canon ? canonize (val, xlen, precision) : xlen; | |
e913b5cd | 150 | } |
151 | ||
152 | /* Construct a wide int from a buffer of length LEN. BUFFER will be | |
d0abd9e0 | 153 | read according to byte endianness and word endianness of the target. |
e4712d1e | 154 | Only the lower BUFFER_LEN bytes of the result are set; the remaining |
155 | high bytes are cleared. */ | |
796b6678 | 156 | wide_int |
157 | wi::from_buffer (const unsigned char *buffer, unsigned int buffer_len) | |
e913b5cd | 158 | { |
796b6678 | 159 | unsigned int precision = buffer_len * BITS_PER_UNIT; |
160 | wide_int result = wide_int::create (precision); | |
161 | unsigned int words = buffer_len / UNITS_PER_WORD; | |
e913b5cd | 162 | |
163 | /* We have to clear all the bits ourself, as we merely or in values | |
164 | below. */ | |
796b6678 | 165 | unsigned int len = BLOCKS_NEEDED (precision); |
166 | HOST_WIDE_INT *val = result.write_val (); | |
167 | for (unsigned int i = 0; i < len; ++i) | |
168 | val[i] = 0; | |
e913b5cd | 169 | |
796b6678 | 170 | for (unsigned int byte = 0; byte < buffer_len; byte++) |
e913b5cd | 171 | { |
796b6678 | 172 | unsigned int offset; |
173 | unsigned int index; | |
174 | unsigned int bitpos = byte * BITS_PER_UNIT; | |
e913b5cd | 175 | unsigned HOST_WIDE_INT value; |
176 | ||
796b6678 | 177 | if (buffer_len > UNITS_PER_WORD) |
e913b5cd | 178 | { |
796b6678 | 179 | unsigned int word = byte / UNITS_PER_WORD; |
e913b5cd | 180 | |
181 | if (WORDS_BIG_ENDIAN) | |
182 | word = (words - 1) - word; | |
183 | ||
184 | offset = word * UNITS_PER_WORD; | |
185 | ||
186 | if (BYTES_BIG_ENDIAN) | |
187 | offset += (UNITS_PER_WORD - 1) - (byte % UNITS_PER_WORD); | |
188 | else | |
189 | offset += byte % UNITS_PER_WORD; | |
190 | } | |
191 | else | |
796b6678 | 192 | offset = BYTES_BIG_ENDIAN ? (buffer_len - 1) - byte : byte; |
e913b5cd | 193 | |
194 | value = (unsigned HOST_WIDE_INT) buffer[offset]; | |
195 | ||
196 | index = bitpos / HOST_BITS_PER_WIDE_INT; | |
796b6678 | 197 | val[index] |= value << (bitpos % HOST_BITS_PER_WIDE_INT); |
e913b5cd | 198 | } |
199 | ||
796b6678 | 200 | result.set_len (canonize (val, len, precision)); |
e913b5cd | 201 | |
202 | return result; | |
203 | } | |
204 | ||
28e557ef | 205 | /* Sets RESULT from X, the sign is taken according to SGN. */ |
e913b5cd | 206 | void |
28e557ef | 207 | wi::to_mpz (const wide_int_ref &x, mpz_t result, signop sgn) |
e913b5cd | 208 | { |
05363b4a | 209 | int len = x.get_len (); |
210 | const HOST_WIDE_INT *v = x.get_val (); | |
28e557ef | 211 | int excess = len * HOST_BITS_PER_WIDE_INT - x.get_precision (); |
e913b5cd | 212 | |
796b6678 | 213 | if (wi::neg_p (x, sgn)) |
e913b5cd | 214 | { |
e913b5cd | 215 | /* We use ones complement to avoid -x80..0 edge case that - |
216 | won't work on. */ | |
28e557ef | 217 | HOST_WIDE_INT *t = XALLOCAVEC (HOST_WIDE_INT, len); |
218 | for (int i = 0; i < len; i++) | |
219 | t[i] = ~v[i]; | |
220 | if (excess > 0) | |
221 | t[len - 1] = (unsigned HOST_WIDE_INT) t[len - 1] << excess >> excess; | |
222 | mpz_import (result, len, -1, sizeof (HOST_WIDE_INT), 0, 0, t); | |
223 | mpz_com (result, result); | |
e913b5cd | 224 | } |
28e557ef | 225 | else if (excess > 0) |
05363b4a | 226 | { |
28e557ef | 227 | HOST_WIDE_INT *t = XALLOCAVEC (HOST_WIDE_INT, len); |
05363b4a | 228 | for (int i = 0; i < len - 1; i++) |
229 | t[i] = v[i]; | |
28e557ef | 230 | t[len - 1] = (unsigned HOST_WIDE_INT) v[len - 1] << excess >> excess; |
05363b4a | 231 | mpz_import (result, len, -1, sizeof (HOST_WIDE_INT), 0, 0, t); |
232 | } | |
233 | else | |
234 | mpz_import (result, len, -1, sizeof (HOST_WIDE_INT), 0, 0, v); | |
e913b5cd | 235 | } |
236 | ||
e4712d1e | 237 | /* Returns X converted to TYPE. If WRAP is true, then out-of-range |
e913b5cd | 238 | values of VAL will be wrapped; otherwise, they will be set to the |
239 | appropriate minimum or maximum TYPE bound. */ | |
796b6678 | 240 | wide_int |
241 | wi::from_mpz (const_tree type, mpz_t x, bool wrap) | |
e913b5cd | 242 | { |
243 | size_t count, numb; | |
a140fb64 | 244 | unsigned int prec = TYPE_PRECISION (type); |
05363b4a | 245 | wide_int res = wide_int::create (prec); |
e913b5cd | 246 | |
247 | if (!wrap) | |
248 | { | |
249 | mpz_t min, max; | |
250 | ||
251 | mpz_init (min); | |
252 | mpz_init (max); | |
253 | get_type_static_bounds (type, min, max); | |
254 | ||
796b6678 | 255 | if (mpz_cmp (x, min) < 0) |
256 | mpz_set (x, min); | |
257 | else if (mpz_cmp (x, max) > 0) | |
258 | mpz_set (x, max); | |
e913b5cd | 259 | |
260 | mpz_clear (min); | |
261 | mpz_clear (max); | |
262 | } | |
263 | ||
264 | /* Determine the number of unsigned HOST_WIDE_INTs that are required | |
47dcac97 | 265 | for representing the absolute value. The code to calculate count is |
e913b5cd | 266 | extracted from the GMP manual, section "Integer Import and Export": |
267 | http://gmplib.org/manual/Integer-Import-and-Export.html */ | |
a140fb64 | 268 | numb = CHAR_BIT * sizeof (HOST_WIDE_INT); |
e4712d1e | 269 | count = (mpz_sizeinbase (x, 2) + numb - 1) / numb; |
796b6678 | 270 | HOST_WIDE_INT *val = res.write_val (); |
47dcac97 | 271 | /* Read the absolute value. |
272 | ||
273 | Write directly to the wide_int storage if possible, otherwise leave | |
a140fb64 | 274 | GMP to allocate the memory for us. It might be slightly more efficient |
275 | to use mpz_tdiv_r_2exp for the latter case, but the situation is | |
276 | pathological and it seems safer to operate on the original mpz value | |
277 | in all cases. */ | |
278 | void *valres = mpz_export (count <= WIDE_INT_MAX_ELTS ? val : 0, | |
279 | &count, -1, sizeof (HOST_WIDE_INT), 0, 0, x); | |
5b2cae25 | 280 | if (count < 1) |
281 | { | |
282 | val[0] = 0; | |
283 | count = 1; | |
284 | } | |
a140fb64 | 285 | count = MIN (count, BLOCKS_NEEDED (prec)); |
286 | if (valres != val) | |
287 | { | |
288 | memcpy (val, valres, count * sizeof (HOST_WIDE_INT)); | |
289 | free (valres); | |
290 | } | |
47dcac97 | 291 | /* Zero-extend the absolute value to PREC bits. */ |
292 | if (count < BLOCKS_NEEDED (prec) && val[count - 1] < 0) | |
293 | val[count++] = 0; | |
294 | else | |
295 | count = canonize (val, count, prec); | |
296 | res.set_len (count); | |
05363b4a | 297 | |
796b6678 | 298 | if (mpz_sgn (x) < 0) |
e913b5cd | 299 | res = -res; |
300 | ||
301 | return res; | |
302 | } | |
303 | ||
304 | /* | |
305 | * Largest and smallest values in a mode. | |
306 | */ | |
307 | ||
796b6678 | 308 | /* Return the largest SGNed number that is representable in PRECISION bits. |
50490037 | 309 | |
310 | TODO: There is still code from the double_int era that trys to | |
311 | make up for the fact that double int's could not represent the | |
312 | min and max values of all types. This code should be removed | |
313 | because the min and max values can always be represented in | |
9292279b | 314 | wide_ints and int-csts. */ |
796b6678 | 315 | wide_int |
316 | wi::max_value (unsigned int precision, signop sgn) | |
e913b5cd | 317 | { |
40df56fe | 318 | gcc_checking_assert (precision != 0); |
319 | if (sgn == UNSIGNED) | |
796b6678 | 320 | /* The unsigned max is just all ones. */ |
321 | return shwi (-1, precision); | |
e913b5cd | 322 | else |
323 | /* The signed max is all ones except the top bit. This must be | |
324 | explicitly represented. */ | |
796b6678 | 325 | return mask (precision - 1, false, precision); |
e913b5cd | 326 | } |
327 | ||
796b6678 | 328 | /* Return the largest SGNed number that is representable in PRECISION bits. */ |
329 | wide_int | |
330 | wi::min_value (unsigned int precision, signop sgn) | |
e913b5cd | 331 | { |
40df56fe | 332 | gcc_checking_assert (precision != 0); |
333 | if (sgn == UNSIGNED) | |
796b6678 | 334 | return uhwi (0, precision); |
e913b5cd | 335 | else |
796b6678 | 336 | /* The signed min is all zeros except the top bit. This must be |
337 | explicitly represented. */ | |
338 | return wi::set_bit_in_zero (precision - 1, precision); | |
e913b5cd | 339 | } |
340 | ||
341 | /* | |
342 | * Public utilities. | |
343 | */ | |
344 | ||
796b6678 | 345 | /* Convert the number represented by XVAL, XLEN and XPRECISION, which has |
346 | signedness SGN, to an integer that has PRECISION bits. Store the blocks | |
347 | in VAL and return the number of blocks used. | |
e913b5cd | 348 | |
796b6678 | 349 | This function can handle both extension (PRECISION > XPRECISION) |
350 | and truncation (PRECISION < XPRECISION). */ | |
351 | unsigned int | |
352 | wi::force_to_size (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval, | |
353 | unsigned int xlen, unsigned int xprecision, | |
354 | unsigned int precision, signop sgn) | |
e913b5cd | 355 | { |
796b6678 | 356 | unsigned int blocks_needed = BLOCKS_NEEDED (precision); |
357 | unsigned int len = blocks_needed < xlen ? blocks_needed : xlen; | |
358 | for (unsigned i = 0; i < len; i++) | |
359 | val[i] = xval[i]; | |
e913b5cd | 360 | |
796b6678 | 361 | if (precision > xprecision) |
e913b5cd | 362 | { |
5b2cae25 | 363 | unsigned int small_xprecision = xprecision % HOST_BITS_PER_WIDE_INT; |
364 | ||
796b6678 | 365 | /* Expanding. */ |
e913b5cd | 366 | if (sgn == UNSIGNED) |
367 | { | |
796b6678 | 368 | if (small_xprecision && len == BLOCKS_NEEDED (xprecision)) |
369 | val[len - 1] = zext_hwi (val[len - 1], small_xprecision); | |
370 | else if (val[len - 1] < 0) | |
e913b5cd | 371 | { |
796b6678 | 372 | while (len < BLOCKS_NEEDED (xprecision)) |
373 | val[len++] = -1; | |
374 | if (small_xprecision) | |
375 | val[len - 1] = zext_hwi (val[len - 1], small_xprecision); | |
376 | else | |
377 | val[len++] = 0; | |
e913b5cd | 378 | } |
379 | } | |
5b2cae25 | 380 | else |
381 | { | |
382 | if (small_xprecision && len == BLOCKS_NEEDED (xprecision)) | |
383 | val[len - 1] = sext_hwi (val[len - 1], small_xprecision); | |
384 | } | |
e913b5cd | 385 | } |
2e9ff529 | 386 | len = canonize (val, len, precision); |
e913b5cd | 387 | |
796b6678 | 388 | return len; |
e913b5cd | 389 | } |
390 | ||
391 | /* This function hides the fact that we cannot rely on the bits beyond | |
392 | the precision. This issue comes up in the relational comparisions | |
393 | where we do allow comparisons of values of different precisions. */ | |
394 | static inline HOST_WIDE_INT | |
395 | selt (const HOST_WIDE_INT *a, unsigned int len, | |
e4712d1e | 396 | unsigned int blocks_needed, unsigned int small_prec, |
397 | unsigned int index, signop sgn) | |
e913b5cd | 398 | { |
5b2cae25 | 399 | HOST_WIDE_INT val; |
400 | if (index < len) | |
401 | val = a[index]; | |
402 | else if (index < blocks_needed || sgn == SIGNED) | |
403 | /* Signed or within the precision. */ | |
404 | val = SIGN_MASK (a[len - 1]); | |
405 | else | |
406 | /* Unsigned extension beyond the precision. */ | |
407 | val = 0; | |
e913b5cd | 408 | |
5b2cae25 | 409 | if (small_prec && index == blocks_needed - 1) |
410 | return (sgn == SIGNED | |
411 | ? sext_hwi (val, small_prec) | |
412 | : zext_hwi (val, small_prec)); | |
05363b4a | 413 | else |
5b2cae25 | 414 | return val; |
e913b5cd | 415 | } |
416 | ||
05363b4a | 417 | /* Find the highest bit represented in a wide int. This will in |
e913b5cd | 418 | general have the same value as the sign bit. */ |
419 | static inline HOST_WIDE_INT | |
5b2cae25 | 420 | top_bit_of (const HOST_WIDE_INT *a, unsigned int len, unsigned int prec) |
e913b5cd | 421 | { |
5b2cae25 | 422 | int excess = len * HOST_BITS_PER_WIDE_INT - prec; |
423 | unsigned HOST_WIDE_INT val = a[len - 1]; | |
424 | if (excess > 0) | |
425 | val <<= excess; | |
426 | return val >> (HOST_BITS_PER_WIDE_INT - 1); | |
e913b5cd | 427 | } |
428 | ||
429 | /* | |
430 | * Comparisons, note that only equality is an operator. The other | |
e4712d1e | 431 | * comparisons cannot be operators since they are inherently signed or |
e913b5cd | 432 | * unsigned and C++ has no such operators. |
433 | */ | |
434 | ||
435 | /* Return true if OP0 == OP1. */ | |
436 | bool | |
796b6678 | 437 | wi::eq_p_large (const HOST_WIDE_INT *op0, unsigned int op0len, |
438 | const HOST_WIDE_INT *op1, unsigned int op1len, | |
439 | unsigned int prec) | |
e913b5cd | 440 | { |
441 | int l0 = op0len - 1; | |
442 | unsigned int small_prec = prec & (HOST_BITS_PER_WIDE_INT - 1); | |
443 | ||
e4712d1e | 444 | if (op0len != op1len) |
e913b5cd | 445 | return false; |
446 | ||
447 | if (op0len == BLOCKS_NEEDED (prec) && small_prec) | |
448 | { | |
449 | /* It does not matter if we zext or sext here, we just have to | |
450 | do both the same way. */ | |
451 | if (zext_hwi (op0 [l0], small_prec) != zext_hwi (op1 [l0], small_prec)) | |
452 | return false; | |
453 | l0--; | |
454 | } | |
455 | ||
456 | while (l0 >= 0) | |
457 | if (op0[l0] != op1[l0]) | |
458 | return false; | |
459 | else | |
460 | l0--; | |
461 | ||
462 | return true; | |
463 | } | |
464 | ||
465 | /* Return true if OP0 < OP1 using signed comparisons. */ | |
466 | bool | |
796b6678 | 467 | wi::lts_p_large (const HOST_WIDE_INT *op0, unsigned int op0len, |
cd9b5516 | 468 | unsigned int precision, |
469 | const HOST_WIDE_INT *op1, unsigned int op1len) | |
e913b5cd | 470 | { |
471 | HOST_WIDE_INT s0, s1; | |
472 | unsigned HOST_WIDE_INT u0, u1; | |
cd9b5516 | 473 | unsigned int blocks_needed = BLOCKS_NEEDED (precision); |
474 | unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1); | |
e913b5cd | 475 | int l = MAX (op0len - 1, op1len - 1); |
476 | ||
477 | /* Only the top block is compared as signed. The rest are unsigned | |
478 | comparisons. */ | |
cd9b5516 | 479 | s0 = selt (op0, op0len, blocks_needed, small_prec, l, SIGNED); |
480 | s1 = selt (op1, op1len, blocks_needed, small_prec, l, SIGNED); | |
e913b5cd | 481 | if (s0 < s1) |
482 | return true; | |
483 | if (s0 > s1) | |
484 | return false; | |
485 | ||
486 | l--; | |
487 | while (l >= 0) | |
488 | { | |
cd9b5516 | 489 | u0 = selt (op0, op0len, blocks_needed, small_prec, l, SIGNED); |
490 | u1 = selt (op1, op1len, blocks_needed, small_prec, l, SIGNED); | |
e913b5cd | 491 | |
492 | if (u0 < u1) | |
493 | return true; | |
494 | if (u0 > u1) | |
495 | return false; | |
496 | l--; | |
497 | } | |
498 | ||
499 | return false; | |
500 | } | |
501 | ||
502 | /* Returns -1 if OP0 < OP1, 0 if OP0 == OP1 and 1 if OP0 > OP1 using | |
503 | signed compares. */ | |
504 | int | |
796b6678 | 505 | wi::cmps_large (const HOST_WIDE_INT *op0, unsigned int op0len, |
cd9b5516 | 506 | unsigned int precision, |
507 | const HOST_WIDE_INT *op1, unsigned int op1len) | |
e913b5cd | 508 | { |
509 | HOST_WIDE_INT s0, s1; | |
510 | unsigned HOST_WIDE_INT u0, u1; | |
cd9b5516 | 511 | unsigned int blocks_needed = BLOCKS_NEEDED (precision); |
512 | unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1); | |
e913b5cd | 513 | int l = MAX (op0len - 1, op1len - 1); |
514 | ||
515 | /* Only the top block is compared as signed. The rest are unsigned | |
516 | comparisons. */ | |
cd9b5516 | 517 | s0 = selt (op0, op0len, blocks_needed, small_prec, l, SIGNED); |
518 | s1 = selt (op1, op1len, blocks_needed, small_prec, l, SIGNED); | |
e913b5cd | 519 | if (s0 < s1) |
520 | return -1; | |
521 | if (s0 > s1) | |
522 | return 1; | |
523 | ||
524 | l--; | |
525 | while (l >= 0) | |
526 | { | |
cd9b5516 | 527 | u0 = selt (op0, op0len, blocks_needed, small_prec, l, SIGNED); |
528 | u1 = selt (op1, op1len, blocks_needed, small_prec, l, SIGNED); | |
e913b5cd | 529 | |
530 | if (u0 < u1) | |
531 | return -1; | |
532 | if (u0 > u1) | |
533 | return 1; | |
534 | l--; | |
535 | } | |
536 | ||
537 | return 0; | |
538 | } | |
539 | ||
540 | /* Return true if OP0 < OP1 using unsigned comparisons. */ | |
541 | bool | |
cd9b5516 | 542 | wi::ltu_p_large (const HOST_WIDE_INT *op0, unsigned int op0len, |
543 | unsigned int precision, | |
544 | const HOST_WIDE_INT *op1, unsigned int op1len) | |
e913b5cd | 545 | { |
546 | unsigned HOST_WIDE_INT x0; | |
547 | unsigned HOST_WIDE_INT x1; | |
cd9b5516 | 548 | unsigned int blocks_needed = BLOCKS_NEEDED (precision); |
549 | unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1); | |
e913b5cd | 550 | int l = MAX (op0len - 1, op1len - 1); |
551 | ||
552 | while (l >= 0) | |
553 | { | |
cd9b5516 | 554 | x0 = selt (op0, op0len, blocks_needed, small_prec, l, UNSIGNED); |
555 | x1 = selt (op1, op1len, blocks_needed, small_prec, l, UNSIGNED); | |
e913b5cd | 556 | if (x0 < x1) |
557 | return true; | |
558 | if (x0 > x1) | |
559 | return false; | |
560 | l--; | |
561 | } | |
562 | ||
563 | return false; | |
564 | } | |
565 | ||
566 | /* Returns -1 if OP0 < OP1, 0 if OP0 == OP1 and 1 if OP0 > OP1 using | |
567 | unsigned compares. */ | |
568 | int | |
cd9b5516 | 569 | wi::cmpu_large (const HOST_WIDE_INT *op0, unsigned int op0len, |
570 | unsigned int precision, | |
571 | const HOST_WIDE_INT *op1, unsigned int op1len) | |
e913b5cd | 572 | { |
573 | unsigned HOST_WIDE_INT x0; | |
574 | unsigned HOST_WIDE_INT x1; | |
cd9b5516 | 575 | unsigned int blocks_needed = BLOCKS_NEEDED (precision); |
576 | unsigned int small_prec = precision & (HOST_BITS_PER_WIDE_INT - 1); | |
e913b5cd | 577 | int l = MAX (op0len - 1, op1len - 1); |
578 | ||
579 | while (l >= 0) | |
580 | { | |
cd9b5516 | 581 | x0 = selt (op0, op0len, blocks_needed, small_prec, l, UNSIGNED); |
582 | x1 = selt (op1, op1len, blocks_needed, small_prec, l, UNSIGNED); | |
e913b5cd | 583 | if (x0 < x1) |
584 | return -1; | |
585 | if (x0 > x1) | |
586 | return 1; | |
587 | l--; | |
588 | } | |
589 | ||
590 | return 0; | |
591 | } | |
592 | ||
e913b5cd | 593 | /* |
594 | * Extension. | |
595 | */ | |
596 | ||
796b6678 | 597 | /* Sign-extend the number represented by XVAL and XLEN into VAL, |
598 | starting at OFFSET. Return the number of blocks in VAL. Both XVAL | |
599 | and VAL have PRECISION bits. */ | |
600 | unsigned int | |
601 | wi::sext_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval, | |
602 | unsigned int xlen, unsigned int precision, unsigned int offset) | |
603 | { | |
604 | unsigned int len = offset / HOST_BITS_PER_WIDE_INT; | |
605 | /* Extending beyond the precision is a no-op. If we have only stored | |
606 | OFFSET bits or fewer, the rest are already signs. */ | |
607 | if (offset >= precision || len >= xlen) | |
608 | { | |
609 | for (unsigned i = 0; i < xlen; ++i) | |
610 | val[i] = xval[i]; | |
611 | return xlen; | |
612 | } | |
613 | unsigned int suboffset = offset % HOST_BITS_PER_WIDE_INT; | |
614 | for (unsigned int i = 0; i < len; i++) | |
615 | val[i] = xval[i]; | |
616 | if (suboffset > 0) | |
617 | { | |
618 | val[len] = sext_hwi (xval[len], suboffset); | |
619 | len += 1; | |
620 | } | |
621 | return canonize (val, len, precision); | |
622 | } | |
623 | ||
624 | /* Zero-extend the number represented by XVAL and XLEN into VAL, | |
625 | starting at OFFSET. Return the number of blocks in VAL. Both XVAL | |
626 | and VAL have PRECISION bits. */ | |
627 | unsigned int | |
628 | wi::zext_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval, | |
629 | unsigned int xlen, unsigned int precision, unsigned int offset) | |
630 | { | |
631 | unsigned int len = offset / HOST_BITS_PER_WIDE_INT; | |
632 | /* Extending beyond the precision is a no-op. If we have only stored | |
633 | OFFSET bits or fewer, and the upper stored bit is zero, then there | |
634 | is nothing to do. */ | |
635 | if (offset >= precision || (len >= xlen && xval[xlen - 1] >= 0)) | |
636 | { | |
637 | for (unsigned i = 0; i < xlen; ++i) | |
638 | val[i] = xval[i]; | |
639 | return xlen; | |
640 | } | |
641 | unsigned int suboffset = offset % HOST_BITS_PER_WIDE_INT; | |
642 | for (unsigned int i = 0; i < len; i++) | |
643 | val[i] = i < xlen ? xval[i] : -1; | |
644 | if (suboffset > 0) | |
645 | val[len] = zext_hwi (len < xlen ? xval[len] : -1, suboffset); | |
e913b5cd | 646 | else |
796b6678 | 647 | val[len] = 0; |
648 | return canonize (val, len + 1, precision); | |
e913b5cd | 649 | } |
650 | ||
651 | /* | |
652 | * Masking, inserting, shifting, rotating. | |
653 | */ | |
654 | ||
796b6678 | 655 | /* Insert WIDTH bits from Y into X starting at START. */ |
656 | wide_int | |
657 | wi::insert (const wide_int &x, const wide_int &y, unsigned int start, | |
658 | unsigned int width) | |
e913b5cd | 659 | { |
660 | wide_int result; | |
661 | wide_int mask; | |
662 | wide_int tmp; | |
663 | ||
796b6678 | 664 | unsigned int precision = x.get_precision (); |
e913b5cd | 665 | if (start >= precision) |
796b6678 | 666 | return x; |
e913b5cd | 667 | |
796b6678 | 668 | gcc_checking_assert (precision >= width); |
e913b5cd | 669 | |
670 | if (start + width >= precision) | |
671 | width = precision - start; | |
672 | ||
796b6678 | 673 | mask = wi::shifted_mask (start, width, false, precision); |
674 | tmp = wi::lshift (wide_int::from (y, precision, UNSIGNED), start); | |
e913b5cd | 675 | result = tmp & mask; |
676 | ||
796b6678 | 677 | tmp = wi::bit_and_not (x, mask); |
e913b5cd | 678 | result = result | tmp; |
679 | ||
e913b5cd | 680 | return result; |
681 | } | |
682 | ||
796b6678 | 683 | /* Copy the number represented by XVAL and XLEN into VAL, setting bit BIT. |
684 | Return the number of blocks in VAL. Both XVAL and VAL have PRECISION | |
685 | bits. */ | |
686 | unsigned int | |
687 | wi::set_bit_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval, | |
688 | unsigned int xlen, unsigned int precision, unsigned int bit) | |
689 | { | |
690 | unsigned int block = bit / HOST_BITS_PER_WIDE_INT; | |
691 | unsigned int subbit = bit % HOST_BITS_PER_WIDE_INT; | |
692 | ||
693 | if (block + 1 >= xlen) | |
694 | { | |
695 | /* The operation either affects the last current block or needs | |
696 | a new block. */ | |
697 | unsigned int len = block + 1; | |
698 | for (unsigned int i = 0; i < len; i++) | |
699 | val[i] = safe_uhwi (xval, xlen, i); | |
edc19fd0 | 700 | val[block] |= HOST_WIDE_INT_1U << subbit; |
796b6678 | 701 | |
702 | /* If the bit we just set is at the msb of the block, make sure | |
703 | that any higher bits are zeros. */ | |
05363b4a | 704 | if (bit + 1 < precision && subbit == HOST_BITS_PER_WIDE_INT - 1) |
796b6678 | 705 | val[len++] = 0; |
706 | return len; | |
707 | } | |
708 | else | |
709 | { | |
710 | for (unsigned int i = 0; i < xlen; i++) | |
711 | val[i] = xval[i]; | |
edc19fd0 | 712 | val[block] |= HOST_WIDE_INT_1U << subbit; |
796b6678 | 713 | return canonize (val, xlen, precision); |
714 | } | |
715 | } | |
716 | ||
e913b5cd | 717 | /* bswap THIS. */ |
796b6678 | 718 | wide_int |
719 | wide_int_storage::bswap () const | |
e913b5cd | 720 | { |
796b6678 | 721 | wide_int result = wide_int::create (precision); |
722 | unsigned int i, s; | |
723 | unsigned int len = BLOCKS_NEEDED (precision); | |
724 | unsigned int xlen = get_len (); | |
725 | const HOST_WIDE_INT *xval = get_val (); | |
726 | HOST_WIDE_INT *val = result.write_val (); | |
e913b5cd | 727 | |
728 | /* This is not a well defined operation if the precision is not a | |
729 | multiple of 8. */ | |
730 | gcc_assert ((precision & 0x7) == 0); | |
731 | ||
e913b5cd | 732 | for (i = 0; i < len; i++) |
796b6678 | 733 | val[i] = 0; |
e913b5cd | 734 | |
735 | /* Only swap the bytes that are not the padding. */ | |
796b6678 | 736 | for (s = 0; s < precision; s += 8) |
e913b5cd | 737 | { |
738 | unsigned int d = precision - s - 8; | |
739 | unsigned HOST_WIDE_INT byte; | |
740 | ||
796b6678 | 741 | unsigned int block = s / HOST_BITS_PER_WIDE_INT; |
742 | unsigned int offset = s & (HOST_BITS_PER_WIDE_INT - 1); | |
e913b5cd | 743 | |
796b6678 | 744 | byte = (safe_uhwi (xval, xlen, block) >> offset) & 0xff; |
e913b5cd | 745 | |
746 | block = d / HOST_BITS_PER_WIDE_INT; | |
747 | offset = d & (HOST_BITS_PER_WIDE_INT - 1); | |
748 | ||
796b6678 | 749 | val[block] |= byte << offset; |
e913b5cd | 750 | } |
751 | ||
796b6678 | 752 | result.set_len (canonize (val, len, precision)); |
e913b5cd | 753 | return result; |
754 | } | |
755 | ||
796b6678 | 756 | /* Fill VAL with a mask where the lower WIDTH bits are ones and the bits |
757 | above that up to PREC are zeros. The result is inverted if NEGATE | |
758 | is true. Return the number of blocks in VAL. */ | |
759 | unsigned int | |
760 | wi::mask (HOST_WIDE_INT *val, unsigned int width, bool negate, | |
761 | unsigned int prec) | |
e913b5cd | 762 | { |
9592fe41 | 763 | if (width >= prec) |
e913b5cd | 764 | { |
796b6678 | 765 | val[0] = negate ? 0 : -1; |
766 | return 1; | |
e913b5cd | 767 | } |
768 | else if (width == 0) | |
769 | { | |
796b6678 | 770 | val[0] = negate ? -1 : 0; |
771 | return 1; | |
e913b5cd | 772 | } |
e913b5cd | 773 | |
796b6678 | 774 | unsigned int i = 0; |
775 | while (i < width / HOST_BITS_PER_WIDE_INT) | |
776 | val[i++] = negate ? 0 : -1; | |
e913b5cd | 777 | |
796b6678 | 778 | unsigned int shift = width & (HOST_BITS_PER_WIDE_INT - 1); |
779 | if (shift != 0) | |
780 | { | |
edc19fd0 | 781 | HOST_WIDE_INT last = (HOST_WIDE_INT_1U << shift) - 1; |
796b6678 | 782 | val[i++] = negate ? ~last : last; |
e913b5cd | 783 | } |
796b6678 | 784 | else |
785 | val[i++] = negate ? -1 : 0; | |
e913b5cd | 786 | |
796b6678 | 787 | return i; |
e913b5cd | 788 | } |
789 | ||
796b6678 | 790 | /* Fill VAL with a mask where the lower START bits are zeros, the next WIDTH |
791 | bits are ones, and the bits above that up to PREC are zeros. The result | |
792 | is inverted if NEGATE is true. Return the number of blocks in VAL. */ | |
793 | unsigned int | |
794 | wi::shifted_mask (HOST_WIDE_INT *val, unsigned int start, unsigned int width, | |
795 | bool negate, unsigned int prec) | |
e913b5cd | 796 | { |
2cd0cb08 | 797 | if (start >= prec || width == 0) |
e913b5cd | 798 | { |
796b6678 | 799 | val[0] = negate ? -1 : 0; |
800 | return 1; | |
e913b5cd | 801 | } |
802 | ||
2cd0cb08 | 803 | if (width > prec - start) |
804 | width = prec - start; | |
805 | unsigned int end = start + width; | |
806 | ||
796b6678 | 807 | unsigned int i = 0; |
e913b5cd | 808 | while (i < start / HOST_BITS_PER_WIDE_INT) |
796b6678 | 809 | val[i++] = negate ? -1 : 0; |
e913b5cd | 810 | |
796b6678 | 811 | unsigned int shift = start & (HOST_BITS_PER_WIDE_INT - 1); |
e913b5cd | 812 | if (shift) |
813 | { | |
edc19fd0 | 814 | HOST_WIDE_INT block = (HOST_WIDE_INT_1U << shift) - 1; |
b309c394 | 815 | shift += width; |
816 | if (shift < HOST_BITS_PER_WIDE_INT) | |
e913b5cd | 817 | { |
818 | /* case 000111000 */ | |
edc19fd0 | 819 | block = (HOST_WIDE_INT_1U << shift) - block - 1; |
796b6678 | 820 | val[i++] = negate ? ~block : block; |
821 | return i; | |
e913b5cd | 822 | } |
823 | else | |
824 | /* ...111000 */ | |
796b6678 | 825 | val[i++] = negate ? block : ~block; |
e913b5cd | 826 | } |
827 | ||
828 | while (i < end / HOST_BITS_PER_WIDE_INT) | |
829 | /* 1111111 */ | |
796b6678 | 830 | val[i++] = negate ? 0 : -1; |
e913b5cd | 831 | |
832 | shift = end & (HOST_BITS_PER_WIDE_INT - 1); | |
833 | if (shift != 0) | |
834 | { | |
835 | /* 000011111 */ | |
edc19fd0 | 836 | HOST_WIDE_INT block = (HOST_WIDE_INT_1U << shift) - 1; |
796b6678 | 837 | val[i++] = negate ? ~block : block; |
e913b5cd | 838 | } |
839 | else if (end < prec) | |
796b6678 | 840 | val[i++] = negate ? -1 : 0; |
e913b5cd | 841 | |
796b6678 | 842 | return i; |
e913b5cd | 843 | } |
844 | ||
e913b5cd | 845 | /* |
846 | * logical operations. | |
847 | */ | |
848 | ||
796b6678 | 849 | /* Set VAL to OP0 & OP1. Return the number of blocks used. */ |
850 | unsigned int | |
851 | wi::and_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0, | |
852 | unsigned int op0len, const HOST_WIDE_INT *op1, | |
853 | unsigned int op1len, unsigned int prec) | |
e913b5cd | 854 | { |
e913b5cd | 855 | int l0 = op0len - 1; |
856 | int l1 = op1len - 1; | |
857 | bool need_canon = true; | |
858 | ||
796b6678 | 859 | unsigned int len = MAX (op0len, op1len); |
e913b5cd | 860 | if (l0 > l1) |
861 | { | |
5b2cae25 | 862 | HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec); |
e4712d1e | 863 | if (op1mask == 0) |
e913b5cd | 864 | { |
865 | l0 = l1; | |
796b6678 | 866 | len = l1 + 1; |
e913b5cd | 867 | } |
868 | else | |
869 | { | |
870 | need_canon = false; | |
871 | while (l0 > l1) | |
872 | { | |
796b6678 | 873 | val[l0] = op0[l0]; |
e913b5cd | 874 | l0--; |
875 | } | |
876 | } | |
877 | } | |
878 | else if (l1 > l0) | |
879 | { | |
5b2cae25 | 880 | HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec); |
e913b5cd | 881 | if (op0mask == 0) |
796b6678 | 882 | len = l0 + 1; |
e913b5cd | 883 | else |
884 | { | |
885 | need_canon = false; | |
886 | while (l1 > l0) | |
887 | { | |
796b6678 | 888 | val[l1] = op1[l1]; |
e913b5cd | 889 | l1--; |
890 | } | |
891 | } | |
892 | } | |
893 | ||
894 | while (l0 >= 0) | |
895 | { | |
796b6678 | 896 | val[l0] = op0[l0] & op1[l0]; |
e913b5cd | 897 | l0--; |
898 | } | |
899 | ||
900 | if (need_canon) | |
796b6678 | 901 | len = canonize (val, len, prec); |
e913b5cd | 902 | |
796b6678 | 903 | return len; |
e913b5cd | 904 | } |
905 | ||
796b6678 | 906 | /* Set VAL to OP0 & ~OP1. Return the number of blocks used. */ |
907 | unsigned int | |
908 | wi::and_not_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0, | |
909 | unsigned int op0len, const HOST_WIDE_INT *op1, | |
910 | unsigned int op1len, unsigned int prec) | |
e913b5cd | 911 | { |
912 | wide_int result; | |
913 | int l0 = op0len - 1; | |
914 | int l1 = op1len - 1; | |
915 | bool need_canon = true; | |
916 | ||
796b6678 | 917 | unsigned int len = MAX (op0len, op1len); |
e913b5cd | 918 | if (l0 > l1) |
919 | { | |
5b2cae25 | 920 | HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec); |
e913b5cd | 921 | if (op1mask != 0) |
922 | { | |
923 | l0 = l1; | |
796b6678 | 924 | len = l1 + 1; |
e913b5cd | 925 | } |
926 | else | |
927 | { | |
928 | need_canon = false; | |
929 | while (l0 > l1) | |
930 | { | |
796b6678 | 931 | val[l0] = op0[l0]; |
e913b5cd | 932 | l0--; |
933 | } | |
934 | } | |
935 | } | |
936 | else if (l1 > l0) | |
937 | { | |
5b2cae25 | 938 | HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec); |
e913b5cd | 939 | if (op0mask == 0) |
796b6678 | 940 | len = l0 + 1; |
e913b5cd | 941 | else |
942 | { | |
943 | need_canon = false; | |
944 | while (l1 > l0) | |
945 | { | |
796b6678 | 946 | val[l1] = ~op1[l1]; |
e913b5cd | 947 | l1--; |
948 | } | |
949 | } | |
950 | } | |
951 | ||
952 | while (l0 >= 0) | |
953 | { | |
796b6678 | 954 | val[l0] = op0[l0] & ~op1[l0]; |
e913b5cd | 955 | l0--; |
956 | } | |
957 | ||
958 | if (need_canon) | |
796b6678 | 959 | len = canonize (val, len, prec); |
e913b5cd | 960 | |
796b6678 | 961 | return len; |
e913b5cd | 962 | } |
963 | ||
796b6678 | 964 | /* Set VAL to OP0 | OP1. Return the number of blocks used. */ |
965 | unsigned int | |
966 | wi::or_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0, | |
967 | unsigned int op0len, const HOST_WIDE_INT *op1, | |
968 | unsigned int op1len, unsigned int prec) | |
e913b5cd | 969 | { |
970 | wide_int result; | |
971 | int l0 = op0len - 1; | |
972 | int l1 = op1len - 1; | |
973 | bool need_canon = true; | |
974 | ||
796b6678 | 975 | unsigned int len = MAX (op0len, op1len); |
e913b5cd | 976 | if (l0 > l1) |
977 | { | |
5b2cae25 | 978 | HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec); |
e913b5cd | 979 | if (op1mask != 0) |
980 | { | |
981 | l0 = l1; | |
796b6678 | 982 | len = l1 + 1; |
e913b5cd | 983 | } |
984 | else | |
985 | { | |
986 | need_canon = false; | |
987 | while (l0 > l1) | |
988 | { | |
796b6678 | 989 | val[l0] = op0[l0]; |
e913b5cd | 990 | l0--; |
991 | } | |
992 | } | |
993 | } | |
994 | else if (l1 > l0) | |
995 | { | |
5b2cae25 | 996 | HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec); |
e913b5cd | 997 | if (op0mask != 0) |
796b6678 | 998 | len = l0 + 1; |
e913b5cd | 999 | else |
1000 | { | |
1001 | need_canon = false; | |
1002 | while (l1 > l0) | |
1003 | { | |
796b6678 | 1004 | val[l1] = op1[l1]; |
e913b5cd | 1005 | l1--; |
1006 | } | |
1007 | } | |
1008 | } | |
1009 | ||
1010 | while (l0 >= 0) | |
1011 | { | |
796b6678 | 1012 | val[l0] = op0[l0] | op1[l0]; |
e913b5cd | 1013 | l0--; |
1014 | } | |
1015 | ||
1016 | if (need_canon) | |
796b6678 | 1017 | len = canonize (val, len, prec); |
e913b5cd | 1018 | |
796b6678 | 1019 | return len; |
e913b5cd | 1020 | } |
1021 | ||
796b6678 | 1022 | /* Set VAL to OP0 | ~OP1. Return the number of blocks used. */ |
1023 | unsigned int | |
1024 | wi::or_not_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0, | |
1025 | unsigned int op0len, const HOST_WIDE_INT *op1, | |
1026 | unsigned int op1len, unsigned int prec) | |
e913b5cd | 1027 | { |
1028 | wide_int result; | |
1029 | int l0 = op0len - 1; | |
1030 | int l1 = op1len - 1; | |
1031 | bool need_canon = true; | |
1032 | ||
796b6678 | 1033 | unsigned int len = MAX (op0len, op1len); |
e913b5cd | 1034 | if (l0 > l1) |
1035 | { | |
5b2cae25 | 1036 | HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec); |
e913b5cd | 1037 | if (op1mask == 0) |
1038 | { | |
1039 | l0 = l1; | |
796b6678 | 1040 | len = l1 + 1; |
e913b5cd | 1041 | } |
1042 | else | |
1043 | { | |
1044 | need_canon = false; | |
1045 | while (l0 > l1) | |
1046 | { | |
796b6678 | 1047 | val[l0] = op0[l0]; |
e913b5cd | 1048 | l0--; |
1049 | } | |
1050 | } | |
1051 | } | |
1052 | else if (l1 > l0) | |
1053 | { | |
5b2cae25 | 1054 | HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec); |
e913b5cd | 1055 | if (op0mask != 0) |
796b6678 | 1056 | len = l0 + 1; |
e913b5cd | 1057 | else |
1058 | { | |
1059 | need_canon = false; | |
1060 | while (l1 > l0) | |
1061 | { | |
796b6678 | 1062 | val[l1] = ~op1[l1]; |
e913b5cd | 1063 | l1--; |
1064 | } | |
1065 | } | |
1066 | } | |
1067 | ||
1068 | while (l0 >= 0) | |
1069 | { | |
796b6678 | 1070 | val[l0] = op0[l0] | ~op1[l0]; |
e913b5cd | 1071 | l0--; |
1072 | } | |
1073 | ||
1074 | if (need_canon) | |
796b6678 | 1075 | len = canonize (val, len, prec); |
e913b5cd | 1076 | |
796b6678 | 1077 | return len; |
e913b5cd | 1078 | } |
1079 | ||
796b6678 | 1080 | /* Set VAL to OP0 ^ OP1. Return the number of blocks used. */ |
1081 | unsigned int | |
1082 | wi::xor_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0, | |
1083 | unsigned int op0len, const HOST_WIDE_INT *op1, | |
1084 | unsigned int op1len, unsigned int prec) | |
e913b5cd | 1085 | { |
1086 | wide_int result; | |
1087 | int l0 = op0len - 1; | |
1088 | int l1 = op1len - 1; | |
1089 | ||
796b6678 | 1090 | unsigned int len = MAX (op0len, op1len); |
e913b5cd | 1091 | if (l0 > l1) |
1092 | { | |
5b2cae25 | 1093 | HOST_WIDE_INT op1mask = -top_bit_of (op1, op1len, prec); |
e913b5cd | 1094 | while (l0 > l1) |
1095 | { | |
796b6678 | 1096 | val[l0] = op0[l0] ^ op1mask; |
e913b5cd | 1097 | l0--; |
1098 | } | |
1099 | } | |
1100 | ||
1101 | if (l1 > l0) | |
1102 | { | |
5b2cae25 | 1103 | HOST_WIDE_INT op0mask = -top_bit_of (op0, op0len, prec); |
e913b5cd | 1104 | while (l1 > l0) |
1105 | { | |
796b6678 | 1106 | val[l1] = op0mask ^ op1[l1]; |
e913b5cd | 1107 | l1--; |
1108 | } | |
1109 | } | |
1110 | ||
1111 | while (l0 >= 0) | |
1112 | { | |
796b6678 | 1113 | val[l0] = op0[l0] ^ op1[l0]; |
e913b5cd | 1114 | l0--; |
1115 | } | |
1116 | ||
796b6678 | 1117 | return canonize (val, len, prec); |
e913b5cd | 1118 | } |
1119 | ||
1120 | /* | |
1121 | * math | |
1122 | */ | |
1123 | ||
796b6678 | 1124 | /* Set VAL to OP0 + OP1. If OVERFLOW is nonnull, record in *OVERFLOW |
1125 | whether the result overflows when OP0 and OP1 are treated as having | |
1126 | signedness SGN. Return the number of blocks in VAL. */ | |
1127 | unsigned int | |
1128 | wi::add_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0, | |
1129 | unsigned int op0len, const HOST_WIDE_INT *op1, | |
1130 | unsigned int op1len, unsigned int prec, | |
1131 | signop sgn, bool *overflow) | |
e913b5cd | 1132 | { |
e913b5cd | 1133 | unsigned HOST_WIDE_INT o0 = 0; |
1134 | unsigned HOST_WIDE_INT o1 = 0; | |
1135 | unsigned HOST_WIDE_INT x = 0; | |
1136 | unsigned HOST_WIDE_INT carry = 0; | |
1137 | unsigned HOST_WIDE_INT old_carry = 0; | |
1138 | unsigned HOST_WIDE_INT mask0, mask1; | |
5b2cae25 | 1139 | unsigned int i; |
e913b5cd | 1140 | |
796b6678 | 1141 | unsigned int len = MAX (op0len, op1len); |
5b2cae25 | 1142 | mask0 = -top_bit_of (op0, op0len, prec); |
1143 | mask1 = -top_bit_of (op1, op1len, prec); | |
e913b5cd | 1144 | /* Add all of the explicitly defined elements. */ |
1145 | ||
796b6678 | 1146 | for (i = 0; i < len; i++) |
e913b5cd | 1147 | { |
5b2cae25 | 1148 | o0 = i < op0len ? (unsigned HOST_WIDE_INT) op0[i] : mask0; |
1149 | o1 = i < op1len ? (unsigned HOST_WIDE_INT) op1[i] : mask1; | |
e913b5cd | 1150 | x = o0 + o1 + carry; |
796b6678 | 1151 | val[i] = x; |
e913b5cd | 1152 | old_carry = carry; |
1153 | carry = carry == 0 ? x < o0 : x <= o0; | |
1154 | } | |
1155 | ||
796b6678 | 1156 | if (len * HOST_BITS_PER_WIDE_INT < prec) |
e913b5cd | 1157 | { |
796b6678 | 1158 | val[len] = mask0 + mask1 + carry; |
1159 | len++; | |
e913b5cd | 1160 | if (overflow) |
1161 | *overflow = false; | |
1162 | } | |
1163 | else if (overflow) | |
1164 | { | |
5b2cae25 | 1165 | unsigned int shift = -prec % HOST_BITS_PER_WIDE_INT; |
e913b5cd | 1166 | if (sgn == SIGNED) |
1167 | { | |
5b2cae25 | 1168 | unsigned HOST_WIDE_INT x = (val[len - 1] ^ o0) & (val[len - 1] ^ o1); |
3b247a20 | 1169 | *overflow = (HOST_WIDE_INT) (x << shift) < 0; |
e913b5cd | 1170 | } |
1171 | else | |
1172 | { | |
5b2cae25 | 1173 | /* Put the MSB of X and O0 and in the top of the HWI. */ |
1174 | x <<= shift; | |
1175 | o0 <<= shift; | |
e913b5cd | 1176 | if (old_carry) |
5b2cae25 | 1177 | *overflow = (x <= o0); |
e913b5cd | 1178 | else |
5b2cae25 | 1179 | *overflow = (x < o0); |
e913b5cd | 1180 | } |
1181 | } | |
1182 | ||
796b6678 | 1183 | return canonize (val, len, prec); |
e913b5cd | 1184 | } |
1185 | ||
e913b5cd | 1186 | /* Subroutines of the multiplication and division operations. Unpack |
1187 | the first IN_LEN HOST_WIDE_INTs in INPUT into 2 * IN_LEN | |
1188 | HOST_HALF_WIDE_INTs of RESULT. The rest of RESULT is filled by | |
1189 | uncompressing the top bit of INPUT[IN_LEN - 1]. */ | |
1190 | static void | |
74eae799 | 1191 | wi_unpack (unsigned HOST_HALF_WIDE_INT *result, const HOST_WIDE_INT *input, |
796b6678 | 1192 | unsigned int in_len, unsigned int out_len, |
1193 | unsigned int prec, signop sgn) | |
e913b5cd | 1194 | { |
796b6678 | 1195 | unsigned int i; |
1196 | unsigned int j = 0; | |
1197 | unsigned int small_prec = prec & (HOST_BITS_PER_WIDE_INT - 1); | |
1198 | unsigned int blocks_needed = BLOCKS_NEEDED (prec); | |
e913b5cd | 1199 | HOST_WIDE_INT mask; |
1200 | ||
1201 | if (sgn == SIGNED) | |
1202 | { | |
5b2cae25 | 1203 | mask = -top_bit_of ((const HOST_WIDE_INT *) input, in_len, prec); |
e913b5cd | 1204 | mask &= HALF_INT_MASK; |
1205 | } | |
1206 | else | |
1207 | mask = 0; | |
1208 | ||
74eae799 | 1209 | for (i = 0; i < blocks_needed - 1; i++) |
e913b5cd | 1210 | { |
74eae799 | 1211 | HOST_WIDE_INT x = safe_uhwi (input, in_len, i); |
e913b5cd | 1212 | result[j++] = x; |
1213 | result[j++] = x >> HOST_BITS_PER_HALF_WIDE_INT; | |
1214 | } | |
1215 | ||
74eae799 | 1216 | HOST_WIDE_INT x = safe_uhwi (input, in_len, i); |
1217 | if (small_prec) | |
1218 | { | |
1219 | if (sgn == SIGNED) | |
1220 | x = sext_hwi (x, small_prec); | |
1221 | else | |
1222 | x = zext_hwi (x, small_prec); | |
1223 | } | |
1224 | result[j++] = x; | |
1225 | result[j++] = x >> HOST_BITS_PER_HALF_WIDE_INT; | |
1226 | ||
e913b5cd | 1227 | /* Smear the sign bit. */ |
1228 | while (j < out_len) | |
1229 | result[j++] = mask; | |
1230 | } | |
1231 | ||
ef7be7f8 | 1232 | /* The inverse of wi_unpack. IN_LEN is the number of input |
1233 | blocks and PRECISION is the precision of the result. Return the | |
1234 | number of blocks in the canonicalized result. */ | |
1235 | static unsigned int | |
1236 | wi_pack (HOST_WIDE_INT *result, | |
e913b5cd | 1237 | const unsigned HOST_HALF_WIDE_INT *input, |
ef7be7f8 | 1238 | unsigned int in_len, unsigned int precision) |
e913b5cd | 1239 | { |
796b6678 | 1240 | unsigned int i = 0; |
1241 | unsigned int j = 0; | |
ef7be7f8 | 1242 | unsigned int blocks_needed = BLOCKS_NEEDED (precision); |
e913b5cd | 1243 | |
ef7be7f8 | 1244 | while (i + 1 < in_len) |
e913b5cd | 1245 | { |
ef7be7f8 | 1246 | result[j++] = ((unsigned HOST_WIDE_INT) input[i] |
1247 | | ((unsigned HOST_WIDE_INT) input[i + 1] | |
1248 | << HOST_BITS_PER_HALF_WIDE_INT)); | |
796b6678 | 1249 | i += 2; |
e913b5cd | 1250 | } |
e913b5cd | 1251 | |
796b6678 | 1252 | /* Handle the case where in_len is odd. For this we zero extend. */ |
1253 | if (in_len & 1) | |
ef7be7f8 | 1254 | result[j++] = (unsigned HOST_WIDE_INT) input[i]; |
1255 | else if (j < blocks_needed) | |
1256 | result[j++] = 0; | |
1257 | return canonize (result, j, precision); | |
e913b5cd | 1258 | } |
1259 | ||
1260 | /* Multiply Op1 by Op2. If HIGH is set, only the upper half of the | |
77d15f37 | 1261 | result is returned. |
1262 | ||
1263 | If HIGH is not set, throw away the upper half after the check is | |
1264 | made to see if it overflows. Unfortunately there is no better way | |
1265 | to check for overflow than to do this. If OVERFLOW is nonnull, | |
1266 | record in *OVERFLOW whether the result overflowed. SGN controls | |
1267 | the signedness and is used to check overflow or if HIGH is set. */ | |
796b6678 | 1268 | unsigned int |
25b6c9eb | 1269 | wi::mul_internal (HOST_WIDE_INT *val, const HOST_WIDE_INT *op1val, |
1270 | unsigned int op1len, const HOST_WIDE_INT *op2val, | |
796b6678 | 1271 | unsigned int op2len, unsigned int prec, signop sgn, |
77d15f37 | 1272 | bool *overflow, bool high) |
e913b5cd | 1273 | { |
e913b5cd | 1274 | unsigned HOST_WIDE_INT o0, o1, k, t; |
1275 | unsigned int i; | |
1276 | unsigned int j; | |
1277 | unsigned int blocks_needed = BLOCKS_NEEDED (prec); | |
1278 | unsigned int half_blocks_needed = blocks_needed * 2; | |
1279 | /* The sizes here are scaled to support a 2x largest mode by 2x | |
1280 | largest mode yielding a 4x largest mode result. This is what is | |
1281 | needed by vpn. */ | |
1282 | ||
1283 | unsigned HOST_HALF_WIDE_INT | |
242947db | 1284 | u[4 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_HALF_WIDE_INT]; |
e913b5cd | 1285 | unsigned HOST_HALF_WIDE_INT |
242947db | 1286 | v[4 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_HALF_WIDE_INT]; |
e913b5cd | 1287 | /* The '2' in 'R' is because we are internally doing a full |
1288 | multiply. */ | |
1289 | unsigned HOST_HALF_WIDE_INT | |
242947db | 1290 | r[2 * 4 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_HALF_WIDE_INT]; |
e913b5cd | 1291 | HOST_WIDE_INT mask = ((HOST_WIDE_INT)1 << HOST_BITS_PER_HALF_WIDE_INT) - 1; |
1292 | ||
1293 | /* If the top level routine did not really pass in an overflow, then | |
1294 | just make sure that we never attempt to set it. */ | |
796b6678 | 1295 | bool needs_overflow = (overflow != 0); |
1296 | if (needs_overflow) | |
1297 | *overflow = false; | |
e913b5cd | 1298 | |
25b6c9eb | 1299 | wide_int_ref op1 = wi::storage_ref (op1val, op1len, prec); |
1300 | wide_int_ref op2 = wi::storage_ref (op2val, op2len, prec); | |
1301 | ||
003e7b67 | 1302 | /* This is a surprisingly common case, so do it first. */ |
25b6c9eb | 1303 | if (op1 == 0 || op2 == 0) |
003e7b67 | 1304 | { |
1305 | val[0] = 0; | |
1306 | return 1; | |
1307 | } | |
1308 | ||
25b6c9eb | 1309 | #ifdef umul_ppmm |
1310 | if (sgn == UNSIGNED) | |
1311 | { | |
1312 | /* If the inputs are single HWIs and the output has room for at | |
1313 | least two HWIs, we can use umul_ppmm directly. */ | |
1314 | if (prec >= HOST_BITS_PER_WIDE_INT * 2 | |
1315 | && wi::fits_uhwi_p (op1) | |
1316 | && wi::fits_uhwi_p (op2)) | |
1317 | { | |
ea796d8b | 1318 | /* This case never overflows. */ |
1319 | if (high) | |
1320 | { | |
1321 | val[0] = 0; | |
1322 | return 1; | |
1323 | } | |
25b6c9eb | 1324 | umul_ppmm (val[1], val[0], op1.ulow (), op2.ulow ()); |
da002466 | 1325 | if (val[1] < 0 && prec > HOST_BITS_PER_WIDE_INT * 2) |
1326 | { | |
1327 | val[2] = 0; | |
1328 | return 3; | |
1329 | } | |
25b6c9eb | 1330 | return 1 + (val[1] != 0 || val[0] < 0); |
1331 | } | |
1332 | /* Likewise if the output is a full single HWI, except that the | |
1333 | upper HWI of the result is only used for determining overflow. | |
1334 | (We handle this case inline when overflow isn't needed.) */ | |
1335 | else if (prec == HOST_BITS_PER_WIDE_INT) | |
1336 | { | |
1337 | unsigned HOST_WIDE_INT upper; | |
1338 | umul_ppmm (upper, val[0], op1.ulow (), op2.ulow ()); | |
1339 | if (needs_overflow) | |
1340 | *overflow = (upper != 0); | |
ea796d8b | 1341 | if (high) |
1342 | val[0] = upper; | |
25b6c9eb | 1343 | return 1; |
1344 | } | |
1345 | } | |
1346 | #endif | |
1347 | ||
530b746c | 1348 | /* Handle multiplications by 1. */ |
25b6c9eb | 1349 | if (op1 == 1) |
530b746c | 1350 | { |
ea796d8b | 1351 | if (high) |
1352 | { | |
1353 | val[0] = wi::neg_p (op2, sgn) ? -1 : 0; | |
1354 | return 1; | |
1355 | } | |
530b746c | 1356 | for (i = 0; i < op2len; i++) |
25b6c9eb | 1357 | val[i] = op2val[i]; |
530b746c | 1358 | return op2len; |
1359 | } | |
25b6c9eb | 1360 | if (op2 == 1) |
530b746c | 1361 | { |
ea796d8b | 1362 | if (high) |
1363 | { | |
1364 | val[0] = wi::neg_p (op1, sgn) ? -1 : 0; | |
1365 | return 1; | |
1366 | } | |
530b746c | 1367 | for (i = 0; i < op1len; i++) |
25b6c9eb | 1368 | val[i] = op1val[i]; |
530b746c | 1369 | return op1len; |
1370 | } | |
1371 | ||
e913b5cd | 1372 | /* If we need to check for overflow, we can only do half wide |
1373 | multiplies quickly because we need to look at the top bits to | |
1374 | check for the overflow. */ | |
77d15f37 | 1375 | if ((high || needs_overflow) |
e913b5cd | 1376 | && (prec <= HOST_BITS_PER_HALF_WIDE_INT)) |
1377 | { | |
5b2cae25 | 1378 | unsigned HOST_WIDE_INT r; |
e913b5cd | 1379 | |
1380 | if (sgn == SIGNED) | |
1381 | { | |
25b6c9eb | 1382 | o0 = op1.to_shwi (); |
1383 | o1 = op2.to_shwi (); | |
e913b5cd | 1384 | } |
1385 | else | |
1386 | { | |
25b6c9eb | 1387 | o0 = op1.to_uhwi (); |
1388 | o1 = op2.to_uhwi (); | |
e913b5cd | 1389 | } |
1390 | ||
1391 | r = o0 * o1; | |
1392 | if (needs_overflow) | |
1393 | { | |
e913b5cd | 1394 | if (sgn == SIGNED) |
1395 | { | |
e4712d1e | 1396 | if ((HOST_WIDE_INT) r != sext_hwi (r, prec)) |
e913b5cd | 1397 | *overflow = true; |
1398 | } | |
1399 | else | |
5b2cae25 | 1400 | { |
1401 | if ((r >> prec) != 0) | |
1402 | *overflow = true; | |
1403 | } | |
e913b5cd | 1404 | } |
5b2cae25 | 1405 | val[0] = high ? r >> prec : r; |
796b6678 | 1406 | return 1; |
e913b5cd | 1407 | } |
1408 | ||
1409 | /* We do unsigned mul and then correct it. */ | |
74eae799 | 1410 | wi_unpack (u, op1val, op1len, half_blocks_needed, prec, SIGNED); |
1411 | wi_unpack (v, op2val, op2len, half_blocks_needed, prec, SIGNED); | |
e913b5cd | 1412 | |
1413 | /* The 2 is for a full mult. */ | |
1414 | memset (r, 0, half_blocks_needed * 2 | |
5a2e4914 | 1415 | * HOST_BITS_PER_HALF_WIDE_INT / CHAR_BIT); |
e913b5cd | 1416 | |
1417 | for (j = 0; j < half_blocks_needed; j++) | |
1418 | { | |
1419 | k = 0; | |
1420 | for (i = 0; i < half_blocks_needed; i++) | |
1421 | { | |
1422 | t = ((unsigned HOST_WIDE_INT)u[i] * (unsigned HOST_WIDE_INT)v[j] | |
1423 | + r[i + j] + k); | |
1424 | r[i + j] = t & HALF_INT_MASK; | |
1425 | k = t >> HOST_BITS_PER_HALF_WIDE_INT; | |
1426 | } | |
1427 | r[j + half_blocks_needed] = k; | |
1428 | } | |
1429 | ||
1430 | /* We did unsigned math above. For signed we must adjust the | |
1431 | product (assuming we need to see that). */ | |
77d15f37 | 1432 | if (sgn == SIGNED && (high || needs_overflow)) |
e913b5cd | 1433 | { |
1434 | unsigned HOST_WIDE_INT b; | |
25b6c9eb | 1435 | if (wi::neg_p (op1)) |
e913b5cd | 1436 | { |
1437 | b = 0; | |
1438 | for (i = 0; i < half_blocks_needed; i++) | |
1439 | { | |
1440 | t = (unsigned HOST_WIDE_INT)r[i + half_blocks_needed] | |
1441 | - (unsigned HOST_WIDE_INT)v[i] - b; | |
1442 | r[i + half_blocks_needed] = t & HALF_INT_MASK; | |
1443 | b = t >> (HOST_BITS_PER_WIDE_INT - 1); | |
1444 | } | |
1445 | } | |
25b6c9eb | 1446 | if (wi::neg_p (op2)) |
e913b5cd | 1447 | { |
1448 | b = 0; | |
1449 | for (i = 0; i < half_blocks_needed; i++) | |
1450 | { | |
1451 | t = (unsigned HOST_WIDE_INT)r[i + half_blocks_needed] | |
1452 | - (unsigned HOST_WIDE_INT)u[i] - b; | |
1453 | r[i + half_blocks_needed] = t & HALF_INT_MASK; | |
1454 | b = t >> (HOST_BITS_PER_WIDE_INT - 1); | |
1455 | } | |
1456 | } | |
1457 | } | |
1458 | ||
1459 | if (needs_overflow) | |
1460 | { | |
1461 | HOST_WIDE_INT top; | |
1462 | ||
1463 | /* For unsigned, overflow is true if any of the top bits are set. | |
1464 | For signed, overflow is true if any of the top bits are not equal | |
1465 | to the sign bit. */ | |
1466 | if (sgn == UNSIGNED) | |
1467 | top = 0; | |
1468 | else | |
1469 | { | |
1470 | top = r[(half_blocks_needed) - 1]; | |
1471 | top = SIGN_MASK (top << (HOST_BITS_PER_WIDE_INT / 2)); | |
1472 | top &= mask; | |
1473 | } | |
1474 | ||
1475 | for (i = half_blocks_needed; i < half_blocks_needed * 2; i++) | |
1476 | if (((HOST_WIDE_INT)(r[i] & mask)) != top) | |
1477 | *overflow = true; | |
1478 | } | |
1479 | ||
ef7be7f8 | 1480 | int r_offset = high ? half_blocks_needed : 0; |
1481 | return wi_pack (val, &r[r_offset], half_blocks_needed, prec); | |
e913b5cd | 1482 | } |
1483 | ||
796b6678 | 1484 | /* Compute the population count of X. */ |
1485 | int | |
1486 | wi::popcount (const wide_int_ref &x) | |
e913b5cd | 1487 | { |
796b6678 | 1488 | unsigned int i; |
e913b5cd | 1489 | int count; |
e913b5cd | 1490 | |
e913b5cd | 1491 | /* The high order block is special if it is the last block and the |
1492 | precision is not an even multiple of HOST_BITS_PER_WIDE_INT. We | |
1493 | have to clear out any ones above the precision before doing | |
1494 | popcount on this block. */ | |
796b6678 | 1495 | count = x.precision - x.len * HOST_BITS_PER_WIDE_INT; |
1496 | unsigned int stop = x.len; | |
1497 | if (count < 0) | |
e913b5cd | 1498 | { |
796b6678 | 1499 | count = popcount_hwi (x.uhigh () << -count); |
1500 | stop -= 1; | |
e913b5cd | 1501 | } |
1502 | else | |
1503 | { | |
796b6678 | 1504 | if (x.sign_mask () >= 0) |
1505 | count = 0; | |
e913b5cd | 1506 | } |
1507 | ||
796b6678 | 1508 | for (i = 0; i < stop; ++i) |
1509 | count += popcount_hwi (x.val[i]); | |
e913b5cd | 1510 | |
796b6678 | 1511 | return count; |
e913b5cd | 1512 | } |
1513 | ||
796b6678 | 1514 | /* Set VAL to OP0 - OP1. If OVERFLOW is nonnull, record in *OVERFLOW |
1515 | whether the result overflows when OP0 and OP1 are treated as having | |
1516 | signedness SGN. Return the number of blocks in VAL. */ | |
1517 | unsigned int | |
1518 | wi::sub_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *op0, | |
1519 | unsigned int op0len, const HOST_WIDE_INT *op1, | |
1520 | unsigned int op1len, unsigned int prec, | |
1521 | signop sgn, bool *overflow) | |
e913b5cd | 1522 | { |
e913b5cd | 1523 | unsigned HOST_WIDE_INT o0 = 0; |
1524 | unsigned HOST_WIDE_INT o1 = 0; | |
1525 | unsigned HOST_WIDE_INT x = 0; | |
1526 | /* We implement subtraction as an in place negate and add. Negation | |
1527 | is just inversion and add 1, so we can do the add of 1 by just | |
1528 | starting the borrow in of the first element at 1. */ | |
1529 | unsigned HOST_WIDE_INT borrow = 0; | |
1530 | unsigned HOST_WIDE_INT old_borrow = 0; | |
1531 | ||
1532 | unsigned HOST_WIDE_INT mask0, mask1; | |
5b2cae25 | 1533 | unsigned int i; |
e913b5cd | 1534 | |
796b6678 | 1535 | unsigned int len = MAX (op0len, op1len); |
5b2cae25 | 1536 | mask0 = -top_bit_of (op0, op0len, prec); |
1537 | mask1 = -top_bit_of (op1, op1len, prec); | |
e913b5cd | 1538 | |
1539 | /* Subtract all of the explicitly defined elements. */ | |
796b6678 | 1540 | for (i = 0; i < len; i++) |
e913b5cd | 1541 | { |
1542 | o0 = i < op0len ? (unsigned HOST_WIDE_INT)op0[i] : mask0; | |
1543 | o1 = i < op1len ? (unsigned HOST_WIDE_INT)op1[i] : mask1; | |
1544 | x = o0 - o1 - borrow; | |
796b6678 | 1545 | val[i] = x; |
e913b5cd | 1546 | old_borrow = borrow; |
1547 | borrow = borrow == 0 ? o0 < o1 : o0 <= o1; | |
1548 | } | |
1549 | ||
796b6678 | 1550 | if (len * HOST_BITS_PER_WIDE_INT < prec) |
e913b5cd | 1551 | { |
796b6678 | 1552 | val[len] = mask0 - mask1 - borrow; |
1553 | len++; | |
e913b5cd | 1554 | if (overflow) |
1555 | *overflow = false; | |
1556 | } | |
1557 | else if (overflow) | |
1558 | { | |
5b2cae25 | 1559 | unsigned int shift = -prec % HOST_BITS_PER_WIDE_INT; |
e913b5cd | 1560 | if (sgn == SIGNED) |
1561 | { | |
5b2cae25 | 1562 | unsigned HOST_WIDE_INT x = (o0 ^ o1) & (val[len - 1] ^ o0); |
3b247a20 | 1563 | *overflow = (HOST_WIDE_INT) (x << shift) < 0; |
e913b5cd | 1564 | } |
1565 | else | |
1566 | { | |
5b2cae25 | 1567 | /* Put the MSB of X and O0 and in the top of the HWI. */ |
1568 | x <<= shift; | |
1569 | o0 <<= shift; | |
e913b5cd | 1570 | if (old_borrow) |
5b2cae25 | 1571 | *overflow = (x >= o0); |
e913b5cd | 1572 | else |
5b2cae25 | 1573 | *overflow = (x > o0); |
e913b5cd | 1574 | } |
1575 | } | |
1576 | ||
796b6678 | 1577 | return canonize (val, len, prec); |
e913b5cd | 1578 | } |
1579 | ||
1580 | ||
1581 | /* | |
1582 | * Division and Mod | |
1583 | */ | |
1584 | ||
1585 | /* Compute B_QUOTIENT and B_REMAINDER from B_DIVIDEND/B_DIVISOR. The | |
1586 | algorithm is a small modification of the algorithm in Hacker's | |
1587 | Delight by Warren, which itself is a small modification of Knuth's | |
1588 | algorithm. M is the number of significant elements of U however | |
1589 | there needs to be at least one extra element of B_DIVIDEND | |
1590 | allocated, N is the number of elements of B_DIVISOR. */ | |
796b6678 | 1591 | static void |
1592 | divmod_internal_2 (unsigned HOST_HALF_WIDE_INT *b_quotient, | |
1593 | unsigned HOST_HALF_WIDE_INT *b_remainder, | |
1594 | unsigned HOST_HALF_WIDE_INT *b_dividend, | |
1595 | unsigned HOST_HALF_WIDE_INT *b_divisor, | |
74eae799 | 1596 | int m, int n) |
e913b5cd | 1597 | { |
1598 | /* The "digits" are a HOST_HALF_WIDE_INT which the size of half of a | |
1599 | HOST_WIDE_INT and stored in the lower bits of each word. This | |
1600 | algorithm should work properly on both 32 and 64 bit | |
1601 | machines. */ | |
1602 | unsigned HOST_WIDE_INT b | |
1603 | = (unsigned HOST_WIDE_INT)1 << HOST_BITS_PER_HALF_WIDE_INT; | |
1604 | unsigned HOST_WIDE_INT qhat; /* Estimate of quotient digit. */ | |
1605 | unsigned HOST_WIDE_INT rhat; /* A remainder. */ | |
1606 | unsigned HOST_WIDE_INT p; /* Product of two digits. */ | |
74eae799 | 1607 | HOST_WIDE_INT t, k; |
1608 | int i, j, s; | |
e913b5cd | 1609 | |
1610 | /* Single digit divisor. */ | |
1611 | if (n == 1) | |
1612 | { | |
1613 | k = 0; | |
1614 | for (j = m - 1; j >= 0; j--) | |
1615 | { | |
1616 | b_quotient[j] = (k * b + b_dividend[j])/b_divisor[0]; | |
1617 | k = ((k * b + b_dividend[j]) | |
1618 | - ((unsigned HOST_WIDE_INT)b_quotient[j] | |
1619 | * (unsigned HOST_WIDE_INT)b_divisor[0])); | |
1620 | } | |
1621 | b_remainder[0] = k; | |
1622 | return; | |
1623 | } | |
1624 | ||
1625 | s = clz_hwi (b_divisor[n-1]) - HOST_BITS_PER_HALF_WIDE_INT; /* CHECK clz */ | |
1626 | ||
1627 | if (s) | |
1628 | { | |
1629 | /* Normalize B_DIVIDEND and B_DIVISOR. Unlike the published | |
1630 | algorithm, we can overwrite b_dividend and b_divisor, so we do | |
1631 | that. */ | |
1632 | for (i = n - 1; i > 0; i--) | |
1633 | b_divisor[i] = (b_divisor[i] << s) | |
1634 | | (b_divisor[i-1] >> (HOST_BITS_PER_HALF_WIDE_INT - s)); | |
1635 | b_divisor[0] = b_divisor[0] << s; | |
0ebd4fb5 | 1636 | |
e913b5cd | 1637 | b_dividend[m] = b_dividend[m-1] >> (HOST_BITS_PER_HALF_WIDE_INT - s); |
1638 | for (i = m - 1; i > 0; i--) | |
1639 | b_dividend[i] = (b_dividend[i] << s) | |
1640 | | (b_dividend[i-1] >> (HOST_BITS_PER_HALF_WIDE_INT - s)); | |
1641 | b_dividend[0] = b_dividend[0] << s; | |
1642 | } | |
1643 | ||
1644 | /* Main loop. */ | |
1645 | for (j = m - n; j >= 0; j--) | |
1646 | { | |
1647 | qhat = (b_dividend[j+n] * b + b_dividend[j+n-1]) / b_divisor[n-1]; | |
1648 | rhat = (b_dividend[j+n] * b + b_dividend[j+n-1]) - qhat * b_divisor[n-1]; | |
1649 | again: | |
1650 | if (qhat >= b || qhat * b_divisor[n-2] > b * rhat + b_dividend[j+n-2]) | |
1651 | { | |
1652 | qhat -= 1; | |
1653 | rhat += b_divisor[n-1]; | |
1654 | if (rhat < b) | |
1655 | goto again; | |
1656 | } | |
1657 | ||
1658 | /* Multiply and subtract. */ | |
1659 | k = 0; | |
1660 | for (i = 0; i < n; i++) | |
1661 | { | |
1662 | p = qhat * b_divisor[i]; | |
1663 | t = b_dividend[i+j] - k - (p & HALF_INT_MASK); | |
1664 | b_dividend[i + j] = t; | |
1665 | k = ((p >> HOST_BITS_PER_HALF_WIDE_INT) | |
1666 | - (t >> HOST_BITS_PER_HALF_WIDE_INT)); | |
1667 | } | |
1668 | t = b_dividend[j+n] - k; | |
1669 | b_dividend[j+n] = t; | |
1670 | ||
1671 | b_quotient[j] = qhat; | |
1672 | if (t < 0) | |
1673 | { | |
1674 | b_quotient[j] -= 1; | |
1675 | k = 0; | |
1676 | for (i = 0; i < n; i++) | |
1677 | { | |
1678 | t = (HOST_WIDE_INT)b_dividend[i+j] + b_divisor[i] + k; | |
1679 | b_dividend[i+j] = t; | |
1680 | k = t >> HOST_BITS_PER_HALF_WIDE_INT; | |
1681 | } | |
1682 | b_dividend[j+n] += k; | |
1683 | } | |
1684 | } | |
1685 | if (s) | |
1686 | for (i = 0; i < n; i++) | |
1687 | b_remainder[i] = (b_dividend[i] >> s) | |
1688 | | (b_dividend[i+1] << (HOST_BITS_PER_HALF_WIDE_INT - s)); | |
1689 | else | |
1690 | for (i = 0; i < n; i++) | |
1691 | b_remainder[i] = b_dividend[i]; | |
1692 | } | |
1693 | ||
1694 | ||
796b6678 | 1695 | /* Divide DIVIDEND by DIVISOR, which have signedness SGN, and truncate |
1696 | the result. If QUOTIENT is nonnull, store the value of the quotient | |
1697 | there and return the number of blocks in it. The return value is | |
1698 | not defined otherwise. If REMAINDER is nonnull, store the value | |
1699 | of the remainder there and store the number of blocks in | |
1700 | *REMAINDER_LEN. If OFLOW is not null, store in *OFLOW whether | |
1701 | the division overflowed. */ | |
1702 | unsigned int | |
1703 | wi::divmod_internal (HOST_WIDE_INT *quotient, unsigned int *remainder_len, | |
d1314cdb | 1704 | HOST_WIDE_INT *remainder, |
1705 | const HOST_WIDE_INT *dividend_val, | |
796b6678 | 1706 | unsigned int dividend_len, unsigned int dividend_prec, |
d1314cdb | 1707 | const HOST_WIDE_INT *divisor_val, unsigned int divisor_len, |
796b6678 | 1708 | unsigned int divisor_prec, signop sgn, |
1709 | bool *oflow) | |
1710 | { | |
1711 | unsigned int dividend_blocks_needed = 2 * BLOCKS_NEEDED (dividend_prec); | |
1712 | unsigned int divisor_blocks_needed = 2 * BLOCKS_NEEDED (divisor_prec); | |
e913b5cd | 1713 | unsigned HOST_HALF_WIDE_INT |
1714 | b_quotient[4 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_HALF_WIDE_INT]; | |
1715 | unsigned HOST_HALF_WIDE_INT | |
1716 | b_remainder[4 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_HALF_WIDE_INT]; | |
1717 | unsigned HOST_HALF_WIDE_INT | |
1718 | b_dividend[(4 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_HALF_WIDE_INT) + 1]; | |
1719 | unsigned HOST_HALF_WIDE_INT | |
1720 | b_divisor[4 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_HALF_WIDE_INT]; | |
796b6678 | 1721 | unsigned int m, n; |
e913b5cd | 1722 | bool dividend_neg = false; |
1723 | bool divisor_neg = false; | |
1724 | bool overflow = false; | |
d1314cdb | 1725 | wide_int neg_dividend, neg_divisor; |
e913b5cd | 1726 | |
d1314cdb | 1727 | wide_int_ref dividend = wi::storage_ref (dividend_val, dividend_len, |
1728 | dividend_prec); | |
1729 | wide_int_ref divisor = wi::storage_ref (divisor_val, divisor_len, | |
1730 | divisor_prec); | |
1731 | if (divisor == 0) | |
e913b5cd | 1732 | overflow = true; |
1733 | ||
d1314cdb | 1734 | /* The smallest signed number / -1 causes overflow. The dividend_len |
1735 | check is for speed rather than correctness. */ | |
5b2cae25 | 1736 | if (sgn == SIGNED |
1737 | && dividend_len == BLOCKS_NEEDED (dividend_prec) | |
d1314cdb | 1738 | && divisor == -1 |
1739 | && wi::only_sign_bit_p (dividend)) | |
1740 | overflow = true; | |
e913b5cd | 1741 | |
3a343682 | 1742 | /* Handle the overflow cases. Viewed as unsigned value, the quotient of |
1743 | (signed min / -1) has the same representation as the orignal dividend. | |
1744 | We have traditionally made division by zero act as division by one, | |
1745 | so there too we use the original dividend. */ | |
e913b5cd | 1746 | if (overflow) |
1747 | { | |
796b6678 | 1748 | if (remainder) |
e913b5cd | 1749 | { |
796b6678 | 1750 | *remainder_len = 1; |
1751 | remainder[0] = 0; | |
e913b5cd | 1752 | } |
1753 | if (oflow != 0) | |
1754 | *oflow = true; | |
796b6678 | 1755 | if (quotient) |
3a343682 | 1756 | for (unsigned int i = 0; i < dividend_len; ++i) |
1757 | quotient[i] = dividend_val[i]; | |
1758 | return dividend_len; | |
e913b5cd | 1759 | } |
1760 | ||
796b6678 | 1761 | if (oflow) |
1762 | *oflow = false; | |
1763 | ||
e913b5cd | 1764 | /* Do it on the host if you can. */ |
d1314cdb | 1765 | if (sgn == SIGNED |
1766 | && wi::fits_shwi_p (dividend) | |
1767 | && wi::fits_shwi_p (divisor)) | |
e913b5cd | 1768 | { |
d1314cdb | 1769 | HOST_WIDE_INT o0 = dividend.to_shwi (); |
1770 | HOST_WIDE_INT o1 = divisor.to_shwi (); | |
e913b5cd | 1771 | |
d1314cdb | 1772 | if (o0 == HOST_WIDE_INT_MIN && o1 == -1) |
1773 | { | |
1774 | gcc_checking_assert (dividend_prec > HOST_BITS_PER_WIDE_INT); | |
796b6678 | 1775 | if (quotient) |
d1314cdb | 1776 | { |
1777 | quotient[0] = HOST_WIDE_INT_MIN; | |
1778 | quotient[1] = 0; | |
1779 | } | |
796b6678 | 1780 | if (remainder) |
1781 | { | |
d1314cdb | 1782 | remainder[0] = 0; |
796b6678 | 1783 | *remainder_len = 1; |
1784 | } | |
d1314cdb | 1785 | return 2; |
e913b5cd | 1786 | } |
1787 | else | |
1788 | { | |
796b6678 | 1789 | if (quotient) |
5b2cae25 | 1790 | quotient[0] = o0 / o1; |
796b6678 | 1791 | if (remainder) |
1792 | { | |
5b2cae25 | 1793 | remainder[0] = o0 % o1; |
796b6678 | 1794 | *remainder_len = 1; |
1795 | } | |
d1314cdb | 1796 | return 1; |
e913b5cd | 1797 | } |
d1314cdb | 1798 | } |
1799 | ||
1800 | if (sgn == UNSIGNED | |
1801 | && wi::fits_uhwi_p (dividend) | |
1802 | && wi::fits_uhwi_p (divisor)) | |
1803 | { | |
1804 | unsigned HOST_WIDE_INT o0 = dividend.to_uhwi (); | |
1805 | unsigned HOST_WIDE_INT o1 = divisor.to_uhwi (); | |
3b8b902b | 1806 | unsigned int quotient_len = 1; |
e913b5cd | 1807 | |
d1314cdb | 1808 | if (quotient) |
3b8b902b | 1809 | { |
1810 | quotient[0] = o0 / o1; | |
70bca70e | 1811 | quotient_len = canonize_uhwi (quotient, dividend_prec); |
3b8b902b | 1812 | } |
d1314cdb | 1813 | if (remainder) |
1814 | { | |
1815 | remainder[0] = o0 % o1; | |
70bca70e | 1816 | *remainder_len = canonize_uhwi (remainder, dividend_prec); |
d1314cdb | 1817 | } |
3b8b902b | 1818 | return quotient_len; |
e913b5cd | 1819 | } |
1820 | ||
1821 | /* Make the divisor and dividend positive and remember what we | |
1822 | did. */ | |
1823 | if (sgn == SIGNED) | |
1824 | { | |
d1314cdb | 1825 | if (wi::neg_p (dividend)) |
e913b5cd | 1826 | { |
d1314cdb | 1827 | neg_dividend = -dividend; |
1828 | dividend = neg_dividend; | |
e913b5cd | 1829 | dividend_neg = true; |
1830 | } | |
d1314cdb | 1831 | if (wi::neg_p (divisor)) |
e913b5cd | 1832 | { |
d1314cdb | 1833 | neg_divisor = -divisor; |
1834 | divisor = neg_divisor; | |
e913b5cd | 1835 | divisor_neg = true; |
1836 | } | |
1837 | } | |
1838 | ||
74eae799 | 1839 | wi_unpack (b_dividend, dividend.get_val (), dividend.get_len (), |
1840 | dividend_blocks_needed, dividend_prec, sgn); | |
1841 | wi_unpack (b_divisor, divisor.get_val (), divisor.get_len (), | |
1842 | divisor_blocks_needed, divisor_prec, sgn); | |
e913b5cd | 1843 | |
74eae799 | 1844 | m = dividend_blocks_needed; |
e80d050d | 1845 | b_dividend[m] = 0; |
74eae799 | 1846 | while (m > 1 && b_dividend[m - 1] == 0) |
1847 | m--; | |
e913b5cd | 1848 | |
74eae799 | 1849 | n = divisor_blocks_needed; |
1850 | while (n > 1 && b_divisor[n - 1] == 0) | |
e913b5cd | 1851 | n--; |
1852 | ||
1853 | memset (b_quotient, 0, sizeof (b_quotient)); | |
1854 | ||
1855 | divmod_internal_2 (b_quotient, b_remainder, b_dividend, b_divisor, m, n); | |
1856 | ||
796b6678 | 1857 | unsigned int quotient_len = 0; |
1858 | if (quotient) | |
e913b5cd | 1859 | { |
ef7be7f8 | 1860 | quotient_len = wi_pack (quotient, b_quotient, m, dividend_prec); |
e913b5cd | 1861 | /* The quotient is neg if exactly one of the divisor or dividend is |
1862 | neg. */ | |
1863 | if (dividend_neg != divisor_neg) | |
796b6678 | 1864 | quotient_len = wi::sub_large (quotient, zeros, 1, quotient, |
1865 | quotient_len, dividend_prec, | |
1866 | UNSIGNED, 0); | |
e913b5cd | 1867 | } |
e913b5cd | 1868 | |
796b6678 | 1869 | if (remainder) |
e913b5cd | 1870 | { |
ef7be7f8 | 1871 | *remainder_len = wi_pack (remainder, b_remainder, n, dividend_prec); |
e913b5cd | 1872 | /* The remainder is always the same sign as the dividend. */ |
1873 | if (dividend_neg) | |
796b6678 | 1874 | *remainder_len = wi::sub_large (remainder, zeros, 1, remainder, |
1875 | *remainder_len, dividend_prec, | |
1876 | UNSIGNED, 0); | |
e913b5cd | 1877 | } |
e913b5cd | 1878 | |
796b6678 | 1879 | return quotient_len; |
e913b5cd | 1880 | } |
1881 | ||
796b6678 | 1882 | /* |
1883 | * Shifting, rotating and extraction. | |
1884 | */ | |
e913b5cd | 1885 | |
796b6678 | 1886 | /* Left shift XVAL by SHIFT and store the result in VAL. Return the |
1887 | number of blocks in VAL. Both XVAL and VAL have PRECISION bits. */ | |
1888 | unsigned int | |
1889 | wi::lshift_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval, | |
1890 | unsigned int xlen, unsigned int precision, | |
1891 | unsigned int shift) | |
1892 | { | |
1893 | /* Split the shift into a whole-block shift and a subblock shift. */ | |
1894 | unsigned int skip = shift / HOST_BITS_PER_WIDE_INT; | |
1895 | unsigned int small_shift = shift % HOST_BITS_PER_WIDE_INT; | |
1896 | ||
1897 | /* The whole-block shift fills with zeros. */ | |
1898 | unsigned int len = BLOCKS_NEEDED (precision); | |
1899 | for (unsigned int i = 0; i < skip; ++i) | |
1900 | val[i] = 0; | |
1901 | ||
1902 | /* It's easier to handle the simple block case specially. */ | |
1903 | if (small_shift == 0) | |
1904 | for (unsigned int i = skip; i < len; ++i) | |
1905 | val[i] = safe_uhwi (xval, xlen, i - skip); | |
1906 | else | |
e913b5cd | 1907 | { |
796b6678 | 1908 | /* The first unfilled output block is a left shift of the first |
1909 | block in XVAL. The other output blocks contain bits from two | |
1910 | consecutive input blocks. */ | |
1911 | unsigned HOST_WIDE_INT carry = 0; | |
1912 | for (unsigned int i = skip; i < len; ++i) | |
1913 | { | |
1914 | unsigned HOST_WIDE_INT x = safe_uhwi (xval, xlen, i - skip); | |
1915 | val[i] = (x << small_shift) | carry; | |
1916 | carry = x >> (-small_shift % HOST_BITS_PER_WIDE_INT); | |
1917 | } | |
e913b5cd | 1918 | } |
796b6678 | 1919 | return canonize (val, len, precision); |
e913b5cd | 1920 | } |
1921 | ||
796b6678 | 1922 | /* Right shift XVAL by SHIFT and store the result in VAL. Return the |
1923 | number of blocks in VAL. The input has XPRECISION bits and the | |
1924 | output has XPRECISION - SHIFT bits. */ | |
1925 | static unsigned int | |
1926 | rshift_large_common (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval, | |
1927 | unsigned int xlen, unsigned int xprecision, | |
1928 | unsigned int shift) | |
e913b5cd | 1929 | { |
796b6678 | 1930 | /* Split the shift into a whole-block shift and a subblock shift. */ |
1931 | unsigned int skip = shift / HOST_BITS_PER_WIDE_INT; | |
1932 | unsigned int small_shift = shift % HOST_BITS_PER_WIDE_INT; | |
e913b5cd | 1933 | |
796b6678 | 1934 | /* Work out how many blocks are needed to store the significant bits |
1935 | (excluding the upper zeros or signs). */ | |
1936 | unsigned int len = BLOCKS_NEEDED (xprecision - shift); | |
e913b5cd | 1937 | |
796b6678 | 1938 | /* It's easier to handle the simple block case specially. */ |
1939 | if (small_shift == 0) | |
1940 | for (unsigned int i = 0; i < len; ++i) | |
1941 | val[i] = safe_uhwi (xval, xlen, i + skip); | |
e913b5cd | 1942 | else |
1943 | { | |
796b6678 | 1944 | /* Each output block but the last is a combination of two input blocks. |
1945 | The last block is a right shift of the last block in XVAL. */ | |
1946 | unsigned HOST_WIDE_INT curr = safe_uhwi (xval, xlen, skip); | |
1947 | for (unsigned int i = 0; i < len; ++i) | |
1948 | { | |
1949 | val[i] = curr >> small_shift; | |
1950 | curr = safe_uhwi (xval, xlen, i + skip + 1); | |
1951 | val[i] |= curr << (-small_shift % HOST_BITS_PER_WIDE_INT); | |
1952 | } | |
e913b5cd | 1953 | } |
796b6678 | 1954 | return len; |
1955 | } | |
e913b5cd | 1956 | |
796b6678 | 1957 | /* Logically right shift XVAL by SHIFT and store the result in VAL. |
1958 | Return the number of blocks in VAL. XVAL has XPRECISION bits and | |
1959 | VAL has PRECISION bits. */ | |
1960 | unsigned int | |
1961 | wi::lrshift_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval, | |
1962 | unsigned int xlen, unsigned int xprecision, | |
1963 | unsigned int precision, unsigned int shift) | |
1964 | { | |
1965 | unsigned int len = rshift_large_common (val, xval, xlen, xprecision, shift); | |
e913b5cd | 1966 | |
796b6678 | 1967 | /* The value we just created has precision XPRECISION - SHIFT. |
1968 | Zero-extend it to wider precisions. */ | |
1969 | if (precision > xprecision - shift) | |
1970 | { | |
1971 | unsigned int small_prec = (xprecision - shift) % HOST_BITS_PER_WIDE_INT; | |
1972 | if (small_prec) | |
1973 | val[len - 1] = zext_hwi (val[len - 1], small_prec); | |
1974 | else if (val[len - 1] < 0) | |
1975 | { | |
1976 | /* Add a new block with a zero. */ | |
1977 | val[len++] = 0; | |
1978 | return len; | |
1979 | } | |
e913b5cd | 1980 | } |
796b6678 | 1981 | return canonize (val, len, precision); |
e913b5cd | 1982 | } |
1983 | ||
796b6678 | 1984 | /* Arithmetically right shift XVAL by SHIFT and store the result in VAL. |
1985 | Return the number of blocks in VAL. XVAL has XPRECISION bits and | |
1986 | VAL has PRECISION bits. */ | |
1987 | unsigned int | |
1988 | wi::arshift_large (HOST_WIDE_INT *val, const HOST_WIDE_INT *xval, | |
1989 | unsigned int xlen, unsigned int xprecision, | |
1990 | unsigned int precision, unsigned int shift) | |
e913b5cd | 1991 | { |
796b6678 | 1992 | unsigned int len = rshift_large_common (val, xval, xlen, xprecision, shift); |
e913b5cd | 1993 | |
796b6678 | 1994 | /* The value we just created has precision XPRECISION - SHIFT. |
1995 | Sign-extend it to wider types. */ | |
1996 | if (precision > xprecision - shift) | |
e913b5cd | 1997 | { |
796b6678 | 1998 | unsigned int small_prec = (xprecision - shift) % HOST_BITS_PER_WIDE_INT; |
1999 | if (small_prec) | |
2000 | val[len - 1] = sext_hwi (val[len - 1], small_prec); | |
e913b5cd | 2001 | } |
796b6678 | 2002 | return canonize (val, len, precision); |
2003 | } | |
e913b5cd | 2004 | |
796b6678 | 2005 | /* Return the number of leading (upper) zeros in X. */ |
2006 | int | |
2007 | wi::clz (const wide_int_ref &x) | |
2008 | { | |
2009 | /* Calculate how many bits there above the highest represented block. */ | |
2010 | int count = x.precision - x.len * HOST_BITS_PER_WIDE_INT; | |
2011 | ||
2012 | unsigned HOST_WIDE_INT high = x.uhigh (); | |
2013 | if (count < 0) | |
2014 | /* The upper -COUNT bits of HIGH are not part of the value. | |
2015 | Clear them out. */ | |
2016 | high = (high << -count) >> -count; | |
2017 | else if (x.sign_mask () < 0) | |
2018 | /* The upper bit is set, so there are no leading zeros. */ | |
2019 | return 0; | |
e913b5cd | 2020 | |
796b6678 | 2021 | /* We don't need to look below HIGH. Either HIGH is nonzero, |
2022 | or the top bit of the block below is nonzero; clz_hwi is | |
2023 | HOST_BITS_PER_WIDE_INT in the latter case. */ | |
2024 | return count + clz_hwi (high); | |
e913b5cd | 2025 | } |
2026 | ||
796b6678 | 2027 | /* Return the number of redundant sign bits in X. (That is, the number |
2028 | of bits immediately below the sign bit that have the same value as | |
2029 | the sign bit.) */ | |
2030 | int | |
2031 | wi::clrsb (const wide_int_ref &x) | |
e913b5cd | 2032 | { |
796b6678 | 2033 | /* Calculate how many bits there above the highest represented block. */ |
2034 | int count = x.precision - x.len * HOST_BITS_PER_WIDE_INT; | |
e913b5cd | 2035 | |
796b6678 | 2036 | unsigned HOST_WIDE_INT high = x.uhigh (); |
2037 | unsigned HOST_WIDE_INT mask = -1; | |
2038 | if (count < 0) | |
e913b5cd | 2039 | { |
796b6678 | 2040 | /* The upper -COUNT bits of HIGH are not part of the value. |
2041 | Clear them from both MASK and HIGH. */ | |
2042 | mask >>= -count; | |
2043 | high &= mask; | |
e913b5cd | 2044 | } |
2045 | ||
796b6678 | 2046 | /* If the top bit is 1, count the number of leading 1s. If the top |
2047 | bit is zero, count the number of leading zeros. */ | |
2048 | if (high > mask / 2) | |
2049 | high ^= mask; | |
e913b5cd | 2050 | |
796b6678 | 2051 | /* There are no sign bits below the top block, so we don't need to look |
2052 | beyond HIGH. Note that clz_hwi is HOST_BITS_PER_WIDE_INT when | |
2053 | HIGH is 0. */ | |
2054 | return count + clz_hwi (high) - 1; | |
2055 | } | |
e913b5cd | 2056 | |
796b6678 | 2057 | /* Return the number of trailing (lower) zeros in X. */ |
2058 | int | |
2059 | wi::ctz (const wide_int_ref &x) | |
2060 | { | |
2061 | if (x.len == 1 && x.ulow () == 0) | |
1cee90ad | 2062 | return x.precision; |
e913b5cd | 2063 | |
796b6678 | 2064 | /* Having dealt with the zero case, there must be a block with a |
2065 | nonzero bit. We don't care about the bits above the first 1. */ | |
2066 | unsigned int i = 0; | |
2067 | while (x.val[i] == 0) | |
2068 | ++i; | |
2069 | return i * HOST_BITS_PER_WIDE_INT + ctz_hwi (x.val[i]); | |
e913b5cd | 2070 | } |
2071 | ||
796b6678 | 2072 | /* If X is an exact power of 2, return the base-2 logarithm, otherwise |
2073 | return -1. */ | |
2074 | int | |
2075 | wi::exact_log2 (const wide_int_ref &x) | |
e913b5cd | 2076 | { |
796b6678 | 2077 | /* Reject cases where there are implicit -1 blocks above HIGH. */ |
2078 | if (x.len * HOST_BITS_PER_WIDE_INT < x.precision && x.sign_mask () < 0) | |
2079 | return -1; | |
e913b5cd | 2080 | |
796b6678 | 2081 | /* Set CRUX to the index of the entry that should be nonzero. |
2082 | If the top block is zero then the next lowest block (if any) | |
2083 | must have the high bit set. */ | |
2084 | unsigned int crux = x.len - 1; | |
2085 | if (crux > 0 && x.val[crux] == 0) | |
2086 | crux -= 1; | |
2087 | ||
2088 | /* Check that all lower blocks are zero. */ | |
2089 | for (unsigned int i = 0; i < crux; ++i) | |
2090 | if (x.val[i] != 0) | |
2091 | return -1; | |
2092 | ||
2093 | /* Get a zero-extended form of block CRUX. */ | |
2094 | unsigned HOST_WIDE_INT hwi = x.val[crux]; | |
e9880ac8 | 2095 | if ((crux + 1) * HOST_BITS_PER_WIDE_INT > x.precision) |
796b6678 | 2096 | hwi = zext_hwi (hwi, x.precision % HOST_BITS_PER_WIDE_INT); |
2097 | ||
2098 | /* Now it's down to whether HWI is a power of 2. */ | |
2099 | int res = ::exact_log2 (hwi); | |
2100 | if (res >= 0) | |
2101 | res += crux * HOST_BITS_PER_WIDE_INT; | |
2102 | return res; | |
2103 | } | |
e913b5cd | 2104 | |
796b6678 | 2105 | /* Return the base-2 logarithm of X, rounding down. Return -1 if X is 0. */ |
2106 | int | |
2107 | wi::floor_log2 (const wide_int_ref &x) | |
2108 | { | |
2109 | return x.precision - 1 - clz (x); | |
2110 | } | |
e913b5cd | 2111 | |
796b6678 | 2112 | /* Return the index of the first (lowest) set bit in X, counting from 1. |
2113 | Return 0 if X is 0. */ | |
2114 | int | |
2115 | wi::ffs (const wide_int_ref &x) | |
2116 | { | |
2117 | return eq_p (x, 0) ? 0 : ctz (x) + 1; | |
2118 | } | |
e913b5cd | 2119 | |
796b6678 | 2120 | /* Return true if sign-extending X to have precision PRECISION would give |
2121 | the minimum signed value at that precision. */ | |
2122 | bool | |
2123 | wi::only_sign_bit_p (const wide_int_ref &x, unsigned int precision) | |
2124 | { | |
2125 | return ctz (x) + 1 == int (precision); | |
2126 | } | |
e913b5cd | 2127 | |
796b6678 | 2128 | /* Return true if X represents the minimum signed value. */ |
2129 | bool | |
2130 | wi::only_sign_bit_p (const wide_int_ref &x) | |
2131 | { | |
2132 | return only_sign_bit_p (x, x.precision); | |
e913b5cd | 2133 | } |
2134 | ||
2135 | /* | |
2136 | * Private utilities. | |
2137 | */ | |
2138 | ||
5de9d3ed | 2139 | void gt_ggc_mx (widest_int *) { } |
2140 | void gt_pch_nx (widest_int *, void (*) (void *, void *), void *) { } | |
2141 | void gt_pch_nx (widest_int *) { } | |
c2393a0b | 2142 | |
2143 | template void wide_int::dump () const; | |
2144 | template void generic_wide_int <wide_int_ref_storage <false> >::dump () const; | |
2145 | template void generic_wide_int <wide_int_ref_storage <true> >::dump () const; | |
2146 | template void offset_int::dump () const; | |
2147 | template void widest_int::dump () const; | |
99b4f3a2 | 2148 | |
2149 | ||
2150 | #if CHECKING_P | |
2151 | ||
2152 | namespace selftest { | |
2153 | ||
2154 | /* Selftests for wide ints. We run these multiple times, once per type. */ | |
2155 | ||
2156 | /* Helper function for building a test value. */ | |
2157 | ||
2158 | template <class VALUE_TYPE> | |
2159 | static VALUE_TYPE | |
2160 | from_int (int i); | |
2161 | ||
2162 | /* Specializations of the fixture for each wide-int type. */ | |
2163 | ||
2164 | /* Specialization for VALUE_TYPE == wide_int. */ | |
2165 | ||
2166 | template <> | |
2167 | wide_int | |
2168 | from_int (int i) | |
2169 | { | |
2170 | return wi::shwi (i, 32); | |
2171 | } | |
2172 | ||
2173 | /* Specialization for VALUE_TYPE == offset_int. */ | |
2174 | ||
2175 | template <> | |
2176 | offset_int | |
2177 | from_int (int i) | |
2178 | { | |
2179 | return offset_int (i); | |
2180 | } | |
2181 | ||
2182 | /* Specialization for VALUE_TYPE == widest_int. */ | |
2183 | ||
2184 | template <> | |
2185 | widest_int | |
2186 | from_int (int i) | |
2187 | { | |
2188 | return widest_int (i); | |
2189 | } | |
2190 | ||
2191 | /* Verify that print_dec (WI, ..., SGN) gives the expected string | |
2192 | representation (using base 10). */ | |
2193 | ||
2194 | static void | |
2195 | assert_deceq (const char *expected, const wide_int_ref &wi, signop sgn) | |
2196 | { | |
2197 | char buf[WIDE_INT_PRINT_BUFFER_SIZE]; | |
2198 | print_dec (wi, buf, sgn); | |
2199 | ASSERT_STREQ (expected, buf); | |
2200 | } | |
2201 | ||
2202 | /* Likewise for base 16. */ | |
2203 | ||
2204 | static void | |
2205 | assert_hexeq (const char *expected, const wide_int_ref &wi) | |
2206 | { | |
2207 | char buf[WIDE_INT_PRINT_BUFFER_SIZE]; | |
2208 | print_hex (wi, buf); | |
2209 | ASSERT_STREQ (expected, buf); | |
2210 | } | |
2211 | ||
2212 | /* Test cases. */ | |
2213 | ||
2214 | /* Verify that print_dec and print_hex work for VALUE_TYPE. */ | |
2215 | ||
2216 | template <class VALUE_TYPE> | |
2217 | static void | |
2218 | test_printing () | |
2219 | { | |
2220 | VALUE_TYPE a = from_int<VALUE_TYPE> (42); | |
2221 | assert_deceq ("42", a, SIGNED); | |
2222 | assert_hexeq ("0x2a", a); | |
2223 | } | |
2224 | ||
2225 | /* Verify that various operations work correctly for VALUE_TYPE, | |
2226 | unary and binary, using both function syntax, and | |
2227 | overloaded-operators. */ | |
2228 | ||
2229 | template <class VALUE_TYPE> | |
2230 | static void | |
2231 | test_ops () | |
2232 | { | |
2233 | VALUE_TYPE a = from_int<VALUE_TYPE> (7); | |
2234 | VALUE_TYPE b = from_int<VALUE_TYPE> (3); | |
2235 | ||
2236 | /* Using functions. */ | |
2237 | assert_deceq ("-7", wi::neg (a), SIGNED); | |
2238 | assert_deceq ("10", wi::add (a, b), SIGNED); | |
2239 | assert_deceq ("4", wi::sub (a, b), SIGNED); | |
2240 | assert_deceq ("-4", wi::sub (b, a), SIGNED); | |
2241 | assert_deceq ("21", wi::mul (a, b), SIGNED); | |
2242 | ||
2243 | /* Using operators. */ | |
2244 | assert_deceq ("-7", -a, SIGNED); | |
2245 | assert_deceq ("10", a + b, SIGNED); | |
2246 | assert_deceq ("4", a - b, SIGNED); | |
2247 | assert_deceq ("-4", b - a, SIGNED); | |
2248 | assert_deceq ("21", a * b, SIGNED); | |
2249 | } | |
2250 | ||
2251 | /* Verify that various comparisons work correctly for VALUE_TYPE. */ | |
2252 | ||
2253 | template <class VALUE_TYPE> | |
2254 | static void | |
2255 | test_comparisons () | |
2256 | { | |
2257 | VALUE_TYPE a = from_int<VALUE_TYPE> (7); | |
2258 | VALUE_TYPE b = from_int<VALUE_TYPE> (3); | |
2259 | ||
2260 | /* == */ | |
2261 | ASSERT_TRUE (wi::eq_p (a, a)); | |
2262 | ASSERT_FALSE (wi::eq_p (a, b)); | |
2263 | ||
2264 | /* != */ | |
2265 | ASSERT_TRUE (wi::ne_p (a, b)); | |
2266 | ASSERT_FALSE (wi::ne_p (a, a)); | |
2267 | ||
2268 | /* < */ | |
2269 | ASSERT_FALSE (wi::lts_p (a, a)); | |
2270 | ASSERT_FALSE (wi::lts_p (a, b)); | |
2271 | ASSERT_TRUE (wi::lts_p (b, a)); | |
2272 | ||
2273 | /* <= */ | |
2274 | ASSERT_TRUE (wi::les_p (a, a)); | |
2275 | ASSERT_FALSE (wi::les_p (a, b)); | |
2276 | ASSERT_TRUE (wi::les_p (b, a)); | |
2277 | ||
2278 | /* > */ | |
2279 | ASSERT_FALSE (wi::gts_p (a, a)); | |
2280 | ASSERT_TRUE (wi::gts_p (a, b)); | |
2281 | ASSERT_FALSE (wi::gts_p (b, a)); | |
2282 | ||
2283 | /* >= */ | |
2284 | ASSERT_TRUE (wi::ges_p (a, a)); | |
2285 | ASSERT_TRUE (wi::ges_p (a, b)); | |
2286 | ASSERT_FALSE (wi::ges_p (b, a)); | |
2287 | ||
2288 | /* comparison */ | |
2289 | ASSERT_EQ (-1, wi::cmps (b, a)); | |
2290 | ASSERT_EQ (0, wi::cmps (a, a)); | |
2291 | ASSERT_EQ (1, wi::cmps (a, b)); | |
2292 | } | |
2293 | ||
2294 | /* Run all of the selftests, using the given VALUE_TYPE. */ | |
2295 | ||
2296 | template <class VALUE_TYPE> | |
2297 | static void run_all_wide_int_tests () | |
2298 | { | |
2299 | test_printing <VALUE_TYPE> (); | |
2300 | test_ops <VALUE_TYPE> (); | |
2301 | test_comparisons <VALUE_TYPE> (); | |
2302 | } | |
2303 | ||
2304 | /* Run all of the selftests within this file, for all value types. */ | |
2305 | ||
2306 | void | |
2307 | wide_int_cc_tests () | |
2308 | { | |
2309 | run_all_wide_int_tests <wide_int> (); | |
2310 | run_all_wide_int_tests <offset_int> (); | |
2311 | run_all_wide_int_tests <widest_int> (); | |
2312 | } | |
2313 | ||
2314 | } // namespace selftest | |
2315 | #endif /* CHECKING_P */ |