Home | History | Annotate | Line # | Download | only in mpz
mul.c revision 1.1.1.1.8.1 
      1 /* mpz_mul -- Multiply two integers.
      2 
      3 Copyright 1991, 1993, 1994, 1996, 2000, 2001, 2005, 2009, 2011, 2012 Free
      4 Software 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 <stdio.h> /* for NULL */
     22 #include "gmp.h"
     23 #include "gmp-impl.h"
     24 
     25 
     26 void
     27 mpz_mul (mpz_ptr w, mpz_srcptr u, mpz_srcptr v)
     28 {
     29   mp_size_t usize;
     30   mp_size_t vsize;
     31   mp_size_t wsize;
     32   mp_size_t sign_product;
     33   mp_ptr up, vp;
     34   mp_ptr wp;
     35   mp_ptr free_me;
     36   size_t free_me_size;
     37   mp_limb_t cy_limb;
     38   TMP_DECL;
     39 
     40   usize = SIZ (u);
     41   vsize = SIZ (v);
     42   sign_product = usize ^ vsize;
     43   usize = ABS (usize);
     44   vsize = ABS (vsize);
     45 
     46   if (usize < vsize)
     47     {
     48       MPZ_SRCPTR_SWAP (u, v);
     49       MP_SIZE_T_SWAP (usize, vsize);
     50     }
     51 
     52   if (vsize == 0)
     53     {
     54       SIZ (w) = 0;
     55       return;
     56     }
     57 
     58 #if HAVE_NATIVE_mpn_mul_2
     59   if (vsize <= 2)
     60     {
     61       wp = MPZ_REALLOC (w, usize+vsize);
     62       if (vsize == 1)
     63 	cy_limb = mpn_mul_1 (wp, PTR (u), usize, PTR (v)[0]);
     64       else
     65 	{
     66 	  cy_limb = mpn_mul_2 (wp, PTR (u), usize, PTR (v));
     67 	  usize++;
     68 	}
     69       wp[usize] = cy_limb;
     70       usize += (cy_limb != 0);
     71       SIZ (w) = (sign_product >= 0 ? usize : -usize);
     72       return;
     73     }
     74 #else
     75   if (vsize == 1)
     76     {
     77       wp = MPZ_REALLOC (w, usize+1);
     78       cy_limb = mpn_mul_1 (wp, PTR (u), usize, PTR (v)[0]);
     79       wp[usize] = cy_limb;
     80       usize += (cy_limb != 0);
     81       SIZ (w) = (sign_product >= 0 ? usize : -usize);
     82       return;
     83     }
     84 #endif
     85 
     86   TMP_MARK;
     87   free_me = NULL;
     88   up = PTR (u);
     89   vp = PTR (v);
     90   wp = PTR (w);
     91 
     92   /* Ensure W has space enough to store the result.  */
     93   wsize = usize + vsize;
     94   if (ALLOC (w) < wsize)
     95     {
     96       if (wp == up || wp == vp)
     97 	{
     98 	  free_me = wp;
     99 	  free_me_size = ALLOC (w);
    100 	}
    101       else
    102 	(*__gmp_free_func) (wp, ALLOC (w) * BYTES_PER_MP_LIMB);
    103 
    104       ALLOC (w) = wsize;
    105       wp = (mp_ptr) (*__gmp_allocate_func) (wsize * BYTES_PER_MP_LIMB);
    106       PTR (w) = wp;
    107     }
    108   else
    109     {
    110       /* Make U and V not overlap with W.  */
    111       if (wp == up)
    112 	{
    113 	  /* W and U are identical.  Allocate temporary space for U.  */
    114 	  up = TMP_ALLOC_LIMBS (usize);
    115 	  /* Is V identical too?  Keep it identical with U.  */
    116 	  if (wp == vp)
    117 	    vp = up;
    118 	  /* Copy to the temporary space.  */
    119 	  MPN_COPY (up, wp, usize);
    120 	}
    121       else if (wp == vp)
    122 	{
    123 	  /* W and V are identical.  Allocate temporary space for V.  */
    124 	  vp = TMP_ALLOC_LIMBS (vsize);
    125 	  /* Copy to the temporary space.  */
    126 	  MPN_COPY (vp, wp, vsize);
    127 	}
    128     }
    129 
    130   if (up == vp)
    131     {
    132       mpn_sqr (wp, up, usize);
    133       cy_limb = wp[wsize - 1];
    134     }
    135   else
    136     {
    137       cy_limb = mpn_mul (wp, up, usize, vp, vsize);
    138     }
    139 
    140   wsize -= cy_limb == 0;
    141 
    142   SIZ (w) = sign_product < 0 ? -wsize : wsize;
    143   if (free_me != NULL)
    144     (*__gmp_free_func) (free_me, free_me_size * BYTES_PER_MP_LIMB);
    145   TMP_FREE;
    146 }
    147