Bignums and .sleb128

Bignums and .sleb128

[Daniel Jacobowitz]

I spent most of this morning chasing a bug in .sleb128 support.  After
I finished running around in circles and discovered that Richard Sandiford
had fixed it two weeks ago (thanks!) I compared the testcases I'd written
with the ones that he committed.  There were a couple of differences,
basically related to this comment from bignum.h:

 *      Bignums are >= 0.                                               *

So generating a sleb128 from one is pretty strange - the sign bit is
ambiguously handled.  To see what I mean, try the attached patch to the
testsuite; several of the new tests fail.  Richard's patch adds this:

  /* Add a sequence of sign bits if the top bit of X_add_number is not
     the sign of the original value.  */
  if ((exp->X_add_number < 0) != !exp->X_unsigned)
    generic_bignum[i++] = exp->X_unsigned ? 0 : LITTLENUM_MASK;

which is pretty similar to what I did, but violates the documentation and (I
think) the expectations of various other bits of gas.  If we're going to use
these semantics, at least the '-' case in operand() needs to be fixed.

I consider the current state "still very broken".  Should we try to fix this
(I can't even see where to start; O_big has percolated into lots of strange
places, so changing its semantics would be tricky)?  Otherwise, can we
reject the internally ambiguous constructs?

The tests:

Index: testsuite/gas/all/sleb128.d
===================================================================
RCS file: /big/fsf/rsync/src-cvs/src/gas/testsuite/gas/all/sleb128.d,v
retrieving revision 1.2
diff -u -p -r1.2 sleb128.d
--- testsuite/gas/all/sleb128.d	24 Jan 2005 15:32:19 -0000	1.2
+++ testsuite/gas/all/sleb128.d	31 Jan 2005 19:21:44 -0000
@@ -52,6 +52,29 @@ Contents of section .data:
 # -0x100000000 :           111_0000 .....................................
 #    000000000 :           000_0000 0000_000 0_0000_00 00_0000_0 000_0000
 # -0x1000      :                             1_0000_00 00_0000_0
+#   fffffffff  :           111_1111 1111_111 1_1111_11 11_1111_1 111_1111 
+# 0xfffffff    : .................. 1111_111 1_1111_11 11_1111_1
 #
- 00.. 70808080 80808040 00000000 00000000 .*
+ 00.. 70808080 80808040 ffffffff ffffffff .*
+#
+# 0xfffffff    : 00_0000_1 111_1111 ............................
+#   fffffffff  :           111_1111 1111_111 1_1111_11 11_1111_1 111_1111 
+#   fffffffff  : 11_1111_1 111_1111 1111_111 1_1111_11 11_1111_1
+# 0xffffff     : 00_1111_1 111_1111 1111_111 1_1111_11
+#
+ 0... ff01ffff ffffffff ffffffff ffffff1f
+#
+#   fffffffff  :           000_0000 0000_000 0_0000_00 00_0000_0 000_0001
+# -0xfffffff   : 111_000_0 000_0000 0000_000 0_0000_00 00_0000_0
+#   fffffffff  :           000_0000 0000_000 0_0000_00 00_0000_0 000_0001
+#   fffffffff  : ..................................... 00_0000_0
+# -0xffffff    : .....................................
+#
+ 0... 81808080 80808080 80f08180 80808080 .*
+#
+#   fffffffff  :           ..............................................
+#   fffffffff  : 00_0000_0 000_0000 0000_000 0_0000_00 .........
+# -0xffffff    : 11_0000_0 000_0000 0000_000 0_0000_00
+#
+ 0... 80808080 80808060 00000000 00000000 .*
 #pass
Index: testsuite/gas/all/sleb128.s
===================================================================
RCS file: /big/fsf/rsync/src-cvs/src/gas/testsuite/gas/all/sleb128.s,v
retrieving revision 1.1
diff -u -p -r1.1 sleb128.s
--- testsuite/gas/all/sleb128.s	19 Jan 2005 11:53:53 -0000	1.1
+++ testsuite/gas/all/sleb128.s	31 Jan 2005 18:51:59 -0000
@@ -19,4 +19,9 @@
 	.sleb128	-0x100000000
 	.sleb128	-0x1000000000000
 
+	.sleb128	0xffffffffffffffff
+	.sleb128	0xffffffffffffffffffffffff
+	.sleb128	-0xffffffffffffffff
+	.sleb128	-0xffffffffffffffffffffffff
+
 	.fill		32


-- 
Daniel Jacobowitz

Re: Bignums and .sleb128

[Richard Sandiford]

Daniel Jacobowitz <drow@false.org> writes:
> I spent most of this morning chasing a bug in .sleb128 support.  After
> I finished running around in circles and discovered that Richard Sandiford
> had fixed it two weeks ago (thanks!) I compared the testcases I'd written
> with the ones that he committed.  There were a couple of differences,
> basically related to this comment from bignum.h:
>
>  *      Bignums are >= 0.                                               *

Ugh, didn't notice that, sorry.  But I think that comment fell by the
wayside the moment we tried to handle '-' for O_bigs.  After all, the
precision of bignums is completely arbitrary, so if the result of
-bignum is supposed to be unsigned, there's no obvious cut-off
point for the sign extension.

You said later that:

> If we're going to use these semantics, at least the '-' case in
> operand() needs to be fixed.

but I wasn't sure what you meant by "these semantics".  Do you mean
treating bignums as signed, or treating them as unsigned?  By my reading,
operand()'s current handling of '-' already assumes they are signed,
just like the sleb128 code does (and did ;).

> So generating a sleb128 from one is pretty strange - the sign bit is
> ambiguously handled.

Perhaps, but the problem isn't limited to sleb128.  E.g.:

	.quad	-0xffffffffffff

acts in the same way as ".quad 1", not ".quad 0xffff000000000001".

The direction of recent changes suggests there really is a need
for negative bignums, so IMO we should try to support them.

Richard

Re: Bignums and .sleb128

[Daniel Jacobowitz]

On Mon, Jan 31, 2005 at 09:32:46PM +0000, Richard Sandiford wrote:
> Daniel Jacobowitz <drow@false.org> writes:
> > I spent most of this morning chasing a bug in .sleb128 support.  After
> > I finished running around in circles and discovered that Richard Sandiford
> > had fixed it two weeks ago (thanks!) I compared the testcases I'd written
> > with the ones that he committed.  There were a couple of differences,
> > basically related to this comment from bignum.h:
> >
> >  *      Bignums are >= 0.                                               *
> 
> Ugh, didn't notice that, sorry.  But I think that comment fell by the
> wayside the moment we tried to handle '-' for O_bigs.  After all, the
> precision of bignums is completely arbitrary, so if the result of
> -bignum is supposed to be unsigned, there's no obvious cut-off
> point for the sign extension.

Yes.  I tried disabling that entirely, but it breaks the .quad and sleb
tests.

> You said later that:
> 
> > If we're going to use these semantics, at least the '-' case in
> > operand() needs to be fixed.
> 
> but I wasn't sure what you meant by "these semantics".  Do you mean
> treating bignums as signed, or treating them as unsigned?  By my reading,
> operand()'s current handling of '-' already assumes they are signed,
> just like the sleb128 code does (and did ;).

It doesn't work, because sometimes bignums are signed and sometimes
they aren't.  Consider -0xffffffffffff; the current code will return 1. 
If you want to treat the input as unsigned, then you need to add a new
word with the sign bit.  Note that with one less leading 'f', it
suddenly works.  So right now 2**64-1 is a negative bignum, and 2**48-1
is a negative bignum, and 2**56-1 is a positive bignum.

> > So generating a sleb128 from one is pretty strange - the sign bit is
> > ambiguously handled.
> 
> Perhaps, but the problem isn't limited to sleb128.  E.g.:
> 
> 	.quad	-0xffffffffffff
> 
> acts in the same way as ".quad 1", not ".quad 0xffff000000000001".
> 
> The direction of recent changes suggests there really is a need
> for negative bignums, so IMO we should try to support them.

I don't much care.  I was working on basically the same testcase you
were; GCC with long long HOST_WIDE_INT will output enumerators as
.sleb128 0xffffffff.  I just encountered all the other bogus bits when
I tried to write tests for .sleb128.

One approach to fix the problem would be to define X_unsigned as a
secondary "sign bit" for the bignum.  The core changes for that would
be easy.  It's the backends that bother me.

-- 
Daniel Jacobowitz

Re: Bignums and .sleb128

[Richard Sandiford]

Daniel Jacobowitz <drow@false.org> writes:
>> You said later that:
>> 
>> > If we're going to use these semantics, at least the '-' case in
>> > operand() needs to be fixed.
>> 
>> but I wasn't sure what you meant by "these semantics".  Do you mean
>> treating bignums as signed, or treating them as unsigned?  By my reading,
>> operand()'s current handling of '-' already assumes they are signed,
>> just like the sleb128 code does (and did ;).
>
> It doesn't work, because sometimes bignums are signed and sometimes
> they aren't.  Consider -0xffffffffffff; the current code will return 1. 
> If you want to treat the input as unsigned, then you need to add a new
> word with the sign bit.  Note that with one less leading 'f', it
> suddenly works.

Right, that's exactly the point I made later.  Like you say, if you
treat the bignum as signed (as the current '-' code does), then
{0xffff, 0xffff, 0xffff} is an invalid representation of a positive
number, it should be {0xffff, 0xffff, 0xffff, 0x0000} instead.
So the '-' code _does_ seem OK if you treat bignums as signed,
the problem is that the integer parsing code is still assuming
that bignums are unsigned, and that the extra 0x0000 littlenum
isn't needed.

I couldn't tell whether that's what you were saying too, or whether
you think that opcode() is wrong even if bignums are treated as signed.
It's quite possible we're in violent agreement here ;)

> One approach to fix the problem would be to define X_unsigned as a
> secondary "sign bit" for the bignum.  The core changes for that would
> be easy.  It's the backends that bother me.

I guess that's one way, but both existing bits of "bignums are signed"
code just use the top bit of the bignum as the sign bit.  Maybe that is
the most natural representation?

Richard

Re: Bignums and .sleb128

[Daniel Jacobowitz]

On Mon, Jan 31, 2005 at 10:17:56PM +0000, Richard Sandiford wrote:
> Daniel Jacobowitz <drow@false.org> writes:
> >> You said later that:
> >> 
> >> > If we're going to use these semantics, at least the '-' case in
> >> > operand() needs to be fixed.
> >> 
> >> but I wasn't sure what you meant by "these semantics".  Do you mean
> >> treating bignums as signed, or treating them as unsigned?  By my reading,
> >> operand()'s current handling of '-' already assumes they are signed,
> >> just like the sleb128 code does (and did ;).
> >
> > It doesn't work, because sometimes bignums are signed and sometimes
> > they aren't.  Consider -0xffffffffffff; the current code will return 1. 
> > If you want to treat the input as unsigned, then you need to add a new
> > word with the sign bit.  Note that with one less leading 'f', it
> > suddenly works.
> 
> Right, that's exactly the point I made later.  Like you say, if you
> treat the bignum as signed (as the current '-' code does), then
> {0xffff, 0xffff, 0xffff} is an invalid representation of a positive
> number, it should be {0xffff, 0xffff, 0xffff, 0x0000} instead.
> So the '-' code _does_ seem OK if you treat bignums as signed,
> the problem is that the integer parsing code is still assuming
> that bignums are unsigned, and that the extra 0x0000 littlenum
> isn't needed.
> 
> I couldn't tell whether that's what you were saying too, or whether
> you think that opcode() is wrong even if bignums are treated as signed.
> It's quite possible we're in violent agreement here ;)

I suppose that's one way to look at it.  If you assume that this code's
assumptions are correct, then it follows that this code is correct; the
bug is earlier.  There's still a bug, we've just rocked the terrarium a
bit :-)

> 
> > One approach to fix the problem would be to define X_unsigned as a
> > secondary "sign bit" for the bignum.  The core changes for that would
> > be easy.  It's the backends that bother me.
> 
> I guess that's one way, but both existing bits of "bignums are signed"
> code just use the top bit of the bignum as the sign bit.  Maybe that is
> the most natural representation?

Lots of places in the backend check that the bignum has a certain size.
These tests will break down with an additional sign-extension word.
Something's gotta give.

-- 
Daniel Jacobowitz

Re: Bignums and .sleb128

[Paul Schlie]

> Daniel Jacobowitz <drow@false.org> writes:
> >> You said later that:
> >> 
> >> > If we're going to use these semantics, at least the '-' case in
> >> > operand() needs to be fixed.
> >> 
> >> but I wasn't sure what you meant by "these semantics".  Do you mean
> >> treating bignums as signed, or treating them as unsigned?  By my reading,
> >> operand()'s current handling of '-' already assumes they are signed,
> >> just like the sleb128 code does (and did ;).
> > It doesn't work, because sometimes bignums are signed and sometimes
> > they aren't.  Consider -0xffffffffffff; the current code will return 1.
> > If you want to treat the input as unsigned, then you need to add a new
> > word with the sign bit.  Note that with one less leading 'f', it
> > suddenly works.

Strongly suspect that the proper idiom to is to treat all non-explicitly
negative constants as being unsigned values; where the point of confusion
is that with the exception of decimal numbers; binary, octal, and hex
digits directly correspond to N-bit patters which were likely specified
as such with the implicit intent they be preserved, the only remaining
ambiguity is whether the most-significant specified set-bit is intended
to be sign-extended if the value is stored with greater precision than
than the otherwise required as determined by the most-significant non-0
bit position i.e.:

  -0x1 == [1...]1, where [1...] represents the variable precision
  sign-extension of the most significant bit explicitly specified, which
  would otherwise only require a signed-bit-field:1, but would need to
  be sign extended to fill the remaining most-significant bits if stored
  with greater precision as may be required.

Thereby all constant values may be treated uniformly:

  +1 == +0b01 == +0x1 ...

  -1 == -0b01 == -0x1 ...

  +2 == +0b10 == +0x2 ...

  -2 == -0b10 == -0x2 ...


Which seems quite sensible.

  

Re: Bignums and .sleb128

[Paul Schlie]

So to be clearer:

 -1 == -0x1 == -0xF...

So: assuming signed char:8, short:16, int:32, etc.

 -1 == (signed char)+0xFF == (short)+0xFFFF == (int)+0xFFFFFFFF
 -1 == (signed char)-0xFF == (short)-0xFFFF == (int)-0xFFFFFFFF

and correspondingly:

   1 == (unsigned char)+0x1        == (unsigned short)+0x1, etc.
 255 == (unsigned char)-0x1, 65536 == (unsigned short)-0x1, etc.

As:

 +0xF == [0...]1111 == 15 (as non-explicitly negative constant is unsigned)
 -0xF == [1...]1111 == -1 (as  an explicitly negative constant is signed)


> From: Paul Schlie <schlie@comcast.net>
>> Daniel Jacobowitz <drow@false.org> writes:
>>>> You said later that:
>>>> 
>>>>> If we're going to use these semantics, at least the '-' case in
>>>>> operand() needs to be fixed.
>>>> 
>>>> but I wasn't sure what you meant by "these semantics".  Do you mean
>>>> treating bignums as signed, or treating them as unsigned?  By my reading,
>>>> operand()'s current handling of '-' already assumes they are signed,
>>>> just like the sleb128 code does (and did ;).
>>> It doesn't work, because sometimes bignums are signed and sometimes
>>> they aren't.  Consider -0xffffffffffff; the current code will return 1.
>>> If you want to treat the input as unsigned, then you need to add a new
>>> word with the sign bit.  Note that with one less leading 'f', it
>>> suddenly works.
> 
> Strongly suspect that the proper idiom to is to treat all non-explicitly
> negative constants as being unsigned values; where the point of confusion
> is that with the exception of decimal numbers; binary, octal, and hex
> digits directly correspond to N-bit patters which were likely specified
> as such with the implicit intent they be preserved, the only remaining
> ambiguity is whether the most-significant specified set-bit is intended
> to be sign-extended if the value is stored with greater precision than
> than the otherwise required as determined by the most-significant non-0
> bit position i.e.:
> 
>   -0x1 == [1...]1, where [1...] represents the variable precision
>   sign-extension of the most significant bit explicitly specified, which
>   would otherwise only require a signed-bit-field:1, but would need to
>   be sign extended to fill the remaining most-significant bits if stored
>   with greater precision as may be required.
> 
> Thereby all constant values may be treated uniformly:
> 
>   +1 == +0b01 == +0x1 ...
> 
>   -1 == -0b01 == -0x1 ...
> 
>   +2 == +0b10 == +0x2 ...
> 
>   -2 == -0b10 == -0x2 ...
> 
> 
> Which seems quite sensible.
> 
>   

Re: Bignums and .sleb128

[Paul Schlie]

(please accept my apologies, and disregard my ramblings)

> From: Paul Schlie <schlie@comcast.net>
> So to be clearer:
> 
>  -1 == -0x1 == -0xF...
> 
> So: assuming signed char:8, short:16, int:32, etc.
> 
>  -1 == (signed char)+0xFF == (short)+0xFFFF == (int)+0xFFFFFFFF
>  -1 == (signed char)-0xFF == (short)-0xFFFF == (int)-0xFFFFFFFF
> 
> and correspondingly:
> 
>    1 == (unsigned char)+0x1        == (unsigned short)+0x1, etc.
>  255 == (unsigned char)-0x1, 65536 == (unsigned short)-0x1, etc.
> 
> As:
> 
>  +0xF == [0...]1111 == 15 (as non-explicitly negative constant is unsigned)
>  -0xF == [1...]1111 == -1 (as  an explicitly negative constant is signed)
> 
> 
>> From: Paul Schlie <schlie@comcast.net>
>>> Daniel Jacobowitz <drow@false.org> writes:
>>>>> You said later that:
>>>>> 
>>>>>> If we're going to use these semantics, at least the '-' case in
>>>>>> operand() needs to be fixed.
>>>>> 
>>>>> but I wasn't sure what you meant by "these semantics".  Do you mean
>>>>> treating bignums as signed, or treating them as unsigned?  By my reading,
>>>>> operand()'s current handling of '-' already assumes they are signed,
>>>>> just like the sleb128 code does (and did ;).
>>>> It doesn't work, because sometimes bignums are signed and sometimes
>>>> they aren't.  Consider -0xffffffffffff; the current code will return 1.
>>>> If you want to treat the input as unsigned, then you need to add a new
>>>> word with the sign bit.  Note that with one less leading 'f', it
>>>> suddenly works.
>> 
>> Strongly suspect that the proper idiom to is to treat all non-explicitly
>> negative constants as being unsigned values; where the point of confusion
>> is that with the exception of decimal numbers; binary, octal, and hex
>> digits directly correspond to N-bit patters which were likely specified
>> as such with the implicit intent they be preserved, the only remaining
>> ambiguity is whether the most-significant specified set-bit is intended
>> to be sign-extended if the value is stored with greater precision than
>> than the otherwise required as determined by the most-significant non-0
>> bit position i.e.:
>> 
>>   -0x1 == [1...]1, where [1...] represents the variable precision
>>   sign-extension of the most significant bit explicitly specified, which
>>   would otherwise only require a signed-bit-field:1, but would need to
>>   be sign extended to fill the remaining most-significant bits if stored
>>   with greater precision as may be required.
>> 
>> Thereby all constant values may be treated uniformly:
>> 
>>   +1 == +0b01 == +0x1 ...
>> 
>>   -1 == -0b01 == -0x1 ...
>> 
>>   +2 == +0b10 == +0x2 ...
>> 
>>   -2 == -0b10 == -0x2 ...
>> 
>> 
>> Which seems quite sensible.
>> 
>>   

Re: Bignums and .sleb128

[Daniel Jacobowitz]

On Mon, Jan 31, 2005 at 07:52:59PM -0500, Paul Schlie wrote:
> > Daniel Jacobowitz <drow@false.org> writes:
> > >> You said later that:
> > >> 
> > >> > If we're going to use these semantics, at least the '-' case in
> > >> > operand() needs to be fixed.
> > >> 
> > >> but I wasn't sure what you meant by "these semantics".  Do you mean
> > >> treating bignums as signed, or treating them as unsigned?  By my reading,
> > >> operand()'s current handling of '-' already assumes they are signed,
> > >> just like the sleb128 code does (and did ;).
> > > It doesn't work, because sometimes bignums are signed and sometimes
> > > they aren't.  Consider -0xffffffffffff; the current code will return 1.
> > > If you want to treat the input as unsigned, then you need to add a new
> > > word with the sign bit.  Note that with one less leading 'f', it
> > > suddenly works.
> 
> Strongly suspect that the proper idiom to is to treat all non-explicitly
> negative constants as being unsigned values; where the point of confusion

This discussion is about the internal representation of bignums; the
user input is not ambiguous in any way.  The meaning of
  .sleb128 0xffffffffffffffff
is quite clear.


-- 
Daniel Jacobowitz