source/int.c

   1 #include <stdlib.h>
   2 #include "../include/cloog/cloog.h"
   3
   4 #define ALLOC(type) (type*)malloc(sizeof(type))
   5 #define ALLOCN(type,n) (type*)malloc((n)*sizeof(type))
   6
   7 #if defined(CLOOG_INT_INT) || \
   8     defined(CLOOG_INT_LONG) || \
   9     defined(CLOOG_INT_LONG_LONG)
  10
  11 cloog_int_t cloog_gcd(cloog_int_t a, cloog_int_t b)
  12 {
  13         while (a) {
  14                 cloog_int_t t = b % a;
  15                 b = a;
  16                 a = t;
  17         }
  18         if (b < 0)
  19                 b = -b;
  20         return b;
  21 }
  22
  23 #endif
  24
  25 struct cloog_vec *cloog_vec_alloc(unsigned size)
  26 {
  27         int i;
  28         struct cloog_vec *vec;
  29
  30         vec = ALLOC(struct cloog_vec);
  31         if (!vec)
  32                 return NULL;
  33
  34         vec->p = ALLOCN(cloog_int_t, size);
  35         if (!vec->p)
  36                 goto error;
  37         vec->size = size;
  38
  39         for (i = 0; i < size; ++i)
  40                 cloog_int_init(vec->p[i]);
  41
  42         return vec;
  43 error:
  44         free(vec);
  45         return NULL;
  46 }
  47
  48 void cloog_vec_free(struct cloog_vec *vec)
  49 {
  50         int i;
  51
  52         if (!vec)
  53                 return;
  54
  55         for (i = 0; i < vec->size; ++i)
  56                 cloog_int_clear(vec->p[i]);
  57         free(vec->p);
  58         free(vec);
  59 }
  60
  61 void cloog_vec_dump(struct cloog_vec *vec)
  62 {
  63         int i;
  64
  65         for (i = 0; i < vec->size; ++i) {
  66                 cloog_int_print(stderr, vec->p[i]);
  67                 fprintf(stderr, " ");
  68         }
  69         fprintf(stderr, "\n");
  70 }
  71
  72 int cloog_seq_first_non_zero(cloog_int_t *p, unsigned len)
  73 {
  74         int i;
  75
  76         for (i = 0; i < len; ++i)
  77                 if (!cloog_int_is_zero(p[i]))
  78                         return i;
  79         return -1;
  80 }
  81
  82 void cloog_seq_neg(cloog_int_t *dst, cloog_int_t *src, unsigned len)
  83 {
  84         int i;
  85         for (i = 0; i < len; ++i)
  86                 cloog_int_neg(dst[i], src[i]);
  87 }
  88
  89 void cloog_seq_cpy(cloog_int_t *dst, cloog_int_t *src, unsigned len)
  90 {
  91         int i;
  92         for (i = 0; i < len; ++i)
  93                 cloog_int_set(dst[i], src[i]);
  94 }
  95
  96 static void cloog_seq_scale_down(cloog_int_t *dst, cloog_int_t *src, cloog_int_t m, unsigned len)
  97 {
  98         int i;
  99         for (i = 0; i < len; ++i)
 100                 cloog_int_divexact(dst[i], src[i], m);
 101 }
 102
 103 void cloog_seq_combine(cloog_int_t *dst, cloog_int_t m1, cloog_int_t *src1,
 104                         cloog_int_t m2, cloog_int_t *src2, unsigned len)
 105 {
 106         int i;
 107         cloog_int_t tmp;
 108
 109         cloog_int_init(tmp);
 110         for (i = 0; i < len; ++i) {
 111                 cloog_int_mul(tmp, m1, src1[i]);
 112                 cloog_int_addmul(tmp, m2, src2[i]);
 113                 cloog_int_set(dst[i], tmp);
 114         }
 115         cloog_int_clear(tmp);
 116 }
 117
 118 static int cloog_seq_abs_min_non_zero(cloog_int_t *p, unsigned len)
 119 {
 120         int i, min = cloog_seq_first_non_zero(p, len);
 121         if (min < 0)
 122                 return -1;
 123         for (i = min + 1; i < len; ++i) {
 124                 if (cloog_int_is_zero(p[i]))
 125                         continue;
 126                 if (cloog_int_abs_lt(p[i], p[min]))
 127                         min = i;
 128         }
 129         return min;
 130 }
 131
 132 void cloog_seq_gcd(cloog_int_t *p, unsigned len, cloog_int_t *gcd)
 133 {
 134         int i, min = cloog_seq_abs_min_non_zero(p, len);
 135
 136         if (min < 0) {
 137                 cloog_int_set_si(*gcd, 0);
 138                 return;
 139         }
 140         cloog_int_abs(*gcd, p[min]);
 141         for (i = 0; cloog_int_cmp_si(*gcd, 1) > 0 && i < len; ++i) {
 142                 if (i == min)
 143                         continue;
 144                 if (cloog_int_is_zero(p[i]))
 145                         continue;
 146                 cloog_int_gcd(*gcd, *gcd, p[i]);
 147         }
 148 }
 149
 150 int cloog_seq_is_neg(cloog_int_t *p1, cloog_int_t *p2, unsigned len)
 151 {
 152         int i;
 153
 154         for (i = 0; i < len; ++i) {
 155                 if (cloog_int_abs_ne(p1[i], p2[i]))
 156                         return 0;
 157                 if (cloog_int_is_zero(p1[i]))
 158                         continue;
 159                 if (cloog_int_eq(p1[i], p2[i]))
 160                         return 0;
 161         }
 162         return 1;
 163 }
 164
 165 void cloog_seq_normalize(cloog_int_t *p, unsigned len)
 166 {
 167         cloog_int_t gcd;
 168
 169         if (len == 0)
 170                 return;
 171
 172         cloog_int_init(gcd);
 173         cloog_seq_gcd(p, len, &gcd);
 174         if (!cloog_int_is_zero(gcd) && !cloog_int_is_one(gcd))
 175                 cloog_seq_scale_down(p, p, gcd, len);
 176         cloog_int_clear(gcd);
 177 }