contrib/gmp/mpz/xor.c

   1 /* mpz_xor -- Logical xor.
   2
   3 Copyright 1991, 1993, 1994, 1996, 1997, 2000, 2001, 2005 Free Software
   4 Foundation, 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 3 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.  If not, see http://www.gnu.org/licenses/.  */
  20
  21 #include "gmp.h"
  22 #include "gmp-impl.h"
  23
  24 void
  25 mpz_xor (mpz_ptr res, mpz_srcptr op1, mpz_srcptr op2)
  26 {
  27   mp_srcptr op1_ptr, op2_ptr;
  28   mp_size_t op1_size, op2_size;
  29   mp_ptr res_ptr;
  30   mp_size_t res_size, res_alloc;
  31   mp_size_t i;
  32   TMP_DECL;
  33
  34   TMP_MARK;
  35   op1_size = SIZ(op1);
  36   op2_size = SIZ(op2);
  37
  38   op1_ptr = PTR(op1);
  39   op2_ptr = PTR(op2);
  40   res_ptr = PTR(res);
  41
  42   if (op1_size >= 0)
  43     {
  44       if (op2_size >= 0)
  45         {
  46           if (op1_size >= op2_size)
  47             {
  48               if (ALLOC(res) < op1_size)
  49                 {
  50                   _mpz_realloc (res, op1_size);
  51                   /* No overlapping possible: op1_ptr = PTR(op1); */
  52                   op2_ptr = PTR(op2);
  53                   res_ptr = PTR(res);
  54                 }
  55
  56               if (res_ptr != op1_ptr)
  57                 MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size,
  58                           op1_size - op2_size);
  59               for (i = op2_size - 1; i >= 0; i--)
  60                 res_ptr[i] = op1_ptr[i] ^ op2_ptr[i];
  61               res_size = op1_size;
  62             }
  63           else
  64             {
  65               if (ALLOC(res) < op2_size)
  66                 {
  67                   _mpz_realloc (res, op2_size);
  68                   op1_ptr = PTR(op1);
  69                   /* No overlapping possible: op2_ptr = PTR(op2); */
  70                   res_ptr = PTR(res);
  71                 }
  72
  73               if (res_ptr != op2_ptr)
  74                 MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size,
  75                           op2_size - op1_size);
  76               for (i = op1_size - 1; i >= 0; i--)
  77                 res_ptr[i] = op1_ptr[i] ^ op2_ptr[i];
  78               res_size = op2_size;
  79             }
  80
  81           MPN_NORMALIZE (res_ptr, res_size);
  82           SIZ(res) = res_size;
  83           return;
  84         }
  85       else /* op2_size < 0 */
  86         {
  87           /* Fall through to the code at the end of the function.  */
  88         }
  89     }
  90   else
  91     {
  92       if (op2_size < 0)
  93         {
  94           mp_ptr opx;
  95
  96           /* Both operands are negative, the result will be positive.
  97               (-OP1) ^ (-OP2) =
  98              = ~(OP1 - 1) ^ ~(OP2 - 1) =
  99              = (OP1 - 1) ^ (OP2 - 1)  */
 100
 101           op1_size = -op1_size;
 102           op2_size = -op2_size;
 103
 104           /* Possible optimization: Decrease mpn_sub precision,
 105              as we won't use the entire res of both.  */
 106           opx = TMP_ALLOC_LIMBS (op1_size);
 107           mpn_sub_1 (opx, op1_ptr, op1_size, (mp_limb_t) 1);
 108           op1_ptr = opx;
 109
 110           opx = TMP_ALLOC_LIMBS (op2_size);
 111           mpn_sub_1 (opx, op2_ptr, op2_size, (mp_limb_t) 1);
 112           op2_ptr = opx;
 113
 114           res_alloc = MAX (op1_size, op2_size);
 115           if (ALLOC(res) < res_alloc)
 116             {
 117               _mpz_realloc (res, res_alloc);
 118               res_ptr = PTR(res);
 119               /* op1_ptr and op2_ptr point to temporary space.  */
 120             }
 121
 122           if (op1_size > op2_size)
 123             {
 124               MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size,
 125                         op1_size - op2_size);
 126               for (i = op2_size - 1; i >= 0; i--)
 127                 res_ptr[i] = op1_ptr[i] ^ op2_ptr[i];
 128               res_size = op1_size;
 129             }
 130           else
 131             {
 132               MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size,
 133                         op2_size - op1_size);
 134               for (i = op1_size - 1; i >= 0; i--)
 135                 res_ptr[i] = op1_ptr[i] ^ op2_ptr[i];
 136               res_size = op2_size;
 137             }
 138
 139           MPN_NORMALIZE (res_ptr, res_size);
 140           SIZ(res) = res_size;
 141           TMP_FREE;
 142           return;
 143         }
 144       else
 145         {
 146           /* We should compute -OP1 ^ OP2.  Swap OP1 and OP2 and fall
 147              through to the code that handles OP1 ^ -OP2.  */
 148           MPZ_SRCPTR_SWAP (op1, op2);
 149           MPN_SRCPTR_SWAP (op1_ptr,op1_size, op2_ptr,op2_size);
 150         }
 151     }
 152
 153   {
 154     mp_ptr opx;
 155     mp_limb_t cy;
 156
 157     /* Operand 2 negative, so will be the result.
 158        -(OP1 ^ (-OP2)) = -(OP1 ^ ~(OP2 - 1)) =
 159        = ~(OP1 ^ ~(OP2 - 1)) + 1 =
 160        = (OP1 ^ (OP2 - 1)) + 1      */
 161
 162     op2_size = -op2_size;
 163
 164     opx = TMP_ALLOC_LIMBS (op2_size);
 165     mpn_sub_1 (opx, op2_ptr, op2_size, (mp_limb_t) 1);
 166     op2_ptr = opx;
 167
 168     res_alloc = MAX (op1_size, op2_size) + 1;
 169     if (ALLOC(res) < res_alloc)
 170       {
 171         _mpz_realloc (res, res_alloc);
 172         op1_ptr = PTR(op1);
 173         /* op2_ptr points to temporary space.  */
 174         res_ptr = PTR(res);
 175       }
 176
 177     if (op1_size > op2_size)
 178       {
 179         MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size, op1_size - op2_size);
 180         for (i = op2_size - 1; i >= 0; i--)
 181           res_ptr[i] = op1_ptr[i] ^ op2_ptr[i];
 182         res_size = op1_size;
 183       }
 184     else
 185       {
 186         MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size, op2_size - op1_size);
 187         for (i = op1_size - 1; i >= 0; i--)
 188           res_ptr[i] = op1_ptr[i] ^ op2_ptr[i];
 189         res_size = op2_size;
 190       }
 191
 192     cy = mpn_add_1 (res_ptr, res_ptr, res_size, (mp_limb_t) 1);
 193     if (cy)
 194       {
 195         res_ptr[res_size] = cy;
 196         res_size++;
 197       }
 198
 199     MPN_NORMALIZE (res_ptr, res_size);
 200     SIZ(res) = -res_size;
 201     TMP_FREE;
 202   }
 203 }