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