add isl_aff_mod_val

[platform/upstream/isl.git] / basis_reduction_templ.c

diff --git a/basis_reduction_templ.c b/basis_reduction_templ.c
index 7f027a7..7f4b28f 100644 (file)
--- a/basis_reduction_templ.c
+++ b/basis_reduction_templ.c
@@ -2,15 +2,18 @@
  * Copyright 2006-2007 Universiteit Leiden
  * Copyright 2008-2009 Katholieke Universiteit Leuven
  *
- * 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, Leiden Institute of Advanced Computer Science,
  * Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands
- * and K.U.Leuven, Departement * Computerwetenschappen, Celestijnenlaan 200A,
+ * 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)
@@ -22,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.
@@ -302,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);
-       tab->basis = isl_mat_identity(bset->ctx, 1 + tab->n_var);
+       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;