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