diff options
| -rw-r--r-- | ChangeLog | 5 | ||||
| -rw-r--r-- | gen-sieve.c | 75 | ||||
| -rw-r--r-- | primesieve.c | 22 |
3 files changed, 80 insertions, 22 deletions
@@ -1,3 +1,8 @@ +2022-01-05 Marco Bodrato <bodrato@mail.dm.unipi.it> + + * gen-sieve.c: Generate masks depending on bit size. + * primesieve.c: Remove fixed size (32 and 64 only) masks. + 2021-12-11 Marco Bodrato <bodrato@mail.dm.unipi.it> * mpn/generic/toom3_sqr.c: Use a shorter mul when it's simple. diff --git a/gen-sieve.c b/gen-sieve.c index 8fac3413f..713391802 100644 --- a/gen-sieve.c +++ b/gen-sieve.c @@ -2,7 +2,7 @@ Contributed to the GNU project by Marco Bodrato. -Copyright 2021 Free Software Foundation, Inc. +Copyright 2021, 2022 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -86,12 +86,82 @@ generate (int limb_bits, int limit) printf ("#define PRIMESIEVE_NUMBEROF_TABLE %d\n", c); printf ("/* #define PRIMESIEVE_PRIMES_IN_TABLE %d */\n", totpc); - printf ("/* #define PRIMESIEVE_HIGHEST_PRIME %d */\n", maxprime); + printf ("#define PRIMESIEVE_HIGHEST_PRIME %d\n", maxprime); printf ("/* #define PRIMESIEVE_FIRST_UNCHECKED %d */\n", bit_to_n (limit)); return c; } +void +setmask (mpz_t mask, int a, int b) +{ + mpz_set_ui (mask, 0); + for (unsigned i = 0; i < 2 * a * b; ++i) + if ((bit_to_n (i) % a == 0) || (bit_to_n (i) % b == 0)) + mpz_setbit (mask, i); +} + +void +gen_sieve_masks (int limb_bits) { + mpz_t mask, limb; + + mpz_init (mask); + mpz_init (limb); + + printf ("\n"); + if (limb_bits > 60 && limb_bits < 91) + { + setmask (mask, 5, 11); + + mpz_tdiv_r_2exp (limb, mask, limb_bits); + printf ("#define SIEVE_MASK1 CNST_LIMB(0x"); + mpz_out_str (stdout, -16, limb); + printf (")\n"); + mpz_tdiv_q_2exp (limb, mask, limb_bits); + printf ("#define SIEVE_MASKT CNST_LIMB(0x"); + mpz_out_str (stdout, -16, limb); + printf (")\n"); + + setmask (mask, 7, 13); + + mpz_tdiv_r_2exp (limb, mask, limb_bits); + printf ("#define SIEVE_2MSK1 CNST_LIMB(0x"); + mpz_out_str (stdout, -16, limb); + printf (")\n"); + mpz_tdiv_q_2exp (mask, mask, limb_bits); + mpz_tdiv_r_2exp (limb, mask, limb_bits); + printf ("#define SIEVE_2MSK2 CNST_LIMB(0x"); + mpz_out_str (stdout, -16, limb); + printf (")\n"); + mpz_tdiv_q_2exp (limb, mask, limb_bits); + printf ("#define SIEVE_2MSKT CNST_LIMB(0x"); + mpz_out_str (stdout, -16, limb); + printf (")\n"); + } + else if (limb_bits > 23 && limb_bits < 36) + { + setmask (mask, 5, 7); + + mpz_tdiv_r_2exp (limb, mask, limb_bits); + printf ("#define SIEVE_MASK1 CNST_LIMB(0x"); + mpz_out_str (stdout, -16, limb); + printf (")\n"); + mpz_tdiv_q_2exp (mask, mask, limb_bits); + mpz_tdiv_r_2exp (limb, mask, limb_bits); + printf ("#define SIEVE_MASK2 CNST_LIMB(0x"); + mpz_out_str (stdout, -16, limb); + printf (")\n"); + mpz_tdiv_q_2exp (limb, mask, limb_bits); + printf ("#define SIEVE_MASKT CNST_LIMB(0x"); + mpz_out_str (stdout, -16, limb); + printf (")\n"); + } + printf ("\n"); + + mpz_clear (limb); + mpz_clear (mask); +} + /* 5*2 = 10 7*2 = 14 5*7*2 = 70 (2*35, 3*24, 4*18, 5*14...) @@ -118,6 +188,7 @@ main (int argc, char *argv[]) if (limit % limb_bits != 0) limit += limb_bits - limit % limb_bits; generate (limb_bits, limit); + gen_sieve_masks (limb_bits); return 0; } diff --git a/primesieve.c b/primesieve.c index 2a33add64..567fab0f5 100644 --- a/primesieve.c +++ b/primesieve.c @@ -7,7 +7,7 @@ IT IS ONLY SAFE TO REACH IT THROUGH DOCUMENTED INTERFACES. IN FACT, IT IS ALMOST GUARANTEED THAT IT WILL CHANGE OR DISAPPEAR IN A FUTURE GNU MP RELEASE. -Copyright 2010-2012, 2015, 2016, 2021 Free Software Foundation, Inc. +Copyright 2010-2012, 2015, 2016, 2021, 2022 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -59,23 +59,6 @@ static mp_size_t primesieve_size (mp_limb_t n) { return n_fto_bit(n) / GMP_LIMB_BITS + 1; } #endif -#if GMP_LIMB_BITS == 64 -/* 110bits pre-sieved mask for primes 5, 11*/ -#define SIEVE_MASK1 CNST_LIMB(0x81214a1204892058) -#define SIEVE_MASKT CNST_LIMB(0xc8130681244) -/* 182bits pre-sieved mask for primes 7, 13*/ -#define SIEVE_2MSK1 CNST_LIMB(0x9402180c40230184) -#define SIEVE_2MSK2 CNST_LIMB(0x0285021088402120) -#define SIEVE_2MSKT CNST_LIMB(0xa41210084421) -#endif - -#if GMP_LIMB_BITS == 32 -/* 70bits pre-sieved mask for primes 5, 7*/ -#define SIEVE_MASK1 CNST_LIMB(0x12148960) -#define SIEVE_MASK2 CNST_LIMB(0x44a120cc) -#define SIEVE_MASKT CNST_LIMB(0x1a) -#endif - #define SET_OFF1(m1, m2, M1, M2, off, BITS) \ if (off) { \ if (off < GMP_LIMB_BITS) { \ @@ -218,11 +201,10 @@ block_resieve (mp_ptr bit_array, mp_size_t limbs, mp_limb_t offset, mp_limb_t mask, i; ASSERT (limbs > 0); - ASSERT (offset >= GMP_LIMB_BITS); bits = limbs * GMP_LIMB_BITS - 1; - i = fill_bitpattern (bit_array, limbs, offset - GMP_LIMB_BITS); + i = fill_bitpattern (bit_array, limbs, offset); ASSERT (i < GMP_LIMB_BITS); |