contrib/libgmp/mpz/ior.c

   1 /* mpz_ior -- Logical inclusive or.
   2
   3 Copyright (C) 1991, 1993, 1994, 1996 Free Software Foundation, Inc.
   4
   5 This file is part of the GNU MP Library.
   6
   7 The GNU MP Library is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU Library General Public License as published by
   9 the Free Software Foundation; either version 2 of the License, or (at your
  10 option) any later version.
  11
  12 The GNU MP Library is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Library General Public
  15 License for more details.
  16
  17 You should have received a copy of the GNU Library General Public License
  18 along with the GNU MP Library; see the file COPYING.LIB.  If not, write to
  19 the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  20 MA 02111-1307, USA. */
  21
  22 #include "gmp.h"
  23 #include "gmp-impl.h"
  24
  25 void
  26 #if __STDC__
  27 mpz_ior (mpz_ptr res, mpz_srcptr op1, mpz_srcptr op2)
  28 #else
  29 mpz_ior (res, op1, op2)
  30      mpz_ptr res;
  31      mpz_srcptr op1;
  32      mpz_srcptr op2;
  33 #endif
  34 {
  35   mp_srcptr op1_ptr, op2_ptr;
  36   mp_size_t op1_size, op2_size;
  37   mp_ptr res_ptr;
  38   mp_size_t res_size;
  39   mp_size_t i;
  40   TMP_DECL (marker);
  41
  42   TMP_MARK (marker);
  43   op1_size = op1->_mp_size;
  44   op2_size = op2->_mp_size;
  45
  46   op1_ptr = op1->_mp_d;
  47   op2_ptr = op2->_mp_d;
  48   res_ptr = res->_mp_d;
  49
  50   if (op1_size >= 0)
  51     {
  52       if (op2_size >= 0)
  53         {
  54           if (op1_size >= op2_size)
  55             {
  56               if (res->_mp_alloc < op1_size)
  57                 {
  58                   _mpz_realloc (res, op1_size);
  59                   op1_ptr = op1->_mp_d;
  60                   op2_ptr = op2->_mp_d;
  61                   res_ptr = res->_mp_d;
  62                 }
  63
  64               if (res_ptr != op1_ptr)
  65                 MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size,
  66                           op1_size - op2_size);
  67               for (i = op2_size - 1; i >= 0; i--)
  68                 res_ptr[i] = op1_ptr[i] | op2_ptr[i];
  69               res_size = op1_size;
  70             }
  71           else
  72             {
  73               if (res->_mp_alloc < op2_size)
  74                 {
  75                   _mpz_realloc (res, op2_size);
  76                   op1_ptr = op1->_mp_d;
  77                   op2_ptr = op2->_mp_d;
  78                   res_ptr = res->_mp_d;
  79                 }
  80
  81               if (res_ptr != op2_ptr)
  82                 MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size,
  83                           op2_size - op1_size);
  84               for (i = op1_size - 1; i >= 0; i--)
  85                 res_ptr[i] = op1_ptr[i] | op2_ptr[i];
  86               res_size = op2_size;
  87             }
  88
  89           res->_mp_size = res_size;
  90           return;
  91         }
  92       else /* op2_size < 0 */
  93         {
  94           /* Fall through to the code at the end of the function.  */
  95         }
  96     }
  97   else
  98     {
  99       if (op2_size < 0)
 100         {
 101           mp_ptr opx;
 102           mp_limb_t cy;
 103
 104           /* Both operands are negative, so will be the result.
 105              -((-OP1) | (-OP2)) = -(~(OP1 - 1) | ~(OP2 - 1)) =
 106              = ~(~(OP1 - 1) | ~(OP2 - 1)) + 1 =
 107              = ((OP1 - 1) & (OP2 - 1)) + 1      */
 108
 109           op1_size = -op1_size;
 110           op2_size = -op2_size;
 111
 112           res_size = MIN (op1_size, op2_size);
 113
 114           /* Possible optimization: Decrease mpn_sub precision,
 115              as we won't use the entire res of both.  */
 116           opx = (mp_ptr) TMP_ALLOC (res_size * BYTES_PER_MP_LIMB);
 117           mpn_sub_1 (opx, op1_ptr, res_size, (mp_limb_t) 1);
 118           op1_ptr = opx;
 119
 120           opx = (mp_ptr) TMP_ALLOC (res_size * BYTES_PER_MP_LIMB);
 121           mpn_sub_1 (opx, op2_ptr, res_size, (mp_limb_t) 1);
 122           op2_ptr = opx;
 123
 124           if (res->_mp_alloc < res_size)
 125             {
 126               _mpz_realloc (res, res_size);
 127               res_ptr = res->_mp_d;
 128               /* Don't re-read OP1_PTR and OP2_PTR.  They point to
 129                  temporary space--never to the space RES->_mp_D used
 130                  to point to before reallocation.  */
 131             }
 132
 133           /* First loop finds the size of the result.  */
 134           for (i = res_size - 1; i >= 0; i--)
 135             if ((op1_ptr[i] & op2_ptr[i]) != 0)
 136               break;
 137           res_size = i + 1;
 138
 139           if (res_size != 0)
 140             {
 141               /* Second loop computes the real result.  */
 142               for (i = res_size - 1; i >= 0; i--)
 143                 res_ptr[i] = op1_ptr[i] & op2_ptr[i];
 144
 145               cy = mpn_add_1 (res_ptr, res_ptr, res_size, (mp_limb_t) 1);
 146               if (cy)
 147                 {
 148                   res_ptr[res_size] = cy;
 149                   res_size++;
 150                 }
 151             }
 152           else
 153             {
 154               res_ptr[0] = 1;
 155               res_size = 1;
 156             }
 157
 158           res->_mp_size = -res_size;
 159           TMP_FREE (marker);
 160           return;
 161         }
 162       else
 163         {
 164           /* We should compute -OP1 | OP2.  Swap OP1 and OP2 and fall
 165              through to the code that handles OP1 | -OP2.  */
 166           {mpz_srcptr t = op1; op1 = op2; op2 = t;}
 167           {mp_srcptr t = op1_ptr; op1_ptr = op2_ptr; op2_ptr = t;}
 168           {mp_size_t t = op1_size; op1_size = op2_size; op2_size = t;}
 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
 191     if (res->_mp_alloc < res_alloc)
 192       {
 193         _mpz_realloc (res, res_alloc);
 194         op1_ptr = op1->_mp_d;
 195         res_ptr = res->_mp_d;
 196         /* Don't re-read OP2_PTR.  It points to temporary space--never
 197            to the space RES->_mp_D used to point to before reallocation.  */
 198       }
 199
 200     if (op1_size >= op2_size)
 201       {
 202         /* We can just ignore the part of OP1 that stretches above OP2,
 203            because the result limbs are zero there.  */
 204
 205         /* First loop finds the size of the result.  */
 206         for (i = op2_size - 1; i >= 0; i--)
 207           if ((~op1_ptr[i] & op2_ptr[i]) != 0)
 208             break;
 209         res_size = i + 1;
 210         count = res_size;
 211       }
 212     else
 213       {
 214         res_size = op2_size;
 215
 216         /* Copy the part of OP2 that stretches above OP1, to RES.  */
 217         MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size, op2_size - op1_size);
 218         count = op1_size;
 219       }
 220
 221     if (res_size != 0)
 222       {
 223         /* Second loop computes the real result.  */
 224         for (i = count - 1; i >= 0; i--)
 225           res_ptr[i] = ~op1_ptr[i] & op2_ptr[i];
 226
 227         cy = mpn_add_1 (res_ptr, res_ptr, res_size, (mp_limb_t) 1);
 228         if (cy)
 229           {
 230             res_ptr[res_size] = cy;
 231             res_size++;
 232           }
 233       }
 234     else
 235       {
 236         res_ptr[0] = 1;
 237         res_size = 1;
 238       }
 239
 240     res->_mp_size = -res_size;
 241   }
 242   TMP_FREE (marker);
 243 }