add isl_basic_set_box_from_points
[platform/upstream/isl.git] / isl_point.c
1 #include <isl_point_private.h>
2 #include <isl_set.h>
3 #include <isl_map_private.h>
4 #include <isl_sample.h>
5 #include <isl_scan.h>
6 #include <isl_seq.h>
7 #include <isl_dim_private.h>
8
9 __isl_give isl_point *isl_point_alloc(__isl_take isl_dim *dim,
10         __isl_take isl_vec *vec)
11 {
12         struct isl_point *pnt;
13
14         if (!dim || !vec)
15                 goto error;
16
17         if (vec->size > 1 + isl_dim_total(dim)) {
18                 vec = isl_vec_cow(vec);
19                 if (!vec)
20                         goto error;
21                 vec->size = 1 + isl_dim_total(dim);
22         }
23
24         pnt = isl_alloc_type(dim->ctx, struct isl_point);
25         if (!pnt)
26                 goto error;
27
28         pnt->ref = 1;
29         pnt->dim = dim;
30         pnt->vec = vec;
31
32         return pnt;
33 error:
34         isl_dim_free(dim);
35         isl_vec_free(vec);
36         return NULL;
37 }
38
39 __isl_give isl_point *isl_point_zero(__isl_take isl_dim *dim)
40 {
41         isl_vec *vec;
42
43         if (!dim)
44                 return NULL;
45         vec = isl_vec_alloc(dim->ctx, 1 + isl_dim_total(dim));
46         if (!vec)
47                 goto error;
48         isl_int_set_si(vec->el[0], 1);
49         isl_seq_clr(vec->el + 1, vec->size - 1);
50         return isl_point_alloc(dim, vec);
51 error:
52         isl_dim_free(dim);
53         return NULL;
54 }
55
56 __isl_give isl_point *isl_point_dup(__isl_keep isl_point *pnt)
57 {
58         struct isl_point *pnt2;
59
60         if (!pnt)
61                 return NULL;
62         pnt2 = isl_point_alloc(isl_dim_copy(pnt->dim), isl_vec_copy(pnt->vec));
63         return pnt2;
64 }
65
66 __isl_give isl_point *isl_point_cow(__isl_take isl_point *pnt)
67 {
68         struct isl_point *pnt2;
69         if (!pnt)
70                 return NULL;
71
72         if (pnt->ref == 1)
73                 return pnt;
74
75         pnt2 = isl_point_dup(pnt);
76         isl_point_free(pnt);
77         return pnt2;
78 }
79
80 __isl_give isl_point *isl_point_copy(__isl_keep isl_point *pnt)
81 {
82         if (!pnt)
83                 return NULL;
84
85         pnt->ref++;
86         return pnt;
87 }
88
89 void isl_point_free(__isl_take isl_point *pnt)
90 {
91         if (!pnt)
92                 return;
93
94         if (--pnt->ref > 0)
95                 return;
96
97         isl_dim_free(pnt->dim);
98         isl_vec_free(pnt->vec);
99         free(pnt);
100 }
101
102 __isl_give isl_point *isl_point_void(__isl_take isl_dim *dim)
103 {
104         if (!dim)
105                 return NULL;
106
107         return isl_point_alloc(dim, isl_vec_alloc(dim->ctx, 0));
108 }
109
110 int isl_point_is_void(__isl_keep isl_point *pnt)
111 {
112         if (!pnt)
113                 return -1;
114
115         return pnt->vec->size == 0;
116 }
117
118 void isl_point_get_coordinate(__isl_keep isl_point *pnt,
119         enum isl_dim_type type, int pos, isl_int *v)
120 {
121         if (!pnt || isl_point_is_void(pnt))
122                 return;
123         if (type == isl_dim_set)
124                 pos += isl_dim_size(pnt->dim, isl_dim_param);
125         isl_int_set(*v, pnt->vec->el[1 + pos]);
126 }
127
128 __isl_give isl_point *isl_point_set_coordinate(__isl_take isl_point *pnt,
129         enum isl_dim_type type, int pos, isl_int v)
130 {
131         if (!pnt || isl_point_is_void(pnt))
132                 return pnt;
133
134         pnt = isl_point_cow(pnt);
135         if (!pnt)
136                 return NULL;
137         pnt->vec = isl_vec_cow(pnt->vec);
138         if (!pnt->vec)
139                 goto error;
140
141         if (type == isl_dim_set)
142                 pos += isl_dim_size(pnt->dim, isl_dim_param);
143
144         isl_int_set(pnt->vec->el[1 + pos], v);
145
146         return pnt;
147 error:
148         isl_point_free(pnt);
149         return NULL;
150 }
151
152 __isl_give isl_point *isl_point_add_ui(__isl_take isl_point *pnt,
153         enum isl_dim_type type, int pos, unsigned val)
154 {
155         if (!pnt || isl_point_is_void(pnt))
156                 return pnt;
157
158         pnt = isl_point_cow(pnt);
159         if (!pnt)
160                 return NULL;
161         pnt->vec = isl_vec_cow(pnt->vec);
162         if (!pnt->vec)
163                 goto error;
164
165         if (type == isl_dim_set)
166                 pos += isl_dim_size(pnt->dim, isl_dim_param);
167
168         isl_int_add_ui(pnt->vec->el[1 + pos], pnt->vec->el[1 + pos], val);
169
170         return pnt;
171 error:
172         isl_point_free(pnt);
173         return NULL;
174 }
175
176 __isl_give isl_point *isl_point_sub_ui(__isl_take isl_point *pnt,
177         enum isl_dim_type type, int pos, unsigned val)
178 {
179         if (!pnt || isl_point_is_void(pnt))
180                 return pnt;
181
182         pnt = isl_point_cow(pnt);
183         if (!pnt)
184                 return NULL;
185         pnt->vec = isl_vec_cow(pnt->vec);
186         if (!pnt->vec)
187                 goto error;
188
189         if (type == isl_dim_set)
190                 pos += isl_dim_size(pnt->dim, isl_dim_param);
191
192         isl_int_sub_ui(pnt->vec->el[1 + pos], pnt->vec->el[1 + pos], val);
193
194         return pnt;
195 error:
196         isl_point_free(pnt);
197         return NULL;
198 }
199
200 struct isl_foreach_point {
201         struct isl_scan_callback callback;
202         int (*fn)(__isl_take isl_point *pnt, void *user);
203         void *user;
204         isl_dim *dim;
205 };
206
207 static int foreach_point(struct isl_scan_callback *cb, __isl_take isl_vec *sample)
208 {
209         struct isl_foreach_point *fp = (struct isl_foreach_point *)cb;
210         isl_point *pnt;
211
212         pnt = isl_point_alloc(isl_dim_copy(fp->dim), sample);
213
214         return fp->fn(pnt, fp->user);
215 }
216
217 int isl_set_foreach_point(__isl_keep isl_set *set,
218         int (*fn)(__isl_take isl_point *pnt, void *user), void *user)
219 {
220         struct isl_foreach_point fp = { { &foreach_point }, fn, user };
221         int i;
222
223         if (!set)
224                 return -1;
225
226         fp.dim = isl_set_get_dim(set);
227         if (!fp.dim)
228                 return -1;
229
230         set = isl_set_copy(set);
231         set = isl_set_cow(set);
232         set = isl_set_make_disjoint(set);
233         set = isl_set_compute_divs(set);
234         if (!set)
235                 goto error;
236
237         for (i = 0; i < set->n; ++i)
238                 if (isl_basic_set_scan(isl_basic_set_copy(set->p[i]),
239                                         &fp.callback) < 0)
240                         goto error;
241
242         isl_set_free(set);
243         isl_dim_free(fp.dim);
244
245         return 0;
246 error:
247         isl_set_free(set);
248         isl_dim_free(fp.dim);
249         return -1;
250 }
251
252 /* Return 1 if "bmap" contains the point "point".
253  * "bmap" is assumed to have known divs.
254  * The point is first extended with the divs and then passed
255  * to basic_map_contains.
256  */
257 int isl_basic_map_contains_point(__isl_keep isl_basic_map *bmap,
258         __isl_keep isl_point *point)
259 {
260         int i;
261         struct isl_vec *vec;
262         unsigned dim;
263         int contains;
264
265         if (!bmap || !point)
266                 return -1;
267         isl_assert(bmap->ctx, isl_dim_equal(bmap->dim, point->dim), return -1);
268         if (bmap->n_div == 0)
269                 return isl_basic_map_contains(bmap, point->vec);
270
271         dim = isl_basic_map_total_dim(bmap) - bmap->n_div;
272         vec = isl_vec_alloc(bmap->ctx, 1 + dim + bmap->n_div);
273         if (!vec)
274                 return -1;
275
276         isl_seq_cpy(vec->el, point->vec->el, point->vec->size);
277         for (i = 0; i < bmap->n_div; ++i) {
278                 isl_seq_inner_product(bmap->div[i] + 1, vec->el,
279                                         1 + dim + i, &vec->el[1+dim+i]);
280                 isl_int_fdiv_q(vec->el[1+dim+i], vec->el[1+dim+i],
281                                 bmap->div[i][0]);
282         }
283
284         contains = isl_basic_map_contains(bmap, vec);
285
286         isl_vec_free(vec);
287         return contains;
288 }
289
290 int isl_map_contains_point(__isl_keep isl_map *map, __isl_keep isl_point *point)
291 {
292         int i;
293         int found = 0;
294
295         if (!map || !point)
296                 return -1;
297
298         map = isl_map_copy(map);
299         map = isl_map_compute_divs(map);
300         if (!map)
301                 return -1;
302
303         for (i = 0; i < map->n; ++i) {
304                 found = isl_basic_map_contains_point(map->p[i], point);
305                 if (found < 0)
306                         goto error;
307                 if (found)
308                         break;
309         }
310         isl_map_free(map);
311
312         return found;
313 error:
314         isl_map_free(map);
315         return -1;
316 }
317
318 int isl_set_contains_point(__isl_keep isl_set *set, __isl_keep isl_point *point)
319 {
320         return isl_map_contains_point((isl_map *)set, point);
321 }
322
323 __isl_give isl_basic_set *isl_basic_set_from_point(__isl_take isl_point *pnt)
324 {
325         isl_basic_set *bset;
326         isl_basic_set *model;
327
328         model = isl_basic_set_empty(isl_dim_copy(pnt->dim));
329         bset = isl_basic_set_from_vec(isl_vec_copy(pnt->vec));
330         bset = isl_basic_set_from_underlying_set(bset, model);
331         isl_point_free(pnt);
332
333         return bset;
334 }
335
336 __isl_give isl_set *isl_set_from_point(__isl_take isl_point *pnt)
337 {
338         isl_basic_set *bset;
339         bset = isl_basic_set_from_point(pnt);
340         return isl_set_from_basic_set(bset);
341 }
342
343 __isl_give isl_basic_set *isl_basic_set_box_from_points(
344         __isl_take isl_point *pnt1, __isl_take isl_point *pnt2)
345 {
346         isl_basic_set *bset;
347         unsigned total;
348         int i;
349         int k;
350         isl_int t;
351
352         isl_int_init(t);
353
354         if (!pnt1 || !pnt2)
355                 goto error;
356
357         isl_assert(pnt1->dim->ctx,
358                         isl_dim_equal(pnt1->dim, pnt2->dim), goto error);
359
360         if (isl_point_is_void(pnt1) && isl_point_is_void(pnt2)) {
361                 isl_dim *dim = isl_dim_copy(pnt1->dim);
362                 isl_point_free(pnt1);
363                 isl_point_free(pnt2);
364                 isl_int_clear(t);
365                 return isl_basic_set_empty(dim);
366         }
367         if (isl_point_is_void(pnt1)) {
368                 isl_point_free(pnt1);
369                 isl_int_clear(t);
370                 return isl_basic_set_from_point(pnt2);
371         }
372         if (isl_point_is_void(pnt2)) {
373                 isl_point_free(pnt2);
374                 isl_int_clear(t);
375                 return isl_basic_set_from_point(pnt1);
376         }
377
378         total = isl_dim_total(pnt1->dim);
379         bset = isl_basic_set_alloc_dim(isl_dim_copy(pnt1->dim), 0, 0, 2 * total);
380
381         for (i = 0; i < total; ++i) {
382                 isl_int_mul(t, pnt1->vec->el[1 + i], pnt2->vec->el[0]);
383                 isl_int_submul(t, pnt2->vec->el[1 + i], pnt1->vec->el[0]);
384
385                 k = isl_basic_set_alloc_inequality(bset);
386                 if (k < 0)
387                         goto error;
388                 isl_seq_clr(bset->ineq[k] + 1, total);
389                 if (isl_int_is_pos(t)) {
390                         isl_int_set_si(bset->ineq[k][1 + i], -1);
391                         isl_int_set(bset->ineq[k][0], pnt1->vec->el[1 + i]);
392                 } else {
393                         isl_int_set_si(bset->ineq[k][1 + i], 1);
394                         isl_int_neg(bset->ineq[k][0], pnt1->vec->el[1 + i]);
395                 }
396                 isl_int_fdiv_q(bset->ineq[k][0], bset->ineq[k][0], pnt1->vec->el[0]);
397
398                 k = isl_basic_set_alloc_inequality(bset);
399                 if (k < 0)
400                         goto error;
401                 isl_seq_clr(bset->ineq[k] + 1, total);
402                 if (isl_int_is_pos(t)) {
403                         isl_int_set_si(bset->ineq[k][1 + i], 1);
404                         isl_int_neg(bset->ineq[k][0], pnt2->vec->el[1 + i]);
405                 } else {
406                         isl_int_set_si(bset->ineq[k][1 + i], -1);
407                         isl_int_set(bset->ineq[k][0], pnt2->vec->el[1 + i]);
408                 }
409                 isl_int_fdiv_q(bset->ineq[k][0], bset->ineq[k][0], pnt2->vec->el[0]);
410         }
411
412         bset = isl_basic_set_finalize(bset);
413
414         isl_point_free(pnt1);
415         isl_point_free(pnt2);
416
417         isl_int_clear(t);
418
419         return bset;
420 error:
421         isl_point_free(pnt1);
422         isl_point_free(pnt2);
423         isl_int_clear(t);
424         return NULL;
425 }
426
427 __isl_give isl_set *isl_set_box_from_points(__isl_take isl_point *pnt1,
428         __isl_take isl_point *pnt2)
429 {
430         isl_basic_set *bset;
431         bset = isl_basic_set_box_from_points(pnt1, pnt2);
432         return isl_set_from_basic_set(bset);
433 }
434
435 void isl_point_print(__isl_keep isl_point *pnt, FILE *out)
436 {
437         int i;
438         unsigned nparam;
439         unsigned dim;
440
441         if (!pnt)
442                 return;
443         if (isl_point_is_void(pnt)) {
444                 fprintf(out, "void\n");
445                 return;
446         }
447
448         nparam = isl_dim_size(pnt->dim, isl_dim_param);
449         dim = isl_dim_size(pnt->dim, isl_dim_set);
450         if (nparam > 0) {
451                 fprintf(out, "[");
452                 for (i = 0; i < nparam; ++i) {
453                         const char *name;
454                         if (i)
455                                 fprintf(out, ", ");
456                         name = isl_dim_get_name(pnt->dim, isl_dim_param, i);
457                         if (name)
458                                 fprintf(out, "%s = ", name);
459                         isl_int_print(out, pnt->vec->el[1 + i], 0);
460                         if (!isl_int_is_one(pnt->vec->el[0])) {
461                                 fprintf(out, "/");
462                                 isl_int_print(out, pnt->vec->el[0], 0);
463                         }
464                 }
465                 fprintf(out, "] -> ");
466         }
467         fprintf(out, "[");
468         for (i = 0; i < dim; ++i) {
469                 if (i)
470                         fprintf(out, ", ");
471                 isl_int_print(out, pnt->vec->el[1 + nparam + i], 0);
472                 if (!isl_int_is_one(pnt->vec->el[0])) {
473                         fprintf(out, "/");
474                         isl_int_print(out, pnt->vec->el[0], 0);
475                 }
476         }
477         fprintf(out, "]\n");
478 }