176 bool empty_p =
false;
282 bool substitute_p =
true;
289 substitute_p =
false;
294 fprintf(stderr,
"Initial constraint v=%p:\n", v);
296 fprintf(stderr,
"Difference dv=%p:\n", dv);
298 fprintf(stderr,
"New constraint nv=%p:\n", nv);
413 fprintf(stderr,
"Selected constraint: %lld %s + %lld %s + %lld\n",
436 "Constraint after change of frame: %lld %s + %lld %s + %lld\n",
440 fprintf(stderr,
"Change of frame: %d\n", *pcb);
443 nv =
vect_make(nv, *px, a, *py, b, NULL, NULL, NULL);
448 fprintf(stderr,
"New constraint nv: ");
468 bool eligible_p =
true;
469 bool bounded_p =
false;
486 bool var_bounded_p =
false;
490 var_bounded_p =
true;
590 fprintf(stderr,
"%s:\n", __FUNCTION__);
591 fprintf(stderr,
"Constraint before change of basis:");
593 fprintf(stderr,
"Initial interval x_min=%lld, x_max=%lld\n",
650 fprintf(stderr,
"%s:\n", __FUNCTION__);
651 fprintf(stderr,
"Constraint after change of basis:");
653 fprintf(stderr,
"Final interval x_min=%lld, x_max=%lld\n", *px_min, *px_max);
656 fprintf(stderr,
"Change of basis: %d\n", *pcb);
722 Value up_0 = a_up * x0 + b_up * y0 + c_up;
723 Value low_0 = a_low * x0 + b_low * y0 + c_low;
732 assert(a_up<0 && b_up>0 );
733 assert(a_low<0 && b_low>0 );
741 assert((xf>x0 && dx>0) || (xf<x0 && dx<0));
743 while(!found &&
x!=xf) {
771 found = (up <= 0 && low >0) &&
x!=x0 &&
x!=xf;
772 assert(!(up>0&&low<0) ||
x==x0 ||
x==xf);
799 Value n = a_up*x0+b_up*y0+c_up;
800 Value d = a_up*ndx+b_up*ndy;
806 assert((d>0 && th>=0) || (d<0 && th<=0));
835 assert(a_low*
x+b_low*y+c_low>=0);
847 fprintf(stderr,
"Intermediate point: (%lld, %lld) for "
848 "[(%lld,%lld),(%lld,%lld)] "
849 "with saturations low %lld and up %lld\n",
850 x, y, x0, y0, xf, yf,
851 (a_low*
x+b_low*y+c_low)/b_low,
852 (a_up*
x+b_up*y+c_up)/b_up);
853 fprintf(stderr,
"for constraints low and up:\n");
858 fprintf(stderr,
"No intermediate point found\n");
923 int rightmost = eni+1;
931 fprintf(stderr,
"%s: input arrays with %d effective points\n", __FUNCTION__, eni);
933 fprintf(stderr,
"(%lld, %lld)%s", ilmpx[i], ilmpy[i], i==eni+1?
"":
", ");
940 ilmpx[right], ilmpy[right]);
943 bool failed_p =
false;
944 for(i=0; i<eni+2 && !failed_p; i++) {
950 fprintf(stderr,
"%s: point %d =(%lld, %lld) is skipped (left=%d is unchanged).\n",
951 __FUNCTION__, right, ilmpx[right], ilmpy[right], left);
957 fprintf(stderr,
"%s: points %d =(%lld, %lld) and %d =(%lld, %lld) "
958 "are used as vertices to define a new constraint.\n",
959 __FUNCTION__, left, ilmpx[left], ilmpy[left],
960 right, ilmpx[right], ilmpy[right]);
973 assert(right-1==rightmost);
976 fprintf(stderr,
"%s: %d constraints obtained:\n", __FUNCTION__,
count);
1004 Value delta_x = rmpx-lmpx-1;
1005 Value delta_y = rmpy-lmpy;
1013 Value ilmpx[ni+2], ilmpy[ni+2];
1019 bool more_to_find_p = ni>0;
1025 while(more_to_find_p) {
1036 &ilmpx[eni+1], &ilmpy[eni+1]);
1039 Value nlmpx = ilmpx[eni];
1040 Value nlmpy = ilmpy[eni];
1041 Value ndelta_x = rmpx-nlmpx-1;
1042 Value ndelta_y = rmpy-nlmpy;
1047 more_to_find_p = nni>0;
1050 more_to_find_p =
false;
1055 ilmpx[eni+1] = rmpx;
1056 ilmpy[eni+1] = rmpy;
1098 Value ilmpx, ilmpy, irmpx, irmpy;
1123 double slope1 = ((double)(ilmpy-lmpy))/((
double)(ilmpx-lmpx));
1124 double slope3 = ((double)(rmpy-irmpy))/((
double)(rmpx-irmpx));
1136 double slope1 = ((double)(ilmpy-lmpy))/((
double)(ilmpx-lmpx));
1137 double slope2 = ((double)(irmpy-ilmpy))/((
double)(irmpx-ilmpx));
1138 double slope3 = ((double)(rmpy-irmpy))/((
double)(rmpx-irmpx));
1139 if(slope1>slope2 && slope2>slope3) {
1150 else if(slope2>slope1) {
1152 double slope12 = ((double)(irmpy-lmpy))/((
double)(irmpx-lmpx));
1153 if(slope12>slope3) {
1163 fprintf(stderr,
"not implemented.\n");
1169 double slope23 = ((double)(rmpy-ilmpy))/((
double)(rmpx-ilmpx));
1170 if(slope1>slope23) {
1180 fprintf(stderr,
"not implemented.\n");
1221 fprintf(stderr,
"%s:\n", __FUNCTION__);
1222 fprintf(stderr,
"Constraint after change of basis:");
1224 fprintf(stderr,
"Interval for %s: x_min=%lld, x_max=%lld\n",
1260 Value x_y_min, x_y_max;
1261 bool found_p, redundant_p;
1304 fprintf(stderr,
"lmpx=%d, lmpy=%d\n", (
int) lmpx, (
int) lmpy);
1312 else if(
value_lt(y_x_max, y_min)) {
1317 if (!redundant_p && !found_p
1332 assert(!redundant_p && found_p);
1341 fprintf(stderr,
"lmpx=%d, lmpy=%d\n", (
int) lmpx, (
int) lmpy);
1342 fprintf(stderr,
"rmpx=%d, rmpy=%d\n", (
int) rmpx, (
int) rmpy);
1352 ifscdebug(1)
fprintf(stderr,
"Case slope01\n");
1375 ifscdebug(1)
fprintf(stderr,
"Case slope02\n");
1382 ifscdebug(1)
fprintf(stderr,
"Case slope03\n");
1411 fprintf(stderr,
"Not implemented yet\n");
1474 assert(a_v!=0 && b_v!=0);
1477 #define MAX_NUMBER_OF_CONSTRAINTS (x_max-x_min)
1516 for(i=x_min;
value_le(i,x_max); i++) {
1527 y_ineq = (y_ineq>y_j)? y_j : y_ineq;
1530 y_ineq = (y_ineq<y_j)? y_j : y_ineq;
1534 "Discrepancy at x=%lld: initial bound=%lld, new bound=%lld\n",
1536 (
long long int) y_v, (
long long int) y_ineq);
1537 fprintf(stderr,
"Initial constraint: ");
1539 fprintf(stderr,
"\nNew constraints: ");
1585 fprintf(stderr,
"Initial constraint:\n");
1593 fprintf(stderr,
"x_min=%lld, x_max=%lld\n", (
long long int) x_min, (
long long int) x_max);
1611 &x_min, &x_max, &y_min, &y_max);
1779 bool empty_p =
false;
1881 else if(lower==upper) {
1891 fprintf(stderr,
"sc_bounded_normalization: empty bounding box\n");
1894 fprintf(stderr,
"sc_bounded_normalization: "
1895 "base for upper bound and upper bound:\n");
1898 fprintf(stderr,
"sc_bounded_normalization: "
1899 "base for lower bound and lower bound:\n");
1902 fprintf(stderr,
"sc_bounded_normalization: constraints found:\n");
1912 fprintf(stderr,
"%d <= %s <= %d\n", (
int) lower,
1915 else if(lower==upper)
1930 fprintf(stderr,
"%d <= %s \n", (
int) lower,
1950 for(
eq=sc_inegalites(ps);
1961 bool lb_failed_p =
false;
1962 bool ub_failed_p =
false;
1967 for(vc=v; !
VECTEUR_NUL_P(vc) && !(ub_failed_p&&lb_failed_p);
2027 fprintf(stderr,
"Redundant constraint:\n");
2057 for(
eq=sc_inegalites(ps);
2065 fprintf(stderr,
"New constraints:\n");
2155 bool is_sc_fais =
true;
2163 static int francois=1;
2172 (
eq != NULL) && is_sc_fais;
2182 (
eq!=NULL) && is_sc_fais;
2283 if (!SC_UNDEFINED_P(ps)) {
2284 Pbase b = sc_base(ps);
2290 bool failure_p =
false;
2335 sc_simple_variable_substitution_with_eq_ofl_ctrl(ps,
eq, v,
OFL_CTRL);
2346 if (!SC_UNDEFINED_P(ps)) {
2350 bool failure_p =
false;
2378 sc_simple_variable_substitution_with_eq_ofl_ctrl(ps,
eq, v,
OFL_CTRL);
2441 if (!ineq->
vecteur)
return(ps);
2447 ps->inegalites = ineq,
2540 volatile Psysteme new_ps = SC_UNDEFINED;
2541 volatile Psysteme proj_ps = SC_UNDEFINED;
2542 volatile bool feasible_p =
true;
2554 fprintf(stderr,
"overflow error in normalization\n");
2559 if(!SC_UNDEFINED_P(ps)) {
2595 for(proj_eq = sc_egalites(proj_ps),
2596 eq = sc_egalites(ps);
2653 sc_simple_variable_substitution_with_eq_ofl_ctrl
2681 proj_eq = next_proj_eq;
2687 for(proj_ineq = sc_inegalites(proj_ps),
2688 ineq = sc_inegalites(ps);
2772 proj_ps = check_feasibility(proj_ps);
2773 feasible_p = !SC_EMPTY_P(proj_ps);
2782 sc_base(new_ps) = sc_base(ps);
2784 sc_dimension(new_ps) = sc_dimension(ps);
2828 #define if_debug_sc_strong_normalize_2 if(false)
2831 bool feasible_p =
true;
2840 fprintf(stderr,
"overflow error in normalization\n");
2846 fprintf(stderr,
"[sc_strong_normalize2]: Begin\n");
2849 if(!SC_UNDEFINED_P(ps)) {
2858 "[sc_strong_normalize2]: After call to sc_normalize\n");
2859 fprintf(stderr,
"[sc_strong_normalize2]: Input system %p\n",
2865 for(
eq = sc_egalites(ps);
2922 sc_simple_variable_substitution_with_eq_ofl_ctrl
2938 "Print the two systems at each elimination step:\n");
2939 fprintf(stderr,
"[sc_strong_normalize2]: Input system %p\n",
2942 fprintf(stderr,
"[sc_strong_normalize2]: New system %p\n",
2956 "Print the three systems after inequality normalization:\n");
2957 fprintf(stderr,
"[sc_strong_normalize2]: Input system %p\n",
2960 fprintf(stderr,
"[sc_strong_normalize2]: New system %p\n",
2968 "[sc_strong_normalize2]:"
2969 " Non-feasibility detected by first call to sc_normalize\n");
2977 "[sc_strong_normalize2]: Empty system as input\n");
2988 sc_base(new_ps) =
base_copy(sc_base(ps));
2989 sc_dimension(new_ps) = sc_dimension(ps);
3000 "[sc_strong_normalize2]: Final value of new system %p:\n",
3003 fprintf(stderr,
"[sc_strong_normalize2]: End\n");
3071 #define if_debug_sc_strong_normalize_and_check_feasibility2 if(false)
3074 bool feasible_p =
true;
3082 fprintf(stderr,
"overflow error in normalization\n");
3089 "[sc_strong_normalize_and_check_feasibility2]"
3090 " Input system %p\n", ps);
3094 if(SC_UNDEFINED_P(ps)) {
3097 "[sc_strong_normalize_and_check_feasibility2]"
3098 " Empty system as input\n");
3105 "[sc_strong_normalize_and_check_feasibility2]:"
3106 " Non-feasibility detected by first call to sc_normalize\n");
3116 int neq = sc_nbre_egalites(ps);
3120 "[sc_strong_normalize_and_check_feasibility2]"
3121 " Input system after normalization %p\n", ps);
3134 feasible_p && neq > 0 && nvar <=
level ;
3136 for(
eq = sc_egalites(ps);
3181 v2 = (v2==
TCST)? nv : v2;
3196 v = (v1==
TCST)? v2 : v1;
3205 sc_simple_variable_substitution_with_eq_ofl_ctrl
3259 "Print the two systems at each nvar=%d step:\n", nvar);
3260 fprintf(stderr,
"[sc_strong_normalize_and_check_feasibility2]: Input system %p\n",
3263 fprintf(stderr,
"[sc_strong_normalize_and_check_feasibility2]: New system %p\n",
3276 feasible_p = feasible_p && !SC_EMPTY_P(ps = check_feasibility(ps));
3280 "Print the three systems after inequality normalization:\n");
3281 fprintf(stderr,
"[sc_strong_normalize_and_check_feasibility2]: Input system %p\n",
3284 fprintf(stderr,
"[sc_strong_normalize_and_check_feasibility2]: New system %p\n",
3296 sc_base(new_ps) =
base_copy(sc_base(ps));
3297 sc_dimension(new_ps) = sc_dimension(ps);
3304 "[sc_strong_normalize_and_check_feasibility2]: "
3305 "Input system %p\n", ps);
3308 "[sc_strong_normalize_and_check_feasibility2]: "
3309 "New system %p\n", new_ps);
3321 "[sc_strong_normalize_and_check_feasibility2]: Final value of new system %p:\n",
3324 fprintf(stderr,
"[sc_strong_normalize_and_check_feasibility2]: End\n");
3341 if (!SC_UNDEFINED_P(ps)) {
3345 for (eq1 = ps->
egalites; eq1 != NULL; eq1 = eq1->
succ) {
3349 for (ineq1 = ps->
inegalites; ineq1 != NULL;ineq1 = ineq1->
succ) {
float a2sf[2] __attribute__((aligned(16)))
USER generates a user error (i.e., non fatal) by printing the given MSG according to the FMT.
#define value_mone_p(val)
#define value_minus(v1, v2)
#define value_min(v1, v2)
#define value_pdiv(v1, v2)
#define value_notzero_p(val)
#define value_uminus(val)
unary operators on values
void const char const char const int
#define value_negz_p(val)
#define value_direct_multiply(v1, v2)
#define value_assign(ref, val)
assigments
#define value_zero_p(val)
#define value_addto(ref, val)
#define value_eq(v1, v2)
bool operators on values
#define value_plus(v1, v2)
binary operators on values
#define value_mult(v, w)
whether the default is protected or not this define makes no sense any more...
#define value_mod(v1, v2)
#define value_div(v1, v2)
#define value_posz_p(val)
Pbase make_base_from_vect(Pvecteur pv)
int rank_of_variable(Pbase base, Variable var)
this function returns the rank of the variable var in the base 0 encodes TCST, but I do not know why,...
bool base_contains_variable_p(Pbase b, Variable v)
bool base_contains_variable_p(Pbase b, Variable v): returns true if variable v is one of b's elements...
#define CONTRAINTE_UNDEFINED_P(c)
#define CONTRAINTE_NULLE_P(c)
contrainte nulle (non contrainte 0 == 0 ou 0 <= 0)
#define contrainte_succ(c)
#define contrainte_vecteur(c)
passage au champ vecteur d'une contrainte "a la Newgen"
#define CONTRAINTE_UNDEFINED
#define contrainte_rm(c)
the standard xxx_rm does not return a value
Pcontrainte contraintes_make(Pvecteur pv,...)
Convert a list of vectors into a list of constraints.
Pcontrainte contrainte_make(Pvecteur pv)
Pcontrainte contrainte_make(Pvecteur pv): allocation et initialisation d'une contrainte avec un vecte...
Pcontrainte contrainte_copy(Pcontrainte c_in)
Have a look at contrainte_dup and contraintes_dup which reverse the order of the list This copy versi...
Pcontrainte contrainte_make_1D(Value a, Variable x, Value b, bool less_p)
Generate a constraint a x <= b or a x >= b, according to less_p, or ax==b, regardless of less_p.
Pcontrainte contrainte_append(Pcontrainte c1, Pcontrainte c2)
Pcontrainte contrainte_append(c1, c2) Pcontrainte c1, c2;.
void eq_set_vect_nul(Pcontrainte)
void_eq_set_vect_nul(Pcontrainte c): transformation d'une contrainte en une contrainte triviale 0 == ...
bool egalite_normalize(Pcontrainte)
bool egalite_normalize(Pcontrainte eg): reduction d'une equation diophantienne par le pgcd de ses coe...
bool cyclic_constraint_list_p(Pcontrainte)
Check if list l contains a cycle.
bool contrainte_constante_p(Pcontrainte)
bool contrainte_constante_p(Pcontrainte c): test de contrainte triviale sans variables (ie du type 0<...
bool contrainte_normalize(Pcontrainte, bool)
normalize.c
bool inegalite_normalize(Pcontrainte)
bool inegalite_normalize(Pcontrainte ineg): normalisation d'une inegalite a variables entieres; voir ...
void inegalites_dump(Pcontrainte)
bool contrainte_verifiee(Pcontrainte, bool)
bool contrainte_verifiee(Pcontrainte ineg, bool eq_p): test de faisabilite d'inegalite (eq_p == false...
static bool(* bound_p)(entity)
void vect_dump(Pvecteur v)
void vect_dump(Pvecteur v): print sparse vector v on stderr.
void vect_fprint(FILE *f, Pvecteur v, get_variable_name_t variable_name)
void vect_fprint(FILE * f, Pvecteur v, char * (*variable_name)()): impression d'un vecteur creux v su...
int vect_dimension(Pvecteur v)
int vect_dimension(Pvecteur v): calcul du nombre de composantes non nulles et non constantes d'un vec...
int vect_size(Pvecteur v)
package vecteur - reductions
char *(* variable_debug_name)(Variable)
Debug support: pointer to the function used by debug print outs.
bool sc_consistent_p(Psysteme sc)
bool sc_consistent_p(Psysteme sc): check that sc is well defined, that the numbers of equalities and ...
Psysteme sc_make(Pcontrainte leg, Pcontrainte lineg)
Psysteme sc_make(Pcontrainte leg, Pcontrainte lineg): allocation et initialisation d'un systeme d'equ...
bool sc_weak_consistent_p(Psysteme sc)
check that sc is well defined, that the numbers of equalities and inequalities are consistent with th...
bool sc_rn_p(Psysteme sc)
bool sc_rn_p(Psysteme sc): check if the set associated to sc is the whole space, rn
Psysteme sc_empty(Pbase b)
Psysteme sc_empty(Pbase b): build a Psysteme with one unfeasible constraint to define the empty subsp...
void sc_rm(Psysteme ps)
void sc_rm(Psysteme ps): liberation de l'espace memoire occupe par le systeme de contraintes ps;
void sc_add_egalite(Psysteme p, Pcontrainte e)
void sc_add_egalite(Psysteme p, Pcontrainte e): macro ajoutant une egalite e a un systeme p; la base ...
void sc_add_inegalites(Psysteme p, Pcontrainte i)
bool sc_empty_p(Psysteme sc)
bool sc_empty_p(Psysteme sc): check if the set associated to sc is the constant sc_empty or not.
void sc_add_inegalite(Psysteme p, Pcontrainte i)
void sc_add_inegalite(Psysteme p, Pcontrainte i): macro ajoutant une inegalite i a un systeme p; la b...
void sc_add_egalites(Psysteme p, Pcontrainte i)
Psysteme sc_copy(Psysteme ps)
Psysteme sc_copy(Psysteme ps): duplication d'un systeme (allocation et copie complete des champs sans...
Psysteme sc_safe_kill_db_eg(Psysteme ps)
same as above, but returns an empty system if the system is not feasible
void sc_rm_empty_constraints(Psysteme ps, bool process_equalities)
package sc: elimination de redondance simple
bool sc_elim_simple_redund_with_ineq(Psysteme ps, Pcontrainte ineg)
bool sc_elim_simple_redund_with_ineq(Psysteme ps, Pcontrainte ineg): elimination des contraintes redo...
Psysteme sc_elim_double_constraints(Psysteme ps)
Psysteme sc_elim_double_constraints(Psysteme ps): elimination des egalites et des inegalites identiqu...
void sc_elim_empty_constraints(Psysteme ps, bool process_equalities)
void sc_elim_empty_constraints(Psysteme ps, bool process_equalities): elimination des "fausses" contr...
bool sc_elim_simple_redund_with_eq(Psysteme ps, Pcontrainte eg)
package sc
int sc_check_inequality_redundancy(Pcontrainte ineq, Psysteme ps)
int sc_check_inequality_redundancy(Pcontrainte ineq, Psysteme ps) Check if an inequality ineq,...
bool sc_rational_feasibility_ofl_ctrl(Psysteme sc, int ofl_ctrl, bool ofl_res)
Pcontrainte eq
element du vecteur colonne du systeme donne par l'analyse
Psysteme sc_safe_append(Psysteme s1, Psysteme s2)
Psysteme sc_safe_append(Psysteme s1, Psysteme s2) input : output : calcul de l'intersection des polye...
void sc_default_dump(Psysteme sc)
void sc_default_dump(Psysteme sc): dump to stderr
int fprintf()
test sc_min : ce test s'appelle par : programme fichier1.data fichier2.data ...
Psysteme sc_add_normalize_ineq(Psysteme ps, Pcontrainte ineq)
static Pvecteur compute_x_and_y_bounds(Pvecteur v, Pvecteur l, Pvecteur lb, Pvecteur u, Pvecteur ub, Variable *px, Variable *py, Value *px_min, Value *px_max, int *pcb)
v is supposed to be the equation of a line in a 2-D space.
Psysteme sc_normalize2(volatile Psysteme ps)
Psysteme sc_normalize2(Psysteme ps): normalisation d'un systeme d'equation et d'inequations lineaires...
static bool eligible_for_coefficient_reduction_with_bounding_box_p(Pvecteur v, Pvecteur l, Pvecteur lb, Pvecteur u, Pvecteur ub)
Is it possible to reduce the magnitude of at least one constraint coefficient because it is larger th...
Psysteme sc_strong_normalize3(Psysteme ps)
static Pcontrainte reduce_coefficients_with_bounding_box(Pvecteur v, Pvecteur l, Pvecteur lb, Pvecteur u, Pvecteur ub)
If at least one of the coefficients of constraint v == ax+by<=c are greater that the intervals of the...
Psysteme sc_strong_normalize5(Psysteme ps, char *(*variable_name)(Variable))
static void check_coefficient_reduction(Pvecteur v, Pcontrainte ineq, Variable x, Variable y, Value x_min, Value x_max)
debug function: check that all 2-D constraints c in ineq are equivalent to contraint v on interval [x...
static Pvecteur new_constraint_for_coefficient_reduction_with_bounding_box(Pvecteur v, int *pcb, Variable x, Variable y, Value *px_min, Value *px_max, Value *py_min, Value *py_max)
Compute a normalized version of the constraint v and the corresponding change of basis.
static void swap_values(Value *p1, Value *p2)
#define MAX_NUMBER_OF_CONSTRAINTS
Psysteme sc_strong_normalize_and_check_feasibility2(volatile Psysteme ps, Psysteme(*check_feasibility)(Psysteme), char *(*variable_name)(Variable), int level)
Psysteme sc_strong_normalize_and_check_feasibility2 (Psysteme ps, Psysteme (*check_feasibility)(Psyst...
static void update_lower_or_upper_bound(Pvecteur *bound_p, Pvecteur *bound_base_p, Variable var, Value nb, bool lower_p)
Bounding box (not really a box most of the time)
static bool small_slope_and_first_quadrant_p(Pvecteur v)
Check that the coefficients on the first and second variables, x and y, define a increasing line.
static Value eval_2D_vecteur(Pvecteur v, Variable x, Variable y, Value xv, Value yv)
FI: a bit too specific for vecteur library?
static Psysteme sc_rational_feasibility(Psysteme sc)
Psysteme sc_strong_normalize4(Psysteme ps, char *(*variable_name)(Variable))
Psysteme sc_strong_normalize4(Psysteme ps, char * (*variable_name)(Variable))
Pcontrainte find_intermediate_constraints_recursively(Pvecteur v, Variable x, Variable y, Value lmpx, Value lmpy, Value rmpx, Value rmpy)
Find a set ineq of 2-D constraints equivalent to 2-D constraint v==ax+by+c over the interval [lmpx,...
Psysteme sc_strong_normalize_and_check_feasibility(volatile Psysteme ps, Psysteme(*check_feasibility)(Psysteme))
static void swap_value_intervals(Value *px_min, Value *px_max, Value *py_min, Value *py_max)
void sc_gcd_normalize(Psysteme ps)
sc_gcd_normalize(ps)
Psysteme sc_strong_normalize2(volatile Psysteme ps)
Psysteme sc_strong_normalize2(Psysteme ps)
static Pcontrainte small_positive_slope_reduce_coefficients_with_bounding_box(Pvecteur v, Variable x, Value x_min, Value x_max, Variable y, Value y_min __attribute__((unused)), Value y_max __attribute__((unused)))
Replace 2-D constraint v by a set of constraints when possible because variable x is bounded by [x_mi...
static Psysteme add_bounding_box_constraints(Psysteme ps, Pbase cb, Pbase lb, Pbase ub, Pvecteur l, Pvecteur u)
Add the constraints defined by cb, lb and ub in Psysteme ps.
Psysteme sc_add_normalize_eq(Psysteme ps, Pcontrainte eq)
static bool find_integer_point_to_the_left(Value x0, Value y0, Pvecteur up, Pvecteur low, Variable x, Variable y, Value xf, Value yf, Value *pfx, Value *pfy)
#define if_debug_sc_strong_normalize_and_check_feasibility2
static void update_coefficient_signs_in_vector(Pvecteur v, int cb, Variable x, Variable y)
Perform a reverse change of base to go back into the source code frame.
static bool find_integer_point_to_the_right(Value x0, Value y0, Pvecteur up, Pvecteur low, Variable x, Variable y, Value xf, Value yf, Value *pfx, Value *pfy)
Psysteme sc_safe_normalize(Psysteme ps)
Psysteme sc_safe_normalize(Psysteme ps) output : ps, normalized.
Psysteme sc_normalize(Psysteme ps)
Psysteme sc_normalize(Psysteme ps): normalisation d'un systeme d'equation et d'inequations lineaires ...
static void update_coefficient_signs_in_constraints(Pcontrainte eq, int cb, Variable x, Variable y, Value *x_min, Value *x_max, Value *y_min, Value *y_max)
Perform the inverse change of basis and update the intervals for later checks.
static bool find_first_integer_point_in_between(Value x0, Value y0, Pvecteur up_c, Pvecteur low_c, Variable xv, Variable yv, Value dx, Value dy, Value xf, Value yf __attribute__((unused)), Value *pfx, Value *pfy)
Find the first significant integer point (*pfx, *pfy) starting from (x0,y0) moving by (dx,...
#define if_debug_sc_strong_normalize_2
Psysteme sc_bounded_normalization(Psysteme ps)
Eliminate trivially redundant integer constraint using a O(n x d^2) algorithm, where n is the number ...
static Pcontrainte build_convex_constraints_from_vertices(Variable x, Variable y, int ni, int eni, Value ilmpx[ni+2], Value ilmpy[ni+2])
Use the first eni+2 points in ilmpx and ilmpy to build at most eni+1 convex constraints,...
Psysteme sc_strong_normalize(Psysteme ps)
Psysteme sc_strong_normalize(Psysteme ps)
Pcontrainte find_intermediate_constraints(Pvecteur v, Variable x, Variable y, Value lmpx, Value lmpy, Value rmpx, Value rmpy)
Find a set ineq of 2-D constraints equivalent to 2-D constraint v==ax+by+c over the interval [lmpx,...
static void simplify_constraint_with_bounding_box(Pcontrainte eq, Pbase cb, Pvecteur l, bool is_inequality_p __attribute__((unused)))
Use constants imposed by the bounding box to eliminate constant terms from constraint eq.
static void negate_value_interval(Value *pmin, Value *pmax)
package sc
static bool update_lower_and_upper_bounds(Pvecteur *ubound_p, Pvecteur *ubound_base_p, Pvecteur *lbound_p, Pvecteur *lbound_base_p, Variable var, Value nb)
Updates upper and lower bounds, (ubound_p, ubound_base_p) and (lbound_p, lbound_base_p),...
static Pvecteur vect_make_line(Variable x, Variable y, Value x0, Value y0, Value x1, Value y1)
FI: Could be moved in vecteur library...
char * variable_name(Variable v)
polynome_ri.c
Pvecteur vect_multiply(Pvecteur v, Value x)
Pvecteur vect_multiply(Pvecteur v, Value x): multiplication du vecteur v par le scalaire x,...
struct Scontrainte * succ
le type des coefficients dans les vecteurs: Value est defini dans le package arithmetique
#define VARIABLE_DEFINED_P(v)
#define TCST
VARIABLE REPRESENTANT LE TERME CONSTANT.
#define VECTEUR_NUL
DEFINITION DU VECTEUR NUL.
#define VECTEUR_UNDEFINED
void * Variable
arithmetique is a requirement for vecteur, but I do not want to inforce it in all pips files....
#define VARIABLE_UNDEFINED_P(v)
#define VARIABLE_UNDEFINED
#define base_dimension(b)
#define BASE_NULLE
MACROS SUR LES BASES.
#define OFL_CTRL
I do thing that overflows are managed in a very poor manner.
#define VECTEUR_UNDEFINED_P(v)
#define base_add_dimension(b, v)
Pvecteur vect_make(Pvecteur v, Variable var, Value val,...)
Pvecteur vect_make(v, [var, val,]* 0, val) Pvecteur v; // may be NULL, use assigne anyway Variable va...
Pbase vect_copy(Pvecteur b)
direct duplication.
Pvecteur vect_new(Variable var, Value coeff)
Pvecteur vect_new(Variable var,Value coeff): allocation d'un vecteur colineaire au vecteur de base va...
Pbase base_copy(Pbase b)
Direct duplication.
void vect_rm(Pvecteur v)
void vect_rm(Pvecteur v): desallocation des couples de v;
Pvecteur vect_add(Pvecteur v1, Pvecteur v2)
package vecteur - operations binaires
void vect_add_elem(Pvecteur *pvect, Variable var, Value val)
void vect_add_elem(Pvecteur * pvect, Variable var, Value val): addition d'un vecteur colineaire au ve...
Value vect_coeff(Variable var, Pvecteur vect)
Variable vect_coeff(Variable var, Pvecteur vect): coefficient de coordonnee var du vecteur vect —> So...
void vect_chg_coeff(Pvecteur *ppv, Variable var, Value val)
void vect_chg_coeff(Pvecteur *ppv, Variable var, Value val): mise de la coordonnee var du vecteur *pp...
void vect_normalize(Pvecteur v)
void vect_normalize(Pvecteur v): division de tous les coefficients de v par leur pgcd; "normalisation...