flint_sys/
qsieve.rs

1#![allow(non_snake_case)]
2#![allow(non_camel_case_types)]
3
4//! *See the [FLINT documentation](http://flintlib.org/doc/qsieve.html).
5
6use crate::deps::*;
7use crate::flint::*;
8use crate::fmpz::{fmpz, fmpz_t};
9use crate::fmpz_factor::fmpz_factor_struct;
10use libc::{c_char, c_int, c_uchar, c_void, pthread_mutex_t, FILE};
11
12#[repr(C)]
13#[derive(Debug, Copy, Clone)]
14pub struct prime_t {
15    pub pinv: mp_limb_t,
16    pub p: c_int,
17    pub size: c_char,
18}
19
20#[repr(C)]
21#[derive(Debug, Copy, Clone)]
22pub struct fac_t {
23    pub ind: mp_limb_signed_t,
24    pub exp: mp_limb_signed_t,
25}
26
27#[repr(C)]
28#[derive(Debug, Copy, Clone)]
29pub struct la_col_t {
30    pub data: *mut mp_limb_signed_t,
31    pub weight: mp_limb_signed_t,
32    pub orig: mp_limb_signed_t,
33}
34
35#[repr(C)]
36#[derive(Debug, Copy, Clone)]
37pub struct hash_t {
38    pub prime: mp_limb_t,
39    pub next: mp_limb_t,
40    pub count: mp_limb_t,
41}
42
43#[repr(C)]
44#[derive(Debug, Copy, Clone)]
45pub struct relation_t {
46    pub lp: mp_limb_t,
47    pub num_factors: mp_limb_signed_t,
48    pub small_primes: mp_limb_signed_t,
49    pub small: *mut mp_limb_signed_t,
50    pub factor: *mut fac_t,
51    pub Y: fmpz_t,
52}
53
54#[repr(C)]
55#[derive(Debug, Copy, Clone)]
56pub struct qs_poly_s {
57    pub B: fmpz_t,
58    pub soln1: *mut c_int,
59    pub soln2: *mut c_int,
60    pub posn1: *mut c_int,
61    pub posn2: *mut c_int,
62    pub small: *mut mp_limb_signed_t,
63    pub factor: *mut fac_t,
64    pub num_factors: mp_limb_signed_t,
65}
66
67pub type qs_poly_t = [qs_poly_s; 1usize];
68
69#[repr(C)]
70#[derive(Copy, Clone)]
71pub struct qs_s {
72    pub index_j: mp_limb_signed_t,
73    pub mutex: pthread_mutex_t,
74    pub handles: *mut thread_pool_handle,
75    pub num_handles: mp_limb_signed_t,
76    pub n: fmpz_t,
77    pub bits: mp_limb_t,
78    pub ks_primes: mp_limb_t,
79    pub k: mp_limb_t,
80    pub kn: fmpz_t,
81    pub num_primes: mp_limb_signed_t,
82    pub factor_base: *mut prime_t,
83    pub sqrts: *mut c_int,
84    pub small_primes: mp_limb_signed_t,
85    pub second_prime: mp_limb_signed_t,
86    pub sieve_size: mp_limb_signed_t,
87    pub sieve_bits: c_uchar,
88    pub sieve_fill: c_uchar,
89    pub A: fmpz_t,
90    pub B: fmpz_t,
91    pub A_ind: *mut mp_limb_t,
92    pub A_divp: *mut fmpz_t,
93    pub B0_terms: *mut mp_limb_t,
94    pub B_terms: *mut fmpz_t,
95    pub A_inv: *mut mp_limb_t,
96    pub A_inv2B: *mut *mut mp_limb_t,
97    pub soln1: *mut c_int,
98    pub soln2: *mut c_int,
99    pub target_A: fmpz_t,
100    pub upp_bound: fmpz_t,
101    pub low_bound: fmpz_t,
102    pub s: mp_limb_signed_t,
103    pub low: mp_limb_signed_t,
104    pub high: mp_limb_signed_t,
105    pub span: mp_limb_signed_t,
106    pub h: mp_limb_signed_t,
107    pub m: mp_limb_signed_t,
108    pub A_ind_diff: mp_limb_signed_t,
109    pub curr_subset: *mut mp_limb_t,
110    pub first_subset: *mut mp_limb_t,
111    pub j: mp_limb_t,
112    pub poly: *mut qs_poly_s,
113    pub siqs: *mut FILE,
114    pub fname: *mut c_char,
115    pub full_relation: mp_limb_signed_t,
116    pub num_cycles: mp_limb_signed_t,
117    pub vertices: mp_limb_signed_t,
118    pub components: mp_limb_signed_t,
119    pub edges: mp_limb_signed_t,
120    pub table_size: mp_limb_signed_t,
121    pub table: *mut hash_t,
122    pub hash_table: *mut mp_limb_t,
123    pub extra_rels: mp_limb_signed_t,
124    pub max_factors: mp_limb_signed_t,
125    pub Y_arr: *mut fmpz,
126    pub curr_rel: *mut mp_limb_signed_t,
127    pub relation: *mut mp_limb_signed_t,
128    pub buffer_size: mp_limb_signed_t,
129    pub num_relations: mp_limb_signed_t,
130    pub small_factor: mp_limb_t,
131    pub matrix: *mut la_col_t,
132    pub qsort_arr: *mut *mut la_col_t,
133    pub columns: mp_limb_signed_t,
134    pub prime_count: *mut mp_limb_signed_t,
135}
136
137pub type qs_t = [qs_s; 1usize];
138
139extern "C" {
140    pub static mut qsieve_tune: [[mp_limb_t; 6usize]; 30usize];
141    pub fn qsieve_init(qs_inf: *mut qs_s, n: *mut fmpz);
142    pub fn qsieve_knuth_schroeppel(qs_inf: *mut qs_s) -> mp_limb_t;
143    pub fn qsieve_clear(qs_inf: *mut qs_s);
144    pub fn qsieve_factor(factors: *mut fmpz_factor_struct, n: *mut fmpz);
145    pub fn compute_factor_base(
146        small_factor: *mut mp_limb_t,
147        qs_inf: *mut qs_s,
148        num_primes: mp_limb_signed_t,
149    ) -> *mut prime_t;
150    pub fn qsieve_primes_init(qs_inf: *mut qs_s) -> mp_limb_t;
151    pub fn qsieve_primes_increment(qs_inf: *mut qs_s, delta: mp_limb_t) -> mp_limb_t;
152    pub fn qsieve_poly_init(qs_inf: *mut qs_s) -> mp_limb_t;
153    pub fn qsieve_init_A(qs_inf: *mut qs_s) -> c_int;
154    pub fn qsieve_reinit_A(qs_inf: *mut qs_s);
155    pub fn qsieve_next_A(qs_inf: *mut qs_s) -> c_int;
156    pub fn qsieve_init_poly_first(qs_inf: *mut qs_s);
157    pub fn qsieve_init_poly_next(qs_inf: *mut qs_s, i: mp_limb_signed_t);
158    pub fn qsieve_compute_C(C: *mut fmpz, qs_inf: *mut qs_s, poly: *mut qs_poly_s);
159    pub fn qsieve_poly_copy(poly: *mut qs_poly_s, qs_inf: *mut qs_s);
160    pub fn qsieve_poly_clear(qs_inf: *mut qs_s);
161    pub fn qsieve_do_sieving(qs_inf: *mut qs_s, sieve: *mut c_uchar, poly: *mut qs_poly_s);
162    pub fn qsieve_do_sieving2(qs_inf: *mut qs_s, sieve: *mut c_uchar, poly: *mut qs_poly_s);
163    pub fn qsieve_evaluate_candidate(
164        qs_inf: *mut qs_s,
165        i: mp_limb_t,
166        sieve: *mut c_uchar,
167        poly: *mut qs_poly_s,
168    ) -> mp_limb_signed_t;
169    pub fn qsieve_evaluate_sieve(
170        qs_inf: *mut qs_s,
171        sieve: *mut c_uchar,
172        poly: *mut qs_poly_s,
173    ) -> mp_limb_signed_t;
174    pub fn qsieve_collect_relations(qs_inf: *mut qs_s, sieve: *mut c_uchar) -> mp_limb_signed_t;
175    pub fn qsieve_linalg_init(qs_inf: *mut qs_s);
176    pub fn qsieve_linalg_realloc(qs_inf: *mut qs_s);
177    pub fn qsieve_linalg_clear(qs_inf: *mut qs_s);
178    pub fn qsieve_relations_cmp(a: *const c_void, b: *const c_void) -> c_int;
179    pub fn qsieve_merge_relations(qs_inf: *mut qs_s) -> mp_limb_signed_t;
180    pub fn qsieve_write_to_file(
181        qs_inf: *mut qs_s,
182        prime: mp_limb_t,
183        Y: *mut fmpz,
184        poly: *mut qs_poly_s,
185    );
186    pub fn qsieve_get_table_entry(qs_inf: *mut qs_s, prime: mp_limb_t) -> *mut hash_t;
187    pub fn qsieve_add_to_hashtable(qs_inf: *mut qs_s, prime: mp_limb_t);
188    pub fn qsieve_parse_relation(qs_inf: *mut qs_s, str_: *mut c_char) -> relation_t;
189    pub fn qsieve_merge_relation(qs_inf: *mut qs_s, a: relation_t, b: relation_t) -> relation_t;
190    pub fn qsieve_compare_relation(a: *const c_void, b: *const c_void) -> c_int;
191    pub fn qsieve_remove_duplicates(
192        rel_list: *mut relation_t,
193        num_relations: mp_limb_signed_t,
194    ) -> c_int;
195    pub fn qsieve_insert_relation(
196        qs_inf: *mut qs_s,
197        rel_list: *mut relation_t,
198        num_relations: mp_limb_signed_t,
199    );
200    pub fn qsieve_process_relation(qs_inf: *mut qs_s) -> c_int;
201    pub fn get_null_entry(nullrows: *mut u64, i: mp_limb_signed_t, l: mp_limb_signed_t) -> u64;
202    pub fn reduce_matrix(
203        qs_inf: *mut qs_s,
204        nrows: *mut mp_limb_signed_t,
205        ncols: *mut mp_limb_signed_t,
206        cols: *mut la_col_t,
207    );
208    pub fn block_lanczos(
209        state: *mut flint_rand_s,
210        nrows: mp_limb_signed_t,
211        dense_rows: mp_limb_signed_t,
212        ncols: mp_limb_signed_t,
213        B: *mut la_col_t,
214    ) -> *mut u64;
215    pub fn qsieve_square_root(
216        X: *mut fmpz,
217        Y: *mut fmpz,
218        qs_inf: *mut qs_s,
219        nullrows: *mut u64,
220        ncols: mp_limb_signed_t,
221        l: mp_limb_signed_t,
222        N: *mut fmpz,
223    );
224}
flint_sys/qsieve.rs

flint_sys/
qsieve.rs
