Left-shift of negative number

Left-shift of negative number

[Loïc Runarvot]

[-- Attachment #1: Type: text/plain, Size: 992 bytes --]


According to the C11 standard, doing a left-shift on a negative integer is considered as an undefined behavior (6.5.7:4).

This undefined behavior occurs in files src/multibyte/internal.c and src/multibyte/internal.h.
At line 21 in the header (http://git.musl-libc.org/cgit/musl/tree/src/multibyte/internal.h?id=0f9c2666aca95eb98eb0ef4f4d8d1473c8ce3fa0#n21),
the implementation of the macro-definition R allow to have a negative value on the expression ((a == 0x80) ? 0x40-b : -a) << 23.

In fact, in the source file, at the line 11 (http://git.musl-libc.org/cgit/musl/tree/src/multibyte/internal.c?id=0f9c2666aca95eb98eb0ef4f4d8d1473c8ce3fa0#n11).
During the application of the macro-definition R(0x90, 0xc0), we have a != 0x90, so it's try to do (-0x90) << 23, which is an undefined behavior.

This bug was found in the context of the libc cross-testing project (a post blog has been written on this subject yesterday: http://trust-in-soft.com/the-libc-cross-testing-project)


[-- Attachment #2: Type: text/html, Size: 1708 bytes --]

Re: Left-shift of negative number

[Jens Gustedt]

[-- Attachment #1: Type: text/plain, Size: 1410 bytes --]

Hello,

Am Freitag, den 17.07.2015, 18:28 +0000 schrieb Loïc Runarvot:
> According to the C11 standard, doing a left-shift on a negative
> integer is considered as an undefined behavior (6.5.7:4).

There is no such thing as "considered undefined behavior", this is a
terminology that makes not much sense. Unfortunately the term
"undefined behavior" is often used as a synonym for "errorneous code"
which it just isn't.

Effectively, the C standard at the place that you cite doesn't define
a behavior for such shifts of negative values. But this doesn't mean
that a particular implementation of a C compiler or the C library
(here musl) can't define a behavior for that.

What worries me more than the shift of a negative value, is that this
code is erroneous if `int` is only 16 bit wide. Whereas we can
reasonably assume that a shift of a negative value in two's complement
is the same as an unsigned shift, compilers tend to produce just crap
if the shift exceeds the width.

So I would feel much more comfortable if we'd use UINT32_C(0x40)
inside the R macro.

Jens

-- 
:: INRIA Nancy Grand Est ::: Camus ::::::: ICube/ICPS :::
:: ::::::::::::::: office Strasbourg : +33 368854536   ::
:: :::::::::::::::::::::: gsm France : +33 651400183   ::
:: ::::::::::::::: gsm international : +49 15737185122 ::
:: http://icube-icps.unistra.fr/index.php/Jens_Gustedt ::






[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 181 bytes --]

Re: Left-shift of negative number

[Alex]

> Effectively, the C standard at the place that you cite doesn't define
> a behavior for such shifts of negative values. But this doesn't mean
> that a particular implementation of a C compiler or the C library
> (here musl) can't define a behavior for that.

The problem is that some (hypothetical) standards-compliant C compiler
could define a behavior which isn't what musl intends. If such a
compiler ever came into existence and was used to build musl, the
resulting library could be subtly broken.

But if no such compiler is known to actually exist right now, does
anybody care? I don't know. Anyways, if the code can be adjusted to
avoid the dreaded "undefined behavior", without losing any
performance, it's probably better to do so.

AD

Re: Left-shift of negative number

[Rich Felker]

On Fri, Jul 17, 2015 at 09:02:59PM +0200, Jens Gustedt wrote:
> Effectively, the C standard at the place that you cite doesn't define
> a behavior for such shifts of negative values. But this doesn't mean
> that a particular implementation of a C compiler or the C library
> (here musl) can't define a behavior for that.

musl does not assume GCC behavior like this, so the code indeed is
wrong and should be fixed.

> What worries me more than the shift of a negative value, is that this
> code is erroneous if `int` is only 16 bit wide. Whereas we can
> reasonably assume that a shift of a negative value in two's complement
> is the same as an unsigned shift, compilers tend to produce just crap
> if the shift exceeds the width.
> 
> So I would feel much more comfortable if we'd use UINT32_C(0x40)
> inside the R macro.

The entire internal API here uses the type unsigned for character
codes and state, so like the rest of musl there is an assumption
(guaranteed by POSIX) that int is at least 32-bit. Since the
UTF-8/multibyte code is written to be largely self-contained and
independent of musl, we could look into enhancing the code to be
portable to systems with 16-bit int, but I suspect this would be
rather useless in practice. If we did that, we would need to use
something ugly like uint_least32_t rather than uint32_t to gain any
portability since the latter need not even exist.

There are also aliasing issues with using a type different than
'unsigned' for the decoding state since mbstate_t's members are
unsigned. So at least at this time I'd really rather not pursue this
further.

Rich

Re: Left-shift of negative number

[ibid.ag]

On Fri, Jul 17, 2015 at 05:35:22PM -0400, Rich Felker wrote:
> > What worries me more than the shift of a negative value, is that this
> > code is erroneous if `int` is only 16 bit wide. Whereas we can
> > reasonably assume that a shift of a negative value in two's complement
> > is the same as an unsigned shift, compilers tend to produce just crap
> > if the shift exceeds the width.
> > 
> > So I would feel much more comfortable if we'd use UINT32_C(0x40)
> > inside the R macro.
> 
> The entire internal API here uses the type unsigned for character
> codes and state, so like the rest of musl there is an assumption
> (guaranteed by POSIX) that int is at least 32-bit. Since the
> UTF-8/multibyte code is written to be largely self-contained and
> independent of musl, we could look into enhancing the code to be
> portable to systems with 16-bit int, but I suspect this would be
> rather useless in practice. If we did that, we would need to use
> something ugly like uint_least32_t rather than uint32_t to gain any
> portability since the latter need not even exist.

As far as I know, 16-bit int is applicable to the following platforms:
-Some ports of certain RTOSes to 8 or 16 bit microcontrollers
 (ie, FreeRTOS and perhaps eCos)
-DOS, when *not* using GCC (DJGPP uses 32-bit int); this boils down to
 OpenWatcom, the old C89 compilers, and even older K&R-ish compilers.
-FUZIX
-ELKS
-Minix (8086 version)
-Xenix and other old commercial 16-bit *nixes

FUZIX uses sdcc, which is an incomplete C89-ish compiler.
ELKS uses a K&R compiler that can be used with a preprocessor
to compile some C89 code.
Old *nixes use K&R C.
8086 Minix uses ACK, which is C89; there's an experimental port of
PCC to the 8086, but that's a long way from being useable right now.
(Alan Cox is working on it part time so he can port FUZIX to the PC.)

In short, the possible compilers are OpenWatcom, or various bits
that are C89 at best (can't rely on uint* being available at all,
short of a custom "limits.h").

I'm not sure if OpenWatcom uses 16-bit int when building in 32-bit mode;
the compatability with HXRT would suggest that it doesn't.
So to make it meaningful, you would have to make it work with segmented
memory and probably C89.

Odd as it may sound, there are people using UTF on DOS (the Blocek text
editor comes to mind); but I'm not aware of interest in UTF on 16-bit DOS.


Thanks,
Isaac Dunham

Re: Left-shift of negative number

[Rich Felker]

On Fri, Jul 17, 2015 at 06:28:00PM +0000, Loïc Runarvot wrote:
> 
> According to the C11 standard, doing a left-shift on a negative
> integer is considered as an undefined behavior (6.5.7:4).
> 
> This undefined behavior occurs in files src/multibyte/internal.c and
> src/multibyte/internal.h. At line 21 in the header
> (http://git.musl-libc.org/cgit/musl/tree/src/multibyte/internal.h?id=0f9c2666aca95eb98eb0ef4f4d8d1473c8ce3fa0#n21),
> the implementation of the macro-definition R allow to have a
> negative value on the expression ((a == 0x80) ? 0x40-b : -a) << 23.
> 
> In fact, in the source file, at the line 11
> (http://git.musl-libc.org/cgit/musl/tree/src/multibyte/internal.c?id=0f9c2666aca95eb98eb0ef4f4d8d1473c8ce3fa0#n11).
> During the application of the macro-definition R(0x90, 0xc0), we
> have a != 0x90, so it's try to do (-0x90) << 23, which is an
> undefined behavior.

Thank you. Reporting of such issues is very welcome, as it is the
intent in musl to avoid undefined behavior regardless of whether it's
believed to cause problems with current compilers. The cleanest
solution is probably to use unsigned arithmetic here (e.g. replace -a
with 0u-a or -(unsigned)a) but I'd like to look at the code in more
detail again and check all of the consequences before committing to a
particular approach to fixing it.

> This bug was found in the context of the libc cross-testing project
> (a post blog has been written on this subject yesterday:
> http://trust-in-soft.com/the-libc-cross-testing-project)

The link doesn't seem to be working for me. I'd like to hear more
about this project, so please let me know if there's somewhere else I
can find info or if there's a corrected link that works.

Rich

Re: Left-shift of negative number

[Rich Felker]

On Fri, Jul 17, 2015 at 05:28:58PM -0400, Rich Felker wrote:
> On Fri, Jul 17, 2015 at 06:28:00PM +0000, Loïc Runarvot wrote:
> > 
> > According to the C11 standard, doing a left-shift on a negative
> > integer is considered as an undefined behavior (6.5.7:4).
> > 
> > This undefined behavior occurs in files src/multibyte/internal.c and
> > src/multibyte/internal.h. At line 21 in the header
> > (http://git.musl-libc.org/cgit/musl/tree/src/multibyte/internal.h?id=0f9c2666aca95eb98eb0ef4f4d8d1473c8ce3fa0#n21),
> > the implementation of the macro-definition R allow to have a
> > negative value on the expression ((a == 0x80) ? 0x40-b : -a) << 23.
> > 
> > In fact, in the source file, at the line 11
> > (http://git.musl-libc.org/cgit/musl/tree/src/multibyte/internal.c?id=0f9c2666aca95eb98eb0ef4f4d8d1473c8ce3fa0#n11).
> > During the application of the macro-definition R(0x90, 0xc0), we
> > have a != 0x90, so it's try to do (-0x90) << 23, which is an
> > undefined behavior.
> 
> Thank you. Reporting of such issues is very welcome, as it is the
> intent in musl to avoid undefined behavior regardless of whether it's
> believed to cause problems with current compilers. The cleanest
> solution is probably to use unsigned arithmetic here (e.g. replace -a
> with 0u-a or -(unsigned)a) but I'd like to look at the code in more
> detail again and check all of the consequences before committing to a
> particular approach to fixing it.

This looks like the best approach, and the macro is only used in
initializers so it was easy to confirm that the object file is not
changed. I also considered replacing <<23 with *(1<<23), which is a
standard idiom I'd like to promote for working around the standard's
failure to define left-shift of negative numbers properly, but
ensuring that the multiplication doesn't overflow is non-trivial
without re-examining the logic, so I'd rather just work with unsigned
arithmetic.

I've gone ahead and made the change as commit
fe7582f4f92152ab60e9523bf146fe28ceae51f6. If anything looks wrong,
please let me know. Thanks again for the bug report.

Rich

Re: Left-shift of negative number

[Alexander Cherepanov]

On 2015-07-25 06:22, Rich Felker wrote:
> On Fri, Jul 17, 2015 at 05:28:58PM -0400, Rich Felker wrote:
>> On Fri, Jul 17, 2015 at 06:28:00PM +0000, Loïc Runarvot wrote:
>>>
>>> According to the C11 standard, doing a left-shift on a negative
>>> integer is considered as an undefined behavior (6.5.7:4).
>>>
>>> This undefined behavior occurs in files src/multibyte/internal.c and
>>> src/multibyte/internal.h. At line 21 in the header
>>> (http://git.musl-libc.org/cgit/musl/tree/src/multibyte/internal.h?id=0f9c2666aca95eb98eb0ef4f4d8d1473c8ce3fa0#n21),
>>> the implementation of the macro-definition R allow to have a
>>> negative value on the expression ((a == 0x80) ? 0x40-b : -a) << 23.
>>>
>>> In fact, in the source file, at the line 11
>>> (http://git.musl-libc.org/cgit/musl/tree/src/multibyte/internal.c?id=0f9c2666aca95eb98eb0ef4f4d8d1473c8ce3fa0#n11).
>>> During the application of the macro-definition R(0x90, 0xc0), we
>>> have a != 0x90, so it's try to do (-0x90) << 23, which is an
>>> undefined behavior.
>>
>> Thank you. Reporting of such issues is very welcome, as it is the
>> intent in musl to avoid undefined behavior regardless of whether it's
>> believed to cause problems with current compilers. The cleanest
>> solution is probably to use unsigned arithmetic here (e.g. replace -a
>> with 0u-a or -(unsigned)a) but I'd like to look at the code in more
>> detail again and check all of the consequences before committing to a
>> particular approach to fixing it.
>
> This looks like the best approach, and the macro is only used in
> initializers so it was easy to confirm that the object file is not
> changed. I also considered replacing <<23 with *(1<<23), which is a
> standard idiom I'd like to promote for working around the standard's
> failure to define left-shift of negative numbers properly, but
> ensuring that the multiplication doesn't overflow is non-trivial
> without re-examining the logic, so I'd rather just work with unsigned
> arithmetic.
>
> I've gone ahead and made the change as commit
> fe7582f4f92152ab60e9523bf146fe28ceae51f6. If anything looks wrong,
> please let me know. Thanks again for the bug report.

The new definition of R:

#define R(a,b) ((uint32_t)((a==0x80 ? 0x40u-b : 0u-a) << 23))

It implicitly casts a and b to unsigned (and triggers 
-Wsign-conversion). Isn't it better to express it explicitly, e.g. by 
moving the cast to uint32_t inside the conditional operator? Or maybe 
more intuitive to move the work with negative numbers outside the 
conditional operator:

#define R(a,b) (-(uint32_t)(a==0x80 ? b-0x40 : a) << 23)

While at it, maybe change -1 to -1u in the definition of C in internal.c 
(triggers -Wsign-compare)?

-- 
Alexander Cherepanov

Re: Left-shift of negative number

[Rich Felker]

On Sat, Jul 25, 2015 at 09:26:34PM +0300, Alexander Cherepanov wrote:
> >I've gone ahead and made the change as commit
> >fe7582f4f92152ab60e9523bf146fe28ceae51f6. If anything looks wrong,
> >please let me know. Thanks again for the bug report.
> 
> The new definition of R:
> 
> #define R(a,b) ((uint32_t)((a==0x80 ? 0x40u-b : 0u-a) << 23))
> 
> It implicitly casts a and b to unsigned (and triggers
> -Wsign-conversion). Isn't it better to express it explicitly, e.g.

Using implicit conversion to unsigned types is idiomatic in musl; we
don't use -Wsign-comparison or similar in the default CFLAGS. A
discussion about changing that should be library-global, not specific
to this one piece of code, but I'd rather not anyway. My view is that
there's a tradeoff between using implicit conversions and casts: using
the implicit conversions (and leaving off warnings for them) could
hide bugs from wrong expectations about types, but using casts can
hide much more dangerous conversions for which an implicit conversion
would not even be possible. I generally like to keep the number of
casts to a minimum.

> by moving the cast to uint32_t inside the conditional operator? Or
> maybe more intuitive to move the work with negative numbers outside
> the conditional operator:
> 
> #define R(a,b) (-(uint32_t)(a==0x80 ? b-0x40 : a) << 23)

This actually would give the wrong result -- and strictly speaking,
even worse, undefined behavior -- if uint32_t had lower rank than int.
While other parts of musl assume 32-bit int for Linux-specific reasons
(advanced parts of the futex API, etc.) I'd rather leave this code
only assuming that int is >=32bit rather than exactly 32-bit.

Rich

Re: Left-shift of negative number

[Alexander Cherepanov]

On 2015-07-26 19:53, Rich Felker wrote:
> On Sat, Jul 25, 2015 at 09:26:34PM +0300, Alexander Cherepanov wrote:
>>> I've gone ahead and made the change as commit
>>> fe7582f4f92152ab60e9523bf146fe28ceae51f6. If anything looks wrong,
>>> please let me know. Thanks again for the bug report.
>>
>> The new definition of R:
>>
>> #define R(a,b) ((uint32_t)((a==0x80 ? 0x40u-b : 0u-a) << 23))
>>
>> It implicitly casts a and b to unsigned (and triggers
>> -Wsign-conversion). Isn't it better to express it explicitly, e.g.
>
> Using implicit conversion to unsigned types is idiomatic in musl; we

Sorry, I didn't know it.

> don't use -Wsign-comparison or similar in the default CFLAGS. A
> discussion about changing that should be library-global, not specific
> to this one piece of code, but I'd rather not anyway. My view is that
> there's a tradeoff between using implicit conversions and casts: using
> the implicit conversions (and leaving off warnings for them) could
> hide bugs from wrong expectations about types, but using casts can
> hide much more dangerous conversions for which an implicit conversion
> would not even be possible. I generally like to keep the number of
> casts to a minimum.

It would be interesting to read when and if you have time to write about 
it in more details.

>> by moving the cast to uint32_t inside the conditional operator? Or
>> maybe more intuitive to move the work with negative numbers outside
>> the conditional operator:
>>
>> #define R(a,b) (-(uint32_t)(a==0x80 ? b-0x40 : a) << 23)
>
> This actually would give the wrong result -- and strictly speaking,
> even worse, undefined behavior -- if uint32_t had lower rank than int.
> While other parts of musl assume 32-bit int for Linux-specific reasons
> (advanced parts of the futex API, etc.) I'd rather leave this code
> only assuming that int is >=32bit rather than exactly 32-bit.

Ok, thanks for the explanation.

-- 
Alexander Cherepanov

Re: Left-shift of negative number

[Pascal Cuoq]

Jens Gustedt wrote:

> Am Freitag, den 17.07.2015, 18:28 +0000 schrieb Loïc Runarvot:
> > According to the C11 standard, doing a left-shift on a negative
> > integer is considered as an undefined behavior (6.5.7:4).
> 
> There is no such thing as "considered undefined behavior",

You are right, the word “considered” is unnecessary.
A left shift on a negative integer is undefined behavior, period.

> this is a
> terminology that makes not much sense. Unfortunately the term
> "undefined behavior" is often used as a synonym for "errorneous code"
> which it just isn't.

But in this case, it is used as a synonym for “being undefined behavior”,
which it is. Or are we reading the phrase “otherwise, the behavior is undefined”
in the relevant clause of the standard differently?

I know that this is not well-known, so perhaps I should explain: ever since
the late 1990s, C compilers have been taking advantage of undefined behavior
in the C standard to introduce new optimizations. So if you rely on undefined
behavior in your C programs, they may not work today, and they may break
tomorrow. For instance, a claim very similar to yours:

> Whereas we can
> reasonably assume that a shift of a negative value in two's complement
> is the same as an unsigned shift,

may be used to justify that INT_MAX + 1 results in INT_MIN on two's
complement platforms. This line of reasoning does not work too well nowadays,
as anyone who has ever read the assembly generated by a modern optimizing
compiler for the function int f(int x) { return x + 1 > x; } has verified for
themselves.

So what about shifts of negative values then? Should we worry that they
will be broken in 2017? No, there is no need to wait.

According to this post, ICC takes full advantage today of the fact
that they are undefined behavior:

http://stackoverflow.com/questions/22883790/left-shift-of-negative-values

And according to one slide in this deck, MSVC does too(*):

http://fsl.cs.illinois.edu/images/2/27/2011-09-30-CK-MVD.pdf

> But this doesn't mean
> that a particular implementation of a C compiler or the C library
> (here musl) can't define a behavior for that.

I sincerely do not think that it's not musl's place to define the behavior
of -1 << 1, until it comes bundled with a C compiler, because until
then, the behavior of that expression is entirely without its control
and entirely within the control of unsympathetic C compilers that have
the C standard on their side. Also the phrase
“strives to be correct in the sense of standards-conformance…”
would need to be amended to something like “works with at least
two GCC-like C compilers”.

Pascal

(*) by the way, do not remember anything that these slides say about
Frama-C. The authors of the slides, when talking about it, have no idea
what the f-word they are talking about, and they have a research the usefulness
of which they conveniently want to impress you with.