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