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