1 #ifndef RENUMBER_HPP_ 2 #define RENUMBER_HPP_ 3 4 #include <cstdint> /* AIX wants it first (it's a bug) */ 5 #include <algorithm> 6 #include <cstdio> 7 #include <limits> 8 #include <string> 9 #include <array> 10 #include <vector> 11 #include <stdexcept> 12 #include <iterator> 13 #include <climits> // for UINT_MAX 14 #include <iosfwd> // for istream, ostream, ptrdiff_t 15 #include <utility> // for pair 16 #include "macros.h" // for ASSERT_ALWAYS 17 #include "mpz_poly.h" // for mpz_poly, mpz_poly_s, mpz_poly_srcptr 18 #include "typedefs.h" 19 #include "cado_poly.h" 20 #include "badideals.hpp" 21 // IWYU pragma: no_forward_declare badideal 22 struct cxx_param_list; // IWYU pragma: keep 23 24 /* To build a renumber table in memory in the simplest way, the 25 * process goes as follows 26 27 renumber_t renumber_table(cpoly); 28 renumber_table.set_lpb(lpb); 29 renumber_table.build(); 30 31 (there are various ways to control the build process, including a way to 32 stream the computed table to a file, and compute free relations as well. 33 This is done in freerel.cpp ; but the heavylifting really happens in 34 renumber proper.) 35 36 Note that by default, the renumber tables include the bad ideals 37 information. There is currently no way to turn it off. It should 38 probably be done. 39 40 * To read a renumber table from a file, this goes as: 41 42 renumber_t renumber_table(cpoly); 43 renumber_table.read_from_file(renumberfilename); 44 45 */ 46 47 #define RENUMBER_MAX_LOG_CACHED 20 48 49 struct renumber_t { 50 struct corrupted_table : public std::runtime_error {/*{{{*/ 51 corrupted_table(std::string const &); 52 };/*}}}*/ 53 struct p_r_side {/*{{{*/ 54 p_r_values_t p; 55 p_r_values_t r; 56 int side; operator ==renumber_t::p_r_side57 bool operator==(p_r_side const & x) const { return p == x.p && r == x.r && side == x.side; } same_prenumber_t::p_r_side58 bool same_p(p_r_side const & x) const { return p == x.p && side == x.side; } operator <renumber_t::p_r_side59 bool operator<(p_r_side const & x) const { 60 int s; 61 if ((s = (side > x.side) - (x.side > side)) != 0) return s < 0; 62 if ((s = (p > x.p) - (x.p > p)) != 0) return s < 0; 63 if ((s = (r > x.r) - (x.r > r)) != 0) return s < 0; 64 return false; 65 } 66 };/*}}}*/ 67 68 /* The various known formats are documented in renumber.cpp */ 69 /* It's public because some of the static functions in renumber.cpp 70 * access these. But really, this stuff should be considered 71 * implementation-only. 72 */ 73 static constexpr const int format_traditional = 20130603; 74 static constexpr const int format_variant = 20199999; 75 static constexpr const int format_flat = 20200515; 76 77 private:/*{{{ internal data fields*/ 78 79 int format = format_traditional; 80 81 /* a random state is needed for the traditional format (and _only_ 82 * for the traditional format), since rootfinding is needed at times 83 * for some lookups */ 84 mutable cxx_gmp_randstate rstate; 85 86 /* all the (p,r,side) description of the bad ideals */ 87 std::vector<std::pair<p_r_side, badideal> > bad_ideals; 88 89 p_r_values_t bad_ideals_max_p = 0; 90 91 cxx_cado_poly cpoly; 92 93 /* What actually goes in the data[] table is implementation 94 * dependent. Currently we have several (3) choices. See in 95 * renumber.cpp 96 */ 97 std::vector<p_r_values_t> traditional_data; 98 std::vector<std::array<p_r_values_t, 2>> flat_data; 99 std::vector<unsigned int> lpb; 100 std::vector<index_t> index_from_p_cache; 101 102 /* 103 * [0..above_add): additional columns 104 * [above_add..above_bad): bad ideals 105 * [above_bad..above_cache): ideals in the big data table, p cached 106 * [above_cache..above_all): rest 107 * 108 * These are the outer indices only. The internal table size depends 109 * on the renumber format that is is use (see renumber.cpp). 110 * 111 * traditional: traditional_data.size() == above_all - above_bad 112 * variant: traditional_data.size() == above_all - above_bad + nprimes 113 * flat: flat_data.size() == above_all - above_bad 114 */ 115 index_t above_add = 0; 116 index_t above_bad = 0; 117 index_t above_cache = 0; 118 index_t above_all = 0; 119 /*}}}*/ 120 121 public: 122 /* various accessors {{{*/ get_formatrenumber_t123 inline int get_format() const { return format; } get_lpbrenumber_t124 inline unsigned int get_lpb(unsigned int i) const { return lpb[i]; } get_max_lpbrenumber_t125 inline unsigned int get_max_lpb() const { return *std::max_element(lpb.begin(), lpb.end()); } get_min_lpbrenumber_t126 inline unsigned int get_min_lpb() const { return *std::min_element(lpb.begin(), lpb.end()); } get_sizerenumber_t127 inline uint64_t get_size() const { return above_all; } get_nb_polysrenumber_t128 inline unsigned int get_nb_polys() const { return cpoly->nb_polys; } get_polyrenumber_t129 inline mpz_poly_srcptr get_poly(int side) const { return cpoly->pols[side]; } get_poly_degrenumber_t130 inline int get_poly_deg(int side) const { return get_poly(side)->deg; } get_rational_siderenumber_t131 inline int get_rational_side() const { 132 for(unsigned int side = 0 ; side < get_nb_polys() ; side++) { 133 if (get_poly_deg(side) == 1) return side; 134 } 135 return -1; 136 } get_max_indexrenumber_t137 inline index_t get_max_index() const { return above_all; } get_max_cached_indexrenumber_t138 inline index_t get_max_cached_index() const { return above_cache; } number_of_additional_columnsrenumber_t139 inline index_t number_of_additional_columns() const { return above_add; } 140 std::vector<int> get_sides_of_additional_columns() const; number_of_bad_idealsrenumber_t141 inline index_t number_of_bad_ideals() const { return above_bad - above_add; } get_memory_sizerenumber_t142 inline size_t get_memory_size() const { 143 return traditional_data.size() * sizeof(decltype(traditional_data)::value_type) 144 + flat_data.size() * sizeof(decltype(flat_data)::value_type); 145 } 146 /*}}}*/ 147 148 /*{{{ default ctors */ 149 renumber_t() = default; 150 // ~renumber_t() = default; 151 renumber_t(renumber_t const &) = delete; 152 renumber_t& operator=(renumber_t const &) = delete; 153 renumber_t(renumber_t &&) = default; 154 renumber_t& operator=(renumber_t &&) = default; 155 /*}}}*/ 156 renumber_trenumber_t157 renumber_t(cxx_cado_poly const & cpoly) : cpoly(cpoly), lpb(cpoly->nb_polys, 0) {} 158 159 /*{{{ configuration when creating the table */ set_lpbrenumber_t160 void set_lpb(std::vector<unsigned int> const & x) { 161 ASSERT_ALWAYS(x.size() == lpb.size()); 162 lpb = x; 163 } 164 /*}}}*/ 165 166 /*{{{ reading the table */ 167 void read_from_file(const char * filename); 168 /*}}}*/ 169 170 /*{{{ most important outer-visible routines: lookups */ 171 172 /* special lookups: 173 * a lookup of an additional column on side s returns {0, 0, s} 174 * a lookup of a bad ideal (given by (p,r)) returns the index of the 175 * _first_ ideal above this (p,r) 176 * except for the non-injectivity of the mapping index->(p,r) for bad 177 * ideals, the map is "almost" a bijection. 178 */ 179 180 /* return the number of bad ideals above x (and therefore zero if 181 * x is not bad) ; likewise for index h. 182 * If the ideal is bad, put in the reference [first] the 183 * first index that corresponds to the bad ideals. 184 */ 185 int is_bad(p_r_side) const; 186 int is_bad(index_t &, p_r_side) const; 187 int is_bad(index_t & first_index, index_t h) const; 188 189 /* two convenience shortcuts, to avoid curlies */ is_badrenumber_t190 inline int is_bad(p_r_values_t p, p_r_values_t r, int side) const { 191 return is_bad({p, r, side}); 192 } is_badrenumber_t193 inline int is_bad(index_t & index, p_r_values_t p, p_r_values_t r, int side) const { 194 return is_bad(index, {p, r, side}); 195 } 196 is_badrenumber_t197 bool is_bad (index_t h) const { 198 return h >= above_add && h < above_bad; 199 } is_additional_columnrenumber_t200 bool is_additional_column (index_t h) const { 201 return h < above_add; 202 } 203 204 index_t index_from_p_r (p_r_side) const; index_from_p_rrenumber_t205 inline index_t index_from_p_r (p_r_values_t p, p_r_values_t r, int side) const { 206 return index_from_p_r({p, r, side}); 207 } 208 p_r_side p_r_from_index (index_t) const; 209 210 class const_iterator; 211 212 index_t index_from_p(p_r_values_t p0) const; 213 const_iterator iterator_from_p(p_r_values_t p0) const; 214 index_t index_from_p(p_r_values_t p0, int side) const; 215 const_iterator iterator_from_p(p_r_values_t p0, int side) const; 216 217 /* This second interface works for bad ideals as well. */ 218 std::pair<index_t, std::vector<int>> indices_from_p_a_b(p_r_side x, int e, int64_t a, uint64_t b) const; 219 /*}}}*/ 220 221 /* {{{ build() functionality */ 222 /* To build a renumber table in memory in the simplest way, the 223 * process goes as follows 224 renumber_t renumber_table(cpoly); 225 renumber_table.set_lpb(lpb); 226 renumber_table.build(); 227 */ 228 229 struct cooked { 230 std::vector<unsigned int> nroots; 231 std::vector<p_r_values_t> traditional; 232 std::vector<std::array<p_r_values_t, 2>> flat; 233 std::string text; emptyrenumber_t::cooked234 bool empty() const { return traditional.empty() && flat.empty(); } 235 }; 236 237 struct hook { 238 virtual void operator()(renumber_t & R, p_r_values_t p, index_t idx, renumber_t::cooked const & C) = 0; 239 virtual ~hook() = default; 240 }; 241 242 static void builder_configure_switches(cxx_param_list &); 243 static void builder_declare_usage(cxx_param_list &); 244 static void builder_lookup_parameters(cxx_param_list &); 245 index_t build(cxx_param_list &, hook * = nullptr); 246 index_t build(hook * = nullptr); 247 /* }}} */ 248 249 /*{{{ debugging aids*/ 250 std::string debug_data(index_t i) const; 251 void info(std::ostream & os) const; 252 void more_info(std::ostream & os) const; 253 /*}}}*/ 254 255 private:/*{{{ more implementation-level stuff. */ 256 void read_header(std::istream& os); 257 void read_bad_ideals(std::istream& is); 258 /* there's no write_table, because writing the table is done by 259 * the build() function (called from freerel) */ 260 void read_table(std::istream& is); 261 void compute_bad_ideals(); 262 void compute_bad_ideals_from_dot_badideals_hint(std::istream&, unsigned int = UINT_MAX); 263 void write_header(std::ostream& os) const; 264 void write_bad_ideals(std::ostream& os) const; 265 /* these two could be made public, I believe. The public way to do 266 * the same is to use the param_list argument to build() 267 */ 268 void use_additional_columns_for_dl(); 269 void set_format(int); 270 271 unsigned int needed_bits() const; 272 /* this returns an index i such that data[i - above_bad] points to 273 * the beginning of data for p. Note that in the 274 * renumber_format_variant case, this does not mean that i is the 275 * index of the first prime above p ! 276 */ 277 index_t get_first_index_from_p(p_r_values_t p) const; 278 279 p_r_values_t compute_vr_from_p_r_side (p_r_side x) const; 280 p_r_side compute_p_r_side_from_p_vr (p_r_values_t p, p_r_values_t vr) const; 281 p_r_values_t compute_vp_from_p (p_r_values_t p) const; 282 p_r_values_t compute_p_from_vp (p_r_values_t vp) const; 283 284 bool traditional_get_largest_nonbad_root_mod_p (p_r_side & x) const; 285 index_t traditional_backtrack_until_vp(index_t i, index_t min = 0, index_t max = std::numeric_limits<index_t>::max()) const; 286 bool traditional_is_vp_marker(index_t i) const; 287 void variant_translate_index(index_t & i0, index_t & ii, index_t i) const; 288 289 290 /* The "cook" function can be used asynchronously to prepare the 291 * fragments of the renumber table in parallel. use_cooked must use 292 * the same data, but synchronously -- and stores it to the table, of 293 * course. use_cooked_nostore does the same, except that it is made 294 * for the situation where we have no interest in keeping track of 295 * the renumber table itself. The only thing that matters is keeping 296 * track of the above_all index, which is done by the input and 297 * output index_t values. 298 * 299 * In the "variant" format, the cooked data is position-dependent, as 300 * it encodes the logical position, which is known only in 301 * synchronous context. This is the reason why C is passed as a 302 * non-const reference. (and we do play dirty tricks with it...) 303 */ 304 cooked cook(unsigned long p, std::vector<std::vector<unsigned long>> &) const; 305 void use_cooked(p_r_values_t p, cooked & C); 306 index_t use_cooked_nostore(index_t n0, p_r_values_t p, cooked & C); 307 308 struct builder; // IWYU pragma: keep 309 friend struct builder; 310 /*}}}*/ 311 312 public: 313 314 friend class const_iterator; 315 316 class const_iterator 317 { 318 friend struct renumber_t; 319 private: 320 renumber_t const & table; 321 /* these are outer indices when below above_bad, and then we have 322 * above_bad + the inner index. Subtract table.above_bad to get 323 * inner table indices. 324 */ 325 index_t i0; 326 index_t i; 327 // void reseat(index_t i0, index_t i); 328 void reseat(index_t i); 329 public: 330 typedef p_r_side value_type; 331 typedef std::ptrdiff_t difference_type; 332 typedef p_r_side const * const_pointer; 333 typedef p_r_side const & const_reference; 334 typedef std::input_iterator_tag iterator_category; 335 336 explicit const_iterator(renumber_t const & table, index_t i); 337 338 p_r_side operator*() const; operator ==(const const_iterator & other) const339 bool operator==(const const_iterator& other) const { return i == other.i; } operator !=(const const_iterator & other) const340 bool operator!=(const const_iterator& other) const { return !(*this == other); } 341 const_iterator operator++(int); 342 const_iterator& operator++(); 343 }; 344 345 const_iterator begin() const; 346 const_iterator end() const; 347 }; 348 #endif /* RENUMBER_HPP_ */ 349 350