isl_seq.c

   1 #include "isl_seq.h"
   2
   3 void isl_seq_clr(isl_int *p, unsigned len)
   4 {
   5         int i;
   6         for (i = 0; i < len; ++i)
   7                 isl_int_set_si(p[i], 0);
   8 }
   9
  10 void isl_seq_neg(isl_int *dst, isl_int *src, unsigned len)
  11 {
  12         int i;
  13         for (i = 0; i < len; ++i)
  14                 isl_int_neg(dst[i], src[i]);
  15 }
  16
  17 void isl_seq_cpy(isl_int *dst, isl_int *src, unsigned len)
  18 {
  19         int i;
  20         for (i = 0; i < len; ++i)
  21                 isl_int_set(dst[i], src[i]);
  22 }
  23
  24 void isl_seq_submul(isl_int *dst, isl_int f, isl_int *src, unsigned len)
  25 {
  26         int i;
  27         for (i = 0; i < len; ++i)
  28                 isl_int_submul(dst[i], f, src[i]);
  29 }
  30
  31 void isl_seq_swp_or_cpy(isl_int *dst, isl_int *src, unsigned len)
  32 {
  33         int i;
  34         for (i = 0; i < len; ++i)
  35                 isl_int_swap_or_set(dst[i], src[i]);
  36 }
  37
  38 void isl_seq_scale(isl_int *dst, isl_int *src, isl_int m, unsigned len)
  39 {
  40         int i;
  41         for (i = 0; i < len; ++i)
  42                 isl_int_mul(dst[i], src[i], m);
  43 }
  44
  45 void isl_seq_scale_down(isl_int *dst, isl_int *src, isl_int m, unsigned len)
  46 {
  47         int i;
  48         for (i = 0; i < len; ++i)
  49                 isl_int_divexact(dst[i], src[i], m);
  50 }
  51
  52 void isl_seq_combine(isl_int *dst, isl_int m1, isl_int *src1,
  53                         isl_int m2, isl_int *src2, unsigned len)
  54 {
  55         int i;
  56         isl_int tmp;
  57
  58         isl_int_init(tmp);
  59         for (i = 0; i < len; ++i) {
  60                 isl_int_mul(tmp, m1, src1[i]);
  61                 isl_int_addmul(tmp, m2, src2[i]);
  62                 isl_int_set(dst[i], tmp);
  63         }
  64         isl_int_clear(tmp);
  65 }
  66
  67 /*
  68  * Let d = dst[pos] and s = src[pos]
  69  * dst is replaced by |s| dst - sgn(s)d src
  70  */
  71 void isl_seq_elim(isl_int *dst, isl_int *src, unsigned pos, unsigned len,
  72                   isl_int *m)
  73 {
  74         isl_int a;
  75         isl_int b;
  76
  77         if (isl_int_is_zero(dst[pos]))
  78                 return;
  79
  80         isl_int_init(a);
  81         isl_int_init(b);
  82
  83         isl_int_gcd(a, src[pos], dst[pos]);
  84         isl_int_divexact(b, dst[pos], a);
  85         if (isl_int_is_pos(src[pos]))
  86                 isl_int_neg(b, b);
  87         isl_int_divexact(a, src[pos], a);
  88         isl_int_abs(a, a);
  89         isl_seq_combine(dst, a, dst, b, src, len);
  90
  91         if (m)
  92                 isl_int_mul(*m, *m, a);
  93
  94         isl_int_clear(a);
  95         isl_int_clear(b);
  96 }
  97
  98 int isl_seq_eq(isl_int *p1, isl_int *p2, unsigned len)
  99 {
 100         int i;
 101         for (i = 0; i < len; ++i)
 102                 if (isl_int_ne(p1[i], p2[i]))
 103                         return 0;
 104         return 1;
 105 }
 106
 107 int isl_seq_cmp(isl_int *p1, isl_int *p2, unsigned len)
 108 {
 109         int i;
 110         int cmp;
 111         for (i = 0; i < len; ++i)
 112                 if ((cmp = isl_int_cmp(p1[i], p2[i])) != 0)
 113                         return cmp;
 114         return 0;
 115 }
 116
 117 int isl_seq_is_neg(isl_int *p1, isl_int *p2, unsigned len)
 118 {
 119         int i;
 120
 121         for (i = 0; i < len; ++i) {
 122                 if (isl_int_abs_ne(p1[i], p2[i]))
 123                         return 0;
 124                 if (isl_int_is_zero(p1[i]))
 125                         continue;
 126                 if (isl_int_eq(p1[i], p2[i]))
 127                         return 0;
 128         }
 129         return 1;
 130 }
 131
 132 int isl_seq_first_non_zero(isl_int *p, unsigned len)
 133 {
 134         int i;
 135
 136         for (i = 0; i < len; ++i)
 137                 if (!isl_int_is_zero(p[i]))
 138                         return i;
 139         return -1;
 140 }
 141
 142 int isl_seq_abs_min_non_zero(isl_int *p, unsigned len)
 143 {
 144         int i, min = isl_seq_first_non_zero(p, len);
 145         if (min < 0)
 146                 return -1;
 147         for (i = min + 1; i < len; ++i) {
 148                 if (isl_int_is_zero(p[i]))
 149                         continue;
 150                 if (isl_int_abs_lt(p[i], p[min]))
 151                         min = i;
 152         }
 153         return min;
 154 }
 155
 156 void isl_seq_gcd(isl_int *p, unsigned len, isl_int *gcd)
 157 {
 158         int i, min = isl_seq_abs_min_non_zero(p, len);
 159
 160         if (min < 0) {
 161                 isl_int_set_si(*gcd, 0);
 162                 return;
 163         }
 164         isl_int_abs(*gcd, p[min]);
 165         for (i = 0; isl_int_cmp_si(*gcd, 1) > 0 && i < len; ++i) {
 166                 if (i == min)
 167                         continue;
 168                 if (isl_int_is_zero(p[i]))
 169                         continue;
 170                 isl_int_gcd(*gcd, *gcd, p[i]);
 171         }
 172 }
 173
 174 void isl_seq_normalize(isl_int *p, unsigned len)
 175 {
 176         isl_int gcd;
 177
 178         if (len == 0)
 179                 return;
 180         isl_int_init(gcd);
 181         isl_seq_gcd(p, len, &gcd);
 182         if (!isl_int_is_zero(gcd))
 183                 isl_seq_scale_down(p, p, gcd, len);
 184         isl_int_clear(gcd);
 185 }
 186
 187 void isl_seq_lcm(isl_int *p, unsigned len, isl_int *lcm)
 188 {
 189         int i;
 190
 191         if (len == 0) {
 192                 isl_int_set_si(*lcm, 1);
 193                 return;
 194         }
 195         isl_int_set(*lcm, p[0]);
 196         for (i = 1; i < len; ++i)
 197                 isl_int_lcm(*lcm, *lcm, p[i]);
 198 }
 199
 200 void isl_seq_inner_product(isl_int *p1, isl_int *p2, unsigned len,
 201                            isl_int *prod)
 202 {
 203         int i;
 204         if (len == 0) {
 205                 isl_int_set_si(*prod, 0);
 206                 return;
 207         }
 208         isl_int_mul(*prod, p1[0], p2[0]);
 209         for (i = 1; i < len; ++i)
 210                 isl_int_addmul(*prod, p1[i], p2[i]);
 211 }
 212
 213 uint32_t isl_seq_hash(isl_int *p, unsigned len, uint32_t hash)
 214 {
 215         int i;
 216         for (i = 0; i < len; ++i) {
 217                 if (isl_int_is_zero(p[i]))
 218                         continue;
 219                 hash *= 16777619;
 220                 hash ^= (i & 0xFF);
 221                 hash = isl_int_hash(p[i], hash);
 222         }
 223         return hash;
 224 }
 225
 226 uint32_t isl_seq_get_hash(isl_int *p, unsigned len)
 227 {
 228         uint32_t hash = isl_hash_init();
 229
 230         return isl_seq_hash(p, len, hash);
 231 }
 232
 233 uint32_t isl_seq_get_hash_bits(isl_int *p, unsigned len, unsigned bits)
 234 {
 235         uint32_t hash;
 236
 237         hash = isl_seq_get_hash(p, len);
 238         return isl_hash_bits(hash, bits);
 239 }