|
131
|
1 /* Polynomial integer classes.
|
|
|
2 Copyright (C) 2014-2018 Free Software Foundation, Inc.
|
|
|
3
|
|
|
4 This file is part of GCC.
|
|
|
5
|
|
|
6 GCC is free software; you can redistribute it and/or modify it under
|
|
|
7 the terms of the GNU General Public License as published by the Free
|
|
|
8 Software Foundation; either version 3, or (at your option) any later
|
|
|
9 version.
|
|
|
10
|
|
|
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
|
|
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
14 for more details.
|
|
|
15
|
|
|
16 You should have received a copy of the GNU General Public License
|
|
|
17 along with GCC; see the file COPYING3. If not see
|
|
|
18 <http://www.gnu.org/licenses/>. */
|
|
|
19
|
|
|
20 /* This file provides a representation of sizes and offsets whose exact
|
|
|
21 values depend on certain runtime properties. The motivating example
|
|
|
22 is the Arm SVE ISA, in which the number of vector elements is only
|
|
|
23 known at runtime. See doc/poly-int.texi for more details.
|
|
|
24
|
|
|
25 Tests for poly-int.h are located in testsuite/gcc.dg/plugin,
|
|
|
26 since they are too expensive (in terms of binary size) to be
|
|
|
27 included as selftests. */
|
|
|
28
|
|
|
29 #ifndef HAVE_POLY_INT_H
|
|
|
30 #define HAVE_POLY_INT_H
|
|
|
31
|
|
|
32 template<unsigned int N, typename T> class poly_int_pod;
|
|
|
33 template<unsigned int N, typename T> class poly_int;
|
|
|
34
|
|
|
35 /* poly_coeff_traiits<T> describes the properties of a poly_int
|
|
|
36 coefficient type T:
|
|
|
37
|
|
|
38 - poly_coeff_traits<T1>::rank is less than poly_coeff_traits<T2>::rank
|
|
|
39 if T1 can promote to T2. For C-like types the rank is:
|
|
|
40
|
|
|
41 (2 * number of bytes) + (unsigned ? 1 : 0)
|
|
|
42
|
|
|
43 wide_ints don't have a normal rank and so use a value of INT_MAX.
|
|
|
44 Any fixed-width integer should be promoted to wide_int if possible
|
|
|
45 and lead to an error otherwise.
|
|
|
46
|
|
|
47 - poly_coeff_traits<T>::int_type is the type to which an integer
|
|
|
48 literal should be cast before comparing it with T.
|
|
|
49
|
|
|
50 - poly_coeff_traits<T>::precision is the number of bits that T can hold.
|
|
|
51
|
|
|
52 - poly_coeff_traits<T>::signedness is:
|
|
|
53 0 if T is unsigned
|
|
|
54 1 if T is signed
|
|
|
55 -1 if T has no inherent sign (as for wide_int).
|
|
|
56
|
|
|
57 - poly_coeff_traits<T>::max_value, if defined, is the maximum value of T.
|
|
|
58
|
|
|
59 - poly_coeff_traits<T>::result is a type that can hold results of
|
|
|
60 operations on T. This is different from T itself in cases where T
|
|
|
61 is the result of an accessor like wi::to_offset. */
|
|
|
62 template<typename T, wi::precision_type = wi::int_traits<T>::precision_type>
|
|
|
63 struct poly_coeff_traits;
|
|
|
64
|
|
|
65 template<typename T>
|
|
|
66 struct poly_coeff_traits<T, wi::FLEXIBLE_PRECISION>
|
|
|
67 {
|
|
|
68 typedef T result;
|
|
|
69 typedef T int_type;
|
|
|
70 static const int signedness = (T (0) >= T (-1));
|
|
|
71 static const int precision = sizeof (T) * CHAR_BIT;
|
|
|
72 static const T max_value = (signedness
|
|
|
73 ? ((T (1) << (precision - 2))
|
|
|
74 + ((T (1) << (precision - 2)) - 1))
|
|
|
75 : T (-1));
|
|
|
76 static const int rank = sizeof (T) * 2 + !signedness;
|
|
|
77 };
|
|
|
78
|
|
|
79 template<typename T>
|
|
|
80 struct poly_coeff_traits<T, wi::VAR_PRECISION>
|
|
|
81 {
|
|
|
82 typedef T result;
|
|
|
83 typedef int int_type;
|
|
|
84 static const int signedness = -1;
|
|
|
85 static const int precision = WIDE_INT_MAX_PRECISION;
|
|
|
86 static const int rank = INT_MAX;
|
|
|
87 };
|
|
|
88
|
|
|
89 template<typename T>
|
|
|
90 struct poly_coeff_traits<T, wi::CONST_PRECISION>
|
|
|
91 {
|
|
|
92 typedef WI_UNARY_RESULT (T) result;
|
|
|
93 typedef int int_type;
|
|
|
94 /* These types are always signed. */
|
|
|
95 static const int signedness = 1;
|
|
|
96 static const int precision = wi::int_traits<T>::precision;
|
|
|
97 static const int rank = precision * 2 / CHAR_BIT;
|
|
|
98 };
|
|
|
99
|
|
|
100 /* Information about a pair of coefficient types. */
|
|
|
101 template<typename T1, typename T2>
|
|
|
102 struct poly_coeff_pair_traits
|
|
|
103 {
|
|
|
104 /* True if T1 can represent all the values of T2.
|
|
|
105
|
|
|
106 Either:
|
|
|
107
|
|
|
108 - T1 should be a type with the same signedness as T2 and no less
|
|
|
109 precision. This allows things like int16_t -> int16_t and
|
|
|
110 uint32_t -> uint64_t.
|
|
|
111
|
|
|
112 - T1 should be signed, T2 should be unsigned, and T1 should be
|
|
|
113 wider than T2. This allows things like uint16_t -> int32_t.
|
|
|
114
|
|
|
115 This rules out cases in which T1 has less precision than T2 or where
|
|
|
116 the conversion would reinterpret the top bit. E.g. int16_t -> uint32_t
|
|
|
117 can be dangerous and should have an explicit cast if deliberate. */
|
|
|
118 static const bool lossless_p = (poly_coeff_traits<T1>::signedness
|
|
|
119 == poly_coeff_traits<T2>::signedness
|
|
|
120 ? (poly_coeff_traits<T1>::precision
|
|
|
121 >= poly_coeff_traits<T2>::precision)
|
|
|
122 : (poly_coeff_traits<T1>::signedness == 1
|
|
|
123 && poly_coeff_traits<T2>::signedness == 0
|
|
|
124 && (poly_coeff_traits<T1>::precision
|
|
|
125 > poly_coeff_traits<T2>::precision)));
|
|
|
126
|
|
|
127 /* 0 if T1 op T2 should promote to HOST_WIDE_INT,
|
|
|
128 1 if T1 op T2 should promote to unsigned HOST_WIDE_INT,
|
|
|
129 2 if T1 op T2 should use wide-int rules. */
|
|
|
130 #define RANK(X) poly_coeff_traits<X>::rank
|
|
|
131 static const int result_kind
|
|
|
132 = ((RANK (T1) <= RANK (HOST_WIDE_INT)
|
|
|
133 && RANK (T2) <= RANK (HOST_WIDE_INT))
|
|
|
134 ? 0
|
|
|
135 : (RANK (T1) <= RANK (unsigned HOST_WIDE_INT)
|
|
|
136 && RANK (T2) <= RANK (unsigned HOST_WIDE_INT))
|
|
|
137 ? 1 : 2);
|
|
|
138 #undef RANK
|
|
|
139 };
|
|
|
140
|
|
|
141 /* SFINAE class that makes T3 available as "type" if T2 can represent all the
|
|
|
142 values in T1. */
|
|
|
143 template<typename T1, typename T2, typename T3,
|
|
|
144 bool lossless_p = poly_coeff_pair_traits<T1, T2>::lossless_p>
|
|
|
145 struct if_lossless;
|
|
|
146 template<typename T1, typename T2, typename T3>
|
|
|
147 struct if_lossless<T1, T2, T3, true>
|
|
|
148 {
|
|
|
149 typedef T3 type;
|
|
|
150 };
|
|
|
151
|
|
|
152 /* poly_int_traits<T> describes an integer type T that might be polynomial
|
|
|
153 or non-polynomial:
|
|
|
154
|
|
|
155 - poly_int_traits<T>::is_poly is true if T is a poly_int-based type
|
|
|
156 and false otherwise.
|
|
|
157
|
|
|
158 - poly_int_traits<T>::num_coeffs gives the number of coefficients in T
|
|
|
159 if T is a poly_int and 1 otherwise.
|
|
|
160
|
|
|
161 - poly_int_traits<T>::coeff_type gives the coefficent type of T if T
|
|
|
162 is a poly_int and T itself otherwise
|
|
|
163
|
|
|
164 - poly_int_traits<T>::int_type is a shorthand for
|
|
|
165 typename poly_coeff_traits<coeff_type>::int_type. */
|
|
|
166 template<typename T>
|
|
|
167 struct poly_int_traits
|
|
|
168 {
|
|
|
169 static const bool is_poly = false;
|
|
|
170 static const unsigned int num_coeffs = 1;
|
|
|
171 typedef T coeff_type;
|
|
|
172 typedef typename poly_coeff_traits<T>::int_type int_type;
|
|
|
173 };
|
|
|
174 template<unsigned int N, typename C>
|
|
|
175 struct poly_int_traits<poly_int_pod<N, C> >
|
|
|
176 {
|
|
|
177 static const bool is_poly = true;
|
|
|
178 static const unsigned int num_coeffs = N;
|
|
|
179 typedef C coeff_type;
|
|
|
180 typedef typename poly_coeff_traits<C>::int_type int_type;
|
|
|
181 };
|
|
|
182 template<unsigned int N, typename C>
|
|
|
183 struct poly_int_traits<poly_int<N, C> > : poly_int_traits<poly_int_pod<N, C> >
|
|
|
184 {
|
|
|
185 };
|
|
|
186
|
|
|
187 /* SFINAE class that makes T2 available as "type" if T1 is a non-polynomial
|
|
|
188 type. */
|
|
|
189 template<typename T1, typename T2 = T1,
|
|
|
190 bool is_poly = poly_int_traits<T1>::is_poly>
|
|
|
191 struct if_nonpoly {};
|
|
|
192 template<typename T1, typename T2>
|
|
|
193 struct if_nonpoly<T1, T2, false>
|
|
|
194 {
|
|
|
195 typedef T2 type;
|
|
|
196 };
|
|
|
197
|
|
|
198 /* SFINAE class that makes T3 available as "type" if both T1 and T2 are
|
|
|
199 non-polynomial types. */
|
|
|
200 template<typename T1, typename T2, typename T3,
|
|
|
201 bool is_poly1 = poly_int_traits<T1>::is_poly,
|
|
|
202 bool is_poly2 = poly_int_traits<T2>::is_poly>
|
|
|
203 struct if_nonpoly2 {};
|
|
|
204 template<typename T1, typename T2, typename T3>
|
|
|
205 struct if_nonpoly2<T1, T2, T3, false, false>
|
|
|
206 {
|
|
|
207 typedef T3 type;
|
|
|
208 };
|
|
|
209
|
|
|
210 /* SFINAE class that makes T2 available as "type" if T1 is a polynomial
|
|
|
211 type. */
|
|
|
212 template<typename T1, typename T2 = T1,
|
|
|
213 bool is_poly = poly_int_traits<T1>::is_poly>
|
|
|
214 struct if_poly {};
|
|
|
215 template<typename T1, typename T2>
|
|
|
216 struct if_poly<T1, T2, true>
|
|
|
217 {
|
|
|
218 typedef T2 type;
|
|
|
219 };
|
|
|
220
|
|
|
221 /* poly_result<T1, T2> describes the result of an operation on two
|
|
|
222 types T1 and T2, where at least one of the types is polynomial:
|
|
|
223
|
|
|
224 - poly_result<T1, T2>::type gives the result type for the operation.
|
|
|
225 The intention is to provide normal C-like rules for integer ranks,
|
|
|
226 except that everything smaller than HOST_WIDE_INT promotes to
|
|
|
227 HOST_WIDE_INT.
|
|
|
228
|
|
|
229 - poly_result<T1, T2>::cast is the type to which an operand of type
|
|
|
230 T1 should be cast before doing the operation, to ensure that
|
|
|
231 the operation is done at the right precision. Casting to
|
|
|
232 poly_result<T1, T2>::type would also work, but casting to this
|
|
|
233 type is more efficient. */
|
|
|
234 template<typename T1, typename T2 = T1,
|
|
|
235 int result_kind = poly_coeff_pair_traits<T1, T2>::result_kind>
|
|
|
236 struct poly_result;
|
|
|
237
|
|
|
238 /* Promote pair to HOST_WIDE_INT. */
|
|
|
239 template<typename T1, typename T2>
|
|
|
240 struct poly_result<T1, T2, 0>
|
|
|
241 {
|
|
|
242 typedef HOST_WIDE_INT type;
|
|
|
243 /* T1 and T2 are primitive types, so cast values to T before operating
|
|
|
244 on them. */
|
|
|
245 typedef type cast;
|
|
|
246 };
|
|
|
247
|
|
|
248 /* Promote pair to unsigned HOST_WIDE_INT. */
|
|
|
249 template<typename T1, typename T2>
|
|
|
250 struct poly_result<T1, T2, 1>
|
|
|
251 {
|
|
|
252 typedef unsigned HOST_WIDE_INT type;
|
|
|
253 /* T1 and T2 are primitive types, so cast values to T before operating
|
|
|
254 on them. */
|
|
|
255 typedef type cast;
|
|
|
256 };
|
|
|
257
|
|
|
258 /* Use normal wide-int rules. */
|
|
|
259 template<typename T1, typename T2>
|
|
|
260 struct poly_result<T1, T2, 2>
|
|
|
261 {
|
|
|
262 typedef WI_BINARY_RESULT (T1, T2) type;
|
|
|
263 /* Don't cast values before operating on them; leave the wi:: routines
|
|
|
264 to handle promotion as necessary. */
|
|
|
265 typedef const T1 &cast;
|
|
|
266 };
|
|
|
267
|
|
|
268 /* The coefficient type for the result of a binary operation on two
|
|
|
269 poly_ints, the first of which has coefficients of type C1 and the
|
|
|
270 second of which has coefficients of type C2. */
|
|
|
271 #define POLY_POLY_COEFF(C1, C2) typename poly_result<C1, C2>::type
|
|
|
272
|
|
|
273 /* Enforce that T2 is non-polynomial and provide the cofficient type of
|
|
|
274 the result of a binary operation in which the first operand is a
|
|
|
275 poly_int with coefficients of type C1 and the second operand is
|
|
|
276 a constant of type T2. */
|
|
|
277 #define POLY_CONST_COEFF(C1, T2) \
|
|
|
278 POLY_POLY_COEFF (C1, typename if_nonpoly<T2>::type)
|
|
|
279
|
|
|
280 /* Likewise in reverse. */
|
|
|
281 #define CONST_POLY_COEFF(T1, C2) \
|
|
|
282 POLY_POLY_COEFF (typename if_nonpoly<T1>::type, C2)
|
|
|
283
|
|
|
284 /* The result type for a binary operation on poly_int<N, C1> and
|
|
|
285 poly_int<N, C2>. */
|
|
|
286 #define POLY_POLY_RESULT(N, C1, C2) poly_int<N, POLY_POLY_COEFF (C1, C2)>
|
|
|
287
|
|
|
288 /* Enforce that T2 is non-polynomial and provide the result type
|
|
|
289 for a binary operation on poly_int<N, C1> and T2. */
|
|
|
290 #define POLY_CONST_RESULT(N, C1, T2) poly_int<N, POLY_CONST_COEFF (C1, T2)>
|
|
|
291
|
|
|
292 /* Enforce that T1 is non-polynomial and provide the result type
|
|
|
293 for a binary operation on T1 and poly_int<N, C2>. */
|
|
|
294 #define CONST_POLY_RESULT(N, T1, C2) poly_int<N, CONST_POLY_COEFF (T1, C2)>
|
|
|
295
|
|
|
296 /* Enforce that T1 and T2 are non-polynomial and provide the result type
|
|
|
297 for a binary operation on T1 and T2. */
|
|
|
298 #define CONST_CONST_RESULT(N, T1, T2) \
|
|
|
299 POLY_POLY_COEFF (typename if_nonpoly<T1>::type, \
|
|
|
300 typename if_nonpoly<T2>::type)
|
|
|
301
|
|
|
302 /* The type to which a coefficient of type C1 should be cast before
|
|
|
303 using it in a binary operation with a coefficient of type C2. */
|
|
|
304 #define POLY_CAST(C1, C2) typename poly_result<C1, C2>::cast
|
|
|
305
|
|
|
306 /* Provide the coefficient type for the result of T1 op T2, where T1
|
|
|
307 and T2 can be polynomial or non-polynomial. */
|
|
|
308 #define POLY_BINARY_COEFF(T1, T2) \
|
|
|
309 typename poly_result<typename poly_int_traits<T1>::coeff_type, \
|
|
|
310 typename poly_int_traits<T2>::coeff_type>::type
|
|
|
311
|
|
|
312 /* The type to which an integer constant should be cast before
|
|
|
313 comparing it with T. */
|
|
|
314 #define POLY_INT_TYPE(T) typename poly_int_traits<T>::int_type
|
|
|
315
|
|
|
316 /* RES is a poly_int result that has coefficients of type C and that
|
|
|
317 is being built up a coefficient at a time. Set coefficient number I
|
|
|
318 to VALUE in the most efficient way possible.
|
|
|
319
|
|
|
320 For primitive C it is better to assign directly, since it avoids
|
|
|
321 any further calls and so is more efficient when the compiler is
|
|
|
322 built at -O0. But for wide-int based C it is better to construct
|
|
|
323 the value in-place. This means that calls out to a wide-int.cc
|
|
|
324 routine can take the address of RES rather than the address of
|
|
|
325 a temporary.
|
|
|
326
|
|
|
327 The dummy comparison against a null C * is just a way of checking
|
|
|
328 that C gives the right type. */
|
|
|
329 #define POLY_SET_COEFF(C, RES, I, VALUE) \
|
|
|
330 ((void) (&(RES).coeffs[0] == (C *) 0), \
|
|
|
331 wi::int_traits<C>::precision_type == wi::FLEXIBLE_PRECISION \
|
|
|
332 ? (void) ((RES).coeffs[I] = VALUE) \
|
|
|
333 : (void) ((RES).coeffs[I].~C (), new (&(RES).coeffs[I]) C (VALUE)))
|
|
|
334
|
|
|
335 /* A base POD class for polynomial integers. The polynomial has N
|
|
|
336 coefficients of type C. */
|
|
|
337 template<unsigned int N, typename C>
|
|
|
338 class poly_int_pod
|
|
|
339 {
|
|
|
340 public:
|
|
|
341 template<typename Ca>
|
|
|
342 poly_int_pod &operator = (const poly_int_pod<N, Ca> &);
|
|
|
343 template<typename Ca>
|
|
|
344 typename if_nonpoly<Ca, poly_int_pod>::type &operator = (const Ca &);
|
|
|
345
|
|
|
346 template<typename Ca>
|
|
|
347 poly_int_pod &operator += (const poly_int_pod<N, Ca> &);
|
|
|
348 template<typename Ca>
|
|
|
349 typename if_nonpoly<Ca, poly_int_pod>::type &operator += (const Ca &);
|
|
|
350
|
|
|
351 template<typename Ca>
|
|
|
352 poly_int_pod &operator -= (const poly_int_pod<N, Ca> &);
|
|
|
353 template<typename Ca>
|
|
|
354 typename if_nonpoly<Ca, poly_int_pod>::type &operator -= (const Ca &);
|
|
|
355
|
|
|
356 template<typename Ca>
|
|
|
357 typename if_nonpoly<Ca, poly_int_pod>::type &operator *= (const Ca &);
|
|
|
358
|
|
|
359 poly_int_pod &operator <<= (unsigned int);
|
|
|
360
|
|
|
361 bool is_constant () const;
|
|
|
362
|
|
|
363 template<typename T>
|
|
|
364 typename if_lossless<T, C, bool>::type is_constant (T *) const;
|
|
|
365
|
|
|
366 C to_constant () const;
|
|
|
367
|
|
|
368 template<typename Ca>
|
|
|
369 static poly_int<N, C> from (const poly_int_pod<N, Ca> &, unsigned int,
|
|
|
370 signop);
|
|
|
371 template<typename Ca>
|
|
|
372 static poly_int<N, C> from (const poly_int_pod<N, Ca> &, signop);
|
|
|
373
|
|
|
374 bool to_shwi (poly_int_pod<N, HOST_WIDE_INT> *) const;
|
|
|
375 bool to_uhwi (poly_int_pod<N, unsigned HOST_WIDE_INT> *) const;
|
|
|
376 poly_int<N, HOST_WIDE_INT> force_shwi () const;
|
|
|
377 poly_int<N, unsigned HOST_WIDE_INT> force_uhwi () const;
|
|
|
378
|
|
|
379 #if POLY_INT_CONVERSION
|
|
|
380 operator C () const;
|
|
|
381 #endif
|
|
|
382
|
|
|
383 C coeffs[N];
|
|
|
384 };
|
|
|
385
|
|
|
386 template<unsigned int N, typename C>
|
|
|
387 template<typename Ca>
|
|
|
388 inline poly_int_pod<N, C>&
|
|
|
389 poly_int_pod<N, C>::operator = (const poly_int_pod<N, Ca> &a)
|
|
|
390 {
|
|
|
391 for (unsigned int i = 0; i < N; i++)
|
|
|
392 POLY_SET_COEFF (C, *this, i, a.coeffs[i]);
|
|
|
393 return *this;
|
|
|
394 }
|
|
|
395
|
|
|
396 template<unsigned int N, typename C>
|
|
|
397 template<typename Ca>
|
|
|
398 inline typename if_nonpoly<Ca, poly_int_pod<N, C> >::type &
|
|
|
399 poly_int_pod<N, C>::operator = (const Ca &a)
|
|
|
400 {
|
|
|
401 POLY_SET_COEFF (C, *this, 0, a);
|
|
|
402 if (N >= 2)
|
|
|
403 for (unsigned int i = 1; i < N; i++)
|
|
|
404 POLY_SET_COEFF (C, *this, i, wi::ints_for<C>::zero (this->coeffs[0]));
|
|
|
405 return *this;
|
|
|
406 }
|
|
|
407
|
|
|
408 template<unsigned int N, typename C>
|
|
|
409 template<typename Ca>
|
|
|
410 inline poly_int_pod<N, C>&
|
|
|
411 poly_int_pod<N, C>::operator += (const poly_int_pod<N, Ca> &a)
|
|
|
412 {
|
|
|
413 for (unsigned int i = 0; i < N; i++)
|
|
|
414 this->coeffs[i] += a.coeffs[i];
|
|
|
415 return *this;
|
|
|
416 }
|
|
|
417
|
|
|
418 template<unsigned int N, typename C>
|
|
|
419 template<typename Ca>
|
|
|
420 inline typename if_nonpoly<Ca, poly_int_pod<N, C> >::type &
|
|
|
421 poly_int_pod<N, C>::operator += (const Ca &a)
|
|
|
422 {
|
|
|
423 this->coeffs[0] += a;
|
|
|
424 return *this;
|
|
|
425 }
|
|
|
426
|
|
|
427 template<unsigned int N, typename C>
|
|
|
428 template<typename Ca>
|
|
|
429 inline poly_int_pod<N, C>&
|
|
|
430 poly_int_pod<N, C>::operator -= (const poly_int_pod<N, Ca> &a)
|
|
|
431 {
|
|
|
432 for (unsigned int i = 0; i < N; i++)
|
|
|
433 this->coeffs[i] -= a.coeffs[i];
|
|
|
434 return *this;
|
|
|
435 }
|
|
|
436
|
|
|
437 template<unsigned int N, typename C>
|
|
|
438 template<typename Ca>
|
|
|
439 inline typename if_nonpoly<Ca, poly_int_pod<N, C> >::type &
|
|
|
440 poly_int_pod<N, C>::operator -= (const Ca &a)
|
|
|
441 {
|
|
|
442 this->coeffs[0] -= a;
|
|
|
443 return *this;
|
|
|
444 }
|
|
|
445
|
|
|
446 template<unsigned int N, typename C>
|
|
|
447 template<typename Ca>
|
|
|
448 inline typename if_nonpoly<Ca, poly_int_pod<N, C> >::type &
|
|
|
449 poly_int_pod<N, C>::operator *= (const Ca &a)
|
|
|
450 {
|
|
|
451 for (unsigned int i = 0; i < N; i++)
|
|
|
452 this->coeffs[i] *= a;
|
|
|
453 return *this;
|
|
|
454 }
|
|
|
455
|
|
|
456 template<unsigned int N, typename C>
|
|
|
457 inline poly_int_pod<N, C>&
|
|
|
458 poly_int_pod<N, C>::operator <<= (unsigned int a)
|
|
|
459 {
|
|
|
460 for (unsigned int i = 0; i < N; i++)
|
|
|
461 this->coeffs[i] <<= a;
|
|
|
462 return *this;
|
|
|
463 }
|
|
|
464
|
|
|
465 /* Return true if the polynomial value is a compile-time constant. */
|
|
|
466
|
|
|
467 template<unsigned int N, typename C>
|
|
|
468 inline bool
|
|
|
469 poly_int_pod<N, C>::is_constant () const
|
|
|
470 {
|
|
|
471 if (N >= 2)
|
|
|
472 for (unsigned int i = 1; i < N; i++)
|
|
|
473 if (this->coeffs[i] != 0)
|
|
|
474 return false;
|
|
|
475 return true;
|
|
|
476 }
|
|
|
477
|
|
|
478 /* Return true if the polynomial value is a compile-time constant,
|
|
|
479 storing its value in CONST_VALUE if so. */
|
|
|
480
|
|
|
481 template<unsigned int N, typename C>
|
|
|
482 template<typename T>
|
|
|
483 inline typename if_lossless<T, C, bool>::type
|
|
|
484 poly_int_pod<N, C>::is_constant (T *const_value) const
|
|
|
485 {
|
|
|
486 if (is_constant ())
|
|
|
487 {
|
|
|
488 *const_value = this->coeffs[0];
|
|
|
489 return true;
|
|
|
490 }
|
|
|
491 return false;
|
|
|
492 }
|
|
|
493
|
|
|
494 /* Return the value of a polynomial that is already known to be a
|
|
|
495 compile-time constant.
|
|
|
496
|
|
|
497 NOTE: When using this function, please add a comment above the call
|
|
|
498 explaining why we know the value is constant in that context. */
|
|
|
499
|
|
|
500 template<unsigned int N, typename C>
|
|
|
501 inline C
|
|
|
502 poly_int_pod<N, C>::to_constant () const
|
|
|
503 {
|
|
|
504 gcc_checking_assert (is_constant ());
|
|
|
505 return this->coeffs[0];
|
|
|
506 }
|
|
|
507
|
|
|
508 /* Convert X to a wide_int-based polynomial in which each coefficient
|
|
|
509 has BITSIZE bits. If X's coefficients are smaller than BITSIZE,
|
|
|
510 extend them according to SGN. */
|
|
|
511
|
|
|
512 template<unsigned int N, typename C>
|
|
|
513 template<typename Ca>
|
|
|
514 inline poly_int<N, C>
|
|
|
515 poly_int_pod<N, C>::from (const poly_int_pod<N, Ca> &a,
|
|
|
516 unsigned int bitsize, signop sgn)
|
|
|
517 {
|
|
|
518 poly_int<N, C> r;
|
|
|
519 for (unsigned int i = 0; i < N; i++)
|
|
|
520 POLY_SET_COEFF (C, r, i, C::from (a.coeffs[i], bitsize, sgn));
|
|
|
521 return r;
|
|
|
522 }
|
|
|
523
|
|
|
524 /* Convert X to a fixed_wide_int-based polynomial, extending according
|
|
|
525 to SGN. */
|
|
|
526
|
|
|
527 template<unsigned int N, typename C>
|
|
|
528 template<typename Ca>
|
|
|
529 inline poly_int<N, C>
|
|
|
530 poly_int_pod<N, C>::from (const poly_int_pod<N, Ca> &a, signop sgn)
|
|
|
531 {
|
|
|
532 poly_int<N, C> r;
|
|
|
533 for (unsigned int i = 0; i < N; i++)
|
|
|
534 POLY_SET_COEFF (C, r, i, C::from (a.coeffs[i], sgn));
|
|
|
535 return r;
|
|
|
536 }
|
|
|
537
|
|
|
538 /* Return true if the coefficients of this generic_wide_int-based
|
|
|
539 polynomial can be represented as signed HOST_WIDE_INTs without loss
|
|
|
540 of precision. Store the HOST_WIDE_INT representation in *R if so. */
|
|
|
541
|
|
|
542 template<unsigned int N, typename C>
|
|
|
543 inline bool
|
|
|
544 poly_int_pod<N, C>::to_shwi (poly_int_pod<N, HOST_WIDE_INT> *r) const
|
|
|
545 {
|
|
|
546 for (unsigned int i = 0; i < N; i++)
|
|
|
547 if (!wi::fits_shwi_p (this->coeffs[i]))
|
|
|
548 return false;
|
|
|
549 for (unsigned int i = 0; i < N; i++)
|
|
|
550 r->coeffs[i] = this->coeffs[i].to_shwi ();
|
|
|
551 return true;
|
|
|
552 }
|
|
|
553
|
|
|
554 /* Return true if the coefficients of this generic_wide_int-based
|
|
|
555 polynomial can be represented as unsigned HOST_WIDE_INTs without
|
|
|
556 loss of precision. Store the unsigned HOST_WIDE_INT representation
|
|
|
557 in *R if so. */
|
|
|
558
|
|
|
559 template<unsigned int N, typename C>
|
|
|
560 inline bool
|
|
|
561 poly_int_pod<N, C>::to_uhwi (poly_int_pod<N, unsigned HOST_WIDE_INT> *r) const
|
|
|
562 {
|
|
|
563 for (unsigned int i = 0; i < N; i++)
|
|
|
564 if (!wi::fits_uhwi_p (this->coeffs[i]))
|
|
|
565 return false;
|
|
|
566 for (unsigned int i = 0; i < N; i++)
|
|
|
567 r->coeffs[i] = this->coeffs[i].to_uhwi ();
|
|
|
568 return true;
|
|
|
569 }
|
|
|
570
|
|
|
571 /* Force a generic_wide_int-based constant to HOST_WIDE_INT precision,
|
|
|
572 truncating if necessary. */
|
|
|
573
|
|
|
574 template<unsigned int N, typename C>
|
|
|
575 inline poly_int<N, HOST_WIDE_INT>
|
|
|
576 poly_int_pod<N, C>::force_shwi () const
|
|
|
577 {
|
|
|
578 poly_int_pod<N, HOST_WIDE_INT> r;
|
|
|
579 for (unsigned int i = 0; i < N; i++)
|
|
|
580 r.coeffs[i] = this->coeffs[i].to_shwi ();
|
|
|
581 return r;
|
|
|
582 }
|
|
|
583
|
|
|
584 /* Force a generic_wide_int-based constant to unsigned HOST_WIDE_INT precision,
|
|
|
585 truncating if necessary. */
|
|
|
586
|
|
|
587 template<unsigned int N, typename C>
|
|
|
588 inline poly_int<N, unsigned HOST_WIDE_INT>
|
|
|
589 poly_int_pod<N, C>::force_uhwi () const
|
|
|
590 {
|
|
|
591 poly_int_pod<N, unsigned HOST_WIDE_INT> r;
|
|
|
592 for (unsigned int i = 0; i < N; i++)
|
|
|
593 r.coeffs[i] = this->coeffs[i].to_uhwi ();
|
|
|
594 return r;
|
|
|
595 }
|
|
|
596
|
|
|
597 #if POLY_INT_CONVERSION
|
|
|
598 /* Provide a conversion operator to constants. */
|
|
|
599
|
|
|
600 template<unsigned int N, typename C>
|
|
|
601 inline
|
|
|
602 poly_int_pod<N, C>::operator C () const
|
|
|
603 {
|
|
|
604 gcc_checking_assert (this->is_constant ());
|
|
|
605 return this->coeffs[0];
|
|
|
606 }
|
|
|
607 #endif
|
|
|
608
|
|
|
609 /* The main class for polynomial integers. The class provides
|
|
|
610 constructors that are necessarily missing from the POD base. */
|
|
|
611 template<unsigned int N, typename C>
|
|
|
612 class poly_int : public poly_int_pod<N, C>
|
|
|
613 {
|
|
|
614 public:
|
|
|
615 poly_int () {}
|
|
|
616
|
|
|
617 template<typename Ca>
|
|
|
618 poly_int (const poly_int<N, Ca> &);
|
|
|
619 template<typename Ca>
|
|
|
620 poly_int (const poly_int_pod<N, Ca> &);
|
|
|
621 template<typename C0>
|
|
|
622 poly_int (const C0 &);
|
|
|
623 template<typename C0, typename C1>
|
|
|
624 poly_int (const C0 &, const C1 &);
|
|
|
625
|
|
|
626 template<typename Ca>
|
|
|
627 poly_int &operator = (const poly_int_pod<N, Ca> &);
|
|
|
628 template<typename Ca>
|
|
|
629 typename if_nonpoly<Ca, poly_int>::type &operator = (const Ca &);
|
|
|
630
|
|
|
631 template<typename Ca>
|
|
|
632 poly_int &operator += (const poly_int_pod<N, Ca> &);
|
|
|
633 template<typename Ca>
|
|
|
634 typename if_nonpoly<Ca, poly_int>::type &operator += (const Ca &);
|
|
|
635
|
|
|
636 template<typename Ca>
|
|
|
637 poly_int &operator -= (const poly_int_pod<N, Ca> &);
|
|
|
638 template<typename Ca>
|
|
|
639 typename if_nonpoly<Ca, poly_int>::type &operator -= (const Ca &);
|
|
|
640
|
|
|
641 template<typename Ca>
|
|
|
642 typename if_nonpoly<Ca, poly_int>::type &operator *= (const Ca &);
|
|
|
643
|
|
|
644 poly_int &operator <<= (unsigned int);
|
|
|
645 };
|
|
|
646
|
|
|
647 template<unsigned int N, typename C>
|
|
|
648 template<typename Ca>
|
|
|
649 inline
|
|
|
650 poly_int<N, C>::poly_int (const poly_int<N, Ca> &a)
|
|
|
651 {
|
|
|
652 for (unsigned int i = 0; i < N; i++)
|
|
|
653 POLY_SET_COEFF (C, *this, i, a.coeffs[i]);
|
|
|
654 }
|
|
|
655
|
|
|
656 template<unsigned int N, typename C>
|
|
|
657 template<typename Ca>
|
|
|
658 inline
|
|
|
659 poly_int<N, C>::poly_int (const poly_int_pod<N, Ca> &a)
|
|
|
660 {
|
|
|
661 for (unsigned int i = 0; i < N; i++)
|
|
|
662 POLY_SET_COEFF (C, *this, i, a.coeffs[i]);
|
|
|
663 }
|
|
|
664
|
|
|
665 template<unsigned int N, typename C>
|
|
|
666 template<typename C0>
|
|
|
667 inline
|
|
|
668 poly_int<N, C>::poly_int (const C0 &c0)
|
|
|
669 {
|
|
|
670 POLY_SET_COEFF (C, *this, 0, c0);
|
|
|
671 for (unsigned int i = 1; i < N; i++)
|
|
|
672 POLY_SET_COEFF (C, *this, i, wi::ints_for<C>::zero (this->coeffs[0]));
|
|
|
673 }
|
|
|
674
|
|
|
675 template<unsigned int N, typename C>
|
|
|
676 template<typename C0, typename C1>
|
|
|
677 inline
|
|
|
678 poly_int<N, C>::poly_int (const C0 &c0, const C1 &c1)
|
|
|
679 {
|
|
|
680 STATIC_ASSERT (N >= 2);
|
|
|
681 POLY_SET_COEFF (C, *this, 0, c0);
|
|
|
682 POLY_SET_COEFF (C, *this, 1, c1);
|
|
|
683 for (unsigned int i = 2; i < N; i++)
|
|
|
684 POLY_SET_COEFF (C, *this, i, wi::ints_for<C>::zero (this->coeffs[0]));
|
|
|
685 }
|
|
|
686
|
|
|
687 template<unsigned int N, typename C>
|
|
|
688 template<typename Ca>
|
|
|
689 inline poly_int<N, C>&
|
|
|
690 poly_int<N, C>::operator = (const poly_int_pod<N, Ca> &a)
|
|
|
691 {
|
|
|
692 for (unsigned int i = 0; i < N; i++)
|
|
|
693 this->coeffs[i] = a.coeffs[i];
|
|
|
694 return *this;
|
|
|
695 }
|
|
|
696
|
|
|
697 template<unsigned int N, typename C>
|
|
|
698 template<typename Ca>
|
|
|
699 inline typename if_nonpoly<Ca, poly_int<N, C> >::type &
|
|
|
700 poly_int<N, C>::operator = (const Ca &a)
|
|
|
701 {
|
|
|
702 this->coeffs[0] = a;
|
|
|
703 if (N >= 2)
|
|
|
704 for (unsigned int i = 1; i < N; i++)
|
|
|
705 this->coeffs[i] = wi::ints_for<C>::zero (this->coeffs[0]);
|
|
|
706 return *this;
|
|
|
707 }
|
|
|
708
|
|
|
709 template<unsigned int N, typename C>
|
|
|
710 template<typename Ca>
|
|
|
711 inline poly_int<N, C>&
|
|
|
712 poly_int<N, C>::operator += (const poly_int_pod<N, Ca> &a)
|
|
|
713 {
|
|
|
714 for (unsigned int i = 0; i < N; i++)
|
|
|
715 this->coeffs[i] += a.coeffs[i];
|
|
|
716 return *this;
|
|
|
717 }
|
|
|
718
|
|
|
719 template<unsigned int N, typename C>
|
|
|
720 template<typename Ca>
|
|
|
721 inline typename if_nonpoly<Ca, poly_int<N, C> >::type &
|
|
|
722 poly_int<N, C>::operator += (const Ca &a)
|
|
|
723 {
|
|
|
724 this->coeffs[0] += a;
|
|
|
725 return *this;
|
|
|
726 }
|
|
|
727
|
|
|
728 template<unsigned int N, typename C>
|
|
|
729 template<typename Ca>
|
|
|
730 inline poly_int<N, C>&
|
|
|
731 poly_int<N, C>::operator -= (const poly_int_pod<N, Ca> &a)
|
|
|
732 {
|
|
|
733 for (unsigned int i = 0; i < N; i++)
|
|
|
734 this->coeffs[i] -= a.coeffs[i];
|
|
|
735 return *this;
|
|
|
736 }
|
|
|
737
|
|
|
738 template<unsigned int N, typename C>
|
|
|
739 template<typename Ca>
|
|
|
740 inline typename if_nonpoly<Ca, poly_int<N, C> >::type &
|
|
|
741 poly_int<N, C>::operator -= (const Ca &a)
|
|
|
742 {
|
|
|
743 this->coeffs[0] -= a;
|
|
|
744 return *this;
|
|
|
745 }
|
|
|
746
|
|
|
747 template<unsigned int N, typename C>
|
|
|
748 template<typename Ca>
|
|
|
749 inline typename if_nonpoly<Ca, poly_int<N, C> >::type &
|
|
|
750 poly_int<N, C>::operator *= (const Ca &a)
|
|
|
751 {
|
|
|
752 for (unsigned int i = 0; i < N; i++)
|
|
|
753 this->coeffs[i] *= a;
|
|
|
754 return *this;
|
|
|
755 }
|
|
|
756
|
|
|
757 template<unsigned int N, typename C>
|
|
|
758 inline poly_int<N, C>&
|
|
|
759 poly_int<N, C>::operator <<= (unsigned int a)
|
|
|
760 {
|
|
|
761 for (unsigned int i = 0; i < N; i++)
|
|
|
762 this->coeffs[i] <<= a;
|
|
|
763 return *this;
|
|
|
764 }
|
|
|
765
|
|
|
766 /* Return true if every coefficient of A is in the inclusive range [B, C]. */
|
|
|
767
|
|
|
768 template<typename Ca, typename Cb, typename Cc>
|
|
|
769 inline typename if_nonpoly<Ca, bool>::type
|
|
|
770 coeffs_in_range_p (const Ca &a, const Cb &b, const Cc &c)
|
|
|
771 {
|
|
|
772 return a >= b && a <= c;
|
|
|
773 }
|
|
|
774
|
|
|
775 template<unsigned int N, typename Ca, typename Cb, typename Cc>
|
|
|
776 inline typename if_nonpoly<Ca, bool>::type
|
|
|
777 coeffs_in_range_p (const poly_int_pod<N, Ca> &a, const Cb &b, const Cc &c)
|
|
|
778 {
|
|
|
779 for (unsigned int i = 0; i < N; i++)
|
|
|
780 if (a.coeffs[i] < b || a.coeffs[i] > c)
|
|
|
781 return false;
|
|
|
782 return true;
|
|
|
783 }
|
|
|
784
|
|
|
785 namespace wi {
|
|
|
786 /* Poly version of wi::shwi, with the same interface. */
|
|
|
787
|
|
|
788 template<unsigned int N>
|
|
|
789 inline poly_int<N, hwi_with_prec>
|
|
|
790 shwi (const poly_int_pod<N, HOST_WIDE_INT> &a, unsigned int precision)
|
|
|
791 {
|
|
|
792 poly_int<N, hwi_with_prec> r;
|
|
|
793 for (unsigned int i = 0; i < N; i++)
|
|
|
794 POLY_SET_COEFF (hwi_with_prec, r, i, wi::shwi (a.coeffs[i], precision));
|
|
|
795 return r;
|
|
|
796 }
|
|
|
797
|
|
|
798 /* Poly version of wi::uhwi, with the same interface. */
|
|
|
799
|
|
|
800 template<unsigned int N>
|
|
|
801 inline poly_int<N, hwi_with_prec>
|
|
|
802 uhwi (const poly_int_pod<N, unsigned HOST_WIDE_INT> &a, unsigned int precision)
|
|
|
803 {
|
|
|
804 poly_int<N, hwi_with_prec> r;
|
|
|
805 for (unsigned int i = 0; i < N; i++)
|
|
|
806 POLY_SET_COEFF (hwi_with_prec, r, i, wi::uhwi (a.coeffs[i], precision));
|
|
|
807 return r;
|
|
|
808 }
|
|
|
809
|
|
|
810 /* Poly version of wi::sext, with the same interface. */
|
|
|
811
|
|
|
812 template<unsigned int N, typename Ca>
|
|
|
813 inline POLY_POLY_RESULT (N, Ca, Ca)
|
|
|
814 sext (const poly_int_pod<N, Ca> &a, unsigned int precision)
|
|
|
815 {
|
|
|
816 typedef POLY_POLY_COEFF (Ca, Ca) C;
|
|
|
817 poly_int<N, C> r;
|
|
|
818 for (unsigned int i = 0; i < N; i++)
|
|
|
819 POLY_SET_COEFF (C, r, i, wi::sext (a.coeffs[i], precision));
|
|
|
820 return r;
|
|
|
821 }
|
|
|
822
|
|
|
823 /* Poly version of wi::zext, with the same interface. */
|
|
|
824
|
|
|
825 template<unsigned int N, typename Ca>
|
|
|
826 inline POLY_POLY_RESULT (N, Ca, Ca)
|
|
|
827 zext (const poly_int_pod<N, Ca> &a, unsigned int precision)
|
|
|
828 {
|
|
|
829 typedef POLY_POLY_COEFF (Ca, Ca) C;
|
|
|
830 poly_int<N, C> r;
|
|
|
831 for (unsigned int i = 0; i < N; i++)
|
|
|
832 POLY_SET_COEFF (C, r, i, wi::zext (a.coeffs[i], precision));
|
|
|
833 return r;
|
|
|
834 }
|
|
|
835 }
|
|
|
836
|
|
|
837 template<unsigned int N, typename Ca, typename Cb>
|
|
|
838 inline POLY_POLY_RESULT (N, Ca, Cb)
|
|
|
839 operator + (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
|
|
|
840 {
|
|
|
841 typedef POLY_CAST (Ca, Cb) NCa;
|
|
|
842 typedef POLY_POLY_COEFF (Ca, Cb) C;
|
|
|
843 poly_int<N, C> r;
|
|
|
844 for (unsigned int i = 0; i < N; i++)
|
|
|
845 POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) + b.coeffs[i]);
|
|
|
846 return r;
|
|
|
847 }
|
|
|
848
|
|
|
849 template<unsigned int N, typename Ca, typename Cb>
|
|
|
850 inline POLY_CONST_RESULT (N, Ca, Cb)
|
|
|
851 operator + (const poly_int_pod<N, Ca> &a, const Cb &b)
|
|
|
852 {
|
|
|
853 typedef POLY_CAST (Ca, Cb) NCa;
|
|
|
854 typedef POLY_CONST_COEFF (Ca, Cb) C;
|
|
|
855 poly_int<N, C> r;
|
|
|
856 POLY_SET_COEFF (C, r, 0, NCa (a.coeffs[0]) + b);
|
|
|
857 if (N >= 2)
|
|
|
858 for (unsigned int i = 1; i < N; i++)
|
|
|
859 POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]));
|
|
|
860 return r;
|
|
|
861 }
|
|
|
862
|
|
|
863 template<unsigned int N, typename Ca, typename Cb>
|
|
|
864 inline CONST_POLY_RESULT (N, Ca, Cb)
|
|
|
865 operator + (const Ca &a, const poly_int_pod<N, Cb> &b)
|
|
|
866 {
|
|
|
867 typedef POLY_CAST (Cb, Ca) NCb;
|
|
|
868 typedef CONST_POLY_COEFF (Ca, Cb) C;
|
|
|
869 poly_int<N, C> r;
|
|
|
870 POLY_SET_COEFF (C, r, 0, a + NCb (b.coeffs[0]));
|
|
|
871 if (N >= 2)
|
|
|
872 for (unsigned int i = 1; i < N; i++)
|
|
|
873 POLY_SET_COEFF (C, r, i, NCb (b.coeffs[i]));
|
|
|
874 return r;
|
|
|
875 }
|
|
|
876
|
|
|
877 namespace wi {
|
|
|
878 /* Poly versions of wi::add, with the same interface. */
|
|
|
879
|
|
|
880 template<unsigned int N, typename Ca, typename Cb>
|
|
|
881 inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
|
|
|
882 add (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
|
|
|
883 {
|
|
|
884 typedef WI_BINARY_RESULT (Ca, Cb) C;
|
|
|
885 poly_int<N, C> r;
|
|
|
886 for (unsigned int i = 0; i < N; i++)
|
|
|
887 POLY_SET_COEFF (C, r, i, wi::add (a.coeffs[i], b.coeffs[i]));
|
|
|
888 return r;
|
|
|
889 }
|
|
|
890
|
|
|
891 template<unsigned int N, typename Ca, typename Cb>
|
|
|
892 inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
|
|
|
893 add (const poly_int_pod<N, Ca> &a, const Cb &b)
|
|
|
894 {
|
|
|
895 typedef WI_BINARY_RESULT (Ca, Cb) C;
|
|
|
896 poly_int<N, C> r;
|
|
|
897 POLY_SET_COEFF (C, r, 0, wi::add (a.coeffs[0], b));
|
|
|
898 for (unsigned int i = 1; i < N; i++)
|
|
|
899 POLY_SET_COEFF (C, r, i, wi::add (a.coeffs[i],
|
|
|
900 wi::ints_for<Cb>::zero (b)));
|
|
|
901 return r;
|
|
|
902 }
|
|
|
903
|
|
|
904 template<unsigned int N, typename Ca, typename Cb>
|
|
|
905 inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
|
|
|
906 add (const Ca &a, const poly_int_pod<N, Cb> &b)
|
|
|
907 {
|
|
|
908 typedef WI_BINARY_RESULT (Ca, Cb) C;
|
|
|
909 poly_int<N, C> r;
|
|
|
910 POLY_SET_COEFF (C, r, 0, wi::add (a, b.coeffs[0]));
|
|
|
911 for (unsigned int i = 1; i < N; i++)
|
|
|
912 POLY_SET_COEFF (C, r, i, wi::add (wi::ints_for<Ca>::zero (a),
|
|
|
913 b.coeffs[i]));
|
|
|
914 return r;
|
|
|
915 }
|
|
|
916
|
|
|
917 template<unsigned int N, typename Ca, typename Cb>
|
|
|
918 inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
|
|
|
919 add (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b,
|
|
|
920 signop sgn, wi::overflow_type *overflow)
|
|
|
921 {
|
|
|
922 typedef WI_BINARY_RESULT (Ca, Cb) C;
|
|
|
923 poly_int<N, C> r;
|
|
|
924 POLY_SET_COEFF (C, r, 0, wi::add (a.coeffs[0], b.coeffs[0], sgn, overflow));
|
|
|
925 for (unsigned int i = 1; i < N; i++)
|
|
|
926 {
|
|
|
927 wi::overflow_type suboverflow;
|
|
|
928 POLY_SET_COEFF (C, r, i, wi::add (a.coeffs[i], b.coeffs[i], sgn,
|
|
|
929 &suboverflow));
|
|
|
930 wi::accumulate_overflow (*overflow, suboverflow);
|
|
|
931 }
|
|
|
932 return r;
|
|
|
933 }
|
|
|
934 }
|
|
|
935
|
|
|
936 template<unsigned int N, typename Ca, typename Cb>
|
|
|
937 inline POLY_POLY_RESULT (N, Ca, Cb)
|
|
|
938 operator - (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
|
|
|
939 {
|
|
|
940 typedef POLY_CAST (Ca, Cb) NCa;
|
|
|
941 typedef POLY_POLY_COEFF (Ca, Cb) C;
|
|
|
942 poly_int<N, C> r;
|
|
|
943 for (unsigned int i = 0; i < N; i++)
|
|
|
944 POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) - b.coeffs[i]);
|
|
|
945 return r;
|
|
|
946 }
|
|
|
947
|
|
|
948 template<unsigned int N, typename Ca, typename Cb>
|
|
|
949 inline POLY_CONST_RESULT (N, Ca, Cb)
|
|
|
950 operator - (const poly_int_pod<N, Ca> &a, const Cb &b)
|
|
|
951 {
|
|
|
952 typedef POLY_CAST (Ca, Cb) NCa;
|
|
|
953 typedef POLY_CONST_COEFF (Ca, Cb) C;
|
|
|
954 poly_int<N, C> r;
|
|
|
955 POLY_SET_COEFF (C, r, 0, NCa (a.coeffs[0]) - b);
|
|
|
956 if (N >= 2)
|
|
|
957 for (unsigned int i = 1; i < N; i++)
|
|
|
958 POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]));
|
|
|
959 return r;
|
|
|
960 }
|
|
|
961
|
|
|
962 template<unsigned int N, typename Ca, typename Cb>
|
|
|
963 inline CONST_POLY_RESULT (N, Ca, Cb)
|
|
|
964 operator - (const Ca &a, const poly_int_pod<N, Cb> &b)
|
|
|
965 {
|
|
|
966 typedef POLY_CAST (Cb, Ca) NCb;
|
|
|
967 typedef CONST_POLY_COEFF (Ca, Cb) C;
|
|
|
968 poly_int<N, C> r;
|
|
|
969 POLY_SET_COEFF (C, r, 0, a - NCb (b.coeffs[0]));
|
|
|
970 if (N >= 2)
|
|
|
971 for (unsigned int i = 1; i < N; i++)
|
|
|
972 POLY_SET_COEFF (C, r, i, -NCb (b.coeffs[i]));
|
|
|
973 return r;
|
|
|
974 }
|
|
|
975
|
|
|
976 namespace wi {
|
|
|
977 /* Poly versions of wi::sub, with the same interface. */
|
|
|
978
|
|
|
979 template<unsigned int N, typename Ca, typename Cb>
|
|
|
980 inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
|
|
|
981 sub (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
|
|
|
982 {
|
|
|
983 typedef WI_BINARY_RESULT (Ca, Cb) C;
|
|
|
984 poly_int<N, C> r;
|
|
|
985 for (unsigned int i = 0; i < N; i++)
|
|
|
986 POLY_SET_COEFF (C, r, i, wi::sub (a.coeffs[i], b.coeffs[i]));
|
|
|
987 return r;
|
|
|
988 }
|
|
|
989
|
|
|
990 template<unsigned int N, typename Ca, typename Cb>
|
|
|
991 inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
|
|
|
992 sub (const poly_int_pod<N, Ca> &a, const Cb &b)
|
|
|
993 {
|
|
|
994 typedef WI_BINARY_RESULT (Ca, Cb) C;
|
|
|
995 poly_int<N, C> r;
|
|
|
996 POLY_SET_COEFF (C, r, 0, wi::sub (a.coeffs[0], b));
|
|
|
997 for (unsigned int i = 1; i < N; i++)
|
|
|
998 POLY_SET_COEFF (C, r, i, wi::sub (a.coeffs[i],
|
|
|
999 wi::ints_for<Cb>::zero (b)));
|
|
|
1000 return r;
|
|
|
1001 }
|
|
|
1002
|
|
|
1003 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1004 inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
|
|
|
1005 sub (const Ca &a, const poly_int_pod<N, Cb> &b)
|
|
|
1006 {
|
|
|
1007 typedef WI_BINARY_RESULT (Ca, Cb) C;
|
|
|
1008 poly_int<N, C> r;
|
|
|
1009 POLY_SET_COEFF (C, r, 0, wi::sub (a, b.coeffs[0]));
|
|
|
1010 for (unsigned int i = 1; i < N; i++)
|
|
|
1011 POLY_SET_COEFF (C, r, i, wi::sub (wi::ints_for<Ca>::zero (a),
|
|
|
1012 b.coeffs[i]));
|
|
|
1013 return r;
|
|
|
1014 }
|
|
|
1015
|
|
|
1016 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1017 inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
|
|
|
1018 sub (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b,
|
|
|
1019 signop sgn, wi::overflow_type *overflow)
|
|
|
1020 {
|
|
|
1021 typedef WI_BINARY_RESULT (Ca, Cb) C;
|
|
|
1022 poly_int<N, C> r;
|
|
|
1023 POLY_SET_COEFF (C, r, 0, wi::sub (a.coeffs[0], b.coeffs[0], sgn, overflow));
|
|
|
1024 for (unsigned int i = 1; i < N; i++)
|
|
|
1025 {
|
|
|
1026 wi::overflow_type suboverflow;
|
|
|
1027 POLY_SET_COEFF (C, r, i, wi::sub (a.coeffs[i], b.coeffs[i], sgn,
|
|
|
1028 &suboverflow));
|
|
|
1029 wi::accumulate_overflow (*overflow, suboverflow);
|
|
|
1030 }
|
|
|
1031 return r;
|
|
|
1032 }
|
|
|
1033 }
|
|
|
1034
|
|
|
1035 template<unsigned int N, typename Ca>
|
|
|
1036 inline POLY_POLY_RESULT (N, Ca, Ca)
|
|
|
1037 operator - (const poly_int_pod<N, Ca> &a)
|
|
|
1038 {
|
|
|
1039 typedef POLY_CAST (Ca, Ca) NCa;
|
|
|
1040 typedef POLY_POLY_COEFF (Ca, Ca) C;
|
|
|
1041 poly_int<N, C> r;
|
|
|
1042 for (unsigned int i = 0; i < N; i++)
|
|
|
1043 POLY_SET_COEFF (C, r, i, -NCa (a.coeffs[i]));
|
|
|
1044 return r;
|
|
|
1045 }
|
|
|
1046
|
|
|
1047 namespace wi {
|
|
|
1048 /* Poly version of wi::neg, with the same interface. */
|
|
|
1049
|
|
|
1050 template<unsigned int N, typename Ca>
|
|
|
1051 inline poly_int<N, WI_UNARY_RESULT (Ca)>
|
|
|
1052 neg (const poly_int_pod<N, Ca> &a)
|
|
|
1053 {
|
|
|
1054 typedef WI_UNARY_RESULT (Ca) C;
|
|
|
1055 poly_int<N, C> r;
|
|
|
1056 for (unsigned int i = 0; i < N; i++)
|
|
|
1057 POLY_SET_COEFF (C, r, i, wi::neg (a.coeffs[i]));
|
|
|
1058 return r;
|
|
|
1059 }
|
|
|
1060
|
|
|
1061 template<unsigned int N, typename Ca>
|
|
|
1062 inline poly_int<N, WI_UNARY_RESULT (Ca)>
|
|
|
1063 neg (const poly_int_pod<N, Ca> &a, wi::overflow_type *overflow)
|
|
|
1064 {
|
|
|
1065 typedef WI_UNARY_RESULT (Ca) C;
|
|
|
1066 poly_int<N, C> r;
|
|
|
1067 POLY_SET_COEFF (C, r, 0, wi::neg (a.coeffs[0], overflow));
|
|
|
1068 for (unsigned int i = 1; i < N; i++)
|
|
|
1069 {
|
|
|
1070 wi::overflow_type suboverflow;
|
|
|
1071 POLY_SET_COEFF (C, r, i, wi::neg (a.coeffs[i], &suboverflow));
|
|
|
1072 wi::accumulate_overflow (*overflow, suboverflow);
|
|
|
1073 }
|
|
|
1074 return r;
|
|
|
1075 }
|
|
|
1076 }
|
|
|
1077
|
|
|
1078 template<unsigned int N, typename Ca>
|
|
|
1079 inline POLY_POLY_RESULT (N, Ca, Ca)
|
|
|
1080 operator ~ (const poly_int_pod<N, Ca> &a)
|
|
|
1081 {
|
|
|
1082 if (N >= 2)
|
|
|
1083 return -1 - a;
|
|
|
1084 return ~a.coeffs[0];
|
|
|
1085 }
|
|
|
1086
|
|
|
1087 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1088 inline POLY_CONST_RESULT (N, Ca, Cb)
|
|
|
1089 operator * (const poly_int_pod<N, Ca> &a, const Cb &b)
|
|
|
1090 {
|
|
|
1091 typedef POLY_CAST (Ca, Cb) NCa;
|
|
|
1092 typedef POLY_CONST_COEFF (Ca, Cb) C;
|
|
|
1093 poly_int<N, C> r;
|
|
|
1094 for (unsigned int i = 0; i < N; i++)
|
|
|
1095 POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) * b);
|
|
|
1096 return r;
|
|
|
1097 }
|
|
|
1098
|
|
|
1099 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1100 inline CONST_POLY_RESULT (N, Ca, Cb)
|
|
|
1101 operator * (const Ca &a, const poly_int_pod<N, Cb> &b)
|
|
|
1102 {
|
|
|
1103 typedef POLY_CAST (Ca, Cb) NCa;
|
|
|
1104 typedef CONST_POLY_COEFF (Ca, Cb) C;
|
|
|
1105 poly_int<N, C> r;
|
|
|
1106 for (unsigned int i = 0; i < N; i++)
|
|
|
1107 POLY_SET_COEFF (C, r, i, NCa (a) * b.coeffs[i]);
|
|
|
1108 return r;
|
|
|
1109 }
|
|
|
1110
|
|
|
1111 namespace wi {
|
|
|
1112 /* Poly versions of wi::mul, with the same interface. */
|
|
|
1113
|
|
|
1114 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1115 inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
|
|
|
1116 mul (const poly_int_pod<N, Ca> &a, const Cb &b)
|
|
|
1117 {
|
|
|
1118 typedef WI_BINARY_RESULT (Ca, Cb) C;
|
|
|
1119 poly_int<N, C> r;
|
|
|
1120 for (unsigned int i = 0; i < N; i++)
|
|
|
1121 POLY_SET_COEFF (C, r, i, wi::mul (a.coeffs[i], b));
|
|
|
1122 return r;
|
|
|
1123 }
|
|
|
1124
|
|
|
1125 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1126 inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
|
|
|
1127 mul (const Ca &a, const poly_int_pod<N, Cb> &b)
|
|
|
1128 {
|
|
|
1129 typedef WI_BINARY_RESULT (Ca, Cb) C;
|
|
|
1130 poly_int<N, C> r;
|
|
|
1131 for (unsigned int i = 0; i < N; i++)
|
|
|
1132 POLY_SET_COEFF (C, r, i, wi::mul (a, b.coeffs[i]));
|
|
|
1133 return r;
|
|
|
1134 }
|
|
|
1135
|
|
|
1136 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1137 inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
|
|
|
1138 mul (const poly_int_pod<N, Ca> &a, const Cb &b,
|
|
|
1139 signop sgn, wi::overflow_type *overflow)
|
|
|
1140 {
|
|
|
1141 typedef WI_BINARY_RESULT (Ca, Cb) C;
|
|
|
1142 poly_int<N, C> r;
|
|
|
1143 POLY_SET_COEFF (C, r, 0, wi::mul (a.coeffs[0], b, sgn, overflow));
|
|
|
1144 for (unsigned int i = 1; i < N; i++)
|
|
|
1145 {
|
|
|
1146 wi::overflow_type suboverflow;
|
|
|
1147 POLY_SET_COEFF (C, r, i, wi::mul (a.coeffs[i], b, sgn, &suboverflow));
|
|
|
1148 wi::accumulate_overflow (*overflow, suboverflow);
|
|
|
1149 }
|
|
|
1150 return r;
|
|
|
1151 }
|
|
|
1152 }
|
|
|
1153
|
|
|
1154 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1155 inline POLY_POLY_RESULT (N, Ca, Ca)
|
|
|
1156 operator << (const poly_int_pod<N, Ca> &a, const Cb &b)
|
|
|
1157 {
|
|
|
1158 typedef POLY_CAST (Ca, Ca) NCa;
|
|
|
1159 typedef POLY_POLY_COEFF (Ca, Ca) C;
|
|
|
1160 poly_int<N, C> r;
|
|
|
1161 for (unsigned int i = 0; i < N; i++)
|
|
|
1162 POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) << b);
|
|
|
1163 return r;
|
|
|
1164 }
|
|
|
1165
|
|
|
1166 namespace wi {
|
|
|
1167 /* Poly version of wi::lshift, with the same interface. */
|
|
|
1168
|
|
|
1169 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1170 inline poly_int<N, WI_BINARY_RESULT (Ca, Ca)>
|
|
|
1171 lshift (const poly_int_pod<N, Ca> &a, const Cb &b)
|
|
|
1172 {
|
|
|
1173 typedef WI_BINARY_RESULT (Ca, Ca) C;
|
|
|
1174 poly_int<N, C> r;
|
|
|
1175 for (unsigned int i = 0; i < N; i++)
|
|
|
1176 POLY_SET_COEFF (C, r, i, wi::lshift (a.coeffs[i], b));
|
|
|
1177 return r;
|
|
|
1178 }
|
|
|
1179 }
|
|
|
1180
|
|
|
1181 /* Return true if a0 + a1 * x might equal b0 + b1 * x for some nonnegative
|
|
|
1182 integer x. */
|
|
|
1183
|
|
|
1184 template<typename Ca, typename Cb>
|
|
|
1185 inline bool
|
|
|
1186 maybe_eq_2 (const Ca &a0, const Ca &a1, const Cb &b0, const Cb &b1)
|
|
|
1187 {
|
|
|
1188 if (a1 != b1)
|
|
|
1189 /* a0 + a1 * x == b0 + b1 * x
|
|
|
1190 ==> (a1 - b1) * x == b0 - a0
|
|
|
1191 ==> x == (b0 - a0) / (a1 - b1)
|
|
|
1192
|
|
|
1193 We need to test whether that's a valid value of x.
|
|
|
1194 (b0 - a0) and (a1 - b1) must not have opposite signs
|
|
|
1195 and the result must be integral. */
|
|
|
1196 return (a1 < b1
|
|
|
1197 ? b0 <= a0 && (a0 - b0) % (b1 - a1) == 0
|
|
|
1198 : b0 >= a0 && (b0 - a0) % (a1 - b1) == 0);
|
|
|
1199 return a0 == b0;
|
|
|
1200 }
|
|
|
1201
|
|
|
1202 /* Return true if a0 + a1 * x might equal b for some nonnegative
|
|
|
1203 integer x. */
|
|
|
1204
|
|
|
1205 template<typename Ca, typename Cb>
|
|
|
1206 inline bool
|
|
|
1207 maybe_eq_2 (const Ca &a0, const Ca &a1, const Cb &b)
|
|
|
1208 {
|
|
|
1209 if (a1 != 0)
|
|
|
1210 /* a0 + a1 * x == b
|
|
|
1211 ==> x == (b - a0) / a1
|
|
|
1212
|
|
|
1213 We need to test whether that's a valid value of x.
|
|
|
1214 (b - a0) and a1 must not have opposite signs and the
|
|
|
1215 result must be integral. */
|
|
|
1216 return (a1 < 0
|
|
|
1217 ? b <= a0 && (a0 - b) % a1 == 0
|
|
|
1218 : b >= a0 && (b - a0) % a1 == 0);
|
|
|
1219 return a0 == b;
|
|
|
1220 }
|
|
|
1221
|
|
|
1222 /* Return true if A might equal B for some indeterminate values. */
|
|
|
1223
|
|
|
1224 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1225 inline bool
|
|
|
1226 maybe_eq (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
|
|
|
1227 {
|
|
|
1228 STATIC_ASSERT (N <= 2);
|
|
|
1229 if (N == 2)
|
|
|
1230 return maybe_eq_2 (a.coeffs[0], a.coeffs[1], b.coeffs[0], b.coeffs[1]);
|
|
|
1231 return a.coeffs[0] == b.coeffs[0];
|
|
|
1232 }
|
|
|
1233
|
|
|
1234 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1235 inline typename if_nonpoly<Cb, bool>::type
|
|
|
1236 maybe_eq (const poly_int_pod<N, Ca> &a, const Cb &b)
|
|
|
1237 {
|
|
|
1238 STATIC_ASSERT (N <= 2);
|
|
|
1239 if (N == 2)
|
|
|
1240 return maybe_eq_2 (a.coeffs[0], a.coeffs[1], b);
|
|
|
1241 return a.coeffs[0] == b;
|
|
|
1242 }
|
|
|
1243
|
|
|
1244 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1245 inline typename if_nonpoly<Ca, bool>::type
|
|
|
1246 maybe_eq (const Ca &a, const poly_int_pod<N, Cb> &b)
|
|
|
1247 {
|
|
|
1248 STATIC_ASSERT (N <= 2);
|
|
|
1249 if (N == 2)
|
|
|
1250 return maybe_eq_2 (b.coeffs[0], b.coeffs[1], a);
|
|
|
1251 return a == b.coeffs[0];
|
|
|
1252 }
|
|
|
1253
|
|
|
1254 template<typename Ca, typename Cb>
|
|
|
1255 inline typename if_nonpoly2<Ca, Cb, bool>::type
|
|
|
1256 maybe_eq (const Ca &a, const Cb &b)
|
|
|
1257 {
|
|
|
1258 return a == b;
|
|
|
1259 }
|
|
|
1260
|
|
|
1261 /* Return true if A might not equal B for some indeterminate values. */
|
|
|
1262
|
|
|
1263 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1264 inline bool
|
|
|
1265 maybe_ne (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
|
|
|
1266 {
|
|
|
1267 if (N >= 2)
|
|
|
1268 for (unsigned int i = 1; i < N; i++)
|
|
|
1269 if (a.coeffs[i] != b.coeffs[i])
|
|
|
1270 return true;
|
|
|
1271 return a.coeffs[0] != b.coeffs[0];
|
|
|
1272 }
|
|
|
1273
|
|
|
1274 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1275 inline typename if_nonpoly<Cb, bool>::type
|
|
|
1276 maybe_ne (const poly_int_pod<N, Ca> &a, const Cb &b)
|
|
|
1277 {
|
|
|
1278 if (N >= 2)
|
|
|
1279 for (unsigned int i = 1; i < N; i++)
|
|
|
1280 if (a.coeffs[i] != 0)
|
|
|
1281 return true;
|
|
|
1282 return a.coeffs[0] != b;
|
|
|
1283 }
|
|
|
1284
|
|
|
1285 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1286 inline typename if_nonpoly<Ca, bool>::type
|
|
|
1287 maybe_ne (const Ca &a, const poly_int_pod<N, Cb> &b)
|
|
|
1288 {
|
|
|
1289 if (N >= 2)
|
|
|
1290 for (unsigned int i = 1; i < N; i++)
|
|
|
1291 if (b.coeffs[i] != 0)
|
|
|
1292 return true;
|
|
|
1293 return a != b.coeffs[0];
|
|
|
1294 }
|
|
|
1295
|
|
|
1296 template<typename Ca, typename Cb>
|
|
|
1297 inline typename if_nonpoly2<Ca, Cb, bool>::type
|
|
|
1298 maybe_ne (const Ca &a, const Cb &b)
|
|
|
1299 {
|
|
|
1300 return a != b;
|
|
|
1301 }
|
|
|
1302
|
|
|
1303 /* Return true if A is known to be equal to B. */
|
|
|
1304 #define known_eq(A, B) (!maybe_ne (A, B))
|
|
|
1305
|
|
|
1306 /* Return true if A is known to be unequal to B. */
|
|
|
1307 #define known_ne(A, B) (!maybe_eq (A, B))
|
|
|
1308
|
|
|
1309 /* Return true if A might be less than or equal to B for some
|
|
|
1310 indeterminate values. */
|
|
|
1311
|
|
|
1312 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1313 inline bool
|
|
|
1314 maybe_le (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
|
|
|
1315 {
|
|
|
1316 if (N >= 2)
|
|
|
1317 for (unsigned int i = 1; i < N; i++)
|
|
|
1318 if (a.coeffs[i] < b.coeffs[i])
|
|
|
1319 return true;
|
|
|
1320 return a.coeffs[0] <= b.coeffs[0];
|
|
|
1321 }
|
|
|
1322
|
|
|
1323 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1324 inline typename if_nonpoly<Cb, bool>::type
|
|
|
1325 maybe_le (const poly_int_pod<N, Ca> &a, const Cb &b)
|
|
|
1326 {
|
|
|
1327 if (N >= 2)
|
|
|
1328 for (unsigned int i = 1; i < N; i++)
|
|
|
1329 if (a.coeffs[i] < 0)
|
|
|
1330 return true;
|
|
|
1331 return a.coeffs[0] <= b;
|
|
|
1332 }
|
|
|
1333
|
|
|
1334 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1335 inline typename if_nonpoly<Ca, bool>::type
|
|
|
1336 maybe_le (const Ca &a, const poly_int_pod<N, Cb> &b)
|
|
|
1337 {
|
|
|
1338 if (N >= 2)
|
|
|
1339 for (unsigned int i = 1; i < N; i++)
|
|
|
1340 if (b.coeffs[i] > 0)
|
|
|
1341 return true;
|
|
|
1342 return a <= b.coeffs[0];
|
|
|
1343 }
|
|
|
1344
|
|
|
1345 template<typename Ca, typename Cb>
|
|
|
1346 inline typename if_nonpoly2<Ca, Cb, bool>::type
|
|
|
1347 maybe_le (const Ca &a, const Cb &b)
|
|
|
1348 {
|
|
|
1349 return a <= b;
|
|
|
1350 }
|
|
|
1351
|
|
|
1352 /* Return true if A might be less than B for some indeterminate values. */
|
|
|
1353
|
|
|
1354 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1355 inline bool
|
|
|
1356 maybe_lt (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
|
|
|
1357 {
|
|
|
1358 if (N >= 2)
|
|
|
1359 for (unsigned int i = 1; i < N; i++)
|
|
|
1360 if (a.coeffs[i] < b.coeffs[i])
|
|
|
1361 return true;
|
|
|
1362 return a.coeffs[0] < b.coeffs[0];
|
|
|
1363 }
|
|
|
1364
|
|
|
1365 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1366 inline typename if_nonpoly<Cb, bool>::type
|
|
|
1367 maybe_lt (const poly_int_pod<N, Ca> &a, const Cb &b)
|
|
|
1368 {
|
|
|
1369 if (N >= 2)
|
|
|
1370 for (unsigned int i = 1; i < N; i++)
|
|
|
1371 if (a.coeffs[i] < 0)
|
|
|
1372 return true;
|
|
|
1373 return a.coeffs[0] < b;
|
|
|
1374 }
|
|
|
1375
|
|
|
1376 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1377 inline typename if_nonpoly<Ca, bool>::type
|
|
|
1378 maybe_lt (const Ca &a, const poly_int_pod<N, Cb> &b)
|
|
|
1379 {
|
|
|
1380 if (N >= 2)
|
|
|
1381 for (unsigned int i = 1; i < N; i++)
|
|
|
1382 if (b.coeffs[i] > 0)
|
|
|
1383 return true;
|
|
|
1384 return a < b.coeffs[0];
|
|
|
1385 }
|
|
|
1386
|
|
|
1387 template<typename Ca, typename Cb>
|
|
|
1388 inline typename if_nonpoly2<Ca, Cb, bool>::type
|
|
|
1389 maybe_lt (const Ca &a, const Cb &b)
|
|
|
1390 {
|
|
|
1391 return a < b;
|
|
|
1392 }
|
|
|
1393
|
|
|
1394 /* Return true if A may be greater than or equal to B. */
|
|
|
1395 #define maybe_ge(A, B) maybe_le (B, A)
|
|
|
1396
|
|
|
1397 /* Return true if A may be greater than B. */
|
|
|
1398 #define maybe_gt(A, B) maybe_lt (B, A)
|
|
|
1399
|
|
|
1400 /* Return true if A is known to be less than or equal to B. */
|
|
|
1401 #define known_le(A, B) (!maybe_gt (A, B))
|
|
|
1402
|
|
|
1403 /* Return true if A is known to be less than B. */
|
|
|
1404 #define known_lt(A, B) (!maybe_ge (A, B))
|
|
|
1405
|
|
|
1406 /* Return true if A is known to be greater than B. */
|
|
|
1407 #define known_gt(A, B) (!maybe_le (A, B))
|
|
|
1408
|
|
|
1409 /* Return true if A is known to be greater than or equal to B. */
|
|
|
1410 #define known_ge(A, B) (!maybe_lt (A, B))
|
|
|
1411
|
|
|
1412 /* Return true if A and B are ordered by the partial ordering known_le. */
|
|
|
1413
|
|
|
1414 template<typename T1, typename T2>
|
|
|
1415 inline bool
|
|
|
1416 ordered_p (const T1 &a, const T2 &b)
|
|
|
1417 {
|
|
|
1418 return ((poly_int_traits<T1>::num_coeffs == 1
|
|
|
1419 && poly_int_traits<T2>::num_coeffs == 1)
|
|
|
1420 || known_le (a, b)
|
|
|
1421 || known_le (b, a));
|
|
|
1422 }
|
|
|
1423
|
|
|
1424 /* Assert that A and B are known to be ordered and return the minimum
|
|
|
1425 of the two.
|
|
|
1426
|
|
|
1427 NOTE: When using this function, please add a comment above the call
|
|
|
1428 explaining why we know the values are ordered in that context. */
|
|
|
1429
|
|
|
1430 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1431 inline POLY_POLY_RESULT (N, Ca, Cb)
|
|
|
1432 ordered_min (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
|
|
|
1433 {
|
|
|
1434 if (known_le (a, b))
|
|
|
1435 return a;
|
|
|
1436 else
|
|
|
1437 {
|
|
|
1438 if (N > 1)
|
|
|
1439 gcc_checking_assert (known_le (b, a));
|
|
|
1440 return b;
|
|
|
1441 }
|
|
|
1442 }
|
|
|
1443
|
|
|
1444 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1445 inline CONST_POLY_RESULT (N, Ca, Cb)
|
|
|
1446 ordered_min (const Ca &a, const poly_int_pod<N, Cb> &b)
|
|
|
1447 {
|
|
|
1448 if (known_le (a, b))
|
|
|
1449 return a;
|
|
|
1450 else
|
|
|
1451 {
|
|
|
1452 if (N > 1)
|
|
|
1453 gcc_checking_assert (known_le (b, a));
|
|
|
1454 return b;
|
|
|
1455 }
|
|
|
1456 }
|
|
|
1457
|
|
|
1458 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1459 inline POLY_CONST_RESULT (N, Ca, Cb)
|
|
|
1460 ordered_min (const poly_int_pod<N, Ca> &a, const Cb &b)
|
|
|
1461 {
|
|
|
1462 if (known_le (a, b))
|
|
|
1463 return a;
|
|
|
1464 else
|
|
|
1465 {
|
|
|
1466 if (N > 1)
|
|
|
1467 gcc_checking_assert (known_le (b, a));
|
|
|
1468 return b;
|
|
|
1469 }
|
|
|
1470 }
|
|
|
1471
|
|
|
1472 /* Assert that A and B are known to be ordered and return the maximum
|
|
|
1473 of the two.
|
|
|
1474
|
|
|
1475 NOTE: When using this function, please add a comment above the call
|
|
|
1476 explaining why we know the values are ordered in that context. */
|
|
|
1477
|
|
|
1478 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1479 inline POLY_POLY_RESULT (N, Ca, Cb)
|
|
|
1480 ordered_max (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
|
|
|
1481 {
|
|
|
1482 if (known_le (a, b))
|
|
|
1483 return b;
|
|
|
1484 else
|
|
|
1485 {
|
|
|
1486 if (N > 1)
|
|
|
1487 gcc_checking_assert (known_le (b, a));
|
|
|
1488 return a;
|
|
|
1489 }
|
|
|
1490 }
|
|
|
1491
|
|
|
1492 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1493 inline CONST_POLY_RESULT (N, Ca, Cb)
|
|
|
1494 ordered_max (const Ca &a, const poly_int_pod<N, Cb> &b)
|
|
|
1495 {
|
|
|
1496 if (known_le (a, b))
|
|
|
1497 return b;
|
|
|
1498 else
|
|
|
1499 {
|
|
|
1500 if (N > 1)
|
|
|
1501 gcc_checking_assert (known_le (b, a));
|
|
|
1502 return a;
|
|
|
1503 }
|
|
|
1504 }
|
|
|
1505
|
|
|
1506 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1507 inline POLY_CONST_RESULT (N, Ca, Cb)
|
|
|
1508 ordered_max (const poly_int_pod<N, Ca> &a, const Cb &b)
|
|
|
1509 {
|
|
|
1510 if (known_le (a, b))
|
|
|
1511 return b;
|
|
|
1512 else
|
|
|
1513 {
|
|
|
1514 if (N > 1)
|
|
|
1515 gcc_checking_assert (known_le (b, a));
|
|
|
1516 return a;
|
|
|
1517 }
|
|
|
1518 }
|
|
|
1519
|
|
|
1520 /* Return a constant lower bound on the value of A, which is known
|
|
|
1521 to be nonnegative. */
|
|
|
1522
|
|
|
1523 template<unsigned int N, typename Ca>
|
|
|
1524 inline Ca
|
|
|
1525 constant_lower_bound (const poly_int_pod<N, Ca> &a)
|
|
|
1526 {
|
|
|
1527 gcc_checking_assert (known_ge (a, POLY_INT_TYPE (Ca) (0)));
|
|
|
1528 return a.coeffs[0];
|
|
|
1529 }
|
|
|
1530
|
|
|
1531 /* Return a value that is known to be no greater than A and B. This
|
|
|
1532 will be the greatest lower bound for some indeterminate values but
|
|
|
1533 not necessarily for all. */
|
|
|
1534
|
|
|
1535 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1536 inline POLY_CONST_RESULT (N, Ca, Cb)
|
|
|
1537 lower_bound (const poly_int_pod<N, Ca> &a, const Cb &b)
|
|
|
1538 {
|
|
|
1539 typedef POLY_CAST (Ca, Cb) NCa;
|
|
|
1540 typedef POLY_CAST (Cb, Ca) NCb;
|
|
|
1541 typedef POLY_INT_TYPE (Cb) ICb;
|
|
|
1542 typedef POLY_CONST_COEFF (Ca, Cb) C;
|
|
|
1543
|
|
|
1544 poly_int<N, C> r;
|
|
|
1545 POLY_SET_COEFF (C, r, 0, MIN (NCa (a.coeffs[0]), NCb (b)));
|
|
|
1546 if (N >= 2)
|
|
|
1547 for (unsigned int i = 1; i < N; i++)
|
|
|
1548 POLY_SET_COEFF (C, r, i, MIN (NCa (a.coeffs[i]), ICb (0)));
|
|
|
1549 return r;
|
|
|
1550 }
|
|
|
1551
|
|
|
1552 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1553 inline CONST_POLY_RESULT (N, Ca, Cb)
|
|
|
1554 lower_bound (const Ca &a, const poly_int_pod<N, Cb> &b)
|
|
|
1555 {
|
|
|
1556 return lower_bound (b, a);
|
|
|
1557 }
|
|
|
1558
|
|
|
1559 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1560 inline POLY_POLY_RESULT (N, Ca, Cb)
|
|
|
1561 lower_bound (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
|
|
|
1562 {
|
|
|
1563 typedef POLY_CAST (Ca, Cb) NCa;
|
|
|
1564 typedef POLY_CAST (Cb, Ca) NCb;
|
|
|
1565 typedef POLY_POLY_COEFF (Ca, Cb) C;
|
|
|
1566
|
|
|
1567 poly_int<N, C> r;
|
|
|
1568 for (unsigned int i = 0; i < N; i++)
|
|
|
1569 POLY_SET_COEFF (C, r, i, MIN (NCa (a.coeffs[i]), NCb (b.coeffs[i])));
|
|
|
1570 return r;
|
|
|
1571 }
|
|
|
1572
|
|
|
1573 template<typename Ca, typename Cb>
|
|
|
1574 inline CONST_CONST_RESULT (N, Ca, Cb)
|
|
|
1575 lower_bound (const Ca &a, const Cb &b)
|
|
|
1576 {
|
|
|
1577 return a < b ? a : b;
|
|
|
1578 }
|
|
|
1579
|
|
|
1580 /* Return a value that is known to be no less than A and B. This will
|
|
|
1581 be the least upper bound for some indeterminate values but not
|
|
|
1582 necessarily for all. */
|
|
|
1583
|
|
|
1584 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1585 inline POLY_CONST_RESULT (N, Ca, Cb)
|
|
|
1586 upper_bound (const poly_int_pod<N, Ca> &a, const Cb &b)
|
|
|
1587 {
|
|
|
1588 typedef POLY_CAST (Ca, Cb) NCa;
|
|
|
1589 typedef POLY_CAST (Cb, Ca) NCb;
|
|
|
1590 typedef POLY_INT_TYPE (Cb) ICb;
|
|
|
1591 typedef POLY_CONST_COEFF (Ca, Cb) C;
|
|
|
1592
|
|
|
1593 poly_int<N, C> r;
|
|
|
1594 POLY_SET_COEFF (C, r, 0, MAX (NCa (a.coeffs[0]), NCb (b)));
|
|
|
1595 if (N >= 2)
|
|
|
1596 for (unsigned int i = 1; i < N; i++)
|
|
|
1597 POLY_SET_COEFF (C, r, i, MAX (NCa (a.coeffs[i]), ICb (0)));
|
|
|
1598 return r;
|
|
|
1599 }
|
|
|
1600
|
|
|
1601 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1602 inline CONST_POLY_RESULT (N, Ca, Cb)
|
|
|
1603 upper_bound (const Ca &a, const poly_int_pod<N, Cb> &b)
|
|
|
1604 {
|
|
|
1605 return upper_bound (b, a);
|
|
|
1606 }
|
|
|
1607
|
|
|
1608 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1609 inline POLY_POLY_RESULT (N, Ca, Cb)
|
|
|
1610 upper_bound (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
|
|
|
1611 {
|
|
|
1612 typedef POLY_CAST (Ca, Cb) NCa;
|
|
|
1613 typedef POLY_CAST (Cb, Ca) NCb;
|
|
|
1614 typedef POLY_POLY_COEFF (Ca, Cb) C;
|
|
|
1615
|
|
|
1616 poly_int<N, C> r;
|
|
|
1617 for (unsigned int i = 0; i < N; i++)
|
|
|
1618 POLY_SET_COEFF (C, r, i, MAX (NCa (a.coeffs[i]), NCb (b.coeffs[i])));
|
|
|
1619 return r;
|
|
|
1620 }
|
|
|
1621
|
|
|
1622 /* Return the greatest common divisor of all nonzero coefficients, or zero
|
|
|
1623 if all coefficients are zero. */
|
|
|
1624
|
|
|
1625 template<unsigned int N, typename Ca>
|
|
|
1626 inline POLY_BINARY_COEFF (Ca, Ca)
|
|
|
1627 coeff_gcd (const poly_int_pod<N, Ca> &a)
|
|
|
1628 {
|
|
|
1629 /* Find the first nonzero coefficient, stopping at 0 whatever happens. */
|
|
|
1630 unsigned int i;
|
|
|
1631 for (i = N - 1; i > 0; --i)
|
|
|
1632 if (a.coeffs[i] != 0)
|
|
|
1633 break;
|
|
|
1634 typedef POLY_BINARY_COEFF (Ca, Ca) C;
|
|
|
1635 C r = a.coeffs[i];
|
|
|
1636 for (unsigned int j = 0; j < i; ++j)
|
|
|
1637 if (a.coeffs[j] != 0)
|
|
|
1638 r = gcd (r, C (a.coeffs[j]));
|
|
|
1639 return r;
|
|
|
1640 }
|
|
|
1641
|
|
|
1642 /* Return a value that is a multiple of both A and B. This will be the
|
|
|
1643 least common multiple for some indeterminate values but necessarily
|
|
|
1644 for all. */
|
|
|
1645
|
|
|
1646 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1647 POLY_CONST_RESULT (N, Ca, Cb)
|
|
|
1648 common_multiple (const poly_int_pod<N, Ca> &a, Cb b)
|
|
|
1649 {
|
|
|
1650 POLY_BINARY_COEFF (Ca, Ca) xgcd = coeff_gcd (a);
|
|
|
1651 return a * (least_common_multiple (xgcd, b) / xgcd);
|
|
|
1652 }
|
|
|
1653
|
|
|
1654 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1655 inline CONST_POLY_RESULT (N, Ca, Cb)
|
|
|
1656 common_multiple (const Ca &a, const poly_int_pod<N, Cb> &b)
|
|
|
1657 {
|
|
|
1658 return common_multiple (b, a);
|
|
|
1659 }
|
|
|
1660
|
|
|
1661 /* Return a value that is a multiple of both A and B, asserting that
|
|
|
1662 such a value exists. The result will be the least common multiple
|
|
|
1663 for some indeterminate values but necessarily for all.
|
|
|
1664
|
|
|
1665 NOTE: When using this function, please add a comment above the call
|
|
|
1666 explaining why we know the values have a common multiple (which might
|
|
|
1667 for example be because we know A / B is rational). */
|
|
|
1668
|
|
|
1669 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1670 POLY_POLY_RESULT (N, Ca, Cb)
|
|
|
1671 force_common_multiple (const poly_int_pod<N, Ca> &a,
|
|
|
1672 const poly_int_pod<N, Cb> &b)
|
|
|
1673 {
|
|
|
1674 if (b.is_constant ())
|
|
|
1675 return common_multiple (a, b.coeffs[0]);
|
|
|
1676 if (a.is_constant ())
|
|
|
1677 return common_multiple (a.coeffs[0], b);
|
|
|
1678
|
|
|
1679 typedef POLY_CAST (Ca, Cb) NCa;
|
|
|
1680 typedef POLY_CAST (Cb, Ca) NCb;
|
|
|
1681 typedef POLY_BINARY_COEFF (Ca, Cb) C;
|
|
|
1682 typedef POLY_INT_TYPE (Ca) ICa;
|
|
|
1683
|
|
|
1684 for (unsigned int i = 1; i < N; ++i)
|
|
|
1685 if (a.coeffs[i] != ICa (0))
|
|
|
1686 {
|
|
|
1687 C lcm = least_common_multiple (NCa (a.coeffs[i]), NCb (b.coeffs[i]));
|
|
|
1688 C amul = lcm / a.coeffs[i];
|
|
|
1689 C bmul = lcm / b.coeffs[i];
|
|
|
1690 for (unsigned int j = 0; j < N; ++j)
|
|
|
1691 gcc_checking_assert (a.coeffs[j] * amul == b.coeffs[j] * bmul);
|
|
|
1692 return a * amul;
|
|
|
1693 }
|
|
|
1694 gcc_unreachable ();
|
|
|
1695 }
|
|
|
1696
|
|
|
1697 /* Compare A and B for sorting purposes, returning -1 if A should come
|
|
|
1698 before B, 0 if A and B are identical, and 1 if A should come after B.
|
|
|
1699 This is a lexicographical compare of the coefficients in reverse order.
|
|
|
1700
|
|
|
1701 A consequence of this is that all constant sizes come before all
|
|
|
1702 non-constant ones, regardless of magnitude (since a size is never
|
|
|
1703 negative). This is what most callers want. For example, when laying
|
|
|
1704 data out on the stack, it's better to keep all the constant-sized
|
|
|
1705 data together so that it can be accessed as a constant offset from a
|
|
|
1706 single base. */
|
|
|
1707
|
|
|
1708 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1709 inline int
|
|
|
1710 compare_sizes_for_sort (const poly_int_pod<N, Ca> &a,
|
|
|
1711 const poly_int_pod<N, Cb> &b)
|
|
|
1712 {
|
|
|
1713 for (unsigned int i = N; i-- > 0; )
|
|
|
1714 if (a.coeffs[i] != b.coeffs[i])
|
|
|
1715 return a.coeffs[i] < b.coeffs[i] ? -1 : 1;
|
|
|
1716 return 0;
|
|
|
1717 }
|
|
|
1718
|
|
|
1719 /* Return true if we can calculate VALUE & (ALIGN - 1) at compile time. */
|
|
|
1720
|
|
|
1721 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1722 inline bool
|
|
|
1723 can_align_p (const poly_int_pod<N, Ca> &value, Cb align)
|
|
|
1724 {
|
|
|
1725 for (unsigned int i = 1; i < N; i++)
|
|
|
1726 if ((value.coeffs[i] & (align - 1)) != 0)
|
|
|
1727 return false;
|
|
|
1728 return true;
|
|
|
1729 }
|
|
|
1730
|
|
|
1731 /* Return true if we can align VALUE up to the smallest multiple of
|
|
|
1732 ALIGN that is >= VALUE. Store the aligned value in *ALIGNED if so. */
|
|
|
1733
|
|
|
1734 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1735 inline bool
|
|
|
1736 can_align_up (const poly_int_pod<N, Ca> &value, Cb align,
|
|
|
1737 poly_int_pod<N, Ca> *aligned)
|
|
|
1738 {
|
|
|
1739 if (!can_align_p (value, align))
|
|
|
1740 return false;
|
|
|
1741 *aligned = value + (-value.coeffs[0] & (align - 1));
|
|
|
1742 return true;
|
|
|
1743 }
|
|
|
1744
|
|
|
1745 /* Return true if we can align VALUE down to the largest multiple of
|
|
|
1746 ALIGN that is <= VALUE. Store the aligned value in *ALIGNED if so. */
|
|
|
1747
|
|
|
1748 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1749 inline bool
|
|
|
1750 can_align_down (const poly_int_pod<N, Ca> &value, Cb align,
|
|
|
1751 poly_int_pod<N, Ca> *aligned)
|
|
|
1752 {
|
|
|
1753 if (!can_align_p (value, align))
|
|
|
1754 return false;
|
|
|
1755 *aligned = value - (value.coeffs[0] & (align - 1));
|
|
|
1756 return true;
|
|
|
1757 }
|
|
|
1758
|
|
|
1759 /* Return true if we can align A and B up to the smallest multiples of
|
|
|
1760 ALIGN that are >= A and B respectively, and if doing so gives the
|
|
|
1761 same value. */
|
|
|
1762
|
|
|
1763 template<unsigned int N, typename Ca, typename Cb, typename Cc>
|
|
|
1764 inline bool
|
|
|
1765 known_equal_after_align_up (const poly_int_pod<N, Ca> &a,
|
|
|
1766 const poly_int_pod<N, Cb> &b,
|
|
|
1767 Cc align)
|
|
|
1768 {
|
|
|
1769 poly_int<N, Ca> aligned_a;
|
|
|
1770 poly_int<N, Cb> aligned_b;
|
|
|
1771 return (can_align_up (a, align, &aligned_a)
|
|
|
1772 && can_align_up (b, align, &aligned_b)
|
|
|
1773 && known_eq (aligned_a, aligned_b));
|
|
|
1774 }
|
|
|
1775
|
|
|
1776 /* Return true if we can align A and B down to the largest multiples of
|
|
|
1777 ALIGN that are <= A and B respectively, and if doing so gives the
|
|
|
1778 same value. */
|
|
|
1779
|
|
|
1780 template<unsigned int N, typename Ca, typename Cb, typename Cc>
|
|
|
1781 inline bool
|
|
|
1782 known_equal_after_align_down (const poly_int_pod<N, Ca> &a,
|
|
|
1783 const poly_int_pod<N, Cb> &b,
|
|
|
1784 Cc align)
|
|
|
1785 {
|
|
|
1786 poly_int<N, Ca> aligned_a;
|
|
|
1787 poly_int<N, Cb> aligned_b;
|
|
|
1788 return (can_align_down (a, align, &aligned_a)
|
|
|
1789 && can_align_down (b, align, &aligned_b)
|
|
|
1790 && known_eq (aligned_a, aligned_b));
|
|
|
1791 }
|
|
|
1792
|
|
|
1793 /* Assert that we can align VALUE to ALIGN at compile time and return
|
|
|
1794 the smallest multiple of ALIGN that is >= VALUE.
|
|
|
1795
|
|
|
1796 NOTE: When using this function, please add a comment above the call
|
|
|
1797 explaining why we know the non-constant coefficients must already
|
|
|
1798 be a multiple of ALIGN. */
|
|
|
1799
|
|
|
1800 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1801 inline poly_int<N, Ca>
|
|
|
1802 force_align_up (const poly_int_pod<N, Ca> &value, Cb align)
|
|
|
1803 {
|
|
|
1804 gcc_checking_assert (can_align_p (value, align));
|
|
|
1805 return value + (-value.coeffs[0] & (align - 1));
|
|
|
1806 }
|
|
|
1807
|
|
|
1808 /* Assert that we can align VALUE to ALIGN at compile time and return
|
|
|
1809 the largest multiple of ALIGN that is <= VALUE.
|
|
|
1810
|
|
|
1811 NOTE: When using this function, please add a comment above the call
|
|
|
1812 explaining why we know the non-constant coefficients must already
|
|
|
1813 be a multiple of ALIGN. */
|
|
|
1814
|
|
|
1815 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1816 inline poly_int<N, Ca>
|
|
|
1817 force_align_down (const poly_int_pod<N, Ca> &value, Cb align)
|
|
|
1818 {
|
|
|
1819 gcc_checking_assert (can_align_p (value, align));
|
|
|
1820 return value - (value.coeffs[0] & (align - 1));
|
|
|
1821 }
|
|
|
1822
|
|
|
1823 /* Return a value <= VALUE that is a multiple of ALIGN. It will be the
|
|
|
1824 greatest such value for some indeterminate values but not necessarily
|
|
|
1825 for all. */
|
|
|
1826
|
|
|
1827 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1828 inline poly_int<N, Ca>
|
|
|
1829 aligned_lower_bound (const poly_int_pod<N, Ca> &value, Cb align)
|
|
|
1830 {
|
|
|
1831 poly_int<N, Ca> r;
|
|
|
1832 for (unsigned int i = 0; i < N; i++)
|
|
|
1833 /* This form copes correctly with more type combinations than
|
|
|
1834 value.coeffs[i] & -align would. */
|
|
|
1835 POLY_SET_COEFF (Ca, r, i, (value.coeffs[i]
|
|
|
1836 - (value.coeffs[i] & (align - 1))));
|
|
|
1837 return r;
|
|
|
1838 }
|
|
|
1839
|
|
|
1840 /* Return a value >= VALUE that is a multiple of ALIGN. It will be the
|
|
|
1841 least such value for some indeterminate values but not necessarily
|
|
|
1842 for all. */
|
|
|
1843
|
|
|
1844 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1845 inline poly_int<N, Ca>
|
|
|
1846 aligned_upper_bound (const poly_int_pod<N, Ca> &value, Cb align)
|
|
|
1847 {
|
|
|
1848 poly_int<N, Ca> r;
|
|
|
1849 for (unsigned int i = 0; i < N; i++)
|
|
|
1850 POLY_SET_COEFF (Ca, r, i, (value.coeffs[i]
|
|
|
1851 + (-value.coeffs[i] & (align - 1))));
|
|
|
1852 return r;
|
|
|
1853 }
|
|
|
1854
|
|
|
1855 /* Assert that we can align VALUE to ALIGN at compile time. Align VALUE
|
|
|
1856 down to the largest multiple of ALIGN that is <= VALUE, then divide by
|
|
|
1857 ALIGN.
|
|
|
1858
|
|
|
1859 NOTE: When using this function, please add a comment above the call
|
|
|
1860 explaining why we know the non-constant coefficients must already
|
|
|
1861 be a multiple of ALIGN. */
|
|
|
1862
|
|
|
1863 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1864 inline poly_int<N, Ca>
|
|
|
1865 force_align_down_and_div (const poly_int_pod<N, Ca> &value, Cb align)
|
|
|
1866 {
|
|
|
1867 gcc_checking_assert (can_align_p (value, align));
|
|
|
1868
|
|
|
1869 poly_int<N, Ca> r;
|
|
|
1870 POLY_SET_COEFF (Ca, r, 0, ((value.coeffs[0]
|
|
|
1871 - (value.coeffs[0] & (align - 1)))
|
|
|
1872 / align));
|
|
|
1873 if (N >= 2)
|
|
|
1874 for (unsigned int i = 1; i < N; i++)
|
|
|
1875 POLY_SET_COEFF (Ca, r, i, value.coeffs[i] / align);
|
|
|
1876 return r;
|
|
|
1877 }
|
|
|
1878
|
|
|
1879 /* Assert that we can align VALUE to ALIGN at compile time. Align VALUE
|
|
|
1880 up to the smallest multiple of ALIGN that is >= VALUE, then divide by
|
|
|
1881 ALIGN.
|
|
|
1882
|
|
|
1883 NOTE: When using this function, please add a comment above the call
|
|
|
1884 explaining why we know the non-constant coefficients must already
|
|
|
1885 be a multiple of ALIGN. */
|
|
|
1886
|
|
|
1887 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1888 inline poly_int<N, Ca>
|
|
|
1889 force_align_up_and_div (const poly_int_pod<N, Ca> &value, Cb align)
|
|
|
1890 {
|
|
|
1891 gcc_checking_assert (can_align_p (value, align));
|
|
|
1892
|
|
|
1893 poly_int<N, Ca> r;
|
|
|
1894 POLY_SET_COEFF (Ca, r, 0, ((value.coeffs[0]
|
|
|
1895 + (-value.coeffs[0] & (align - 1)))
|
|
|
1896 / align));
|
|
|
1897 if (N >= 2)
|
|
|
1898 for (unsigned int i = 1; i < N; i++)
|
|
|
1899 POLY_SET_COEFF (Ca, r, i, value.coeffs[i] / align);
|
|
|
1900 return r;
|
|
|
1901 }
|
|
|
1902
|
|
|
1903 /* Return true if we know at compile time the difference between VALUE
|
|
|
1904 and the equal or preceding multiple of ALIGN. Store the value in
|
|
|
1905 *MISALIGN if so. */
|
|
|
1906
|
|
|
1907 template<unsigned int N, typename Ca, typename Cb, typename Cm>
|
|
|
1908 inline bool
|
|
|
1909 known_misalignment (const poly_int_pod<N, Ca> &value, Cb align, Cm *misalign)
|
|
|
1910 {
|
|
|
1911 gcc_checking_assert (align != 0);
|
|
|
1912 if (!can_align_p (value, align))
|
|
|
1913 return false;
|
|
|
1914 *misalign = value.coeffs[0] & (align - 1);
|
|
|
1915 return true;
|
|
|
1916 }
|
|
|
1917
|
|
|
1918 /* Return X & (Y - 1), asserting that this value is known. Please add
|
|
|
1919 an a comment above callers to this function to explain why the condition
|
|
|
1920 is known to hold. */
|
|
|
1921
|
|
|
1922 template<unsigned int N, typename Ca, typename Cb>
|
|
|
1923 inline POLY_BINARY_COEFF (Ca, Ca)
|
|
|
1924 force_get_misalignment (const poly_int_pod<N, Ca> &a, Cb align)
|
|
|
1925 {
|
|
|
1926 gcc_checking_assert (can_align_p (a, align));
|
|
|
1927 return a.coeffs[0] & (align - 1);
|
|
|
1928 }
|
|
|
1929
|
|
|
1930 /* Return the maximum alignment that A is known to have. Return 0
|
|
|
1931 if A is known to be zero. */
|
|
|
1932
|
|
|
1933 template<unsigned int N, typename Ca>
|
|
|
1934 inline POLY_BINARY_COEFF (Ca, Ca)
|
|
|
1935 known_alignment (const poly_int_pod<N, Ca> &a)
|
|
|
1936 {
|
|
|
1937 typedef POLY_BINARY_COEFF (Ca, Ca) C;
|
|
|
1938 C r = a.coeffs[0];
|
|
|
1939 for (unsigned int i = 1; i < N; ++i)
|
|
|
1940 r |= a.coeffs[i];
|
|
|
1941 return r & -r;
|
|
|
1942 }
|
|
|
1943
|
|
|
1944 /* Return true if we can compute A | B at compile time, storing the
|
|
|
1945 result in RES if so. */
|
|
|
1946
|
|
|
1947 template<unsigned int N, typename Ca, typename Cb, typename Cr>
|
|
|
1948 inline typename if_nonpoly<Cb, bool>::type
|
|
|
1949 can_ior_p (const poly_int_pod<N, Ca> &a, Cb b, Cr *result)
|
|
|
1950 {
|
|
|
1951 /* Coefficients 1 and above must be a multiple of something greater
|
|
|
1952 than B. */
|
|
|
1953 typedef POLY_INT_TYPE (Ca) int_type;
|
|
|
1954 if (N >= 2)
|
|
|
1955 for (unsigned int i = 1; i < N; i++)
|
|
|
1956 if ((-(a.coeffs[i] & -a.coeffs[i]) & b) != int_type (0))
|
|
|
1957 return false;
|
|
|
1958 *result = a;
|
|
|
1959 result->coeffs[0] |= b;
|
|
|
1960 return true;
|
|
|
1961 }
|
|
|
1962
|
|
|
1963 /* Return true if A is a constant multiple of B, storing the
|
|
|
1964 multiple in *MULTIPLE if so. */
|
|
|
1965
|
|
|
1966 template<unsigned int N, typename Ca, typename Cb, typename Cm>
|
|
|
1967 inline typename if_nonpoly<Cb, bool>::type
|
|
|
1968 constant_multiple_p (const poly_int_pod<N, Ca> &a, Cb b, Cm *multiple)
|
|
|
1969 {
|
|
|
1970 typedef POLY_CAST (Ca, Cb) NCa;
|
|
|
1971 typedef POLY_CAST (Cb, Ca) NCb;
|
|
|
1972
|
|
|
1973 /* Do the modulus before the constant check, to catch divide by
|
|
|
1974 zero errors. */
|
|
|
1975 if (NCa (a.coeffs[0]) % NCb (b) != 0 || !a.is_constant ())
|
|
|
1976 return false;
|
|
|
1977 *multiple = NCa (a.coeffs[0]) / NCb (b);
|
|
|
1978 return true;
|
|
|
1979 }
|
|
|
1980
|
|
|
1981 template<unsigned int N, typename Ca, typename Cb, typename Cm>
|
|
|
1982 inline typename if_nonpoly<Ca, bool>::type
|
|
|
1983 constant_multiple_p (Ca a, const poly_int_pod<N, Cb> &b, Cm *multiple)
|
|
|
1984 {
|
|
|
1985 typedef POLY_CAST (Ca, Cb) NCa;
|
|
|
1986 typedef POLY_CAST (Cb, Ca) NCb;
|
|
|
1987 typedef POLY_INT_TYPE (Ca) int_type;
|
|
|
1988
|
|
|
1989 /* Do the modulus before the constant check, to catch divide by
|
|
|
1990 zero errors. */
|
|
|
1991 if (NCa (a) % NCb (b.coeffs[0]) != 0
|
|
|
1992 || (a != int_type (0) && !b.is_constant ()))
|
|
|
1993 return false;
|
|
|
1994 *multiple = NCa (a) / NCb (b.coeffs[0]);
|
|
|
1995 return true;
|
|
|
1996 }
|
|
|
1997
|
|
|
1998 template<unsigned int N, typename Ca, typename Cb, typename Cm>
|
|
|
1999 inline bool
|
|
|
2000 constant_multiple_p (const poly_int_pod<N, Ca> &a,
|
|
|
2001 const poly_int_pod<N, Cb> &b, Cm *multiple)
|
|
|
2002 {
|
|
|
2003 typedef POLY_CAST (Ca, Cb) NCa;
|
|
|
2004 typedef POLY_CAST (Cb, Ca) NCb;
|
|
|
2005 typedef POLY_INT_TYPE (Ca) ICa;
|
|
|
2006 typedef POLY_INT_TYPE (Cb) ICb;
|
|
|
2007 typedef POLY_BINARY_COEFF (Ca, Cb) C;
|
|
|
2008
|
|
|
2009 if (NCa (a.coeffs[0]) % NCb (b.coeffs[0]) != 0)
|
|
|
2010 return false;
|
|
|
2011
|
|
|
2012 C r = NCa (a.coeffs[0]) / NCb (b.coeffs[0]);
|
|
|
2013 for (unsigned int i = 1; i < N; ++i)
|
|
|
2014 if (b.coeffs[i] == ICb (0)
|
|
|
2015 ? a.coeffs[i] != ICa (0)
|
|
|
2016 : (NCa (a.coeffs[i]) % NCb (b.coeffs[i]) != 0
|
|
|
2017 || NCa (a.coeffs[i]) / NCb (b.coeffs[i]) != r))
|
|
|
2018 return false;
|
|
|
2019
|
|
|
2020 *multiple = r;
|
|
|
2021 return true;
|
|
|
2022 }
|
|
|
2023
|
|
|
2024 /* Return true if A is a multiple of B. */
|
|
|
2025
|
|
|
2026 template<typename Ca, typename Cb>
|
|
|
2027 inline typename if_nonpoly2<Ca, Cb, bool>::type
|
|
|
2028 multiple_p (Ca a, Cb b)
|
|
|
2029 {
|
|
|
2030 return a % b == 0;
|
|
|
2031 }
|
|
|
2032
|
|
|
2033 /* Return true if A is a (polynomial) multiple of B. */
|
|
|
2034
|
|
|
2035 template<unsigned int N, typename Ca, typename Cb>
|
|
|
2036 inline typename if_nonpoly<Cb, bool>::type
|
|
|
2037 multiple_p (const poly_int_pod<N, Ca> &a, Cb b)
|
|
|
2038 {
|
|
|
2039 for (unsigned int i = 0; i < N; ++i)
|
|
|
2040 if (a.coeffs[i] % b != 0)
|
|
|
2041 return false;
|
|
|
2042 return true;
|
|
|
2043 }
|
|
|
2044
|
|
|
2045 /* Return true if A is a (constant) multiple of B. */
|
|
|
2046
|
|
|
2047 template<unsigned int N, typename Ca, typename Cb>
|
|
|
2048 inline typename if_nonpoly<Ca, bool>::type
|
|
|
2049 multiple_p (Ca a, const poly_int_pod<N, Cb> &b)
|
|
|
2050 {
|
|
|
2051 typedef POLY_INT_TYPE (Ca) int_type;
|
|
|
2052
|
|
|
2053 /* Do the modulus before the constant check, to catch divide by
|
|
|
2054 potential zeros. */
|
|
|
2055 return a % b.coeffs[0] == 0 && (a == int_type (0) || b.is_constant ());
|
|
|
2056 }
|
|
|
2057
|
|
|
2058 /* Return true if A is a (polynomial) multiple of B. This handles cases
|
|
|
2059 where either B is constant or the multiple is constant. */
|
|
|
2060
|
|
|
2061 template<unsigned int N, typename Ca, typename Cb>
|
|
|
2062 inline bool
|
|
|
2063 multiple_p (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
|
|
|
2064 {
|
|
|
2065 if (b.is_constant ())
|
|
|
2066 return multiple_p (a, b.coeffs[0]);
|
|
|
2067 POLY_BINARY_COEFF (Ca, Ca) tmp;
|
|
|
2068 return constant_multiple_p (a, b, &tmp);
|
|
|
2069 }
|
|
|
2070
|
|
|
2071 /* Return true if A is a (constant) multiple of B, storing the
|
|
|
2072 multiple in *MULTIPLE if so. */
|
|
|
2073
|
|
|
2074 template<typename Ca, typename Cb, typename Cm>
|
|
|
2075 inline typename if_nonpoly2<Ca, Cb, bool>::type
|
|
|
2076 multiple_p (Ca a, Cb b, Cm *multiple)
|
|
|
2077 {
|
|
|
2078 if (a % b != 0)
|
|
|
2079 return false;
|
|
|
2080 *multiple = a / b;
|
|
|
2081 return true;
|
|
|
2082 }
|
|
|
2083
|
|
|
2084 /* Return true if A is a (polynomial) multiple of B, storing the
|
|
|
2085 multiple in *MULTIPLE if so. */
|
|
|
2086
|
|
|
2087 template<unsigned int N, typename Ca, typename Cb, typename Cm>
|
|
|
2088 inline typename if_nonpoly<Cb, bool>::type
|
|
|
2089 multiple_p (const poly_int_pod<N, Ca> &a, Cb b, poly_int_pod<N, Cm> *multiple)
|
|
|
2090 {
|
|
|
2091 if (!multiple_p (a, b))
|
|
|
2092 return false;
|
|
|
2093 for (unsigned int i = 0; i < N; ++i)
|
|
|
2094 multiple->coeffs[i] = a.coeffs[i] / b;
|
|
|
2095 return true;
|
|
|
2096 }
|
|
|
2097
|
|
|
2098 /* Return true if B is a constant and A is a (constant) multiple of B,
|
|
|
2099 storing the multiple in *MULTIPLE if so. */
|
|
|
2100
|
|
|
2101 template<unsigned int N, typename Ca, typename Cb, typename Cm>
|
|
|
2102 inline typename if_nonpoly<Ca, bool>::type
|
|
|
2103 multiple_p (Ca a, const poly_int_pod<N, Cb> &b, Cm *multiple)
|
|
|
2104 {
|
|
|
2105 typedef POLY_CAST (Ca, Cb) NCa;
|
|
|
2106
|
|
|
2107 /* Do the modulus before the constant check, to catch divide by
|
|
|
2108 potential zeros. */
|
|
|
2109 if (a % b.coeffs[0] != 0 || (NCa (a) != 0 && !b.is_constant ()))
|
|
|
2110 return false;
|
|
|
2111 *multiple = a / b.coeffs[0];
|
|
|
2112 return true;
|
|
|
2113 }
|
|
|
2114
|
|
|
2115 /* Return true if A is a (polynomial) multiple of B, storing the
|
|
|
2116 multiple in *MULTIPLE if so. This handles cases where either
|
|
|
2117 B is constant or the multiple is constant. */
|
|
|
2118
|
|
|
2119 template<unsigned int N, typename Ca, typename Cb, typename Cm>
|
|
|
2120 inline bool
|
|
|
2121 multiple_p (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b,
|
|
|
2122 poly_int_pod<N, Cm> *multiple)
|
|
|
2123 {
|
|
|
2124 if (b.is_constant ())
|
|
|
2125 return multiple_p (a, b.coeffs[0], multiple);
|
|
|
2126 return constant_multiple_p (a, b, multiple);
|
|
|
2127 }
|
|
|
2128
|
|
|
2129 /* Return A / B, given that A is known to be a multiple of B. */
|
|
|
2130
|
|
|
2131 template<unsigned int N, typename Ca, typename Cb>
|
|
|
2132 inline POLY_CONST_RESULT (N, Ca, Cb)
|
|
|
2133 exact_div (const poly_int_pod<N, Ca> &a, Cb b)
|
|
|
2134 {
|
|
|
2135 typedef POLY_CONST_COEFF (Ca, Cb) C;
|
|
|
2136 poly_int<N, C> r;
|
|
|
2137 for (unsigned int i = 0; i < N; i++)
|
|
|
2138 {
|
|
|
2139 gcc_checking_assert (a.coeffs[i] % b == 0);
|
|
|
2140 POLY_SET_COEFF (C, r, i, a.coeffs[i] / b);
|
|
|
2141 }
|
|
|
2142 return r;
|
|
|
2143 }
|
|
|
2144
|
|
|
2145 /* Return A / B, given that A is known to be a multiple of B. */
|
|
|
2146
|
|
|
2147 template<unsigned int N, typename Ca, typename Cb>
|
|
|
2148 inline POLY_POLY_RESULT (N, Ca, Cb)
|
|
|
2149 exact_div (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
|
|
|
2150 {
|
|
|
2151 if (b.is_constant ())
|
|
|
2152 return exact_div (a, b.coeffs[0]);
|
|
|
2153
|
|
|
2154 typedef POLY_CAST (Ca, Cb) NCa;
|
|
|
2155 typedef POLY_CAST (Cb, Ca) NCb;
|
|
|
2156 typedef POLY_BINARY_COEFF (Ca, Cb) C;
|
|
|
2157 typedef POLY_INT_TYPE (Cb) int_type;
|
|
|
2158
|
|
|
2159 gcc_checking_assert (a.coeffs[0] % b.coeffs[0] == 0);
|
|
|
2160 C r = NCa (a.coeffs[0]) / NCb (b.coeffs[0]);
|
|
|
2161 for (unsigned int i = 1; i < N; ++i)
|
|
|
2162 gcc_checking_assert (b.coeffs[i] == int_type (0)
|
|
|
2163 ? a.coeffs[i] == int_type (0)
|
|
|
2164 : (a.coeffs[i] % b.coeffs[i] == 0
|
|
|
2165 && NCa (a.coeffs[i]) / NCb (b.coeffs[i]) == r));
|
|
|
2166
|
|
|
2167 return r;
|
|
|
2168 }
|
|
|
2169
|
|
|
2170 /* Return true if there is some constant Q and polynomial r such that:
|
|
|
2171
|
|
|
2172 (1) a = b * Q + r
|
|
|
2173 (2) |b * Q| <= |a|
|
|
|
2174 (3) |r| < |b|
|
|
|
2175
|
|
|
2176 Store the value Q in *QUOTIENT if so. */
|
|
|
2177
|
|
|
2178 template<unsigned int N, typename Ca, typename Cb, typename Cq>
|
|
|
2179 inline typename if_nonpoly2<Cb, Cq, bool>::type
|
|
|
2180 can_div_trunc_p (const poly_int_pod<N, Ca> &a, Cb b, Cq *quotient)
|
|
|
2181 {
|
|
|
2182 typedef POLY_CAST (Ca, Cb) NCa;
|
|
|
2183 typedef POLY_CAST (Cb, Ca) NCb;
|
|
|
2184
|
|
|
2185 /* Do the division before the constant check, to catch divide by
|
|
|
2186 zero errors. */
|
|
|
2187 Cq q = NCa (a.coeffs[0]) / NCb (b);
|
|
|
2188 if (!a.is_constant ())
|
|
|
2189 return false;
|
|
|
2190 *quotient = q;
|
|
|
2191 return true;
|
|
|
2192 }
|
|
|
2193
|
|
|
2194 template<unsigned int N, typename Ca, typename Cb, typename Cq>
|
|
|
2195 inline typename if_nonpoly<Cq, bool>::type
|
|
|
2196 can_div_trunc_p (const poly_int_pod<N, Ca> &a,
|
|
|
2197 const poly_int_pod<N, Cb> &b,
|
|
|
2198 Cq *quotient)
|
|
|
2199 {
|
|
|
2200 /* We can calculate Q from the case in which the indeterminates
|
|
|
2201 are zero. */
|
|
|
2202 typedef POLY_CAST (Ca, Cb) NCa;
|
|
|
2203 typedef POLY_CAST (Cb, Ca) NCb;
|
|
|
2204 typedef POLY_INT_TYPE (Ca) ICa;
|
|
|
2205 typedef POLY_INT_TYPE (Cb) ICb;
|
|
|
2206 typedef POLY_BINARY_COEFF (Ca, Cb) C;
|
|
|
2207 C q = NCa (a.coeffs[0]) / NCb (b.coeffs[0]);
|
|
|
2208
|
|
|
2209 /* Check the other coefficients and record whether the division is exact.
|
|
|
2210 The only difficult case is when it isn't. If we require a and b to
|
|
|
2211 ordered wrt zero, there can be no two coefficients of the same value
|
|
|
2212 that have opposite signs. This means that:
|
|
|
2213
|
|
|
2214 |a| = |a0| + |a1 * x1| + |a2 * x2| + ...
|
|
|
2215 |b| = |b0| + |b1 * x1| + |b2 * x2| + ...
|
|
|
2216
|
|
|
2217 The Q we've just calculated guarantees:
|
|
|
2218
|
|
|
2219 |b0 * Q| <= |a0|
|
|
|
2220 |a0 - b0 * Q| < |b0|
|
|
|
2221
|
|
|
2222 and so:
|
|
|
2223
|
|
|
2224 (2) |b * Q| <= |a|
|
|
|
2225
|
|
|
2226 is satisfied if:
|
|
|
2227
|
|
|
2228 |bi * xi * Q| <= |ai * xi|
|
|
|
2229
|
|
|
2230 for each i in [1, N]. This is trivially true when xi is zero.
|
|
|
2231 When it isn't we need:
|
|
|
2232
|
|
|
2233 (2') |bi * Q| <= |ai|
|
|
|
2234
|
|
|
2235 r is calculated as:
|
|
|
2236
|
|
|
2237 r = r0 + r1 * x1 + r2 * x2 + ...
|
|
|
2238 where ri = ai - bi * Q
|
|
|
2239
|
|
|
2240 Restricting to ordered a and b also guarantees that no two ris
|
|
|
2241 have opposite signs, so we have:
|
|
|
2242
|
|
|
2243 |r| = |r0| + |r1 * x1| + |r2 * x2| + ...
|
|
|
2244
|
|
|
2245 We know from the calculation of Q that |r0| < |b0|, so:
|
|
|
2246
|
|
|
2247 (3) |r| < |b|
|
|
|
2248
|
|
|
2249 is satisfied if:
|
|
|
2250
|
|
|
2251 (3') |ai - bi * Q| <= |bi|
|
|
|
2252
|
|
|
2253 for each i in [1, N]. */
|
|
|
2254 bool rem_p = NCa (a.coeffs[0]) % NCb (b.coeffs[0]) != 0;
|
|
|
2255 for (unsigned int i = 1; i < N; ++i)
|
|
|
2256 {
|
|
|
2257 if (b.coeffs[i] == ICb (0))
|
|
|
2258 {
|
|
|
2259 /* For bi == 0 we simply need: (3') |ai| == 0. */
|
|
|
2260 if (a.coeffs[i] != ICa (0))
|
|
|
2261 return false;
|
|
|
2262 }
|
|
|
2263 else
|
|
|
2264 {
|
|
|
2265 if (q == 0)
|
|
|
2266 {
|
|
|
2267 /* For Q == 0 we simply need: (3') |ai| <= |bi|. */
|
|
|
2268 if (a.coeffs[i] != ICa (0))
|
|
|
2269 {
|
|
|
2270 /* Use negative absolute to avoid overflow, i.e.
|
|
|
2271 -|ai| >= -|bi|. */
|
|
|
2272 C neg_abs_a = (a.coeffs[i] < 0 ? a.coeffs[i] : -a.coeffs[i]);
|
|
|
2273 C neg_abs_b = (b.coeffs[i] < 0 ? b.coeffs[i] : -b.coeffs[i]);
|
|
|
2274 if (neg_abs_a < neg_abs_b)
|
|
|
2275 return false;
|
|
|
2276 rem_p = true;
|
|
|
2277 }
|
|
|
2278 }
|
|
|
2279 else
|
|
|
2280 {
|
|
|
2281 /* Otherwise just check for the case in which ai / bi == Q. */
|
|
|
2282 if (NCa (a.coeffs[i]) / NCb (b.coeffs[i]) != q)
|
|
|
2283 return false;
|
|
|
2284 if (NCa (a.coeffs[i]) % NCb (b.coeffs[i]) != 0)
|
|
|
2285 rem_p = true;
|
|
|
2286 }
|
|
|
2287 }
|
|
|
2288 }
|
|
|
2289
|
|
|
2290 /* If the division isn't exact, require both values to be ordered wrt 0,
|
|
|
2291 so that we can guarantee conditions (2) and (3) for all indeterminate
|
|
|
2292 values. */
|
|
|
2293 if (rem_p && (!ordered_p (a, ICa (0)) || !ordered_p (b, ICb (0))))
|
|
|
2294 return false;
|
|
|
2295
|
|
|
2296 *quotient = q;
|
|
|
2297 return true;
|
|
|
2298 }
|
|
|
2299
|
|
|
2300 /* Likewise, but also store r in *REMAINDER. */
|
|
|
2301
|
|
|
2302 template<unsigned int N, typename Ca, typename Cb, typename Cq, typename Cr>
|
|
|
2303 inline typename if_nonpoly<Cq, bool>::type
|
|
|
2304 can_div_trunc_p (const poly_int_pod<N, Ca> &a,
|
|
|
2305 const poly_int_pod<N, Cb> &b,
|
|
|
2306 Cq *quotient, Cr *remainder)
|
|
|
2307 {
|
|
|
2308 if (!can_div_trunc_p (a, b, quotient))
|
|
|
2309 return false;
|
|
|
2310 *remainder = a - *quotient * b;
|
|
|
2311 return true;
|
|
|
2312 }
|
|
|
2313
|
|
|
2314 /* Return true if there is some polynomial q and constant R such that:
|
|
|
2315
|
|
|
2316 (1) a = B * q + R
|
|
|
2317 (2) |B * q| <= |a|
|
|
|
2318 (3) |R| < |B|
|
|
|
2319
|
|
|
2320 Store the value q in *QUOTIENT if so. */
|
|
|
2321
|
|
|
2322 template<unsigned int N, typename Ca, typename Cb, typename Cq>
|
|
|
2323 inline typename if_nonpoly<Cb, bool>::type
|
|
|
2324 can_div_trunc_p (const poly_int_pod<N, Ca> &a, Cb b,
|
|
|
2325 poly_int_pod<N, Cq> *quotient)
|
|
|
2326 {
|
|
|
2327 /* The remainder must be constant. */
|
|
|
2328 for (unsigned int i = 1; i < N; ++i)
|
|
|
2329 if (a.coeffs[i] % b != 0)
|
|
|
2330 return false;
|
|
|
2331 for (unsigned int i = 0; i < N; ++i)
|
|
|
2332 quotient->coeffs[i] = a.coeffs[i] / b;
|
|
|
2333 return true;
|
|
|
2334 }
|
|
|
2335
|
|
|
2336 /* Likewise, but also store R in *REMAINDER. */
|
|
|
2337
|
|
|
2338 template<unsigned int N, typename Ca, typename Cb, typename Cq, typename Cr>
|
|
|
2339 inline typename if_nonpoly<Cb, bool>::type
|
|
|
2340 can_div_trunc_p (const poly_int_pod<N, Ca> &a, Cb b,
|
|
|
2341 poly_int_pod<N, Cq> *quotient, Cr *remainder)
|
|
|
2342 {
|
|
|
2343 if (!can_div_trunc_p (a, b, quotient))
|
|
|
2344 return false;
|
|
|
2345 *remainder = a.coeffs[0] % b;
|
|
|
2346 return true;
|
|
|
2347 }
|
|
|
2348
|
|
|
2349 /* Return true if we can compute A / B at compile time, rounding towards zero.
|
|
|
2350 Store the result in QUOTIENT if so.
|
|
|
2351
|
|
|
2352 This handles cases in which either B is constant or the result is
|
|
|
2353 constant. */
|
|
|
2354
|
|
|
2355 template<unsigned int N, typename Ca, typename Cb, typename Cq>
|
|
|
2356 inline bool
|
|
|
2357 can_div_trunc_p (const poly_int_pod<N, Ca> &a,
|
|
|
2358 const poly_int_pod<N, Cb> &b,
|
|
|
2359 poly_int_pod<N, Cq> *quotient)
|
|
|
2360 {
|
|
|
2361 if (b.is_constant ())
|
|
|
2362 return can_div_trunc_p (a, b.coeffs[0], quotient);
|
|
|
2363 if (!can_div_trunc_p (a, b, "ient->coeffs[0]))
|
|
|
2364 return false;
|
|
|
2365 for (unsigned int i = 1; i < N; ++i)
|
|
|
2366 quotient->coeffs[i] = 0;
|
|
|
2367 return true;
|
|
|
2368 }
|
|
|
2369
|
|
|
2370 /* Return true if there is some constant Q and polynomial r such that:
|
|
|
2371
|
|
|
2372 (1) a = b * Q + r
|
|
|
2373 (2) |a| <= |b * Q|
|
|
|
2374 (3) |r| < |b|
|
|
|
2375
|
|
|
2376 Store the value Q in *QUOTIENT if so. */
|
|
|
2377
|
|
|
2378 template<unsigned int N, typename Ca, typename Cb, typename Cq>
|
|
|
2379 inline typename if_nonpoly<Cq, bool>::type
|
|
|
2380 can_div_away_from_zero_p (const poly_int_pod<N, Ca> &a,
|
|
|
2381 const poly_int_pod<N, Cb> &b,
|
|
|
2382 Cq *quotient)
|
|
|
2383 {
|
|
|
2384 if (!can_div_trunc_p (a, b, quotient))
|
|
|
2385 return false;
|
|
|
2386 if (maybe_ne (*quotient * b, a))
|
|
|
2387 *quotient += (*quotient < 0 ? -1 : 1);
|
|
|
2388 return true;
|
|
|
2389 }
|
|
|
2390
|
|
|
2391 /* Use print_dec to print VALUE to FILE, where SGN is the sign
|
|
|
2392 of the values. */
|
|
|
2393
|
|
|
2394 template<unsigned int N, typename C>
|
|
|
2395 void
|
|
|
2396 print_dec (const poly_int_pod<N, C> &value, FILE *file, signop sgn)
|
|
|
2397 {
|
|
|
2398 if (value.is_constant ())
|
|
|
2399 print_dec (value.coeffs[0], file, sgn);
|
|
|
2400 else
|
|
|
2401 {
|
|
|
2402 fprintf (file, "[");
|
|
|
2403 for (unsigned int i = 0; i < N; ++i)
|
|
|
2404 {
|
|
|
2405 print_dec (value.coeffs[i], file, sgn);
|
|
|
2406 fputc (i == N - 1 ? ']' : ',', file);
|
|
|
2407 }
|
|
|
2408 }
|
|
|
2409 }
|
|
|
2410
|
|
|
2411 /* Likewise without the signop argument, for coefficients that have an
|
|
|
2412 inherent signedness. */
|
|
|
2413
|
|
|
2414 template<unsigned int N, typename C>
|
|
|
2415 void
|
|
|
2416 print_dec (const poly_int_pod<N, C> &value, FILE *file)
|
|
|
2417 {
|
|
|
2418 STATIC_ASSERT (poly_coeff_traits<C>::signedness >= 0);
|
|
|
2419 print_dec (value, file,
|
|
|
2420 poly_coeff_traits<C>::signedness ? SIGNED : UNSIGNED);
|
|
|
2421 }
|
|
|
2422
|
|
|
2423 /* Use print_hex to print VALUE to FILE. */
|
|
|
2424
|
|
|
2425 template<unsigned int N, typename C>
|
|
|
2426 void
|
|
|
2427 print_hex (const poly_int_pod<N, C> &value, FILE *file)
|
|
|
2428 {
|
|
|
2429 if (value.is_constant ())
|
|
|
2430 print_hex (value.coeffs[0], file);
|
|
|
2431 else
|
|
|
2432 {
|
|
|
2433 fprintf (file, "[");
|
|
|
2434 for (unsigned int i = 0; i < N; ++i)
|
|
|
2435 {
|
|
|
2436 print_hex (value.coeffs[i], file);
|
|
|
2437 fputc (i == N - 1 ? ']' : ',', file);
|
|
|
2438 }
|
|
|
2439 }
|
|
|
2440 }
|
|
|
2441
|
|
|
2442 /* Helper for calculating the distance between two points P1 and P2,
|
|
|
2443 in cases where known_le (P1, P2). T1 and T2 are the types of the
|
|
|
2444 two positions, in either order. The coefficients of P2 - P1 have
|
|
|
2445 type unsigned HOST_WIDE_INT if the coefficients of both T1 and T2
|
|
|
2446 have C++ primitive type, otherwise P2 - P1 has its usual
|
|
|
2447 wide-int-based type.
|
|
|
2448
|
|
|
2449 The actual subtraction should look something like this:
|
|
|
2450
|
|
|
2451 typedef poly_span_traits<T1, T2> span_traits;
|
|
|
2452 span_traits::cast (P2) - span_traits::cast (P1)
|
|
|
2453
|
|
|
2454 Applying the cast before the subtraction avoids undefined overflow
|
|
|
2455 for signed T1 and T2.
|
|
|
2456
|
|
|
2457 The implementation of the cast tries to avoid unnecessary arithmetic
|
|
|
2458 or copying. */
|
|
|
2459 template<typename T1, typename T2,
|
|
|
2460 typename Res = POLY_BINARY_COEFF (POLY_BINARY_COEFF (T1, T2),
|
|
|
2461 unsigned HOST_WIDE_INT)>
|
|
|
2462 struct poly_span_traits
|
|
|
2463 {
|
|
|
2464 template<typename T>
|
|
|
2465 static const T &cast (const T &x) { return x; }
|
|
|
2466 };
|
|
|
2467
|
|
|
2468 template<typename T1, typename T2>
|
|
|
2469 struct poly_span_traits<T1, T2, unsigned HOST_WIDE_INT>
|
|
|
2470 {
|
|
|
2471 template<typename T>
|
|
|
2472 static typename if_nonpoly<T, unsigned HOST_WIDE_INT>::type
|
|
|
2473 cast (const T &x) { return x; }
|
|
|
2474
|
|
|
2475 template<unsigned int N, typename T>
|
|
|
2476 static poly_int<N, unsigned HOST_WIDE_INT>
|
|
|
2477 cast (const poly_int_pod<N, T> &x) { return x; }
|
|
|
2478 };
|
|
|
2479
|
|
|
2480 /* Return true if SIZE represents a known size, assuming that all-ones
|
|
|
2481 indicates an unknown size. */
|
|
|
2482
|
|
|
2483 template<typename T>
|
|
|
2484 inline bool
|
|
|
2485 known_size_p (const T &a)
|
|
|
2486 {
|
|
|
2487 return maybe_ne (a, POLY_INT_TYPE (T) (-1));
|
|
|
2488 }
|
|
|
2489
|
|
|
2490 /* Return true if range [POS, POS + SIZE) might include VAL.
|
|
|
2491 SIZE can be the special value -1, in which case the range is
|
|
|
2492 open-ended. */
|
|
|
2493
|
|
|
2494 template<typename T1, typename T2, typename T3>
|
|
|
2495 inline bool
|
|
|
2496 maybe_in_range_p (const T1 &val, const T2 &pos, const T3 &size)
|
|
|
2497 {
|
|
|
2498 typedef poly_span_traits<T1, T2> start_span;
|
|
|
2499 typedef poly_span_traits<T3, T3> size_span;
|
|
|
2500 if (known_lt (val, pos))
|
|
|
2501 return false;
|
|
|
2502 if (!known_size_p (size))
|
|
|
2503 return true;
|
|
|
2504 if ((poly_int_traits<T1>::num_coeffs > 1
|
|
|
2505 || poly_int_traits<T2>::num_coeffs > 1)
|
|
|
2506 && maybe_lt (val, pos))
|
|
|
2507 /* In this case we don't know whether VAL >= POS is true at compile
|
|
|
2508 time, so we can't prove that VAL >= POS + SIZE. */
|
|
|
2509 return true;
|
|
|
2510 return maybe_lt (start_span::cast (val) - start_span::cast (pos),
|
|
|
2511 size_span::cast (size));
|
|
|
2512 }
|
|
|
2513
|
|
|
2514 /* Return true if range [POS, POS + SIZE) is known to include VAL.
|
|
|
2515 SIZE can be the special value -1, in which case the range is
|
|
|
2516 open-ended. */
|
|
|
2517
|
|
|
2518 template<typename T1, typename T2, typename T3>
|
|
|
2519 inline bool
|
|
|
2520 known_in_range_p (const T1 &val, const T2 &pos, const T3 &size)
|
|
|
2521 {
|
|
|
2522 typedef poly_span_traits<T1, T2> start_span;
|
|
|
2523 typedef poly_span_traits<T3, T3> size_span;
|
|
|
2524 return (known_size_p (size)
|
|
|
2525 && known_ge (val, pos)
|
|
|
2526 && known_lt (start_span::cast (val) - start_span::cast (pos),
|
|
|
2527 size_span::cast (size)));
|
|
|
2528 }
|
|
|
2529
|
|
|
2530 /* Return true if the two ranges [POS1, POS1 + SIZE1) and [POS2, POS2 + SIZE2)
|
|
|
2531 might overlap. SIZE1 and/or SIZE2 can be the special value -1, in which
|
|
|
2532 case the range is open-ended. */
|
|
|
2533
|
|
|
2534 template<typename T1, typename T2, typename T3, typename T4>
|
|
|
2535 inline bool
|
|
|
2536 ranges_maybe_overlap_p (const T1 &pos1, const T2 &size1,
|
|
|
2537 const T3 &pos2, const T4 &size2)
|
|
|
2538 {
|
|
|
2539 if (maybe_in_range_p (pos2, pos1, size1))
|
|
|
2540 return maybe_ne (size2, POLY_INT_TYPE (T4) (0));
|
|
|
2541 if (maybe_in_range_p (pos1, pos2, size2))
|
|
|
2542 return maybe_ne (size1, POLY_INT_TYPE (T2) (0));
|
|
|
2543 return false;
|
|
|
2544 }
|
|
|
2545
|
|
|
2546 /* Return true if the two ranges [POS1, POS1 + SIZE1) and [POS2, POS2 + SIZE2)
|
|
|
2547 are known to overlap. SIZE1 and/or SIZE2 can be the special value -1,
|
|
|
2548 in which case the range is open-ended. */
|
|
|
2549
|
|
|
2550 template<typename T1, typename T2, typename T3, typename T4>
|
|
|
2551 inline bool
|
|
|
2552 ranges_known_overlap_p (const T1 &pos1, const T2 &size1,
|
|
|
2553 const T3 &pos2, const T4 &size2)
|
|
|
2554 {
|
|
|
2555 typedef poly_span_traits<T1, T3> start_span;
|
|
|
2556 typedef poly_span_traits<T2, T2> size1_span;
|
|
|
2557 typedef poly_span_traits<T4, T4> size2_span;
|
|
|
2558 /* known_gt (POS1 + SIZE1, POS2) [infinite precision]
|
|
|
2559 --> known_gt (SIZE1, POS2 - POS1) [infinite precision]
|
|
|
2560 --> known_gt (SIZE1, POS2 - lower_bound (POS1, POS2)) [infinite precision]
|
|
|
2561 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ always nonnegative
|
|
|
2562 --> known_gt (SIZE1, span1::cast (POS2 - lower_bound (POS1, POS2))).
|
|
|
2563
|
|
|
2564 Using the saturating subtraction enforces that SIZE1 must be
|
|
|
2565 nonzero, since known_gt (0, x) is false for all nonnegative x.
|
|
|
2566 If POS2.coeff[I] < POS1.coeff[I] for some I > 0, increasing
|
|
|
2567 indeterminate number I makes the unsaturated condition easier to
|
|
|
2568 satisfy, so using a saturated coefficient of zero tests the case in
|
|
|
2569 which the indeterminate is zero (the minimum value). */
|
|
|
2570 return (known_size_p (size1)
|
|
|
2571 && known_size_p (size2)
|
|
|
2572 && known_lt (start_span::cast (pos2)
|
|
|
2573 - start_span::cast (lower_bound (pos1, pos2)),
|
|
|
2574 size1_span::cast (size1))
|
|
|
2575 && known_lt (start_span::cast (pos1)
|
|
|
2576 - start_span::cast (lower_bound (pos1, pos2)),
|
|
|
2577 size2_span::cast (size2)));
|
|
|
2578 }
|
|
|
2579
|
|
|
2580 /* Return true if range [POS1, POS1 + SIZE1) is known to be a subrange of
|
|
|
2581 [POS2, POS2 + SIZE2). SIZE1 and/or SIZE2 can be the special value -1,
|
|
|
2582 in which case the range is open-ended. */
|
|
|
2583
|
|
|
2584 template<typename T1, typename T2, typename T3, typename T4>
|
|
|
2585 inline bool
|
|
|
2586 known_subrange_p (const T1 &pos1, const T2 &size1,
|
|
|
2587 const T3 &pos2, const T4 &size2)
|
|
|
2588 {
|
|
|
2589 typedef typename poly_int_traits<T2>::coeff_type C2;
|
|
|
2590 typedef poly_span_traits<T1, T3> start_span;
|
|
|
2591 typedef poly_span_traits<T2, T4> size_span;
|
|
|
2592 return (known_gt (size1, POLY_INT_TYPE (T2) (0))
|
|
|
2593 && (poly_coeff_traits<C2>::signedness > 0
|
|
|
2594 || known_size_p (size1))
|
|
|
2595 && known_size_p (size2)
|
|
|
2596 && known_ge (pos1, pos2)
|
|
|
2597 && known_le (size1, size2)
|
|
|
2598 && known_le (start_span::cast (pos1) - start_span::cast (pos2),
|
|
|
2599 size_span::cast (size2) - size_span::cast (size1)));
|
|
|
2600 }
|
|
|
2601
|
|
|
2602 /* Return true if the endpoint of the range [POS, POS + SIZE) can be
|
|
|
2603 stored in a T, or if SIZE is the special value -1, which makes the
|
|
|
2604 range open-ended. */
|
|
|
2605
|
|
|
2606 template<typename T>
|
|
|
2607 inline typename if_nonpoly<T, bool>::type
|
|
|
2608 endpoint_representable_p (const T &pos, const T &size)
|
|
|
2609 {
|
|
|
2610 return (!known_size_p (size)
|
|
|
2611 || pos <= poly_coeff_traits<T>::max_value - size);
|
|
|
2612 }
|
|
|
2613
|
|
|
2614 template<unsigned int N, typename C>
|
|
|
2615 inline bool
|
|
|
2616 endpoint_representable_p (const poly_int_pod<N, C> &pos,
|
|
|
2617 const poly_int_pod<N, C> &size)
|
|
|
2618 {
|
|
|
2619 if (known_size_p (size))
|
|
|
2620 for (unsigned int i = 0; i < N; ++i)
|
|
|
2621 if (pos.coeffs[i] > poly_coeff_traits<C>::max_value - size.coeffs[i])
|
|
|
2622 return false;
|
|
|
2623 return true;
|
|
|
2624 }
|
|
|
2625
|
|
|
2626 template<unsigned int N, typename C>
|
|
|
2627 void
|
|
|
2628 gt_ggc_mx (poly_int_pod<N, C> *)
|
|
|
2629 {
|
|
|
2630 }
|
|
|
2631
|
|
|
2632 template<unsigned int N, typename C>
|
|
|
2633 void
|
|
|
2634 gt_pch_nx (poly_int_pod<N, C> *)
|
|
|
2635 {
|
|
|
2636 }
|
|
|
2637
|
|
|
2638 template<unsigned int N, typename C>
|
|
|
2639 void
|
|
|
2640 gt_pch_nx (poly_int_pod<N, C> *, void (*) (void *, void *), void *)
|
|
|
2641 {
|
|
|
2642 }
|
|
|
2643
|
|
|
2644 #undef POLY_SET_COEFF
|
|
|
2645 #undef POLY_INT_TYPE
|
|
|
2646 #undef POLY_BINARY_COEFF
|
|
|
2647 #undef CONST_CONST_RESULT
|
|
|
2648 #undef POLY_CONST_RESULT
|
|
|
2649 #undef CONST_POLY_RESULT
|
|
|
2650 #undef POLY_POLY_RESULT
|
|
|
2651 #undef POLY_CONST_COEFF
|
|
|
2652 #undef CONST_POLY_COEFF
|
|
|
2653 #undef POLY_POLY_COEFF
|
|
|
2654
|
|
|
2655 #endif
|
