mpn/generic/compute_powtab.c - gmp - Git at Google

 /* 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
 }
	/* 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
	}