1/* mpz_ior -- Logical inclusive or.
2
3Copyright 1991, 1993, 1994, 1996, 1997, 2000, 2001, 2005 Free Software
4Foundation, Inc.
5
6This file is part of the GNU MP Library.
7
8The GNU MP Library is free software; you can redistribute it and/or modify
9it under the terms of the GNU Lesser General Public License as published by
10the Free Software Foundation; either version 3 of the License, or (at your
11option) any later version.
12
13The GNU MP Library is distributed in the hope that it will be useful, but
14WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
16License for more details.
17
18You should have received a copy of the GNU Lesser General Public License
19along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
20
21#include "gmp.h"
22#include "gmp-impl.h"
23
24void
25mpz_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