contrib/libgmp/mpz/mul.c

   1 /* mpz_mul -- Multiply two integers.
   2
   3 Copyright (C) 1991, 1993, 1994, 1996 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 Library General Public License as published by
   9 the Free Software Foundation; either version 2 of the License, or (at your
  10 option) any later version.
  11
  12 The GNU MP Library is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Library General Public
  15 License for more details.
  16
  17 You should have received a copy of the GNU Library General Public License
  18 along with the GNU MP Library; see the file COPYING.LIB.  If not, write to
  19 the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  20 MA 02111-1307, USA. */
  21
  22 #include "gmp.h"
  23 #include "gmp-impl.h"
  24
  25 #ifndef BERKELEY_MP
  26 void
  27 #if __STDC__
  28 mpz_mul (mpz_ptr w, mpz_srcptr u, mpz_srcptr v)
  29 #else
  30 mpz_mul (w, u, v)
  31      mpz_ptr w;
  32      mpz_srcptr u;
  33      mpz_srcptr v;
  34 #endif
  35 #else /* BERKELEY_MP */
  36 void
  37 #if __STDC__
  38 mult (mpz_srcptr u, mpz_srcptr v, mpz_ptr w)
  39 #else
  40 mult (u, v, w)
  41      mpz_srcptr u;
  42      mpz_srcptr v;
  43      mpz_ptr w;
  44 #endif
  45 #endif /* BERKELEY_MP */
  46 {
  47   mp_size_t usize = u->_mp_size;
  48   mp_size_t vsize = v->_mp_size;
  49   mp_size_t wsize;
  50   mp_size_t sign_product;
  51   mp_ptr up, vp;
  52   mp_ptr wp;
  53   mp_ptr free_me = NULL;
  54   size_t free_me_size;
  55   mp_limb_t cy_limb;
  56   TMP_DECL (marker);
  57
  58   TMP_MARK (marker);
  59   sign_product = usize ^ vsize;
  60   usize = ABS (usize);
  61   vsize = ABS (vsize);
  62
  63   if (usize < vsize)
  64     {
  65       /* Swap U and V.  */
  66       {const __mpz_struct *t = u; u = v; v = t;}
  67       {mp_size_t t = usize; usize = vsize; vsize = t;}
  68     }
  69
  70   up = u->_mp_d;
  71   vp = v->_mp_d;
  72   wp = w->_mp_d;
  73
  74   /* Ensure W has space enough to store the result.  */
  75   wsize = usize + vsize;
  76   if (w->_mp_alloc < wsize)
  77     {
  78       if (wp == up || wp == vp)
  79         {
  80           free_me = wp;
  81           free_me_size = w->_mp_alloc;
  82         }
  83       else
  84         (*_mp_free_func) (wp, w->_mp_alloc * BYTES_PER_MP_LIMB);
  85
  86       w->_mp_alloc = wsize;
  87       wp = (mp_ptr) (*_mp_allocate_func) (wsize * BYTES_PER_MP_LIMB);
  88       w->_mp_d = wp;
  89     }
  90   else
  91     {
  92       /* Make U and V not overlap with W.  */
  93       if (wp == up)
  94         {
  95           /* W and U are identical.  Allocate temporary space for U.  */
  96           up = (mp_ptr) TMP_ALLOC (usize * BYTES_PER_MP_LIMB);
  97           /* Is V identical too?  Keep it identical with U.  */
  98           if (wp == vp)
  99             vp = up;
 100           /* Copy to the temporary space.  */
 101           MPN_COPY (up, wp, usize);
 102         }
 103       else if (wp == vp)
 104         {
 105           /* W and V are identical.  Allocate temporary space for V.  */
 106           vp = (mp_ptr) TMP_ALLOC (vsize * BYTES_PER_MP_LIMB);
 107           /* Copy to the temporary space.  */
 108           MPN_COPY (vp, wp, vsize);
 109         }
 110     }
 111
 112   if (vsize == 0)
 113     {
 114       wsize = 0;
 115     }
 116   else
 117     {
 118       cy_limb = mpn_mul (wp, up, usize, vp, vsize);
 119       wsize = usize + vsize;
 120       wsize -= cy_limb == 0;
 121     }
 122
 123   w->_mp_size = sign_product < 0 ? -wsize : wsize;
 124   if (free_me != NULL)
 125     (*_mp_free_func) (free_me, free_me_size * BYTES_PER_MP_LIMB);
 126   TMP_FREE (marker);
 127 }