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 int cloog_seq_first_non_zero(cloog_int_t *p, unsigned len)
  62 {
  63         int i;
  64
  65         for (i = 0; i < len; ++i)
  66                 if (!cloog_int_is_zero(p[i]))
  67                         return i;
  68         return -1;
  69 }
  70
  71 void cloog_seq_neg(cloog_int_t *dst, cloog_int_t *src, unsigned len)
  72 {
  73         int i;
  74         for (i = 0; i < len; ++i)
  75                 cloog_int_neg(dst[i], src[i]);
  76 }
  77
  78 void cloog_seq_cpy(cloog_int_t *dst, cloog_int_t *src, unsigned len)
  79 {
  80         int i;
  81         for (i = 0; i < len; ++i)
  82                 cloog_int_set(dst[i], src[i]);
  83 }
  84
  85 static void cloog_seq_scale_down(cloog_int_t *dst, cloog_int_t *src, cloog_int_t m, unsigned len)
  86 {
  87         int i;
  88         for (i = 0; i < len; ++i)
  89                 cloog_int_divexact(dst[i], src[i], m);
  90 }
  91
  92 void cloog_seq_combine(cloog_int_t *dst, cloog_int_t m1, cloog_int_t *src1,
  93                         cloog_int_t m2, cloog_int_t *src2, unsigned len)
  94 {
  95         int i;
  96         cloog_int_t tmp;
  97
  98         cloog_int_init(tmp);
  99         for (i = 0; i < len; ++i) {
 100                 cloog_int_mul(tmp, m1, src1[i]);
 101                 cloog_int_addmul(tmp, m2, src2[i]);
 102                 cloog_int_set(dst[i], tmp);
 103         }
 104         cloog_int_clear(tmp);
 105 }
 106
 107 static int cloog_seq_abs_min_non_zero(cloog_int_t *p, unsigned len)
 108 {
 109         int i, min = cloog_seq_first_non_zero(p, len);
 110         if (min < 0)
 111                 return -1;
 112         for (i = min + 1; i < len; ++i) {
 113                 if (cloog_int_is_zero(p[i]))
 114                         continue;
 115                 if (cloog_int_abs_lt(p[i], p[min]))
 116                         min = i;
 117         }
 118         return min;
 119 }
 120
 121 void cloog_seq_gcd(cloog_int_t *p, unsigned len, cloog_int_t *gcd)
 122 {
 123         int i, min = cloog_seq_abs_min_non_zero(p, len);
 124
 125         if (min < 0) {
 126                 cloog_int_set_si(*gcd, 0);
 127                 return;
 128         }
 129         cloog_int_abs(*gcd, p[min]);
 130         for (i = 0; cloog_int_cmp_si(*gcd, 1) > 0 && i < len; ++i) {
 131                 if (i == min)
 132                         continue;
 133                 if (cloog_int_is_zero(p[i]))
 134                         continue;
 135                 cloog_int_gcd(*gcd, *gcd, p[i]);
 136         }
 137 }
 138
 139 int cloog_seq_is_neg(cloog_int_t *p1, cloog_int_t *p2, unsigned len)
 140 {
 141         int i;
 142
 143         for (i = 0; i < len; ++i) {
 144                 if (cloog_int_abs_ne(p1[i], p2[i]))
 145                         return 0;
 146                 if (cloog_int_is_zero(p1[i]))
 147                         continue;
 148                 if (cloog_int_eq(p1[i], p2[i]))
 149                         return 0;
 150         }
 151         return 1;
 152 }
 153
 154 void cloog_seq_normalize(cloog_int_t *p, unsigned len)
 155 {
 156         cloog_int_t gcd;
 157
 158         if (len == 0)
 159                 return;
 160
 161         cloog_int_init(gcd);
 162         cloog_seq_gcd(p, len, &gcd);
 163         if (!cloog_int_is_zero(gcd) && !cloog_int_is_one(gcd))
 164                 cloog_seq_scale_down(p, p, gcd, len);
 165         cloog_int_clear(gcd);
 166 }