rts/gmp/mpz/mul.c

   1 /* mpz_mul -- Multiply two integers.
   2
   3 Copyright (C) 1991, 1993, 1994, 1996, 2000 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 Lesser General Public License as published by
   9 the Free Software Foundation; either version 2.1 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 Lesser General Public
  15 License for more details.
  16
  17 You should have received a copy of the GNU Lesser 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 <stdio.h> /* for NULL */
  23 #include "gmp.h"
  24 #include "gmp-impl.h"
  25 #ifdef BERKELEY_MP
  26 #include "mp.h"
  27 #endif
  28
  29 #ifndef BERKELEY_MP
  30 void
  31 #if __STDC__
  32 mpz_mul (mpz_ptr w, mpz_srcptr u, mpz_srcptr v)
  33 #else
  34 mpz_mul (w, u, v)
  35      mpz_ptr w;
  36      mpz_srcptr u;
  37      mpz_srcptr v;
  38 #endif
  39 #else /* BERKELEY_MP */
  40 void
  41 #if __STDC__
  42 mult (mpz_srcptr u, mpz_srcptr v, mpz_ptr w)
  43 #else
  44 mult (u, v, w)
  45      mpz_srcptr u;
  46      mpz_srcptr v;
  47      mpz_ptr w;
  48 #endif
  49 #endif /* BERKELEY_MP */
  50 {
  51   mp_size_t usize = u->_mp_size;
  52   mp_size_t vsize = v->_mp_size;
  53   mp_size_t wsize;
  54   mp_size_t sign_product;
  55   mp_ptr up, vp;
  56   mp_ptr wp;
  57   mp_ptr free_me = NULL;
  58   size_t free_me_size;
  59   mp_limb_t cy_limb;
  60   TMP_DECL (marker);
  61
  62   TMP_MARK (marker);
  63   sign_product = usize ^ vsize;
  64   usize = ABS (usize);
  65   vsize = ABS (vsize);
  66
  67   if (usize < vsize)
  68     {
  69       /* Swap U and V.  */
  70       {const __mpz_struct *t = u; u = v; v = t;}
  71       {mp_size_t t = usize; usize = vsize; vsize = t;}
  72     }
  73
  74   up = u->_mp_d;
  75   vp = v->_mp_d;
  76   wp = w->_mp_d;
  77
  78   /* Ensure W has space enough to store the result.  */
  79   wsize = usize + vsize;
  80   if (w->_mp_alloc < wsize)
  81     {
  82       if (wp == up || wp == vp)
  83         {
  84           free_me = wp;
  85           free_me_size = w->_mp_alloc;
  86         }
  87       else
  88         (*_mp_free_func) (wp, w->_mp_alloc * BYTES_PER_MP_LIMB);
  89
  90       w->_mp_alloc = wsize;
  91       wp = (mp_ptr) (*_mp_allocate_func) (wsize * BYTES_PER_MP_LIMB);
  92       w->_mp_d = wp;
  93     }
  94   else
  95     {
  96       /* Make U and V not overlap with W.  */
  97       if (wp == up)
  98         {
  99           /* W and U are identical.  Allocate temporary space for U.  */
 100           up = (mp_ptr) TMP_ALLOC (usize * BYTES_PER_MP_LIMB);
 101           /* Is V identical too?  Keep it identical with U.  */
 102           if (wp == vp)
 103             vp = up;
 104           /* Copy to the temporary space.  */
 105           MPN_COPY (up, wp, usize);
 106         }
 107       else if (wp == vp)
 108         {
 109           /* W and V are identical.  Allocate temporary space for V.  */
 110           vp = (mp_ptr) TMP_ALLOC (vsize * BYTES_PER_MP_LIMB);
 111           /* Copy to the temporary space.  */
 112           MPN_COPY (vp, wp, vsize);
 113         }
 114     }
 115
 116   if (vsize == 0)
 117     {
 118       wsize = 0;
 119     }
 120   else
 121     {
 122       cy_limb = mpn_mul (wp, up, usize, vp, vsize);
 123       wsize = usize + vsize;
 124       wsize -= cy_limb == 0;
 125     }
 126
 127   w->_mp_size = sign_product < 0 ? -wsize : wsize;
 128   if (free_me != NULL)
 129     (*_mp_free_func) (free_me, free_me_size * BYTES_PER_MP_LIMB);
 130   TMP_FREE (marker);
 131 }