1 /* mpz_and -- Logical and.
2
3 Copyright 1991, 1993, 1994, 1996, 1997, 2000, 2001, 2003, 2005 Free Software
4 Foundation, Inc.
5
6 This file is part of the GNU MP Library.
7
8 The GNU MP Library is free software; you can redistribute it and/or modify
9 it under the terms of the GNU Lesser General Public License as published by
10 the Free Software Foundation; either version 3 of the License, or (at your
11 option) any later version.
12
13 The GNU MP Library is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
16 License for more details.
17
18 You should have received a copy of the GNU Lesser General Public License
19 along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
20
21 #include "gmp.h"
22 #include "gmp-impl.h"
23
24 void
mpz_and(mpz_ptr res,mpz_srcptr op1,mpz_srcptr op2)25 mpz_and (mpz_ptr res, mpz_srcptr op1, mpz_srcptr op2)
26 {
27 mp_srcptr op1_ptr, op2_ptr;
28 mp_size_t op1_size, op2_size;
29 mp_ptr res_ptr;
30 mp_size_t res_size;
31 mp_size_t i;
32 TMP_DECL;
33
34 TMP_MARK;
35 op1_size = SIZ(op1);
36 op2_size = SIZ(op2);
37
38 op1_ptr = PTR(op1);
39 op2_ptr = PTR(op2);
40 res_ptr = PTR(res);
41
42 if (op1_size >= 0)
43 {
44 if (op2_size >= 0)
45 {
46 res_size = MIN (op1_size, op2_size);
47 /* First loop finds the size of the result. */
48 for (i = res_size - 1; i >= 0; i--)
49 if ((op1_ptr[i] & op2_ptr[i]) != 0)
50 break;
51 res_size = i + 1;
52
53 /* Handle allocation, now then we know exactly how much space is
54 needed for the result. */
55 if (UNLIKELY (ALLOC(res) < res_size))
56 {
57 _mpz_realloc (res, res_size);
58 res_ptr = PTR(res);
59 /* Don't re-read op1_ptr and op2_ptr. Since res_size <=
60 MIN(op1_size, op2_size), we will not reach this code when op1
61 is identical to res or op2 is identical to res. */
62 }
63
64 SIZ(res) = res_size;
65 if (LIKELY (res_size != 0))
66 mpn_and_n (res_ptr, op1_ptr, op2_ptr, res_size);
67 return;
68 }
69 else /* op2_size < 0 */
70 {
71 /* Fall through to the code at the end of the function. */
72 }
73 }
74 else
75 {
76 if (op2_size < 0)
77 {
78 mp_ptr opx;
79 mp_limb_t cy;
80 mp_size_t res_alloc;
81
82 /* Both operands are negative, so will be the result.
83 -((-OP1) & (-OP2)) = -(~(OP1 - 1) & ~(OP2 - 1)) =
84 = ~(~(OP1 - 1) & ~(OP2 - 1)) + 1 =
85 = ((OP1 - 1) | (OP2 - 1)) + 1 */
86
87 /* It might seem as we could end up with an (invalid) result with
88 a leading zero-limb here when one of the operands is of the
89 type 1,,0,,..,,.0. But some analysis shows that we surely
90 would get carry into the zero-limb in this situation... */
91
92 op1_size = -op1_size;
93 op2_size = -op2_size;
94
95 res_alloc = 1 + MAX (op1_size, op2_size);
96
97 opx = TMP_ALLOC_LIMBS (op1_size);
98 mpn_sub_1 (opx, op1_ptr, op1_size, (mp_limb_t) 1);
99 op1_ptr = opx;
100
101 opx = TMP_ALLOC_LIMBS (op2_size);
102 mpn_sub_1 (opx, op2_ptr, op2_size, (mp_limb_t) 1);
103 op2_ptr = opx;
104
105 if (ALLOC(res) < res_alloc)
106 {
107 _mpz_realloc (res, res_alloc);
108 res_ptr = PTR(res);
109 /* Don't re-read OP1_PTR and OP2_PTR. They point to temporary
110 space--never to the space PTR(res) used to point to before
111 reallocation. */
112 }
113
114 if (op1_size >= op2_size)
115 {
116 MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size,
117 op1_size - op2_size);
118 for (i = op2_size - 1; i >= 0; i--)
119 res_ptr[i] = op1_ptr[i] | op2_ptr[i];
120 res_size = op1_size;
121 }
122 else
123 {
124 MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size,
125 op2_size - op1_size);
126 for (i = op1_size - 1; i >= 0; i--)
127 res_ptr[i] = op1_ptr[i] | op2_ptr[i];
128 res_size = op2_size;
129 }
130
131 cy = mpn_add_1 (res_ptr, res_ptr, res_size, (mp_limb_t) 1);
132 if (cy)
133 {
134 res_ptr[res_size] = cy;
135 res_size++;
136 }
137
138 SIZ(res) = -res_size;
139 TMP_FREE;
140 return;
141 }
142 else
143 {
144 /* We should compute -OP1 & OP2. Swap OP1 and OP2 and fall
145 through to the code that handles OP1 & -OP2. */
146 MPZ_SRCPTR_SWAP (op1, op2);
147 MPN_SRCPTR_SWAP (op1_ptr,op1_size, op2_ptr,op2_size);
148 }
149
150 }
151
152 {
153 #if ANDNEW
154 mp_size_t op2_lim;
155 mp_size_t count;
156
157 /* OP2 must be negated as with infinite precision.
158
159 Scan from the low end for a non-zero limb. The first non-zero
160 limb is simply negated (two's complement). Any subsequent
161 limbs are one's complemented. Of course, we don't need to
162 handle more limbs than there are limbs in the other, positive
163 operand as the result for those limbs is going to become zero
164 anyway. */
165
166 /* Scan for the least significant non-zero OP2 limb, and zero the
167 result meanwhile for those limb positions. (We will surely
168 find a non-zero limb, so we can write the loop with one
169 termination condition only.) */
170 for (i = 0; op2_ptr[i] == 0; i++)
171 res_ptr[i] = 0;
172 op2_lim = i;
173
174 op2_size = -op2_size;
175
176 if (op1_size <= op2_size)
177 {
178 /* The ones-extended OP2 is >= than the zero-extended OP1.
179 RES_SIZE <= OP1_SIZE. Find the exact size. */
180 for (i = op1_size - 1; i > op2_lim; i--)
181 if ((op1_ptr[i] & ~op2_ptr[i]) != 0)
182 break;
183 res_size = i + 1;
184 for (i = res_size - 1; i > op2_lim; i--)
185 res_ptr[i] = op1_ptr[i] & ~op2_ptr[i];
186 res_ptr[op2_lim] = op1_ptr[op2_lim] & -op2_ptr[op2_lim];
187 /* Yes, this *can* happen! */
188 MPN_NORMALIZE (res_ptr, res_size);
189 }
190 else
191 {
192 /* The ones-extended OP2 is < than the zero-extended OP1.
193 RES_SIZE == OP1_SIZE, since OP1 is normalized. */
194 res_size = op1_size;
195 MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size, op1_size - op2_size);
196 for (i = op2_size - 1; i > op2_lim; i--)
197 res_ptr[i] = op1_ptr[i] & ~op2_ptr[i];
198 res_ptr[op2_lim] = op1_ptr[op2_lim] & -op2_ptr[op2_lim];
199 }
200
201 SIZ(res) = res_size;
202 #else
203
204 /* OP1 is positive and zero-extended,
205 OP2 is negative and ones-extended.
206 The result will be positive.
207 OP1 & -OP2 = OP1 & ~(OP2 - 1). */
208
209 mp_ptr opx;
210
211 op2_size = -op2_size;
212 opx = TMP_ALLOC_LIMBS (op2_size);
213 mpn_sub_1 (opx, op2_ptr, op2_size, (mp_limb_t) 1);
214 op2_ptr = opx;
215
216 if (op1_size > op2_size)
217 {
218 /* The result has the same size as OP1, since OP1 is normalized
219 and longer than the ones-extended OP2. */
220 res_size = op1_size;
221
222 /* Handle allocation, now then we know exactly how much space is
223 needed for the result. */
224 if (ALLOC(res) < res_size)
225 {
226 _mpz_realloc (res, res_size);
227 res_ptr = PTR(res);
228 /* Don't re-read OP1_PTR or OP2_PTR. Since res_size = op1_size,
229 we will not reach this code when op1 is identical to res.
230 OP2_PTR points to temporary space. */
231 }
232
233 MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size, res_size - op2_size);
234 for (i = op2_size - 1; i >= 0; i--)
235 res_ptr[i] = op1_ptr[i] & ~op2_ptr[i];
236
237 SIZ(res) = res_size;
238 }
239 else
240 {
241 /* Find out the exact result size. Ignore the high limbs of OP2,
242 OP1 is zero-extended and would make the result zero. */
243 for (i = op1_size - 1; i >= 0; i--)
244 if ((op1_ptr[i] & ~op2_ptr[i]) != 0)
245 break;
246 res_size = i + 1;
247
248 /* Handle allocation, now then we know exactly how much space is
249 needed for the result. */
250 if (ALLOC(res) < res_size)
251 {
252 _mpz_realloc (res, res_size);
253 res_ptr = PTR(res);
254 /* Don't re-read OP1_PTR. Since res_size <= op1_size, we will
255 not reach this code when op1 is identical to res. */
256 /* Don't re-read OP2_PTR. It points to temporary space--never
257 to the space PTR(res) used to point to before reallocation. */
258 }
259
260 for (i = res_size - 1; i >= 0; i--)
261 res_ptr[i] = op1_ptr[i] & ~op2_ptr[i];
262
263 SIZ(res) = res_size;
264 }
265 #endif
266 }
267 TMP_FREE;
268 }
269