1 /*
2 Copyright (C) 2007 David Howden
3 Copyright (C) 2010 William Hart
4
5 This file is part of FLINT.
6
7 FLINT is free software: you can redistribute it and/or modify it under
8 the terms of the GNU Lesser General Public License (LGPL) as published
9 by the Free Software Foundation; either version 2.1 of the License, or
10 (at your option) any later version. See <http://www.gnu.org/licenses/>.
11 */
12
13 #include <stdlib.h>
14 #include <gmp.h>
15 #include "flint.h"
16 #include "nmod_vec.h"
17 #include "nmod_poly.h"
18 #include "fmpz.h"
19
20 /* Assumes length > 0, bits > 0. */
21 void
_nmod_poly_bit_pack(mp_ptr res,mp_srcptr poly,slong len,flint_bitcnt_t bits)22 _nmod_poly_bit_pack(mp_ptr res, mp_srcptr poly, slong len, flint_bitcnt_t bits)
23 {
24 slong i;
25 ulong current_bit = 0, current_limb = 0;
26 ulong total_limbs = (len * bits - 1) / FLINT_BITS + 1;
27 mp_limb_t temp_lower, temp_upper;
28
29 res[0] = WORD(0);
30
31 if (bits < FLINT_BITS)
32 {
33 ulong boundary_limit_bit = FLINT_BITS - bits;
34
35 for (i = 0; i < len; i++)
36 {
37 if (current_bit > boundary_limit_bit)
38 {
39 /* the coefficient will be added accross a limb boundary */
40 temp_lower = (poly[i] << current_bit);
41 temp_upper = (poly[i] >> (FLINT_BITS - current_bit));
42
43 res[current_limb] |= temp_lower;
44
45 current_limb++;
46 res[current_limb] = temp_upper;
47
48 current_bit += bits - FLINT_BITS;
49 }
50 else
51 {
52 /* the coefficient will fit in the current limb */
53 temp_lower = poly[i] << current_bit;
54 res[current_limb] |= temp_lower;
55
56 current_bit += bits;
57
58 if (current_bit == FLINT_BITS)
59 {
60 current_limb++;
61 if (current_limb < total_limbs)
62 res[current_limb] = WORD(0);
63 current_bit = 0;
64 }
65 }
66 }
67 }
68 else if (bits == FLINT_BITS)
69 {
70 for (i = 0; i < len; i++)
71 res[i] = poly[i];
72 }
73 else if (bits == 2 * FLINT_BITS)
74 {
75 for (i = 0; i < len; i++)
76 {
77 res[current_limb++] = poly[i];
78 res[current_limb++] = WORD(0);
79 }
80 }
81 else if (bits < 2 * FLINT_BITS)
82 {
83 for (i = 0; i < len; i++)
84 {
85 /* the coefficient will be added accross a limb boundary */
86 temp_lower = poly[i] << current_bit;
87 temp_upper = r_shift(poly[i], FLINT_BITS - current_bit);
88
89 res[current_limb++] |= temp_lower;
90 res[current_limb] = temp_upper;
91
92 current_bit += bits - FLINT_BITS;
93
94 if (current_bit >= FLINT_BITS)
95 {
96 current_bit -= FLINT_BITS;
97 current_limb++;
98 if (current_limb < total_limbs)
99 res[current_limb] = WORD(0);
100 }
101 }
102 }
103 else /* 2*FLINT_BITS < bits < 3*FLINT_BITS */
104 {
105 for (i = 0; i < len; i++)
106 {
107 temp_lower = poly[i] << current_bit;
108 temp_upper = r_shift(poly[i], FLINT_BITS - current_bit);
109
110 res[current_limb++] |= temp_lower;
111 res[current_limb++] = temp_upper;
112
113 if (current_limb < total_limbs)
114 res[current_limb] = WORD(0);
115 current_bit += bits - 2 * FLINT_BITS;
116
117 if (current_bit >= FLINT_BITS)
118 {
119 current_bit -= FLINT_BITS;
120 current_limb++;
121 if (current_limb < total_limbs)
122 res[current_limb] = WORD(0);
123 }
124 }
125 }
126 }
127
128 void
nmod_poly_bit_pack(fmpz_t f,const nmod_poly_t poly,flint_bitcnt_t bit_size)129 nmod_poly_bit_pack(fmpz_t f, const nmod_poly_t poly,
130 flint_bitcnt_t bit_size)
131 {
132 slong len, limbs;
133 __mpz_struct * mpz;
134 slong i;
135
136 len = nmod_poly_length(poly);
137
138 if (len == 0 || bit_size == 0)
139 {
140 fmpz_zero(f);
141 return;
142 }
143
144 mpz = _fmpz_promote(f);
145 mpz_realloc2(mpz, len * bit_size);
146
147 limbs = (len * bit_size - 1) / FLINT_BITS + 1;
148
149 _nmod_poly_bit_pack(mpz->_mp_d, poly->coeffs, len, bit_size);
150
151 for (i = limbs - 1; i >= 0; i--)
152 {
153 if (mpz->_mp_d[i] != 0)
154 break;
155 }
156
157 mpz->_mp_size = i + 1;
158 _fmpz_demote_val(f);
159 }
160