mpn/generic/mulmod_bknp1.c: New file, with mpn_{mul,sqr}mod_bknp1

configure.ac: Compile it
gmp-impl.h: Define new functions

1 files changed, 63 insertions, 0 deletions

diff --git a/gmp-impl.h b/gmp-impl.h
index 60d7ee345..099c92b2b 100644
--- a/gmp-impl.h
+++ b/gmp-impl.h
@@ -1276,6 +1276,64 @@ mpn_mulmod_bnm1_itch (mp_size_t rn, mp_size_t an, mp_size_t bn) {
   return itch;
 }
 
+#ifndef MOD_BKNP1_USE11
+#define MOD_BKNP1_USE11 ((GMP_NUMB_BITS % 8 != 0) && (GMP_NUMB_BITS % 2 == 0))
+#endif
+#ifndef MOD_BKNP1_ONLY3
+#define MOD_BKNP1_ONLY3 0
+#endif
+#define mpn_mulmod_bknp1 __MPN(mulmod_bknp1)
+__GMP_DECLSPEC void mpn_mulmod_bknp1 (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, unsigned, mp_ptr);
+static inline mp_size_t
+mpn_mulmod_bknp1_itch (mp_size_t rn) {
+  return rn << 2;
+}
+#if MOD_BKNP1_ONLY3
+#define MPN_MULMOD_BKNP1_USABLE(rn, k, mn)				\
+  ((GMP_NUMB_BITS % 8 == 0) && ((mn) >= 18) && ((rn) > 16) &&		\
+   (((rn) % ((k) = 3) == 0)))
+#else
+#define MPN_MULMOD_BKNP1_USABLE(rn, k, mn)				\
+  ((GMP_NUMB_BITS % 8 == 0) && ((mn) >= 18) && ((rn) > 16) &&		\
+   (((rn) % ((k) = 3) == 0) ||						\
+    ((GMP_NUMB_BITS % 16 != 0) || ((mn) >= 35) && ((rn) >= 32)) &&	\
+    ((GMP_NUMB_BITS % 16 == 0) && ((rn) % ((k) = 5) == 0) ||		\
+     ((mn) >= 49) &&							\
+     (((rn) % ((k) = 7) == 0) ||					\
+      (GMP_NUMB_BITS % 16 == 0) && ((mn) >= 104) && ((rn) >= 64) &&	\
+      ((MOD_BKNP1_USE11 && ((rn) % ((k) = 11) == 0)) ||			\
+       ((rn) % ((k) = 13) == 0) ||					\
+       (GMP_NUMB_BITS % 32 == 0) && ((mn) >= 136) && ((rn) >= 128) &&	\
+       ((rn) % ((k) = 17) == 0)						\
+       )))))
+#endif
+
+#define mpn_sqrmod_bknp1 __MPN(sqrmod_bknp1)
+__GMP_DECLSPEC void mpn_sqrmod_bknp1 (mp_ptr, mp_srcptr, mp_size_t, unsigned, mp_ptr);
+static inline mp_size_t
+mpn_sqrmod_bknp1_itch (mp_size_t rn) {
+  return rn * 3;
+}
+#if MOD_BKNP1_ONLY3
+#define MPN_SQRMOD_BKNP1_USABLE(rn, k, mn)				\
+  MPN_MULMOD_BKNP1_USABLE(rn, k, mn)
+#else
+#define MPN_SQRMOD_BKNP1_USABLE(rn, k, mn)				\
+  ((GMP_NUMB_BITS % 8 == 0) && ((mn) >= 27) && ((rn) > 24) &&		\
+   (((rn) % ((k) = 3) == 0) ||						\
+    ((GMP_NUMB_BITS % 16 != 0) || ((mn) >= 55) && ((rn) > 50)) &&	\
+    ((GMP_NUMB_BITS % 16 == 0) && ((rn) % ((k) = 5) == 0) ||		\
+     ((mn) >= 56) &&							\
+     (((rn) % ((k) = 7) == 0) ||					\
+      (GMP_NUMB_BITS % 16 == 0) && ((mn) >= 143) && ((rn) >= 128) &&	\
+      ((MOD_BKNP1_USE11 && ((rn) % ((k) = 11) == 0)) ||			\
+       ((rn) % ((k) = 13) == 0) ||					\
+       (GMP_NUMB_BITS % 32 == 0) && ((mn) >= 272) && ((rn) >= 256) &&	\
+       ((rn) % ((k) = 17) == 0)						\
+       )))))
+#endif
+
+
 #define mpn_sqrmod_bnm1 __MPN(sqrmod_bnm1)
 __GMP_DECLSPEC void mpn_sqrmod_bnm1 (mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
 #define mpn_sqrmod_bnm1_next_size __MPN(sqrmod_bnm1_next_size)
@@ -1697,6 +1755,11 @@ __GMP_DECLSPEC void mpn_sec_pi1_div_r (mp_ptr, mp_size_t, mp_srcptr, mp_size_t,
   (15 & 1 * mpn_bdiv_dbm1 (dst, src, size, __GMP_CAST (mp_limb_t, GMP_NUMB_MASK / 15)))
 #endif
 
+#if GMP_NUMB_BITS % 8 == 0
+#define mpn_divexact_by17(dst,src,size) \
+  (31 & 15 * mpn_bdiv_dbm1 (dst, src, size, __GMP_CAST (mp_limb_t, GMP_NUMB_MASK / 17)))
+#endif
+
 #define mpz_divexact_gcd  __gmpz_divexact_gcd
 __GMP_DECLSPEC void    mpz_divexact_gcd (mpz_ptr, mpz_srcptr, mpz_srcptr);