/* mpn_compute_powtab.

   Contributed to the GNU project by Torbjorn Granlund.

   THE FUNCTIONS IN THIS FILE ARE INTERNAL WITH MUTABLE INTERFACES.  IT IS ONLY

   SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES.  IN FACT, IT IS ALMOST

   GUARANTEED THAT THEY WILL CHANGE OR DISAPPEAR IN A FUTURE GNU MP RELEASE.

Copyright 1991-2017 Free Software Foundation, Inc.

This file is part of the GNU MP Library.

The GNU MP Library is free software; you can redistribute it and/or modify

it under the terms of either:

  * the GNU Lesser General Public License as published by the Free

    Software Foundation; either version 3 of the License, or (at your

    option) any later version.

or

  * the GNU General Public License as published by the Free Software

    Foundation; either version 2 of the License, or (at your option) any

    later version.

or both in parallel, as here.

The GNU MP Library is distributed in the hope that it will be useful, but

WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY

or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

for more details.

You should have received copies of the GNU General Public License and the

GNU Lesser General Public License along with the GNU MP Library.  If not,

see https://www.gnu.org/licenses/.  */

/*

  CAVEATS:

  * The exptab and powtab vectors are in opposite orders.  Probably OK.

  * Consider getting rid of exptab, doing bit ops on the un argument instead.

  * Consider rounding greatest power slightly upwards to save adjustments.

  * In powtab_decide, consider computing cost from just the 2-3 largest

    operands, since smaller operand contribute little.  This makes most sense

    if exptab is suppressed.

*/

#include "gmp-impl.h"

#ifndef DIV_1_VS_MUL_1_PERCENT

#define DIV_1_VS_MUL_1_PERCENT 150

#endif

#define SET_powers_t(dest, ptr, size, dib, b, sh) \

  do {             \

    dest.p = ptr;         \

    dest.n = size;          \

    dest.digits_in_base = dib;        \

    dest.base = b;          \

    dest.shift = sh;          \

  } while (0)

#if DIV_1_VS_MUL_1_PERCENT > 120

#define HAVE_mpn_compute_powtab_mul 1

static void

mpn_compute_powtab_mul (powers_t *powtab, mp_ptr powtab_mem, mp_size_t un,

      int base, const size_t *exptab, size_t n_pows)

{

  mp_size_t n;

  mp_ptr p, t;

  mp_limb_t cy;

  long start_idx;

  int c;

  mp_limb_t big_base = mp_bases[base].big_base;

  int chars_per_limb = mp_bases[base].chars_per_limb;

  mp_ptr powtab_mem_ptr = powtab_mem;

  size_t digits_in_base = chars_per_limb;

  powers_t *pt = powtab;

  p = powtab_mem_ptr;

  powtab_mem_ptr += 1;

  p[0] = big_base;

  SET_powers_t (pt[0], p, 1, digits_in_base, base, 0);

  pt++;

  t = powtab_mem_ptr;

  powtab_mem_ptr += 2;

  t[1] = mpn_mul_1 (t, p, 1, big_base);

  n = 2;

  digits_in_base *= 2;

  c = t[0] == 0;

  t += c;

  n -= c;

  mp_size_t shift = c;

  SET_powers_t (pt[0], t, n, digits_in_base, base, shift);

  p = t;

  pt++;

  if (exptab[0] == ((size_t) chars_per_limb << n_pows))

    {

      start_idx = n_pows - 2;

    }

  else

    {

      if (((digits_in_base + chars_per_limb) << (n_pows-2)) <= exptab[0])

  {

    /* 3, sometimes adjusted to 4.  */

    t = powtab_mem_ptr;

    powtab_mem_ptr += 4;

    t[n] = cy = mpn_mul_1 (t, p, n, big_base);

    n += cy != 0;;

    digits_in_base += chars_per_limb;

    c  = t[0] == 0;

    t += c;

    n -= c;

    shift += c;

  }

      else

  {

    /* 2 copy, will always become 3 with back-multiplication.  */

    t = powtab_mem_ptr;

    powtab_mem_ptr += 3;

    t[0] = p[0];

    t[1] = p[1];

  }

      SET_powers_t (pt[0], t, n, digits_in_base, base, shift);

      p = t;

      pt++;

      start_idx = n_pows - 3;

    }

  for (long pi = start_idx; pi >= 0; pi--)

    {

      t = powtab_mem_ptr;

      powtab_mem_ptr += 2 * n + 2;

      ASSERT (powtab_mem_ptr < powtab_mem + mpn_str_powtab_alloc (un));

      mpn_sqr (t, p, n);

      digits_in_base *= 2;

      n *= 2;

      n -= t[n - 1] == 0;

      shift *= 2;

      c = t[0] == 0;

      t += c;

      n -= c;

      shift += c;

      /* Adjust new value if it is too small as input to the next squaring.  */

      if (((digits_in_base + chars_per_limb) << pi) <= exptab[0])

  {

    t[n] = cy = mpn_mul_1 (t, t, n, big_base);

    n += cy != 0;

    digits_in_base += chars_per_limb;

    c  = t[0] == 0;

    t += c;

    n -= c;

    shift += c;

  }

      SET_powers_t (pt[0], t, n, digits_in_base, base, shift);

      /* Adjust previous value if it is not at its target power.  */

      if (pt[-1].digits_in_base < exptab[pi + 1])

  {

    mp_size_t n = pt[-1].n;

    mp_ptr p = pt[-1].p;

    p[n] = cy = mpn_mul_1 (p, p, n, big_base);

    n += cy != 0;

    ASSERT (pt[-1].digits_in_base + chars_per_limb == exptab[pi + 1]);

    pt[-1].digits_in_base = exptab[pi + 1];

    c = p[0] == 0;

    pt[-1].p = p + c;

    pt[-1].n = n - c;

    pt[-1].shift += c;

  }

      p = t;

      pt++;

    }

}

#endif

#if DIV_1_VS_MUL_1_PERCENT < 275

#define HAVE_mpn_compute_powtab_div 1

static void

mpn_compute_powtab_div (powers_t *powtab, mp_ptr powtab_mem, mp_size_t un,

      int base, const size_t *exptab, size_t n_pows)

{

  mp_ptr p, t;

  mp_limb_t big_base = mp_bases[base].big_base;

  int chars_per_limb = mp_bases[base].chars_per_limb;

  mp_ptr powtab_mem_ptr = powtab_mem;

  size_t digits_in_base = chars_per_limb;

  powers_t *pt = powtab;

  p = powtab_mem_ptr;

  powtab_mem_ptr += 1;

  p[0] = big_base;

  SET_powers_t (pt[0], p, 1, digits_in_base, base, 0);

  pt++;

  mp_size_t n = 1;

  mp_size_t shift = 0;

  for (long pi = n_pows - 1; pi >= 0; pi--)

    {

      t = powtab_mem_ptr;

      powtab_mem_ptr += 2 * n;

      ASSERT (powtab_mem_ptr < powtab_mem + mpn_str_powtab_alloc (un));

      mpn_sqr (t, p, n);

      n = 2 * n - 1; n += t[n] != 0;

      digits_in_base *= 2;

      if (digits_in_base != exptab[pi]) /* if ((((un - 1) >> pi) & 2) == 0) */

  {

#if HAVE_NATIVE_mpn_pi1_bdiv_q_1 || ! HAVE_NATIVE_mpn_divexact_1

    if (__GMP_LIKELY (base == 10))

      mpn_pi1_bdiv_q_1 (t, t, n, big_base >> MP_BASES_BIG_BASE_CTZ_10,

            MP_BASES_BIG_BASE_BINVERTED_10,

            MP_BASES_BIG_BASE_CTZ_10);

    else

#endif

      /* FIXME: We could use _pi1 here if we add big_base_binverted and

         big_base_ctz fields to struct bases.  That would add about 2 KiB

         to mp_bases.c.

         FIXME: Use mpn_bdiv_q_1 here when mpn_divexact_1 is converted to

         mpn_bdiv_q_1 for more machines. */

      mpn_divexact_1 (t, t, n, big_base);

    n -= t[n - 1] == 0;

    digits_in_base -= chars_per_limb;

  }

      shift *= 2;

      /* Strip low zero limbs, but be careful to keep the result divisible by

   big_base.  */

      while (t[0] == 0 && (t[1] & ((big_base & -big_base) - 1)) == 0)

  {

    t++;

    n--;

    shift++;

  }

      p = t;

      SET_powers_t (pt[0], p, n, digits_in_base, base, shift);

      pt++;

    }

  /* Strip any remaining low zero limbs.  */

  pt -= n_pows + 1;

  for (long pi = n_pows; pi >= 0; pi--)

    {

      mp_ptr t = pt[pi].p;

      mp_size_t shift = pt[pi].shift;

      mp_size_t n = pt[pi].n;

      int c;

      c = t[0] == 0;

      t += c;

      n -= c;

      shift += c;

      pt[pi].p = t;

      pt[pi].shift = shift;

      pt[pi].n = n;

    }

}

#endif

static long

powtab_decide (size_t *exptab, size_t un, int base)

{

  int chars_per_limb = mp_bases[base].chars_per_limb;

  long n_pows = 0;

  for (size_t pn = (un + 1) >> 1; pn != 1; pn = (pn + 1) >> 1)

    {

      exptab[n_pows] = pn * chars_per_limb;

      n_pows++;

    }

  exptab[n_pows] = chars_per_limb;

#if HAVE_mpn_compute_powtab_mul && HAVE_mpn_compute_powtab_div

  size_t pn = un - 1;

  size_t xn = (un + 1) >> 1;

  unsigned mcost = 1;

  unsigned dcost = 1;

  for (long i = n_pows - 2; i >= 0; i--)

    {

      size_t pow = (pn >> (i + 1)) + 1;

      if (pow & 1)

  dcost += pow;

      if (xn != (pow << i))

  {

    if (pow > 2 && (pow & 1) == 0)

      mcost += 2 * pow;

    else

      mcost += pow;

  }

      else

  {

    if (pow & 1)

      mcost += pow;

  }

    }

  dcost = dcost * DIV_1_VS_MUL_1_PERCENT / 100;

  if (mcost <= dcost)

    return n_pows;

  else

    return -n_pows;

#elif HAVE_mpn_compute_powtab_mul

  return n_pows;

#elif HAVE_mpn_compute_powtab_div

  return -n_pows;

#else

#error "no powtab function available"

#endif

}

size_t

mpn_compute_powtab (powers_t *powtab, mp_ptr powtab_mem, mp_size_t un, int base)

{

  size_t exptab[GMP_LIMB_BITS];

  long n_pows = powtab_decide (exptab, un, base);

#if HAVE_mpn_compute_powtab_mul && HAVE_mpn_compute_powtab_div

  if (n_pows >= 0)

    {

      mpn_compute_powtab_mul (powtab, powtab_mem, un, base, exptab, n_pows);

      return n_pows;

    }

  else

    {

      mpn_compute_powtab_div (powtab, powtab_mem, un, base, exptab, -n_pows);

      return -n_pows;

    }

#elif HAVE_mpn_compute_powtab_mul

  ASSERT (n_pows > 0);

  mpn_compute_powtab_mul (powtab, powtab_mem, un, base, exptab, n_pows);

  return n_pows;

#elif HAVE_mpn_compute_powtab_div

  ASSERT (n_pows < 0);

  mpn_compute_powtab_div (powtab, powtab_mem, un, base, exptab, -n_pows);

  return -n_pows;

#else

#error "no powtab function available"

#endif

}