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