ghc/rts/gmp/mpz/and.c

   1 /* mpz_and -- Logical and.
   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_and (mpz_ptr res, mpz_srcptr op1, mpz_srcptr op2)
  29 #else
  30 mpz_and (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           res_size = MIN (op1_size, op2_size);
  56           /* First loop finds the size of the result.  */
  57           for (i = res_size - 1; i >= 0; i--)
  58             if ((op1_ptr[i] & op2_ptr[i]) != 0)
  59               break;
  60           res_size = i + 1;
  61
  62           /* Handle allocation, now then we know exactly how much space is
  63              needed for the result.  */
  64           if (res->_mp_alloc < res_size)
  65             {
  66               _mpz_realloc (res, res_size);
  67               op1_ptr = op1->_mp_d;
  68               op2_ptr = op2->_mp_d;
  69               res_ptr = res->_mp_d;
  70             }
  71
  72           /* Second loop computes the real result.  */
  73           for (i = res_size - 1; i >= 0; i--)
  74             res_ptr[i] = op1_ptr[i] & op2_ptr[i];
  75
  76           res->_mp_size = res_size;
  77           return;
  78         }
  79       else /* op2_size < 0 */
  80         {
  81           /* Fall through to the code at the end of the function.  */
  82         }
  83     }
  84   else
  85     {
  86       if (op2_size < 0)
  87         {
  88           mp_ptr opx;
  89           mp_limb_t cy;
  90           mp_size_t res_alloc;
  91
  92           /* Both operands are negative, so will be the result.
  93              -((-OP1) & (-OP2)) = -(~(OP1 - 1) & ~(OP2 - 1)) =
  94              = ~(~(OP1 - 1) & ~(OP2 - 1)) + 1 =
  95              = ((OP1 - 1) | (OP2 - 1)) + 1      */
  96
  97           /* It might seem as we could end up with an (invalid) result with
  98              a leading zero-limb here when one of the operands is of the
  99              type 1,,0,,..,,.0.  But some analysis shows that we surely
 100              would get carry into the zero-limb in this situation...  */
 101
 102           op1_size = -op1_size;
 103           op2_size = -op2_size;
 104
 105           res_alloc = 1 + MAX (op1_size, op2_size);
 106
 107           opx = (mp_ptr) TMP_ALLOC (op1_size * BYTES_PER_MP_LIMB);
 108           mpn_sub_1 (opx, op1_ptr, op1_size, (mp_limb_t) 1);
 109           op1_ptr = opx;
 110
 111           opx = (mp_ptr) TMP_ALLOC (op2_size * BYTES_PER_MP_LIMB);
 112           mpn_sub_1 (opx, op2_ptr, op2_size, (mp_limb_t) 1);
 113           op2_ptr = opx;
 114
 115           if (res->_mp_alloc < res_alloc)
 116             {
 117               _mpz_realloc (res, res_alloc);
 118               res_ptr = res->_mp_d;
 119               /* Don't re-read OP1_PTR and OP2_PTR.  They point to
 120                  temporary space--never to the space RES->_mp_d used
 121                  to point to before reallocation.  */
 122             }
 123
 124           if (op1_size >= op2_size)
 125             {
 126               MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size,
 127                         op1_size - op2_size);
 128               for (i = op2_size - 1; i >= 0; i--)
 129                 res_ptr[i] = op1_ptr[i] | op2_ptr[i];
 130               res_size = op1_size;
 131             }
 132           else
 133             {
 134               MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size,
 135                         op2_size - op1_size);
 136               for (i = op1_size - 1; i >= 0; i--)
 137                 res_ptr[i] = op1_ptr[i] | op2_ptr[i];
 138               res_size = op2_size;
 139             }
 140
 141           cy = mpn_add_1 (res_ptr, res_ptr, res_size, (mp_limb_t) 1);
 142           if (cy)
 143             {
 144               res_ptr[res_size] = cy;
 145               res_size++;
 146             }
 147
 148           res->_mp_size = -res_size;
 149           TMP_FREE (marker);
 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   {
 163 #if ANDNEW
 164     mp_size_t op2_lim;
 165     mp_size_t count;
 166
 167     /* OP2 must be negated as with infinite precision.
 168
 169        Scan from the low end for a non-zero limb.  The first non-zero
 170        limb is simply negated (two's complement).  Any subsequent
 171        limbs are one's complemented.  Of course, we don't need to
 172        handle more limbs than there are limbs in the other, positive
 173        operand as the result for those limbs is going to become zero
 174        anyway.  */
 175
 176     /* Scan for the least significant non-zero OP2 limb, and zero the
 177        result meanwhile for those limb positions.  (We will surely
 178        find a non-zero limb, so we can write the loop with one
 179        termination condition only.)  */
 180     for (i = 0; op2_ptr[i] == 0; i++)
 181       res_ptr[i] = 0;
 182     op2_lim = i;
 183
 184     op2_size = -op2_size;
 185
 186     if (op1_size <= op2_size)
 187       {
 188         /* The ones-extended OP2 is >= than the zero-extended OP1.
 189            RES_SIZE <= OP1_SIZE.  Find the exact size.  */
 190         for (i = op1_size - 1; i > op2_lim; i--)
 191           if ((op1_ptr[i] & ~op2_ptr[i]) != 0)
 192             break;
 193         res_size = i + 1;
 194         for (i = res_size - 1; i > op2_lim; i--)
 195           res_ptr[i] = op1_ptr[i] & ~op2_ptr[i];
 196         res_ptr[op2_lim] = op1_ptr[op2_lim] & -op2_ptr[op2_lim];
 197         /* Yes, this *can* happen!  */
 198         MPN_NORMALIZE (res_ptr, res_size);
 199       }
 200     else
 201       {
 202         /* The ones-extended OP2 is < than the zero-extended OP1.
 203            RES_SIZE == OP1_SIZE, since OP1 is normalized.  */
 204         res_size = op1_size;
 205         MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size, op1_size - op2_size);
 206         for (i = op2_size - 1; i > op2_lim; i--)
 207           res_ptr[i] = op1_ptr[i] & ~op2_ptr[i];
 208         res_ptr[op2_lim] = op1_ptr[op2_lim] & -op2_ptr[op2_lim];
 209       }
 210
 211     res->_mp_size = res_size;
 212 #else
 213
 214     /* OP1 is positive and zero-extended,
 215        OP2 is negative and ones-extended.
 216        The result will be positive.
 217        OP1 & -OP2 = OP1 & ~(OP2 - 1).  */
 218
 219     mp_ptr opx;
 220
 221     op2_size = -op2_size;
 222     opx = (mp_ptr) TMP_ALLOC (op2_size * BYTES_PER_MP_LIMB);
 223     mpn_sub_1 (opx, op2_ptr, op2_size, (mp_limb_t) 1);
 224     op2_ptr = opx;
 225
 226     if (op1_size > op2_size)
 227       {
 228         /* The result has the same size as OP1, since OP1 is normalized
 229            and longer than the ones-extended OP2.  */
 230         res_size = op1_size;
 231
 232         /* Handle allocation, now then we know exactly how much space is
 233            needed for the result.  */
 234         if (res->_mp_alloc < res_size)
 235           {
 236             _mpz_realloc (res, res_size);
 237             res_ptr = res->_mp_d;
 238             op1_ptr = op1->_mp_d;
 239             /* Don't re-read OP2_PTR.  It points to temporary space--never
 240                to the space RES->_mp_d used to point to before reallocation.  */
 241           }
 242
 243         MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size,
 244                   res_size - op2_size);
 245         for (i = op2_size - 1; i >= 0; i--)
 246           res_ptr[i] = op1_ptr[i] & ~op2_ptr[i];
 247
 248         res->_mp_size = res_size;
 249       }
 250     else
 251       {
 252         /* Find out the exact result size.  Ignore the high limbs of OP2,
 253            OP1 is zero-extended and would make the result zero.  */
 254         for (i = op1_size - 1; i >= 0; i--)
 255           if ((op1_ptr[i] & ~op2_ptr[i]) != 0)
 256             break;
 257         res_size = i + 1;
 258
 259         /* Handle allocation, now then we know exactly how much space is
 260            needed for the result.  */
 261         if (res->_mp_alloc < res_size)
 262           {
 263             _mpz_realloc (res, res_size);
 264             res_ptr = res->_mp_d;
 265             op1_ptr = op1->_mp_d;
 266             /* Don't re-read OP2_PTR.  It points to temporary space--never
 267                to the space RES->_mp_d used to point to before reallocation.  */
 268           }
 269
 270         for (i = res_size - 1; i >= 0; i--)
 271           res_ptr[i] = op1_ptr[i] & ~op2_ptr[i];
 272
 273         res->_mp_size = res_size;
 274       }
 275 #endif
 276   }
 277   TMP_FREE (marker);
 278 }