[C/C++] Force subtraction to perform comparison

[brucehoult]

My problem is how to force the compiler to perform `b` - `a` > 0 when I write `b - a > 0`, because (it is not shown in the above code example) but when I wrote:

Code: [Select]

if (spin && !unlock && ticks && (epoch - at > 0)) {
    __CLREX();
    return false;
}I get a program that didn't work because (epoch - at > 0) was assembled as the previous "CMP + BGT" sequence that didn't work.

"CMP + BGT" is exactly correct and exactly what you asked it to do.

"CMP" and "SUBS" are the same operation, with the sole difference being that "CMP" doesn't write the result of the subtraction to a register.

[emece67]

.

[NorthGuy]

I get a program that didn't work because (epoch - at > 0) was assembled as the previous "CMP + BGT" sequence that didn't work for this case.

There must be something about these variables that made such optimization possible. Does it still hold when you declare both variables volatile? The "volatile" would prevent the compiler from making any assumptions about values the variables may hold.

[emece67]

.

[brucehoult]

My problem is how to force the compiler to perform `b` - `a` > 0 when I write `b - a > 0`, because (it is not shown in the above code example) but when I wrote:

Code: [Select]

if (spin && !unlock && ticks && (epoch - at > 0)) {
    __CLREX();
    return false;
}I get a program that didn't work because (epoch - at > 0) was assembled as the previous "CMP + BGT" sequence that didn't work.

"CMP + BGT" is exactly correct and exactly what you asked it to do.

"CMP" and "SUBS" are the same operation, with the sole difference being that "CMP" doesn't write the result of the subtraction to a register.

As I demonstrated before "CMP + BGT" and "SUBS + CMP #0 + BGT" are different.

Of course they are. The "CMP #0" throws away information, specifically the carry and overflow flags from the CMP/SUBS, so you get the result of a wrapped calculation not the mathematically correct result of the subtract.

"CMP + BGT" and "SUBS + BGT" are the same thing.

EDIT:

Code: [Select]

          LDR       R0, =0x80000002
          LDR       R1, =0x7FFFFFFA
          SUBS      R2, R0, R1
          CMP       R2, #0
          BGT       testwill take the branch.

Code: [Select]

          LDR       R0, =0x80000002
          LDR       R1, =0x7FFFFFFA
          CMP       R0, R1
          BGT       testwill not.

Your numbers are -2147483646 and 2147483642. The former is clearly much smaller and a signed comparison (using SUBS/BGT or SMP/BGT) will show that.

If you subtract them the mathematical result is -4294967288, which is very negative so BGT correctly does not branch.

If you force the result of the subtraction to be brought into the 32 bit range by storing it to memory and loading it back, or by comparing directly to 0, then you get 8, which is greater than 0, which is why the first one branches.

Overflow in signed arithmetic in C is UB. The compiler is allowed by the rules of the language to assume that you do not do anything that overflows, and that you are happy with either the true mathematical result or the wrapped result -- or in fact with anything else.

In particular for signed values the compiler is allowed to assume mathematical rules such as commutativity and associativity and assume that for the values you give it, "epoch - at > 0" and "epoch - at + at > 0 + at" and "epoch > at" are equivalent. In the vast vast majority of code this is a *good* thing.

But you are trying to do something tricky and non-mathematical.

If you want to depend on wrapping modulo 2^32 arithmetic in C then you *must* use "unsigned". It's as simple as that.

If you want to program in C then learn the language. Don't try to figure out how to trick some particular compiler. Write code that is guaranteed by the clearly written rules of the language to work with any compiler, at any optimisation level, on any instruction set, on any day of the week.

[brucehoult]

Nope - unsigned subtraction has standard defined behavior in case of overflow. Signed does not. And, timestamps are the most usual example where overflows happen by design.

It is undefined for the reason that CPUs might exist where signed numbers have a different representation (e.g. a separate sign and absolute value), in which case the overflow would produce different results. I don't know if such CPUs ever existed, I don't think they exist now. So, the only way for the compiler to produce unexpected behaviour is to purposely butcher the code. 

Both sign-magnitude and ones-complement computers have certainly existed and been popular in the distant past.

The very famous CDC 6600 for example used ones-complement for integers and also for both the exponent and the significant in floating point.

Someone pointed out before that in my "(int)(a-b) > 0" where a and b are unsigned, the cast to signed is UB. I replied previously that it's UB only because of the past existence of sign-magnitude and ones-complement computers.

However! Thinking about it more now, the value of the negative number you'll get from an unsigned mod 2^32 result with the hi bit set varies between all three systems, but the FACT of it being negative doesn't. So the above code will work fine on all three types of system. The only way you'd get a problem would be if the sign bit was stored somewhere else, for example in the LSB instead of the MSB.

Another possibility for the compiler to screw up is to replace (a - b > 0) with (a > b), but this would be an optimization which alters the behaviour and should not be used (see C-99 5.1.2.3.14 for example)

No, that's perfectly fine and allowed in signed arithmetic. It is the programmer's responsibility to ensure that is doesn't change the behaviour.

Consider also that it's valid to implement C on a machine whose native representation is bignums e.g. perhaps something designed for Lisp -- or Python. Or, for that matter, on a machine that operates in trinary or decimal. Signed arithmetic can simply proceed to use the native instructions, while unsigned arithmetic must do a mod(2^32) operation after every arithmetic operation (semantically -- it could be done after several operations if the result is guaranteed to be the same).


Another completely standards-compliant no UB formulation, btw:

Code: [Select]

int timeHasElapsed(unsigned timeStamp, unsigned now){
  return (now - timeStamp - 1) < 0x80000000u;
}

Just like ...

Code: [Select]

int timeHasElapsed(unsigned timeStamp, unsigned now){
  return ((now - timeStamp - 1) & 0x80000000u) != 0;
}

... this compiles to a subtract and 31 bit right shift (logical) on every 32 bit ISA I tried it on, with both GCC and Clang.

[DavidAlfa]

RISC-V
Many compilers don't use them anymore because they are relatively hard to get to (need to read coprocessor status bits, increasing register pressure).

Hmm so instead of making accessing easier, they removed it... Sounds like Retarded Instruction Set

[ejeffrey]

I get a program that didn't work because (epoch - at > 0) was assembled as the previous "CMP + BGT" sequence that didn't work for this case.

There must be something about these variables that made such optimization possible. Does it still hold when you declare both variables volatile? The "volatile" would prevent the compiler from making any assumptions about values the variables may hold.

Please don't go dragging volatile into this.  That's got nothing to do with it, and will only confuse matters more.

[hans]

It seems like the compiler optimization routines has a different idea of how mathematics maps onto the arithmetic. Example by "fixing" the issue *without* volatile:

https://godbolt.org/z/n6Pesxvo9

Comment in/out the printf lines. You'll see the compare flags suddenly springing back to life. Even on cmp0 where the intermediate result 'sub' is not used in the printf statements, does make the compiler 2nd think it's optimization actions and fixes the issue..

Also writing the subtraction result to some other unused variable seems to work... 

[cv007]

I'm still trying to understand 'signed timestamp'. Not sure what you are doing or what numbers you are getting for time, but maybe you are focused on only using a timestamp (?) when you could be using a start time + duration. With a start reference time, you have almost the whole 32bits of us to use (~71 minutes) with easy unsigned arithmetic (doesn't matter what you starting number is, you always get the 'next' 32bits to use). If you need more than 71 minutes of us, then you need to extend it while still using the same time source (can be done, and at that point you probably want an addition of some type of rtc time).

Example-
https://godbolt.org/z/9aW4Wv6Ms

Unsigned arithmetic. You only have to watch out when getting too close to the max value, where you could happen to 'miss' the timestamp (a small window of time where your time check went from not elapsed to elapsed but you missed checking it while other things were going on). Its not hard to pick a number as a max time that will always work.

[brucehoult]

Comment in/out the printf lines. You'll see the compare flags suddenly springing back to life. Even on cmp0 where the intermediate result 'sub' is not used in the printf statements, does make the compiler 2nd think it's optimization actions and fixes the issue..

Also writing the subtraction result to some other unused variable seems to work... 

On that compiler version. Maybe not on the next one. Or with different optimisation flags.

Doing it *wrong* by using overflowing signed arithmetic doesn't get made right by finding some combination of tricks that happens to get the answer you want. It's still wrong. And incredibly dangerous to publish.

[brucehoult]

Unsigned arithmetic. You only have to watch out when getting too close to the max value, where you could happen to 'miss' the timestamp (a small window of time where your time check went from not elapsed to elapsed but you missed checking it while other things were going on). Its not hard to pick a number as a max time that will always work.

Right. You don't have to split the interval so your maximum time period is 2^31 ticks and you get 2^31 ticks to check it. If you can guarantee that in the worst case you check for expired time intervals every N ticks then you can use a maximum interval up to 2^32 - N.

[emece67]

.

[newbrain]

will work in two's complement, one's complement and sign+magnitude, no matter the bit size of an int, correct?

Not guaranteed by the standard, in fact.
There's no guarantee that INT_MAX is less than UINT_MAX - e.g. in a sign magnitude architecture you might only have native signed operations and unsigned maths would be very inefficient, so the right choice for C is to have UINT_MAX == INT_MAX.

You have to wait for C23. Then two's complement will be the only accepted representation.

[hans]

Unsigned has no 2s complement etc. Thats only for signed numbers. So any adder overflowing will go from UINT_MAX to 0.

HOW a signed number is typecasted to unsigned is implementation specific (or in C, probably UB)

Comment in/out the printf lines. You'll see the compare flags suddenly springing back to life. Even on cmp0 where the intermediate result 'sub' is not used in the printf statements, does make the compiler 2nd think it's optimization actions and fixes the issue..

Also writing the subtraction result to some other unused variable seems to work... 

On that compiler version. Maybe not on the next one. Or with different optimisation flags.

Doing it *wrong* by using overflowing signed arithmetic doesn't get made right by finding some combination of tricks that happens to get the answer you want. It's still wrong. And incredibly dangerous to publish.

Always take any "publication" with a grain of salt, especially on forums. Even academia papers get it wrong (more than) half of the time, I can tell from experience. Forums are about discussions where people try to trade knowledge (=learn), all from a different working experience and background.

Yes signed int overflow in C99 is UB. But perhaps I'm too pragmatic, but I always wonder why and does it apply? Signed magnitude, 1s and 2s complement will have different overflow behaviour, and if the Clang language can assume that is unknown, then it is right to optimize "i+1 > i" to be always "true", even when on a 2s complement computer with i=INT32_MAX , that expression would be false. GCC does the same.

The point at which Clang seems to take 1 step further, is moving variables across the comparison operator, as a mathematical number. So "a - b < 0" is equal to "a < b". GCC doesn't do this, and generates the "intended" subtraction comparison. You would need to force the Clang compiler to assume integers are stored 2s complement with argument fwrapv. Then it won't do this optimization.. Even for i+1>i will be executed on the CPU using both compilers.

And here is where perhaps my pragmatism (or I'm too ignorant) comes in: how many 1s or sign magn computers have I programmed? Zero. Would I feel bad about "hacks" to get signed int overflow to "work"? To some degree yes.. but on the other hand, how "portable" is C when there dozen of platform dependent behaviours that you as a programmer need to solve. How portable is C when you need to specify the crosscompiler, CPU architecture etc. for it to work? The compiler assuming that a INT32 is a "math integer" is somewhat ambitious in my opinion. Why would we have 8, 16, and 64 bit types instead? All machines will have limitations..

I'm not suggesting anyone to implement any of my volatile/side-effect/fwrapv "hacks". Unsigned is the proper way to do it in C. But maybe I should start programming Rust instead.. that tries to leave as little to UB as possible

[brucehoult]

Code: [Select]

int timeHasElapsed(unsigned timeStamp, unsigned now){
  return ((now - timeStamp - 1) & 0x80000000u) != 0;
}


If I understand it correctly, this:

Code: [Select]

bool timeHasElapsed(unsigned timeStamp, unsigned now){
  return (now - timeStamp - 1) & ~MAX_INT;
}will work in two's complement, one's complement and sign+magnitude, no matter the bit size of an int, correct?

As a practical matter, probably. I think ((UINT_MAX>>1)+1) would be more guaranteed to work.

[Nominal Animal]

Without invoking UB or Implementation Defined functionality, in standard C (C99 or later):

Code: [Select]

static inline int32_t to_int32(uint32_t value)
{
    union {
        uint32_t u;
        int32_t  i;
    } temp = { .u = value };
    return temp.i;
}

static inline int32_t elapsed(uint32_t now, uint32_t then)
{
    return to_int32(now - then);
}

int hasElapsed(uint32_t now, uint32_t then)
{
    return elapsed(now, then) < 0;
}
(The inline is there for us humans only, and does not affect the compiler at all.)

The reason this works and is not UB or implementation defined, is that type-punning via an union is described in the C standards (C99 6.5.2.3 footnote 82, C11 6.5.2.3 footnote 95, C17 6.5.2.3 footnote 97), and the exact-width integer types have an exact storage representation (C99 7.8.1.1, C11 7.20.1.1, C17 7.20.1.1): even on non-twos complement architectures, int32_t has a two's complement storage representation in C.

Because in C a logical comparison yields an integer value of 0 (if false) or 1 (if true), the hasElapsed() tends to compile (Compiler Explorer) to a subtraction followed by a right shift by 31 bits.

Of course, there is already so much existing C code that uses (int32_t)(uint32_t expression) with the expectation that it behaves exactly like to_int32(uint32_t expression), that one can expect a practically useful C compiler to do just that.

[NorthGuy]

I'm not suggesting anyone to implement any of my volatile/side-effect/fwrapv "hacks". Unsigned is the proper way to do it in C. But maybe I should start programming Rust instead.. that tries to leave as little to UB as possible

Or assembler, where there's no UB at all

[SiliconWizard]

will work in two's complement, one's complement and sign+magnitude, no matter the bit size of an int, correct?

Not guaranteed by the standard, in fact.
There's no guarantee that INT_MAX is less than UINT_MAX - e.g. in a sign magnitude architecture you might only have native signed operations and unsigned maths would be very inefficient, so the right choice for C is to have UINT_MAX == INT_MAX.

You have to wait for C23. Then two's complement will be the only accepted representation.

Yup.

[ejeffrey]

Yes signed int overflow in C99 is UB. But perhaps I'm too pragmatic, but I always wonder why and does it apply? Signed magnitude, 1s and 2s complement will have different overflow behaviour, and if the Clang language can assume that is unknown, then it is right to optimize "i+1 > i" to be always "true", even when on a 2s complement computer with i=INT32_MAX , that expression would be false. GCC does the same.

The point at which Clang seems to take 1 step further, is moving variables across the comparison operator, as a mathematical number. So "a - b < 0" is equal to "a < b". GCC doesn't do this, and generates the "intended" subtraction comparison.

I think your two examples are exactly the same thing.  The fact that one compiler does only one optimization and the other does both is mostly irrelevant.

You would need to force the Clang compiler to assume integers are stored 2s complement with argument fwrapv. Then it won't do this optimization.. Even for i+1>i will be executed on the CPU using both compilers.

It's not like the compiler has any illusion about the architectural data type.  The compiler knows that it is using twos compliment arithmetic and generates it's code based on that.  What you are doing with fwrapv is forcing the compiler to emit code that behaves as if it were evaluated by the arithmetic rules of the language -- operator precedence and promotion rules -- on a twos compliment machine.  Right now the compiler is not required to do that even when using 2s compliment hardware.

IMO this is a design flaw in C.  The language could easily say that signed integers must have a consistent implementation defined overflow behavior.  That could be twos compliment, saturation, or if someone actually wanted to implement c99 on a ones compliment architecture they could do that.  This would be analogous to how C allows implementations to select the size of short/int/long based on what is efficient but its not allowed to occasionally perform optimization with a different width that changes the behavior.  I get that there are legitimate optimizations this would prevent but there are also a lot of totally legitimate operations that can't be done without casting to unsigned and back.  One of the most important is testing for overflow.  If you do an operation on signed integers and then test for overflow the compiler can and often will remove the check.  This is stupid.  While people argue that "mandating predictable but 'incorrect' behavior is worse than undefined behavior" they are just wrong.  But that is the way the C standard currently is, and the current trend in compilers is to not promise more than the standard requires even when the standard is stupid.  So until c23 comes out and mandates 2s compliment behavior that is what we have.

[emece67]

.

[Nominal Animal]

The conclusions I extract from this thread are:

There is one point missing, though.  In C (C99 and later), casting a numeric expression to a numeric type limits the value of that expression to the type and range of that expression.  (For unsigned integer types, this applies modular arithmetic.)

This matters, because when using arithmetic on types smaller than int, they are promoted to int.

That is, even if you have uint16_t a and b, (a - b) is of int type, on typical 32-bit and 64-bit architectures (because the range of uint16_t, 0 through 65535, inclusive, is included within the range of int).  This is the extremely common case for the signed-to-unsigned casting case I mentioned before: in such cases, you very often see e.g. (uint16_t)(a - b) used, to obtain the result of the subtraction as an unsigned 16-bit integer; and is the reason why sane C compilers have to do this cast via the storage representation.

In more practical terms, with uint16_t a = 0; and b = 65535; on 32-bit architectures, (a - b) == -65535, but (uint16_t)(a - b) == 1 (if one ignores the silliness of the standard saying the cast is UB here).  Most compilers do seem to treat (uint16_t)(int_expression) as (int_expression)&0xFFFF, which really is the only way it makes any sense at all; and similarly for (uint8_t)(int expression) and (int_expression)&0xFF.   I don't think I have access to any compilers where int is 64-bit, but if there were, I'd expect (uint32_t)(int_expression) to be treated as (int_expression)&0xFFFFFFFF there.

[langwadt]

You have to wait for C23. Then two's complement will be the only accepted representation.

is there any platforms in common use that isn't two's complement ?

[ozcar]

Key thing here is that time is kept unsigned.

Perhaps not if you wanted to represent times prior to the epoch.

[Nominal Animal]

Key thing here is that time is kept unsigned.

Perhaps not if you wanted to represent times prior to the epoch.

Eh, just use a 64-bit unsigned integer, so that 19690721T025600Z matches 2⁵⁹ (approximately 18 billion years), and you're good for half a trillion years, and anything crossing zero is unphysical.  The difference to the Unix epoch is then 2⁵⁹+14166240 = 576460752317589728 seconds.

Kidding, sorta.  Standardizing on twos complement and IEEE-754 floating-point types makes sense, because anything different can emulate those.  Just like now, compilers can then provide options to break standards compliance, if it supports a weird architecture; and e.g. built-ins and compiler extensions to access the underlying hardware capabilities.

Anything that deals with dates further out than a century or so will need to be prepared for all sorts of configurable calendar oddities anyway.  For example, in the common era calendar system we use, 1 BCE was followed by 1 CE.  In ISO 8601, year 1 == 1 CE, year 0 == 1 BCE, year -1 = 2 BCE, and so on.