1 #ifndef LAS_UNSIEVE_HPP_
2 #define LAS_UNSIEVE_HPP_
3
4 #include "cado_config.h"
5 #include <stdint.h>
6 #include <utility> // pair
7 #include <vector>
8 #include "ularith.h"
9 #include "fb-types.h" // for sublat_t
10
11 #ifdef HAVE_SSE2
12 #include <emmintrin.h>
13 #include "macros.h"
14 #endif
15
16 struct unsieve_data {
17 struct entry {
18 unsigned int lpf, cof;
entryunsieve_data::entry19 entry(unsigned int lpf = 0, unsigned int cof = 0)
20 : lpf(lpf), cof(cof) {}
21 };
22 #ifdef HAVE_SSE2
23 typedef __m128i pattern_t;
24 // oh my...
25 // http://stackoverflow.com/questions/2804902/whats-the-difference-between-logical-sse-intrinsics
26 #define UNSIEVE_OR(a,b) do{(a) = _mm_or_si128((a),(b));}while(0)
27 #else
28 typedef unsigned long pattern_t;
29 #define UNSIEVE_OR(a,b) do{(a) |= (b);}while(0)
30 #endif
31 /* entry[i].lpf is largest prime factor of i, for i < Jmax,
32 cof is the cofactor i/lpf^k s.t. lfp^k || i,
33 */
34 uint32_t Jmax;
35 entry *entries;
36 pattern_t pattern3[3];
37 pattern_t pattern5[5];
38 pattern_t pattern7[7];
39 unsieve_data();
40 unsieve_data(int logI, int logA);
unsieve_dataunsieve_data41 unsieve_data(std::pair<int, int> IA) : unsieve_data(IA.first, IA.second) {};
42 unsieve_data(unsieve_data const &);
43 unsieve_data& operator=(unsieve_data const &);
44 ~unsieve_data();
45 };
46
47 /* {{{ j_divisibility_helper
48 * A structure for factoring the line-coordinate j into distinct odd primes
49 * and performing fast divisibility tests of i by those primes.
50 */
51 struct j_divisibility_helper {
52 struct entry {
53 unsigned int p, /* The odd prime that divides this entry */
54 cof, /* The cofactor after dividing out p as often as possible */
55 inv, /* p^(-1) (mod 2^32) */
56 bound; /* (2^32-1) / p */
57 };
58 std::vector<entry> entries;
operator []j_divisibility_helper59 entry& operator[](int i) { return entries[i]; }
operator []j_divisibility_helper60 entry const & operator[](int i) const { return entries[i]; }
61 j_divisibility_helper(uint32_t J);
62 };
63
64
65 /* Helper function shared by las-unsieve.cpp and las-unsieve-sse2.cpp.
66 Polluting global namespace is a little unfortunate here - #ifdef? */
67 static inline unsigned int
extract_j_div(unsigned int (* div)[2],const unsigned int j,j_divisibility_helper const & j_div,const unsigned int pmin,const unsigned int pmax)68 extract_j_div(unsigned int (*div)[2], const unsigned int j, j_divisibility_helper const & j_div,
69 const unsigned int pmin, const unsigned int pmax)
70 {
71 unsigned int c, nr_div = 0;
72 ASSERT(j < j_div.entries.size());
73 /* For each distict odd prime factor p of j, if pmin <= p <= pmax,
74 store the inverse and bound in array */
75 c = j;
76 c >>= ularith_ctz(c);
77 while (c > 1) {
78 unsigned int p = j_div[c].p;
79 if (p < pmin)
80 break;
81 if (p <= pmax) {
82 div[nr_div][0] = j_div[c].inv;
83 div[nr_div++][1] = j_div[c].bound;
84 }
85 c = j_div[c].cof;
86 }
87 return nr_div;
88 }
89 /* }}} */
90
91 j_divisibility_helper * init_j_div(uint32_t);
92 void clear_j_div(j_divisibility_helper *);
93 void search_survivors_in_line(unsigned char * const SS[2],
94 const unsigned char bound[2],
95 unsigned int j, int i0, int i1,
96 int N, j_divisibility_helper const & j_div,
97 unsigned int td_max, unsieve_data const & us,
98 std::vector<uint32_t> &survivors, sublat_t);
99 #ifdef HAVE_SSE2
100 void search_survivors_in_line_sse2(unsigned char * const SS[2],
101 const unsigned char bound[2],
102 unsigned int j, int i0, int i1,
103 int N, j_divisibility_helper const & j_div,
104 unsigned int td_max,
105 std::vector<uint32_t> &survivors);
106 void search_survivors_in_line_sse2_oneside(unsigned char * const SS,
107 const unsigned char bound,
108 unsigned int j, int i0, int i1,
109 int N, j_divisibility_helper const & j_div,
110 unsigned int td_max,
111 std::vector<uint32_t> &survivors);
112 #endif
113
114 #endif /* LAS_UNSIEVE_HPP_ */
115