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