[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
Re: [wide-int] Fix some division cases
this is fine.
On 05/02/2014 03:22 PM, Richard Sandiford wrote:
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_divide
