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

diff --git a/basis_reduction_templ.c b/basis_reduction_templ.c
index 7d6e2e7..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)
@@ -10,7 +25,7 @@ static void save_alpha(GBR_LP *lp, int first, int n, GBR_type *alpha)
 }
 
 /* Compute a reduced basis for the set represented by the tableau "tab".
- * tab->basis, must be initialized by the calling function to an affine
+ * 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.
@@ -290,15 +305,46 @@ error:
 	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;
 
-	isl_assert(bset->ctx, bset->n_eq == 0, return NULL);
+	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;
 
-	tab = isl_tab_from_basic_set(bset);
-	tab->basis = isl_mat_identity(bset->ctx, 1 + tab->n_var);
+	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;