Hacker News Reader

Comment by Joker_vD | Hacker News Reader

Also, C23 (and C2y) is moving ever closer to actually having defined semantics. As in, "just because one branch of your code, for this particular input, has read a value out of an array's bounds, your whole program's execution doesn't suddenly rewinds back to the start (with I/O included) and NOPs/loops infinitely/executes random bytes after main()".

Also, I'm personally still waiting for a "shift left" operator having cleaner wording in the standard:

    If E1 has an unsigned type, the value of the result is E1 × 2**E2, wrapped
    around. If E1 has a signed type and nonnegative value, and E1 × 2**E2 is
    representable in the result type, then that is the resulting value; otherwise,
    the behavior is undefined.

What does "otherwise" means here? It can't mean "if E1 has an unsigned type, or negative value, or E1 × 2**E2 is unrepresentable, then the behavior is undefined" because the part "if E1 has an unsigned type" has already been covered by the previous clause. Does it mean "If E1 has negative value, or E1 × 2**E2 is unrepresentable, then the behavior is undefined"? Because that's a ridiculous ordinance: (-1) << 1 is UB?!

View on HN

> Does it mean "If E1 has negative value, or E1 × 2*E2 is unrepresentable, then the behavior is undefined"? Because that's a ridiculous ordinance.

That's exactly what it means, see the change mentioned in https://www.open-std.org/jtc1/sc22/wg14/www/docs/n723.htm. (Previously, in C89, left shift on signed integers was completely undefined, only unsigned integers had a defined left-shift operation.) My guess is that it has to do with signed-magnitude representation causing left shifts to be absolute garbage with negative numbers. You also have to remember that the standard having undefined behavior doesn't preclude implementations from defining that behavior, and this is especially true with the freewheeling nature of a lot of the original undefined behavior introduced in C89 and C99.

> Also, C23 (and C2y) is moving ever closer to actually having defined semantics.

Eh, having seen how some of the sausage gets made, there's definitely been some cases where the overeager urge to rip out undefined behavior from the standard has worsened the quality.

Well, you could start to help? (instead of just being there to make sure special interests are preserved in voting)

I also do not see where the quality suffered. There were some rather minor issues we created and need to cleaned up.

> (instead of just being there to make sure special interests are preserved in voting)

This kind of attitude tends to make me suspect that you are disinclined to actually listen to my feedback.

Prove it. Aaron told me explicitly that he was inviting people because he was not happy that there are too many with a user view point. And then a couple people show up that never contribute papers but consistently vote for some special interest.

Just as a recent example. There is a case where the standard obviously is broken . With a lot of support by most of the committee and actual work by a couple of people there is a paper that aims to fix it. The only people who never constructively helped but still vote against this important repair is your block of other non-contributing people you are part of: https://github.com/c-lang-org/polls/blob/main/n3909.md

(Also a counter proposal would be constructive.)

But I apologize, I should not be so negative. But I hope you see where the frustration comes from. The cleanup efforts are driven by a lot of volunteer work. We could use any help and instead of people just voting against such works.

> 404

Very informative, thanks

yes, internal link. It is about discarded: https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3909.htm

The complaint that has been brought up there--repeatedly--is that the term 'discarded' creates confusion with the similar 'discarded-value expression' in C++, which is completely different semantically despite the similar name.

I joined WG14 and WG21 because I was worried that there were not enough people on either committees who had the perspective of someone who works in middle-end optimization rather than the frontend. I haven't written any papers for WG14 because so far all of the feedback I need to give can easily be given merely by discussion on the reflector or during the paper discussions (this is not the case for WG21, and I have consequently written papers for them), and--as a middle-end person--there is actually relatively little feature development for me to specifically propose. Most of the big features I'd want to see included already have active proposals (e.g., _Vec) and there's little reason for me to write a different proposal. Maybe you'll eventually see a paper from me if I take up some of the proposal work for CFP, or if I get around to writing a version of restrict that's based off of the Tree Borrows model. Or maybe if I turn some of my thoughts on multiple return values into a paper, though I don't actually have a proper frontend proposal for that that I like, so it's more likely to remain a reflector message.

Yes, thanks. Sorry I am not trying to be hostile, I am just a little bit annoyed about the lack of progress we have in some areas.

> My guess is that it has to do with signed-magnitude representation causing left shifts to be absolute garbage with negative numbers.

First of all, why not make it implementation-defined? That seems rather more useful for the programmer. Second, I'm personally aware of only a single machine with signed-magnitude representation, IBM 7090, and its ALS (Accumulator Left Shift) instruction treated the sign bit as sticky; amusingly, LGL (Logical Shift Left) did as well, so you had to put the value being shifted into the MQ register, not the accumulator, when you wanted an unsigned shift. So... no, that can't be it?

One of the tricky things is that undefined behavior is commonly understood as having an unlimited "blast radius" and implementation-defined behavior is commonly understood as not permitting that kind of "blast radius." So any extension point that needed that unlimited "blast radius" had to be undefined behavior. (This has changed somewhat in modern times, but it does hold a little bit today--I'd point you to the discussion of N3863 at the most recent meeting, but I don't have any minutes that I feel really captured that discussion well enough.)

And one of those kinds of "blast radius" is traps, and I suspect the original motivation for making signed integer overflow undefined behavior was precisely to preserve the ability to trap on signed integer overflow, which couldn't be implementation-defined. But the records of the discussions leading up to C89 and C99 are just too fragmentary for me to be certain.

The problem with UB, as evidenced over the years, is that it causes compiler writers to drift much too far from reality, despite the standard itself suggesting "behaving [...] in a documented manner characteristic of the environment" as one of the (better) choices.

> And one of those kinds of "blast radius" is traps,

Wait. An implementation-defined behaviour isn't allowed to be trap/termination of execution? Okay, make it unspecified then, with the options of trapping or calculating some unspecified (not indeterminate) integer value.

> N3863

Hm?

    Because implementation-defined behavior relies on the definition of unspecified behavior, it
    means that implementation-defined behavior requires two or more possibilities to be defined in
    the standard. However, a brief look at its uses in the standard clearly shows that there isn’t
    always a list of potential behaviors to pick from.

Eh, I'd argue that omission of such a list is merely an implicit infinite ("two or more", you know) list of possibilities, its construction being self-evident.

    N3783 5.2.1.2p1.1: Physical source file multibyte characters are mapped, in an implementation-
    defined manner, to the source character set (introducing new-line characters for end-of-line
    indicators) if necessary.

There is an infinite list of possible ways to map multibyte characters to the source character set — an implementation has to pick one and document it.

    N3783 5.2.1.3p1: A conforming implementation shall produce at least one diagnostic message
    (identified in an implementation-defined manner)

There is an infinite list of possible diagnostic messages...

    N3783 5.2.2.2p1-2: In a freestanding environment (in which C program execution can take
    place without any benefit of an operating system), the name and type of the function called at
    program startup are implementation-defined.

There is an infinite list of possible C identifiers that an implementation may chose as the name of the function to call at program startup.

N3863 is one of those papers where what the paper proposed and what was actually discussed in the meeting ended up being rather different things, and it's the meeting discussion that I'm pointing to, not the paper itself.

> Wait. An implementation-defined behaviour isn't allowed to be trap/termination of execution? Okay, make it unspecified then, with the options of trapping or calculating some unspecified (not indeterminate) integer value.

Unspecified behavior also isn't allowed to be a trap. The difference between unspecified and implementation-defined is whether or not the compiler has to document its choice; the difference between unspecified and undefined is whether or not the choice is limited.

There is already a precedent for a signed integer operation to produce an implementation-defined value or to trap. It's for integer conversion:

https://open-std.org/JTC1/SC22/WG14/www/docs/n3220.pdf#subsu...

> Otherwise, the new type is signed and the value cannot be represented in it; either the result is implementation-defined or an implementation-defined signal is raised.

There is no reason that this wording strategy could not be reused for bit shifts.

In general there is no constraint that unspecified or implementation-defined behavior can't be a trap. Without further qualification "unspecified behavior" or "implementation-defined behavior" is still open-ended, and it's up to the surrounding standard text to restrict the behavior further.

https://open-std.org/JTC1/SC22/WG14/www/docs/n3220.pdf#subse...

> behavior, that results from the use of an unspecified value, or other behavior upon which this document provides two or more possibilities and imposes no further requirements on which is chosen in any instance

"Possibilities" include trap

> Previously, in C89, left shift on signed integers was completely undefined...

No, it was implementation defined, which is very different. Every implementation you were ever likely to encounter defined it reasonably. Making some of it undefined now has created a bunch of code that uses macros to cast back and forth between unsigned to get the expected behavior (or, for cases where it is provable that the result is representable, to replace the left shift with a multiplication and hope the optimizing compiler translates it back, because compilers now warn on any left shift of a negative value, despite the fact that the semantics are supposed to be the same as the corresponding multiplication now).

In other words, it created a mess for basically no reason.

This is the complete definition of the behavior of left shift operators in C89:

> The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has an unsigned type, the value of the result is E1 multiplied by the quantity, 2 raised to the power E2, reduced modulo ULONG_MAX+l if E1 has type unsigned long, UINT_MAX+1 otherwise. (The constants ULONG_MAX and UINT_MAX are defined in the header <limits.h>.)

You notice what's not mentioned there? What happens if E1 is signed. The standard says nothing. And when the standard says nothing, it's undefined behavior.

The behavior at the bit level seems very well defined based on that excerpt. You would need to know how signed integers are defined to know what the numeric value of the result would be. That sounds like it would be implementation dependent, but also completely predictable. Am I missing something?

From the beginning of Section 3.3 (several pages before the text you quoted in Section 3.3.7):

      Some operators (the unary operator ~ , and the binary operators << ,
  >> , & , ^ , and | , collectively described as bitwise operators)
  shall have operands that have integral type.  These operators return
  values that depend on the internal representations of integers, and
  thus have implementation-defined aspects for signed types.

this only warn that there is some implementation-defined stuff coming next, not that all these operator are free of undefined behaviour

I would be very curious to know why such shifts would be UB as opposed to merely implementation specific.

I guess I can understand that signed shifts bump up against how the hardware represents signed numbers at the bit level, but it’s not like the assembly is unclear on any given platform.

Some ancient machines trapped on signed overflow, including the ones caused by arithmetic shift left (as opposed to logical shift left), and apparently you can't define your implementation-defined behaviour as "oh, it traps in this case" — although still I don't believe the last part.

But if it is true, then yeah, that'd make (some) sense. I say "some" because surely in this case the implementations could simply emit the "logical shift left" instruction for the shift operation both for ints and unsigned ints? I don't think there ever was a machine that actually tracked the signedness/unsignedness of registers.

Yeah that’s what I was thinking. I didn’t think of the traps until I read the sibling threads, but even that doesn’t seem like an impediment.

I think it means what you think is ridiculous. Shifting the sign bit out is UB. Unrepresentable results are UB.

> Shifting the sign bit out is UB

Shifting into the sign bit is also UB. Can I please have a language that actually has bitwise operators with defined semantics? No CPUs had differentiated between SAL/SHL for more than 30 years, if that was the original justification.

I'm fine with left shift trapping on overflow. I'm fine with it just wrapping around. I'm even fine with bitwise shifts simply unapplicable to ints ("cast to unsigned first, then cast back to int"). I am not fine with an operator that invokes UB for literally half of the values of the lhs's domains.

Swift: https://developer.apple.com/documentation/swift/binaryintege...

> The << operator performs a smart shift, which defines a result for a shift of any value.

> - Using a negative value for rhs performs a right shift using abs(rhs).

> - Using a value for rhs that is greater than or equal to the bit width of lhs is an overshift, resulting in zero.

> - Using any other value for rhs performs a left shift on lhs by that amount.

And while the docs don’t say it, `Int.max << 1 == -2`. And in fact, `T.max << 1 == -2` for all `T: BinaryInteger`.

That seems like an exceedingly bad thing. It means that << can't be compiled to a single instruction with single-clock throughput on x86, since shift instructions take an UNSIGNED shift count. As a further complication, x86 processors treat overshifts differently.

e.g.

   MOV AX, 1
   MOV CL, 33
   SHL AX, CL

Afterward, on an 80186, AX contains 2, since the contents of CL are treated MOD 32. The AX register gets shifted by one bit. On an 8086, AX contains zero, since the 8086 implementation shifts by one bit 33 times. (Yes, it will shift 255 times, taking 1024 CPU cycles if you tell it to do that).

Given a choice, I'd prefer performant bit-twiddling in exchange for UB in cases that never occur in practice.

It may seem like an exceedingly bad thing, but in practice most shift amounts are constants, statically known to the compiler, which makes choosing between single instruction-long sequences "shl eax/rax, <imm8>", "shr eax/rax, <imm8>", and "xor eax, eax" trivial.

But variable shifts also happen sometimes, which brings me to the next point:

> in exchange for UB in cases that never occur in practice.

It does happen, and people depend on what their platform does. That's one of the things that sunk John Regehr's proposal for "Friendly C" [0]:

    After publishing the Friendly C Proposal, I spent some time discussing its design with people,
    and eventually I came to the depressing conclusion that there’s no way to get a group of C
    experts — even if they are knowledgable, intelligent, and otherwise reasonable — to agree on
    the Friendly C dialect. There are just too many variations, each with its own set of performance
    tradeoffs, for consensus to be possible. [...] Another example is what should be done when a
    32-bit integer is shifted by 32 places (this is undefined behavior in C and C++). Stephen Canon
    pointed out on twitter that there are many programs typically compiled for ARM that would fail
    if this produced something besides 0, and there are also many programs typically compiled for
    x86 that would fail when this evaluates to something other than the original value. So what is
    the friendly thing to do here?

So. You want a modulo behaviour? Write "expr << (var & 32)" or "expr << (var & 64)", the compiler will recognize this idiom and emit a simple "mov cl, var; shl eax/rax, cl" on x64 and RISC-V, and an additional explicit AND mask on ARMs. You want an overshift? Well, that's the default semantics, and it would emit an simple shift on ARM, and "xor eax, eax; shl edx/rdx, cl; cmp ecx, 32/64; cmovb eax/rax, edx/rdx" on x64 (and something similar on RISC-V). It's your choice!

[0] https://blog.regehr.org/archives/1287

In passing, just to make things even more fun, ARM32 overshifting produces zero; ARM64 uses MODULO overshifting. :-P

I was thinking about eliminating this shift-into-left bit UB. There was a previous attempt though that failed to get consensus. (but long enough ago that one could try again).

But all this signed overflow UB can be turned into traps using sanitizers. In practice, generally mandating a trap is difficult though in ISO C. My plan is to mandate this as part of a special mode, in which case I would just leave this UB in the main standard.

(One problem we also have that some special interests groups in WG14 are rather hostile to our work and the rest of the C community - so I encourage everybody who is actually using C and caring about it to join).

> I was thinking about eliminating this shift-into-left bit UB.

At least make it "change of the sign bit is UB" — if 0 shifts into the sign-bit of a positive number, or 1 shifts into the sign-bit of a negative number, that shouldn't be UB. This would make left-shifts of negative numbers well-defined, their behaviour being that of two's complement numbers. And C23 already demands two's complement from the implementations, doesn't?

> signed overflow UB can be turned into traps using sanitizers.

Well, yeah, sure, but shifting -1 one place to the left doesn't overflow, it produces -2; only shifting INT_MIN or something up to and including INT_MIN + (INT_MAX/2) would overflow.

I agree. Thanks!

The problem is that this is different from C++, so probably we can not do the reasonable thing because it makes the "it must be exactly like C++" people upset.

Apparently, C++23 went on and fully defined it, see the sibling comment from leni536 [0]:

    1) ........................ The behavior is undefined if the right operand is negative,
    or greater than or equal to the width of the promoted left operand.

    2) The value of E1 << E2 is the unique value congruent to E1 × 2**E2 modulo 2**N, where
    N is the width of the type of the result.

    [Note 1 : E1 is left-shifted E2 bit positions; vacated bits are zero-filled. — end note]

    3) The value of E1 >> E2 is E1 / 2**E2, rounded down.

    [Note 2 : E1 is right-shifted E2 bit positions. Right-shift on signed integral types is
    an arithmetic right shift, which performs sign-extension. — end note]

So you can adopt that as well. In any case: since C23/C++23 the integers are two's complement, so make them behave so. Again, I don't mind signed overflow being undefined all that much (although again, I feel like there has to be some middle ground between "full-blown UB and nasal demons" and "the implementations/sanitiziers are allowed to trap it instead of silently wrapping/assuming it never happens") so perhaps you can slightly deviate from C++ here: it apparently allows 1 << (INT_WIDTH - 1) to become INT_MIN, fully defined-ly, maybe this can still be UB in C? But (-1) << (whatever up to INT_WIDTH - 1) absolutely should be defined, it's just ridiculous otherwise.

[0] https://news.ycombinator.com/item?id=50117296

Ah right, they had improved that. Btw: Everbody can submit proposals to WG14.

> Can I please have a language that actually has bitwise operators with defined semantics?

C++? It has defined semantics since C++20.

No, not really? From C++23:

    4) The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits
    are filled with zeros. If E1 has an unsigned type, the value of the result
    is E1 × 2**E2, wrapped around. If E1 has a signed type and nonnegative value,
    and E1 × 2**E2 is representable in the result type, then that is the resulting
    value; otherwise, the behavior is undefined.

    5) The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an
    unsigned type or if E1 has a signed type and a nonnegative value, the value of
    the result is the integral part of the quotient of E1 / 2**E2. If E1 has a
    signed type and a negative value, the resulting value is implementation-defined.

It's marginally more well-defined, sure, but not fully. The right shifts of negative numbers are no longer UB but are still an unportable mystery; and the left shifts of negative values are still outright UB.

Huh, I stand corrected. It is defined in the current draft though:

https://eel.is/c++draft/expr.shift

I thought this was part of the guaranteed two's complement change in C++20.

Actually, no, your copy of C++23 doesn't match mine:

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/n49...

This is indeed from the C++20 paper P1236R1:

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p12...

Ah, I see. Those "final drafts PDFs" are a bit confusing to google, I must admit. I guess I'd better save them once locally, properly titled, and reference those copies instead?

In any case, thanks; it's nice to see C++ at least fully embracing the mandate on integers being two's complement, finally. There is enough footguns already without basic arithmetic operators being UB half of the time.

Ada?

Operations are well defined, and to do stuff like in C, you must do Unchecked_Something calls.

The more immediate problem is modern x86 processors have anomalous over-shift behavior, and can't do signed shift counts. On x86 (80186 and later), the shift count of SHL is UNSIGNED MODULO 32 (or MODULO 64). So the over-shift behavior MUST be UB. So any attempt to define the behavior is going to be incredibly painful, and the best one can do is make provisions for optional sanitizers in debug builds.

It's exactly understandable if you think like a human instead of like a stupid logic machine. It would make no sense for the same thing to be both defined and undefined, and they defined it in the previous sentence, so obviously they did not mean to also undefine it.

Reply on news.ycombinator.com