X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=basis_reduction_templ.c;h=7f4b28f06c9fc95557fc06e1e27d8ef4d2aa01e6;hb=ba12024d62fff3e2d5ff6d565944e2984ccd53b0;hp=aa1e71fcd5b23256baef115a5b4df7a02ff581fb;hpb=01fb9764e7ff92a13edd56d91833490afee4da7d;p=platform%2Fupstream%2Fisl.git diff --git a/basis_reduction_templ.c b/basis_reduction_templ.c index aa1e71f..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 +#include +#include +#include #include "isl_basis_reduction.h" static void save_alpha(GBR_LP *lp, int first, int n, GBR_type *alpha) @@ -10,19 +25,23 @@ 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. * 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. */ @@ -51,17 +70,24 @@ struct isl_tab *isl_tab_compute_reduced_basis(struct isl_tab *tab) int fixed = 0; int fixed_saved = 0; int mu_fixed[2]; + int n_bounded; + int gbr_only_first; if (!tab) 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 <= tab->n_zero + 1) + n_bounded = dim - tab->n_unbounded; + if (n_bounded <= tab->n_zero + 1) return tab; isl_int_init(tmp); @@ -81,15 +107,15 @@ struct isl_tab *isl_tab_compute_reduced_basis(struct isl_tab *tab) if (!b_tmp) goto error; - F = isl_alloc_array(ctx, GBR_type, dim); - alpha_buffer[0] = isl_alloc_array(ctx, GBR_type, dim); - alpha_buffer[1] = isl_alloc_array(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]); @@ -149,7 +175,8 @@ struct isl_tab *isl_tab_compute_reduced_basis(struct isl_tab *tab) 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); @@ -213,11 +240,12 @@ struct isl_tab *isl_tab_compute_reduced_basis(struct isl_tab *tab) 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[tab->n_zero], F_new); - if (ctx->gbr_only_first && GBR_lt(F[tab->n_zero], two)) + if (gbr_only_first && GBR_lt(F[tab->n_zero], two)) break; if (fixed) { @@ -234,7 +262,7 @@ struct isl_tab *isl_tab_compute_reduced_basis(struct isl_tab *tab) GBR_lp_add_row(lp, B->row[1+i]+1, dim); ++i; } - } while (i < dim-1); + } while (i < n_bounded - 1); if (0) { done: @@ -248,7 +276,7 @@ error: 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]); @@ -277,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;