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 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