try and avoid depending on mpz_gcdext internals

The results of mpz_gcdext are not uniquely defined and may depend
on the version of GMP used.  Since the results may influence the
construction of the stride offset in detect_stride in isl_ast_build.c,
this may result in user visible differences.

We therefore try to obtain more consistent results by analyzing
the results of the installed version of GMP and calling a modified
version of mpz_gcdext if needed.  This modified version may not
be complete and may still have to be extended.  In the worst case,
we may have to revert to the open-coded version that was removed in
10a7f8a (isl_ast_build.c: use isl_int_gcdext instead of open-coded version,
Wed Apr 17 17:51:55 2013 +0200).

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>

diff --git a/configure.ac b/configure.ac
index bb19dde..edd3693 100644 (file)
--- a/configure.ac
+++ b/configure.ac
@@ -71,13 +71,39 @@ build)
        ;;
 esac
 SAVE_CPPFLAGS="$CPPFLAGS"
+SAVE_LDFLAGS="$LDFLAGS"
+SAVE_LIBS="$LIBS"
 CPPFLAGS="$GMP_CPPFLAGS $CPPFLAGS"
+LDFLAGS="$GMP_LDFLAGS $LDFLAGS"
+LIBS="$GMP_LIBS $LIBS"
 need_get_memory_functions=false
 AC_CHECK_DECLS(mp_get_memory_functions,[],[
        need_get_memory_functions=true
 ],[#include <gmp.h>])
+AC_RUN_IFELSE([AC_LANG_PROGRAM([[#include <gmp.h>]], [[
+       mpz_t x,y,g,a,b;
+       mpz_init(x);
+       mpz_init(y);
+       mpz_init(g);
+       mpz_init(a);
+       mpz_init(b);
+       mpz_set_si(x, -1);
+       mpz_set_si(y, 9);
+       mpz_gcdext(g, a, b, x, y);
+       if (mpz_get_si(a) == -1 && mpz_get_si(b) == 0)
+               return 0;
+       else
+               return 1;
+]])], [need_normalized_gcdext=false], [need_normalized_gcdext=true],
+[need_normalized_gcdext=true])
 CPPFLAGS="$SAVE_CPPFLAGS"
+LDFLAGS="$SAVE_LDFLAGS"
+LIBS="$SAVE_LIBS"
 AM_CONDITIONAL(NEED_GET_MEMORY_FUNCTIONS, test x$need_get_memory_functions = xtrue)
+if test $need_normalized_gcdext = true; then
+AC_DEFINE([GMP_NORMALIZE_GCDEXT], [],
+       [result of mpz_gcdext needs to be normalized])
+fi
 
 AX_SUBMODULE(piplib,no|system|build,no)
 

diff --git a/isl_gmp.c b/isl_gmp.c
index d488fd2..2dbce62 100644 (file)
--- a/isl_gmp.c
+++ b/isl_gmp.c
@@ -1,3 +1,4 @@
+#include <stdio.h>
 /*
  * Copyright 2008-2009 Katholieke Universiteit Leuven
  *
@@ -22,3 +23,36 @@ uint32_t isl_gmp_hash(mpz_t v, uint32_t hash)
                isl_hash_byte(hash, *data);
        return hash;
 }
+
+/* This function tries to produce outputs that do not depend on
+ * the version of GMP that is being used.
+ *
+ * In particular, when computing the extended gcd of -1 and 9,
+ * some versions will produce
+ *
+ *     1 = -1 * -1 + 0 * 9
+ *
+ * while other versions will produce
+ *
+ *     1 = 8 * -1 + 1 * 9
+ *
+ * If configure detects that we are in the former case, then
+ * mpz_gcdext will be called directly.  Otherwise, this function
+ * is called and then we try to mimic the behavior of the other versions.
+ */
+void isl_gmp_gcdext(mpz_t G, mpz_t S, mpz_t T, mpz_t A, mpz_t B)
+{
+       if (mpz_divisible_p(B, A)) {
+               mpz_set_si(S, mpz_sgn(A));
+               mpz_set_si(T, 0);
+               mpz_abs(G, A);
+               return;
+       }
+       if (mpz_divisible_p(A, B)) {
+               mpz_set_si(S, 0);
+               mpz_set_si(T, mpz_sgn(B));
+               mpz_abs(G, B);
+               return;
+       }
+       mpz_gcdext(G, S, T, A, B);
+}

diff --git a/isl_int.h b/isl_int.h
index 8f09f65..c661f29 100644 (file)
--- a/isl_int.h
+++ b/isl_int.h
@@ -13,6 +13,7 @@
 #include <isl/hash.h>
 #include <string.h>
 #include <gmp.h>
+#include <isl_config.h>
 
 #ifndef mp_get_memory_functions
 void mp_get_memory_functions(
@@ -68,7 +69,12 @@ typedef void (*isl_int_print_gmp_free_t)(void *, size_t);
 #define isl_int_submul_ui(r,i,j)       mpz_submul_ui(r,i,j)
 
 #define isl_int_gcd(r,i,j)     mpz_gcd(r,i,j)
+#ifdef GMP_NORMALIZE_GCDEXT
+void isl_gmp_gcdext(mpz_t G, mpz_t S, mpz_t T, mpz_t A, mpz_t B);
+#define isl_int_gcdext(g,x,y,i,j)      isl_gmp_gcdext(g,x,y,i,j)
+#else
 #define isl_int_gcdext(g,x,y,i,j)      mpz_gcdext(g,x,y,i,j)
+#endif
 #define isl_int_lcm(r,i,j)     mpz_lcm(r,i,j)
 #define isl_int_divexact(r,i,j)        mpz_divexact(r,i,j)
 #define isl_int_divexact_ui(r,i,j)     mpz_divexact_ui(r,i,j)