source/libs/gmp/gmp-src/mpz/ior.c

   1 /* mpz_ior -- Logical inclusive or.
   2
   3 Copyright 1991, 1993, 1994, 1996, 1997, 2000, 2001, 2005, 2012, 2013 Free
   4 Software 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 either:
  10
  11   * the GNU Lesser General Public License as published by the Free
  12     Software Foundation; either version 3 of the License, or (at your
  13     option) any later version.
  14
  15 or
  16
  17   * the GNU General Public License as published by the Free Software
  18     Foundation; either version 2 of the License, or (at your option) any
  19     later version.
  20
  21 or both in parallel, as here.
  22
  23 The GNU MP Library is distributed in the hope that it will be useful, but
  24 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  25 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  26 for more details.
  27
  28 You should have received copies of the GNU General Public License and the
  29 GNU Lesser General Public License along with the GNU MP Library.  If not,
  30 see https://www.gnu.org/licenses/.  */
  31
  32 #include "gmp.h"
  33 #include "gmp-impl.h"
  34
  35 void
  36 mpz_ior (mpz_ptr res, mpz_srcptr op1, mpz_srcptr op2)
  37 {
  38   mp_srcptr op1_ptr, op2_ptr;
  39   mp_size_t op1_size, op2_size;
  40   mp_ptr res_ptr;
  41   mp_size_t res_size;
  42   mp_size_t i;
  43   TMP_DECL;
  44
  45   TMP_MARK;
  46   op1_size = SIZ(op1);
  47   op2_size = SIZ(op2);
  48
  49   op1_ptr = PTR(op1);
  50   op2_ptr = PTR(op2);
  51   res_ptr = PTR(res);
  52
  53   if (op1_size >= 0)
  54     {
  55       if (op2_size >= 0)
  56         {
  57           if (op1_size >= op2_size)
  58             {
  59               if (ALLOC(res) < op1_size)
  60                 {
  61                   res_ptr = MPZ_REALLOC (res, op1_size);
  62                   /* No overlapping possible: op1_ptr = PTR(op1); */
  63                   op2_ptr = PTR(op2);
  64                 }
  65
  66               if (res_ptr != op1_ptr)
  67                 MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size,
  68                           op1_size - op2_size);
  69               if (LIKELY (op2_size != 0))
  70                 mpn_ior_n (res_ptr, op1_ptr, op2_ptr, op2_size);
  71               res_size = op1_size;
  72             }
  73           else
  74             {
  75               if (ALLOC(res) < op2_size)
  76                 {
  77                   res_ptr = MPZ_REALLOC (res, op2_size);
  78                   op1_ptr = PTR(op1);
  79                   /* No overlapping possible: op2_ptr = PTR(op2); */
  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               if (LIKELY (op1_size != 0))
  86                 mpn_ior_n (res_ptr, op1_ptr, op2_ptr, op1_size);
  87               res_size = op2_size;
  88             }
  89
  90           SIZ(res) = 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, opy;
 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           TMP_ALLOC_LIMBS_2 (opx, res_size, opy, res_size);
 117           mpn_sub_1 (opx, op1_ptr, res_size, (mp_limb_t) 1);
 118           op1_ptr = opx;
 119
 120           mpn_sub_1 (opy, op2_ptr, res_size, (mp_limb_t) 1);
 121           op2_ptr = opy;
 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               res_ptr = MPZ_NEWALLOC (res, res_size + 1);
 132
 133               /* Second loop computes the real result.  */
 134               mpn_and_n (res_ptr, op1_ptr, op2_ptr, res_size);
 135
 136               res_ptr[res_size] = 0;
 137               MPN_INCR_U (res_ptr, res_size + 1, 1);
 138               res_size += res_ptr[res_size];
 139             }
 140           else
 141             {
 142               res_ptr[0] = 1;
 143               res_size = 1;
 144             }
 145
 146           SIZ(res) = -res_size;
 147           TMP_FREE;
 148           return;
 149         }
 150       else
 151         {
 152           /* We should compute -OP1 | OP2.  Swap OP1 and OP2 and fall
 153              through to the code that handles OP1 | -OP2.  */
 154           MPZ_SRCPTR_SWAP (op1, op2);
 155           MPN_SRCPTR_SWAP (op1_ptr,op1_size, op2_ptr,op2_size);
 156         }
 157     }
 158
 159   {
 160     mp_ptr opx;
 161     mp_limb_t cy;
 162     mp_size_t res_alloc;
 163     mp_size_t count;
 164
 165     /* Operand 2 negative, so will be the result.
 166        -(OP1 | (-OP2)) = -(OP1 | ~(OP2 - 1)) =
 167        = ~(OP1 | ~(OP2 - 1)) + 1 =
 168        = (~OP1 & (OP2 - 1)) + 1      */
 169
 170     op2_size = -op2_size;
 171
 172     res_alloc = op2_size;
 173
 174     opx = TMP_ALLOC_LIMBS (op2_size);
 175     mpn_sub_1 (opx, op2_ptr, op2_size, (mp_limb_t) 1);
 176     op2_ptr = opx;
 177     op2_size -= op2_ptr[op2_size - 1] == 0;
 178
 179     if (ALLOC(res) < res_alloc)
 180       {
 181         _mpz_realloc (res, res_alloc);
 182         op1_ptr = PTR(op1);
 183         /* op2_ptr points to temporary space.  */
 184         res_ptr = PTR(res);
 185       }
 186
 187     if (op1_size >= op2_size)
 188       {
 189         /* We can just ignore the part of OP1 that stretches above OP2,
 190            because the result limbs are zero there.  */
 191
 192         /* First loop finds the size of the result.  */
 193         for (i = op2_size - 1; i >= 0; i--)
 194           if ((~op1_ptr[i] & op2_ptr[i]) != 0)
 195             break;
 196         res_size = i + 1;
 197         count = res_size;
 198       }
 199     else
 200       {
 201         res_size = op2_size;
 202
 203         /* Copy the part of OP2 that stretches above OP1, to RES.  */
 204         MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size, op2_size - op1_size);
 205         count = op1_size;
 206       }
 207
 208     if (res_size != 0)
 209       {
 210         /* Second loop computes the real result.  */
 211         if (LIKELY (count != 0))
 212           mpn_andn_n (res_ptr, op2_ptr, op1_ptr, count);
 213
 214         cy = mpn_add_1 (res_ptr, res_ptr, res_size, (mp_limb_t) 1);
 215         if (cy)
 216           {
 217             res_ptr[res_size] = cy;
 218             res_size++;
 219           }
 220       }
 221     else
 222       {
 223         res_ptr[0] = 1;
 224         res_size = 1;
 225       }
 226
 227     SIZ(res) = -res_size;
 228   }
 229   TMP_FREE;
 230 }