rts/gmp/mpz/xor.c

   1 /* mpz_xor -- Logical xor.
   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_xor (mpz_ptr res, mpz_srcptr op1, mpz_srcptr op2)
  29 #else
  30 mpz_xor (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, res_alloc;
  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           if (op1_size >= op2_size)
  56             {
  57               if (res->_mp_alloc < op1_size)
  58                 {
  59                   _mpz_realloc (res, op1_size);
  60                   op1_ptr = op1->_mp_d;
  61                   op2_ptr = op2->_mp_d;
  62                   res_ptr = res->_mp_d;
  63                 }
  64
  65               if (res_ptr != op1_ptr)
  66                 MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size,
  67                           op1_size - op2_size);
  68               for (i = op2_size - 1; i >= 0; i--)
  69                 res_ptr[i] = op1_ptr[i] ^ op2_ptr[i];
  70               res_size = op1_size;
  71             }
  72           else
  73             {
  74               if (res->_mp_alloc < op2_size)
  75                 {
  76                   _mpz_realloc (res, op2_size);
  77                   op1_ptr = op1->_mp_d;
  78                   op2_ptr = op2->_mp_d;
  79                   res_ptr = res->_mp_d;
  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               for (i = op1_size - 1; i >= 0; i--)
  86                 res_ptr[i] = op1_ptr[i] ^ op2_ptr[i];
  87               res_size = op2_size;
  88             }
  89
  90           MPN_NORMALIZE (res_ptr, res_size);
  91           res->_mp_size = res_size;
  92           return;
  93         }
  94       else /* op2_size < 0 */
  95         {
  96           /* Fall through to the code at the end of the function.  */
  97         }
  98     }
  99   else
 100     {
 101       if (op2_size < 0)
 102         {
 103           mp_ptr opx;
 104           mp_limb_t cy;
 105
 106           /* Both operands are negative, the result will be positive.
 107               (-OP1) ^ (-OP2) =
 108              = ~(OP1 - 1) ^ ~(OP2 - 1) =
 109              = (OP1 - 1) ^ (OP2 - 1)  */
 110
 111           op1_size = -op1_size;
 112           op2_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) TMP_ALLOC (op1_size * BYTES_PER_MP_LIMB);
 117           mpn_sub_1 (opx, op1_ptr, op1_size, (mp_limb_t) 1);
 118           op1_ptr = opx;
 119
 120           opx = (mp_ptr) TMP_ALLOC (op2_size * BYTES_PER_MP_LIMB);
 121           mpn_sub_1 (opx, op2_ptr, op2_size, (mp_limb_t) 1);
 122           op2_ptr = opx;
 123
 124           res_alloc = MAX (op1_size, op2_size);
 125           if (res->_mp_alloc < res_alloc)
 126             {
 127               _mpz_realloc (res, res_alloc);
 128               res_ptr = res->_mp_d;
 129               /* Don't re-read OP1_PTR and OP2_PTR.  They point to
 130                  temporary space--never to the space RES->_mp_d used
 131                  to point to before reallocation.  */
 132             }
 133
 134           if (op1_size > op2_size)
 135             {
 136               MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size,
 137                         op1_size - op2_size);
 138               for (i = op2_size - 1; i >= 0; i--)
 139                 res_ptr[i] = op1_ptr[i] ^ op2_ptr[i];
 140               res_size = op1_size;
 141             }
 142           else
 143             {
 144               MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size,
 145                         op2_size - op1_size);
 146               for (i = op1_size - 1; i >= 0; i--)
 147                 res_ptr[i] = op1_ptr[i] ^ op2_ptr[i];
 148               res_size = op2_size;
 149             }
 150
 151           MPN_NORMALIZE (res_ptr, res_size);
 152           res->_mp_size = res_size;
 153           TMP_FREE (marker);
 154           return;
 155         }
 156       else
 157         {
 158           /* We should compute -OP1 ^ OP2.  Swap OP1 and OP2 and fall
 159              through to the code that handles OP1 ^ -OP2.  */
 160           MPZ_SRCPTR_SWAP (op1, op2);
 161           MPN_SRCPTR_SWAP (op1_ptr,op1_size, op2_ptr,op2_size);
 162         }
 163     }
 164
 165   {
 166     mp_ptr opx;
 167     mp_limb_t cy;
 168     mp_size_t count;
 169
 170     /* Operand 2 negative, so will be the result.
 171        -(OP1 ^ (-OP2)) = -(OP1 ^ ~(OP2 - 1)) =
 172        = ~(OP1 ^ ~(OP2 - 1)) + 1 =
 173        = (OP1 ^ (OP2 - 1)) + 1      */
 174
 175     op2_size = -op2_size;
 176
 177     opx = (mp_ptr) TMP_ALLOC (op2_size * BYTES_PER_MP_LIMB);
 178     mpn_sub_1 (opx, op2_ptr, op2_size, (mp_limb_t) 1);
 179     op2_ptr = opx;
 180
 181     res_alloc = MAX (op1_size, op2_size) + 1;
 182     if (res->_mp_alloc < res_alloc)
 183       {
 184         _mpz_realloc (res, res_alloc);
 185         op1_ptr = op1->_mp_d;
 186         res_ptr = res->_mp_d;
 187         /* Don't re-read OP2_PTR.  It points to temporary space--never
 188            to the space RES->_mp_d used to point to before reallocation.  */
 189       }
 190
 191     if (op1_size > op2_size)
 192       {
 193         MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size, op1_size - op2_size);
 194         for (i = op2_size - 1; i >= 0; i--)
 195           res_ptr[i] = op1_ptr[i] ^ op2_ptr[i];
 196         res_size = op1_size;
 197       }
 198     else
 199       {
 200         MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size, op2_size - op1_size);
 201         for (i = op1_size - 1; i >= 0; i--)
 202           res_ptr[i] = op1_ptr[i] ^ op2_ptr[i];
 203         res_size = op2_size;
 204       }
 205
 206     cy = mpn_add_1 (res_ptr, res_ptr, res_size, (mp_limb_t) 1);
 207     if (cy)
 208       {
 209         res_ptr[res_size] = cy;
 210         res_size++;
 211       }
 212
 213     MPN_NORMALIZE (res_ptr, res_size);
 214     res->_mp_size = -res_size;
 215     TMP_FREE (marker);
 216   }
 217 }