[Gmp-commit] /var/hg/gmp: primesieve.c: Fill sieve with a presieved 70bits pa...

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/652acd606f78
changeset: 16971:652acd606f78
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Thu Nov 19 08:53:24 2015 +0100
description:
primesieve.c: Fill sieve with a presieved 70bits pattern.

diffstat:

 primesieve.c |  38 ++++++++++++++++++++++++++++++++------
 1 files changed, 32 insertions(+), 6 deletions(-)

diffs (83 lines):

diff -r 9845905fe548 -r 652acd606f78 primesieve.c
--- a/primesieve.c	Mon Nov 16 18:44:27 2015 +0100
+++ b/primesieve.c	Thu Nov 19 08:53:24 2015 +0100
@@ -130,8 +130,9 @@
 #endif /* 30 */
 #endif /* 61 */
 
+/* FIXME: cleanup code, and support offset also for 32-bits machines */
 static mp_limb_t
-fill_bitpattern (mp_ptr bit_array, mp_size_t limbs)
+fill_bitpattern (mp_ptr bit_array, mp_size_t limbs, mp_limb_t offset)
 {
 #ifdef SIEVE_MASK1
   mp_limb_t mask = SIEVE_MASK1;
@@ -140,6 +141,13 @@
 #ifdef SIEVE_MASK2
   mp_limb_t mask2= SIEVE_MASK2;
 
+  offset %= 70;
+  if (offset)
+    {
+      /* FIXME: support nonzero offset!! */
+        MPN_ZERO (bit_array, limbs);
+	return 0;
+    }
   do {
     *bit_array = mask;
     if (--limbs == 0)
@@ -149,6 +157,25 @@
     mask2 = mask2 << (70 - GMP_LIMB_BITS * 2) | mask >> (GMP_LIMB_BITS - (70 - GMP_LIMB_BITS * 2));
     mask = mask << (70 - GMP_LIMB_BITS * 2) | tail;
 #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;
+    }
+  };
   do {
     *bit_array = mask;
     tmp = mask >> (GMP_LIMB_BITS - (70 - GMP_LIMB_BITS));
@@ -176,7 +203,7 @@
   bits  = n_to_bit(n);
   limbs = bits / GMP_LIMB_BITS + 1;
 
-  i = fill_bitpattern (bit_array, limbs);
+  i = fill_bitpattern (bit_array, limbs, 0);
   bit_array[0] = SIEVE_SEED;
 
   if ((bits + 1) % GMP_LIMB_BITS != 0)
@@ -234,16 +261,15 @@
 block_resieve (mp_ptr bit_array, mp_size_t limbs, mp_limb_t offset,
 		      mp_srcptr sieve, mp_limb_t sieve_bits)
 {
-  mp_size_t bits, step;
+  mp_size_t bits, step, i;
 
   ASSERT (limbs > 0);
 
   bits = limbs * GMP_LIMB_BITS - 1;
 
-  /* FIXME: We can skip 5 and 7 too, filling with a 70-bits pattern. */
-  MPN_FILL (bit_array, limbs, 0);
+  i = fill_bitpattern (bit_array, limbs, offset);
 
-  LOOP_ON_SIEVE_BEGIN(step,0,sieve_bits,0,sieve);
+  LOOP_ON_SIEVE_BEGIN(step,i,sieve_bits,0,sieve);
   {
     mp_size_t lindex;
     mp_limb_t lmask;