This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[wide-int] Fix some division cases


divmod_internal didn't handle unsigned division in which the inputs
have implicit all-one upper bits.  There were two problems:

- wi_unpack should extend implicit 1s to index blocks_needed - 1
  (possibly with a zext_hwi on the last block for small_prec)
  regardless of signedness

- when calculating m and n, divmod_internal only used the
  *_blocks_needed value if the division was signed.  Neither is value
  is really signed in this context, since we've already calculated
  absolute values if sgnop == SIGNED, so the neg_p (and its pre-wi::
  incarnation) would only have held for the minimum integer.

  Using a simple while loop to find the top half-HWI seems more direct.

Also, divmod_internal_2 took n and m as unsigned values but used
HOST_WIDE_INT iterators on m - n.  m can be less than n for
things like 0 / big, and the negative m - n was being treated
as an unsigned int and zero-extended to HOST_WIDE_INT.
The patch fixes both the types of n and m and the types
of the iterators.

Tested on x86_64-linux-gnu and powerpc64-linux-gnu.  OK to install?

Thanks,
Richard


Index: gcc/wide-int.cc
===================================================================
--- gcc/wide-int.cc	2014-05-02 16:28:09.560842845 +0100
+++ gcc/wide-int.cc	2014-05-02 16:40:40.002916374 +0100
@@ -1126,8 +1126,7 @@ wi::add_large (HOST_WIDE_INT *val, const
    HOST_HALF_WIDE_INTs of RESULT.  The rest of RESULT is filled by
    uncompressing the top bit of INPUT[IN_LEN - 1].  */
 static void
-wi_unpack (unsigned HOST_HALF_WIDE_INT *result,
-	   const unsigned HOST_WIDE_INT *input,
+wi_unpack (unsigned HOST_HALF_WIDE_INT *result, const HOST_WIDE_INT *input,
 	   unsigned int in_len, unsigned int out_len,
 	   unsigned int prec, signop sgn)
 {
@@ -1145,20 +1144,24 @@ wi_unpack (unsigned HOST_HALF_WIDE_INT *
   else
     mask = 0;
 
-  for (i = 0; i < in_len; i++)
+  for (i = 0; i < blocks_needed - 1; i++)
     {
-      HOST_WIDE_INT x = input[i];
-      if (i == blocks_needed - 1 && small_prec)
-	{
-	  if (sgn == SIGNED)
-	    x = sext_hwi (x, small_prec);
-	  else
-	    x = zext_hwi (x, small_prec);
-	}
+      HOST_WIDE_INT x = safe_uhwi (input, in_len, i);
       result[j++] = x;
       result[j++] = x >> HOST_BITS_PER_HALF_WIDE_INT;
     }
 
+  HOST_WIDE_INT x = safe_uhwi (input, in_len, i);
+  if (small_prec)
+    {
+      if (sgn == SIGNED)
+	x = sext_hwi (x, small_prec);
+      else
+	x = zext_hwi (x, small_prec);
+    }
+  result[j++] = x;
+  result[j++] = x >> HOST_BITS_PER_HALF_WIDE_INT;
+
   /* Smear the sign bit.  */
   while (j < out_len)
     result[j++] = mask;
@@ -1317,10 +1320,8 @@ wi::mul_internal (HOST_WIDE_INT *val, co
     }
 
   /* We do unsigned mul and then correct it.  */
-  wi_unpack (u, (const unsigned HOST_WIDE_INT *) op1val, op1len,
-	     half_blocks_needed, prec, SIGNED);
-  wi_unpack (v, (const unsigned HOST_WIDE_INT *) op2val, op2len,
-	     half_blocks_needed, prec, SIGNED);
+  wi_unpack (u, op1val, op1len, half_blocks_needed, prec, SIGNED);
+  wi_unpack (v, op2val, op2len, half_blocks_needed, prec, SIGNED);
 
   /* The 2 is for a full mult.  */
   memset (r, 0, half_blocks_needed * 2
@@ -1519,7 +1520,7 @@ divmod_internal_2 (unsigned HOST_HALF_WI
 		   unsigned HOST_HALF_WIDE_INT *b_remainder,
 		   unsigned HOST_HALF_WIDE_INT *b_dividend,
 		   unsigned HOST_HALF_WIDE_INT *b_divisor,
-		   unsigned int m, unsigned int n)
+		   int m, int n)
 {
   /* The "digits" are a HOST_HALF_WIDE_INT which the size of half of a
      HOST_WIDE_INT and stored in the lower bits of each word.  This
@@ -1530,7 +1531,8 @@ divmod_internal_2 (unsigned HOST_HALF_WI
   unsigned HOST_WIDE_INT qhat;   /* Estimate of quotient digit.  */
   unsigned HOST_WIDE_INT rhat;   /* A remainder.  */
   unsigned HOST_WIDE_INT p;      /* Product of two digits.  */
-  HOST_WIDE_INT s, i, j, t, k;
+  HOST_WIDE_INT t, k;
+  int i, j, s;
 
   /* Single digit divisor.  */
   if (n == 1)
@@ -1757,26 +1759,17 @@ wi::divmod_internal (HOST_WIDE_INT *quot
 	}
     }
 
-  wi_unpack (b_dividend, (const unsigned HOST_WIDE_INT *) dividend.get_val (),
-	     dividend.get_len (), dividend_blocks_needed, dividend_prec, sgn);
-  wi_unpack (b_divisor, (const unsigned HOST_WIDE_INT *) divisor.get_val (),
-	     divisor.get_len (), divisor_blocks_needed, divisor_prec, sgn);
-
-  if (wi::neg_p (dividend, sgn))
-    m = dividend_blocks_needed;
-  else
-    m = 2 * dividend.get_len ();
+  wi_unpack (b_dividend, dividend.get_val (), dividend.get_len (),
+	     dividend_blocks_needed, dividend_prec, sgn);
+  wi_unpack (b_divisor, divisor.get_val (), divisor.get_len (),
+	     divisor_blocks_needed, divisor_prec, sgn);
+
+  m = dividend_blocks_needed;
+  while (m > 1 && b_dividend[m - 1] == 0)
+    m--;
 
-  if (wi::neg_p (divisor, sgn))
-    n = divisor_blocks_needed;
-  else
-    n = 2 * divisor.get_len ();
-
-  /* We need to find the top non zero block of b_divisor.  At most the
-     top two blocks are zero.  */
-  if (b_divisor[n - 1] == 0)
-    n--;
-  if (b_divisor[n - 1] == 0)
+  n = divisor_blocks_needed;
+  while (n > 1 && b_divisor[n - 1] == 0)
     n--;
 
   memset (b_quotient, 0, sizeof (b_quotient));



Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]