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