ghc/runtime/gmp/mpz_ior.c

   1 /* mpz_ior -- Logical inclusive or.
   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_ior (MP_INT *res, const MP_INT *op1, const MP_INT *op2)
  30 #else
  31 mpz_ior (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           if (op1_size >= op2_size)
  55             {
  56               if (res->alloc < op1_size)
  57                 {
  58                   _mpz_realloc (res, op1_size);
  59                   op1_ptr = op1->d;
  60                   op2_ptr = op2->d;
  61                   res_ptr = res->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->alloc < op2_size)
  74                 {
  75                   _mpz_realloc (res, op2_size);
  76                   op1_ptr = op1->d;
  77                   op2_ptr = op2->d;
  78                   res_ptr = res->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->size = res_size;
  90           return;
  91         }
  92       else /* op2_size < 0 */
  93         /* Fall through to the code at the end of the function.  */
  94         ;
  95     }
  96   else
  97     {
  98       if (op2_size < 0)
  99         {
 100           mp_ptr opx;
 101           mp_limb cy;
 102           mp_limb one = 1;
 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) alloca (op1_size * BYTES_PER_MP_LIMB);
 117           op1_size += mpn_sub (opx, op1_ptr, op1_size, &one, 1);
 118           op1_ptr = opx;
 119
 120           opx = (mp_ptr) alloca (op2_size * BYTES_PER_MP_LIMB);
 121           op2_size += mpn_sub (opx, op2_ptr, op2_size, &one, 1);
 122           op2_ptr = opx;
 123
 124           if (res->alloc < res_size)
 125             {
 126               _mpz_realloc (res, res_size);
 127               res_ptr = res->d;
 128               /* Don't re-read OP1_PTR and OP2_PTR.  They point to
 129                  temporary space--never to the space RES->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           /* Second loop computes the real result.  */
 140           for (i = res_size - 1; i >= 0; i--)
 141             res_ptr[i] = op1_ptr[i] & op2_ptr[i];
 142
 143           if (res_size != 0)
 144             {
 145               cy = mpn_add (res_ptr, res_ptr, res_size, &one, 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->size = -res_size;
 159           return;
 160         }
 161       else
 162         {
 163           /* We should compute -OP1 | OP2.  Swap OP1 and OP2 and fall
 164              through to the code that handles OP1 | -OP2.  */
 165           {const MP_INT *t = op1; op1 = op2; op2 = t;}
 166           {mp_srcptr t = op1_ptr; op1_ptr = op2_ptr; op2_ptr = t;}
 167           {mp_size t = op1_size; op1_size = op2_size; op2_size = t;}
 168         }
 169     }
 170
 171   {
 172     mp_ptr opx;
 173     mp_limb cy;
 174     mp_limb one = 1;
 175     mp_size res_alloc;
 176
 177     /* Operand 2 negative, so will be the result.
 178        -(OP1 | (-OP2)) = -(OP1 | ~(OP2 - 1)) =
 179        = ~(OP1 | ~(OP2 - 1)) + 1 =
 180        = (~OP1 & (OP2 - 1)) + 1      */
 181
 182     op2_size = -op2_size;
 183
 184     res_alloc = op2_size;
 185
 186     opx = (mp_ptr) alloca (op2_size * BYTES_PER_MP_LIMB);
 187     op2_size += mpn_sub (opx, op2_ptr, op2_size, &one, 1);
 188     op2_ptr = opx;
 189
 190     if (res->alloc < res_alloc)
 191       {
 192         _mpz_realloc (res, res_alloc);
 193         op1_ptr = op1->d;
 194         res_ptr = res->d;
 195         /* Don't re-read OP2_PTR.  It points to temporary space--never
 196            to the space RES->D used to point to before reallocation.  */
 197       }
 198
 199     if (op1_size >= op2_size)
 200       {
 201         /* We can just ignore the part of OP1 that stretches above OP2,
 202            because the result limbs are zero there.  */
 203
 204         /* First loop finds the size of the result.  */
 205         for (i = op2_size - 1; i >= 0; i--)
 206           if ((~op1_ptr[i] & op2_ptr[i]) != 0)
 207             break;
 208         res_size = i + 1;
 209       }
 210     else
 211       {
 212         res_size = op2_size;
 213
 214         /* Copy the part of OP2 that stretches above OP1, to RES.  */
 215         MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size,
 216                   op2_size - op1_size);
 217       }
 218
 219     /* Second loop computes the real result.  */
 220     for (i = res_size - 1; i >= 0; i--)
 221       res_ptr[i] = ~op1_ptr[i] & op2_ptr[i];
 222
 223     if (res_size != 0)
 224       {
 225         cy = mpn_add (res_ptr, res_ptr, res_size, &one, 1);
 226         if (cy)
 227           {
 228             res_ptr[res_size] = cy;
 229             res_size++;
 230           }
 231       }
 232     else
 233       {
 234         res_ptr[0] = 1;
 235         res_size = 1;
 236       }
 237
 238     res->size = -res_size;
 239     alloca (0);
 240     return;
 241   }
 242 }