1/* mpn_mul_basecase -- Internal routine to multiply two natural numbers
2   of length m and n.
3
4   THIS IS AN INTERNAL FUNCTION WITH A MUTABLE INTERFACE.  IT IS ONLY
5   SAFE TO REACH THIS FUNCTION THROUGH DOCUMENTED INTERFACES.
6
7
8Copyright 1991, 1992, 1993, 1994, 1996, 1997, 2000, 2001, 2002 Free Software
9Foundation, Inc.
10
11This file is part of the GNU MP Library.
12
13The GNU MP Library is free software; you can redistribute it and/or modify
14it under the terms of the GNU Lesser General Public License as published by
15the Free Software Foundation; either version 3 of the License, or (at your
16option) any later version.
17
18The GNU MP Library is distributed in the hope that it will be useful, but
19WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
20or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
21License for more details.
22
23You should have received a copy of the GNU Lesser General Public License
24along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
25
26#include "gmp.h"
27#include "gmp-impl.h"
28
29
30/* Multiply {up,usize} by {vp,vsize} and write the result to
31   {prodp,usize+vsize}.  Must have usize>=vsize.
32
33   Note that prodp gets usize+vsize limbs stored, even if the actual result
34   only needs usize+vsize-1.
35
36   There's no good reason to call here with vsize>=MUL_TOOM22_THRESHOLD.
37   Currently this is allowed, but it might not be in the future.
38
39   This is the most critical code for multiplication.  All multiplies rely
40   on this, both small and huge.  Small ones arrive here immediately, huge
41   ones arrive here as this is the base case for Karatsuba's recursive
42   algorithm.  */
43
44void
45mpn_mul_basecase (mp_ptr rp,
46		  mp_srcptr up, mp_size_t un,
47		  mp_srcptr vp, mp_size_t vn)
48{
49  ASSERT (un >= vn);
50  ASSERT (vn >= 1);
51  ASSERT (! MPN_OVERLAP_P (rp, un+vn, up, un));
52  ASSERT (! MPN_OVERLAP_P (rp, un+vn, vp, vn));
53
54  /* We first multiply by the low order limb (or depending on optional function
55     availability, limbs).  This result can be stored, not added, to rp.  We
56     also avoid a loop for zeroing this way.  */
57
58#if HAVE_NATIVE_mpn_mul_2
59  if (vn >= 2)
60    {
61      rp[un + 1] = mpn_mul_2 (rp, up, un, vp);
62      rp += 2, vp += 2, vn -= 2;
63    }
64  else
65    {
66      rp[un] = mpn_mul_1 (rp, up, un, vp[0]);
67      return;
68    }
69#else
70  rp[un] = mpn_mul_1 (rp, up, un, vp[0]);
71  rp += 1, vp += 1, vn -= 1;
72#endif
73
74  /* Now accumulate the product of up[] and the next higher limb (or depending
75     on optional function availability, limbs) from vp[].  */
76
77#define MAX_LEFT MP_SIZE_T_MAX	/* Used to simplify loops into if statements */
78
79
80#if HAVE_NATIVE_mpn_addmul_6
81  while (vn >= 6)
82    {
83      rp[un + 6 - 1] = mpn_addmul_6 (rp, up, un, vp);
84      if (MAX_LEFT == 6)
85	return;
86      rp += 6, vp += 6, vn -= 6;
87      if (MAX_LEFT < 2 * 6)
88	break;
89    }
90#undef MAX_LEFT
91#define MAX_LEFT (6 - 1)
92#endif
93
94#if HAVE_NATIVE_mpn_addmul_5
95  while (vn >= 5)
96    {
97      rp[un + 5 - 1] = mpn_addmul_5 (rp, up, un, vp);
98      if (MAX_LEFT == 5)
99	return;
100      rp += 5, vp += 5, vn -= 5;
101      if (MAX_LEFT < 2 * 5)
102	break;
103    }
104#undef MAX_LEFT
105#define MAX_LEFT (5 - 1)
106#endif
107
108#if HAVE_NATIVE_mpn_addmul_4
109  while (vn >= 4)
110    {
111      rp[un + 4 - 1] = mpn_addmul_4 (rp, up, un, vp);
112      if (MAX_LEFT == 4)
113	return;
114      rp += 4, vp += 4, vn -= 4;
115      if (MAX_LEFT < 2 * 4)
116	break;
117    }
118#undef MAX_LEFT
119#define MAX_LEFT (4 - 1)
120#endif
121
122#if HAVE_NATIVE_mpn_addmul_3
123  while (vn >= 3)
124    {
125      rp[un + 3 - 1] = mpn_addmul_3 (rp, up, un, vp);
126      if (MAX_LEFT == 3)
127	return;
128      rp += 3, vp += 3, vn -= 3;
129      if (MAX_LEFT < 2 * 3)
130	break;
131    }
132#undef MAX_LEFT
133#define MAX_LEFT (3 - 1)
134#endif
135
136#if HAVE_NATIVE_mpn_addmul_2
137  while (vn >= 2)
138    {
139      rp[un + 2 - 1] = mpn_addmul_2 (rp, up, un, vp);
140      if (MAX_LEFT == 2)
141	return;
142      rp += 2, vp += 2, vn -= 2;
143      if (MAX_LEFT < 2 * 2)
144	break;
145    }
146#undef MAX_LEFT
147#define MAX_LEFT (2 - 1)
148#endif
149
150  while (vn >= 1)
151    {
152      rp[un] = mpn_addmul_1 (rp, up, un, vp[0]);
153      if (MAX_LEFT == 1)
154	return;
155      rp += 1, vp += 1, vn -= 1;
156    }
157}
158