1 /* mpz_ior -- Logical inclusive or.
2
3 Copyright 1991, 1993, 1994, 1996, 1997, 2000, 2001, 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_ior(mpz_ptr res,mpz_srcptr op1,mpz_srcptr op2)25 mpz_ior (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 if (op1_size >= op2_size)
47 {
48 if (ALLOC(res) < op1_size)
49 {
50 _mpz_realloc (res, op1_size);
51 /* No overlapping possible: op1_ptr = PTR(op1); */
52 op2_ptr = PTR(op2);
53 res_ptr = PTR(res);
54 }
55
56 if (res_ptr != op1_ptr)
57 MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size,
58 op1_size - op2_size);
59 for (i = op2_size - 1; i >= 0; i--)
60 res_ptr[i] = op1_ptr[i] | op2_ptr[i];
61 res_size = op1_size;
62 }
63 else
64 {
65 if (ALLOC(res) < op2_size)
66 {
67 _mpz_realloc (res, op2_size);
68 op1_ptr = PTR(op1);
69 /* No overlapping possible: op2_ptr = PTR(op2); */
70 res_ptr = PTR(res);
71 }
72
73 if (res_ptr != op2_ptr)
74 MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size,
75 op2_size - op1_size);
76 for (i = op1_size - 1; i >= 0; i--)
77 res_ptr[i] = op1_ptr[i] | op2_ptr[i];
78 res_size = op2_size;
79 }
80
81 SIZ(res) = res_size;
82 return;
83 }
84 else /* op2_size < 0 */
85 {
86 /* Fall through to the code at the end of the function. */
87 }
88 }
89 else
90 {
91 if (op2_size < 0)
92 {
93 mp_ptr opx;
94 mp_limb_t cy;
95
96 /* Both operands are negative, so will be the result.
97 -((-OP1) | (-OP2)) = -(~(OP1 - 1) | ~(OP2 - 1)) =
98 = ~(~(OP1 - 1) | ~(OP2 - 1)) + 1 =
99 = ((OP1 - 1) & (OP2 - 1)) + 1 */
100
101 op1_size = -op1_size;
102 op2_size = -op2_size;
103
104 res_size = MIN (op1_size, op2_size);
105
106 /* Possible optimization: Decrease mpn_sub precision,
107 as we won't use the entire res of both. */
108 opx = TMP_ALLOC_LIMBS (res_size);
109 mpn_sub_1 (opx, op1_ptr, res_size, (mp_limb_t) 1);
110 op1_ptr = opx;
111
112 opx = TMP_ALLOC_LIMBS (res_size);
113 mpn_sub_1 (opx, op2_ptr, res_size, (mp_limb_t) 1);
114 op2_ptr = opx;
115
116 if (ALLOC(res) < res_size)
117 {
118 _mpz_realloc (res, res_size);
119 /* op1_ptr and op2_ptr point to temporary space. */
120 res_ptr = PTR(res);
121 }
122
123 /* First loop finds the size of the result. */
124 for (i = res_size - 1; i >= 0; i--)
125 if ((op1_ptr[i] & op2_ptr[i]) != 0)
126 break;
127 res_size = i + 1;
128
129 if (res_size != 0)
130 {
131 /* Second loop computes the real result. */
132 for (i = res_size - 1; i >= 0; i--)
133 res_ptr[i] = op1_ptr[i] & op2_ptr[i];
134
135 cy = mpn_add_1 (res_ptr, res_ptr, res_size, (mp_limb_t) 1);
136 if (cy)
137 {
138 res_ptr[res_size] = cy;
139 res_size++;
140 }
141 }
142 else
143 {
144 res_ptr[0] = 1;
145 res_size = 1;
146 }
147
148 SIZ(res) = -res_size;
149 TMP_FREE;
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. */
156 MPZ_SRCPTR_SWAP (op1, op2);
157 MPN_SRCPTR_SWAP (op1_ptr,op1_size, op2_ptr,op2_size);
158 }
159 }
160
161 {
162 mp_ptr opx;
163 mp_limb_t cy;
164 mp_size_t res_alloc;
165 mp_size_t count;
166
167 /* Operand 2 negative, so will be the result.
168 -(OP1 | (-OP2)) = -(OP1 | ~(OP2 - 1)) =
169 = ~(OP1 | ~(OP2 - 1)) + 1 =
170 = (~OP1 & (OP2 - 1)) + 1 */
171
172 op2_size = -op2_size;
173
174 res_alloc = op2_size;
175
176 opx = TMP_ALLOC_LIMBS (op2_size);
177 mpn_sub_1 (opx, op2_ptr, op2_size, (mp_limb_t) 1);
178 op2_ptr = opx;
179 op2_size -= op2_ptr[op2_size - 1] == 0;
180
181 if (ALLOC(res) < res_alloc)
182 {
183 _mpz_realloc (res, res_alloc);
184 op1_ptr = PTR(op1);
185 /* op2_ptr points to temporary space. */
186 res_ptr = PTR(res);
187 }
188
189 if (op1_size >= op2_size)
190 {
191 /* We can just ignore the part of OP1 that stretches above OP2,
192 because the result limbs are zero there. */
193
194 /* First loop finds the size of the result. */
195 for (i = op2_size - 1; i >= 0; i--)
196 if ((~op1_ptr[i] & op2_ptr[i]) != 0)
197 break;
198 res_size = i + 1;
199 count = res_size;
200 }
201 else
202 {
203 res_size = op2_size;
204
205 /* Copy the part of OP2 that stretches above OP1, to RES. */
206 MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size, op2_size - op1_size);
207 count = op1_size;
208 }
209
210 if (res_size != 0)
211 {
212 /* Second loop computes the real result. */
213 for (i = count - 1; i >= 0; i--)
214 res_ptr[i] = ~op1_ptr[i] & op2_ptr[i];
215
216 cy = mpn_add_1 (res_ptr, res_ptr, res_size, (mp_limb_t) 1);
217 if (cy)
218 {
219 res_ptr[res_size] = cy;
220 res_size++;
221 }
222 }
223 else
224 {
225 res_ptr[0] = 1;
226 res_size = 1;
227 }
228
229 SIZ(res) = -res_size;
230 }
231 TMP_FREE;
232 }
233