-#include "isl_mat.h"
-#include "isl_seq.h"
+/*
+ * Copyright 2008-2009 Katholieke Universiteit Leuven
+ *
+ * Use of this software is governed by the GNU LGPLv2.1 license
+ *
+ * Written by Sven Verdoolaege, K.U.Leuven, Departement
+ * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
+ */
+
+#include <isl_mat_private.h>
+#include <isl/seq.h>
#include "isl_map_private.h"
#include "isl_equalities.h"
A = isl_mat_left_hermite(A, 0, NULL, NULL);
T = isl_mat_sub_alloc(A->ctx, A->row, 0, A->n_row, 0, A->n_row);
T = isl_mat_lin_to_aff(T);
+ if (!T)
+ goto error;
isl_int_set(T->row[0][0], D);
T = isl_mat_right_inverse(T);
+ if (!T)
+ goto error;
isl_assert(T->ctx, isl_int_is_one(T->row[0][0]), goto error);
T = isl_mat_transpose(T);
isl_mat_free(A);
* then we divide this row of A by the common factor, unless gcd(A_i) = 0.
* In the later case, we simply drop the row (in both A and d).
*
- * If there are no rows left in A, the G is the identity matrix. Otherwise,
+ * If there are no rows left in A, then G is the identity matrix. Otherwise,
* for each row i, we now determine the lattice of integer vectors
* that satisfies this row. Let U_i be the unimodular extension of the
* row A_i. This unimodular extension exists because gcd(A_i) = 1.
*
* M x - c = 0
*
- * this function computes unimodular transformation from a lower-dimensional
+ * this function computes a unimodular transformation from a lower-dimensional
* space to the original space that bijectively maps the integer points x'
* in the lower-dimensional space to the integer points x in the original
* space that satisfy the equalities.
*
- * The input is given as a matrix B = [ -c M ] and the out is a
+ * The input is given as a matrix B = [ -c M ] and the output is a
* matrix that maps [1 x'] to [1 x].
* If T2 is not NULL, then *T2 is set to a matrix mapping [1 x] to [1 x'].
*
*
* If any of the c' is non-integer, then the original set has no
* integer solutions (since the x' are a unimodular transformation
- * of the x).
+ * of the x) and a zero-column matrix is returned.
* Otherwise, the transformation is given by
*
* x = U1 H1^{-1} c + U2 x2'
isl_mat_free(U);
return -1;
}
+
+/* Check if dimension dim belongs to a residue class
+ * i_dim \equiv r mod m
+ * with m != 1 and if so return m in *modulo and r in *residue.
+ * As a special case, when i_dim has a fixed value v, then
+ * *modulo is set to 0 and *residue to v.
+ *
+ * If i_dim does not belong to such a residue class, then *modulo
+ * is set to 1 and *residue is set to 0.
+ */
+int isl_set_dim_residue_class(struct isl_set *set,
+ int pos, isl_int *modulo, isl_int *residue)
+{
+ isl_int m;
+ isl_int r;
+ int i;
+
+ if (!set || !modulo || !residue)
+ return -1;
+
+ if (set->n == 0) {
+ isl_int_set_si(*modulo, 0);
+ isl_int_set_si(*residue, 0);
+ return 0;
+ }
+
+ if (isl_basic_set_dim_residue_class(set->p[0], pos, modulo, residue)<0)
+ return -1;
+
+ if (set->n == 1)
+ return 0;
+
+ if (isl_int_is_one(*modulo))
+ return 0;
+
+ isl_int_init(m);
+ isl_int_init(r);
+
+ for (i = 1; i < set->n; ++i) {
+ if (isl_basic_set_dim_residue_class(set->p[0], pos, &m, &r) < 0)
+ goto error;
+ isl_int_gcd(*modulo, *modulo, m);
+ if (!isl_int_is_zero(*modulo))
+ isl_int_fdiv_r(*residue, *residue, *modulo);
+ if (isl_int_is_one(*modulo))
+ break;
+ if (!isl_int_is_zero(*modulo))
+ isl_int_fdiv_r(r, r, *modulo);
+ if (isl_int_ne(*residue, r)) {
+ isl_int_set_si(*modulo, 1);
+ isl_int_set_si(*residue, 0);
+ break;
+ }
+ }
+
+ isl_int_clear(m);
+ isl_int_clear(r);
+
+ return 0;
+error:
+ isl_int_clear(m);
+ isl_int_clear(r);
+ return -1;
+}