1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
/*
Copyright (C) 2010 William Hart
This file is part of FLINT.
FLINT is free software: you can redistribute it and/or modify it under
the terms of the GNU Lesser General Public License (LGPL) as published
by the Free Software Foundation; either version 3 of the License, or
(at your option) any later version. See <https://www.gnu.org/licenses/>.
*/
#include "mpn_extras.h"
#include "fmpz.h"
int
fmpz_bit_pack(nn_ptr arr, flint_bitcnt_t shift, flint_bitcnt_t bits,
const fmpz_t coeff, int negate, int borrow)
{
ulong save = arr[0];
fmpz c = *coeff;
int sign = fmpz_sgn(coeff);
ulong cy;
ulong limbs = (shift + bits) / FLINT_BITS;
ulong rem_bits = (shift + bits) % FLINT_BITS;
ulong mask;
ulong size;
if (sign == 0) /* special case, deal with zero (store -borrow) */
{
if (borrow)
{
/* store -1 shifted and add save back in */
arr[0] = ((~(ulong) 0) << shift) + save;
/* com remaining limbs */
if (limbs > 1)
flint_mpn_store(arr + 1, limbs - 1, ~(ulong) 0);
/* com remaining bits */
if (limbs)
{
if (rem_bits)
arr[limbs] = (((ulong) 1) << rem_bits) - (ulong) 1;
}
else
{
/* mask off final limb */
mask = (((ulong) 1) << rem_bits) - (ulong) 1;
arr[limbs] &= mask;
}
}
return borrow;
}
/*
Let |c| = b. If c is -ve and negate == 0 or c is positive and negate is 1
we want -b - borrow.
If c is +ve and negate is 0 or c is negative and negate == 1, we want
b - borrow.
*/
if ((sign ^ negate) < 0) /* -b - borrow = com(b) + 1 - borrow */
{
if (!COEFF_IS_MPZ(c))
{
/* compute d = -b - borrow */
ulong d = (c < WORD(0) ? c - borrow : -c - borrow);
/* store d << shift and add save back into place */
arr[0] = (d << shift) + save;
/* store carry from d<<shift and com remaining bits of second limb */
if (limbs)
{
if (shift)
arr[1] =
(d >> (FLINT_BITS - shift)) +
((~(ulong) 0) << shift);
else
arr[1] = ~(ulong) 0;
}
size = 2;
}
else
{
mpz_ptr ptr = COEFF_TO_PTR(c);
size = FLINT_ABS(ptr->_mp_size);
/* complement coefficient into arr */
mpn_com(arr, ptr->_mp_d, size);
/* deal with +1 - borrow */
if (!borrow)
mpn_add_1(arr, arr, size, 1); /* cannot be a carry, else we com'd 0 */
/* shift into place */
if (shift)
{
cy = mpn_lshift(arr, arr, size, shift);
if (limbs + (rem_bits != 0) > size)
arr[size++] = ((~(ulong) 0) << shift) + cy;
}
/* add back in saved bits from start of field */
arr[0] += save;
}
if (limbs >= size)
{
/* com any additional limbs */
if (limbs > size)
flint_mpn_store(arr + size, limbs - size, ~(ulong) 0);
/* com remaining bits */
if (rem_bits)
arr[limbs] = (((ulong) 1) << rem_bits) - (ulong) 1;
}
else
{
/* mask off final limb */
mask = (((ulong) 1) << rem_bits) - (ulong) 1;
arr[limbs] &= mask;
}
return 1;
}
else /* b - borrow */
{
if (!COEFF_IS_MPZ(c))
{
/* compute d = b - borrow */
ulong d = (c < WORD(0) ? -c - borrow : c - borrow);
/* store d<<shift and add save back into place */
arr[0] = (d << shift) + save;
/* store carry from d<<shift */
if (limbs + (rem_bits != 0) > 1)
{
if (shift)
arr[1] = (d >> (FLINT_BITS - shift));
}
}
else
{
mpz_ptr ptr = COEFF_TO_PTR(c);
size = FLINT_ABS(ptr->_mp_size);
/* shift into place */
if (shift)
{
cy = mpn_lshift(arr, ptr->_mp_d, size, shift);
if (cy)
arr[size++] = cy;
}
else
flint_mpn_copyi(arr, ptr->_mp_d, size);
/* deal with - borrow */
if (borrow)
mpn_sub_1(arr, arr, size, ((ulong) 1) << shift);
/* add back in saved bits from start of field */
arr[0] += save;
}
return 0;
}
}