Coverage Report

Created: 2024-11-21 07:03

/src/libgmp/mpz/mul.c
Line
Count
Source
1
/* mpz_mul -- Multiply two integers.
2
3
Copyright 1991, 1993, 1994, 1996, 2000, 2001, 2005, 2009, 2011, 2012,
4
2015 Free Software 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 <stdio.h> /* for NULL */
33
#include "gmp-impl.h"
34
35
36
void
37
mpz_mul (mpz_ptr w, mpz_srcptr u, mpz_srcptr v)
38
966k
{
39
966k
  mp_size_t usize;
40
966k
  mp_size_t vsize;
41
966k
  mp_size_t wsize;
42
966k
  mp_size_t sign_product;
43
966k
  mp_ptr up, vp;
44
966k
  mp_ptr wp;
45
966k
  mp_ptr free_me;
46
966k
  size_t free_me_size;
47
966k
  mp_limb_t cy_limb;
48
966k
  TMP_DECL;
49
50
966k
  usize = SIZ (u);
51
966k
  vsize = SIZ (v);
52
966k
  sign_product = usize ^ vsize;
53
966k
  usize = ABS (usize);
54
966k
  vsize = ABS (vsize);
55
56
966k
  if (usize < vsize)
57
10.1k
    {
58
10.1k
      MPZ_SRCPTR_SWAP (u, v);
59
10.1k
      MP_SIZE_T_SWAP (usize, vsize);
60
10.1k
    }
61
62
966k
  if (vsize == 0)
63
1.15k
    {
64
1.15k
      SIZ (w) = 0;
65
1.15k
      return;
66
1.15k
    }
67
68
965k
#if HAVE_NATIVE_mpn_mul_2
69
965k
  if (vsize <= 2)
70
171k
    {
71
171k
      wp = MPZ_REALLOC (w, usize+vsize);
72
171k
      if (vsize == 1)
73
135k
  cy_limb = mpn_mul_1 (wp, PTR (u), usize, PTR (v)[0]);
74
36.2k
      else
75
36.2k
  {
76
36.2k
    cy_limb = mpn_mul_2 (wp, PTR (u), usize, PTR (v));
77
36.2k
    usize++;
78
36.2k
  }
79
171k
      wp[usize] = cy_limb;
80
171k
      usize += (cy_limb != 0);
81
171k
      SIZ (w) = (sign_product >= 0 ? usize : -usize);
82
171k
      return;
83
171k
    }
84
#else
85
  if (vsize == 1)
86
    {
87
      wp = MPZ_REALLOC (w, usize+1);
88
      cy_limb = mpn_mul_1 (wp, PTR (u), usize, PTR (v)[0]);
89
      wp[usize] = cy_limb;
90
      usize += (cy_limb != 0);
91
      SIZ (w) = (sign_product >= 0 ? usize : -usize);
92
      return;
93
    }
94
#endif
95
96
793k
  TMP_MARK;
97
793k
  free_me = NULL;
98
793k
  up = PTR (u);
99
793k
  vp = PTR (v);
100
793k
  wp = PTR (w);
101
102
  /* Ensure W has space enough to store the result.  */
103
793k
  wsize = usize + vsize;
104
793k
  if (ALLOC (w) < wsize)
105
18.0k
    {
106
18.0k
      if (ALLOC (w) != 0)
107
18.0k
  {
108
18.0k
    if (wp == up || wp == vp)
109
14.5k
      {
110
14.5k
        free_me = wp;
111
14.5k
        free_me_size = ALLOC (w);
112
14.5k
      }
113
3.42k
    else
114
3.42k
      (*__gmp_free_func) (wp, (size_t) ALLOC (w) * GMP_LIMB_BYTES);
115
18.0k
  }
116
117
18.0k
      ALLOC (w) = wsize;
118
18.0k
      wp = __GMP_ALLOCATE_FUNC_LIMBS (wsize);
119
18.0k
      PTR (w) = wp;
120
18.0k
    }
121
775k
  else
122
775k
    {
123
      /* Make U and V not overlap with W.  */
124
775k
      if (wp == up)
125
11.2k
  {
126
    /* W and U are identical.  Allocate temporary space for U.  */
127
11.2k
    up = TMP_ALLOC_LIMBS (usize);
128
    /* Is V identical too?  Keep it identical with U.  */
129
11.2k
    if (wp == vp)
130
200
      vp = up;
131
    /* Copy to the temporary space.  */
132
11.2k
    MPN_COPY (up, wp, usize);
133
11.2k
  }
134
764k
      else if (wp == vp)
135
3.07k
  {
136
    /* W and V are identical.  Allocate temporary space for V.  */
137
3.07k
    vp = TMP_ALLOC_LIMBS (vsize);
138
    /* Copy to the temporary space.  */
139
3.07k
    MPN_COPY (vp, wp, vsize);
140
3.07k
  }
141
775k
    }
142
143
793k
  if (up == vp)
144
763k
    {
145
763k
      mpn_sqr (wp, up, usize);
146
763k
      cy_limb = wp[wsize - 1];
147
763k
    }
148
29.7k
  else
149
29.7k
    {
150
29.7k
      cy_limb = mpn_mul (wp, up, usize, vp, vsize);
151
29.7k
    }
152
153
793k
  wsize -= cy_limb == 0;
154
155
793k
  SIZ (w) = sign_product < 0 ? -wsize : wsize;
156
793k
  if (free_me != NULL)
157
14.5k
    (*__gmp_free_func) (free_me, free_me_size * GMP_LIMB_BYTES);
158
793k
  TMP_FREE;
159
793k
}