From: Sven Verdoolaege Date: Wed, 19 Jun 2013 09:22:18 +0000 (+0200) Subject: try and avoid depending on mpz_gcdext internals X-Git-Tag: isl-0.12~2 X-Git-Url: https://repo.or.cz/w/isl.git/commitdiff_plain/0a83197c479109b0f7c327484b80a878f291b296 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 --- diff --git a/configure.ac b/configure.ac index bb19ddec..edd36931 100644 --- 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 ]) +AC_RUN_IFELSE([AC_LANG_PROGRAM([[#include ]], [[ + 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 d488fd2e..2dbce62e 100644 --- a/isl_gmp.c +++ b/isl_gmp.c @@ -1,3 +1,4 @@ +#include /* * 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 8f09f65e..c661f292 100644 --- a/isl_int.h +++ b/isl_int.h @@ -13,6 +13,7 @@ #include #include #include +#include #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)