1use crate::deps::*;
4use crate::flint::*;
5
6
7extern "C" {
8 pub fn flint_mpn_sumdiff_n(
9 s: mp_ptr,
10 d: mp_ptr,
11 x: mp_srcptr,
12 y: mp_srcptr,
13 n: mp_size_t,
14 ) -> mp_limb_t;
15 #[link_name = "mpn_addmod_2expp1_1__extern"]
16 pub fn mpn_addmod_2expp1_1(r: *mut mp_limb_t, limbs: mp_size_t, c: mp_limb_signed_t);
17 pub fn fft_combine_limbs(
18 res: *mut mp_limb_t,
19 poly: *mut *mut mp_limb_t,
20 length: slong,
21 coeff_limbs: mp_size_t,
22 output_limbs: mp_size_t,
23 total_limbs: mp_size_t,
24 );
25 pub fn fft_combine_bits(
26 res: *mut mp_limb_t,
27 poly: *mut *mut mp_limb_t,
28 length: slong,
29 bits: flint_bitcnt_t,
30 output_limbs: mp_size_t,
31 total_limbs: mp_size_t,
32 );
33 pub fn fft_split_limbs(
34 poly: *mut *mut mp_limb_t,
35 limbs: mp_srcptr,
36 total_limbs: mp_size_t,
37 coeff_limbs: mp_size_t,
38 output_limbs: mp_size_t,
39 ) -> mp_size_t;
40 pub fn fft_split_bits(
41 poly: *mut *mut mp_limb_t,
42 limbs: mp_srcptr,
43 total_limbs: mp_size_t,
44 bits: flint_bitcnt_t,
45 output_limbs: mp_size_t,
46 ) -> mp_size_t;
47 pub fn fermat_to_mpz(m: *mut __mpz_struct, i: *mut mp_limb_t, limbs: mp_size_t);
48 pub fn mpn_normmod_2expp1(t: *mut mp_limb_t, limbs: mp_size_t);
49 pub fn butterfly_lshB(
50 t: *mut mp_limb_t,
51 u: *mut mp_limb_t,
52 i1: *mut mp_limb_t,
53 i2: *mut mp_limb_t,
54 limbs: mp_size_t,
55 x: mp_size_t,
56 y: mp_size_t,
57 );
58 pub fn butterfly_rshB(
59 t: *mut mp_limb_t,
60 u: *mut mp_limb_t,
61 i1: *mut mp_limb_t,
62 i2: *mut mp_limb_t,
63 limbs: mp_size_t,
64 x: mp_size_t,
65 y: mp_size_t,
66 );
67 pub fn mpn_negmod_2expp1(z: *mut mp_limb_t, a: *const mp_limb_t, limbs: mp_size_t);
68 pub fn mpn_mul_2expmod_2expp1(
69 t: *mut mp_limb_t,
70 i1: *mut mp_limb_t,
71 limbs: mp_size_t,
72 d: flint_bitcnt_t,
73 );
74 pub fn mpn_div_2expmod_2expp1(
75 t: *mut mp_limb_t,
76 i1: *mut mp_limb_t,
77 limbs: mp_size_t,
78 d: flint_bitcnt_t,
79 );
80 pub fn fft_adjust(
81 r: *mut mp_limb_t,
82 i1: *mut mp_limb_t,
83 i: mp_size_t,
84 limbs: mp_size_t,
85 w: flint_bitcnt_t,
86 );
87 pub fn fft_butterfly(
88 s: *mut mp_limb_t,
89 t: *mut mp_limb_t,
90 i1: *mut mp_limb_t,
91 i2: *mut mp_limb_t,
92 i: mp_size_t,
93 limbs: mp_size_t,
94 w: flint_bitcnt_t,
95 );
96 pub fn ifft_butterfly(
97 s: *mut mp_limb_t,
98 t: *mut mp_limb_t,
99 i1: *mut mp_limb_t,
100 i2: *mut mp_limb_t,
101 i: mp_size_t,
102 limbs: mp_size_t,
103 w: flint_bitcnt_t,
104 );
105 pub fn fft_radix2(
106 ii: *mut *mut mp_limb_t,
107 n: mp_size_t,
108 w: flint_bitcnt_t,
109 t1: *mut *mut mp_limb_t,
110 t2: *mut *mut mp_limb_t,
111 );
112 pub fn fft_truncate1(
113 ii: *mut *mut mp_limb_t,
114 n: mp_size_t,
115 w: flint_bitcnt_t,
116 t1: *mut *mut mp_limb_t,
117 t2: *mut *mut mp_limb_t,
118 trunc: mp_size_t,
119 );
120 pub fn fft_truncate(
121 ii: *mut *mut mp_limb_t,
122 n: mp_size_t,
123 w: flint_bitcnt_t,
124 t1: *mut *mut mp_limb_t,
125 t2: *mut *mut mp_limb_t,
126 trunc: mp_size_t,
127 );
128 pub fn ifft_radix2(
129 ii: *mut *mut mp_limb_t,
130 n: mp_size_t,
131 w: flint_bitcnt_t,
132 t1: *mut *mut mp_limb_t,
133 t2: *mut *mut mp_limb_t,
134 );
135 pub fn ifft_truncate1(
136 ii: *mut *mut mp_limb_t,
137 n: mp_size_t,
138 w: flint_bitcnt_t,
139 t1: *mut *mut mp_limb_t,
140 t2: *mut *mut mp_limb_t,
141 trunc: mp_size_t,
142 );
143 pub fn ifft_truncate(
144 ii: *mut *mut mp_limb_t,
145 n: mp_size_t,
146 w: flint_bitcnt_t,
147 t1: *mut *mut mp_limb_t,
148 t2: *mut *mut mp_limb_t,
149 trunc: mp_size_t,
150 );
151 pub fn fft_butterfly_sqrt2(
152 s: *mut mp_limb_t,
153 t: *mut mp_limb_t,
154 i1: *mut mp_limb_t,
155 i2: *mut mp_limb_t,
156 i: mp_size_t,
157 limbs: mp_size_t,
158 w: flint_bitcnt_t,
159 temp: *mut mp_limb_t,
160 );
161 pub fn ifft_butterfly_sqrt2(
162 s: *mut mp_limb_t,
163 t: *mut mp_limb_t,
164 i1: *mut mp_limb_t,
165 i2: *mut mp_limb_t,
166 i: mp_size_t,
167 limbs: mp_size_t,
168 w: flint_bitcnt_t,
169 temp: *mut mp_limb_t,
170 );
171 pub fn fft_adjust_sqrt2(
172 r: *mut mp_limb_t,
173 i1: *mut mp_limb_t,
174 i: mp_size_t,
175 limbs: mp_size_t,
176 w: flint_bitcnt_t,
177 temp: *mut mp_limb_t,
178 );
179 pub fn fft_truncate_sqrt2(
180 ii: *mut *mut mp_limb_t,
181 n: mp_size_t,
182 w: flint_bitcnt_t,
183 t1: *mut *mut mp_limb_t,
184 t2: *mut *mut mp_limb_t,
185 temp: *mut *mut mp_limb_t,
186 trunc: mp_size_t,
187 );
188 pub fn ifft_truncate_sqrt2(
189 ii: *mut *mut mp_limb_t,
190 n: mp_size_t,
191 w: flint_bitcnt_t,
192 t1: *mut *mut mp_limb_t,
193 t2: *mut *mut mp_limb_t,
194 temp: *mut *mut mp_limb_t,
195 trunc: mp_size_t,
196 );
197 pub fn mul_truncate_sqrt2(
198 r1: mp_ptr,
199 i1: mp_srcptr,
200 n1: mp_size_t,
201 i2: mp_srcptr,
202 n2: mp_size_t,
203 depth: flint_bitcnt_t,
204 w: flint_bitcnt_t,
205 );
206 pub fn fft_butterfly_twiddle(
207 u: *mut mp_limb_t,
208 v: *mut mp_limb_t,
209 s: *mut mp_limb_t,
210 t: *mut mp_limb_t,
211 limbs: mp_size_t,
212 b1: flint_bitcnt_t,
213 b2: flint_bitcnt_t,
214 );
215 pub fn ifft_butterfly_twiddle(
216 u: *mut mp_limb_t,
217 v: *mut mp_limb_t,
218 s: *mut mp_limb_t,
219 t: *mut mp_limb_t,
220 limbs: mp_size_t,
221 b1: flint_bitcnt_t,
222 b2: flint_bitcnt_t,
223 );
224 pub fn fft_radix2_twiddle(
225 ii: *mut *mut mp_limb_t,
226 is: mp_size_t,
227 n: mp_size_t,
228 w: flint_bitcnt_t,
229 t1: *mut *mut mp_limb_t,
230 t2: *mut *mut mp_limb_t,
231 ws: mp_size_t,
232 r: mp_size_t,
233 c: mp_size_t,
234 rs: mp_size_t,
235 );
236 pub fn ifft_radix2_twiddle(
237 ii: *mut *mut mp_limb_t,
238 is: mp_size_t,
239 n: mp_size_t,
240 w: flint_bitcnt_t,
241 t1: *mut *mut mp_limb_t,
242 t2: *mut *mut mp_limb_t,
243 ws: mp_size_t,
244 r: mp_size_t,
245 c: mp_size_t,
246 rs: mp_size_t,
247 );
248 pub fn fft_truncate1_twiddle(
249 ii: *mut *mut mp_limb_t,
250 is: mp_size_t,
251 n: mp_size_t,
252 w: flint_bitcnt_t,
253 t1: *mut *mut mp_limb_t,
254 t2: *mut *mut mp_limb_t,
255 ws: mp_size_t,
256 r: mp_size_t,
257 c: mp_size_t,
258 rs: mp_size_t,
259 trunc: mp_size_t,
260 );
261 pub fn ifft_truncate1_twiddle(
262 ii: *mut *mut mp_limb_t,
263 is: mp_size_t,
264 n: mp_size_t,
265 w: flint_bitcnt_t,
266 t1: *mut *mut mp_limb_t,
267 t2: *mut *mut mp_limb_t,
268 ws: mp_size_t,
269 r: mp_size_t,
270 c: mp_size_t,
271 rs: mp_size_t,
272 trunc: mp_size_t,
273 );
274 pub fn fft_mfa_truncate_sqrt2(
275 ii: *mut *mut mp_limb_t,
276 n: mp_size_t,
277 w: flint_bitcnt_t,
278 t1: *mut *mut mp_limb_t,
279 t2: *mut *mut mp_limb_t,
280 temp: *mut *mut mp_limb_t,
281 n1: mp_size_t,
282 trunc: mp_size_t,
283 );
284 pub fn ifft_mfa_truncate_sqrt2(
285 ii: *mut *mut mp_limb_t,
286 n: mp_size_t,
287 w: flint_bitcnt_t,
288 t1: *mut *mut mp_limb_t,
289 t2: *mut *mut mp_limb_t,
290 temp: *mut *mut mp_limb_t,
291 n1: mp_size_t,
292 trunc: mp_size_t,
293 );
294 pub fn mul_mfa_truncate_sqrt2(
295 r1: mp_ptr,
296 i1: mp_srcptr,
297 n1: mp_size_t,
298 i2: mp_srcptr,
299 n2: mp_size_t,
300 depth: flint_bitcnt_t,
301 w: flint_bitcnt_t,
302 );
303 pub fn fft_mfa_truncate_sqrt2_outer(
304 ii: *mut *mut mp_limb_t,
305 n: mp_size_t,
306 w: flint_bitcnt_t,
307 t1: *mut *mut mp_limb_t,
308 t2: *mut *mut mp_limb_t,
309 temp: *mut *mut mp_limb_t,
310 n1: mp_size_t,
311 trunc: mp_size_t,
312 );
313 pub fn fft_mfa_truncate_sqrt2_inner(
314 ii: *mut *mut mp_limb_t,
315 jj: *mut *mut mp_limb_t,
316 n: mp_size_t,
317 w: flint_bitcnt_t,
318 t1: *mut *mut mp_limb_t,
319 t2: *mut *mut mp_limb_t,
320 UNUSED_temp: *mut *mut mp_limb_t,
321 n1: mp_size_t,
322 trunc: mp_size_t,
323 tt: *mut *mut mp_limb_t,
324 );
325 pub fn ifft_mfa_truncate_sqrt2_outer(
326 ii: *mut *mut mp_limb_t,
327 n: mp_size_t,
328 w: flint_bitcnt_t,
329 t1: *mut *mut mp_limb_t,
330 t2: *mut *mut mp_limb_t,
331 temp: *mut *mut mp_limb_t,
332 n1: mp_size_t,
333 trunc: mp_size_t,
334 );
335 pub fn fft_negacyclic(
336 ii: *mut *mut mp_limb_t,
337 n: mp_size_t,
338 w: flint_bitcnt_t,
339 t1: *mut *mut mp_limb_t,
340 t2: *mut *mut mp_limb_t,
341 temp: *mut *mut mp_limb_t,
342 );
343 pub fn ifft_negacyclic(
344 ii: *mut *mut mp_limb_t,
345 n: mp_size_t,
346 w: flint_bitcnt_t,
347 t1: *mut *mut mp_limb_t,
348 t2: *mut *mut mp_limb_t,
349 temp: *mut *mut mp_limb_t,
350 );
351 pub fn fft_naive_convolution_1(
352 r: *mut mp_limb_t,
353 ii: *mut mp_limb_t,
354 jj: *mut mp_limb_t,
355 m: mp_size_t,
356 );
357 pub fn _fft_mulmod_2expp1(
358 r1: *mut mp_limb_t,
359 i1: *mut mp_limb_t,
360 i2: *mut mp_limb_t,
361 r_limbs: mp_size_t,
362 depth: flint_bitcnt_t,
363 w: flint_bitcnt_t,
364 );
365 pub fn fft_adjust_limbs(limbs: mp_size_t) -> slong;
366 pub fn fft_mulmod_2expp1(
367 r: *mut mp_limb_t,
368 i1: *mut mp_limb_t,
369 i2: *mut mp_limb_t,
370 n: mp_size_t,
371 w: mp_size_t,
372 tt: *mut mp_limb_t,
373 );
374 pub fn flint_mpn_mul_fft_main(
375 r1: mp_ptr,
376 i1: mp_srcptr,
377 n1: mp_size_t,
378 i2: mp_srcptr,
379 n2: mp_size_t,
380 );
381 pub fn fft_convolution_basic(
382 ii: *mut *mut mp_limb_t,
383 jj: *mut *mut mp_limb_t,
384 depth: slong,
385 limbs: slong,
386 trunc: slong,
387 t1: *mut *mut mp_limb_t,
388 t2: *mut *mut mp_limb_t,
389 s1: *mut *mut mp_limb_t,
390 tt: *mut *mut mp_limb_t,
391 );
392 pub fn fft_convolution(
393 ii: *mut *mut mp_limb_t,
394 jj: *mut *mut mp_limb_t,
395 depth: slong,
396 limbs: slong,
397 trunc: slong,
398 t1: *mut *mut mp_limb_t,
399 t2: *mut *mut mp_limb_t,
400 s1: *mut *mut mp_limb_t,
401 tt: *mut *mut mp_limb_t,
402 );
403 #[doc = " FFT Precaching"]
404 pub fn fft_precache(
405 jj: *mut *mut mp_limb_t,
406 depth: slong,
407 limbs: slong,
408 trunc: slong,
409 t1: *mut *mut mp_limb_t,
410 t2: *mut *mut mp_limb_t,
411 s1: *mut *mut mp_limb_t,
412 );
413 pub fn fft_convolution_precache(
414 ii: *mut *mut mp_limb_t,
415 jj: *mut *mut mp_limb_t,
416 depth: slong,
417 limbs: slong,
418 trunc: slong,
419 t1: *mut *mut mp_limb_t,
420 t2: *mut *mut mp_limb_t,
421 s1: *mut *mut mp_limb_t,
422 tt: *mut *mut mp_limb_t,
423 );
424}