X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=basis_reduction_templ.c;h=7f4b28f06c9fc95557fc06e1e27d8ef4d2aa01e6;hb=1a9c7afa1e0ca242fb348575afbf8e493deffbfd;hp=988bde13346a34a1c9f073a2fbecd56c019745ee;hpb=c602fcb7955b716879370b3f93a3c996e66fe863;p=platform%2Fupstream%2Fisl.git

diff --git a/basis_reduction_templ.c b/basis_reduction_templ.c
index 988bde1..7f4b28f 100644
--- a/basis_reduction_templ.c
+++ b/basis_reduction_templ.c
@@ -1,4 +1,19 @@
+/*
+ * Copyright 2006-2007 Universiteit Leiden
+ * Copyright 2008-2009 Katholieke Universiteit Leuven
+ *
+ * Use of this software is governed by the MIT license
+ *
+ * Written by Sven Verdoolaege, Leiden Institute of Advanced Computer Science,
+ * Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands
+ * and K.U.Leuven, Departement Computerwetenschappen, Celestijnenlaan 200A,
+ * B-3001 Leuven, Belgium
+ */
+
 #include <stdlib.h>
+#include <isl_ctx_private.h>
+#include <isl_map_private.h>
+#include <isl_options_private.h>
 #include "isl_basis_reduction.h"
 
 static void save_alpha(GBR_LP *lp, int first, int n, GBR_type *alpha)
@@ -9,19 +24,32 @@ static void save_alpha(GBR_LP *lp, int first, int n, GBR_type *alpha)
 		GBR_lp_get_alpha(lp, first + i, &alpha[i]);
 }
 
-/* This function implements the algorithm described in
+/* Compute a reduced basis for the set represented by the tableau "tab".
+ * tab->basis, which must be initialized by the calling function to an affine
+ * unimodular basis, is updated to reflect the reduced basis.
+ * The first tab->n_zero rows of the basis (ignoring the constant row)
+ * are assumed to correspond to equalities and are left untouched.
+ * tab->n_zero is updated to reflect any additional equalities that
+ * have been detected in the first rows of the new basis.
+ * The final tab->n_unbounded rows of the basis are assumed to correspond
+ * to unbounded directions and are also left untouched.
+ * In particular this means that the remaining rows are assumed to
+ * correspond to bounded directions.
+ *
+ * This function implements the algorithm described in
  * "An Implementation of the Generalized Basis Reduction Algorithm
  *  for Integer Programming" of Cook el al. to compute a reduced basis.
  * We use \epsilon = 1/4.
  *
- * If ctx->gbr_only_first is set, the user is only interested
+ * If ctx->opt->gbr_only_first is set, the user is only interested
  * in the first direction.  In this case we stop the basis reduction when
  * the width in the first direction becomes smaller than 2.
  */
-struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset)
+struct isl_tab *isl_tab_compute_reduced_basis(struct isl_tab *tab)
 {
 	unsigned dim;
-	struct isl_mat *basis;
+	struct isl_ctx *ctx;
+	struct isl_mat *B;
 	int unbounded;
 	int i;
 	GBR_LP *lp = NULL;
@@ -38,22 +66,29 @@ struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset)
 	GBR_type mu_F[2];
 	GBR_type two;
 	GBR_type one;
-	int n_zero = 0;
 	int empty = 0;
 	int fixed = 0;
 	int fixed_saved = 0;
 	int mu_fixed[2];
+	int n_bounded;
+	int gbr_only_first;
 
-	if (!bset)
+	if (!tab)
 		return NULL;
 
-	dim = isl_basic_set_total_dim(bset);
-	basis = isl_mat_identity(bset->ctx, dim);
-	if (!basis)
-		return NULL;
+	if (tab->empty)
+		return tab;
+
+	ctx = tab->mat->ctx;
+	gbr_only_first = ctx->opt->gbr_only_first;
+	dim = tab->n_var;
+	B = tab->basis;
+	if (!B)
+		return tab;
 
-	if (dim == 1)
-		return basis;
+	n_bounded = dim - tab->n_unbounded;
+	if (n_bounded <= tab->n_zero + 1)
+		return tab;
 
 	isl_int_init(tmp);
 	isl_int_init(mu[0]);
@@ -68,19 +103,19 @@ struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset)
 	GBR_init(two);
 	GBR_init(one);
 
-	b_tmp = isl_vec_alloc(bset->ctx, dim);
+	b_tmp = isl_vec_alloc(ctx, dim);
 	if (!b_tmp)
 		goto error;
 
-	F = isl_alloc_array(bset->ctx, GBR_type, dim);
-	alpha_buffer[0] = isl_alloc_array(bset->ctx, GBR_type, dim);
-	alpha_buffer[1] = isl_alloc_array(bset->ctx, GBR_type, dim);
+	F = isl_alloc_array(ctx, GBR_type, n_bounded);
+	alpha_buffer[0] = isl_alloc_array(ctx, GBR_type, n_bounded);
+	alpha_buffer[1] = isl_alloc_array(ctx, GBR_type, n_bounded);
 	alpha_saved = alpha_buffer[0];
 
 	if (!F || !alpha_buffer[0] || !alpha_buffer[1])
 		goto error;
 
-	for (i = 0; i < dim; ++i) {
+	for (i = 0; i < n_bounded; ++i) {
 		GBR_init(F[i]);
 		GBR_init(alpha_buffer[0][i]);
 		GBR_init(alpha_buffer[1][i]);
@@ -89,34 +124,34 @@ struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset)
 	GBR_set_ui(two, 2);
 	GBR_set_ui(one, 1);
 
-	lp = GBR_lp_init(bset);
+	lp = GBR_lp_init(tab);
 	if (!lp)
 		goto error;
 
-	i = 0;
+	i = tab->n_zero;
 
-	GBR_lp_set_obj(lp, basis->row[0], dim);
-	bset->ctx->stats->gbr_solved_lps++;
+	GBR_lp_set_obj(lp, B->row[1+i]+1, dim);
+	ctx->stats->gbr_solved_lps++;
 	unbounded = GBR_lp_solve(lp);
-	isl_assert(bset->ctx, !unbounded, goto error);
-	GBR_lp_get_obj_val(lp, &F[0]);
+	isl_assert(ctx, !unbounded, goto error);
+	GBR_lp_get_obj_val(lp, &F[i]);
 
-	if (GBR_lt(F[0], one)) {
-		if (!GBR_is_zero(F[0])) {
-			empty = GBR_lp_cut(lp, basis->row[0]);
+	if (GBR_lt(F[i], one)) {
+		if (!GBR_is_zero(F[i])) {
+			empty = GBR_lp_cut(lp, B->row[1+i]+1);
 			if (empty)
 				goto done;
-			GBR_set_ui(F[0], 0);
+			GBR_set_ui(F[i], 0);
 		}
-		n_zero++;
+		tab->n_zero++;
 	}
 
 	do {
-		if (i+1 == n_zero) {
-			GBR_lp_set_obj(lp, basis->row[i+1], dim);
-			bset->ctx->stats->gbr_solved_lps++;
+		if (i+1 == tab->n_zero) {
+			GBR_lp_set_obj(lp, B->row[1+i+1]+1, dim);
+			ctx->stats->gbr_solved_lps++;
 			unbounded = GBR_lp_solve(lp);
-			isl_assert(bset->ctx, !unbounded, goto error);
+			isl_assert(ctx, !unbounded, goto error);
 			GBR_lp_get_obj_val(lp, &F_new);
 			fixed = GBR_lp_is_fixed(lp);
 			GBR_set_ui(alpha, 0);
@@ -127,11 +162,11 @@ struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset)
 			fixed = fixed_saved;
 			GBR_set(alpha, alpha_saved[i]);
 		} else {
-			row = GBR_lp_add_row(lp, basis->row[i], dim);
-			GBR_lp_set_obj(lp, basis->row[i+1], dim);
-			bset->ctx->stats->gbr_solved_lps++;
+			row = GBR_lp_add_row(lp, B->row[1+i]+1, dim);
+			GBR_lp_set_obj(lp, B->row[1+i+1]+1, dim);
+			ctx->stats->gbr_solved_lps++;
 			unbounded = GBR_lp_solve(lp);
-			isl_assert(bset->ctx, !unbounded, goto error);
+			isl_assert(ctx, !unbounded, goto error);
 			GBR_lp_get_obj_val(lp, &F_new);
 			fixed = GBR_lp_is_fixed(lp);
 
@@ -140,7 +175,8 @@ struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset)
 			if (i > 0)
 				save_alpha(lp, row-i, i, alpha_saved);
 
-			GBR_lp_del_row(lp);
+			if (GBR_lp_del_row(lp) < 0)
+				goto error;
 		}
 		GBR_set(F[i+1], F_new);
 
@@ -155,12 +191,12 @@ struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset)
 			for (j = 0; j <= 1; ++j) {
 				isl_int_set(tmp, mu[j]);
 				isl_seq_combine(b_tmp->el,
-						bset->ctx->one, basis->row[i+1],
-						tmp, basis->row[i], dim);
+						ctx->one, B->row[1+i+1]+1,
+						tmp, B->row[1+i]+1, dim);
 				GBR_lp_set_obj(lp, b_tmp->el, dim);
-				bset->ctx->stats->gbr_solved_lps++;
+				ctx->stats->gbr_solved_lps++;
 				unbounded = GBR_lp_solve(lp);
-				isl_assert(bset->ctx, !unbounded, goto error);
+				isl_assert(ctx, !unbounded, goto error);
 				GBR_lp_get_obj_val(lp, &mu_F[j]);
 				mu_fixed[j] = GBR_lp_is_fixed(lp);
 				if (i > 0)
@@ -177,18 +213,17 @@ struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset)
 			fixed = mu_fixed[j];
 			alpha_saved = alpha_buffer[j];
 		}
-		isl_seq_combine(basis->row[i+1],
-				bset->ctx->one, basis->row[i+1],
-				tmp, basis->row[i], dim);
+		isl_seq_combine(B->row[1+i+1]+1, ctx->one, B->row[1+i+1]+1,
+				tmp, B->row[1+i]+1, dim);
 
-		if (i+1 == n_zero && fixed) {
+		if (i+1 == tab->n_zero && fixed) {
 			if (!GBR_is_zero(F[i+1])) {
-				empty = GBR_lp_cut(lp, basis->row[i+1]);
+				empty = GBR_lp_cut(lp, B->row[1+i+1]+1);
 				if (empty)
 					goto done;
 				GBR_set_ui(F[i+1], 0);
 			}
-			n_zero++;
+			tab->n_zero++;
 		}
 
 		GBR_set(F_old, F[i]);
@@ -200,48 +235,48 @@ struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset)
 		GBR_set_ui(mu_F[1], 3);
 		GBR_mul(mu_F[1], mu_F[1], F_old);
 		if (GBR_lt(mu_F[0], mu_F[1])) {
-			basis = isl_mat_swap_rows(basis, i, i + 1);
-			if (i > 0) {
+			B = isl_mat_swap_rows(B, 1 + i, 1 + i + 1);
+			if (i > tab->n_zero) {
 				use_saved = 1;
 				GBR_set(F_saved, F_new);
 				fixed_saved = fixed;
-				GBR_lp_del_row(lp);
+				if (GBR_lp_del_row(lp) < 0)
+					goto error;
 				--i;
 			} else {
-				GBR_set(F[0], F_new);
-				if (bset->ctx->gbr_only_first &&
-				    GBR_lt(F[0], two))
+				GBR_set(F[tab->n_zero], F_new);
+				if (gbr_only_first && GBR_lt(F[tab->n_zero], two))
 					break;
 
 				if (fixed) {
-					if (!GBR_is_zero(F[0])) {
-						empty = GBR_lp_cut(lp, basis->row[0]);
+					if (!GBR_is_zero(F[tab->n_zero])) {
+						empty = GBR_lp_cut(lp, B->row[1+tab->n_zero]+1);
 						if (empty)
 							goto done;
-						GBR_set_ui(F[0], 0);
+						GBR_set_ui(F[tab->n_zero], 0);
 					}
-					n_zero++;
+					tab->n_zero++;
 				}
 			}
 		} else {
-			GBR_lp_add_row(lp, basis->row[i], dim);
+			GBR_lp_add_row(lp, B->row[1+i]+1, dim);
 			++i;
 		}
-	} while (i < dim-1);
+	} while (i < n_bounded - 1);
 
 	if (0) {
 done:
 		if (empty < 0) {
 error:
-			isl_mat_free(basis);
-			basis = NULL;
+			isl_mat_free(B);
+			B = NULL;
 		}
 	}
 
 	GBR_lp_delete(lp);
 
 	if (alpha_buffer[1])
-		for (i = 0; i < dim; ++i) {
+		for (i = 0; i < n_bounded; ++i) {
 			GBR_clear(F[i]);
 			GBR_clear(alpha_buffer[0][i]);
 			GBR_clear(alpha_buffer[1][i]);
@@ -265,5 +300,58 @@ error:
 	isl_int_clear(mu[0]);
 	isl_int_clear(mu[1]);
 
+	tab->basis = B;
+
+	return tab;
+}
+
+/* Compute an affine form of a reduced basis of the given basic
+ * non-parametric set, which is assumed to be bounded and not
+ * include any integer divisions.
+ * The first column and the first row correspond to the constant term.
+ *
+ * If the input contains any equalities, we first create an initial
+ * basis with the equalities first.  Otherwise, we start off with
+ * the identity matrix.
+ */
+struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset)
+{
+	struct isl_mat *basis;
+	struct isl_tab *tab;
+
+	if (!bset)
+		return NULL;
+
+	if (isl_basic_set_dim(bset, isl_dim_div) != 0)
+		isl_die(bset->ctx, isl_error_invalid,
+			"no integer division allowed", return NULL);
+	if (isl_basic_set_dim(bset, isl_dim_param) != 0)
+		isl_die(bset->ctx, isl_error_invalid,
+			"no parameters allowed", return NULL);
+
+	tab = isl_tab_from_basic_set(bset, 0);
+	if (!tab)
+		return NULL;
+
+	if (bset->n_eq == 0)
+		tab->basis = isl_mat_identity(bset->ctx, 1 + tab->n_var);
+	else {
+		isl_mat *eq;
+		unsigned nvar = isl_basic_set_total_dim(bset);
+		eq = isl_mat_sub_alloc6(bset->ctx, bset->eq, 0, bset->n_eq,
+					1, nvar);
+		eq = isl_mat_left_hermite(eq, 0, NULL, &tab->basis);
+		tab->basis = isl_mat_lin_to_aff(tab->basis);
+		tab->n_zero = bset->n_eq;
+		isl_mat_free(eq);
+	}
+	tab = isl_tab_compute_reduced_basis(tab);
+	if (!tab)
+		return NULL;
+
+	basis = isl_mat_copy(tab->basis);
+
+	isl_tab_free(tab);
+
 	return basis;
 }