[src/set_z_exp.c] Fixed possible integer overflows with huge mpz_t.

  Note: In practice, they may occur only with a 32-bit ABI. Moreover,
  with a usual compilation, they should have no effect, assuming the
  processor does signed addition and multiplication mod 2^32 (as usual).
  However, UBsan will detect the issue, and LTO might have unpredictable
  effects.

[tests/tset_z_exp.c] Added testcases, enabled only when the
MPFR_CHECK_LARGEMEM environment variable is set.

(merged changesets r14136-14145 of src/set_z_2exp.c and tset_z_2exp.c
from the trunk)

git-svn-id: https://scm.gforge.inria.fr/anonscm/svn/mpfr/branches/4.1@14147 280ebfd0-de03-0410-8827-d642c229c3f4

2 files changed, 94 insertions, 11 deletions

diff --git a/src/set_z_exp.c b/src/set_z_exp.c
index 718fbe6c6..67e58510b 100644
--- a/src/set_z_exp.c
+++ b/src/set_z_exp.c
@@ -28,10 +28,11 @@ https://www.gnu.org/licenses/ or write to the Free Software Foundation, Inc.,
 int
 mpfr_set_z_2exp (mpfr_ptr f, mpz_srcptr z, mpfr_exp_t e, mpfr_rnd_t rnd_mode)
 {
-  mp_size_t fn, zn, dif, en;
+  mp_size_t fn, zn, dif;
   int k, sign_z, inex;
   mp_limb_t *fp, *zp;
-  mpfr_exp_t exp;
+  mpfr_exp_t exp, nmax;
+  mpfr_uexp_t uexp;
 
   sign_z = mpz_sgn (z);
   if (MPFR_UNLIKELY (sign_z == 0)) /* ignore the exponent for 0 */
@@ -43,10 +44,15 @@ mpfr_set_z_2exp (mpfr_ptr f, mpz_srcptr z, mpfr_exp_t e, mpfr_rnd_t rnd_mode)
   MPFR_ASSERTD (sign_z == MPFR_SIGN_POS || sign_z == MPFR_SIGN_NEG);
 
   zn = ABSIZ(z); /* limb size of z */
-  /* compute en = floor(e/GMP_NUMB_BITS) */
-  en = (e >= 0) ? e / GMP_NUMB_BITS : (e + 1) / GMP_NUMB_BITS - 1;
   MPFR_ASSERTD (zn >= 1);
-  if (MPFR_UNLIKELY (zn + en > MPFR_EMAX_MAX / GMP_NUMB_BITS + 1))
+  nmax = MPFR_EMAX_MAX / GMP_NUMB_BITS + 1;
+  /* Detect early overflow with zn + en > nmax,
+     where en = floor(e / GMP_NUMB_BITS).
+     This is checked without an integer overflow (even assuming some
+     future version of GMP, where limitations may be removed). */
+  if (MPFR_UNLIKELY (e >= 0 ?
+                     zn > nmax - e / GMP_NUMB_BITS :
+                     zn + (e + 1) / GMP_NUMB_BITS - 1 > nmax))
     return mpfr_overflow (f, rnd_mode, sign_z);
   /* because zn + en >= MPFR_EMAX_MAX / GMP_NUMB_BITS + 2
      implies (zn + en) * GMP_NUMB_BITS >= MPFR_EMAX_MAX + GMP_NUMB_BITS + 1
@@ -64,13 +70,31 @@ mpfr_set_z_2exp (mpfr_ptr f, mpz_srcptr z, mpfr_exp_t e, mpfr_rnd_t rnd_mode)
      and exp = zn * GMP_NUMB_BITS + e - k
              <= (zn + en) * GMP_NUMB_BITS - k + GMP_NUMB_BITS - 1
              <= MPFR_EMAX_MAX + 2 * GMP_NUMB_BITS - 1 */
-  exp = (mpfr_prec_t) zn * GMP_NUMB_BITS + e - k;
+  /* We need to compute exp = zn * GMP_NUMB_BITS + e - k with well-defined
+     operations (no integer overflows / no implementation-defined results).
+     The mathematical result of zn * GMP_NUMB_BITS may be larger than
+     the largest value of mpfr_exp_t while exp could still be less than
+     __gmpfr_emax. Thanks to early overflow detection, we can compute the
+     result in modular arithmetic, using mpfr_uexp_t, and convert it to
+     mpfr_exp_t. */
+  uexp = (mpfr_uexp_t) zn * GMP_NUMB_BITS + (mpfr_uexp_t) e - k;
   /* The exponent will be exp or exp + 1 (due to rounding) */
-  if (MPFR_UNLIKELY (exp > __gmpfr_emax))
-    return mpfr_overflow (f, rnd_mode, sign_z);
-  if (MPFR_UNLIKELY (exp + 1 < __gmpfr_emin))
-    return mpfr_underflow (f, rnd_mode == MPFR_RNDN ? MPFR_RNDZ : rnd_mode,
-                           sign_z);
+  if (uexp <= MPFR_EXP_MAX)  /* non-negative */
+    {
+      if (MPFR_UNLIKELY (uexp > __gmpfr_emax))
+        return mpfr_overflow (f, rnd_mode, sign_z);
+      exp = uexp;
+    }
+  else  /* negative */
+    {
+      /* Convert to signed in a portable way (see doc/README.dev).
+         On most platforms, this can be optimized to identity (no-op). */
+      exp = -1 - (mpfr_exp_t) ~uexp;
+      if (MPFR_UNLIKELY (exp + 1 < __gmpfr_emin))
+        return mpfr_underflow (f,
+                               rnd_mode == MPFR_RNDN ? MPFR_RNDZ : rnd_mode,
+                               sign_z);
+    }
 
   if (MPFR_LIKELY (dif >= 0))
     {
diff --git a/tests/tset_z_exp.c b/tests/tset_z_exp.c
index 59cd88a01..ac26c4b06 100644
--- a/tests/tset_z_exp.c
+++ b/tests/tset_z_exp.c
@@ -140,6 +140,63 @@ check (long i, mpfr_rnd_t rnd)
   mpz_clear (z);
 }
 
+static void
+check_huge (void)
+{
+  if (getenv ("MPFR_CHECK_LARGEMEM") != NULL)
+    {
+      mpfr_t x;
+      mpz_t z;
+      long e;
+
+      /* Increase tests_memory_limit to the maximum in order to avoid
+         an obvious failure due to insufficient memory. */
+      tests_memory_limit = (size_t) -1;  /* no memory limit */
+
+      mpfr_init2 (x, 32);
+
+      /* In r14140, with a 32-bit ABI (GCC's -m32):
+         - With UBsan (-fsanitize=undefined -fno-sanitize-recover),
+           this fails with:
+             set_z_2exp.c:71:26: runtime error: signed integer overflow:
+             67108864 * 32 cannot be represented in type 'long int'
+         - With -D_MPFR_EXP_FORMAT=4, this fails with:
+             Expected 0.10001000000000000000000000000000E5
+             Got      0
+      */
+      mpz_init_set_ui (z, 17);
+      e = 0x7ffffff0;
+      mpz_mul_2exp (z, z, e);
+      mpz_add_ui (z, z, 1);
+      mpfr_set_z_2exp (x, z, -e, MPFR_RNDN);
+      if (mpfr_cmp_ui0 (x, 17) != 0)
+        {
+          printf ("Error 1 in check_huge\n");
+          printf ("Expected 0.10001000000000000000000000000000E5\n");
+          printf ("Got      ");
+          mpfr_dump (x);
+          exit (1);
+        }
+      mpz_clear (z);
+
+      mpz_init_set_ui (z, 17);
+      mpz_mul_2exp (z, z, 0xffffffb0);
+      mpz_add_ui (z, z, 1);
+      mpfr_set_z_2exp (x, z, -1, MPFR_RNDN);
+      if (! MPFR_IS_INF (x) || MPFR_IS_NEG (x))
+        {
+          printf ("Error 2 in check_huge\n");
+          printf ("Expected @Inf@\n");
+          printf ("Got      ");
+          mpfr_dump (x);
+          exit (1);
+        }
+      mpz_clear (z);
+
+      mpfr_clear (x);
+    }
+}
+
 int
 main (int argc, char *argv[])
 {
@@ -152,6 +209,8 @@ main (int argc, char *argv[])
     check (randlimb () & LONG_MAX, RND_RAND ());
   check0 ();
 
+  check_huge ();
+
   tests_end_mpfr ();
 
   return 0;