Coverage Report

Created: 2024-11-21 07:03

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