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