ghc/rts/gmp/mpz/and.c

   1 /* mpz_and -- Logical and.
   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_and (mpz_ptr res, mpz_srcptr op1, mpz_srcptr op2)
  28 #else
  29 mpz_and (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           res_size = MIN (op1_size, op2_size);
  55           /* First loop finds the size of the result.  */
  56           for (i = res_size - 1; i >= 0; i--)
  57             if ((op1_ptr[i] & op2_ptr[i]) != 0)
  58               break;
  59           res_size = i + 1;
  60
  61           /* Handle allocation, now then we know exactly how much space is
  62              needed for the result.  */
  63           if (res->_mp_alloc < res_size)
  64             {
  65               _mpz_realloc (res, res_size);
  66               op1_ptr = op1->_mp_d;
  67               op2_ptr = op2->_mp_d;
  68               res_ptr = res->_mp_d;
  69             }
  70
  71           /* Second loop computes the real result.  */
  72           for (i = res_size - 1; i >= 0; i--)
  73             res_ptr[i] = op1_ptr[i] & op2_ptr[i];
  74
  75           res->_mp_size = res_size;
  76           return;
  77         }
  78       else /* op2_size < 0 */
  79         {
  80           /* Fall through to the code at the end of the function.  */
  81         }
  82     }
  83   else
  84     {
  85       if (op2_size < 0)
  86         {
  87           mp_ptr opx;
  88           mp_limb_t cy;
  89           mp_size_t res_alloc;
  90
  91           /* Both operands are negative, so will be the result.
  92              -((-OP1) & (-OP2)) = -(~(OP1 - 1) & ~(OP2 - 1)) =
  93              = ~(~(OP1 - 1) & ~(OP2 - 1)) + 1 =
  94              = ((OP1 - 1) | (OP2 - 1)) + 1      */
  95
  96           /* It might seem as we could end up with an (invalid) result with
  97              a leading zero-limb here when one of the operands is of the
  98              type 1,,0,,..,,.0.  But some analysis shows that we surely
  99              would get carry into the zero-limb in this situation...  */
 100
 101           op1_size = -op1_size;
 102           op2_size = -op2_size;
 103
 104           res_alloc = 1 + MAX (op1_size, op2_size);
 105
 106           opx = (mp_ptr) TMP_ALLOC (op1_size * BYTES_PER_MP_LIMB);
 107           mpn_sub_1 (opx, op1_ptr, op1_size, (mp_limb_t) 1);
 108           op1_ptr = opx;
 109
 110           opx = (mp_ptr) TMP_ALLOC (op2_size * BYTES_PER_MP_LIMB);
 111           mpn_sub_1 (opx, op2_ptr, op2_size, (mp_limb_t) 1);
 112           op2_ptr = opx;
 113
 114           if (res->_mp_alloc < res_alloc)
 115             {
 116               _mpz_realloc (res, res_alloc);
 117               res_ptr = res->_mp_d;
 118               /* Don't re-read OP1_PTR and OP2_PTR.  They point to
 119                  temporary space--never to the space RES->_mp_D used
 120                  to point to before reallocation.  */
 121             }
 122
 123           if (op1_size >= op2_size)
 124             {
 125               MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size,
 126                         op1_size - op2_size);
 127               for (i = op2_size - 1; i >= 0; i--)
 128                 res_ptr[i] = op1_ptr[i] | op2_ptr[i];
 129               res_size = op1_size;
 130             }
 131           else
 132             {
 133               MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size,
 134                         op2_size - op1_size);
 135               for (i = op1_size - 1; i >= 0; i--)
 136                 res_ptr[i] = op1_ptr[i] | op2_ptr[i];
 137               res_size = op2_size;
 138             }
 139
 140           cy = mpn_add_1 (res_ptr, res_ptr, res_size, (mp_limb_t) 1);
 141           if (cy)
 142             {
 143               res_ptr[res_size] = cy;
 144               res_size++;
 145             }
 146
 147           res->_mp_size = -res_size;
 148           TMP_FREE (marker);
 149           return;
 150         }
 151       else
 152         {
 153           /* We should compute -OP1 & OP2.  Swap OP1 and OP2 and fall
 154              through to the code that handles OP1 & -OP2.  */
 155           {mpz_srcptr t = op1; op1 = op2; op2 = t;}
 156           {mp_srcptr t = op1_ptr; op1_ptr = op2_ptr; op2_ptr = t;}
 157           {mp_size_t t = op1_size; op1_size = op2_size; op2_size = t;}
 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 }