#include "isl_ctx.h"#include "isl_seq.h"#include "isl_set.h"#include "isl_lp.h"#include "isl_map.h"#include "isl_map_private.h"#include "isl_equalities.h"#include "isl_sample.h"#include "isl_tab.h"Go to the source code of this file.
| struct isl_basic_map* isl_basic_map_implicit_equalities | ( | struct isl_basic_map * | bmap | ) | [read] |
Definition at line 11 of file isl_affine_hull.c.
00013 { 00014 struct isl_tab *tab; 00015 00016 if (!bmap) 00017 return bmap; 00018 00019 bmap = isl_basic_map_gauss(bmap, NULL); 00020 if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY)) 00021 return bmap; 00022 if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_NO_IMPLICIT)) 00023 return bmap; 00024 if (bmap->n_ineq <= 1) 00025 return bmap; 00026 00027 tab = isl_tab_from_basic_map(bmap); 00028 tab = isl_tab_detect_equalities(bmap->ctx, tab); 00029 bmap = isl_basic_map_update_from_tab(bmap, tab); 00030 isl_tab_free(bmap->ctx, tab); 00031 bmap = isl_basic_map_gauss(bmap, NULL); 00032 ISL_F_SET(bmap, ISL_BASIC_MAP_NO_IMPLICIT); 00033 return bmap; 00034 }
| struct isl_basic_set* isl_basic_set_implicit_equalities | ( | struct isl_basic_set * | bset | ) | [read] |
Definition at line 36 of file isl_affine_hull.c.
00038 { 00039 return (struct isl_basic_set *) 00040 isl_basic_map_implicit_equalities((struct isl_basic_map*)bset); 00041 }
Definition at line 43 of file isl_affine_hull.c.
00044 { 00045 int i; 00046 00047 if (!map) 00048 return map; 00049 00050 for (i = 0; i < map->n; ++i) { 00051 map->p[i] = isl_basic_map_implicit_equalities(map->p[i]); 00052 if (!map->p[i]) 00053 goto error; 00054 } 00055 00056 return map; 00057 error: 00058 isl_map_free(map); 00059 return NULL; 00060 }
| static void set_common_multiple | ( | struct isl_basic_set * | bset1, | |
| struct isl_basic_set * | bset2, | |||
| unsigned | row, | |||
| unsigned | col | |||
| ) | [static] |
Definition at line 67 of file isl_affine_hull.c.
00070 { 00071 isl_int m, c; 00072 00073 if (isl_int_eq(bset1->eq[row][col], bset2->eq[row][col])) 00074 return; 00075 00076 isl_int_init(c); 00077 isl_int_init(m); 00078 isl_int_lcm(m, bset1->eq[row][col], bset2->eq[row][col]); 00079 isl_int_divexact(c, m, bset1->eq[row][col]); 00080 isl_seq_scale(bset1->eq[row], bset1->eq[row], c, col+1); 00081 isl_int_divexact(c, m, bset2->eq[row][col]); 00082 isl_seq_scale(bset2->eq[row], bset2->eq[row], c, col+1); 00083 isl_int_clear(c); 00084 isl_int_clear(m); 00085 }
| static void delete_row | ( | struct isl_basic_set * | bset, | |
| unsigned | row | |||
| ) | [static] |
| static void construct_column | ( | struct isl_basic_set * | bset1, | |
| struct isl_basic_set * | bset2, | |||
| unsigned | row, | |||
| unsigned | col | |||
| ) | [static] |
Definition at line 110 of file isl_affine_hull.c.
00113 { 00114 int r; 00115 isl_int a; 00116 isl_int b; 00117 unsigned total; 00118 00119 isl_int_init(a); 00120 isl_int_init(b); 00121 total = 1 + isl_basic_set_n_dim(bset1); 00122 for (r = 0; r < row; ++r) { 00123 if (isl_int_is_zero(bset2->eq[r][col])) 00124 continue; 00125 isl_int_gcd(b, bset2->eq[r][col], bset1->eq[row][col]); 00126 isl_int_divexact(a, bset1->eq[row][col], b); 00127 isl_int_divexact(b, bset2->eq[r][col], b); 00128 isl_seq_combine(bset1->eq[r], a, bset1->eq[r], 00129 b, bset1->eq[row], total); 00130 isl_seq_scale(bset2->eq[r], bset2->eq[r], a, total); 00131 } 00132 isl_int_clear(a); 00133 isl_int_clear(b); 00134 delete_row(bset1, row); 00135 }
| static int transform_column | ( | struct isl_basic_set * | bset1, | |
| struct isl_basic_set * | bset2, | |||
| unsigned | row, | |||
| unsigned | col | |||
| ) | [static] |
Definition at line 146 of file isl_affine_hull.c.
00149 { 00150 int i, t; 00151 isl_int a, b, g; 00152 unsigned total; 00153 00154 for (t = row-1; t >= 0; --t) 00155 if (isl_int_ne(bset1->eq[t][col], bset2->eq[t][col])) 00156 break; 00157 if (t < 0) 00158 return 0; 00159 00160 total = 1 + isl_basic_set_n_dim(bset1); 00161 isl_int_init(a); 00162 isl_int_init(b); 00163 isl_int_init(g); 00164 isl_int_sub(b, bset1->eq[t][col], bset2->eq[t][col]); 00165 for (i = 0; i < t; ++i) { 00166 isl_int_sub(a, bset2->eq[i][col], bset1->eq[i][col]); 00167 isl_int_gcd(g, a, b); 00168 isl_int_divexact(a, a, g); 00169 isl_int_divexact(g, b, g); 00170 isl_seq_combine(bset1->eq[i], g, bset1->eq[i], a, bset1->eq[t], 00171 total); 00172 isl_seq_combine(bset2->eq[i], g, bset2->eq[i], a, bset2->eq[t], 00173 total); 00174 } 00175 isl_int_clear(a); 00176 isl_int_clear(b); 00177 isl_int_clear(g); 00178 delete_row(bset1, t); 00179 delete_row(bset2, t); 00180 return 1; 00181 }
| static struct isl_basic_set* affine_hull | ( | struct isl_basic_set * | bset1, | |
| struct isl_basic_set * | bset2 | |||
| ) | [static, read] |
Definition at line 188 of file isl_affine_hull.c.
00190 { 00191 unsigned total; 00192 int col; 00193 int row; 00194 00195 total = 1 + isl_basic_set_n_dim(bset1); 00196 00197 row = 0; 00198 for (col = total-1; col >= 0; --col) { 00199 int is_zero1 = row >= bset1->n_eq || 00200 isl_int_is_zero(bset1->eq[row][col]); 00201 int is_zero2 = row >= bset2->n_eq || 00202 isl_int_is_zero(bset2->eq[row][col]); 00203 if (!is_zero1 && !is_zero2) { 00204 set_common_multiple(bset1, bset2, row, col); 00205 ++row; 00206 } else if (!is_zero1 && is_zero2) { 00207 construct_column(bset1, bset2, row, col); 00208 } else if (is_zero1 && !is_zero2) { 00209 construct_column(bset2, bset1, row, col); 00210 } else { 00211 if (transform_column(bset1, bset2, row, col)) 00212 --row; 00213 } 00214 } 00215 isl_basic_set_free(bset2); 00216 isl_assert(ctx, row == bset1->n_eq, goto error); 00217 bset1 = isl_basic_set_normalize_constraints(bset1); 00218 return bset1; 00219 error: 00220 isl_basic_set_free(bset1); 00221 return NULL; 00222 }
| static struct isl_basic_set* isl_basic_set_from_vec | ( | struct isl_ctx * | ctx, | |
| struct isl_vec * | vec | |||
| ) | [static, read] |
Definition at line 224 of file isl_affine_hull.c.
00226 { 00227 int i; 00228 int k; 00229 struct isl_basic_set *bset = NULL; 00230 unsigned dim; 00231 00232 if (!vec) 00233 return NULL; 00234 isl_assert(ctx, vec->size != 0, goto error); 00235 00236 bset = isl_basic_set_alloc(ctx, 0, vec->size - 1, 0, vec->size - 1, 0); 00237 if (!bset) 00238 goto error; 00239 dim = isl_basic_set_n_dim(bset); 00240 for (i = dim - 1; i >= 0; --i) { 00241 k = isl_basic_set_alloc_equality(bset); 00242 if (k < 0) 00243 goto error; 00244 isl_seq_clr(bset->eq[k], 1 + dim); 00245 isl_int_neg(bset->eq[k][0], vec->block.data[1 + i]); 00246 isl_int_set(bset->eq[k][1 + i], vec->block.data[0]); 00247 } 00248 isl_vec_free(ctx, vec); 00249 00250 return bset; 00251 error: 00252 isl_basic_set_free(bset); 00253 isl_vec_free(ctx, vec); 00254 return NULL; 00255 }
| static struct isl_basic_set* outside_point | ( | struct isl_ctx * | ctx, | |
| struct isl_basic_set * | bset, | |||
| isl_int * | eq, | |||
| int | up | |||
| ) | [static, read] |
Definition at line 269 of file isl_affine_hull.c.
00271 { 00272 struct isl_basic_set *slice = NULL; 00273 struct isl_vec *sample; 00274 struct isl_basic_set *point; 00275 unsigned dim; 00276 int k; 00277 00278 dim = isl_basic_set_n_dim(bset); 00279 sample = isl_vec_alloc(ctx, 1 + dim); 00280 if (!sample) 00281 return NULL; 00282 isl_int_set_si(sample->block.data[0], 1); 00283 isl_seq_combine(sample->block.data + 1, 00284 ctx->one, bset->sample->block.data + 1, 00285 up ? ctx->one : ctx->negone, eq + 1, dim); 00286 if (isl_basic_set_contains(bset, sample)) 00287 return isl_basic_set_from_vec(ctx, sample); 00288 isl_vec_free(ctx, sample); 00289 sample = NULL; 00290 00291 slice = isl_basic_set_copy(bset); 00292 if (!slice) 00293 goto error; 00294 slice = isl_basic_set_cow(slice); 00295 slice = isl_basic_set_extend(slice, 0, dim, 0, 0, 1); 00296 k = isl_basic_set_alloc_inequality(slice); 00297 if (k < 0) 00298 goto error; 00299 if (up) 00300 isl_seq_cpy(slice->ineq[k], eq, 1 + dim); 00301 else 00302 isl_seq_neg(slice->ineq[k], eq, 1 + dim); 00303 isl_int_sub_ui(slice->ineq[k][0], slice->ineq[k][0], 1); 00304 00305 sample = isl_basic_set_sample(slice); 00306 if (!sample) 00307 goto error; 00308 if (sample->size == 0) { 00309 isl_vec_free(ctx, sample); 00310 point = isl_basic_set_empty_like(bset); 00311 } else 00312 point = isl_basic_set_from_vec(ctx, sample); 00313 00314 return point; 00315 error: 00316 isl_basic_set_free(slice); 00317 return NULL; 00318 }
| static struct isl_basic_set* recession_cone | ( | struct isl_basic_set * | bset | ) | [static, read] |
Definition at line 320 of file isl_affine_hull.c.
00321 { 00322 int i; 00323 00324 bset = isl_basic_set_cow(bset); 00325 if (!bset) 00326 return NULL; 00327 00328 for (i = 0; i < bset->n_eq; ++i) 00329 isl_int_set_si(bset->eq[i][0], 0); 00330 00331 for (i = 0; i < bset->n_ineq; ++i) 00332 isl_int_set_si(bset->ineq[i][0], 0); 00333 00334 ISL_F_CLR(bset, ISL_BASIC_SET_NO_IMPLICIT); 00335 return isl_basic_set_implicit_equalities(bset); 00336 }
| static struct isl_basic_set* shift | ( | struct isl_basic_set * | bset, | |
| isl_int * | point | |||
| ) | [static, read] |
Definition at line 338 of file isl_affine_hull.c.
00339 { 00340 int i; 00341 unsigned dim; 00342 00343 bset = isl_basic_set_cow(bset); 00344 if (!bset) 00345 return NULL; 00346 00347 dim = isl_basic_set_n_dim(bset); 00348 for (i = 0; i < bset->n_eq; ++i) { 00349 isl_seq_inner_product(bset->eq[i]+1, point+1, dim, 00350 &bset->eq[i][0]); 00351 isl_int_neg(bset->eq[i][0], bset->eq[i][0]); 00352 } 00353 00354 for (i = 0; i < bset->n_ineq; ++i) { 00355 isl_seq_inner_product(bset->ineq[i]+1, point+1, dim, 00356 &bset->ineq[i][0]); 00357 isl_int_neg(bset->ineq[i][0], bset->ineq[i][0]); 00358 } 00359 00360 return bset; 00361 }
| static struct isl_basic_set* uset_affine_hull | ( | struct isl_basic_set * | bset | ) | [static, read] |
Definition at line 376 of file isl_affine_hull.c.
00377 { 00378 int i, j; 00379 struct isl_basic_set *hull = NULL; 00380 struct isl_vec *sample; 00381 struct isl_ctx *ctx; 00382 unsigned dim; 00383 00384 if (isl_basic_set_is_empty(bset)) 00385 return bset; 00386 00387 ctx = bset->ctx; 00388 sample = isl_basic_set_sample(isl_basic_set_copy(bset)); 00389 if (!sample) 00390 goto error; 00391 if (sample->size == 0) { 00392 isl_vec_free(ctx, sample); 00393 hull = isl_basic_set_empty_like(bset); 00394 isl_basic_set_free(bset); 00395 return hull; 00396 } else 00397 hull = isl_basic_set_from_vec(ctx, sample); 00398 00399 if (hull->n_eq > 0) { 00400 struct isl_basic_set *cone; 00401 cone = recession_cone(isl_basic_set_copy(bset)); 00402 isl_basic_set_free_inequality(cone, cone->n_ineq); 00403 cone = isl_basic_set_normalize_constraints(cone); 00404 cone = shift(cone, bset->sample->block.data); 00405 hull = affine_hull(hull, cone); 00406 } 00407 00408 dim = isl_basic_set_n_dim(bset); 00409 for (i = 0; i < dim; ++i) { 00410 struct isl_basic_set *point; 00411 for (j = 0; j < hull->n_eq; ++j) { 00412 point = outside_point(ctx, bset, hull->eq[j], 1); 00413 if (!point) 00414 goto error; 00415 if (!ISL_F_ISSET(point, ISL_BASIC_SET_EMPTY)) 00416 break; 00417 isl_basic_set_free(point); 00418 point = outside_point(ctx, bset, hull->eq[j], 0); 00419 if (!point) 00420 goto error; 00421 if (!ISL_F_ISSET(point, ISL_BASIC_SET_EMPTY)) 00422 break; 00423 isl_basic_set_free(point); 00424 } 00425 if (j == hull->n_eq) 00426 break; 00427 hull = affine_hull(hull, point); 00428 } 00429 isl_basic_set_free(bset); 00430 00431 return hull; 00432 error: 00433 isl_basic_set_free(bset); 00434 isl_basic_set_free(hull); 00435 return NULL; 00436 }
| static struct isl_basic_set* equalities_in_underlying_set | ( | struct isl_basic_map * | bmap | ) | [static, read] |
Definition at line 451 of file isl_affine_hull.c.
00453 { 00454 struct isl_mat *T2 = NULL; 00455 struct isl_basic_set *bset = NULL; 00456 struct isl_basic_set *hull = NULL; 00457 struct isl_ctx *ctx; 00458 00459 ctx = bmap->ctx; 00460 bset = isl_basic_map_underlying_set(bmap); 00461 bset = isl_basic_set_remove_equalities(bset, NULL, &T2); 00462 if (!bset) 00463 goto error; 00464 00465 hull = uset_affine_hull(bset); 00466 if (T2) 00467 hull = isl_basic_set_preimage(hull, T2); 00468 00469 return hull; 00470 error: 00471 isl_mat_free(ctx, T2); 00472 isl_basic_set_free(bset); 00473 isl_basic_set_free(hull); 00474 return NULL; 00475 }
| struct isl_basic_map* isl_basic_map_detect_equalities | ( | struct isl_basic_map * | bmap | ) | [read] |
Definition at line 480 of file isl_affine_hull.c.
00482 { 00483 int i, j; 00484 struct isl_basic_set *hull = NULL; 00485 00486 if (!bmap) 00487 return NULL; 00488 if (bmap->n_ineq == 0) 00489 return bmap; 00490 if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY)) 00491 return bmap; 00492 if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_ALL_EQUALITIES)) 00493 return bmap; 00494 if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) 00495 return isl_basic_map_implicit_equalities(bmap); 00496 00497 hull = equalities_in_underlying_set(isl_basic_map_copy(bmap)); 00498 if (!hull) 00499 goto error; 00500 if (ISL_F_ISSET(hull, ISL_BASIC_SET_EMPTY)) { 00501 isl_basic_set_free(hull); 00502 return isl_basic_map_set_to_empty(bmap); 00503 } 00504 bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim), 0, 00505 hull->n_eq, 0); 00506 for (i = 0; i < hull->n_eq; ++i) { 00507 j = isl_basic_map_alloc_equality(bmap); 00508 if (j < 0) 00509 goto error; 00510 isl_seq_cpy(bmap->eq[j], hull->eq[i], 00511 1 + isl_basic_set_total_dim(hull)); 00512 } 00513 isl_basic_set_free(hull); 00514 ISL_F_SET(bmap, ISL_BASIC_MAP_NO_IMPLICIT | ISL_BASIC_MAP_ALL_EQUALITIES); 00515 bmap = isl_basic_map_simplify(bmap); 00516 return isl_basic_map_finalize(bmap); 00517 error: 00518 isl_basic_set_free(hull); 00519 isl_basic_map_free(bmap); 00520 return NULL; 00521 }
Definition at line 523 of file isl_affine_hull.c.
00524 { 00525 struct isl_basic_map *bmap; 00526 int i; 00527 00528 if (!map) 00529 return NULL; 00530 00531 for (i = 0; i < map->n; ++i) { 00532 bmap = isl_basic_map_copy(map->p[i]); 00533 bmap = isl_basic_map_detect_equalities(bmap); 00534 if (!bmap) 00535 goto error; 00536 isl_basic_map_free(map->p[i]); 00537 map->p[i] = bmap; 00538 } 00539 00540 return map; 00541 error: 00542 isl_map_free(map); 00543 return NULL; 00544 }
| struct isl_basic_map* isl_basic_map_affine_hull | ( | struct isl_basic_map * | bmap | ) | [read] |
Definition at line 550 of file isl_affine_hull.c.
00551 { 00552 struct isl_basic_set *hull = NULL; 00553 00554 bmap = isl_basic_map_detect_equalities(bmap); 00555 bmap = isl_basic_map_cow(bmap); 00556 isl_basic_map_free_inequality(bmap, bmap->n_ineq); 00557 return bmap; 00558 }
| struct isl_basic_set* isl_basic_set_affine_hull | ( | struct isl_basic_set * | bset | ) | [read] |
Definition at line 560 of file isl_affine_hull.c.
00561 { 00562 return (struct isl_basic_set *) 00563 isl_basic_map_affine_hull((struct isl_basic_map *)bset); 00564 }
| struct isl_basic_map* isl_map_affine_hull | ( | struct isl_map * | map | ) | [read] |
Definition at line 566 of file isl_affine_hull.c.
00567 { 00568 int i; 00569 struct isl_basic_map *model = NULL; 00570 struct isl_basic_map *hull = NULL; 00571 struct isl_set *set; 00572 00573 if (!map) 00574 return NULL; 00575 00576 if (map->n == 0) { 00577 hull = isl_basic_map_empty_like_map(map); 00578 isl_map_free(map); 00579 return hull; 00580 } 00581 00582 map = isl_map_detect_equalities(map); 00583 map = isl_map_align_divs(map); 00584 if (!map) 00585 return NULL; 00586 model = isl_basic_map_copy(map->p[0]); 00587 set = isl_map_underlying_set(map); 00588 set = isl_set_cow(set); 00589 if (!set) 00590 goto error; 00591 00592 for (i = 0; i < set->n; ++i) { 00593 set->p[i] = isl_basic_set_cow(set->p[i]); 00594 set->p[i] = isl_basic_set_affine_hull(set->p[i]); 00595 set->p[i] = isl_basic_set_gauss(set->p[i], NULL); 00596 if (!set->p[i]) 00597 goto error; 00598 } 00599 set = isl_set_remove_empty_parts(set); 00600 if (set->n == 0) { 00601 hull = isl_basic_map_empty_like(model); 00602 isl_basic_map_free(model); 00603 } else { 00604 struct isl_basic_set *bset; 00605 while (set->n > 1) { 00606 set->p[0] = affine_hull(set->p[0], set->p[--set->n]); 00607 if (!set->p[0]) 00608 goto error; 00609 } 00610 bset = isl_basic_set_copy(set->p[0]); 00611 hull = isl_basic_map_overlying_set(bset, model); 00612 } 00613 isl_set_free(set); 00614 hull = isl_basic_map_simplify(hull); 00615 return isl_basic_map_finalize(hull); 00616 error: 00617 isl_basic_map_free(model); 00618 isl_set_free(set); 00619 return NULL; 00620 }
| struct isl_basic_set* isl_set_affine_hull | ( | struct isl_set * | set | ) | [read] |
Definition at line 622 of file isl_affine_hull.c.
00623 { 00624 return (struct isl_basic_set *) 00625 isl_map_affine_hull((struct isl_map *)set); 00626 }
1.5.9