|
Packit |
5c3484 |
/* mpn_mul_basecase -- Internal routine to multiply two natural numbers
|
|
Packit |
5c3484 |
of length m and n.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
THIS IS AN INTERNAL FUNCTION WITH A MUTABLE INTERFACE. IT IS ONLY
|
|
Packit |
5c3484 |
SAFE TO REACH THIS FUNCTION THROUGH DOCUMENTED INTERFACES.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
Copyright 1991-1994, 1996, 1997, 2000-2002 Free Software Foundation, Inc.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
This file is part of the GNU MP Library.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
The GNU MP Library is free software; you can redistribute it and/or modify
|
|
Packit |
5c3484 |
it under the terms of either:
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
* the GNU Lesser General Public License as published by the Free
|
|
Packit |
5c3484 |
Software Foundation; either version 3 of the License, or (at your
|
|
Packit |
5c3484 |
option) any later version.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
or
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
* the GNU General Public License as published by the Free Software
|
|
Packit |
5c3484 |
Foundation; either version 2 of the License, or (at your option) any
|
|
Packit |
5c3484 |
later version.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
or both in parallel, as here.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
The GNU MP Library is distributed in the hope that it will be useful, but
|
|
Packit |
5c3484 |
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
|
|
Packit |
5c3484 |
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
Packit |
5c3484 |
for more details.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
You should have received copies of the GNU General Public License and the
|
|
Packit |
5c3484 |
GNU Lesser General Public License along with the GNU MP Library. If not,
|
|
Packit |
5c3484 |
see https://www.gnu.org/licenses/. */
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#include "gmp.h"
|
|
Packit |
5c3484 |
#include "gmp-impl.h"
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* Multiply {up,usize} by {vp,vsize} and write the result to
|
|
Packit |
5c3484 |
{prodp,usize+vsize}. Must have usize>=vsize.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
Note that prodp gets usize+vsize limbs stored, even if the actual result
|
|
Packit |
5c3484 |
only needs usize+vsize-1.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
There's no good reason to call here with vsize>=MUL_TOOM22_THRESHOLD.
|
|
Packit |
5c3484 |
Currently this is allowed, but it might not be in the future.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
This is the most critical code for multiplication. All multiplies rely
|
|
Packit |
5c3484 |
on this, both small and huge. Small ones arrive here immediately, huge
|
|
Packit |
5c3484 |
ones arrive here as this is the base case for Karatsuba's recursive
|
|
Packit |
5c3484 |
algorithm. */
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
void
|
|
Packit |
5c3484 |
mpn_mul_basecase (mp_ptr rp,
|
|
Packit |
5c3484 |
mp_srcptr up, mp_size_t un,
|
|
Packit |
5c3484 |
mp_srcptr vp, mp_size_t vn)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
ASSERT (un >= vn);
|
|
Packit |
5c3484 |
ASSERT (vn >= 1);
|
|
Packit |
5c3484 |
ASSERT (! MPN_OVERLAP_P (rp, un+vn, up, un));
|
|
Packit |
5c3484 |
ASSERT (! MPN_OVERLAP_P (rp, un+vn, vp, vn));
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* We first multiply by the low order limb (or depending on optional function
|
|
Packit |
5c3484 |
availability, limbs). This result can be stored, not added, to rp. We
|
|
Packit |
5c3484 |
also avoid a loop for zeroing this way. */
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#if HAVE_NATIVE_mpn_mul_2
|
|
Packit |
5c3484 |
if (vn >= 2)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
rp[un + 1] = mpn_mul_2 (rp, up, un, vp);
|
|
Packit |
5c3484 |
rp += 2, vp += 2, vn -= 2;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
else
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
rp[un] = mpn_mul_1 (rp, up, un, vp[0]);
|
|
Packit |
5c3484 |
return;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
#else
|
|
Packit |
5c3484 |
rp[un] = mpn_mul_1 (rp, up, un, vp[0]);
|
|
Packit |
5c3484 |
rp += 1, vp += 1, vn -= 1;
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* Now accumulate the product of up[] and the next higher limb (or depending
|
|
Packit |
5c3484 |
on optional function availability, limbs) from vp[]. */
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#define MAX_LEFT MP_SIZE_T_MAX /* Used to simplify loops into if statements */
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#if HAVE_NATIVE_mpn_addmul_6
|
|
Packit |
5c3484 |
while (vn >= 6)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
rp[un + 6 - 1] = mpn_addmul_6 (rp, up, un, vp);
|
|
Packit |
5c3484 |
if (MAX_LEFT == 6)
|
|
Packit |
5c3484 |
return;
|
|
Packit |
5c3484 |
rp += 6, vp += 6, vn -= 6;
|
|
Packit |
5c3484 |
if (MAX_LEFT < 2 * 6)
|
|
Packit |
5c3484 |
break;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
#undef MAX_LEFT
|
|
Packit |
5c3484 |
#define MAX_LEFT (6 - 1)
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#if HAVE_NATIVE_mpn_addmul_5
|
|
Packit |
5c3484 |
while (vn >= 5)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
rp[un + 5 - 1] = mpn_addmul_5 (rp, up, un, vp);
|
|
Packit |
5c3484 |
if (MAX_LEFT == 5)
|
|
Packit |
5c3484 |
return;
|
|
Packit |
5c3484 |
rp += 5, vp += 5, vn -= 5;
|
|
Packit |
5c3484 |
if (MAX_LEFT < 2 * 5)
|
|
Packit |
5c3484 |
break;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
#undef MAX_LEFT
|
|
Packit |
5c3484 |
#define MAX_LEFT (5 - 1)
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#if HAVE_NATIVE_mpn_addmul_4
|
|
Packit |
5c3484 |
while (vn >= 4)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
rp[un + 4 - 1] = mpn_addmul_4 (rp, up, un, vp);
|
|
Packit |
5c3484 |
if (MAX_LEFT == 4)
|
|
Packit |
5c3484 |
return;
|
|
Packit |
5c3484 |
rp += 4, vp += 4, vn -= 4;
|
|
Packit |
5c3484 |
if (MAX_LEFT < 2 * 4)
|
|
Packit |
5c3484 |
break;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
#undef MAX_LEFT
|
|
Packit |
5c3484 |
#define MAX_LEFT (4 - 1)
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#if HAVE_NATIVE_mpn_addmul_3
|
|
Packit |
5c3484 |
while (vn >= 3)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
rp[un + 3 - 1] = mpn_addmul_3 (rp, up, un, vp);
|
|
Packit |
5c3484 |
if (MAX_LEFT == 3)
|
|
Packit |
5c3484 |
return;
|
|
Packit |
5c3484 |
rp += 3, vp += 3, vn -= 3;
|
|
Packit |
5c3484 |
if (MAX_LEFT < 2 * 3)
|
|
Packit |
5c3484 |
break;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
#undef MAX_LEFT
|
|
Packit |
5c3484 |
#define MAX_LEFT (3 - 1)
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#if HAVE_NATIVE_mpn_addmul_2
|
|
Packit |
5c3484 |
while (vn >= 2)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
rp[un + 2 - 1] = mpn_addmul_2 (rp, up, un, vp);
|
|
Packit |
5c3484 |
if (MAX_LEFT == 2)
|
|
Packit |
5c3484 |
return;
|
|
Packit |
5c3484 |
rp += 2, vp += 2, vn -= 2;
|
|
Packit |
5c3484 |
if (MAX_LEFT < 2 * 2)
|
|
Packit |
5c3484 |
break;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
#undef MAX_LEFT
|
|
Packit |
5c3484 |
#define MAX_LEFT (2 - 1)
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
while (vn >= 1)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
rp[un] = mpn_addmul_1 (rp, up, un, vp[0]);
|
|
Packit |
5c3484 |
if (MAX_LEFT == 1)
|
|
Packit |
5c3484 |
return;
|
|
Packit |
5c3484 |
rp += 1, vp += 1, vn -= 1;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
}
|