contrib/gmp/mpz/ior.c

   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 }