Re: Patch ping

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

> I believe that the last sixty years of digital computation have
> decisively shown the superiority of two's complement arithmetic
> for representing signed integers as binary, and convenient for
> interconversion with unsigned values.

yes, this is why I have chosen to use it (well, why I haven't considered
any other in the first place).

> You should treat double_int like you would a TImode.  For example, -1
> should be represented by both the high an low words containing all one
> bits.

This is quite orthogonal issue to whether to use two's complement
arithmetic or something else.  As far as I understand, this is the
main point of your objection, so I will focus on it.  There are several
basic properties I want double_int to satisfy:

1) it is possible to represent numbers with smaller precision than
   2 * HOST_BITS_PER_WIDE_INT
2) it is not neccessary to distinguish between signed and unsigned
   values in functions that perform arithmetics modulo 2^precision
   (+, -, *, negation,...)
3) each number has only one possible representation.

I will for now assume that we agree on that these are desirable; if not,
I will present my arguments on this issue in the followup mail(s).

1) and 3) leave us with basically three choices of how to represent the
numbers; avoiding long explanation, let us demonstrate these on
examples, say we want to represent 8-bit values:

-- (a):
   unsigned 127 = signed 127 = {0, 127}
   unsigned 255 = signed -1 = {0, 255}
-- (b)
   unsigned 127 = signed 127 = {0, 127}
   unsigned 255 = signed -1 = {-1, -1}
-- (c)
   unsigned 127 = signed 127 = {0, 127}
   unsigned 255 = {0,255}
   signed -1 = {-1, -1}

My choice is (a).  Your choice seems to be either (b) or (c), you are
not quite clear about it.  By property 2, it would be nice for signed
and unsigned numbers with the same precision to have the same
representation (use the same range of numbers); this leaves only (a) and
(b) as possibilities.

Regardless of the choice, because of 3) you need to have some normalization of the
results of the operation -- e.g., in representation (b), 127 + 127 = 254 = {-1, -2},
but add_double would return {0,254}.  In representation (a), -1 + -1 = -2 = {0,254},
but add_double would return {0, 510}.

For (a), this normalization is X & MASK.  For (b), it is
if (X & (1<< (prec - 1)) == 0) ? X & MASK : X | ~MASK.
Between (a) and (b), I have chosen (a) as the normalization is simpler.

> + /* Returns true if CST is minus one in precision of MASK.  */
> +
> + static inline bool
> + double_int_minus_one_p (double_int mask, double_int cst)
> + {
> +   return (DI_LOW (cst) == DI_LOW (mask)
> + 	  && DI_HIGH (cst) == DI_HIGH (mask));
> + }
> 
> Then you wouldn't need a mask to test for minus one!
>
> + /* Returns true if SCALE is negative in precision of MASK.  */
> +
> + bool
> + double_int_negative_p (double_int mask, double_int scale)
> + {
> +   if (DI_HIGH (mask))
> +     return (DI_HIGH (scale) & ~(DI_HIGH (mask) >> 1)) != 0;
> +   else
> +     return (DI_LOW (scale) & ~(DI_LOW (mask) >> 1)) != 0;
> + }
> 
> And you wouldn't have to do pass in a mask to determine whether
> a value is negative.

yes, this is about the only real advantage of the representation (b).

> You would be able to implement a signed comparison, which is
> not so mysteriously missing from from your patch.

You would still need to distinguish between signed and unsigned versions
of the comparison, at the very least for numbers whose precision is
exactly 2 * HOST_BITS_PER_WIDE_INT.

The reason I do not implement signed comparison is that I do not need it
anywhere, not because it would be somehow fundamentally harder than the
unsigned case.

> But most importantly....
> 
> +   mul_double (DI_LOW (a), DI_HIGH (a),
> +               DI_LOW (b), DI_HIGH (b), &lo, &hi);
> ...
> +   add_double (DI_LOW (a), DI_HIGH (a),
> + 	      DI_LOW (b), DI_HIGH (b), &lo, &hi);
> ...
> +   neg_double (DI_LOW (a), DI_HIGH (a), &lo, &hi);
> ...
> +   div_and_round_double (FLOOR_DIV_EXPR, true,
> + 			DI_LOW (a), DI_HIGH (a),
> + 			DI_LOW (b), DI_HIGH (b),
> + 			&lo, &hi, &rem_lo, &rem_hi);
> 
> You'll now get the correct results out of all of these routines, which
> assume the same sign-extended two's complement representation of
> integers as used in the rest of the compiler, and the vast majority
> of the rest of the planet.

Regardless of whether the representation you choose is (a), (b), or (c),
you need to do some normalization of the result.  This is simplest for
(a) -- just mask out bits outside of the precision, more complicated for
(b) -- you need to do sign extension, and even more quite complex for (c)
(you need to distinguish between the signed and unsigned cases).

Zdenek