1use libc::*;
4use crate::deps::*;
5use crate::flint::*;
6use crate::fmpz_types::*;
7
8
9pub const QS_DEBUG: u32 = 0;
10pub const BITS_ADJUST: u32 = 25;
11pub const BLOCK_SIZE: u32 = 262144;
12#[repr(C)]
13pub struct prime_t {
14 pub pinv: ulong,
15 pub pinv2: ulong,
16 pub p: libc::c_int,
17 pub size: libc::c_char,
18}
19#[allow(clippy::unnecessary_operation, clippy::identity_op)]
20const _: () = {
21 ["Size of prime_t"][::std::mem::size_of::<prime_t>() - 24usize];
22 ["Alignment of prime_t"][::std::mem::align_of::<prime_t>() - 8usize];
23 ["Offset of field: prime_t::pinv"][::std::mem::offset_of!(prime_t, pinv) - 0usize];
24 ["Offset of field: prime_t::pinv2"][::std::mem::offset_of!(prime_t, pinv2) - 8usize];
25 ["Offset of field: prime_t::p"][::std::mem::offset_of!(prime_t, p) - 16usize];
26 ["Offset of field: prime_t::size"][::std::mem::offset_of!(prime_t, size) - 20usize];
27};
28impl Default for prime_t {
29 fn default() -> Self {
30 let mut s = ::std::mem::MaybeUninit::<Self>::uninit();
31 unsafe {
32 ::std::ptr::write_bytes(s.as_mut_ptr(), 0, 1);
33 s.assume_init()
34 }
35 }
36}
37#[repr(C)]
38pub struct fac_t {
39 pub ind: slong,
40 pub exp: slong,
41}
42#[allow(clippy::unnecessary_operation, clippy::identity_op)]
43const _: () = {
44 ["Size of fac_t"][::std::mem::size_of::<fac_t>() - 16usize];
45 ["Alignment of fac_t"][::std::mem::align_of::<fac_t>() - 8usize];
46 ["Offset of field: fac_t::ind"][::std::mem::offset_of!(fac_t, ind) - 0usize];
47 ["Offset of field: fac_t::exp"][::std::mem::offset_of!(fac_t, exp) - 8usize];
48};
49impl Default for fac_t {
50 fn default() -> Self {
51 let mut s = ::std::mem::MaybeUninit::<Self>::uninit();
52 unsafe {
53 ::std::ptr::write_bytes(s.as_mut_ptr(), 0, 1);
54 s.assume_init()
55 }
56 }
57}
58#[repr(C)]
59pub struct la_col_t {
60 pub data: *mut slong,
61 pub weight: slong,
62 pub orig: slong,
63}
64#[allow(clippy::unnecessary_operation, clippy::identity_op)]
65const _: () = {
66 ["Size of la_col_t"][::std::mem::size_of::<la_col_t>() - 24usize];
67 ["Alignment of la_col_t"][::std::mem::align_of::<la_col_t>() - 8usize];
68 ["Offset of field: la_col_t::data"][::std::mem::offset_of!(la_col_t, data) - 0usize];
69 ["Offset of field: la_col_t::weight"][::std::mem::offset_of!(la_col_t, weight) - 8usize];
70 ["Offset of field: la_col_t::orig"][::std::mem::offset_of!(la_col_t, orig) - 16usize];
71};
72impl Default for la_col_t {
73 fn default() -> Self {
74 let mut s = ::std::mem::MaybeUninit::<Self>::uninit();
75 unsafe {
76 ::std::ptr::write_bytes(s.as_mut_ptr(), 0, 1);
77 s.assume_init()
78 }
79 }
80}
81#[repr(C)]
82pub struct hash_t {
83 pub prime: ulong,
84 pub next: ulong,
85 pub count: ulong,
86}
87#[allow(clippy::unnecessary_operation, clippy::identity_op)]
88const _: () = {
89 ["Size of hash_t"][::std::mem::size_of::<hash_t>() - 24usize];
90 ["Alignment of hash_t"][::std::mem::align_of::<hash_t>() - 8usize];
91 ["Offset of field: hash_t::prime"][::std::mem::offset_of!(hash_t, prime) - 0usize];
92 ["Offset of field: hash_t::next"][::std::mem::offset_of!(hash_t, next) - 8usize];
93 ["Offset of field: hash_t::count"][::std::mem::offset_of!(hash_t, count) - 16usize];
94};
95impl Default for hash_t {
96 fn default() -> Self {
97 let mut s = ::std::mem::MaybeUninit::<Self>::uninit();
98 unsafe {
99 ::std::ptr::write_bytes(s.as_mut_ptr(), 0, 1);
100 s.assume_init()
101 }
102 }
103}
104#[repr(C)]
105pub struct relation_t {
106 pub lp: ulong,
107 pub num_factors: slong,
108 pub small_primes: slong,
109 pub small: *mut slong,
110 pub factor: *mut fac_t,
111 pub Y: fmpz_t,
112}
113#[allow(clippy::unnecessary_operation, clippy::identity_op)]
114const _: () = {
115 ["Size of relation_t"][::std::mem::size_of::<relation_t>() - 48usize];
116 ["Alignment of relation_t"][::std::mem::align_of::<relation_t>() - 8usize];
117 ["Offset of field: relation_t::lp"][::std::mem::offset_of!(relation_t, lp) - 0usize];
118 ["Offset of field: relation_t::num_factors"]
119 [::std::mem::offset_of!(relation_t, num_factors) - 8usize];
120 ["Offset of field: relation_t::small_primes"]
121 [::std::mem::offset_of!(relation_t, small_primes) - 16usize];
122 ["Offset of field: relation_t::small"][::std::mem::offset_of!(relation_t, small) - 24usize];
123 ["Offset of field: relation_t::factor"][::std::mem::offset_of!(relation_t, factor) - 32usize];
124 ["Offset of field: relation_t::Y"][::std::mem::offset_of!(relation_t, Y) - 40usize];
125};
126impl Default for relation_t {
127 fn default() -> Self {
128 let mut s = ::std::mem::MaybeUninit::<Self>::uninit();
129 unsafe {
130 ::std::ptr::write_bytes(s.as_mut_ptr(), 0, 1);
131 s.assume_init()
132 }
133 }
134}
135#[repr(C)]
136pub struct qs_poly_s {
137 pub B: fmpz_t,
138 pub soln1: *mut libc::c_int,
139 pub soln2: *mut libc::c_int,
140 pub posn1: *mut libc::c_int,
141 pub posn2: *mut libc::c_int,
142 pub small: *mut slong,
143 pub factor: *mut fac_t,
144 pub num_factors: slong,
145}
146#[allow(clippy::unnecessary_operation, clippy::identity_op)]
147const _: () = {
148 ["Size of qs_poly_s"][::std::mem::size_of::<qs_poly_s>() - 64usize];
149 ["Alignment of qs_poly_s"][::std::mem::align_of::<qs_poly_s>() - 8usize];
150 ["Offset of field: qs_poly_s::B"][::std::mem::offset_of!(qs_poly_s, B) - 0usize];
151 ["Offset of field: qs_poly_s::soln1"][::std::mem::offset_of!(qs_poly_s, soln1) - 8usize];
152 ["Offset of field: qs_poly_s::soln2"][::std::mem::offset_of!(qs_poly_s, soln2) - 16usize];
153 ["Offset of field: qs_poly_s::posn1"][::std::mem::offset_of!(qs_poly_s, posn1) - 24usize];
154 ["Offset of field: qs_poly_s::posn2"][::std::mem::offset_of!(qs_poly_s, posn2) - 32usize];
155 ["Offset of field: qs_poly_s::small"][::std::mem::offset_of!(qs_poly_s, small) - 40usize];
156 ["Offset of field: qs_poly_s::factor"][::std::mem::offset_of!(qs_poly_s, factor) - 48usize];
157 ["Offset of field: qs_poly_s::num_factors"]
158 [::std::mem::offset_of!(qs_poly_s, num_factors) - 56usize];
159};
160impl Default for qs_poly_s {
161 fn default() -> Self {
162 let mut s = ::std::mem::MaybeUninit::<Self>::uninit();
163 unsafe {
164 ::std::ptr::write_bytes(s.as_mut_ptr(), 0, 1);
165 s.assume_init()
166 }
167 }
168}
169pub type qs_poly_t = [qs_poly_s; 1usize];
170#[repr(C)]
171pub struct qs_s {
172 pub index_j: slong,
173 pub mutex: pthread_mutex_t,
174 pub handles: *mut thread_pool_handle,
175 pub num_handles: slong,
176 pub n: fmpz_t,
177 pub bits: flint_bitcnt_t,
178 pub ks_primes: ulong,
179 pub k: ulong,
180 pub kn: fmpz_t,
181 pub num_primes: slong,
182 pub factor_base: *mut prime_t,
183 pub sqrts: *mut libc::c_int,
184 pub small_primes: slong,
185 pub second_prime: slong,
186 pub sieve_size: slong,
187 pub sieve_bits: libc::c_uchar,
188 pub sieve_fill: libc::c_uchar,
189 #[doc = "POLYNOMIAL DATA"]
190 pub A: fmpz_t,
191 pub B: fmpz_t,
192 pub A_ind: *mut ulong,
193 pub A_divp: *mut fmpz_t,
194 pub B0_terms: *mut ulong,
195 pub B_terms: *mut fmpz_t,
196 pub A_inv: *mut ulong,
197 pub A_inv2B: *mut *mut ulong,
198 pub soln1: *mut libc::c_int,
199 pub soln2: *mut libc::c_int,
200 pub target_A: fmpz_t,
201 pub upp_bound: fmpz_t,
202 pub low_bound: fmpz_t,
203 pub s: slong,
204 pub low: slong,
205 pub high: slong,
206 pub span: slong,
207 pub h: slong,
208 pub m: slong,
209 pub A_ind_diff: slong,
210 pub curr_subset: *mut ulong,
211 pub first_subset: *mut ulong,
212 pub j: ulong,
213 pub poly: *mut qs_poly_s,
214 #[doc = "RELATION DATA"]
215 pub siqs: *mut FLINT_FILE,
216 pub fname: *mut libc::c_char,
217 pub full_relation: slong,
218 pub num_cycles: slong,
219 pub vertices: slong,
220 pub components: slong,
221 pub edges: slong,
222 pub table_size: slong,
223 pub table: *mut hash_t,
224 pub hash_table: *mut ulong,
225 pub extra_rels: slong,
226 pub max_factors: slong,
227 pub Y_arr: *mut fmpz,
228 pub curr_rel: *mut slong,
229 pub relation: *mut slong,
230 pub buffer_size: slong,
231 pub num_relations: slong,
232 pub small_factor: ulong,
233 #[doc = "LINEAR ALGEBRA DATA"]
234 pub matrix: *mut la_col_t,
235 pub qsort_arr: *mut *mut la_col_t,
236 pub columns: slong,
237 #[doc = "SQUARE ROOT DATA"]
238 pub prime_count: *mut slong,
239}
240#[allow(clippy::unnecessary_operation, clippy::identity_op)]
241const _: () = {
242 ["Size of qs_s"][::std::mem::size_of::<qs_s>() - 528usize];
243 ["Alignment of qs_s"][::std::mem::align_of::<qs_s>() - 8usize];
244 ["Offset of field: qs_s::index_j"][::std::mem::offset_of!(qs_s, index_j) - 0usize];
245 ["Offset of field: qs_s::mutex"][::std::mem::offset_of!(qs_s, mutex) - 8usize];
246 ["Offset of field: qs_s::handles"][::std::mem::offset_of!(qs_s, handles) - 48usize];
247 ["Offset of field: qs_s::num_handles"][::std::mem::offset_of!(qs_s, num_handles) - 56usize];
248 ["Offset of field: qs_s::n"][::std::mem::offset_of!(qs_s, n) - 64usize];
249 ["Offset of field: qs_s::bits"][::std::mem::offset_of!(qs_s, bits) - 72usize];
250 ["Offset of field: qs_s::ks_primes"][::std::mem::offset_of!(qs_s, ks_primes) - 80usize];
251 ["Offset of field: qs_s::k"][::std::mem::offset_of!(qs_s, k) - 88usize];
252 ["Offset of field: qs_s::kn"][::std::mem::offset_of!(qs_s, kn) - 96usize];
253 ["Offset of field: qs_s::num_primes"][::std::mem::offset_of!(qs_s, num_primes) - 104usize];
254 ["Offset of field: qs_s::factor_base"][::std::mem::offset_of!(qs_s, factor_base) - 112usize];
255 ["Offset of field: qs_s::sqrts"][::std::mem::offset_of!(qs_s, sqrts) - 120usize];
256 ["Offset of field: qs_s::small_primes"][::std::mem::offset_of!(qs_s, small_primes) - 128usize];
257 ["Offset of field: qs_s::second_prime"][::std::mem::offset_of!(qs_s, second_prime) - 136usize];
258 ["Offset of field: qs_s::sieve_size"][::std::mem::offset_of!(qs_s, sieve_size) - 144usize];
259 ["Offset of field: qs_s::sieve_bits"][::std::mem::offset_of!(qs_s, sieve_bits) - 152usize];
260 ["Offset of field: qs_s::sieve_fill"][::std::mem::offset_of!(qs_s, sieve_fill) - 153usize];
261 ["Offset of field: qs_s::A"][::std::mem::offset_of!(qs_s, A) - 160usize];
262 ["Offset of field: qs_s::B"][::std::mem::offset_of!(qs_s, B) - 168usize];
263 ["Offset of field: qs_s::A_ind"][::std::mem::offset_of!(qs_s, A_ind) - 176usize];
264 ["Offset of field: qs_s::A_divp"][::std::mem::offset_of!(qs_s, A_divp) - 184usize];
265 ["Offset of field: qs_s::B0_terms"][::std::mem::offset_of!(qs_s, B0_terms) - 192usize];
266 ["Offset of field: qs_s::B_terms"][::std::mem::offset_of!(qs_s, B_terms) - 200usize];
267 ["Offset of field: qs_s::A_inv"][::std::mem::offset_of!(qs_s, A_inv) - 208usize];
268 ["Offset of field: qs_s::A_inv2B"][::std::mem::offset_of!(qs_s, A_inv2B) - 216usize];
269 ["Offset of field: qs_s::soln1"][::std::mem::offset_of!(qs_s, soln1) - 224usize];
270 ["Offset of field: qs_s::soln2"][::std::mem::offset_of!(qs_s, soln2) - 232usize];
271 ["Offset of field: qs_s::target_A"][::std::mem::offset_of!(qs_s, target_A) - 240usize];
272 ["Offset of field: qs_s::upp_bound"][::std::mem::offset_of!(qs_s, upp_bound) - 248usize];
273 ["Offset of field: qs_s::low_bound"][::std::mem::offset_of!(qs_s, low_bound) - 256usize];
274 ["Offset of field: qs_s::s"][::std::mem::offset_of!(qs_s, s) - 264usize];
275 ["Offset of field: qs_s::low"][::std::mem::offset_of!(qs_s, low) - 272usize];
276 ["Offset of field: qs_s::high"][::std::mem::offset_of!(qs_s, high) - 280usize];
277 ["Offset of field: qs_s::span"][::std::mem::offset_of!(qs_s, span) - 288usize];
278 ["Offset of field: qs_s::h"][::std::mem::offset_of!(qs_s, h) - 296usize];
279 ["Offset of field: qs_s::m"][::std::mem::offset_of!(qs_s, m) - 304usize];
280 ["Offset of field: qs_s::A_ind_diff"][::std::mem::offset_of!(qs_s, A_ind_diff) - 312usize];
281 ["Offset of field: qs_s::curr_subset"][::std::mem::offset_of!(qs_s, curr_subset) - 320usize];
282 ["Offset of field: qs_s::first_subset"][::std::mem::offset_of!(qs_s, first_subset) - 328usize];
283 ["Offset of field: qs_s::j"][::std::mem::offset_of!(qs_s, j) - 336usize];
284 ["Offset of field: qs_s::poly"][::std::mem::offset_of!(qs_s, poly) - 344usize];
285 ["Offset of field: qs_s::siqs"][::std::mem::offset_of!(qs_s, siqs) - 352usize];
286 ["Offset of field: qs_s::fname"][::std::mem::offset_of!(qs_s, fname) - 360usize];
287 ["Offset of field: qs_s::full_relation"]
288 [::std::mem::offset_of!(qs_s, full_relation) - 368usize];
289 ["Offset of field: qs_s::num_cycles"][::std::mem::offset_of!(qs_s, num_cycles) - 376usize];
290 ["Offset of field: qs_s::vertices"][::std::mem::offset_of!(qs_s, vertices) - 384usize];
291 ["Offset of field: qs_s::components"][::std::mem::offset_of!(qs_s, components) - 392usize];
292 ["Offset of field: qs_s::edges"][::std::mem::offset_of!(qs_s, edges) - 400usize];
293 ["Offset of field: qs_s::table_size"][::std::mem::offset_of!(qs_s, table_size) - 408usize];
294 ["Offset of field: qs_s::table"][::std::mem::offset_of!(qs_s, table) - 416usize];
295 ["Offset of field: qs_s::hash_table"][::std::mem::offset_of!(qs_s, hash_table) - 424usize];
296 ["Offset of field: qs_s::extra_rels"][::std::mem::offset_of!(qs_s, extra_rels) - 432usize];
297 ["Offset of field: qs_s::max_factors"][::std::mem::offset_of!(qs_s, max_factors) - 440usize];
298 ["Offset of field: qs_s::Y_arr"][::std::mem::offset_of!(qs_s, Y_arr) - 448usize];
299 ["Offset of field: qs_s::curr_rel"][::std::mem::offset_of!(qs_s, curr_rel) - 456usize];
300 ["Offset of field: qs_s::relation"][::std::mem::offset_of!(qs_s, relation) - 464usize];
301 ["Offset of field: qs_s::buffer_size"][::std::mem::offset_of!(qs_s, buffer_size) - 472usize];
302 ["Offset of field: qs_s::num_relations"]
303 [::std::mem::offset_of!(qs_s, num_relations) - 480usize];
304 ["Offset of field: qs_s::small_factor"][::std::mem::offset_of!(qs_s, small_factor) - 488usize];
305 ["Offset of field: qs_s::matrix"][::std::mem::offset_of!(qs_s, matrix) - 496usize];
306 ["Offset of field: qs_s::qsort_arr"][::std::mem::offset_of!(qs_s, qsort_arr) - 504usize];
307 ["Offset of field: qs_s::columns"][::std::mem::offset_of!(qs_s, columns) - 512usize];
308 ["Offset of field: qs_s::prime_count"][::std::mem::offset_of!(qs_s, prime_count) - 520usize];
309};
310impl Default for qs_s {
311 fn default() -> Self {
312 let mut s = ::std::mem::MaybeUninit::<Self>::uninit();
313 unsafe {
314 ::std::ptr::write_bytes(s.as_mut_ptr(), 0, 1);
315 s.assume_init()
316 }
317 }
318}
319pub type qs_t = [qs_s; 1usize];
320extern "C" {
321 pub static mut qsieve_tune: [[ulong; 6usize]; 30usize];
322 pub fn qsieve_init(qs_inf: *mut qs_s, n: *const fmpz);
323 pub fn qsieve_knuth_schroeppel(qs_inf: *mut qs_s) -> ulong;
324 pub fn qsieve_clear(qs_inf: *mut qs_s);
325 pub fn qsieve_factor(factors: *mut fmpz_factor_struct, n: *const fmpz);
326 pub fn compute_factor_base(
327 small_factor: *mut ulong,
328 qs_inf: *mut qs_s,
329 num_primes: slong,
330 ) -> *mut prime_t;
331 pub fn qsieve_primes_init(qs_inf: *mut qs_s) -> ulong;
332 pub fn qsieve_primes_increment(qs_inf: *mut qs_s, delta: ulong) -> ulong;
333 pub fn qsieve_poly_init(qs_inf: *mut qs_s) -> ulong;
334 pub fn qsieve_init_A(qs_inf: *mut qs_s) -> libc::c_int;
335 pub fn qsieve_reinit_A(qs_inf: *mut qs_s);
336 pub fn qsieve_next_A(qs_inf: *mut qs_s) -> libc::c_int;
337 pub fn qsieve_init_poly_first(qs_inf: *mut qs_s);
338 pub fn qsieve_init_poly_next(qs_inf: *mut qs_s, i: slong);
339 pub fn qsieve_compute_C(C: *mut fmpz, qs_inf: *mut qs_s, poly: *mut qs_poly_s);
340 pub fn qsieve_poly_copy(poly: *mut qs_poly_s, qs_inf: *mut qs_s);
341 pub fn qsieve_poly_clear(qs_inf: *mut qs_s);
342 pub fn qsieve_do_sieving(qs_inf: *mut qs_s, sieve: *mut libc::c_uchar, poly: *mut qs_poly_s);
343 pub fn qsieve_do_sieving2(qs_inf: *mut qs_s, sieve: *mut libc::c_uchar, poly: *mut qs_poly_s);
344 pub fn qsieve_evaluate_candidate(
345 qs_inf: *mut qs_s,
346 i: ulong,
347 sieve: *mut libc::c_uchar,
348 poly: *mut qs_poly_s,
349 ) -> slong;
350 pub fn qsieve_evaluate_sieve(
351 qs_inf: *mut qs_s,
352 sieve: *mut libc::c_uchar,
353 poly: *mut qs_poly_s,
354 ) -> slong;
355 pub fn qsieve_collect_relations(qs_inf: *mut qs_s, sieve: *mut libc::c_uchar) -> slong;
356 pub fn qsieve_linalg_init(qs_inf: *mut qs_s);
357 pub fn qsieve_linalg_realloc(qs_inf: *mut qs_s);
358 pub fn qsieve_linalg_clear(qs_inf: *mut qs_s);
359 pub fn qsieve_relations_cmp(a: *const libc::c_void, b: *const libc::c_void) -> libc::c_int;
360 pub fn qsieve_merge_relations(qs_inf: *mut qs_s) -> slong;
361 pub fn qsieve_write_to_file(
362 qs_inf: *mut qs_s,
363 prime: ulong,
364 Y: *const fmpz,
365 poly: *const qs_poly_s,
366 );
367 pub fn qsieve_get_table_entry(qs_inf: *mut qs_s, prime: ulong) -> *mut hash_t;
368 pub fn qsieve_add_to_hashtable(qs_inf: *mut qs_s, prime: ulong);
369 pub fn qsieve_parse_relation(qs_inf: *mut qs_s) -> relation_t;
370 pub fn qsieve_merge_relation(qs_inf: *mut qs_s, a: relation_t, b: relation_t) -> relation_t;
371 pub fn qsieve_compare_relation(a: *const libc::c_void, b: *const libc::c_void) -> libc::c_int;
372 pub fn qsieve_remove_duplicates(rel_list: *mut relation_t, num_relations: slong)
373 -> libc::c_int;
374 pub fn qsieve_insert_relation(
375 qs_inf: *mut qs_s,
376 rel_list: *mut relation_t,
377 num_relations: slong,
378 );
379 pub fn qsieve_process_relation(qs_inf: *mut qs_s) -> libc::c_int;
380 #[link_name = "insert_col_entry__extern"]
381 pub fn insert_col_entry(col: *mut la_col_t, entry: slong);
382 #[link_name = "swap_cols__extern"]
383 pub fn swap_cols(col2: *mut la_col_t, col1: *mut la_col_t);
384 #[link_name = "clear_col__extern"]
385 pub fn clear_col(col: *mut la_col_t);
386 #[link_name = "free_col__extern"]
387 pub fn free_col(col: *mut la_col_t);
388 pub fn get_null_entry(nullrows: *mut u64, i: slong, l: slong) -> u64;
389 pub fn reduce_matrix(
390 qs_inf: *mut qs_s,
391 nrows: *mut slong,
392 ncols: *mut slong,
393 cols: *mut la_col_t,
394 );
395 pub fn block_lanczos(
396 state: *mut flint_rand_struct,
397 nrows: slong,
398 dense_rows: slong,
399 ncols: slong,
400 B: *mut la_col_t,
401 ) -> *mut u64;
402 pub fn qsieve_square_root(
403 X: *mut fmpz,
404 Y: *mut fmpz,
405 qs_inf: *mut qs_s,
406 nullrows: *mut u64,
407 ncols: slong,
408 l: slong,
409 N: *mut fmpz,
410 );
411}