davidbrown wrote on Thursday, February 09, 2012:
One thing that is missing from this discussion is to understand that signed integer overflow and wrap is undefined in C. Usually it works as you expect, but not always - and the compiler can take advantage of the undefined behaviour (according to C standards) to generate smaller and faster code, even though it does not work as you expect. So if you are going to define macros like timeAfter, then do it right.
To make the types clearer, use “static inline” functions rather than function-like macros. I know FreeRTOS has to work even on some horrible dinosaur compilers that can’t handle “static inline” functions, and therefore still uses outdated macro styles, but we’ll ignore that here.
The suggestion from the OP was:
static inline bool badTimeAfter(uint16_t a, uint16_t b) {
return (((int16_t)(a) - (int16_t)(b)) > 0);
}
This code looks fine - as long as you call it with “a” and “b” less than half a period apart, it will give the right answer.
However, sometimes it can go wrong. To take a simple example, supposing you call badTimeAfter(0, b) But the compiler can see that “a” is fixed at zero. It knows that “b” is unsigned, and therefore by definition >= 0. So (int16_t)(b) is therefore also >= 0, since signed integer overflow is undefined - either “b” is in range and the value is correct, or it is out of range and the result is undefined, and the compiler can therefore assume anything it likes about the result. Since (int16_t)(b) is >= 0, the compiler can optimise away the entire function with a fixed result “false”. That is certainly not the result you would expect if “b” happened to have it’s MSB set (i.e., it represents a negative number). But the compiler is correct here - the source code is wrong.
When you want to rely on overflows and wraparound, you must use unsigned arithmetic - this is defined explicitly as twos-complement arithmetic.
At first glance, you might think we can do the arithmetic in unsigned, then cast the result to signed for the comparison with 0:
static inline bool bad2TimeAfter(uint16_t a, uint16_t b) {
return ( (int16_t)(a - b) > 0 );
}
That too has a flaw. Since (a -b) is unsigned, it is always >= 0 - if the compiler can figure out that it is non-zero, then it can optimise the function to being always true.
One way to handle unsigned to signed conversions that avoids the risk of undefined behaviour is to use type punning with unions (strictly speaking, this is also undefined behaviour according to the C standards - but there is an unwritten rule that all C compilers define type punning to work as expected):
static inline bool goodTimeAfter(uint16_t a, uint16_t b) {
union { uint16_t u; int16_t s } us;
us.u = (a - b);
return (us.s > 0);
}
Of course, that might miss out on the optimiser’s conversion between “> 0” and “< 0” ("< 0" is usually faster to execute), so you might want to write:
static inline bool goodTimeAfter(uint16_t a, uint16_t b) {
union { uint16_t u; int16_t s } us;
us.u = (b - a);
return (us.s < 0);
}
If you want to avoid type punning (maybe your compiler does something horrible here, like putting the union on the stack), you can stick to unsigned all the way:
static inline bool goodTimeAfter(uint16_t a, uint16_t b) {
uint16_t u = (b - a);
return (u & 0x8000u);
}