1 /*
2 Copyright (C) 2016 Jean-Pierre Flori
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 <http://www.gnu.org/licenses/>.
10 */
11
12 #include "fq_nmod_poly.h"
13
14 void
_fq_nmod_poly_mul_univariate_no_pad(fq_nmod_struct * rop,const fq_nmod_struct * op1,slong len1,const fq_nmod_struct * op2,slong len2,const fq_nmod_ctx_t ctx)15 _fq_nmod_poly_mul_univariate_no_pad (fq_nmod_struct * rop,
16 const fq_nmod_struct * op1, slong len1,
17 const fq_nmod_struct * op2, slong len2,
18 const fq_nmod_ctx_t ctx)
19 {
20 const slong fqlen = ctx->modulus->length - 1;
21 const slong pfqlen = 2*fqlen - 1;
22 const nmod_t mod = ctx->mod;
23 const slong rlen = len1 + len2 - 1;
24 const slong llen1 = (op1 + (len1 - 1))->length;
25 const slong llen2 = (op2 + (len2 - 1))->length;
26 const slong clen1 = pfqlen*(len1-1) + llen1;
27 const slong clen2 = pfqlen*(len2-1) + llen2;
28 const slong crlen = clen1 + clen2 - 1;
29 const slong lrlen = llen1 + llen2 - 1;
30 slong i;
31 slong len;
32
33 mp_ptr cop1, cop2, crop;
34
35 cop1 = (mp_limb_t *) flint_malloc(clen1*sizeof(mp_limb_t));
36 for (i = 0; i < len1 - 1; i++)
37 {
38 flint_mpn_copyi(cop1 + pfqlen*i, (op1 + i)->coeffs, (op1 + i)->length);
39 flint_mpn_zero(cop1 + pfqlen*i + (op1 + i)->length, pfqlen - (op1 + i)->length);
40 }
41 {
42 flint_mpn_copyi(cop1 + pfqlen*i, (op1 + i)->coeffs, (op1 + i)->length);
43 }
44
45 if (op2 != op1)
46 {
47 cop2 = (mp_limb_t *) flint_malloc(clen2*sizeof(mp_limb_t));
48 for (i = 0; i < len2 - 1; i++)
49 {
50 flint_mpn_copyi(cop2 + pfqlen*i, (op2 + i)->coeffs,(op2 + i)->length);
51 flint_mpn_zero(cop2 + pfqlen*i + (op2 + i)->length, pfqlen - (op2 + i)->length);
52 }
53 {
54 flint_mpn_copyi(cop2 + pfqlen*i, (op2 + i)->coeffs, (op2 + i)->length);
55 }
56 }
57 else
58 {
59 cop2 = cop1;
60 }
61
62 crop = (mp_limb_t *) flint_malloc(crlen*sizeof(mp_limb_t));
63
64 if (clen1 >= clen2)
65 _nmod_poly_mul(crop, cop1, clen1, cop2, clen2, mod);
66 else
67 _nmod_poly_mul(crop, cop2, clen2, cop1, clen1, mod);
68
69 for (i = 0; i < rlen - 1; i++)
70 {
71 _fq_nmod_reduce(crop + pfqlen*i, pfqlen, ctx);
72 len = fqlen;
73 while (len && (*(crop + pfqlen*i + len - 1) == UWORD(0))) len--;
74 nmod_poly_fit_length(rop + i, len);
75 (rop + i)->length = len;
76 flint_mpn_copyi((rop + i)->coeffs, crop + pfqlen*i, len);
77 }
78 {
79 len = lrlen;
80 if (len > fqlen)
81 {
82 _fq_nmod_reduce(crop + pfqlen*i, len, ctx);
83 len = fqlen;
84 while (len && (*(crop + pfqlen*i + len - 1) == UWORD(0))) len--;
85 }
86 nmod_poly_fit_length(rop + i, len);
87 (rop + i)->length = len;
88 flint_mpn_copyi((rop + i)->coeffs, crop + pfqlen*i, len);
89 }
90
91 flint_free(cop1);
92 if (op2 != op1)
93 {
94 flint_free(cop2);
95 }
96 flint_free(crop);
97 }
98
99 void
_fq_nmod_poly_mul_univariate(fq_nmod_struct * rop,const fq_nmod_struct * op1,slong len1,const fq_nmod_struct * op2,slong len2,const fq_nmod_ctx_t ctx)100 _fq_nmod_poly_mul_univariate (fq_nmod_struct * rop, const fq_nmod_struct * op1, slong len1, const fq_nmod_struct * op2, slong len2, const fq_nmod_ctx_t ctx)
101 {
102 slong len1n = len1, len2n = len2;
103
104 _fq_nmod_poly_normalise2(op1, &len1n, ctx);
105 _fq_nmod_poly_normalise2(op2, &len2n, ctx);
106
107 if (len1n == 0)
108 _fq_nmod_vec_zero(rop, len1 + len2 - 1, ctx);
109 else if (len2n == 0)
110 _fq_nmod_vec_zero(rop, len1 + len2 - 1, ctx);
111 else
112 {
113 _fq_nmod_poly_mul_univariate_no_pad(rop, op1, len1n, op2, len2n, ctx);
114
115 _fq_nmod_vec_zero(rop + len1n + len2n - 1,
116 len1 + len2 - len1n - len2n, ctx);
117 }
118 }
119
120 void
fq_nmod_poly_mul_univariate(fq_nmod_poly_t rop,const fq_nmod_poly_t op1,const fq_nmod_poly_t op2,const fq_nmod_ctx_t ctx)121 fq_nmod_poly_mul_univariate (fq_nmod_poly_t rop,
122 const fq_nmod_poly_t op1,
123 const fq_nmod_poly_t op2,
124 const fq_nmod_ctx_t ctx)
125 {
126 const slong len1 = op1->length;
127 const slong len2 = op2->length;
128 const slong rlen = op1->length + op2->length - 1;
129
130 if (len1 == 0 || len2 == 0)
131 {
132 fq_nmod_poly_zero(rop, ctx);
133 return;
134 }
135 else
136 {
137 fq_nmod_poly_fit_length(rop, rlen, ctx);
138 _fq_nmod_poly_mul_univariate(rop->coeffs, op1->coeffs, len1,
139 op2->coeffs, len2, ctx);
140 _fq_nmod_poly_set_length(rop, rlen, ctx);
141 }
142 }
143
144