Refactor bignum multiplication, exponentiation

This doesn’t alter behavior, and simplifies the next commit.
* src/bignum.c (GMP_NLIMBS_MAX, NLIMBS_LIMIT, emacs_mpz_size)
(emacs_mpz_mul, emacs_mpz_mul_2exp, emacs_mpz_pow_ui): Move here ...
* src/data.c: ... from here.

1 files changed, 78 insertions, 0 deletions

diff --git a/src/bignum.c b/src/bignum.c
index 167b73eee02..c31cf3d59a4 100644
--- a/src/bignum.c
+++ b/src/bignum.c
@@ -273,6 +273,84 @@ bignum_to_uintmax (Lisp_Object x)
   return mpz_to_uintmax (*xbignum_val (x), &i) ? i : 0;
 }
 
+
+/* Multiply and exponentiate mpz_t values without aborting due to size
+   limits.  */
+
+/* GMP tests for this value and aborts (!) if it is exceeded.
+   This is as of GMP 6.1.2 (2016); perhaps future versions will differ.  */
+enum { GMP_NLIMBS_MAX = min (INT_MAX, ULONG_MAX / GMP_NUMB_BITS) };
+
+/* An upper bound on limb counts, needed to prevent libgmp and/or
+   Emacs from aborting or otherwise misbehaving.  This bound applies
+   to estimates of mpz_t sizes before the mpz_t objects are created,
+   as opposed to integer-width which operates on mpz_t values after
+   creation and before conversion to Lisp bignums.  */
+enum
+  {
+   NLIMBS_LIMIT = min (min (/* libgmp needs to store limb counts.  */
+                            GMP_NLIMBS_MAX,
+
+                            /* Size calculations need to work.  */
+                            min (PTRDIFF_MAX, SIZE_MAX) / sizeof (mp_limb_t)),
+
+                       /* Emacs puts bit counts into fixnums.  */
+                       MOST_POSITIVE_FIXNUM / GMP_NUMB_BITS)
+  };
+
+/* Like mpz_size, but tell the compiler the result is a nonnegative int.  */
+
+static int
+emacs_mpz_size (mpz_t const op)
+{
+  mp_size_t size = mpz_size (op);
+  eassume (0 <= size && size <= INT_MAX);
+  return size;
+}
+
+/* Wrappers to work around GMP limitations.  As of GMP 6.1.2 (2016),
+   the library code aborts when a number is too large.  These wrappers
+   avoid the problem for functions that can return numbers much larger
+   than their arguments.  For slowly-growing numbers, the integer
+   width checks in bignum.c should suffice.  */
+
+void
+emacs_mpz_mul (mpz_t rop, mpz_t const op1, mpz_t const op2)
+{
+  if (NLIMBS_LIMIT - emacs_mpz_size (op1) < emacs_mpz_size (op2))
+    overflow_error ();
+  mpz_mul (rop, op1, op2);
+}
+
+void
+emacs_mpz_mul_2exp (mpz_t rop, mpz_t const op1, EMACS_INT op2)
+{
+  /* Fudge factor derived from GMP 6.1.2, to avoid an abort in
+     mpz_mul_2exp (look for the '+ 1' in its source code).  */
+  enum { mul_2exp_extra_limbs = 1 };
+  enum { lim = min (NLIMBS_LIMIT, GMP_NLIMBS_MAX - mul_2exp_extra_limbs) };
+
+  EMACS_INT op2limbs = op2 / GMP_NUMB_BITS;
+  if (lim - emacs_mpz_size (op1) < op2limbs)
+    overflow_error ();
+  mpz_mul_2exp (rop, op1, op2);
+}
+
+void
+emacs_mpz_pow_ui (mpz_t rop, mpz_t const base, unsigned long exp)
+{
+  /* This fudge factor is derived from GMP 6.1.2, to avoid an abort in
+     mpz_n_pow_ui (look for the '5' in its source code).  */
+  enum { pow_ui_extra_limbs = 5 };
+  enum { lim = min (NLIMBS_LIMIT, GMP_NLIMBS_MAX - pow_ui_extra_limbs) };
+
+  int nbase = emacs_mpz_size (base), n;
+  if (INT_MULTIPLY_WRAPV (nbase, exp, &n) || lim < n)
+    overflow_error ();
+  mpz_pow_ui (rop, base, exp);
+}
+
+
 /* Yield an upper bound on the buffer size needed to contain a C
    string representing the NUM in base BASE.  This includes any
    preceding '-' and the terminating NUL.  */