|
Packit |
5c3484 |
/* mpz_addmul_ui, mpz_submul_ui - add or subtract small multiple.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
THE mpz_aorsmul_1 FUNCTION IN THIS FILE IS FOR INTERNAL USE ONLY AND IS
|
|
Packit |
5c3484 |
ALMOST CERTAIN TO BE SUBJECT TO INCOMPATIBLE CHANGES OR DISAPPEAR
|
|
Packit |
5c3484 |
COMPLETELY IN FUTURE GNU MP RELEASES.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
Copyright 2001, 2002, 2004, 2005, 2012 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 |
#if HAVE_NATIVE_mpn_mul_1c
|
|
Packit |
5c3484 |
#define MPN_MUL_1C(cout, dst, src, size, n, cin) \
|
|
Packit |
5c3484 |
do { \
|
|
Packit |
5c3484 |
(cout) = mpn_mul_1c (dst, src, size, n, cin); \
|
|
Packit |
5c3484 |
} while (0)
|
|
Packit |
5c3484 |
#else
|
|
Packit |
5c3484 |
#define MPN_MUL_1C(cout, dst, src, size, n, cin) \
|
|
Packit |
5c3484 |
do { \
|
|
Packit |
5c3484 |
mp_limb_t __cy; \
|
|
Packit |
5c3484 |
__cy = mpn_mul_1 (dst, src, size, n); \
|
|
Packit |
5c3484 |
(cout) = __cy + mpn_add_1 (dst, dst, size, cin); \
|
|
Packit |
5c3484 |
} while (0)
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* sub>=0 means an addmul w += x*y, sub<0 means a submul w -= x*y.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
All that's needed to account for negative w or x is to flip "sub".
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
The final w will retain its sign, unless an underflow occurs in a submul
|
|
Packit |
5c3484 |
of absolute values, in which case it's flipped.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
If x has more limbs than w, then mpn_submul_1 followed by mpn_com is
|
|
Packit |
5c3484 |
used. The alternative would be mpn_mul_1 into temporary space followed
|
|
Packit |
5c3484 |
by mpn_sub_n. Avoiding temporary space seem good, and submul+com stands
|
|
Packit |
5c3484 |
a chance of being faster since it involves only one set of carry
|
|
Packit |
5c3484 |
propagations, not two. Note that doing an addmul_1 with a
|
|
Packit |
5c3484 |
twos-complement negative y doesn't work, because it effectively adds an
|
|
Packit |
5c3484 |
extra x * 2^GMP_LIMB_BITS. */
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
REGPARM_ATTR(1) void
|
|
Packit |
5c3484 |
mpz_aorsmul_1 (mpz_ptr w, mpz_srcptr x, mp_limb_t y, mp_size_t sub)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mp_size_t xsize, wsize, wsize_signed, new_wsize, min_size, dsize;
|
|
Packit |
5c3484 |
mp_srcptr xp;
|
|
Packit |
5c3484 |
mp_ptr wp;
|
|
Packit |
5c3484 |
mp_limb_t cy;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* w unaffected if x==0 or y==0 */
|
|
Packit |
5c3484 |
xsize = SIZ (x);
|
|
Packit |
5c3484 |
if (xsize == 0 || y == 0)
|
|
Packit |
5c3484 |
return;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
sub ^= xsize;
|
|
Packit |
5c3484 |
xsize = ABS (xsize);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
wsize_signed = SIZ (w);
|
|
Packit |
5c3484 |
if (wsize_signed == 0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
/* nothing to add to, just set x*y, "sub" gives the sign */
|
|
Packit |
5c3484 |
wp = MPZ_REALLOC (w, xsize+1);
|
|
Packit |
5c3484 |
cy = mpn_mul_1 (wp, PTR(x), xsize, y);
|
|
Packit |
5c3484 |
wp[xsize] = cy;
|
|
Packit |
5c3484 |
xsize += (cy != 0);
|
|
Packit |
5c3484 |
SIZ (w) = (sub >= 0 ? xsize : -xsize);
|
|
Packit |
5c3484 |
return;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
sub ^= wsize_signed;
|
|
Packit |
5c3484 |
wsize = ABS (wsize_signed);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
new_wsize = MAX (wsize, xsize);
|
|
Packit |
5c3484 |
wp = MPZ_REALLOC (w, new_wsize+1);
|
|
Packit |
5c3484 |
xp = PTR (x);
|
|
Packit |
5c3484 |
min_size = MIN (wsize, xsize);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (sub >= 0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
/* addmul of absolute values */
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
cy = mpn_addmul_1 (wp, xp, min_size, y);
|
|
Packit |
5c3484 |
wp += min_size;
|
|
Packit |
5c3484 |
xp += min_size;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
dsize = xsize - wsize;
|
|
Packit |
5c3484 |
#if HAVE_NATIVE_mpn_mul_1c
|
|
Packit |
5c3484 |
if (dsize > 0)
|
|
Packit |
5c3484 |
cy = mpn_mul_1c (wp, xp, dsize, y, cy);
|
|
Packit |
5c3484 |
else if (dsize < 0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
dsize = -dsize;
|
|
Packit |
5c3484 |
cy = mpn_add_1 (wp, wp, dsize, cy);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
#else
|
|
Packit |
5c3484 |
if (dsize != 0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mp_limb_t cy2;
|
|
Packit |
5c3484 |
if (dsize > 0)
|
|
Packit |
5c3484 |
cy2 = mpn_mul_1 (wp, xp, dsize, y);
|
|
Packit |
5c3484 |
else
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
dsize = -dsize;
|
|
Packit |
5c3484 |
cy2 = 0;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
cy = cy2 + mpn_add_1 (wp, wp, dsize, cy);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
wp[dsize] = cy;
|
|
Packit |
5c3484 |
new_wsize += (cy != 0);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
else
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
/* submul of absolute values */
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
cy = mpn_submul_1 (wp, xp, min_size, y);
|
|
Packit |
5c3484 |
if (wsize >= xsize)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
/* if w bigger than x, then propagate borrow through it */
|
|
Packit |
5c3484 |
if (wsize != xsize)
|
|
Packit |
5c3484 |
cy = mpn_sub_1 (wp+xsize, wp+xsize, wsize-xsize, cy);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (cy != 0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
/* Borrow out of w, take twos complement negative to get
|
|
Packit |
5c3484 |
absolute value, flip sign of w. */
|
|
Packit |
5c3484 |
wp[new_wsize] = ~-cy; /* extra limb is 0-cy */
|
|
Packit |
5c3484 |
mpn_com (wp, wp, new_wsize);
|
|
Packit |
5c3484 |
new_wsize++;
|
|
Packit |
5c3484 |
MPN_INCR_U (wp, new_wsize, CNST_LIMB(1));
|
|
Packit |
5c3484 |
wsize_signed = -wsize_signed;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
else /* wsize < xsize */
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
/* x bigger than w, so want x*y-w. Submul has given w-x*y, so
|
|
Packit |
5c3484 |
take twos complement and use an mpn_mul_1 for the rest. */
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mp_limb_t cy2;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* -(-cy*b^n + w-x*y) = (cy-1)*b^n + ~(w-x*y) + 1 */
|
|
Packit |
5c3484 |
mpn_com (wp, wp, wsize);
|
|
Packit |
5c3484 |
cy += mpn_add_1 (wp, wp, wsize, CNST_LIMB(1));
|
|
Packit |
5c3484 |
cy -= 1;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* If cy-1 == -1 then hold that -1 for latter. mpn_submul_1 never
|
|
Packit |
5c3484 |
returns cy==MP_LIMB_T_MAX so that value always indicates a -1. */
|
|
Packit |
5c3484 |
cy2 = (cy == MP_LIMB_T_MAX);
|
|
Packit |
5c3484 |
cy += cy2;
|
|
Packit |
5c3484 |
MPN_MUL_1C (cy, wp+wsize, xp+wsize, xsize-wsize, y, cy);
|
|
Packit |
5c3484 |
wp[new_wsize] = cy;
|
|
Packit |
5c3484 |
new_wsize += (cy != 0);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* Apply any -1 from above. The value at wp+wsize is non-zero
|
|
Packit |
5c3484 |
because y!=0 and the high limb of x will be non-zero. */
|
|
Packit |
5c3484 |
if (cy2)
|
|
Packit |
5c3484 |
MPN_DECR_U (wp+wsize, new_wsize-wsize, CNST_LIMB(1));
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
wsize_signed = -wsize_signed;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* submul can produce high zero limbs due to cancellation, both when w
|
|
Packit |
5c3484 |
has more limbs or x has more */
|
|
Packit |
5c3484 |
MPN_NORMALIZE (wp, new_wsize);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
SIZ (w) = (wsize_signed >= 0 ? new_wsize : -new_wsize);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
ASSERT (new_wsize == 0 || PTR(w)[new_wsize-1] != 0);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
void
|
|
Packit |
5c3484 |
mpz_addmul_ui (mpz_ptr w, mpz_srcptr x, unsigned long y)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
#if BITS_PER_ULONG > GMP_NUMB_BITS
|
|
Packit |
5c3484 |
if (UNLIKELY (y > GMP_NUMB_MAX))
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mpz_t t;
|
|
Packit |
5c3484 |
mp_ptr tp;
|
|
Packit |
5c3484 |
mp_size_t xn;
|
|
Packit |
5c3484 |
TMP_DECL;
|
|
Packit |
5c3484 |
TMP_MARK;
|
|
Packit |
5c3484 |
xn = SIZ (x);
|
|
Packit |
5c3484 |
if (xn == 0) return;
|
|
Packit |
5c3484 |
MPZ_TMP_INIT (t, ABS (xn) + 1);
|
|
Packit |
5c3484 |
tp = PTR (t);
|
|
Packit |
5c3484 |
tp[0] = 0;
|
|
Packit |
5c3484 |
MPN_COPY (tp + 1, PTR(x), ABS (xn));
|
|
Packit |
5c3484 |
SIZ(t) = xn >= 0 ? xn + 1 : xn - 1;
|
|
Packit |
5c3484 |
mpz_aorsmul_1 (w, t, (mp_limb_t) y >> GMP_NUMB_BITS, (mp_size_t) 0);
|
|
Packit |
5c3484 |
PTR(t) = tp + 1;
|
|
Packit |
5c3484 |
SIZ(t) = xn;
|
|
Packit |
5c3484 |
mpz_aorsmul_1 (w, t, (mp_limb_t) y & GMP_NUMB_MASK, (mp_size_t) 0);
|
|
Packit |
5c3484 |
TMP_FREE;
|
|
Packit |
5c3484 |
return;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
mpz_aorsmul_1 (w, x, (mp_limb_t) y, (mp_size_t) 0);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
void
|
|
Packit |
5c3484 |
mpz_submul_ui (mpz_ptr w, mpz_srcptr x, unsigned long y)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
#if BITS_PER_ULONG > GMP_NUMB_BITS
|
|
Packit |
5c3484 |
if (y > GMP_NUMB_MAX)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mpz_t t;
|
|
Packit |
5c3484 |
mp_ptr tp;
|
|
Packit |
5c3484 |
mp_size_t xn;
|
|
Packit |
5c3484 |
TMP_DECL;
|
|
Packit |
5c3484 |
TMP_MARK;
|
|
Packit |
5c3484 |
xn = SIZ (x);
|
|
Packit |
5c3484 |
if (xn == 0) return;
|
|
Packit |
5c3484 |
MPZ_TMP_INIT (t, ABS (xn) + 1);
|
|
Packit |
5c3484 |
tp = PTR (t);
|
|
Packit |
5c3484 |
tp[0] = 0;
|
|
Packit |
5c3484 |
MPN_COPY (tp + 1, PTR(x), ABS (xn));
|
|
Packit |
5c3484 |
SIZ(t) = xn >= 0 ? xn + 1 : xn - 1;
|
|
Packit |
5c3484 |
mpz_aorsmul_1 (w, t, (mp_limb_t) y >> GMP_NUMB_BITS, (mp_size_t) -1);
|
|
Packit |
5c3484 |
PTR(t) = tp + 1;
|
|
Packit |
5c3484 |
SIZ(t) = xn;
|
|
Packit |
5c3484 |
mpz_aorsmul_1 (w, t, (mp_limb_t) y & GMP_NUMB_MASK, (mp_size_t) -1);
|
|
Packit |
5c3484 |
TMP_FREE;
|
|
Packit |
5c3484 |
return;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
mpz_aorsmul_1 (w, x, (mp_limb_t) y & GMP_NUMB_MASK, (mp_size_t) -1);
|
|
Packit |
5c3484 |
}
|