1 /* mpn_mul -- Multiply two natural numbers.
3 Copyright (C) 1991 Free Software Foundation, Inc.
5 This file is part of the GNU MP Library.
7 The GNU MP Library is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 1, or (at your option)
12 The GNU MP Library is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with the GNU MP Library; see the file COPYING. If not, write to
19 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
25 /* Multiply the natural numbers u (pointed to by UP, with USIZE limbs)
26 and v (pointed to by VP, with VSIZE limbs), and store the result at
27 PRODP. USIZE + VSIZE limbs are always stored, but if the input
28 operands are normalized, the return value will reflect the true
29 result size (which is either USIZE + VSIZE, or USIZE + VSIZE -1).
31 NOTE: The space pointed to by PRODP is overwritten before finished
32 with U and V, so overlap is an error.
36 2. PRODP != UP and PRODP != VP, i.e. the destination
37 must be distinct from the multiplier and the multiplicand. */
40 mpn_mul_classic (mp_ptr prodp,
41 mp_srcptr up, mp_size_t usize,
42 mp_srcptr vp, mp_size_t vsize)
48 mp_limb prod_low, prod_high;
55 /* Offset UP and PRODP so that the inner loop can be faster. */
59 /* Multiply by the first limb in V separately, as the result can
60 be stored (not added) to PROD. We also avoid a loop for zeroing. */
66 umul_ppmm (prod_high, prod_low, up[j], v_limb);
67 add_ssaaaa (cy_dig, prodp[j], prod_high, prod_low, 0, cy_dig);
75 /* For each iteration in the outer loop, multiply one limb from
76 U with one limb from V, and add it to PROD. */
77 for (i = 1; i < vsize; i++)
83 /* Inner loops. Simulate the carry flag by jumping between
84 these loops. The first is used when there was no carry
85 in the previois iteration; the second when there was carry. */
89 umul_ppmm (prod_high, prod_low, up[j], v_limb);
90 add_ssaaaa (cy_dig, prod_low, prod_high, prod_low, 0, cy_dig);
107 umul_ppmm (prod_high, prod_low, up[j], v_limb);
108 add_ssaaaa (cy_dig, prod_low, prod_high, prod_low, 0, cy_dig);
124 return usize + vsize - (cy_dig == 0);