Signed Integers Are Two’s Complement • Hacker News Board

Re: Signed Integers Are Two’s Complement

#101

Post by sanxiyn » Thu, May 31, 2018, 2:03 PM UTC

kazinator wrote: post #97

yoklov wrote: post #94

Earlier quoted context omitted.

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.

GCC documentation is another such contract, which provides -fwrapv. If you want -fwrapv, use -fwrapv.

Re: Signed Integers Are Two’s Complement

#102

Post by kazinator » Thu, May 31, 2018, 2:10 PM UTC

johannes1234321 wrote: post #78

sanxiyn wrote: post #56

Earlier quoted context omitted.

I don't see how. Integer overflows still can be security issues even if they wrap.

They can be security issues since the compiler is allowed to optimize stuff. The compiler can check, that some checks the user added "don't make sense" since those only would be hit if something undefined happens. An example is shown in https://www.tripwire.com/state-of-security/vulnerability-man... but there are many more.

No, they can be security issues in that the program expected x + 1 to be a value bigger than x, but it is suddenly a big negative value.

The fact that this behavior is now blessed by ISO C makes no difference to it being wrong, and causing some security issue in the program.

Re: Signed Integers Are Two’s Complement

#103

Post by sanxiyn » Thu, May 31, 2018, 2:12 PM UTC

loup-vaillant wrote: post #83

GlitchMr wrote: post #79

I like the idea of forbidding signed integer representations other than 2's complement, as it is de facto standard, pretty much nobody makes CPUs with non-standard integer representations, partly due to C programs assuming 2's complement integer representation. What I don't like about this proposal is defining signed integer overflow as 2's complement wrapping. Yes, yes, I know undefined behaviour is evil, and progra…

> However, if a program has signed overflow, it's likely a bug anyway. There are programs that check for overflow after the fact. Is that a bug?

No, but since most overflows are bugs, I think the right solution is to standardize something like GCC's __builtin_add_overflow for overflow checks. Rust does this.

Re: Signed Integers Are Two’s Complement

#104

Post by markrages » Thu, May 31, 2018, 2:13 PM UTC

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…

Yes, it is annoying to rrad comments that assume overflow is always a programming error.

You can store the angle as a union of signed and unsigned type. Do arithmetic on the unsigned member, where overflow is defined. (Both members are equivalent angles)

Re: Signed Integers Are Two’s Complement

#105

Post by sanxiyn » Thu, May 31, 2018, 2:17 PM UTC

markrages wrote: post #104

phkahler wrote: post #96

Earlier quoted context omitted.

>> 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…

Yes, it is annoying to rrad comments that assume overflow is always a programming error. You can store the angle as a union of signed and unsigned type. Do arithmetic on the unsigned member, where overflow is defined. (Both members are equivalent angles)

Not always, but overflows are usually bugs. This is replicated finding of dynamic overflow checking tools, over and over.

Re: Signed Integers Are Two’s Complement

#106

Post by virgilp » Thu, May 31, 2018, 2:25 PM UTC

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…

Why are you assuming "machine from the 70s"? I know modern processors (DSPs) that need to saturate on integer arithmetic in order to maintain correctness. If you want your naive overflow checks to work on your x86 project, why not just use a compiler option like -fwrapv?

IMO, this is just plain ignorance - people arguing against the standard, while believing only their favorite platform is significant. C code is still big in embedded, you can't just trash the standard like that.

Re: Signed Integers Are Two’s Complement

#107

Post by deathanatos » Thu, May 31, 2018, 2:41 PM UTC

ridiculous_fish wrote: post #15

> Overflow in the positive direction shall wrap around This appears to be defining signed integer overflow semantics, which prevents the compiler from doing certain basic optimizations, for example, that (x*2)/2 == x. Is that part of this? Has anyone measured the perf cost on a real program?

For some examples of the types of optimizations enabled by allowing overflow to be undefined: https://kristerw.blogspot.com/2016/02/how-undefined-signed-o...

Re: Signed Integers Are Two’s Complement

#108

Post by amelius » Thu, May 31, 2018, 2:56 PM UTC

cjensen wrote: post #13

greenhouse_gas wrote: post #7

The real issue isn't that C doesn't have a standard int overflow, but that it's undefined. What they could have done is made it implementation defined , like sizeof(int), which depends on the implementation (hardware) but on the other hand isn't undefined behavior (so on x86/amd4 sizeof(int) will always be equal to 4).

It's undefined for a reason. size_t size = unreasonable large number; char buf = malloc (size); char *mid = buf + size / 2; int index = 0; for (size_t x = 0; x A common optimization by a compiler is to introduce a temporary char *temp = mid + index; prior to the loop and then replace the body of the loop with *(temp++) = x; If the compiler has to worry about integer overflow, this optimization is not valid. (I'm not…

> If the compiler has to worry about integer overflow, this optimization is not valid.

I'm sure it's still possible to come up with an optimization that takes into account signed-ness, and doesn't give in to performance or code-size much.

Re: Signed Integers Are Two’s Complement

#109

Post by loup-vaillant » Thu, May 31, 2018, 2:57 PM UTC

loup-vaillant wrote: post #87

cjensen wrote: post #13

Earlier quoted context omitted.

It's undefined for a reason. size_t size = unreasonable large number; char buf = malloc (size); char *mid = buf + size / 2; int index = 0; for (size_t x = 0; x A common optimization by a compiler is to introduce a temporary char *temp = mid + index; prior to the loop and then replace the body of the loop with *(temp++) = x; If the compiler has to worry about integer overflow, this optimization is not valid. (I'm not…

This case is not worth optimising, because the index should be size_t just like the original size. Then the compiler knows it won't overflow, and doesn't have to check.

And, the fix is easy: just use types of the same width for the counter and the boundary. Using a narrower counter is just begging for errors to happen. This is not a good coding style, and there is no point in having the compiler condoning it.

Compiling it and making it run? Sure. Bending over backwards to ensure it runs fast? Hell no.

Re: Signed Integers Are Two’s Complement

#110

Post by kazinator » Thu, May 31, 2018, 3:03 PM UTC

cjensen wrote: post #13

greenhouse_gas wrote: post #7

The real issue isn't that C doesn't have a standard int overflow, but that it's undefined. What they could have done is made it implementation defined , like sizeof(int), which depends on the implementation (hardware) but on the other hand isn't undefined behavior (so on x86/amd4 sizeof(int) will always be equal to 4).

It's undefined for a reason. size_t size = unreasonable large number; char buf = malloc (size); char *mid = buf + size / 2; int index = 0; for (size_t x = 0; x A common optimization by a compiler is to introduce a temporary char *temp = mid + index; prior to the loop and then replace the body of the loop with *(temp++) = x; If the compiler has to worry about integer overflow, this optimization is not valid. (I'm not…

Integer overflow is certainly not undefined for this reason.

It's undefined because in the majority of situations, it is the result of a bug, and the actual value (such as a wrapped value) is unexpected and causes a problem.

For instance, oh, the Y2038 problem with 32 bit time_t.