1/* mpn_mul_n -- multiply natural numbers.
2
3Copyright 1991, 1993, 1994, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003,
42005, 2008, 2009 Free Software Foundation, Inc.
5
6This file is part of the GNU MP Library.
7
8The GNU MP Library is free software; you can redistribute it and/or modify
9it under the terms of the GNU Lesser General Public License as published by
10the Free Software Foundation; either version 3 of the License, or (at your
11option) any later version.
12
13The GNU MP Library is distributed in the hope that it will be useful, but
14WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
16License for more details.
17
18You should have received a copy of the GNU Lesser General Public License
19along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
20
21#include "gmp.h"
22#include "gmp-impl.h"
23#include "longlong.h"
24
25void
26mpn_mul_n (mp_ptr p, mp_srcptr a, mp_srcptr b, mp_size_t n)
27{
28  ASSERT (n >= 1);
29  ASSERT (! MPN_OVERLAP_P (p, 2 * n, a, n));
30  ASSERT (! MPN_OVERLAP_P (p, 2 * n, b, n));
31
32  if (BELOW_THRESHOLD (n, MUL_TOOM22_THRESHOLD))
33    {
34      mpn_mul_basecase (p, a, n, b, n);
35    }
36  else if (BELOW_THRESHOLD (n, MUL_TOOM33_THRESHOLD))
37    {
38      /* Allocate workspace of fixed size on stack: fast! */
39      mp_limb_t ws[mpn_toom22_mul_itch (MUL_TOOM33_THRESHOLD_LIMIT-1,
40					MUL_TOOM33_THRESHOLD_LIMIT-1)];
41      ASSERT (MUL_TOOM33_THRESHOLD <= MUL_TOOM33_THRESHOLD_LIMIT);
42      mpn_toom22_mul (p, a, n, b, n, ws);
43    }
44  else if (BELOW_THRESHOLD (n, MUL_TOOM44_THRESHOLD))
45    {
46      mp_ptr ws;
47      TMP_SDECL;
48      TMP_SMARK;
49      ws = TMP_SALLOC_LIMBS (mpn_toom33_mul_itch (n, n));
50      mpn_toom33_mul (p, a, n, b, n, ws);
51      TMP_SFREE;
52    }
53  else if (BELOW_THRESHOLD (n, MUL_TOOM6H_THRESHOLD))
54    {
55      mp_ptr ws;
56      TMP_SDECL;
57      TMP_SMARK;
58      ws = TMP_SALLOC_LIMBS (mpn_toom44_mul_itch (n, n));
59      mpn_toom44_mul (p, a, n, b, n, ws);
60      TMP_SFREE;
61    }
62  else if (BELOW_THRESHOLD (n, MUL_TOOM8H_THRESHOLD))
63    {
64      mp_ptr ws;
65      TMP_SDECL;
66      TMP_SMARK;
67      ws = TMP_SALLOC_LIMBS (mpn_toom6_mul_n_itch (n));
68      mpn_toom6h_mul (p, a, n, b, n, ws);
69      TMP_SFREE;
70    }
71  else if (BELOW_THRESHOLD (n, MUL_FFT_THRESHOLD))
72    {
73      mp_ptr ws;
74      TMP_DECL;
75      TMP_MARK;
76      ws = TMP_ALLOC_LIMBS (mpn_toom8_mul_n_itch (n));
77      mpn_toom8h_mul (p, a, n, b, n, ws);
78      TMP_FREE;
79    }
80  else
81    {
82      /* The current FFT code allocates its own space.  That should probably
83	 change.  */
84      mpn_fft_mul (p, a, n, b, n);
85    }
86}
87