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