Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Signed Integers Are Two’s Complement

open-std.org

Post reply on HN
Print view View original

91–100 of 126 posts

Re: Signed Integers Are Two’s Complement

#91

Post by kazinator »

dzdt wrote: post #89
sanxiyn wrote: post #50

Earlier quoted context omitted.

This got rejected in the next revision of this proposal. Naive overflow checks are still undefined.

If a signed operation would naturally produce a value that is not within the range of the result type, the behavior is undefined. The author had hoped to make this well-defined as wrapping (the operations produce the same value bits as for the corresponding unsigned type), but WG21 had strong resistance against this. Who are the standards committee people having strong resistance against this, and what in the world i…

Undefined doesn't mean incorrect; it's just the absence of a requirement. A compiler writer can add requirements locally (like "signed integer overflows have wrapping behavior") that are missing in the standard.

The standard is not a suitable babysitting tool for GCC maintainers, which is what I suspect is the motivation here.

Re: Signed Integers Are Two’s Complement

#92

Post by mannykannot »

iainmerrick wrote: post #64
fulafel wrote: post #59

Earlier quoted context omitted.

Isn't the quoted part 180 degrees wrong? Such code was not "correctly performing security checks", since it was undefined behaviour - two's complement or not. Which was the whole problem.

The checks were not correct for all possible representations. If the only representation were two’s complement, there could be fewer areas of undefined behavior, so simple and straightforward security checks would be much more likely to be correct. (Unfortunately it sounds like this proposal has been revised to leave overflow behavior as undefined. That’s a biggie. Oh well)

> The checks were not correct for all possible representations.

This raises the question of whether the optimization was valid, given the target architecture. I am assuming that, technically speaking, it was, because that is what the standard allowed, but that view leaves unexamined the question of whether it is contrary to the purposes for having and using the C language in the first place.

I can imagine an argument pointing out that this optimization is applied at an abstract level of representation prior to code generation, and that it would be a violation of modularity to take into account the target architecture at that point. This, however, would be a point about the compiler architecture, which I think should, where practical, yield to concerns about the overall purpose and use of the compiler, where the principle of 'no (or minimal) surprises' is important.

Re: Signed Integers Are Two’s Complement

#93

Post by mannykannot »

kazinator wrote: post #90

Requiring two's complement just means you can't have a sensible C language on some sign-magnitude machine. Even if nobody cares about such a machine, nothing is achieved other than perhaps simplifying a spec. A language spec can provide a more detailed two's complement model with certain behaviors being defined that only make sense on two's complement machines, without tossing other machines out the window. There cou…

The worst case is that there would not be an ISO C for such machines. As they are very unusual, this does not strike me as a big deal, and definitely less of an issue than making it easier to avoid invoking undefined behavior.

I take your point about the possible motives behind this proposal, which seem quite plausible.

Re: Signed Integers Are Two’s Complement

#94

Post by yoklov »

kazinator wrote: post #91
dzdt wrote: post #89

Earlier quoted context omitted.

If a signed operation would naturally produce a value that is not within the range of the result type, the behavior is undefined. The author had hoped to make this well-defined as wrapping (the operations produce the same value bits as for the corresponding unsigned type), but WG21 had strong resistance against this. Who are the standards committee people having strong resistance against this, and what in the world i…

Undefined doesn't mean incorrect; it's just the absence of a requirement. A compiler writer can add requirements locally (like "signed integer overflows have wrapping behavior") that are missing in the standard. The standard is not a suitable babysitting tool for GCC maintainers, which is what I suspect is the motivation here.

This isn’t entirely untrue in theory, but in practice it is. Compilers optimize under the assumption that undefined behavior never occurs, and the standard is written with this assumption. Any conforming compiler is free to break code that relies on this.

Typically, behavior that reasonably may vary from compiler/machine is considered implementation defined, and not undefined.

Re: Signed Integers Are Two’s Complement

#95

Post by JdeBP »

fulafel wrote: post #59
raverbashing wrote: post #44

> Naïve overflow checks, which are often security-critical, often get eliminated by compilers. This leads to exploitable code when the intent was clearly not to and the code, while naïve, was correctly performing security checks for two’s complement integers. This is the most critical aspect. We have enough trouble already without the compiler actually fighting against security because this would fail in a machine fr…

Isn't the quoted part 180 degrees wrong? Such code was not "correctly performing security checks", since it was undefined behaviour - two's complement or not. Which was the whole problem.

The whole problem is in fact this.

* The language standards came from a time where there was no standard (de facto, that is) for signed integer arithmetic across instruction architectures. Bear in mind that many people involved in standardization (rightly) want to standardize what is in actual practice in the world. If the world hasn't settled on one thing, it is difficult to standardize. (It's why the system administration parts of Unix were not addressed by IEEE 1003.1, for example. There were a whole lot of significantly different ways in which system administration was done.)

* Programmers were coding "knowing" that 2s-complement arithmetic led to certain tricks for detecting overflow and other sorts of bit twiddling (https://news.ycombinator.com/item?id=17044546); "knowing" that their processor architectures were 2s-complement; and "knowing" that compilers naively just translated straight to the arithmetic machine instructions of the target architecture.

* Compiler implementors were writing compilers knowing that programmers did not in fact have these guarantees, and implementing their optimizers as if the target processor architectures were not 2s-complement (in particular, as if integers had infinite bits); even when the actual machine code generation parts of their compilers were designed with the knowledge that the target processor architecture was 2s-complement.

The whole problem is that this is a mess that does not hang together.

There are several ways out of it. One is to make Sean Eron Anderson's life a living hell (https://graphics.stanford.edu/~seander/bithacks.html), and attempt to stamp out every piece of samizdat doco and programmer folklore that circulates these tricks, or at least make every one of them carry a lengthy "health warning" that the world is not, in fact, guaranteed to provide 2s-complement arithmetic to programmers. Another is to give in and say that the heretofore unwarranted assumptions by the programmers are now in fact supported, and that the compiler implementors have to change their now invalid compiler designs.

A third is to do part of each, by accepting and legitimizing the programmer folklore to an extent, but realizing that programmers often "know" quite the opposite case and assume that they are not using 2s-complement arithmetic. Where one programmer can be surprised to find that (x + 1) > (x) is always true because on the 2s-complement architecture that xe expects it isn't; another programmer can be surprised to find that ((x * 2) / 2) == (x) is not always true because in elementary school arithmetic multiplication by 2 is the inverse of division by 2, and be further surprised that (say) some deep nesting of macros that results in such things doesn't reduce to a no-op.

Re: Signed Integers Are Two’s Complement

#96

Post by phkahler »

kazinator wrote: post #90

Requiring two's complement just means you can't have a sensible C language on some sign-magnitude machine. Even if nobody cares about such a machine, nothing is achieved other than perhaps simplifying a spec. A language spec can provide a more detailed two's complement model with certain behaviors being defined that only make sense on two's complement machines, without tossing other machines out the window. There cou…

>> Even if nobody cares about such a machine, nothing is achieved other than perhaps simplifying a spec.

No, I use 16bit values to represent angles in embedded systems all the time. I routinely expect arithmetic on these values to roll over as 2's complement and I expect to take differences of angles using 2's complement all the time. I'm fully aware that this is undefined behavior and needs to be verified on each compiler/processor combination. It has always worked and yet it's undefined behavior. It would be nice for it to be defined. There are no modern machines that would be impacted by this.

Re: Signed Integers Are Two’s Complement

#97

Post by kazinator »

yoklov wrote: post #94
kazinator wrote: post #91

Earlier quoted context omitted.

Undefined doesn't mean incorrect; it's just the absence of a requirement. A compiler writer can add requirements locally (like "signed integer overflows have wrapping behavior") that are missing in the standard. The standard is not a suitable babysitting tool for GCC maintainers, which is what I suspect is the motivation here.

This isn’t entirely untrue in theory, but in practice it is. Compilers optimize under the assumption that undefined behavior never occurs, and the standard is written with this assumption. Any conforming compiler is free to break code that relies on this. Typically, behavior that reasonably may vary from compiler/machine is considered implementation defined, and not undefined.

> Any conforming compiler is free to break code that relies on this.

Ah, but, for example, __attribute__((packed)) is undefined behavior; is the compiler free to break that?

This "free to break" is a juvenile fiction based on the idea that the only document that applies is ISO C; there is no other contract or promise between user and implementor.

Re: Signed Integers Are Two’s Complement

#98

Post by kazinator »

phkahler wrote: post #96
kazinator wrote: post #90

Requiring two's complement just means you can't have a sensible C language on some sign-magnitude machine. Even if nobody cares about such a machine, nothing is achieved other than perhaps simplifying a spec. A language spec can provide a more detailed two's complement model with certain behaviors being defined that only make sense on two's complement machines, without tossing other machines out the window. There cou…

>> Even if nobody cares about such a machine, nothing is achieved other than perhaps simplifying a spec. No, I use 16bit values to represent angles in embedded systems all the time. I routinely expect arithmetic on these values to roll over as 2's complement and I expect to take differences of angles using 2's complement all the time. I'm fully aware that this is undefined behavior and needs to be verified on each co…

> It would be nice for it to be defined.

Your compiler implementors can do that in their documentation; it doesn't have to be pushed into the standard.

There are reasons for it being regarded as not nice to define something like that or make it some compiler option or pragma and whatever. Overflow is in fact an error in many situations, because it can happen unexpectedly; it's useful for the compiler or machine to trap overflows.

What I was referring to in my above remark is mainly the removal of support for sign-magnitude; if you read my response more carefully you will see that I favor ways of making the behavior defined without sacrificing things.

Anyway, you can use unsigned arithmetic instead to do portable two's complement. Unsigned integers have the required roll-over behavior.

Some 28 years ago I made an emulator for the MC68000 processor. I used unsigned 32 bit integers for all the arithmetic, including the signed operations. E.g. the difference between a signed and unsigned addition was only how the flag are calculated, like Z, X and C.

Re: Signed Integers Are Two’s Complement

#99

Post by kazinator »

mannykannot wrote: post #93
kazinator wrote: post #90

Requiring two's complement just means you can't have a sensible C language on some sign-magnitude machine. Even if nobody cares about such a machine, nothing is achieved other than perhaps simplifying a spec. A language spec can provide a more detailed two's complement model with certain behaviors being defined that only make sense on two's complement machines, without tossing other machines out the window. There cou…

The worst case is that there would not be an ISO C for such machines. As they are very unusual, this does not strike me as a big deal, and definitely less of an issue than making it easier to avoid invoking undefined behavior. I take your point about the possible motives behind this proposal, which seem quite plausible.

But gutting support for sign-magnitude machines has nothing to do with making certain two's complement behaviors defined.

It's like saying we have to drop USB 1.0 support in an OS in order to fix missing features in the Bluetooth stack.

Re: Signed Integers Are Two’s Complement

#100

Post by sanxiyn »

kazinator wrote: post #91
dzdt wrote: post #89

Earlier quoted context omitted.

If a signed operation would naturally produce a value that is not within the range of the result type, the behavior is undefined. The author had hoped to make this well-defined as wrapping (the operations produce the same value bits as for the corresponding unsigned type), but WG21 had strong resistance against this. Who are the standards committee people having strong resistance against this, and what in the world i…

Undefined doesn't mean incorrect; it's just the absence of a requirement. A compiler writer can add requirements locally (like "signed integer overflows have wrapping behavior") that are missing in the standard. The standard is not a suitable babysitting tool for GCC maintainers, which is what I suspect is the motivation here.

I am not sure why people pick GCC in particular for this issue. LLVM does exactly the same.
Post reply on HN