isl_input.c: extract out common is_start_of_div
[platform/upstream/isl.git] / isl_val.c
1 /*
2  * Copyright 2013      Ecole Normale Superieure
3  *
4  * Use of this software is governed by the MIT license
5  *
6  * Written by Sven Verdoolaege,
7  * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
8  */
9
10 #include <isl_int.h>
11 #include <isl_ctx_private.h>
12 #include <isl_val_private.h>
13
14 #undef BASE
15 #define BASE val
16
17 #include <isl_list_templ.c>
18
19 /* Allocate an isl_val object with indeterminate value.
20  */
21 __isl_give isl_val *isl_val_alloc(isl_ctx *ctx)
22 {
23         isl_val *v;
24
25         v = isl_alloc_type(ctx, struct isl_val);
26         if (!v)
27                 return NULL;
28
29         v->ctx = ctx;
30         isl_ctx_ref(ctx);
31         v->ref = 1;
32         isl_int_init(v->n);
33         isl_int_init(v->d);
34
35         return v;
36 }
37
38 /* Return a reference to an isl_val representing zero.
39  */
40 __isl_give isl_val *isl_val_zero(isl_ctx *ctx)
41 {
42         return isl_val_int_from_si(ctx, 0);
43 }
44
45 /* Return a reference to an isl_val representing one.
46  */
47 __isl_give isl_val *isl_val_one(isl_ctx *ctx)
48 {
49         return isl_val_int_from_si(ctx, 1);
50 }
51
52 /* Return a reference to an isl_val representing NaN.
53  */
54 __isl_give isl_val *isl_val_nan(isl_ctx *ctx)
55 {
56         isl_val *v;
57
58         v = isl_val_alloc(ctx);
59         if (!v)
60                 return NULL;
61
62         isl_int_set_si(v->n, 0);
63         isl_int_set_si(v->d, 0);
64
65         return v;
66 }
67
68 /* Change "v" into a NaN.
69  */
70 __isl_give isl_val *isl_val_set_nan(__isl_take isl_val *v)
71 {
72         if (!v)
73                 return NULL;
74         if (isl_val_is_nan(v))
75                 return v;
76         v = isl_val_cow(v);
77         if (!v)
78                 return NULL;
79
80         isl_int_set_si(v->n, 0);
81         isl_int_set_si(v->d, 0);
82
83         return v;
84 }
85
86 /* Return a reference to an isl_val representing +infinity.
87  */
88 __isl_give isl_val *isl_val_infty(isl_ctx *ctx)
89 {
90         isl_val *v;
91
92         v = isl_val_alloc(ctx);
93         if (!v)
94                 return NULL;
95
96         isl_int_set_si(v->n, 1);
97         isl_int_set_si(v->d, 0);
98
99         return v;
100 }
101
102 /* Return a reference to an isl_val representing -infinity.
103  */
104 __isl_give isl_val *isl_val_neginfty(isl_ctx *ctx)
105 {
106         isl_val *v;
107
108         v = isl_val_alloc(ctx);
109         if (!v)
110                 return NULL;
111
112         isl_int_set_si(v->n, -1);
113         isl_int_set_si(v->d, 0);
114
115         return v;
116 }
117
118 /* Return a reference to an isl_val representing the integer "i".
119  */
120 __isl_give isl_val *isl_val_int_from_si(isl_ctx *ctx, long i)
121 {
122         isl_val *v;
123
124         v = isl_val_alloc(ctx);
125         if (!v)
126                 return NULL;
127
128         isl_int_set_si(v->n, i);
129         isl_int_set_si(v->d, 1);
130
131         return v;
132 }
133
134 /* Change the value of "v" to be equal to the integer "i".
135  */
136 __isl_give isl_val *isl_val_set_si(__isl_take isl_val *v, long i)
137 {
138         if (!v)
139                 return NULL;
140         if (isl_val_is_int(v) && isl_int_cmp_si(v->n, i) == 0)
141                 return v;
142         v = isl_val_cow(v);
143         if (!v)
144                 return NULL;
145
146         isl_int_set_si(v->n, i);
147         isl_int_set_si(v->d, 1);
148
149         return v;
150 }
151
152 /* Change the value of "v" to be equal to zero.
153  */
154 __isl_give isl_val *isl_val_set_zero(__isl_take isl_val *v)
155 {
156         return isl_val_set_si(v, 0);
157 }
158
159 /* Return a reference to an isl_val representing the unsigned integer "u".
160  */
161 __isl_give isl_val *isl_val_int_from_ui(isl_ctx *ctx, unsigned long u)
162 {
163         isl_val *v;
164
165         v = isl_val_alloc(ctx);
166         if (!v)
167                 return NULL;
168
169         isl_int_set_ui(v->n, u);
170         isl_int_set_si(v->d, 1);
171
172         return v;
173 }
174
175 /* Return a reference to an isl_val representing the integer "n".
176  */
177 __isl_give isl_val *isl_val_int_from_isl_int(isl_ctx *ctx, isl_int n)
178 {
179         isl_val *v;
180
181         v = isl_val_alloc(ctx);
182         if (!v)
183                 return NULL;
184
185         isl_int_set(v->n, n);
186         isl_int_set_si(v->d, 1);
187
188         return v;
189 }
190
191 /* Return a reference to an isl_val representing the rational value "n"/"d".
192  * Normalizing the isl_val (if needed) is left to the caller.
193  */
194 __isl_give isl_val *isl_val_rat_from_isl_int(isl_ctx *ctx,
195         isl_int n, isl_int d)
196 {
197         isl_val *v;
198
199         v = isl_val_alloc(ctx);
200         if (!v)
201                 return NULL;
202
203         isl_int_set(v->n, n);
204         isl_int_set(v->d, d);
205
206         return v;
207 }
208
209 /* Return a new reference to "v".
210  */
211 __isl_give isl_val *isl_val_copy(__isl_keep isl_val *v)
212 {
213         if (!v)
214                 return NULL;
215
216         v->ref++;
217         return v;
218 }
219
220 /* Return a fresh copy of "val".
221  */
222 __isl_give isl_val *isl_val_dup(__isl_keep isl_val *val)
223 {
224         isl_val *dup;
225
226         if (!val)
227                 return NULL;
228
229         dup = isl_val_alloc(isl_val_get_ctx(val));
230         if (!dup)
231                 return NULL;
232
233         isl_int_set(dup->n, val->n);
234         isl_int_set(dup->d, val->d);
235
236         return dup;
237 }
238
239 /* Return an isl_val that is equal to "val" and that has only
240  * a single reference.
241  */
242 __isl_give isl_val *isl_val_cow(__isl_take isl_val *val)
243 {
244         if (!val)
245                 return NULL;
246
247         if (val->ref == 1)
248                 return val;
249         val->ref--;
250         return isl_val_dup(val);
251 }
252
253 /* Free "v" and return NULL.
254  */
255 void *isl_val_free(__isl_take isl_val *v)
256 {
257         if (!v)
258                 return NULL;
259
260         if (--v->ref > 0)
261                 return NULL;
262
263         isl_ctx_deref(v->ctx);
264         isl_int_clear(v->n);
265         isl_int_clear(v->d);
266         free(v);
267         return NULL;
268 }
269
270 /* Extract the numerator of a rational value "v" as an integer.
271  *
272  * If "v" is not a rational value, then the result is undefined.
273  */
274 long isl_val_get_num_si(__isl_keep isl_val *v)
275 {
276         if (!v)
277                 return 0;
278         if (!isl_val_is_rat(v))
279                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
280                         "expecting rational value", return 0);
281         if (!isl_int_fits_slong(v->n))
282                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
283                         "numerator too large", return 0);
284         return isl_int_get_si(v->n);
285 }
286
287 /* Extract the numerator of a rational value "v" as an isl_int.
288  *
289  * If "v" is not a rational value, then the result is undefined.
290  */
291 int isl_val_get_num_isl_int(__isl_keep isl_val *v, isl_int *n)
292 {
293         if (!v)
294                 return -1;
295         if (!isl_val_is_rat(v))
296                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
297                         "expecting rational value", return -1);
298         isl_int_set(*n, v->n);
299         return 0;
300 }
301
302 /* Extract the denominator of a rational value "v" as an integer.
303  *
304  * If "v" is not a rational value, then the result is undefined.
305  */
306 long isl_val_get_den_si(__isl_keep isl_val *v)
307 {
308         if (!v)
309                 return 0;
310         if (!isl_val_is_rat(v))
311                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
312                         "expecting rational value", return 0);
313         if (!isl_int_fits_slong(v->d))
314                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
315                         "denominator too large", return 0);
316         return isl_int_get_si(v->d);
317 }
318
319 /* Return an approximation of "v" as a double.
320  */
321 double isl_val_get_d(__isl_keep isl_val *v)
322 {
323         if (!v)
324                 return 0;
325         if (!isl_val_is_rat(v))
326                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
327                         "expecting rational value", return 0);
328         return isl_int_get_d(v->n) / isl_int_get_d(v->d);
329 }
330
331 /* Return the isl_ctx to which "val" belongs.
332  */
333 isl_ctx *isl_val_get_ctx(__isl_keep isl_val *val)
334 {
335         return val ? val->ctx : NULL;
336 }
337
338 /* Normalize "v".
339  *
340  * In particular, make sure that the denominator of a rational value
341  * is positive and the numerator and denominator do not have any
342  * common divisors.
343  *
344  * This function should not be called by an external user
345  * since it will only be given normalized values.
346  */
347 __isl_give isl_val *isl_val_normalize(__isl_take isl_val *v)
348 {
349         isl_ctx *ctx;
350
351         if (!v)
352                 return NULL;
353         if (isl_val_is_int(v))
354                 return v;
355         if (!isl_val_is_rat(v))
356                 return v;
357         if (isl_int_is_neg(v->d)) {
358                 isl_int_neg(v->d, v->d);
359                 isl_int_neg(v->n, v->n);
360         }
361         ctx = isl_val_get_ctx(v);
362         isl_int_gcd(ctx->normalize_gcd, v->n, v->d);
363         if (isl_int_is_one(ctx->normalize_gcd))
364                 return v;
365         isl_int_divexact(v->n, v->n, ctx->normalize_gcd);
366         isl_int_divexact(v->d, v->d, ctx->normalize_gcd);
367         return v;
368 }
369
370 /* Return the opposite of "v".
371  */
372 __isl_give isl_val *isl_val_neg(__isl_take isl_val *v)
373 {
374         if (!v)
375                 return NULL;
376         if (isl_val_is_nan(v))
377                 return v;
378         if (isl_val_is_zero(v))
379                 return v;
380
381         v = isl_val_cow(v);
382         if (!v)
383                 return NULL;
384         isl_int_neg(v->n, v->n);
385
386         return v;
387 }
388
389 /* Return the absolute value of "v".
390  */
391 __isl_give isl_val *isl_val_abs(__isl_take isl_val *v)
392 {
393         if (!v)
394                 return NULL;
395         if (isl_val_is_nan(v))
396                 return v;
397         if (isl_val_is_nonneg(v))
398                 return v;
399         return isl_val_neg(v);
400 }
401
402 /* Return the "floor" (greatest integer part) of "v".
403  * That is, return the result of rounding towards -infinity.
404  */
405 __isl_give isl_val *isl_val_floor(__isl_take isl_val *v)
406 {
407         if (!v)
408                 return NULL;
409         if (isl_val_is_int(v))
410                 return v;
411         if (!isl_val_is_rat(v))
412                 return v;
413
414         v = isl_val_cow(v);
415         if (!v)
416                 return NULL;
417         isl_int_fdiv_q(v->n, v->n, v->d);
418         isl_int_set_si(v->d, 1);
419
420         return v;
421 }
422
423 /* Return the "ceiling" of "v".
424  * That is, return the result of rounding towards +infinity.
425  */
426 __isl_give isl_val *isl_val_ceil(__isl_take isl_val *v)
427 {
428         if (!v)
429                 return NULL;
430         if (isl_val_is_int(v))
431                 return v;
432         if (!isl_val_is_rat(v))
433                 return v;
434
435         v = isl_val_cow(v);
436         if (!v)
437                 return NULL;
438         isl_int_cdiv_q(v->n, v->n, v->d);
439         isl_int_set_si(v->d, 1);
440
441         return v;
442 }
443
444 /* Truncate "v".
445  * That is, return the result of rounding towards zero.
446  */
447 __isl_give isl_val *isl_val_trunc(__isl_take isl_val *v)
448 {
449         if (!v)
450                 return NULL;
451         if (isl_val_is_int(v))
452                 return v;
453         if (!isl_val_is_rat(v))
454                 return v;
455
456         v = isl_val_cow(v);
457         if (!v)
458                 return NULL;
459         isl_int_tdiv_q(v->n, v->n, v->d);
460         isl_int_set_si(v->d, 1);
461
462         return v;
463 }
464
465 /* Return 2^v, where v is an integer (that is not too large).
466  */
467 __isl_give isl_val *isl_val_2exp(__isl_take isl_val *v)
468 {
469         unsigned long exp;
470         int neg;
471
472         v = isl_val_cow(v);
473         if (!v)
474                 return NULL;
475         if (!isl_val_is_int(v))
476                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
477                         "can only compute integer powers",
478                         return isl_val_free(v));
479         neg = isl_val_is_neg(v);
480         if (neg)
481                 isl_int_neg(v->n, v->n);
482         if (!isl_int_fits_ulong(v->n))
483                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
484                         "exponent too large", return isl_val_free(v));
485         exp = isl_int_get_ui(v->n);
486         if (neg) {
487                 isl_int_mul_2exp(v->d, v->d, exp);
488                 isl_int_set_si(v->n, 1);
489         } else {
490                 isl_int_mul_2exp(v->n, v->d, exp);
491         }
492
493         return v;
494 }
495
496 /* Return the minimum of "v1" and "v2".
497  */
498 __isl_give isl_val *isl_val_min(__isl_take isl_val *v1, __isl_take isl_val *v2)
499 {
500         if (!v1 || !v2)
501                 goto error;
502
503         if (isl_val_is_nan(v1)) {
504                 isl_val_free(v2);
505                 return v1;
506         }
507         if (isl_val_is_nan(v2)) {
508                 isl_val_free(v1);
509                 return v2;
510         }
511         if (isl_val_le(v1, v2)) {
512                 isl_val_free(v2);
513                 return v1;
514         } else {
515                 isl_val_free(v1);
516                 return v2;
517         }
518 error:
519         isl_val_free(v1);
520         isl_val_free(v2);
521         return NULL;
522 }
523
524 /* Return the maximum of "v1" and "v2".
525  */
526 __isl_give isl_val *isl_val_max(__isl_take isl_val *v1, __isl_take isl_val *v2)
527 {
528         if (!v1 || !v2)
529                 goto error;
530
531         if (isl_val_is_nan(v1)) {
532                 isl_val_free(v2);
533                 return v1;
534         }
535         if (isl_val_is_nan(v2)) {
536                 isl_val_free(v1);
537                 return v2;
538         }
539         if (isl_val_ge(v1, v2)) {
540                 isl_val_free(v2);
541                 return v1;
542         } else {
543                 isl_val_free(v1);
544                 return v2;
545         }
546 error:
547         isl_val_free(v1);
548         isl_val_free(v2);
549         return NULL;
550 }
551
552 /* Return the sum of "v1" and "v2".
553  */
554 __isl_give isl_val *isl_val_add(__isl_take isl_val *v1, __isl_take isl_val *v2)
555 {
556         if (!v1 || !v2)
557                 goto error;
558         if (isl_val_is_nan(v1)) {
559                 isl_val_free(v2);
560                 return v1;
561         }
562         if (isl_val_is_nan(v2)) {
563                 isl_val_free(v1);
564                 return v2;
565         }
566         if ((isl_val_is_infty(v1) && isl_val_is_neginfty(v2)) ||
567             (isl_val_is_neginfty(v1) && isl_val_is_infty(v2))) {
568                 isl_val_free(v2);
569                 return isl_val_set_nan(v1);
570         }
571         if (isl_val_is_infty(v1) || isl_val_is_neginfty(v1)) {
572                 isl_val_free(v2);
573                 return v1;
574         }
575         if (isl_val_is_infty(v2) || isl_val_is_neginfty(v2)) {
576                 isl_val_free(v1);
577                 return v2;
578         }
579         if (isl_val_is_zero(v1)) {
580                 isl_val_free(v1);
581                 return v2;
582         }
583         if (isl_val_is_zero(v2)) {
584                 isl_val_free(v2);
585                 return v1;
586         }
587
588         v1 = isl_val_cow(v1);
589         if (!v1)
590                 goto error;
591         if (isl_val_is_int(v1) && isl_val_is_int(v2))
592                 isl_int_add(v1->n, v1->n, v2->n);
593         else {
594                 if (isl_int_eq(v1->d, v2->d))
595                         isl_int_add(v1->n, v1->n, v2->n);
596                 else {
597                         isl_int_mul(v1->n, v1->n, v2->d);
598                         isl_int_addmul(v1->n, v2->n, v1->d);
599                         isl_int_mul(v1->d, v1->d, v2->d);
600                 }
601                 v1 = isl_val_normalize(v1);
602         }
603         isl_val_free(v2);
604         return v1;
605 error:
606         isl_val_free(v1);
607         isl_val_free(v2);
608         return NULL;
609 }
610
611 /* Return the sum of "v1" and "v2".
612  */
613 __isl_give isl_val *isl_val_add_ui(__isl_take isl_val *v1, unsigned long v2)
614 {
615         if (!v1)
616                 return NULL;
617         if (!isl_val_is_rat(v1))
618                 return v1;
619         if (v2 == 0)
620                 return v1;
621         v1 = isl_val_cow(v1);
622         if (!v1)
623                 return NULL;
624
625         isl_int_addmul_ui(v1->n, v1->d, v2);
626
627         return v1;
628 }
629
630 /* Subtract "v2" from "v1".
631  */
632 __isl_give isl_val *isl_val_sub(__isl_take isl_val *v1, __isl_take isl_val *v2)
633 {
634         if (!v1 || !v2)
635                 goto error;
636         if (isl_val_is_nan(v1)) {
637                 isl_val_free(v2);
638                 return v1;
639         }
640         if (isl_val_is_nan(v2)) {
641                 isl_val_free(v1);
642                 return v2;
643         }
644         if ((isl_val_is_infty(v1) && isl_val_is_infty(v2)) ||
645             (isl_val_is_neginfty(v1) && isl_val_is_neginfty(v2))) {
646                 isl_val_free(v2);
647                 return isl_val_set_nan(v1);
648         }
649         if (isl_val_is_infty(v1) || isl_val_is_neginfty(v1)) {
650                 isl_val_free(v2);
651                 return v1;
652         }
653         if (isl_val_is_infty(v2) || isl_val_is_neginfty(v2)) {
654                 isl_val_free(v1);
655                 return isl_val_neg(v2);
656         }
657         if (isl_val_is_zero(v2)) {
658                 isl_val_free(v2);
659                 return v1;
660         }
661         if (isl_val_is_zero(v1)) {
662                 isl_val_free(v1);
663                 return isl_val_neg(v2);
664         }
665
666         v1 = isl_val_cow(v1);
667         if (!v1)
668                 goto error;
669         if (isl_val_is_int(v1) && isl_val_is_int(v2))
670                 isl_int_sub(v1->n, v1->n, v2->n);
671         else {
672                 if (isl_int_eq(v1->d, v2->d))
673                         isl_int_sub(v1->n, v1->n, v2->n);
674                 else {
675                         isl_int_mul(v1->n, v1->n, v2->d);
676                         isl_int_submul(v1->n, v2->n, v1->d);
677                         isl_int_mul(v1->d, v1->d, v2->d);
678                 }
679                 v1 = isl_val_normalize(v1);
680         }
681         isl_val_free(v2);
682         return v1;
683 error:
684         isl_val_free(v1);
685         isl_val_free(v2);
686         return NULL;
687 }
688
689 /* Subtract "v2" from "v1".
690  */
691 __isl_give isl_val *isl_val_sub_ui(__isl_take isl_val *v1, unsigned long v2)
692 {
693         if (!v1)
694                 return NULL;
695         if (!isl_val_is_rat(v1))
696                 return v1;
697         if (v2 == 0)
698                 return v1;
699         v1 = isl_val_cow(v1);
700         if (!v1)
701                 return NULL;
702
703         isl_int_submul_ui(v1->n, v1->d, v2);
704
705         return v1;
706 }
707
708 /* Return the product of "v1" and "v2".
709  */
710 __isl_give isl_val *isl_val_mul(__isl_take isl_val *v1, __isl_take isl_val *v2)
711 {
712         if (!v1 || !v2)
713                 goto error;
714         if (isl_val_is_nan(v1)) {
715                 isl_val_free(v2);
716                 return v1;
717         }
718         if (isl_val_is_nan(v2)) {
719                 isl_val_free(v1);
720                 return v2;
721         }
722         if ((!isl_val_is_rat(v1) && isl_val_is_zero(v2)) ||
723             (isl_val_is_zero(v1) && !isl_val_is_rat(v2))) {
724                 isl_val_free(v2);
725                 return isl_val_set_nan(v1);
726         }
727         if (isl_val_is_zero(v1)) {
728                 isl_val_free(v2);
729                 return v1;
730         }
731         if (isl_val_is_zero(v2)) {
732                 isl_val_free(v1);
733                 return v2;
734         }
735         if (isl_val_is_infty(v1) || isl_val_is_neginfty(v1)) {
736                 if (isl_val_is_neg(v2))
737                         v1 = isl_val_neg(v1);
738                 isl_val_free(v2);
739                 return v1;
740         }
741         if (isl_val_is_infty(v2) || isl_val_is_neginfty(v2)) {
742                 if (isl_val_is_neg(v1))
743                         v2 = isl_val_neg(v2);
744                 isl_val_free(v1);
745                 return v2;
746         }
747
748         v1 = isl_val_cow(v1);
749         if (!v1)
750                 goto error;
751         if (isl_val_is_int(v1) && isl_val_is_int(v2))
752                 isl_int_mul(v1->n, v1->n, v2->n);
753         else {
754                 isl_int_mul(v1->n, v1->n, v2->n);
755                 isl_int_mul(v1->d, v1->d, v2->d);
756                 v1 = isl_val_normalize(v1);
757         }
758         isl_val_free(v2);
759         return v1;
760 error:
761         isl_val_free(v1);
762         isl_val_free(v2);
763         return NULL;
764 }
765
766 /* Return the product of "v1" and "v2".
767  *
768  * This is a private copy of isl_val_mul for use in the generic
769  * isl_multi_*_scale_val instantiated for isl_val.
770  */
771 __isl_give isl_val *isl_val_scale_val(__isl_take isl_val *v1,
772         __isl_take isl_val *v2)
773 {
774         return isl_val_mul(v1, v2);
775 }
776
777 /* Return the product of "v1" and "v2".
778  */
779 __isl_give isl_val *isl_val_mul_ui(__isl_take isl_val *v1, unsigned long v2)
780 {
781         if (!v1)
782                 return NULL;
783         if (isl_val_is_nan(v1))
784                 return v1;
785         if (!isl_val_is_rat(v1)) {
786                 if (v2 == 0)
787                         v1 = isl_val_set_nan(v1);
788                 return v1;
789         }
790         if (v2 == 1)
791                 return v1;
792         v1 = isl_val_cow(v1);
793         if (!v1)
794                 return NULL;
795
796         isl_int_mul_ui(v1->n, v1->n, v2);
797
798         return isl_val_normalize(v1);
799 }
800
801 /* Divide "v1" by "v2".
802  */
803 __isl_give isl_val *isl_val_div(__isl_take isl_val *v1, __isl_take isl_val *v2)
804 {
805         if (!v1 || !v2)
806                 goto error;
807         if (isl_val_is_nan(v1)) {
808                 isl_val_free(v2);
809                 return v1;
810         }
811         if (isl_val_is_nan(v2)) {
812                 isl_val_free(v1);
813                 return v2;
814         }
815         if (isl_val_is_zero(v2) ||
816             (!isl_val_is_rat(v1) && !isl_val_is_rat(v2))) {
817                 isl_val_free(v2);
818                 return isl_val_set_nan(v1);
819         }
820         if (isl_val_is_zero(v1)) {
821                 isl_val_free(v2);
822                 return v1;
823         }
824         if (isl_val_is_infty(v1) || isl_val_is_neginfty(v1)) {
825                 if (isl_val_is_neg(v2))
826                         v1 = isl_val_neg(v1);
827                 isl_val_free(v2);
828                 return v1;
829         }
830         if (isl_val_is_infty(v2) || isl_val_is_neginfty(v2)) {
831                 isl_val_free(v2);
832                 return isl_val_set_zero(v1);
833         }
834
835         v1 = isl_val_cow(v1);
836         if (!v1)
837                 goto error;
838         if (isl_val_is_int(v2)) {
839                 isl_int_mul(v1->d, v1->d, v2->n);
840                 v1 = isl_val_normalize(v1);
841         } else {
842                 isl_int_mul(v1->d, v1->d, v2->n);
843                 isl_int_mul(v1->n, v1->n, v2->d);
844                 v1 = isl_val_normalize(v1);
845         }
846         isl_val_free(v2);
847         return v1;
848 error:
849         isl_val_free(v1);
850         isl_val_free(v2);
851         return NULL;
852 }
853
854 /* Given two integer values "v1" and "v2", check if "v1" is divisible by "v2".
855  */
856 int isl_val_is_divisible_by(__isl_keep isl_val *v1, __isl_keep isl_val *v2)
857 {
858         if (!v1 || !v2)
859                 return -1;
860
861         if (!isl_val_is_int(v1) || !isl_val_is_int(v2))
862                 isl_die(isl_val_get_ctx(v1), isl_error_invalid,
863                         "expecting two integers", return -1);
864
865         return isl_int_is_divisible_by(v1->n, v2->n);
866 }
867
868 /* Given two integer values "v1" and "v2", return the residue of "v1"
869  * modulo "v2".
870  */
871 __isl_give isl_val *isl_val_mod(__isl_take isl_val *v1, __isl_take isl_val *v2)
872 {
873         if (!v1 || !v2)
874                 goto error;
875         if (!isl_val_is_int(v1) || !isl_val_is_int(v2))
876                 isl_die(isl_val_get_ctx(v1), isl_error_invalid,
877                         "expecting two integers", goto error);
878         if (isl_val_is_nonneg(v1) && isl_val_lt(v1, v2)) {
879                 isl_val_free(v2);
880                 return v1;
881         }
882         v1 = isl_val_cow(v1);
883         if (!v1)
884                 goto error;
885         isl_int_fdiv_r(v1->n, v1->n, v2->n);
886         isl_val_free(v2);
887         return v1;
888 error:
889         isl_val_free(v1);
890         isl_val_free(v2);
891         return NULL;
892 }
893
894 /* Given two integer values, return their greatest common divisor.
895  */
896 __isl_give isl_val *isl_val_gcd(__isl_take isl_val *v1, __isl_take isl_val *v2)
897 {
898         if (!v1 || !v2)
899                 goto error;
900         if (!isl_val_is_int(v1) || !isl_val_is_int(v2))
901                 isl_die(isl_val_get_ctx(v1), isl_error_invalid,
902                         "expecting two integers", goto error);
903         if (isl_val_eq(v1, v2)) {
904                 isl_val_free(v2);
905                 return v1;
906         }
907         if (isl_val_is_one(v1)) {
908                 isl_val_free(v2);
909                 return v1;
910         }
911         if (isl_val_is_one(v2)) {
912                 isl_val_free(v1);
913                 return v2;
914         }
915         v1 = isl_val_cow(v1);
916         if (!v1)
917                 goto error;
918         isl_int_gcd(v1->n, v1->n, v2->n);
919         isl_val_free(v2);
920         return v1;
921 error:
922         isl_val_free(v1);
923         isl_val_free(v2);
924         return NULL;
925 }
926
927 /* Given two integer values v1 and v2, return their greatest common divisor g,
928  * as well as two integers x and y such that x * v1 + y * v2 = g.
929  */
930 __isl_give isl_val *isl_val_gcdext(__isl_take isl_val *v1,
931         __isl_take isl_val *v2, __isl_give isl_val **x, __isl_give isl_val **y)
932 {
933         isl_ctx *ctx;
934         isl_val *a = NULL, *b = NULL;
935
936         if (!x && !y)
937                 return isl_val_gcd(v1, v2);
938
939         if (!v1 || !v2)
940                 goto error;
941
942         ctx = isl_val_get_ctx(v1);
943         if (!isl_val_is_int(v1) || !isl_val_is_int(v2))
944                 isl_die(ctx, isl_error_invalid,
945                         "expecting two integers", goto error);
946
947         v1 = isl_val_cow(v1);
948         a = isl_val_alloc(ctx);
949         b = isl_val_alloc(ctx);
950         if (!v1 || !a || !b)
951                 goto error;
952         isl_int_gcdext(v1->n, a->n, b->n, v1->n, v2->n);
953         if (x) {
954                 isl_int_set_si(a->d, 1);
955                 *x = a;
956         } else
957                 isl_val_free(a);
958         if (y) {
959                 isl_int_set_si(b->d, 1);
960                 *y = b;
961         } else
962                 isl_val_free(b);
963         isl_val_free(v2);
964         return v1;
965 error:
966         isl_val_free(v1);
967         isl_val_free(v2);
968         isl_val_free(a);
969         isl_val_free(b);
970         if (x)
971                 *x = NULL;
972         if (y)
973                 *y = NULL;
974         return NULL;
975 }
976
977 /* Does "v" represent an integer value?
978  */
979 int isl_val_is_int(__isl_keep isl_val *v)
980 {
981         if (!v)
982                 return -1;
983
984         return isl_int_is_one(v->d);
985 }
986
987 /* Does "v" represent a rational value?
988  */
989 int isl_val_is_rat(__isl_keep isl_val *v)
990 {
991         if (!v)
992                 return -1;
993
994         return !isl_int_is_zero(v->d);
995 }
996
997 /* Does "v" represent NaN?
998  */
999 int isl_val_is_nan(__isl_keep isl_val *v)
1000 {
1001         if (!v)
1002                 return -1;
1003
1004         return isl_int_is_zero(v->n) && isl_int_is_zero(v->d);
1005 }
1006
1007 /* Does "v" represent +infinity?
1008  */
1009 int isl_val_is_infty(__isl_keep isl_val *v)
1010 {
1011         if (!v)
1012                 return -1;
1013
1014         return isl_int_is_pos(v->n) && isl_int_is_zero(v->d);
1015 }
1016
1017 /* Does "v" represent -infinity?
1018  */
1019 int isl_val_is_neginfty(__isl_keep isl_val *v)
1020 {
1021         if (!v)
1022                 return -1;
1023
1024         return isl_int_is_neg(v->n) && isl_int_is_zero(v->d);
1025 }
1026
1027 /* Does "v" represent the integer zero?
1028  */
1029 int isl_val_is_zero(__isl_keep isl_val *v)
1030 {
1031         if (!v)
1032                 return -1;
1033
1034         return isl_int_is_zero(v->n) && !isl_int_is_zero(v->d);
1035 }
1036
1037 /* Does "v" represent the integer one?
1038  */
1039 int isl_val_is_one(__isl_keep isl_val *v)
1040 {
1041         if (!v)
1042                 return -1;
1043
1044         return isl_int_eq(v->n, v->d);
1045 }
1046
1047 /* Does "v" represent the integer negative one?
1048  */
1049 int isl_val_is_negone(__isl_keep isl_val *v)
1050 {
1051         if (!v)
1052                 return -1;
1053
1054         return isl_int_is_neg(v->n) && isl_int_abs_eq(v->n, v->d);
1055 }
1056
1057 /* Is "v" (strictly) positive?
1058  */
1059 int isl_val_is_pos(__isl_keep isl_val *v)
1060 {
1061         if (!v)
1062                 return -1;
1063
1064         return isl_int_is_pos(v->n);
1065 }
1066
1067 /* Is "v" (strictly) negative?
1068  */
1069 int isl_val_is_neg(__isl_keep isl_val *v)
1070 {
1071         if (!v)
1072                 return -1;
1073
1074         return isl_int_is_neg(v->n);
1075 }
1076
1077 /* Is "v" non-negative?
1078  */
1079 int isl_val_is_nonneg(__isl_keep isl_val *v)
1080 {
1081         if (!v)
1082                 return -1;
1083
1084         if (isl_val_is_nan(v))
1085                 return 0;
1086
1087         return isl_int_is_nonneg(v->n);
1088 }
1089
1090 /* Is "v" non-positive?
1091  */
1092 int isl_val_is_nonpos(__isl_keep isl_val *v)
1093 {
1094         if (!v)
1095                 return -1;
1096
1097         if (isl_val_is_nan(v))
1098                 return 0;
1099
1100         return isl_int_is_nonpos(v->n);
1101 }
1102
1103 /* Return the sign of "v".
1104  *
1105  * The sign of NaN is undefined.
1106  */
1107 int isl_val_sgn(__isl_keep isl_val *v)
1108 {
1109         if (!v)
1110                 return 0;
1111         if (isl_val_is_zero(v))
1112                 return 0;
1113         if (isl_val_is_pos(v))
1114                 return 1;
1115         return -1;
1116 }
1117
1118 /* Is "v1" (strictly) less than "v2"?
1119  */
1120 int isl_val_lt(__isl_keep isl_val *v1, __isl_keep isl_val *v2)
1121 {
1122         isl_int t;
1123         int lt;
1124
1125         if (!v1 || !v2)
1126                 return -1;
1127         if (isl_val_is_int(v1) && isl_val_is_int(v2))
1128                 return isl_int_lt(v1->n, v2->n);
1129         if (isl_val_is_nan(v1) || isl_val_is_nan(v2))
1130                 return 0;
1131         if (isl_val_eq(v1, v2))
1132                 return 0;
1133         if (isl_val_is_infty(v2))
1134                 return 1;
1135         if (isl_val_is_infty(v1))
1136                 return 0;
1137         if (isl_val_is_neginfty(v1))
1138                 return 1;
1139         if (isl_val_is_neginfty(v2))
1140                 return 0;
1141
1142         isl_int_init(t);
1143         isl_int_mul(t, v1->n, v2->d);
1144         isl_int_submul(t, v2->n, v1->d);
1145         lt = isl_int_is_neg(t);
1146         isl_int_clear(t);
1147
1148         return lt;
1149 }
1150
1151 /* Is "v1" (strictly) greater than "v2"?
1152  */
1153 int isl_val_gt(__isl_keep isl_val *v1, __isl_keep isl_val *v2)
1154 {
1155         return isl_val_lt(v2, v1);
1156 }
1157
1158 /* Is "v1" less than or equal to "v2"?
1159  */
1160 int isl_val_le(__isl_keep isl_val *v1, __isl_keep isl_val *v2)
1161 {
1162         isl_int t;
1163         int le;
1164
1165         if (!v1 || !v2)
1166                 return -1;
1167         if (isl_val_is_int(v1) && isl_val_is_int(v2))
1168                 return isl_int_le(v1->n, v2->n);
1169         if (isl_val_is_nan(v1) || isl_val_is_nan(v2))
1170                 return 0;
1171         if (isl_val_eq(v1, v2))
1172                 return 1;
1173         if (isl_val_is_infty(v2))
1174                 return 1;
1175         if (isl_val_is_infty(v1))
1176                 return 0;
1177         if (isl_val_is_neginfty(v1))
1178                 return 1;
1179         if (isl_val_is_neginfty(v2))
1180                 return 0;
1181
1182         isl_int_init(t);
1183         isl_int_mul(t, v1->n, v2->d);
1184         isl_int_submul(t, v2->n, v1->d);
1185         le = isl_int_is_nonpos(t);
1186         isl_int_clear(t);
1187
1188         return le;
1189 }
1190
1191 /* Is "v1" greater than or equal to "v2"?
1192  */
1193 int isl_val_ge(__isl_keep isl_val *v1, __isl_keep isl_val *v2)
1194 {
1195         return isl_val_le(v2, v1);
1196 }
1197
1198 /* How does "v" compare to "i"?
1199  *
1200  * Return 1 if v is greater, -1 if v is smaller and 0 if v is equal to i.
1201  *
1202  * If v is NaN (or NULL), then the result is undefined.
1203  */
1204 int isl_val_cmp_si(__isl_keep isl_val *v, long i)
1205 {
1206         isl_int t;
1207         int cmp;
1208
1209         if (!v)
1210                 return 0;
1211         if (isl_val_is_int(v))
1212                 return isl_int_cmp_si(v->n, i);
1213         if (isl_val_is_nan(v))
1214                 return 0;
1215         if (isl_val_is_infty(v))
1216                 return 1;
1217         if (isl_val_is_neginfty(v))
1218                 return -1;
1219
1220         isl_int_init(t);
1221         isl_int_mul_si(t, v->d, i);
1222         isl_int_sub(t, v->n, t);
1223         cmp = isl_int_sgn(t);
1224         isl_int_clear(t);
1225
1226         return cmp;
1227 }
1228
1229 /* Is "v1" equal to "v2"?
1230  */
1231 int isl_val_eq(__isl_keep isl_val *v1, __isl_keep isl_val *v2)
1232 {
1233         if (!v1 || !v2)
1234                 return -1;
1235         if (isl_val_is_nan(v1) || isl_val_is_nan(v2))
1236                 return 0;
1237
1238         return isl_int_eq(v1->n, v2->n) && isl_int_eq(v1->d, v2->d);
1239 }
1240
1241 /* Is "v1" different from "v2"?
1242  */
1243 int isl_val_ne(__isl_keep isl_val *v1, __isl_keep isl_val *v2)
1244 {
1245         if (!v1 || !v2)
1246                 return -1;
1247         if (isl_val_is_nan(v1) || isl_val_is_nan(v2))
1248                 return 0;
1249
1250         return isl_int_ne(v1->n, v2->n) || isl_int_ne(v1->d, v2->d);
1251 }
1252
1253 /* Print a textual representation of "v" onto "p".
1254  */
1255 __isl_give isl_printer *isl_printer_print_val(__isl_take isl_printer *p,
1256         __isl_keep isl_val *v)
1257 {
1258         int neg;
1259
1260         if (!p || !v)
1261                 return isl_printer_free(p);
1262
1263         neg = isl_int_is_neg(v->n);
1264         if (neg) {
1265                 p = isl_printer_print_str(p, "-");
1266                 isl_int_neg(v->n, v->n);
1267         }
1268         if (isl_int_is_zero(v->d)) {
1269                 int sgn = isl_int_sgn(v->n);
1270                 p = isl_printer_print_str(p, sgn < 0 ? "-infty" :
1271                                             sgn == 0 ? "NaN" : "infty");
1272         } else
1273                 p = isl_printer_print_isl_int(p, v->n);
1274         if (neg)
1275                 isl_int_neg(v->n, v->n);
1276         if (!isl_int_is_zero(v->d) && !isl_int_is_one(v->d)) {
1277                 p = isl_printer_print_str(p, "/");
1278                 p = isl_printer_print_isl_int(p, v->d);
1279         }
1280
1281         return p;
1282 }
1283
1284 /* Insert "n" dimensions of type "type" at position "first".
1285  *
1286  * This function is only meant to be used in the generic isl_multi_*
1287  * functions which have to deal with base objects that have an associated
1288  * space.  Since an isl_val does not have an associated space, this function
1289  * does not do anything.
1290  */
1291 __isl_give isl_val *isl_val_insert_dims(__isl_take isl_val *v,
1292         enum isl_dim_type type, unsigned first, unsigned n)
1293 {
1294         return v;
1295 }
1296
1297 /* Drop the the "n" first dimensions of type "type" at position "first".
1298  *
1299  * This function is only meant to be used in the generic isl_multi_*
1300  * functions which have to deal with base objects that have an associated
1301  * space.  Since an isl_val does not have an associated space, this function
1302  * does not do anything.
1303  */
1304 __isl_give isl_val *isl_val_drop_dims(__isl_take isl_val *v,
1305         enum isl_dim_type type, unsigned first, unsigned n)
1306 {
1307         return v;
1308 }
1309
1310 /* Change the name of the dimension of type "type" at position "pos" to "s".
1311  *
1312  * This function is only meant to be used in the generic isl_multi_*
1313  * functions which have to deal with base objects that have an associated
1314  * space.  Since an isl_val does not have an associated space, this function
1315  * does not do anything.
1316  */
1317 __isl_give isl_val *isl_val_set_dim_name(__isl_take isl_val *v,
1318         enum isl_dim_type type, unsigned pos, const char *s)
1319 {
1320         return v;
1321 }
1322
1323 /* Reset the domain space of "v" to "space".
1324  *
1325  * This function is only meant to be used in the generic isl_multi_*
1326  * functions which have to deal with base objects that have an associated
1327  * space.  Since an isl_val does not have an associated space, this function
1328  * does not do anything, apart from error handling and cleaning up memory.
1329  */
1330 __isl_give isl_val *isl_val_reset_domain_space(__isl_take isl_val *v,
1331         __isl_take isl_space *space)
1332 {
1333         if (!space)
1334                 return isl_val_free(v);
1335         isl_space_free(space);
1336         return v;
1337 }
1338
1339 /* Reorder the dimensions of the domain of "v" according
1340  * to the given reordering.
1341  *
1342  * This function is only meant to be used in the generic isl_multi_*
1343  * functions which have to deal with base objects that have an associated
1344  * space.  Since an isl_val does not have an associated space, this function
1345  * does not do anything, apart from error handling and cleaning up memory.
1346  */
1347 __isl_give isl_val *isl_val_realign_domain(__isl_take isl_val *v,
1348         __isl_take isl_reordering *r)
1349 {
1350         if (!r)
1351                 return isl_val_free(v);
1352         isl_reordering_free(r);
1353         return v;
1354 }
1355
1356 /* Return an isl_val that is zero on "ls".
1357  *
1358  * This function is only meant to be used in the generic isl_multi_*
1359  * functions which have to deal with base objects that have an associated
1360  * space.  Since an isl_val does not have an associated space, this function
1361  * simply returns a zero isl_val in the same context as "ls".
1362  */
1363 __isl_give isl_val *isl_val_zero_on_domain(__isl_take isl_local_space *ls)
1364 {
1365         isl_ctx *ctx;
1366
1367         if (!ls)
1368                 return NULL;
1369         ctx = isl_local_space_get_ctx(ls);
1370         isl_local_space_free(ls);
1371         return isl_val_zero(ctx);
1372 }
1373
1374 /* Check that the domain space of "v" matches "space".
1375  *
1376  * Return 0 on success and -1 on error.
1377  *
1378  * This function is only meant to be used in the generic isl_multi_*
1379  * functions which have to deal with base objects that have an associated
1380  * space.  Since an isl_val does not have an associated space, this function
1381  * simply returns 0, except if "v" or "space" are NULL.
1382  */
1383 int isl_val_check_match_domain_space(__isl_keep isl_val *v,
1384         __isl_keep isl_space *space)
1385 {
1386         if (!v || !space)
1387                 return -1;
1388         return 0;
1389 }
1390
1391 #undef BASE
1392 #define BASE val
1393
1394 #define NO_GIST
1395 #define NO_IDENTITY
1396 #define NO_FROM_BASE
1397 #include <isl_multi_templ.c>
1398
1399 /* Apply "fn" to each of the elements of "mv" with as second argument "v".
1400  */
1401 static __isl_give isl_multi_val *isl_multi_val_fn_val(
1402         __isl_take isl_multi_val *mv,
1403         __isl_give isl_val *(*fn)(__isl_take isl_val *v1,
1404                                         __isl_take isl_val *v2),
1405         __isl_take isl_val *v)
1406 {
1407         int i;
1408
1409         mv = isl_multi_val_cow(mv);
1410         if (!mv || !v)
1411                 goto error;
1412
1413         for (i = 0; i < mv->n; ++i) {
1414                 mv->p[i] = fn(mv->p[i], isl_val_copy(v));
1415                 if (!mv->p[i])
1416                         goto error;
1417         }
1418
1419         isl_val_free(v);
1420         return mv;
1421 error:
1422         isl_val_free(v);
1423         isl_multi_val_free(mv);
1424         return NULL;
1425 }
1426
1427 /* Add "v" to each of the elements of "mv".
1428  */
1429 __isl_give isl_multi_val *isl_multi_val_add_val(__isl_take isl_multi_val *mv,
1430         __isl_take isl_val *v)
1431 {
1432         if (!v)
1433                 return isl_multi_val_free(mv);
1434         if (isl_val_is_zero(v)) {
1435                 isl_val_free(v);
1436                 return mv;
1437         }
1438         return isl_multi_val_fn_val(mv, &isl_val_add, v);
1439 }
1440
1441 /* Reduce the elements of "mv" modulo "v".
1442  */
1443 __isl_give isl_multi_val *isl_multi_val_mod_val(__isl_take isl_multi_val *mv,
1444         __isl_take isl_val *v)
1445 {
1446         return isl_multi_val_fn_val(mv, &isl_val_mod, v);
1447 }