1/* mpn_mul -- Multiply two natural numbers.
2
3Copyright (C) 1991, 1993, 1994, 1996 Free Software Foundation, Inc.
4
5This file is part of the GNU MP Library.
6
7The GNU MP Library is free software; you can redistribute it and/or modify
8it under the terms of the GNU Lesser General Public License as published by
9the Free Software Foundation; either version 2.1 of the License, or (at your
10option) any later version.
11
12The GNU MP Library is distributed in the hope that it will be useful, but
13WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
15License for more details.
16
17You should have received a copy of the GNU Lesser General Public License
18along with the GNU MP Library; see the file COPYING.LIB.  If not, write to
19the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
20MA 02111-1307, USA. */
21
22#include "gmp.h"
23#include "gmp-impl.h"
24
25/* Multiply the natural numbers u (pointed to by UP, with USIZE limbs)
26   and v (pointed to by VP, with VSIZE limbs), and store the result at
27   PRODP.  USIZE + VSIZE limbs are always stored, but if the input
28   operands are normalized.  Return the most significant limb of the
29   result.
30
31   NOTE: The space pointed to by PRODP is overwritten before finished
32   with U and V, so overlap is an error.
33
34   Argument constraints:
35   1. USIZE >= VSIZE.
36   2. PRODP != UP and PRODP != VP, i.e. the destination
37      must be distinct from the multiplier and the multiplicand.  */
38
39/* If KARATSUBA_THRESHOLD is not already defined, define it to a
40   value which is good on most machines.  */
41#ifndef KARATSUBA_THRESHOLD
42#define KARATSUBA_THRESHOLD 32
43#endif
44
45mp_limb_t
46#if __STDC__
47mpn_mul (mp_ptr prodp,
48	 mp_srcptr up, mp_size_t usize,
49	 mp_srcptr vp, mp_size_t vsize)
50#else
51mpn_mul (prodp, up, usize, vp, vsize)
52     mp_ptr prodp;
53     mp_srcptr up;
54     mp_size_t usize;
55     mp_srcptr vp;
56     mp_size_t vsize;
57#endif
58{
59  mp_ptr prod_endp = prodp + usize + vsize - 1;
60  mp_limb_t cy;
61  mp_ptr tspace;
62  TMP_DECL (marker);
63
64  if (vsize < KARATSUBA_THRESHOLD)
65    {
66      /* Handle simple cases with traditional multiplication.
67
68	 This is the most critical code of the entire function.  All
69	 multiplies rely on this, both small and huge.  Small ones arrive
70	 here immediately.  Huge ones arrive here as this is the base case
71	 for Karatsuba's recursive algorithm below.  */
72      mp_size_t i;
73      mp_limb_t cy_limb;
74      mp_limb_t v_limb;
75
76      if (vsize == 0)
77	return 0;
78
79      /* Multiply by the first limb in V separately, as the result can be
80	 stored (not added) to PROD.  We also avoid a loop for zeroing.  */
81      v_limb = vp[0];
82      if (v_limb <= 1)
83	{
84	  if (v_limb == 1)
85	    MPN_COPY (prodp, up, usize);
86	  else
87	    MPN_ZERO (prodp, usize);
88	  cy_limb = 0;
89	}
90      else
91	cy_limb = mpn_mul_1 (prodp, up, usize, v_limb);
92
93      prodp[usize] = cy_limb;
94      prodp++;
95
96      /* For each iteration in the outer loop, multiply one limb from
97	 U with one limb from V, and add it to PROD.  */
98      for (i = 1; i < vsize; i++)
99	{
100	  v_limb = vp[i];
101	  if (v_limb <= 1)
102	    {
103	      cy_limb = 0;
104	      if (v_limb == 1)
105		cy_limb = mpn_add_n (prodp, prodp, up, usize);
106	    }
107	  else
108	    cy_limb = mpn_addmul_1 (prodp, up, usize, v_limb);
109
110	  prodp[usize] = cy_limb;
111	  prodp++;
112	}
113      return cy_limb;
114    }
115
116  TMP_MARK (marker);
117
118  tspace = (mp_ptr) TMP_ALLOC (2 * vsize * BYTES_PER_MP_LIMB);
119  MPN_MUL_N_RECURSE (prodp, up, vp, vsize, tspace);
120
121  prodp += vsize;
122  up += vsize;
123  usize -= vsize;
124  if (usize >= vsize)
125    {
126      mp_ptr tp = (mp_ptr) TMP_ALLOC (2 * vsize * BYTES_PER_MP_LIMB);
127      do
128	{
129	  MPN_MUL_N_RECURSE (tp, up, vp, vsize, tspace);
130	  cy = mpn_add_n (prodp, prodp, tp, vsize);
131	  mpn_add_1 (prodp + vsize, tp + vsize, vsize, cy);
132	  prodp += vsize;
133	  up += vsize;
134	  usize -= vsize;
135	}
136      while (usize >= vsize);
137    }
138
139  /* True: usize < vsize.  */
140
141  /* Make life simple: Recurse.  */
142
143  if (usize != 0)
144    {
145      mpn_mul (tspace, vp, vsize, up, usize);
146      cy = mpn_add_n (prodp, prodp, tspace, vsize);
147      mpn_add_1 (prodp + vsize, tspace + vsize, usize, cy);
148    }
149
150  TMP_FREE (marker);
151  return *prod_endp;
152}
153