1 /*
2 Copyright (C) 2008-2011 William Hart
3
4 This file is part of FLINT.
5
6 FLINT is free software: you can redistribute it and/or modify it under
7 the terms of the GNU Lesser General Public License (LGPL) as published
8 by the Free Software Foundation; either version 2.1 of the License, or
9 (at your option) any later version. See <https://www.gnu.org/licenses/>.
10 */
11
12 #include <stdlib.h>
13 #include <gmp.h>
14 #include "flint.h"
15 #include "fmpz.h"
16 #include "fmpz_vec.h"
17 #include "fmpz_poly.h"
18 #include "fft.h"
19
_fmpz_vec_get_fft(mp_limb_t ** coeffs_f,const fmpz * coeffs_m,slong l,slong length)20 slong _fmpz_vec_get_fft(mp_limb_t ** coeffs_f,
21 const fmpz * coeffs_m, slong l, slong length)
22 {
23 slong size_f = l + 1;
24 mp_limb_t * coeff;
25
26 mp_limb_t mask = WORD(-1);
27 slong bits = 0, limbs = 0, size_j, i, c;
28 int sign = 1, signed_c;
29
30 for (i = 0; i < length; i++, coeffs_m++)
31 {
32 c = *coeffs_m;
33 signed_c = 0;
34
35 if (!COEFF_IS_MPZ(c)) /* coeff is small */
36 {
37 size_j = 1;
38
39 if (c < 0)
40 {
41 signed_c = 1;
42 c = -c;
43 coeff = (mp_limb_t *) &c;
44 } else
45 coeff = (mp_limb_t *) coeffs_m;
46 } else /* coeff is an mpz_t */
47 {
48 __mpz_struct * mpz_ptr = COEFF_TO_PTR(c);
49 size_j = mpz_ptr->_mp_size;
50 if (size_j < 0)
51 {
52 signed_c = 1;
53 size_j = -size_j;
54 }
55 coeff = mpz_ptr->_mp_d;
56 }
57
58 if (signed_c) sign = -1;
59
60 if (size_j > limbs + 1) /* coeff is at least 1 limb bigger */
61 {
62 limbs = size_j - 1;
63 bits = FLINT_BIT_COUNT(coeff[size_j - 1]);
64 if (bits == FLINT_BITS) mask = WORD(0);
65 else mask = WORD(-1) - ((WORD(1)<<bits) - 1);
66 } else if (size_j == limbs + 1) /* coeff is same size as prev biggest */
67 {
68 if (coeff[size_j - 1] & mask) /* see if we have more bits than before */
69 {
70 bits = FLINT_BIT_COUNT(coeff[size_j - 1]);
71 if (bits == FLINT_BITS) mask = WORD(0);
72 else mask = WORD(-1) - ((WORD(1)<<bits) - 1);
73 }
74 }
75
76 if (signed_c) /* write out FFT coefficient, ensuring sign is correct */
77 {
78 mpn_neg_n(coeffs_f[i], coeff, size_j);
79 flint_mpn_store(coeffs_f[i] + size_j, size_f - size_j, WORD(-1));
80 } else
81 {
82 flint_mpn_copyi(coeffs_f[i], coeff, size_j);
83 flint_mpn_zero(coeffs_f[i] + size_j, size_f - size_j);
84 }
85 }
86
87 return sign*(FLINT_BITS*limbs + bits);
88 }
89