isl_gmp.c

   1 /*
   2  * Copyright 2008-2009 Katholieke Universiteit Leuven
   3  *
   4  * Use of this software is governed by the MIT license
   5  *
   6  * Written by Sven Verdoolaege, K.U.Leuven, Departement
   7  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
   8  */
   9
  10 #include <isl_int.h>
  11
  12 uint32_t isl_gmp_hash(mpz_t v, uint32_t hash)
  13 {
  14         int sa = v[0]._mp_size;
  15         int abs_sa = sa < 0 ? -sa : sa;
  16         unsigned char *data = (unsigned char *)v[0]._mp_d;
  17         unsigned char *end = data + abs_sa * sizeof(v[0]._mp_d[0]);
  18
  19         if (sa < 0)
  20                 isl_hash_byte(hash, 0xFF);
  21         for (; data < end; ++data)
  22                 isl_hash_byte(hash, *data);
  23         return hash;
  24 }
  25
  26 /* This function tries to produce outputs that do not depend on
  27  * the version of GMP that is being used.
  28  *
  29  * In particular, when computing the extended gcd of -1 and 9,
  30  * some versions will produce
  31  *
  32  *      1 = -1 * -1 + 0 * 9
  33  *
  34  * while other versions will produce
  35  *
  36  *      1 = 8 * -1 + 1 * 9
  37  *
  38  * If configure detects that we are in the former case, then
  39  * mpz_gcdext will be called directly.  Otherwise, this function
  40  * is called and then we try to mimic the behavior of the other versions.
  41  */
  42 void isl_gmp_gcdext(mpz_t G, mpz_t S, mpz_t T, mpz_t A, mpz_t B)
  43 {
  44         if (mpz_divisible_p(B, A)) {
  45                 mpz_set_si(S, mpz_sgn(A));
  46                 mpz_set_si(T, 0);
  47                 mpz_abs(G, A);
  48                 return;
  49         }
  50         if (mpz_divisible_p(A, B)) {
  51                 mpz_set_si(S, 0);
  52                 mpz_set_si(T, mpz_sgn(B));
  53                 mpz_abs(G, B);
  54                 return;
  55         }
  56         mpz_gcdext(G, S, T, A, B);
  57 }