isl_basic_set_sample: break early if sample found in basic_set_range

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

diff --git a/isl_mat.c b/isl_mat.c
index aa68941..d72d929 100644 (file)
--- a/isl_mat.c
+++ b/isl_mat.c
@@ -40,6 +40,7 @@ struct isl_mat *isl_mat_extend(struct isl_ctx *ctx, struct isl_mat *mat,
        unsigned n_row, unsigned n_col)
 {
        int i;
+       isl_int *old;
 
        if (!mat)
                return NULL;
@@ -64,6 +65,7 @@ struct isl_mat *isl_mat_extend(struct isl_ctx *ctx, struct isl_mat *mat,
                goto error;
 
        assert(mat->ref == 1);
+       old = mat->block.data;
        mat->block = isl_blk_extend(ctx, mat->block, n_row * mat->n_col);
        if (isl_blk_is_error(mat->block))
                goto error;
@@ -71,7 +73,9 @@ struct isl_mat *isl_mat_extend(struct isl_ctx *ctx, struct isl_mat *mat,
        if (!mat->row)
                goto error;
 
-       for (i = 0; i < n_row; ++i)
+       for (i = 0; i < mat->n_row; ++i)
+               mat->row[i] = mat->block.data + (mat->row[i] - old);
+       for (i = mat->n_row; i < n_row; ++i)
                mat->row[i] = mat->block.data + i * mat->n_col;
        mat->n_row = n_row;
 
@@ -209,14 +213,14 @@ struct isl_vec *isl_mat_vec_product(struct isl_ctx *ctx,
                goto error;
 
        for (i = 0; i < prod->size; ++i)
-               isl_seq_inner_product(mat->row[i], vec->block.data, vec->size,
+               isl_seq_inner_product(mat->row[i], vec->el, vec->size,
                                        &prod->block.data[i]);
        isl_mat_free(ctx, mat);
-       isl_vec_free(ctx, vec);
+       isl_vec_free(vec);
        return prod;
 error:
        isl_mat_free(ctx, mat);
-       isl_vec_free(ctx, vec);
+       isl_vec_free(vec);
        return NULL;
 }
 
@@ -795,6 +799,45 @@ error:
        return NULL;
 }
 
+/* Replace the variables x in the rows q by x' given by x = M x',
+ * with M the matrix mat.
+ *
+ * If the number of new variables is greater than the original
+ * number of variables, then the rows q have already been
+ * preextended.  If the new number is smaller, then the coefficients
+ * of the divs, which are not changed, need to be shifted down.
+ * The row q may be the equalities, the inequalities or the
+ * div expressions.  In the latter case, has_div is true and
+ * we need to take into account the extra denominator column.
+ */
+static int preimage(struct isl_ctx *ctx, isl_int **q, unsigned n,
+       unsigned n_div, int has_div, struct isl_mat *mat)
+{
+       int i;
+       struct isl_mat *t;
+       int e;
+
+       if (mat->n_col >= mat->n_row)
+               e = 0;
+       else
+               e = mat->n_row - mat->n_col;
+       if (has_div)
+               for (i = 0; i < n; ++i)
+                       isl_int_mul(q[i][0], q[i][0], mat->row[0][0]);
+       t = isl_mat_sub_alloc(ctx, q, 0, n, has_div, mat->n_row);
+       t = isl_mat_product(ctx, t, mat);
+       if (!t)
+               return -1;
+       for (i = 0; i < n; ++i) {
+               isl_seq_swp_or_cpy(q[i] + has_div, t->row[i], t->n_col);
+               isl_seq_cpy(q[i] + has_div + t->n_col,
+                           q[i] + has_div + t->n_col + e, n_div);
+               isl_seq_clr(q[i] + has_div + t->n_col + n_div, e);
+       }
+       isl_mat_free(ctx, t);
+       return 0;
+}
+
 /* Replace the variables x in bset by x' given by x = M x', with
  * M the matrix mat.
  *
@@ -809,8 +852,6 @@ struct isl_basic_set *isl_basic_set_preimage(struct isl_basic_set *bset,
        struct isl_mat *mat)
 {
        struct isl_ctx *ctx;
-       struct isl_mat *t;
-       int i;
 
        if (!bset || !mat)
                goto error;
@@ -821,7 +862,6 @@ struct isl_basic_set *isl_basic_set_preimage(struct isl_basic_set *bset,
                goto error;
 
        isl_assert(ctx, bset->dim->nparam == 0, goto error);
-       isl_assert(ctx, bset->n_div == 0, goto error);
        isl_assert(ctx, 1+bset->dim->n_out == mat->n_row, goto error);
 
        if (mat->n_col > mat->n_row)
@@ -834,25 +874,16 @@ struct isl_basic_set *isl_basic_set_preimage(struct isl_basic_set *bset,
                bset->dim->n_out -= mat->n_row - mat->n_col;
        }
 
-       t = isl_mat_sub_alloc(ctx, bset->eq, 0, bset->n_eq, 0, mat->n_row);
-       t = isl_mat_product(ctx, t, isl_mat_copy(ctx, mat));
-       if (!t)
+       if (preimage(ctx, bset->eq, bset->n_eq, bset->n_div, 0,
+                       isl_mat_copy(ctx, mat)) < 0)
                goto error;
-       for (i = 0; i < bset->n_eq; ++i) {
-               isl_seq_swp_or_cpy(bset->eq[i], t->row[i], t->n_col);
-               isl_seq_clr(bset->eq[i]+t->n_col, bset->extra);
-       }
-       isl_mat_free(ctx, t);
 
-       t = isl_mat_sub_alloc(ctx, bset->ineq, 0, bset->n_ineq, 0, mat->n_row);
-       t = isl_mat_product(ctx, t, mat);
-       if (!t)
+       if (preimage(ctx, bset->ineq, bset->n_ineq, bset->n_div, 0,
+                       isl_mat_copy(ctx, mat)) < 0)
+               goto error;
+
+       if (preimage(ctx, bset->div, bset->n_div, bset->n_div, 1, mat) < 0)
                goto error2;
-       for (i = 0; i < bset->n_ineq; ++i) {
-               isl_seq_swp_or_cpy(bset->ineq[i], t->row[i], t->n_col);
-               isl_seq_clr(bset->ineq[i]+t->n_col, bset->extra);
-       }
-       isl_mat_free(ctx, t);
 
        ISL_F_CLR(bset, ISL_BASIC_SET_NO_IMPLICIT);
        ISL_F_CLR(bset, ISL_BASIC_SET_NO_REDUNDANT);
@@ -983,3 +1014,29 @@ void isl_mat_col_mul(struct isl_mat *mat, int dst_col, isl_int f, int src_col)
        for (i = 0; i < mat->n_row; ++i)
                isl_int_mul(mat->row[i][dst_col], f, mat->row[i][src_col]);
 }
+
+struct isl_mat *isl_mat_unimodular_complete(struct isl_ctx *ctx,
+                                               struct isl_mat *M, int row)
+{
+       int r;
+       struct isl_mat *H = NULL, *Q = NULL;
+
+       isl_assert(ctx, M->n_row == M->n_col, goto error);
+       M->n_row = row;
+       H = isl_mat_left_hermite(ctx, isl_mat_copy(ctx, M), 0, NULL, &Q);
+       M->n_row = M->n_col;
+       if (!H)
+               goto error;
+       for (r = 0; r < row; ++r)
+               isl_assert(ctx, isl_int_is_one(H->row[r][r]), goto error);
+       for (r = row; r < M->n_row; ++r)
+               isl_seq_cpy(M->row[r], Q->row[r], M->n_col);
+       isl_mat_free(ctx, H);
+       isl_mat_free(ctx, Q);
+       return M;
+error:
+       isl_mat_free(ctx, H);
+       isl_mat_free(ctx, Q);
+       isl_mat_free(ctx, M);
+       return NULL;
+}