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 | } |