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