ghc/runtime/gmp/mpz_and.c

   1 /* mpz_and -- Logical and.
   2
   3 Copyright (C) 1991 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 General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 The GNU MP Library is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with the GNU MP Library; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  20
  21 #include "gmp.h"
  22 #include "gmp-impl.h"
  23
  24 #define min(l,o) ((l) < (o) ? (l) : (o))
  25 #define max(h,i) ((h) > (i) ? (h) : (i))
  26
  27 void
  28 #ifdef __STDC__
  29 mpz_and (MP_INT *res, const MP_INT *op1, const MP_INT *op2)
  30 #else
  31 mpz_and (res, op1, op2)
  32      MP_INT *res;
  33      const MP_INT *op1;
  34      const MP_INT *op2;
  35 #endif
  36 {
  37   mp_srcptr op1_ptr, op2_ptr;
  38   mp_size op1_size, op2_size;
  39   mp_ptr res_ptr;
  40   mp_size res_size;
  41   mp_size i;
  42
  43   op1_size = op1->size;
  44   op2_size = op2->size;
  45
  46   op1_ptr = op1->d;
  47   op2_ptr = op2->d;
  48   res_ptr = res->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 when we know exactly how much space is
  62              needed for the result.  */
  63           if (res->alloc < res_size)
  64             {
  65               _mpz_realloc (res, res_size);
  66               op1_ptr = op1->d;
  67               op2_ptr = op2->d;
  68               res_ptr = res->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->size = res_size;
  76           return;
  77         }
  78       else /* op2_size < 0 */
  79         /* Fall through to the code at the end of the function.  */
  80         ;
  81     }
  82   else
  83     {
  84       if (op2_size < 0)
  85         {
  86           mp_ptr opx;
  87           mp_limb cy;
  88           mp_limb one = 1;
  89           mp_size 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           op1_size = -op1_size;
  97           op2_size = -op2_size;
  98
  99           res_alloc = 1 + max (op1_size, op2_size);
 100
 101           opx = (mp_ptr) alloca (op1_size * BYTES_PER_MP_LIMB);
 102           op1_size += mpn_sub (opx, op1_ptr, op1_size, &one, 1);
 103           op1_ptr = opx;
 104
 105           opx = (mp_ptr) alloca (op2_size * BYTES_PER_MP_LIMB);
 106           op2_size += mpn_sub (opx, op2_ptr, op2_size, &one, 1);
 107           op2_ptr = opx;
 108
 109           if (res->alloc < res_alloc)
 110             {
 111               _mpz_realloc (res, res_alloc);
 112               res_ptr = res->d;
 113               /* Don't re-read OP1_PTR and OP2_PTR.  They point to
 114                  temporary space--never to the space RES->D used
 115                  to point to before reallocation.  */
 116             }
 117
 118           if (op1_size >= op2_size)
 119             {
 120               MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size,
 121                         op1_size - op2_size);
 122               for (i = op2_size - 1; i >= 0; i--)
 123                 res_ptr[i] = op1_ptr[i] | op2_ptr[i];
 124               res_size = op1_size;
 125             }
 126           else
 127             {
 128               MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size,
 129                         op2_size - op1_size);
 130               for (i = op1_size - 1; i >= 0; i--)
 131                 res_ptr[i] = op1_ptr[i] | op2_ptr[i];
 132               res_size = op2_size;
 133             }
 134
 135           if (res_size != 0)
 136             {
 137               cy = mpn_add (res_ptr, res_ptr, res_size, &one, 1);
 138               if (cy)
 139                 {
 140                   res_ptr[res_size] = cy;
 141                   res_size++;
 142                 }
 143             }
 144           else
 145             {
 146               res_ptr[0] = 1;
 147               res_size = 1;
 148             }
 149
 150           res->size = -res_size;
 151           return;
 152         }
 153       else
 154         {
 155           /* We should compute -OP1 & OP2.  Swap OP1 and OP2 and fall
 156              through to the code that handles OP1 & -OP2.  */
 157           {const MP_INT *t = op1; op1 = op2; op2 = t;}
 158           {mp_srcptr t = op1_ptr; op1_ptr = op2_ptr; op2_ptr = t;}
 159           {mp_size t = op1_size; op1_size = op2_size; op2_size = t;}
 160         }
 161
 162     }
 163
 164   {
 165 #if 0
 166     mp_size op2_lim;
 167
 168     /* OP2 must be negated as with infinite precision.
 169
 170        Scan from the low end for a non-zero limb.  The first non-zero
 171        limb is simply negated (two's complement).  Any subsequent
 172        limbs are one's complemented.  Of course, we don't need to
 173        handle more limbs than there are limbs in the other, positive
 174        operand as the result for those limbs is going to become zero
 175        anyway.  */
 176
 177     /* Scan for the least significant. non-zero OP2 limb, and zero the
 178        result meanwhile for those limb positions.  (We will surely
 179        find a non-zero limb, so we can write the loop with one
 180        termination condition only.)  */
 181     for (i = 0; op2_ptr[i] == 0; i++)
 182       res_ptr[i] = 0;
 183     op2_lim = i;
 184
 185     op2_size = -op2_size;
 186
 187     if (op1_size <= op2_size)
 188       {
 189         /* The ones-extended OP2 is >= than the zero-extended OP1.
 190            RES_SIZE <= OP1_SIZE.  Find the exact size.  */
 191         for (i = op1_size - 1; i > op2_lim; i--)
 192           if ((op1_ptr[i] & ~op2_ptr[i]) != 0)
 193             break;
 194         res_size = i + 1;
 195       }
 196     else
 197       {
 198         /* The ones-extended OP2 is < than the zero-extended OP1.
 199            RES_SIZE == OP1_SIZE, since OP1 is normalized.  */
 200         res_size = op1_size;
 201       }
 202 #endif
 203
 204     /* OP1 is positive and zero-extended,
 205        OP2 is negative and ones-extended.
 206        The result will be positive.
 207        OP1 & -OP2 = OP1 & ~(OP2 - 1).  */
 208
 209     mp_ptr opx;
 210     const mp_limb one = 1;
 211
 212     op2_size = -op2_size;
 213     opx = (mp_ptr) alloca (op2_size * BYTES_PER_MP_LIMB);
 214     op2_size += mpn_sub (opx, op2_ptr, op2_size, &one, 1);
 215     op2_ptr = opx;
 216
 217     if (op1_size > op2_size)
 218       {
 219         /* The result has the same size as OP1, since OP1 is normalized
 220            and longer than the ones-extended OP2.  */
 221         res_size = op1_size;
 222
 223         /* Handle allocation, now when we know exactly how much space is
 224            needed for the result.  */
 225         if (res->alloc < res_size)
 226           {
 227             _mpz_realloc (res, res_size);
 228             res_ptr = res->d;
 229             op1_ptr = op1->d;
 230             /* Don't re-read OP2_PTR.  It points to temporary space--never
 231                to the space RES->D used to point to before reallocation.  */
 232           }
 233
 234         MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size,
 235                   res_size - op2_size);
 236         for (i = op2_size - 1; i >= 0; i--)
 237           res_ptr[i] = op1_ptr[i] & ~op2_ptr[i];
 238
 239         res->size = res_size;
 240       }
 241     else
 242       {
 243         /* Find out the exact result size.  Ignore the high limbs of OP2,
 244            OP1 is zero-extended and would make the result zero.  */
 245         for (i = op1_size - 1; i >= 0; i--)
 246           if ((op1_ptr[i] & ~op2_ptr[i]) != 0)
 247             break;
 248         res_size = i + 1;
 249
 250         /* Handle allocation, now when we know exactly how much space is
 251            needed for the result.  */
 252         if (res->alloc < res_size)
 253           {
 254             _mpz_realloc (res, res_size);
 255             res_ptr = res->d;
 256             op1_ptr = op1->d;
 257             /* Don't re-read OP2_PTR.  It points to temporary space--never
 258                to the space RES->D used to point to before reallocation.  */
 259           }
 260
 261         for (i = res_size - 1; i >= 0; i--)
 262           res_ptr[i] = op1_ptr[i] & ~op2_ptr[i];
 263
 264         res->size = res_size;
 265       }
 266   }
 267 }