[Gmp-commit] /var/hg/gmp: 3 new changesets

mercurial at gmplib.org mercurial at gmplib.org
Tue Nov 24 14:32:31 UTC 2015


details:   /var/hg/gmp/rev/c045a87a0f31
changeset: 16978:c045a87a0f31
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Mon Nov 23 17:34:36 2015 +0100
description:
-typo

details:   /var/hg/gmp/rev/ec7d16a99272
changeset: 16979:ec7d16a99272
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Tue Nov 24 15:29:22 2015 +0100
description:
(fill_bitpattern): support two independent mask, use for 64-bits.

details:   /var/hg/gmp/rev/bb072477386f
changeset: 16980:bb072477386f
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Tue Nov 24 15:31:26 2015 +0100
description:
ChangeLog

diffstat:

 ChangeLog    |    2 +
 doc/gmp.texi |    2 +-
 primesieve.c |  179 ++++++++++++++++++++++++++++++++++++++++++++--------------
 3 files changed, 137 insertions(+), 46 deletions(-)

diffs (272 lines):

diff -r bd9580e00fe9 -r bb072477386f ChangeLog
--- a/ChangeLog	Sun Nov 22 10:18:21 2015 +0100
+++ b/ChangeLog	Tue Nov 24 15:31:26 2015 +0100
@@ -9,6 +9,8 @@
 	* tune/speed.h: Declare it.
 	* tune/speed.c (routine): Add mpz_primorial_ui.
 
+	* primesieve.c: Use two presieved patterns on 64-bits CPUs.
+
 2015-11-13 Marco Bodrato <bodrato at mail.dm.unipi.it>
 
 	* mini-gmp/mini-gmp.c: Lazy allocation for mpz_t.
diff -r bd9580e00fe9 -r bb072477386f doc/gmp.texi
--- a/doc/gmp.texi	Sun Nov 22 10:18:21 2015 +0100
+++ b/doc/gmp.texi	Tue Nov 24 15:31:26 2015 +0100
@@ -4231,7 +4231,7 @@
 Rational numbers are stored in objects of type @code{mpq_t}.
 
 All rational arithmetic functions assume operands have a canonical form, and
-canonicalize their result.  The canonical from means that the denominator and
+canonicalize their result.  The canonical form means that the denominator and
 the numerator have no common factors, and that the denominator is positive.
 Zero has the unique representation 0/1.
 
diff -r bd9580e00fe9 -r bb072477386f primesieve.c
--- a/primesieve.c	Sun Nov 22 10:18:21 2015 +0100
+++ b/primesieve.c	Tue Nov 24 15:31:26 2015 +0100
@@ -38,10 +38,6 @@
 #include "gmp.h"
 #include "gmp-impl.h"
 
-/*********************************************************/
-/* Section sieve: sieving functions and tools for primes */
-/*********************************************************/
-
 #if 0
 static mp_limb_t
 bit_to_n (mp_limb_t bit) { return (bit*3+4)|1; }
@@ -62,17 +58,30 @@
 
 #if GMP_LIMB_BITS > 61
 #define SIEVE_SEED CNST_LIMB(0x3294C9E069128480)
+#if GMP_LIMB_BITS == 64
+/* 110bits pre-sieved mask for primes 5, 11*/
+#define SIEVE_MASK1 CNST_LIMB(0x3204C1A049120485)
+#define SIEVE_MASKT CNST_LIMB(0xA1204892058)
+/* 182bits pre-sieved mask for primes 7, 13*/
+#define SIEVE_2MSK1 CNST_LIMB(0x029048402110840A)
+#define SIEVE_2MSK2 CNST_LIMB(0x9402180C40230184)
+#define SIEVE_2MSKT CNST_LIMB(0x5021088402120)
+#define SEED_LIMIT 210
+#else
 #if GMP_LIMB_BITS < 67
+/* 70bits pre-sieved mask for primes 5, 7*/
 #define SIEVE_MASK1 CNST_LIMB(0x1214896069128483)
 #define SIEVE_MASKT (CNST_LIMB(0x3) << (66 - GMP_LIMB_BITS))
 #define SEED_LIMIT 208
 #else
 #define SEED_LIMIT 202
 #endif
+#endif
 #else
 #if GMP_LIMB_BITS > 30
 #define SIEVE_SEED CNST_LIMB(0x69128480)
 #if GMP_LIMB_BITS < 35
+/* 70bits pre-sieved mask for primes 5, 7*/
 #define SIEVE_MASK1 CNST_LIMB(0x69128483)
 #define SIEVE_MASK2 (CNST_LIMB(0x1214896) << (36 - GMP_LIMB_BITS))
 #define SIEVE_MASKT (CNST_LIMB(0x3) << (34 - GMP_LIMB_BITS))
@@ -96,59 +105,132 @@
 #endif /* 30 */
 #endif /* 61 */
 
-/* FIXME: cleanup code, and support offset also for 32-bits machines */
+#define SET_OFF1(m1, m2, M1, M2, off, BITS)		\
+  if (off) {						\
+    if (off < GMP_LIMB_BITS) {				\
+      m1 = (M1 >> off) | (M2 << (GMP_LIMB_BITS - off));	\
+      if (off <= BITS - GMP_LIMB_BITS) {		\
+	m2 = M1 << (BITS - GMP_LIMB_BITS - off)		\
+	  | M2 >> off;					\
+      } else {						\
+	m1 |= M1 << (BITS - off);			\
+	m2 = M1 >> (off + GMP_LIMB_BITS - BITS);	\
+      }							\
+    } else {						\
+      m1 = M1 << (BITS - off)				\
+	| M2 >> (off - GMP_LIMB_BITS);			\
+      m2 = M2 << (BITS - off)				\
+	| M1 >> (off + GMP_LIMB_BITS - BITS);		\
+    }							\
+  } else {						\
+    m1 = M1; m2 = M2;					\
+  }
+
+#define SET_OFF2(m1, m2, m3, M1, M2, M3, off, BITS)	\
+  if (off) {						\
+    if (off <= GMP_LIMB_BITS) {				\
+      m1 = M2 << (GMP_LIMB_BITS - off);			\
+      m2 = M3 << (GMP_LIMB_BITS - off);			\
+      if (off != GMP_LIMB_BITS) {			\
+	m1 |= (M1 >> off);				\
+	m2 |= (M2 >> off);				\
+      }							\
+      if (off <= BITS - 2 * GMP_LIMB_BITS) {		\
+	m3 = M1 << (BITS - 2 * GMP_LIMB_BITS - off)	\
+	  | M3 >> off;					\
+      } else {						\
+	m2 |= M1 << (BITS - GMP_LIMB_BITS - off);	\
+	m3 = M1 >> (off + 2 * GMP_LIMB_BITS - BITS);	\
+      }							\
+    } else if (off < 2 *GMP_LIMB_BITS) {		\
+      m1 = M2 >> (off - GMP_LIMB_BITS)			\
+	| M3 << (2 * GMP_LIMB_BITS - off);		\
+      if (off <= BITS - GMP_LIMB_BITS) {		\
+	m2 = M3 >> (off - GMP_LIMB_BITS)		\
+	  | M1 << (BITS - GMP_LIMB_BITS - off);		\
+	m3 = M2 << (BITS - GMP_LIMB_BITS - off);	\
+	if (off != BITS - GMP_LIMB_BITS) {		\
+	  m3 |= M1 >> (off + 2 * GMP_LIMB_BITS - BITS);	\
+	}						\
+      } else {						\
+	m1 |= M1 << (BITS - off);			\
+	m2 = M2 << (BITS - off)				\
+	  | M1 >> (GMP_LIMB_BITS - BITS + off);		\
+	m3 = M2 >> (GMP_LIMB_BITS - BITS + off);	\
+      }							\
+    } else {						\
+      m1 = M1 << (BITS - off)				\
+	| M3 >> (off - 2 * GMP_LIMB_BITS);		\
+      m2 = M2 << (BITS - off)				\
+	| M1 >> (off + GMP_LIMB_BITS - BITS);		\
+      m3 = M3 << (BITS - off)				\
+	| M2 >> (off + GMP_LIMB_BITS - BITS);		\
+    }							\
+  } else {						\
+    m1 = M1; m2 = M2; m3 = M3;				\
+  }
+
+#define ROTATE1(m1, m2, BITS)			\
+  do {						\
+    mp_limb_t __tmp;				\
+    __tmp = m1 >> (2 * GMP_LIMB_BITS - BITS);	\
+    m1 = (m1 << (BITS - GMP_LIMB_BITS)) | m2;	\
+    m2 = __tmp;					\
+  } while (0)
+
+#define ROTATE2(m1, m2, m3, BITS)		\
+  do {						\
+    mp_limb_t __tmp;				\
+    __tmp = m2 >> (3 * GMP_LIMB_BITS - BITS);	\
+    m2 = m2 << (BITS - GMP_LIMB_BITS * 2)	\
+      | m1 >> (3 * GMP_LIMB_BITS - BITS);	\
+    m1 = m1 << (BITS - GMP_LIMB_BITS * 2) | m3;	\
+    m3 = __tmp;					\
+  } while (0)
+
+/* FIXME: cleanup code, to support different conditions. */
 static mp_limb_t
 fill_bitpattern (mp_ptr bit_array, mp_size_t limbs, mp_limb_t offset)
 {
+#ifdef SIEVE_2MSK2
+  mp_limb_t m11, m12, m21, m22, m23;
+
+  m21 = offset % 110;
+  SET_OFF1 (m11, m12, SIEVE_MASK1, SIEVE_MASKT, m21, 110);
+  offset %= 182;
+  SET_OFF2 (m21, m22, m23, SIEVE_2MSK1, SIEVE_2MSK2, SIEVE_2MSKT, offset, 182);
+  do {
+    *bit_array = m11 | m21;
+    if (--limbs == 0)
+      break;
+    ROTATE1 (m11, m12, 110);
+    *++bit_array = m11 | m22;
+    ROTATE1 (m11, m12, 110);
+    ROTATE2 (m21, m22, m23, 182);
+    bit_array++;
+  } while (--limbs != 0);
+  return 4;
+#else
 #ifdef SIEVE_MASK1
-  mp_limb_t mask = SIEVE_MASK1;
-  mp_limb_t tail = SIEVE_MASKT;
-  mp_limb_t tmp;
+  mp_limb_t mask, tail;
 #ifdef SIEVE_MASK2
-  mp_limb_t mask2= SIEVE_MASK2;
+  mp_limb_t mask2;
 
   offset %= 70;
-  if (offset)
-    {
-      /* FIXME: support nonzero offset!! */
-        MPN_ZERO (bit_array, limbs);
-	return 0;
-    }
+  SET_OFF2 (mask, mask2, tail, SIEVE_MASK1, SIEVE_MASK2, SIEVE_MASKT, offset, 70);
   do {
     *bit_array = mask;
     if (--limbs == 0)
       break;
     *++bit_array = mask2;
-    tmp = mask2 >> (GMP_LIMB_BITS - (70 - GMP_LIMB_BITS * 2));
-    mask2 = mask2 << (70 - GMP_LIMB_BITS * 2) | mask >> (GMP_LIMB_BITS - (70 - GMP_LIMB_BITS * 2));
-    mask = mask << (70 - GMP_LIMB_BITS * 2) | tail;
+    ROTATE2 (mask, mask2, tail, 70);
 #else
   offset %= 70;
-  if (offset) {
-    if (offset < GMP_LIMB_BITS) {
-      tmp = mask << (GMP_LIMB_BITS - offset);
-      mask >>= offset;
-      mask |= tail << (GMP_LIMB_BITS - offset);
-      if (offset <= 70 - GMP_LIMB_BITS) {
-	tail = (tail >> offset) | (tmp >> (GMP_LIMB_BITS * 2 - 70));
-      } else {
-	mask |= tmp << (70 - GMP_LIMB_BITS);
-	tail = tmp >> (GMP_LIMB_BITS * 2 - 70);
-      }
-    } else {
-      tmp = mask >> (offset + GMP_LIMB_BITS - 70);
-      mask <<= 70 - offset;
-      mask |= tail >> (offset - GMP_LIMB_BITS);
-      tail = ((tail << (70 - offset)) | tmp) & 0x3f;
-    }
-  };
+  SET_OFF1 (mask, tail, SIEVE_MASK1, SIEVE_MASKT, offset, 70);
   do {
     *bit_array = mask;
-    tmp = mask >> (GMP_LIMB_BITS - (70 - GMP_LIMB_BITS));
-    mask <<= 70 - GMP_LIMB_BITS;
+    ROTATE1 (mask, tail, 70);
 #endif
-    mask |= tail;
-    tail = tmp;
     bit_array++;
   } while (--limbs != 0);
   return 2;
@@ -156,6 +238,7 @@
   MPN_ZERO (bit_array, limbs);
   return 0;
 #endif
+#endif
 }
 
 static void
@@ -334,14 +417,20 @@
   if ((bits + 1) % GMP_LIMB_BITS != 0)
     bit_array[size-1] |= MP_LIMB_T_MAX << ((bits + 1) % GMP_LIMB_BITS);
 
-
   return size * GMP_LIMB_BITS - mpn_popcount (bit_array, size);
 }
 
 #undef BLOCK_SIZE
 #undef SEED_LIMIT
 #undef SIEVE_SEED
-#undef LOOP_ON_SIEVE_CLOSE
-#undef LOOP_ON_SIEVE_NOCOND
-#undef LOOP_ON_SIEVE_BEGIN
-#undef LOOP_ON_SIEVE_CONTINUE
+#undef SIEVE_MASK1
+#undef SIEVE_MASK2
+#undef SIEVE_MASKT
+#undef SIEVE_2MSK1
+#undef SIEVE_2MSK2
+#undef SIEVE_2MSKT
+#undef SET_OFF1
+#undef SET_OFF2
+#undef ROTATE1
+#undef ROTATE2
+


More information about the gmp-commit mailing list