Blame mpn/generic/toom_eval_pm2rexp.c

Packit 5c3484
/* mpn_toom_eval_pm2rexp -- Evaluate a polynomial in +2^-k and -2^-k
Packit 5c3484
Packit 5c3484
   Contributed to the GNU project by Marco Bodrato
Packit 5c3484
Packit 5c3484
   THE FUNCTION IN THIS FILE IS INTERNAL WITH A MUTABLE INTERFACE.  IT IS ONLY
Packit 5c3484
   SAFE TO REACH IT THROUGH DOCUMENTED INTERFACES.  IN FACT, IT IS ALMOST
Packit 5c3484
   GUARANTEED THAT IT WILL CHANGE OR DISAPPEAR IN A FUTURE GNU MP RELEASE.
Packit 5c3484
Packit 5c3484
Copyright 2009 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
Packit 5c3484
#include "gmp.h"
Packit 5c3484
#include "gmp-impl.h"
Packit 5c3484
Packit 5c3484
#if HAVE_NATIVE_mpn_addlsh_n
Packit 5c3484
#define DO_mpn_addlsh_n(dst,src,n,s,ws) mpn_addlsh_n(dst,dst,src,n,s)
Packit 5c3484
#else
Packit 5c3484
static mp_limb_t
Packit 5c3484
DO_mpn_addlsh_n(mp_ptr dst, mp_srcptr src, mp_size_t n, unsigned int s, mp_ptr ws)
Packit 5c3484
{
Packit 5c3484
#if USE_MUL_1 && 0
Packit 5c3484
  return mpn_addmul_1(dst,src,n,CNST_LIMB(1) <<(s));
Packit 5c3484
#else
Packit 5c3484
  mp_limb_t __cy;
Packit 5c3484
  __cy = mpn_lshift(ws,src,n,s);
Packit 5c3484
  return    __cy + mpn_add_n(dst,dst,ws,n);
Packit 5c3484
#endif
Packit 5c3484
}
Packit 5c3484
#endif
Packit 5c3484
Packit 5c3484
/* Evaluates a polynomial of degree k >= 3. */
Packit 5c3484
int
Packit 5c3484
mpn_toom_eval_pm2rexp (mp_ptr rp, mp_ptr rm,
Packit 5c3484
		      unsigned int q, mp_srcptr ap, mp_size_t n, mp_size_t t,
Packit 5c3484
		      unsigned int s, mp_ptr ws)
Packit 5c3484
{
Packit 5c3484
  unsigned int i;
Packit 5c3484
  int neg;
Packit 5c3484
  /* {ap,q*n+t} -> {rp,n+1} {rm,n+1} , with {ws, n+1}*/
Packit 5c3484
  ASSERT (n >= t);
Packit 5c3484
  ASSERT (s != 0); /* or _eval_pm1 should be used */
Packit 5c3484
  ASSERT (q > 1);
Packit 5c3484
  ASSERT (s*q < GMP_NUMB_BITS);
Packit 5c3484
  rp[n] = mpn_lshift(rp, ap, n, s*q);
Packit 5c3484
  ws[n] = mpn_lshift(ws, ap+n, n, s*(q-1));
Packit 5c3484
  if( (q & 1) != 0) {
Packit 5c3484
    ASSERT_NOCARRY(mpn_add(ws,ws,n+1,ap+n*q,t));
Packit 5c3484
    rp[n] += DO_mpn_addlsh_n(rp, ap+n*(q-1), n, s, rm);
Packit 5c3484
  } else {
Packit 5c3484
    ASSERT_NOCARRY(mpn_add(rp,rp,n+1,ap+n*q,t));
Packit 5c3484
  }
Packit 5c3484
  for(i=2; i
Packit 5c3484
  {
Packit 5c3484
    rp[n] += DO_mpn_addlsh_n(rp, ap+n*i, n, s*(q-i), rm);
Packit 5c3484
    i++;
Packit 5c3484
    ws[n] += DO_mpn_addlsh_n(ws, ap+n*i, n, s*(q-i), rm);
Packit 5c3484
  };
Packit 5c3484
Packit 5c3484
  neg = (mpn_cmp (rp, ws, n + 1) < 0) ? ~0 : 0;
Packit 5c3484
Packit 5c3484
#if HAVE_NATIVE_mpn_add_n_sub_n
Packit 5c3484
  if (neg)
Packit 5c3484
    mpn_add_n_sub_n (rp, rm, ws, rp, n + 1);
Packit 5c3484
  else
Packit 5c3484
    mpn_add_n_sub_n (rp, rm, rp, ws, n + 1);
Packit 5c3484
#else /* !HAVE_NATIVE_mpn_add_n_sub_n */
Packit 5c3484
  if (neg)
Packit 5c3484
    mpn_sub_n (rm, ws, rp, n + 1);
Packit 5c3484
  else
Packit 5c3484
    mpn_sub_n (rm, rp, ws, n + 1);
Packit 5c3484
Packit 5c3484
  ASSERT_NOCARRY (mpn_add_n (rp, rp, ws, n + 1));
Packit 5c3484
#endif /* !HAVE_NATIVE_mpn_add_n_sub_n */
Packit 5c3484
Packit 5c3484
  return neg;
Packit 5c3484
}