Comparing int and uint in C

[NorthGuy]

On the other hand, timers and counters are exacly the sort of situations that cause problems with unsigned variables.  Because people inevitably want to subtract them.

That's what they're for. To subtract them and thereby determine the number of ticks between two counts. What problem is this causing?

[brucehoult]

You'd imagine no problem, as long as you do the subtraction in the correct order.

At least you always get a meaningful and correct answer if you subtract two unsigned numbers (in the correct order).

If you subtract signed numbers you can get massive overflows. e.g. -128 - 127 is -255 and 127 - -128 is +255, both far outside the range of an 8 bit signed number so they're produce incorrect 1 and -1 results respectively. (And a set V flag if you have one of those)

[SiliconWizard]

Yes - unsigned arithmetics in C is pretty straightforward, it's just the expected operations modulo 2^N.
So yes, subtracting two unsigned timer values (for instance) is guaranteed to be correct even if the timer overflowed (and so wrapped around) between the two timestamps (as long as it overflowed only once).
It's fun to see how many devs still have a hard time with that and are unsure that it will be correct.

[brucehoult]

Yes - unsigned arithmetics in C is pretty straightforward, it's just the expected operations modulo 2^N.
So yes, subtracting two unsigned timer values (for instance) is guaranteed to be correct even if the timer overflowed (and so wrapped around) between the two timestamps (as long as it overflowed only once).

More correctly end - start is correct if and only if fewer than 2^N ticks have elapsed between them.

Wrapping once is bad if end has also gone past start since then.

[5U4GB]

You also need to be careful if you're using stdlib time sources rather than hardware-specific timers and counters since you need to handle time running backwards or moving forwards discontinuously. Our code has an entire module to make sure that some sort of sane behaviour is preserved in these cases.

[peter-h]

A non monotonic clock will break a lot of code

That's why when I do GPS RTC sync I do it once a minute, when secs=0 (a few ms after) so there are no funny values appearing.

[SiliconWizard]

Yes - unsigned arithmetics in C is pretty straightforward, it's just the expected operations modulo 2^N.
So yes, subtracting two unsigned timer values (for instance) is guaranteed to be correct even if the timer overflowed (and so wrapped around) between the two timestamps (as long as it overflowed only once).

More correctly end - start is correct if and only if fewer than 2^N ticks have elapsed between them.

Yes, that was obviously implied by the modulo 2^N arithmetics: results are always modulo 2^N, so must be strictly less than 2^N to be correct. Otherwise the true result will be result + k* 2^N with k >= 1.

So that works only if the elapsed time is strictly less than 2^N. No way around it. Check that this assumption always hold true in a given use case, and all you need is just unsigned subtraction.

Wrapping once is bad if end has also gone past start since then.

modulo 2^N arithmetics guarantees that the subtraction will be correct as long as the actual difference is strictly less than 2^N, as we said above. Once that guarantee holds, 'end' cannot wrap around and become equal to or greater than 'start' after having wrapped once. It's just not possible. It happens only if the actual difference is greater than or equal to 2^N.

So if elapsed time is < 2^N and 'end' happens to wrap, the subtraction is correct. That's the point that many people often seem unsure of.

Of course, if you can't guarantee that elapsed time between timestamps is strictly less than 2^N, then you have to handle timer overflow properly, and that will usually be equivalent to implementing an extended timer (counting overflows as a most significant part of the timer), and you have to guarantee that you can count overflows that without the timer overflowing more than just once in between successive overflows.

[langwadt]

I've often used that "trick" to extend a 16bit quadrature decoder timer to 32bit. At some rate fast enough that the 16 bit position will never wrap more than once, subtract previous and current position and add that to a 32bit variable

[5U4GB]

A non monotonic clock will break a lot of code

Yup, which is why we go to great lengths to try and avoid that.  Just had a look at the clock/time module and it's around 1k LOC, with a good chunk of that being tests for all the possible cases, e.g. clock goes foward, clock jumps backwards, clock keeps going forward again from the earlier time.  This sort of thing isn't entirely unheard-of when you've got devices with RTCs that run in isolation for extended periods of time and then have them pulled back into sync at some random moment when they briefly get access to a reliable time source.

[brucehoult]

A non monotonic clock will break a lot of code

Yup, which is why we go to great lengths to try and avoid that.  Just had a look at the clock/time module and it's around 1k LOC, with a good chunk of that being tests for all the possible cases, e.g. clock goes foward, clock jumps backwards, clock keeps going forward again from the earlier time.  This sort of thing isn't entirely unheard-of when you've got devices with RTCs that run in isolation for extended periods of time and then have them pulled back into sync at some random moment when they briefly get access to a reliable time source.

Having also done that kind of thing, I can't see why it's THAT complicated.

You tend to have two different kinds of things:

1) ones that need to be done at regular intervals: use the CPU clock, which never jumps around, other than wrapping

2) ones that need to be done at a particular RTC time. Just keep them in order and when the request is added, if the current time is already past that time for whatever reason, then perform that action immediately. Or, more precisely, add it into the queue in the correct order and then perform in order all actions that should be at or before the current time.

You might in some cases prefer to not do certain actions if they are very late, but that logic can be in those actions.

[peter-h]

How does windoze avoid time jumping backwards?

It can be done only by slowing the clock down (or even stopping it) until it catches up with the correct time.

[gf]

How does windoze avoid time jumping backwards?
It can be done only by slowing the clock down (or even stopping it) until it catches up with the correct time.

The w32time service corrects the system clock by slewing small offsets and stepping large ones that exceed a configurable threshold, similar to ntpd and chrony on Linux.

[Alien Brother]

Let me abuse this topic for a much broader question: What's the autoritative source about C?

Not authoritative, but cppreference.com is my favourite place to look things up. For this particular topic, it would have somewhere the explanation of how integer promotions are defined.

[udok]

On all modern computers (pretty much anything since 1970 I would say), -N is represented as 2^16-N, or 2^32-N or 2^64-N depending on the data type size.

This is not entirely true. Digital Signal Processors (DSP) traditionally represented integers as absolute values with a sign bit (they have +0 and -0 too).
They implemented saturation arithmetic with no wraparound and provide guard bits in the accumulator to handle temporary overflows.
Two complement integers are not suitable for serious numeric work because of great errors you get in case of overflows.
The fixed point integer format uses simple and fast hardware.
Because of cheap hardware and convenience most DSP switched to floating point after 2010.

[peter-h]

That's very true.

I suspect the big change over say past 30 years is that normal CPUs have become so fast that far fewer people bother with DSPs. But then you have to handle overflows/underflows etc explicitly.

Recently I had to write a lot of code where one was outputting basically 24 bit integers, sometimes signed sometimes not (the weird and wonderful ARINC429 area) and I went to 64 bit ints where the original 32 bit int could be handled properly when right up to its limit.

[gf]

On all modern computers (pretty much anything since 1970 I would say), -N is represented as 2^16-N, or 2^32-N or 2^64-N depending on the data type size.

This is not entirely true. Digital Signal Processors (DSP) traditionally represented integers as absolute values with a sign bit (they have +0 and -0 too).
They implemented saturation arithmetic with no wraparound and provide guard bits in the accumulator to handle temporary overflows.
Two complement integers are not suitable for serious numeric work because of great errors you get in case of overflows.
The fixed point integer format uses simple and fast hardware.
Because of cheap hardware and convenience most DSP switched to floating point after 2010.

The C23 standard officially mandates two's complement representation for all signed integer types. If the machine does not support it natively, the compiler is expected to emulate it.

For DSP and embedded systems, the ISO/IEC TR 18037 extensions support fixed-point types that allow saturation, such as _Sat signed _Fract (Saturating fixed-point fraction) or _Sat signed _Accum (Saturating accumulator).

[NorthGuy]

I suspect the big change over say past 30 years is that normal CPUs have become so fast that far fewer people bother with DSPs. But then you have to handle overflows/underflows etc explicitly.

Many CPU have saturating instructions, for example Cortex-M4 which you use.

[peter-h]

Every day is a school day

Does GCC implement them?

[Siwastaja]

Every day is a school day

Does GCC implement them?

It might use them when optimizing, but if you want to be sure they are emitted, you might want to use asm intrinsics, which you could also use with the SIMD instructions anyway. As always, profiling the performance and looking at the output and hand-optimizing if necessary is still the way to go.

[NorthGuy]

Every day is a school day

Does GCC implement them?

Usually there are builtins for such things, but I never use them. Writing a few lines in assembler seems much easier to me than figuring out the builtins.

[gf]

Every day is a school day

Does GCC implement them?

See https://gcc.gnu.org/onlinedocs/gcc/Fixed-Point.html

But not all targets support fixed-point types.

[SiliconWizard]

That's very true.

I suspect the big change over say past 30 years is that normal CPUs have become so fast that far fewer people bother with DSPs. But then you have to handle overflows/underflows etc explicitly.

So you mean we use floating point pretty much everywhere these days, and rarely fixed-point. That's mostly true. But fixed-point DSPs still exist and have some uses, although that's becoming more niche.

FP is not completely without its own issues though, so there are cases where fixed point is better because it's easier to reason about. FP can get tricky when it comes to corner cases.

[westfw]

Quote from: peter-h on Today at 04:26:25 am

Does GCC implement them?

Saturating instructions, or fixed point math?

I believe recent versions have added support for fixed point math.
Processors with "DSP" instructions usually have a vendor-provided library for using them, for example https://arm-software.github.io/CMSIS_6/latest/Core/group__intrinsic__SIMD__gr.html and https://arm-software.github.io/CMSIS_5/DSP/html/index.html
(In the case of ARM-based chips, ARM (the Core IP vendor; not a chip vendor) tries to enforce the standardization of such functions (via CMSIS) across chip and compiler vendors.)

[peter-h]

Saturating maths.

[brucehoult]

Now known as "rangemaxing"