Annotation of OpenXM_contrib/gmp/mpz/and.c, Revision 1.1.1.1
1.1 maekawa 1: /* mpz_and -- Logical and.
2:
3: Copyright (C) 1991, 1993, 1994, 1996 Free Software Foundation, Inc.
4:
5: This file is part of the GNU MP Library.
6:
7: The GNU MP Library is free software; you can redistribute it and/or modify
8: it under the terms of the GNU Library General Public License as published by
9: the Free Software Foundation; either version 2 of the License, or (at your
10: option) any later version.
11:
12: The GNU MP Library is distributed in the hope that it will be useful, but
13: WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14: or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public
15: License for more details.
16:
17: You should have received a copy of the GNU Library General Public License
18: along with the GNU MP Library; see the file COPYING.LIB. If not, write to
19: the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
20: MA 02111-1307, USA. */
21:
22: #include "gmp.h"
23: #include "gmp-impl.h"
24:
25: void
26: #if __STDC__
27: mpz_and (mpz_ptr res, mpz_srcptr op1, mpz_srcptr op2)
28: #else
29: mpz_and (res, op1, op2)
30: mpz_ptr res;
31: mpz_srcptr op1;
32: mpz_srcptr op2;
33: #endif
34: {
35: mp_srcptr op1_ptr, op2_ptr;
36: mp_size_t op1_size, op2_size;
37: mp_ptr res_ptr;
38: mp_size_t res_size;
39: mp_size_t i;
40: TMP_DECL (marker);
41:
42: TMP_MARK (marker);
43: op1_size = op1->_mp_size;
44: op2_size = op2->_mp_size;
45:
46: op1_ptr = op1->_mp_d;
47: op2_ptr = op2->_mp_d;
48: res_ptr = res->_mp_d;
49:
50: if (op1_size >= 0)
51: {
52: if (op2_size >= 0)
53: {
54: res_size = MIN (op1_size, op2_size);
55: /* First loop finds the size of the result. */
56: for (i = res_size - 1; i >= 0; i--)
57: if ((op1_ptr[i] & op2_ptr[i]) != 0)
58: break;
59: res_size = i + 1;
60:
61: /* Handle allocation, now then we know exactly how much space is
62: needed for the result. */
63: if (res->_mp_alloc < res_size)
64: {
65: _mpz_realloc (res, res_size);
66: op1_ptr = op1->_mp_d;
67: op2_ptr = op2->_mp_d;
68: res_ptr = res->_mp_d;
69: }
70:
71: /* Second loop computes the real result. */
72: for (i = res_size - 1; i >= 0; i--)
73: res_ptr[i] = op1_ptr[i] & op2_ptr[i];
74:
75: res->_mp_size = res_size;
76: return;
77: }
78: else /* op2_size < 0 */
79: {
80: /* Fall through to the code at the end of the function. */
81: }
82: }
83: else
84: {
85: if (op2_size < 0)
86: {
87: mp_ptr opx;
88: mp_limb_t cy;
89: mp_size_t res_alloc;
90:
91: /* Both operands are negative, so will be the result.
92: -((-OP1) & (-OP2)) = -(~(OP1 - 1) & ~(OP2 - 1)) =
93: = ~(~(OP1 - 1) & ~(OP2 - 1)) + 1 =
94: = ((OP1 - 1) | (OP2 - 1)) + 1 */
95:
96: /* It might seem as we could end up with an (invalid) result with
97: a leading zero-limb here when one of the operands is of the
98: type 1,,0,,..,,.0. But some analysis shows that we surely
99: would get carry into the zero-limb in this situation... */
100:
101: op1_size = -op1_size;
102: op2_size = -op2_size;
103:
104: res_alloc = 1 + MAX (op1_size, op2_size);
105:
106: opx = (mp_ptr) TMP_ALLOC (op1_size * BYTES_PER_MP_LIMB);
107: mpn_sub_1 (opx, op1_ptr, op1_size, (mp_limb_t) 1);
108: op1_ptr = opx;
109:
110: opx = (mp_ptr) TMP_ALLOC (op2_size * BYTES_PER_MP_LIMB);
111: mpn_sub_1 (opx, op2_ptr, op2_size, (mp_limb_t) 1);
112: op2_ptr = opx;
113:
114: if (res->_mp_alloc < res_alloc)
115: {
116: _mpz_realloc (res, res_alloc);
117: res_ptr = res->_mp_d;
118: /* Don't re-read OP1_PTR and OP2_PTR. They point to
119: temporary space--never to the space RES->_mp_D used
120: to point to before reallocation. */
121: }
122:
123: if (op1_size >= op2_size)
124: {
125: MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size,
126: op1_size - op2_size);
127: for (i = op2_size - 1; i >= 0; i--)
128: res_ptr[i] = op1_ptr[i] | op2_ptr[i];
129: res_size = op1_size;
130: }
131: else
132: {
133: MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size,
134: op2_size - op1_size);
135: for (i = op1_size - 1; i >= 0; i--)
136: res_ptr[i] = op1_ptr[i] | op2_ptr[i];
137: res_size = op2_size;
138: }
139:
140: cy = mpn_add_1 (res_ptr, res_ptr, res_size, (mp_limb_t) 1);
141: if (cy)
142: {
143: res_ptr[res_size] = cy;
144: res_size++;
145: }
146:
147: res->_mp_size = -res_size;
148: TMP_FREE (marker);
149: return;
150: }
151: else
152: {
153: /* We should compute -OP1 & OP2. Swap OP1 and OP2 and fall
154: through to the code that handles OP1 & -OP2. */
155: {mpz_srcptr t = op1; op1 = op2; op2 = t;}
156: {mp_srcptr t = op1_ptr; op1_ptr = op2_ptr; op2_ptr = t;}
157: {mp_size_t t = op1_size; op1_size = op2_size; op2_size = t;}
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:
176: /* Scan for the least significant. non-zero OP2 limb, and zero the
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
240: to the space RES->_mp_D used to point to before reallocation. */
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
267: to the space RES->_mp_D used to point to before reallocation. */
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