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

[emece67]

.

[DavidAlfa]

Use parenthesis to perform an operation before anything else.

Code: [Select]

  if ( !( (b - a) > 0) ) {
    ++cntsubs;    // triggered 0 times
  }

Are a and b modified by some interrupt?
Then you must declare them as volatile, or the compile won't expect them randomly changing, ex.:

Code: [Select]

uint32_t time=0;
void main(){
  if(time>1000){
    // This might never work, compiler thinks it's always 0
    // because there's no direct call to Timer ISR
    // (Because it's an interrupt)
  }
}

void Timer_ISR(){
  time++;
}
Declaring as volatile completely changes how the compiler treats the variable:

Code: [Select]

volatile uint32_t time=0;
void main(){
  if(time>1000){
    // This will work, compiler understands time can change at any time
    // So it'll always check it, not optimizing or caching
  }
}

void Timer_ISR(){
  time++;
}


[brucehoult]

Use parenthesis to perform an operation before anything else.

No, that's fine as is. The compiler understands C.

Are a and b modified by some interrupt?
Then you must declare them as volatile, or the compile won't expect them randomly changing, ex.:

That's not the problem either. The problem is using signed int.

[brucehoult]

Hi all,

In an application I use some timestamps (signed 32 bit integers counting μs since system reset) and I want to test if they have elapsed comparing them against current time. Now consider this code (compiled with armclang for Cortex-M4):

Code: [Select]

int a, b, cntcomp, cntsubs;

a = 0;
cntcomp = 0;
cntsubs = 0;

do {
  b = a + 5;      // b is "always" greater that n
 
  if (!(b > a)) {
    ++cntcomp;    // triggered 5 times, when previous add overflows
  }
 
  if (!(b - a > 0)) {
    ++cntsubs;    // triggered 0 times
  }
} while (++a);

What are you actually trying to do here?

The test code is crazy because the compiler can easily see the fixed relationship between a and b. And since you declared them as signed types, the compiler is entitled to assume that you know what you are doing and a will never have a value that makes a+5 overflow. It can assume the mathematical relationship between a and b.

A correct thing for the compiler to do here is to replace the whole thing with "a=cntcomp=cntsubs=0". And in fact I see gcc -O1 doing exactly that.

The correct way to do this is to store the timestamps as unsigned -- which the compiler must treat as modulo(2^32) arithmetic -- and to cast the result of the subtraction to signed.

Code: [Select]

int timeHasElapsed(unsigned timeStamp, unsigned now){
  return (int)(now - timeStamp) > 0;
}

Note that you can only set a timestamp a maximum of 2^31-1 ticks ahead of the current time. If you need a larger delay than that then you'll have to do it in parts. You also must call timeHasElapsed() less than 2^31 ticks after the current time is past the timestamp.

[wek]

The correct way to do this is to store the timestamps as unsigned -- which the compiler must treat as modulo(2^32) arithmetic -- and to cast the result of the subtraction to signed.

Strictly speaking, this is not entirely flawless either. While subtraction of two unsigned integers indeed won't overflow thanks to second sentence of C99 6.2.5#9, casting unsigned to signed of the same width is implementation defined (6.3.1.3#3), so you have to check documentation of your compiler and accept that it's non-portable.

JW

[brucehoult]

The correct way to do this is to store the timestamps as unsigned -- which the compiler must treat as modulo(2^32) arithmetic -- and to cast the result of the subtraction to signed.

Strictly speaking, this is not entirely flawless either. While subtraction of two unsigned integers indeed won't overflow thanks to second sentence of C99 6.2.5#9, casting unsigned to signed of the same width is implementation defined (6.3.1.3#3), so you have to check documentation of your compiler and accept that it's non-portable.

It's implementation defined because of sign-magnitude and ones-complement machines. Which, probably, no one here has ever used or will ever use in future.

A compiler would have to really go perversely out of its way to make it not work as intended on twos-complement machines.

Feel free to instead use ...

Code: [Select]

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

... which should be as fast or faster.

[Jeroen3]

Key thing here is that time is kept unsigned.
So uses of time, eg: next = now + 100 do not give you a negative result which would cast poorly into bruceholts function.

That you store it in an unsigned 31 bit variable is your extra work. If's everywhere you might wraparound. Lots of points for bugs.

This is one of those functions that you really want tight unit tests for  becasue if not, the bugs it will produce are sporadic and difficult to reproduce.

[eugene]

Hi all,

In an application I use some timestamps (signed 32 bit integers counting μs since system reset) and I want to test if they have elapsed comparing them against current time. Now consider this code (compiled with armclang for Cortex-M4):

Code: [Select]

int a, b, cntcomp, cntsubs;

a = 0;
cntcomp = 0;
cntsubs = 0;

do {
  b = a + 5;      // b is "always" greater that n
 
  if (!(b > a)) {
    ++cntcomp;    // triggered 5 times, when previous add overflows
  }
 
  if (!(b - a > 0)) {
    ++cntsubs;    // triggered 0 times
  }
} while (++a);

What are you actually trying to do here?

The test code is crazy because the compiler can easily see the fixed relationship between a and b. And since you declared them as signed types, the compiler is entitled to assume that you know what you are doing and a will never have a value that makes a+5 overflow. It can assume the mathematical relationship between a and b.

A correct thing for the compiler to do here is to replace the whole thing with "a=cntcomp=cntsubs=0". And in fact I see gcc -O1 doing exactly that.

The correct way to do this is to store the timestamps as unsigned -- which the compiler must treat as modulo(2^32) arithmetic -- and to cast the result of the subtraction to signed.

I have to say that this seems wrong to me. I don't mean that you're wrong about what the compiler will do. I mean the compiler does the wrong thing. A feature of C is that it assumes I know what I'm doing, and consequently does what I say, not what it suspects I might really be thinking. This is why I use C to program microcontrollers where I know (and control) how data is stored in memory. I reserve the right to exploit overflow, no matter how stupid it might look to the compiler!

I understand your explanation that storage of signed int is implementation dependent. But if the compiler is going to assume that I know what I'm doing, then it should assume that I know how signed int (and especially int32_t) is stored with the hardware and compiler that I'm using. I depend on that.

How about changing the declarations of a and b from int to int32_t? Int is defined more loosely than int32_t, so maybe if I explicitly ask for 32 bits to store my signed integer the compiler will get the hint? No. Same result.

[/rant]

I know my objections aren't going to change the minds of the people that write the standards, but I might need to start coding everything in assembly.

[Siwastaja]

Signed overflow is implementation-defined undefined behavior, so it's your responsibility to run time check absence of overflow.

Instead, unsigned overflow is well defined and does exactly what you need (modulo-2^n wrapping), works perfectly with timestamps.

So keep the two timestamps uint32_t, subtract then, and then, you can cast the result to int32_t if you want the range from - 2^31 ..  2^31 - 1.

Oh boy I did hunt a bug for a long time, caused by using signed ints for timestamps and assuming it just works.

[hans]

With GCC, I can't fault it: https://godbolt.org/z/vhbzYffnx
All compare functions should return true if 'b' is greater than 'a', even when datatype overflows.

Subtraction arguments can be reversed for slight optimizations (such as not having to negate the result)

It looks like a bitshift or a mask is the fastest method, but both will need to be aware of the timestamp size and/or subtraction result size.
CLang seems to outsmart us and produces less-than-reliable results for signed timestamps: https://godbolt.org/z/fT89G89aG

Even the template instantations are subject to Clangs aggressive mathematical optimizations, and breaks the function for the signed case, except when the intermediate result 'sub' is made volatile (!).
Sounds like a Clang bug to me.

[NorthGuy]

My problem is that I cannot (easily) coerce the compiler to always perform the comparison in the right way, and the same (b - a > 0) expression above, placed in other part of the program (or using different compiler options), may result in the wrong test.

If so, this is a bug in the compiler. Post the example when this happen along with the disassembly.

Subtraction is the same whether arguments are signed or unsigned, the only thing to worry about is the type of the result of the subtraction which affects the comparison.

If a and b are signed, the result will be signed too, so the comparison will work. If they're unsigned, the result will be unsigned and the comparison will not work, so you would have to cast or isolate the sign bit.

Either way, this will work for up to (2^31-1)-long intervals. Longer intervals will produce wrong results.

[Siwastaja]

If so, this is a bug in the compiler.

Compiler bugs are possible, but rare. First suspect your own code.

Subtraction is the same whether arguments are signed or unsigned

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.

Of course, if the result never overflows, then it does not matter, but the OP said they are counting microseconds from boot. So if the thing runs longer than 35 minutes, an overflow will happen. Therefore, unsigned type should be used. Signed type can be used if the code is designed to work with a specific compiler (and version), and the documentation of the compiler or disassembly/testing of the code proves the code works correctly. But this makes no sense, as you can write standard portable code just as easily, by just using unsigned type.

[NorthGuy]

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. 

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)

Of course, if the result never overflows, then it does not matter, but the OP said they are counting microseconds from boot. So if the thing runs longer than 35 minutes, an overflow will happen. Therefore, unsigned type should be used. Signed type can be used if the code is designed to work with a specific compiler (and version), and the documentation of the compiler or disassembly/testing of the code proves the code works correctly. But this makes no sense, as you can write standard portable code just as easily, by just using unsigned type.

I use unsigned for timestamps but for a different reason. Simply because the timestamp cannot really be negative. But IMHO, the compiler will produce the same code for either signed or unsigned, because on the CPU level there's only one subtraction command (except for older MIPS perhaps) which doesn't give the compiler much choice, unless the compiler decides to be destructive on purpose. Do you have any real-world examples where a compiler generated any code which produced incorrect overflow for signed integers?

[Siwastaja]

Do you have any real-world examples where a compiler generated any code which produced incorrect overflow for signed integers?

I hunted for such a bug for months. It was a wheel position count, in int16_t, and difference between the previous and current count (every millisecond or so), correct result being almost always -1, 0 or +1 (maybe sometimes -2 or +2, when going really fast). When the count was wrapping around +/-32768, the result was a large number, so a sudden jump in integration occurred. All I did to solve the problem was to read the standard, which said this is UB, and thus, change it to a unsigned operation for the desired modulo-32768 arithmetic. This fixed the issue. I did never look at the disassembly. This was Cortex-M3 and GCC.

Relying on UB is rarely a good idea, even if you think you are smart enough to do it. Especially when there is no upside. Just use unsigned types when overflow is expected, and modulo-2^n operation required.

[NorthGuy]

I hunted for such a bug for months. It was a wheel position count, in int16_t, and difference between the previous and current count (every millisecond or so), correct result being almost always -1, 0 or +1 (maybe sometimes -2 or +2, when going really fast). When the count was wrapping around +/-32768, the result was a large number, so a sudden jump in integration occurred.

That's the integer promotion. With signed, 0x7fff gets promoted to 0x00007fff, while 0x8000 gets promoted to 0xffff8000, hence the huge difference. With unsigned, it works as expected. Assigning the result to a 16-bit variable would fix it too. Using 32-bit signed integers would work too.

[SiliconWizard]

(...)
Relying on UB is rarely a good idea, even if you think you are smart enough to do it.

Not rarely: NEVER. And I would say: especially if you think you are smart enough.
Of course, the problem often is that the developer may not even know what is UB and what isn't. And this is a whole topic in itself.

[cv007]

Not rarely: NEVER.

Never may be a little strong. We get UB every time we access the mcu hardware.

In an application I use some timestamps (signed 32 bit integers counting μs since system reset)

Maybe describe what those timestamps are since they are signed- counts up to 0x7FFFFFFF then what? Are there negative timestamps?

[hans]

If a and b are signed, the result will be signed too, so the comparison will work. If they're unsigned, the result will be unsigned and the comparison will not work, so you would have to cast or isolate the sign bit.

Subtractions are "promoted" to an int32 for many platforms, for example ARM and x86. Let's take this example:

Code: [Select]

uint8_t calc() {
  uint8_t a = 0;
  uint8_t b = 1;
  return (a - b) >> 1;
}
This function will return 255. But so will:

Code: [Select]

uint8_t calc() {
  uint8_t a = 0;
  uint8_t b = 1;
  return (a - b) >> 32;
}Only here the compiler will warn that '32' is wider than the type width. That warning threshold is passed at 31/32 shifts, meaning that (a-b) returns an int32, which is arithmetically shifted right (sign extension), and then downcasted to a uint8_t for the out result.

I can't find explicitly, right now, what return type a subtract operation in C should have, but it seems like many conversions and these kind of 'basic' operations are implementation specific in the manual. Is that UB? Probably, to some degree.. but if that implementation specific is as generic 2s complement and perhaps little-endian, then I'm sure the code will work on a majority of systems (and break on others, but that's similar to how you can mess around with pointers and break things on systems without unaligned memory access support)

Intuitively it makes sense to me why a subtraction would be signed by default: the compiler doesn't know if lhs or rhs is larger, and so therefore the result can be positive or negative. If you can guarantee that lhs>=rhs, then you can typecast the signed result to unsigned without risk of underflow.

It's unfortunate that we don't have CPUs with int33 for cases like this (or a carry bit in a status register), because that MSB/Carry bit will tell you if the result has gone negative, and would basically act as the comparator for this use-case.

(also see: https://youtu.be/R6_PFqOSa_c)

[DavidAlfa]

What processor doesn't have Carry/Borrow bit? That's one of the most basics CPU features since... ever?

[hans]

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).

I just looked up the C99 standard, and it looks like "integer promotions" are a core part of the C standard. The video I linked said that unsigned-unsigned should return unsigned, but still, I can't find a specific mention of that specification in the manual. The manual says on 6.3.1.1 bulletpoint 2, that if a result fits in 'int', then it should be promoted to int.

The compiler argument -Wconversion (not included in -Wall) does help catch these kind of things.. but it can also extremely tiresome to use.

Edit: I seem to be somewhat mistaken, it seems like "integer promotion" does not happen for types that are already unsigned 32-bit..

[brucehoult]

What processor doesn't have Carry/Borrow bit? That's one of the most basics CPU features since... ever?

Many of the world's fastest computers (at the time they were released):

1964: CDC 6600
1975: CRAY 1
1985: MIPS
1992: DEC Alpha

And, as already mentioned, RISC-V (2015).

Not a one of them has a carry flag, or zero, negative, or overflow flags either. For integer calculations.

FP does tend to have a flag saying whether overflow has happened in at least one instruction since it was last reset.

There was a recent thread in which we compared adding the numbers up to 100,000,000 in various languages. Someone proposed some ARM assembly language using the carry flag to implement double precision adds. I showed RISC-V code that did it (obviously) without a carry flag. It needed one more instruction in the loop -- 5 instead of 4.

Interestingly (to me), when I ran both on QEMU on the same machine, the RISC-V code was 20% faster not 25% slower as you might expect (the ARM code took 25% longer then the RISC-V).

https://www.eevblog.com/forum/programming/python-becomes-the-most-popular-language/msg4161652/#msg4161652

[SiliconWizard]

I remember a discussion we had on RISC-V regarding carry flags and how they were a pain to deal with, in particular for instruction dependency in a pipeline.

[brucehoult]

I remember a discussion we had on RISC-V regarding carry flags and how they were a pain to deal with, in particular for instruction dependency in a pipeline.

I wrote something recently about the three steps needed to compare two variables and branch based on that, and five different ways various ISAs split those steps up into different instructions and communicate between those different instructions.

It's at ...

https://www.reddit.com/r/embedded/comments/uihmry/comment/i7dpc4h

... but I'll copy it here. The initial reference point was PIC.

-------

One further example: there are no conditional branch instructions but instead conditional skips, so to conditionally branch you skip one instruction and goto !

That's a lot less weird than having the awful memory paging only because they were too cheap to put a wide adder in the address generation.

Many ISAs have quite limited range on their conditional branch instructions -- often just 8 bit range i.e. ±128 bytes (or instructions). Some only have 3 or 5 bit branch offsets. If that's far enough then great. If it's not then you reverse the condition and branch over a jump. With the very short fixed length instructions in PIC (just 12 bits in some models, 14 in many more) they don't have room to encode a branch offset along with the 5 or 7 bit register number and 3 bits for the bit to test, and 1 bit for whether to branch on clear or set.

Doing a conditional branch based on two variables has three parts to it:

1) subtracting the two values,

2) deciding if the relationship you want to test (eq, ne, lt, ge) is true or false, and

3) branching to the destination if the test succeeds.

RISC-V with fixed size 32 bit instructions does all this in one instruction:

Code: [Select]

blt r12,r13,.+345 // ±4 KB range

In PIC this needs four instructions (unlike the other examples, this is unsigned, signed is harder on baseline/PIC12/PIC16 with only C and Z flags, N was added in PIC18)...

Code: [Select]

movf 13,1
subwf 12,w
btfsc 3,0 // C is bit 0 of register 3
goto 345 // relative addressing not supported

Probably the largest number of ISAs combine the first two instructions into a cmp (sub that doesn't write the result anywhere) that sets a multi bit flags register, then combine the test of which condition is desired (eq, ne, lt, ge, and others) and the branch into a single instruction:

Code: [Select]

cmp r12,r13
blt .+345

But a few use a general register to store a 1 or 0, and combine the subtract and the comparison type in one instruction, then branch simply on true/false. e.g. MIPS

Code: [Select]

slt r8,r12,r13
bne r8,.+345

Another variation is to have a kind of condition code register but have only one bit, which functions the same as r8 in the above MIPS code. e.g. SuperH

Code: [Select]

cmp/ge r13,r12 // result stored in T bit
bt .+345 // branch if T bit is True


[emece67]

.

[newbrain]

The video I linked said that unsigned-unsigned should return unsigned, but still, I can't find a specific mention of that specification in the manual.

Edit: I seem to be somewhat mistaken, it seems like "integer promotion" does not happen for types that are already unsigned 32-bit..

The relevant chapter is "6.3.1.8 Usual arithmetic conversions", whose purpose is:

he purpose is to determine a common real type for the operands and result.

(real types are integers and non complex FP, 6.2.5§17).
After all the FP descriptions, but still in §1,  we have:

Otherwise, the integer promotions are performed on both operands. Then the following rules are applied to the promoted operands:
If both operands have the same type, then no further conversion is needed.

So two unsigned integers (of any rank/width) will always give an unsigned result.

[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.

[SiliconWizard]

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 ?

Not sure about that, and that's probably precisely why they are removing any other possibility from the standard. Makes everyone's life easier, without harming any foreseeable platform.

If the underlying question is, "why so late?", then that may look like a fair question, but this slow rate of change has been one of the reasons things haven't been broken in any major way with the C language over the years, and why it's still relevant after 5 whole decades.

[brucehoult]

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 ?

One assumes they've checked :-)

Long shot, but did you have this username on BIX?

[hans]

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.

That's true, but the optimization and code generation will happen in multiple steps, and optimization may not need to account all side-effects from the actual code generation (since it's UB). Therefore the optimizer won't "see" the 2's complement signed overflow side effects, and any satisifyability solver will transform those expressions. When the compiler is forced to use/store an intermediate result (like `a-b`) into an int32 (or fwrapv to add it under the hood), then the optimization is split into 2 steps with the arithmetic world in betwee, and will it actually see the overflow.

Personally I think a compiler that leaves as little UB as possible is better, especially since on any modern platform this is not even UB.

Anyhow, I think that on new systems a 64-bit unsigned integer for (high res) timestamping is the easiest fix. Even if you keep time at 1GHz in unsigned 64-bit, you won't have an overflow in 585 years. But perhaps that's is a bit beyond the scope of this topic.

[brucehoult]

Anyhow, I think that on new systems a 64-bit unsigned integer for (high res) timestamping is the easiest fix. Even if you keep time at 1GHz in unsigned 64-bit, you won't have an overflow in 585 years. But perhaps that's is a bit beyond the scope of this topic.

Yes. And you can easily do it even if you only have a 32 bit hardware counter, as long as you look at the counter at least (at your 1 GHz) every four seconds or less. If the counter value is smaller than last time you looked at it then increment the upper half.