rts/gmp/mpz/ior.c

   1 /* mpz_ior -- Logical inclusive or.
   2
   3 Copyright (C) 1991, 1993, 1994, 1996, 1997, 2000 Free Software Foundation,
   4 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 2.1 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; see the file COPYING.LIB.  If not, write to
  20 the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  21 MA 02111-1307, USA. */
  22
  23 #include "gmp.h"
  24 #include "gmp-impl.h"
  25
  26 void
  27 #if __STDC__
  28 mpz_ior (mpz_ptr res, mpz_srcptr op1, mpz_srcptr op2)
  29 #else
  30 mpz_ior (res, op1, op2)
  31      mpz_ptr res;
  32      mpz_srcptr op1;
  33      mpz_srcptr op2;
  34 #endif
  35 {
  36   mp_srcptr op1_ptr, op2_ptr;
  37   mp_size_t op1_size, op2_size;
  38   mp_ptr res_ptr;
  39   mp_size_t res_size;
  40   mp_size_t i;
  41   TMP_DECL (marker);
  42
  43   TMP_MARK (marker);
  44   op1_size = op1->_mp_size;
  45   op2_size = op2->_mp_size;
  46
  47   op1_ptr = op1->_mp_d;
  48   op2_ptr = op2->_mp_d;
  49   res_ptr = res->_mp_d;
  50
  51   if (op1_size >= 0)
  52     {
  53       if (op2_size >= 0)
  54         {
  55           if (op1_size >= op2_size)
  56             {
  57               if (res->_mp_alloc < op1_size)
  58                 {
  59                   _mpz_realloc (res, op1_size);
  60                   op1_ptr = op1->_mp_d;
  61                   op2_ptr = op2->_mp_d;
  62                   res_ptr = res->_mp_d;
  63                 }
  64
  65               if (res_ptr != op1_ptr)
  66                 MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size,
  67                           op1_size - op2_size);
  68               for (i = op2_size - 1; i >= 0; i--)
  69                 res_ptr[i] = op1_ptr[i] | op2_ptr[i];
  70               res_size = op1_size;
  71             }
  72           else
  73             {
  74               if (res->_mp_alloc < op2_size)
  75                 {
  76                   _mpz_realloc (res, op2_size);
  77                   op1_ptr = op1->_mp_d;
  78                   op2_ptr = op2->_mp_d;
  79                   res_ptr = res->_mp_d;
  80                 }
  81
  82               if (res_ptr != op2_ptr)
  83                 MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size,
  84                           op2_size - op1_size);
  85               for (i = op1_size - 1; i >= 0; i--)
  86                 res_ptr[i] = op1_ptr[i] | op2_ptr[i];
  87               res_size = op2_size;
  88             }
  89
  90           res->_mp_size = res_size;
  91           return;
  92         }
  93       else /* op2_size < 0 */
  94         {
  95           /* Fall through to the code at the end of the function.  */
  96         }
  97     }
  98   else
  99     {
 100       if (op2_size < 0)
 101         {
 102           mp_ptr opx;
 103           mp_limb_t cy;
 104
 105           /* Both operands are negative, so will be the result.
 106              -((-OP1) | (-OP2)) = -(~(OP1 - 1) | ~(OP2 - 1)) =
 107              = ~(~(OP1 - 1) | ~(OP2 - 1)) + 1 =
 108              = ((OP1 - 1) & (OP2 - 1)) + 1      */
 109
 110           op1_size = -op1_size;
 111           op2_size = -op2_size;
 112
 113           res_size = MIN (op1_size, op2_size);
 114
 115           /* Possible optimization: Decrease mpn_sub precision,
 116              as we won't use the entire res of both.  */
 117           opx = (mp_ptr) TMP_ALLOC (res_size * BYTES_PER_MP_LIMB);
 118           mpn_sub_1 (opx, op1_ptr, res_size, (mp_limb_t) 1);
 119           op1_ptr = opx;
 120
 121           opx = (mp_ptr) TMP_ALLOC (res_size * BYTES_PER_MP_LIMB);
 122           mpn_sub_1 (opx, op2_ptr, res_size, (mp_limb_t) 1);
 123           op2_ptr = opx;
 124
 125           if (res->_mp_alloc < res_size)
 126             {
 127               _mpz_realloc (res, res_size);
 128               res_ptr = res->_mp_d;
 129               /* Don't re-read OP1_PTR and OP2_PTR.  They point to
 130                  temporary space--never to the space RES->_mp_d used
 131                  to point to before reallocation.  */
 132             }
 133
 134           /* First loop finds the size of the result.  */
 135           for (i = res_size - 1; i >= 0; i--)
 136             if ((op1_ptr[i] & op2_ptr[i]) != 0)
 137               break;
 138           res_size = i + 1;
 139
 140           if (res_size != 0)
 141             {
 142               /* Second loop computes the real result.  */
 143               for (i = res_size - 1; i >= 0; i--)
 144                 res_ptr[i] = op1_ptr[i] & op2_ptr[i];
 145
 146               cy = mpn_add_1 (res_ptr, res_ptr, res_size, (mp_limb_t) 1);
 147               if (cy)
 148                 {
 149                   res_ptr[res_size] = cy;
 150                   res_size++;
 151                 }
 152             }
 153           else
 154             {
 155               res_ptr[0] = 1;
 156               res_size = 1;
 157             }
 158
 159           res->_mp_size = -res_size;
 160           TMP_FREE (marker);
 161           return;
 162         }
 163       else
 164         {
 165           /* We should compute -OP1 | OP2.  Swap OP1 and OP2 and fall
 166              through to the code that handles OP1 | -OP2.  */
 167           MPZ_SRCPTR_SWAP (op1, op2);
 168           MPN_SRCPTR_SWAP (op1_ptr,op1_size, op2_ptr,op2_size);
 169         }
 170     }
 171
 172   {
 173     mp_ptr opx;
 174     mp_limb_t cy;
 175     mp_size_t res_alloc;
 176     mp_size_t count;
 177
 178     /* Operand 2 negative, so will be the result.
 179        -(OP1 | (-OP2)) = -(OP1 | ~(OP2 - 1)) =
 180        = ~(OP1 | ~(OP2 - 1)) + 1 =
 181        = (~OP1 & (OP2 - 1)) + 1      */
 182
 183     op2_size = -op2_size;
 184
 185     res_alloc = op2_size;
 186
 187     opx = (mp_ptr) TMP_ALLOC (op2_size * BYTES_PER_MP_LIMB);
 188     mpn_sub_1 (opx, op2_ptr, op2_size, (mp_limb_t) 1);
 189     op2_ptr = opx;
 190     op2_size -= op2_ptr[op2_size - 1] == 0;
 191
 192     if (res->_mp_alloc < res_alloc)
 193       {
 194         _mpz_realloc (res, res_alloc);
 195         op1_ptr = op1->_mp_d;
 196         res_ptr = res->_mp_d;
 197         /* Don't re-read OP2_PTR.  It points to temporary space--never
 198            to the space RES->_mp_d used to point to before reallocation.  */
 199       }
 200
 201     if (op1_size >= op2_size)
 202       {
 203         /* We can just ignore the part of OP1 that stretches above OP2,
 204            because the result limbs are zero there.  */
 205
 206         /* First loop finds the size of the result.  */
 207         for (i = op2_size - 1; i >= 0; i--)
 208           if ((~op1_ptr[i] & op2_ptr[i]) != 0)
 209             break;
 210         res_size = i + 1;
 211         count = res_size;
 212       }
 213     else
 214       {
 215         res_size = op2_size;
 216
 217         /* Copy the part of OP2 that stretches above OP1, to RES.  */
 218         MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size, op2_size - op1_size);
 219         count = op1_size;
 220       }
 221
 222     if (res_size != 0)
 223       {
 224         /* Second loop computes the real result.  */
 225         for (i = count - 1; i >= 0; i--)
 226           res_ptr[i] = ~op1_ptr[i] & op2_ptr[i];
 227
 228         cy = mpn_add_1 (res_ptr, res_ptr, res_size, (mp_limb_t) 1);
 229         if (cy)
 230           {
 231             res_ptr[res_size] = cy;
 232             res_size++;
 233           }
 234       }
 235     else
 236       {
 237         res_ptr[0] = 1;
 238         res_size = 1;
 239       }
 240
 241     res->_mp_size = -res_size;
 242   }
 243   TMP_FREE (marker);
 244 }