X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_polynomial.c;h=45676e5e83ac81f9eb0e4fb0162166aad85c3f8d;hb=19596bc4e5cd282b2e75d17077b1aaaeacbfd6f9;hp=2341bab09a803e6435b1b322a8f6caff4083a244;hpb=0d458c47aefdc037512282a3250de99d9d24b8c9;p=platform%2Fupstream%2Fisl.git

diff --git a/isl_polynomial.c b/isl_polynomial.c
index 2341bab..45676e5 100644
--- a/isl_polynomial.c
+++ b/isl_polynomial.c
@@ -1,7 +1,7 @@
 /*
  * Copyright 2010      INRIA Saclay
  *
- * Use of this software is governed by the GNU LGPLv2.1 license
+ * Use of this software is governed by the MIT license
  *
  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
@@ -20,11 +20,11 @@
 #include <isl_polynomial_private.h>
 #include <isl_point_private.h>
 #include <isl_space_private.h>
-#include <isl_div_private.h>
 #include <isl_mat_private.h>
 #include <isl_range.h>
 #include <isl_local_space_private.h>
 #include <isl_aff_private.h>
+#include <isl_val_private.h>
 #include <isl_config.h>
 
 static unsigned pos(__isl_keep isl_space *dim, enum isl_dim_type type)
@@ -802,6 +802,60 @@ error:
 	return NULL;
 }
 
+/* Multiply the constant polynomial "up" by "v".
+ */
+static __isl_give struct isl_upoly *isl_upoly_cst_scale_val(
+	__isl_take struct isl_upoly *up, __isl_keep isl_val *v)
+{
+	struct isl_upoly_cst *cst;
+
+	if (isl_upoly_is_zero(up))
+		return up;
+
+	up = isl_upoly_cow(up);
+	if (!up)
+		return NULL;
+
+	cst = isl_upoly_as_cst(up);
+
+	isl_int_mul(cst->n, cst->n, v->n);
+	isl_int_mul(cst->d, cst->d, v->d);
+	isl_upoly_cst_reduce(cst);
+
+	return up;
+}
+
+/* Multiply the polynomial "up" by "v".
+ */
+static __isl_give struct isl_upoly *isl_upoly_scale_val(
+	__isl_take struct isl_upoly *up, __isl_keep isl_val *v)
+{
+	int i;
+	struct isl_upoly_rec *rec;
+
+	if (!up)
+		return NULL;
+
+	if (isl_upoly_is_cst(up))
+		return isl_upoly_cst_scale_val(up, v);
+
+	up = isl_upoly_cow(up);
+	rec = isl_upoly_as_rec(up);
+	if (!rec)
+		goto error;
+
+	for (i = 0; i < rec->n; ++i) {
+		rec->p[i] = isl_upoly_scale_val(rec->p[i], v);
+		if (!rec->p[i])
+			goto error;
+	}
+
+	return up;
+error:
+	isl_upoly_free(up);
+	return NULL;
+}
+
 __isl_give struct isl_upoly *isl_upoly_mul_cst(__isl_take struct isl_upoly *up1,
 	__isl_take struct isl_upoly *up2)
 {
@@ -1464,6 +1518,48 @@ __isl_give isl_qpolynomial *isl_qpolynomial_scale(
 	return isl_qpolynomial_mul_isl_int(qp, v);
 }
 
+/* Multiply "qp" by "v".
+ */
+__isl_give isl_qpolynomial *isl_qpolynomial_scale_val(
+	__isl_take isl_qpolynomial *qp, __isl_take isl_val *v)
+{
+	if (!qp || !v)
+		goto error;
+
+	if (!isl_val_is_rat(v))
+		isl_die(isl_qpolynomial_get_ctx(qp), isl_error_invalid,
+			"expecting rational factor", goto error);
+
+	if (isl_val_is_one(v)) {
+		isl_val_free(v);
+		return qp;
+	}
+
+	if (isl_val_is_zero(v)) {
+		isl_space *space;
+
+		space = isl_qpolynomial_get_domain_space(qp);
+		isl_qpolynomial_free(qp);
+		isl_val_free(v);
+		return isl_qpolynomial_zero_on_domain(space);
+	}
+
+	qp = isl_qpolynomial_cow(qp);
+	if (!qp)
+		goto error;
+
+	qp->upoly = isl_upoly_scale_val(qp->upoly, v);
+	if (!qp->upoly)
+		qp = isl_qpolynomial_free(qp);
+
+	isl_val_free(v);
+	return qp;
+error:
+	isl_val_free(v);
+	isl_qpolynomial_free(qp);
+	return NULL;
+}
+
 __isl_give isl_qpolynomial *isl_qpolynomial_mul(__isl_take isl_qpolynomial *qp1,
 	__isl_take isl_qpolynomial *qp2)
 {
@@ -1614,6 +1710,42 @@ int isl_qpolynomial_is_cst(__isl_keep isl_qpolynomial *qp,
 	return 1;
 }
 
+/* Return the constant term of "up".
+ */
+static __isl_give isl_val *isl_upoly_get_constant_val(
+	__isl_keep struct isl_upoly *up)
+{
+	struct isl_upoly_cst *cst;
+
+	if (!up)
+		return NULL;
+
+	while (!isl_upoly_is_cst(up)) {
+		struct isl_upoly_rec *rec;
+
+		rec = isl_upoly_as_rec(up);
+		if (!rec)
+			return NULL;
+		up = rec->p[0];
+	}
+
+	cst = isl_upoly_as_cst(up);
+	if (!cst)
+		return NULL;
+	return isl_val_rat_from_isl_int(cst->up.ctx, cst->n, cst->d);
+}
+
+/* Return the constant term of "qp".
+ */
+__isl_give isl_val *isl_qpolynomial_get_constant_val(
+	__isl_keep isl_qpolynomial *qp)
+{
+	if (!qp)
+		return NULL;
+
+	return isl_upoly_get_constant_val(qp->upoly);
+}
+
 int isl_upoly_is_affine(__isl_keep struct isl_upoly *up)
 {
 	int is_cst;
@@ -2127,75 +2259,51 @@ error:
 	return NULL;
 }
 
-/* Assumes each div only depends on earlier divs.
- */
-__isl_give isl_qpolynomial *isl_qpolynomial_div_pow(__isl_take isl_div *div,
-	int power)
+__isl_give isl_qpolynomial *isl_qpolynomial_rat_cst_on_domain(
+	__isl_take isl_space *dim, const isl_int n, const isl_int d)
 {
-	struct isl_qpolynomial *qp = NULL;
-	struct isl_upoly_rec *rec;
+	struct isl_qpolynomial *qp;
 	struct isl_upoly_cst *cst;
-	int i, d;
-	int pos;
 
-	if (!div)
+	if (!dim)
 		return NULL;
 
-	d = div->line - div->bmap->div;
-
-	pos = isl_space_dim(div->bmap->dim, isl_dim_all) + d;
-	rec = isl_upoly_alloc_rec(div->ctx, pos, 1 + power);
-	qp = isl_qpolynomial_alloc(isl_basic_map_get_space(div->bmap),
-				   div->bmap->n_div, &rec->up);
+	qp = isl_qpolynomial_alloc(dim, 0, isl_upoly_zero(dim->ctx));
 	if (!qp)
-		goto error;
-
-	for (i = 0; i < div->bmap->n_div; ++i)
-		isl_seq_cpy(qp->div->row[i], div->bmap->div[i], qp->div->n_col);
-
-	for (i = 0; i < 1 + power; ++i) {
-		rec->p[i] = isl_upoly_zero(div->ctx);
-		if (!rec->p[i])
-			goto error;
-		rec->n++;
-	}
-	cst = isl_upoly_as_cst(rec->p[power]);
-	isl_int_set_si(cst->n, 1);
-
-	isl_div_free(div);
+		return NULL;
 
-	qp = reduce_divs(qp);
+	cst = isl_upoly_as_cst(qp->upoly);
+	isl_int_set(cst->n, n);
+	isl_int_set(cst->d, d);
 
 	return qp;
-error:
-	isl_qpolynomial_free(qp);
-	isl_div_free(div);
-	return NULL;
-}
-
-__isl_give isl_qpolynomial *isl_qpolynomial_div(__isl_take isl_div *div)
-{
-	return isl_qpolynomial_div_pow(div, 1);
 }
 
-__isl_give isl_qpolynomial *isl_qpolynomial_rat_cst_on_domain(
-	__isl_take isl_space *dim, const isl_int n, const isl_int d)
+/* Return an isl_qpolynomial that is equal to "val" on domain space "domain".
+ */
+__isl_give isl_qpolynomial *isl_qpolynomial_val_on_domain(
+	__isl_take isl_space *domain, __isl_take isl_val *val)
 {
-	struct isl_qpolynomial *qp;
+	isl_qpolynomial *qp;
 	struct isl_upoly_cst *cst;
 
-	if (!dim)
-		return NULL;
+	if (!domain || !val)
+		goto error;
 
-	qp = isl_qpolynomial_alloc(dim, 0, isl_upoly_zero(dim->ctx));
+	qp = isl_qpolynomial_alloc(domain, 0, isl_upoly_zero(domain->ctx));
 	if (!qp)
-		return NULL;
+		goto error;
 
 	cst = isl_upoly_as_cst(qp->upoly);
-	isl_int_set(cst->n, n);
-	isl_int_set(cst->d, d);
+	isl_int_set(cst->n, val->n);
+	isl_int_set(cst->d, val->d);
 
+	isl_val_free(val);
 	return qp;
+error:
+	isl_space_free(domain);
+	isl_val_free(val);
+	return NULL;
 }
 
 static int up_set_active(__isl_keep struct isl_upoly *up, int *active, int d)
@@ -2555,7 +2663,7 @@ __isl_give isl_qpolynomial *isl_qpolynomial_substitute_equalities(
 	if (!qp || !eq)
 		goto error;
 	if (qp->div->n_row > 0)
-		eq = isl_basic_set_add(eq, isl_dim_set, qp->div->n_row);
+		eq = isl_basic_set_add_dims(eq, isl_dim_set, qp->div->n_row);
 	return isl_qpolynomial_substitute_equalities_lifted(qp, eq);
 error:
 	isl_basic_set_free(eq);
@@ -2619,6 +2727,15 @@ error:
 	return NULL;
 }
 
+__isl_give isl_qpolynomial *isl_qpolynomial_gist_params(
+	__isl_take isl_qpolynomial *qp, __isl_take isl_set *context)
+{
+	isl_space *space = isl_qpolynomial_get_domain_space(qp);
+	isl_set *dom_context = isl_set_universe(space);
+	dom_context = isl_set_intersect_params(dom_context, context);
+	return isl_qpolynomial_gist(qp, dom_context);
+}
+
 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_from_qpolynomial(
 	__isl_take isl_qpolynomial *qp)
 {
@@ -2648,6 +2765,10 @@ __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_from_qpolynomial(
 #define IS_ZERO is_zero
 #undef FIELD
 #define FIELD qp
+#undef DEFAULT_IS_ZERO
+#define DEFAULT_IS_ZERO 1
+
+#define NO_PULLBACK
 
 #include <isl_pw_templ.c>
 
@@ -2675,6 +2796,13 @@ int isl_pw_qpolynomial_is_one(__isl_keep isl_pw_qpolynomial *pwqp)
 	return isl_qpolynomial_is_one(pwqp->p[0].qp);
 }
 
+__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_add(
+	__isl_take isl_pw_qpolynomial *pwqp1,
+	__isl_take isl_pw_qpolynomial *pwqp2)
+{
+	return isl_pw_qpolynomial_union_add_(pwqp1, pwqp2);
+}
+
 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_mul(
 	__isl_take isl_pw_qpolynomial *pwqp1,
 	__isl_take isl_pw_qpolynomial *pwqp2)
@@ -3247,7 +3375,7 @@ int isl_qpolynomial_as_polynomial_on_domain(__isl_keep isl_qpolynomial *qp,
 	dim = isl_space_add_dims(dim, isl_dim_set, qp->div->n_row);
 	poly = isl_qpolynomial_alloc(dim, 0, isl_upoly_copy(qp->upoly));
 	bset = isl_basic_set_copy(bset);
-	bset = isl_basic_set_add(bset, isl_dim_set, qp->div->n_row);
+	bset = isl_basic_set_add_dims(bset, isl_dim_set, qp->div->n_row);
 	bset = add_div_constraints(bset, div);
 
 	return fn(bset, poly, user);
@@ -3516,7 +3644,7 @@ __isl_give isl_term *isl_term_dup(__isl_keep isl_term *term)
 	isl_term *dup;
 	unsigned total;
 
-	if (term)
+	if (!term)
 		return NULL;
 
 	total = isl_space_dim(term->dim, isl_dim_all) + term->div->n_row;
@@ -3595,6 +3723,17 @@ void isl_term_get_den(__isl_keep isl_term *term, isl_int *d)
 	isl_int_set(*d, term->d);
 }
 
+/* Return the coefficient of the term "term".
+ */
+__isl_give isl_val *isl_term_get_coefficient_val(__isl_keep isl_term *term)
+{
+	if (!term)
+		return NULL;
+
+	return isl_val_rat_from_isl_int(isl_term_get_ctx(term),
+					term->n, term->d);
+}
+
 int isl_term_get_exp(__isl_keep isl_term *term,
 	enum isl_dim_type type, unsigned pos)
 {
@@ -3611,11 +3750,10 @@ int isl_term_get_exp(__isl_keep isl_term *term,
 	return term->pow[pos];
 }
 
-__isl_give isl_div *isl_term_get_div(__isl_keep isl_term *term, unsigned pos)
+__isl_give isl_aff *isl_term_get_div(__isl_keep isl_term *term, unsigned pos)
 {
-	isl_basic_map *bmap;
-	unsigned total;
-	int k;
+	isl_local_space *ls;
+	isl_aff *aff;
 
 	if (!term)
 		return NULL;
@@ -3623,23 +3761,17 @@ __isl_give isl_div *isl_term_get_div(__isl_keep isl_term *term, unsigned pos)
 	isl_assert(term->dim->ctx, pos < isl_term_dim(term, isl_dim_div),
 			return NULL);
 
-	total = term->div->n_col - term->div->n_row - 2;
-	/* No nested divs for now */
-	isl_assert(term->dim->ctx,
-		isl_seq_first_non_zero(term->div->row[pos] + 2 + total,
-					term->div->n_row) == -1,
-		return NULL);
+	ls = isl_local_space_alloc_div(isl_space_copy(term->dim),
+					isl_mat_copy(term->div));
+	aff = isl_aff_alloc(ls);
+	if (!aff)
+		return NULL;
 
-	bmap = isl_basic_map_alloc_space(isl_space_copy(term->dim), 1, 0, 0);
-	if ((k = isl_basic_map_alloc_div(bmap)) < 0)
-		goto error;
+	isl_seq_cpy(aff->v->el, term->div->row[pos], aff->v->size);
 
-	isl_seq_cpy(bmap->div[k], term->div->row[pos], 2 + total);
+	aff = isl_aff_normalize(aff);
 
-	return isl_basic_map_div(bmap, k);
-error:
-	isl_basic_map_free(bmap);
-	return NULL;
+	return aff;
 }
 
 __isl_give isl_term *isl_upoly_foreach_term(__isl_keep struct isl_upoly *up,
@@ -3919,7 +4051,7 @@ __isl_give isl_qpolynomial *isl_qpolynomial_morph_domain(
 	int n_sub;
 	isl_ctx *ctx;
 	struct isl_upoly **subs;
-	isl_mat *mat;
+	isl_mat *mat, *diag;
 
 	qp = isl_qpolynomial_cow(qp);
 	if (!qp || !morph)
@@ -3949,8 +4081,10 @@ __isl_give isl_qpolynomial *isl_qpolynomial_morph_domain(
 		isl_upoly_free(subs[i]);
 	free(subs);
 
-	mat = isl_mat_diagonal(isl_mat_identity(ctx, 1), isl_mat_copy(morph->inv));
-	mat = isl_mat_diagonal(mat, isl_mat_identity(ctx, qp->div->n_row));
+	diag = isl_mat_diag(ctx, 1, morph->inv->row[0][0]);
+	mat = isl_mat_diagonal(diag, isl_mat_copy(morph->inv));
+	diag = isl_mat_diag(ctx, qp->div->n_row, morph->inv->row[0][0]);
+	mat = isl_mat_diagonal(mat, diag);
 	qp->div = isl_mat_product(qp->div, mat);
 	isl_space_free(qp->dim);
 	qp->dim = isl_space_copy(morph->ran->dim);
@@ -3993,52 +4127,11 @@ error:
 	return NULL;
 }
 
-__isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_sub(
-	__isl_take isl_union_pw_qpolynomial *upwqp1,
-	__isl_take isl_union_pw_qpolynomial *upwqp2)
-{
-	return isl_union_pw_qpolynomial_add(upwqp1,
-					isl_union_pw_qpolynomial_neg(upwqp2));
-}
-
-static int mul_entry(void **entry, void *user)
-{
-	struct isl_union_pw_qpolynomial_match_bin_data *data = user;
-	uint32_t hash;
-	struct isl_hash_table_entry *entry2;
-	isl_pw_qpolynomial *pwpq = *entry;
-	int empty;
-
-	hash = isl_space_get_hash(pwpq->dim);
-	entry2 = isl_hash_table_find(data->u2->dim->ctx, &data->u2->table,
-				     hash, &has_dim, pwpq->dim, 0);
-	if (!entry2)
-		return 0;
-
-	pwpq = isl_pw_qpolynomial_copy(pwpq);
-	pwpq = isl_pw_qpolynomial_mul(pwpq,
-				      isl_pw_qpolynomial_copy(entry2->data));
-
-	empty = isl_pw_qpolynomial_is_zero(pwpq);
-	if (empty < 0) {
-		isl_pw_qpolynomial_free(pwpq);
-		return -1;
-	}
-	if (empty) {
-		isl_pw_qpolynomial_free(pwpq);
-		return 0;
-	}
-
-	data->res = isl_union_pw_qpolynomial_add_pw_qpolynomial(data->res, pwpq);
-
-	return 0;
-}
-
 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_mul(
 	__isl_take isl_union_pw_qpolynomial *upwqp1,
 	__isl_take isl_union_pw_qpolynomial *upwqp2)
 {
-	return match_bin_op(upwqp1, upwqp2, &mul_entry);
+	return match_bin_op(upwqp1, upwqp2, &isl_pw_qpolynomial_mul);
 }
 
 /* Reorder the columns of the given div definitions according to the
@@ -4499,7 +4592,7 @@ error:
 
 /* Drop all floors in "qp", turning each integer division [a/m] into
  * a rational division a/m.  If "down" is set, then the integer division
- * is replaces by (a-(m-1))/m instead.
+ * is replaced by (a-(m-1))/m instead.
  */
 static __isl_give isl_qpolynomial *qp_drop_floors(
 	__isl_take isl_qpolynomial *qp, int down)