and.c
上传用户:qaz666999
上传日期:2022-08-06
资源大小:2570k
文件大小:8k
源码类别:

数学计算

开发平台:

Unix_Linux

  1. /* mpz_and -- Logical and.
  2. Copyright 1991, 1993, 1994, 1996, 1997, 2000, 2001, 2003, 2005 Free Software
  3. Foundation, Inc.
  4. This file is part of the GNU MP Library.
  5. The GNU MP Library is free software; you can redistribute it and/or modify
  6. it under the terms of the GNU Lesser General Public License as published by
  7. the Free Software Foundation; either version 3 of the License, or (at your
  8. option) any later version.
  9. The GNU MP Library is distributed in the hope that it will be useful, but
  10. WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  11. or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  12. License for more details.
  13. You should have received a copy of the GNU Lesser General Public License
  14. along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
  15. #include "gmp.h"
  16. #include "gmp-impl.h"
  17. void
  18. mpz_and (mpz_ptr res, mpz_srcptr op1, mpz_srcptr op2)
  19. {
  20.   mp_srcptr op1_ptr, op2_ptr;
  21.   mp_size_t op1_size, op2_size;
  22.   mp_ptr res_ptr;
  23.   mp_size_t res_size;
  24.   mp_size_t i;
  25.   TMP_DECL;
  26.   TMP_MARK;
  27.   op1_size = SIZ(op1);
  28.   op2_size = SIZ(op2);
  29.   op1_ptr = PTR(op1);
  30.   op2_ptr = PTR(op2);
  31.   res_ptr = PTR(res);
  32.   if (op1_size >= 0)
  33.     {
  34.       if (op2_size >= 0)
  35. {
  36.   res_size = MIN (op1_size, op2_size);
  37.   /* First loop finds the size of the result.  */
  38.   for (i = res_size - 1; i >= 0; i--)
  39.     if ((op1_ptr[i] & op2_ptr[i]) != 0)
  40.       break;
  41.   res_size = i + 1;
  42.   /* Handle allocation, now then we know exactly how much space is
  43.      needed for the result.  */
  44.   if (UNLIKELY (ALLOC(res) < res_size))
  45.     {
  46.       _mpz_realloc (res, res_size);
  47.       res_ptr = PTR(res);
  48.       /* Don't re-read op1_ptr and op2_ptr.  Since res_size <=
  49.  MIN(op1_size, op2_size), we will not reach this code when op1
  50.  is identical to res or op2 is identical to res.  */
  51.     }
  52.   SIZ(res) = res_size;
  53.           if (LIKELY (res_size != 0))
  54.             mpn_and_n (res_ptr, op1_ptr, op2_ptr, res_size);
  55.   return;
  56. }
  57.       else /* op2_size < 0 */
  58. {
  59.   /* Fall through to the code at the end of the function.  */
  60. }
  61.     }
  62.   else
  63.     {
  64.       if (op2_size < 0)
  65. {
  66.   mp_ptr opx;
  67.   mp_limb_t cy;
  68.   mp_size_t res_alloc;
  69.   /* Both operands are negative, so will be the result.
  70.      -((-OP1) & (-OP2)) = -(~(OP1 - 1) & ~(OP2 - 1)) =
  71.      = ~(~(OP1 - 1) & ~(OP2 - 1)) + 1 =
  72.      = ((OP1 - 1) | (OP2 - 1)) + 1      */
  73.   /* It might seem as we could end up with an (invalid) result with
  74.      a leading zero-limb here when one of the operands is of the
  75.      type 1,,0,,..,,.0.  But some analysis shows that we surely
  76.      would get carry into the zero-limb in this situation...  */
  77.   op1_size = -op1_size;
  78.   op2_size = -op2_size;
  79.   res_alloc = 1 + MAX (op1_size, op2_size);
  80.   opx = TMP_ALLOC_LIMBS (op1_size);
  81.   mpn_sub_1 (opx, op1_ptr, op1_size, (mp_limb_t) 1);
  82.   op1_ptr = opx;
  83.   opx = TMP_ALLOC_LIMBS (op2_size);
  84.   mpn_sub_1 (opx, op2_ptr, op2_size, (mp_limb_t) 1);
  85.   op2_ptr = opx;
  86.   if (ALLOC(res) < res_alloc)
  87.     {
  88.       _mpz_realloc (res, res_alloc);
  89.       res_ptr = PTR(res);
  90.       /* Don't re-read OP1_PTR and OP2_PTR.  They point to temporary
  91.  space--never to the space PTR(res) used to point to before
  92.  reallocation.  */
  93.     }
  94.   if (op1_size >= op2_size)
  95.     {
  96.       MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size,
  97. op1_size - op2_size);
  98.       for (i = op2_size - 1; i >= 0; i--)
  99. res_ptr[i] = op1_ptr[i] | op2_ptr[i];
  100.       res_size = op1_size;
  101.     }
  102.   else
  103.     {
  104.       MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size,
  105. op2_size - op1_size);
  106.       for (i = op1_size - 1; i >= 0; i--)
  107. res_ptr[i] = op1_ptr[i] | op2_ptr[i];
  108.       res_size = op2_size;
  109.     }
  110.   cy = mpn_add_1 (res_ptr, res_ptr, res_size, (mp_limb_t) 1);
  111.   if (cy)
  112.     {
  113.       res_ptr[res_size] = cy;
  114.       res_size++;
  115.     }
  116.   SIZ(res) = -res_size;
  117.   TMP_FREE;
  118.   return;
  119. }
  120.       else
  121. {
  122.   /* We should compute -OP1 & OP2.  Swap OP1 and OP2 and fall
  123.      through to the code that handles OP1 & -OP2.  */
  124.           MPZ_SRCPTR_SWAP (op1, op2);
  125.           MPN_SRCPTR_SWAP (op1_ptr,op1_size, op2_ptr,op2_size);
  126. }
  127.     }
  128.   {
  129. #if ANDNEW
  130.     mp_size_t op2_lim;
  131.     mp_size_t count;
  132.     /* OP2 must be negated as with infinite precision.
  133.        Scan from the low end for a non-zero limb.  The first non-zero
  134.        limb is simply negated (two's complement).  Any subsequent
  135.        limbs are one's complemented.  Of course, we don't need to
  136.        handle more limbs than there are limbs in the other, positive
  137.        operand as the result for those limbs is going to become zero
  138.        anyway.  */
  139.     /* Scan for the least significant non-zero OP2 limb, and zero the
  140.        result meanwhile for those limb positions.  (We will surely
  141.        find a non-zero limb, so we can write the loop with one
  142.        termination condition only.)  */
  143.     for (i = 0; op2_ptr[i] == 0; i++)
  144.       res_ptr[i] = 0;
  145.     op2_lim = i;
  146.     op2_size = -op2_size;
  147.     if (op1_size <= op2_size)
  148.       {
  149. /* The ones-extended OP2 is >= than the zero-extended OP1.
  150.    RES_SIZE <= OP1_SIZE.  Find the exact size.  */
  151. for (i = op1_size - 1; i > op2_lim; i--)
  152.   if ((op1_ptr[i] & ~op2_ptr[i]) != 0)
  153.     break;
  154. res_size = i + 1;
  155. for (i = res_size - 1; i > op2_lim; i--)
  156.   res_ptr[i] = op1_ptr[i] & ~op2_ptr[i];
  157. res_ptr[op2_lim] = op1_ptr[op2_lim] & -op2_ptr[op2_lim];
  158. /* Yes, this *can* happen!  */
  159. MPN_NORMALIZE (res_ptr, res_size);
  160.       }
  161.     else
  162.       {
  163. /* The ones-extended OP2 is < than the zero-extended OP1.
  164.    RES_SIZE == OP1_SIZE, since OP1 is normalized.  */
  165. res_size = op1_size;
  166. MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size, op1_size - op2_size);
  167. for (i = op2_size - 1; i > op2_lim; i--)
  168.   res_ptr[i] = op1_ptr[i] & ~op2_ptr[i];
  169. res_ptr[op2_lim] = op1_ptr[op2_lim] & -op2_ptr[op2_lim];
  170.       }
  171.     SIZ(res) = res_size;
  172. #else
  173.     /* OP1 is positive and zero-extended,
  174.        OP2 is negative and ones-extended.
  175.        The result will be positive.
  176.        OP1 & -OP2 = OP1 & ~(OP2 - 1).  */
  177.     mp_ptr opx;
  178.     op2_size = -op2_size;
  179.     opx = TMP_ALLOC_LIMBS (op2_size);
  180.     mpn_sub_1 (opx, op2_ptr, op2_size, (mp_limb_t) 1);
  181.     op2_ptr = opx;
  182.     if (op1_size > op2_size)
  183.       {
  184. /* The result has the same size as OP1, since OP1 is normalized
  185.    and longer than the ones-extended OP2.  */
  186. res_size = op1_size;
  187. /* Handle allocation, now then we know exactly how much space is
  188.    needed for the result.  */
  189. if (ALLOC(res) < res_size)
  190.   {
  191.     _mpz_realloc (res, res_size);
  192.     res_ptr = PTR(res);
  193.     /* Don't re-read OP1_PTR or OP2_PTR.  Since res_size = op1_size,
  194.        we will not reach this code when op1 is identical to res.
  195.        OP2_PTR points to temporary space.  */
  196.   }
  197. MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size, res_size - op2_size);
  198. for (i = op2_size - 1; i >= 0; i--)
  199.   res_ptr[i] = op1_ptr[i] & ~op2_ptr[i];
  200. SIZ(res) = res_size;
  201.       }
  202.     else
  203.       {
  204. /* Find out the exact result size.  Ignore the high limbs of OP2,
  205.    OP1 is zero-extended and would make the result zero.  */
  206. for (i = op1_size - 1; i >= 0; i--)
  207.   if ((op1_ptr[i] & ~op2_ptr[i]) != 0)
  208.     break;
  209. res_size = i + 1;
  210. /* Handle allocation, now then we know exactly how much space is
  211.    needed for the result.  */
  212. if (ALLOC(res) < res_size)
  213.   {
  214.     _mpz_realloc (res, res_size);
  215.     res_ptr = PTR(res);
  216.     /* Don't re-read OP1_PTR.  Since res_size <= op1_size, we will
  217.        not reach this code when op1 is identical to res.  */
  218.     /* Don't re-read OP2_PTR.  It points to temporary space--never
  219.        to the space PTR(res) used to point to before reallocation.  */
  220.   }
  221. for (i = res_size - 1; i >= 0; i--)
  222.   res_ptr[i] = op1_ptr[i] & ~op2_ptr[i];
  223. SIZ(res) = res_size;
  224.       }
  225. #endif
  226.   }
  227.   TMP_FREE;
  228. }