Measuring Elapsed Time With Counters That Wrap
In embedded systems it is often necessary to measure and/or generate time intervals. Even the smallest microcontrollers typically have a timer/counter register of some sort. By configuring the register to count cycles of a steady clock, the register can be used to measure time. The difference between the count values when event A occurs and when event B occurs gives the elapsed time.
But what if the counter “wraps”, i.e., rolls over from its maximum count back to zero during the measurement interval? No counter can be infinite. I’ve seen various elaborate schemes for dealing with all the contingencies that can arise, particularly when the count value is regarded as a signed integer.
For example, say your platform has a 16-bit timer/counter register and it is being incremented by a steady 1MHz clock. After 65,536 microseconds, it wraps around and starts counting from zero again. Say you need to perform some task B 100 microseconds after event A occurs. The first thought is to simply capture the timer value when event A occurs, add 100 to it, then perform task B when the timer is greater than or equal to the new value. This works fine as long as the timer did not wrap between event A and when task B was supposed to occur. But what if the timer was at, say 65,500 when event A occurred? It will never reach 65,600, so task B will never be performed.
“Well obviously”, you’re thinking, “the arithmetic needs to be done with the same number of bits as the timer so you don’t end up with values larger than the timer can possibly reach!”
Okay, so in this case, we use 16-bit integer arithmetic to arrive at 65,500 plus 100 equals 64. The timer will reach that value, but it is already larger than that the instant event A occurs, so task B will be performed too soon! Clearly, an if statement is called for to detect the special case and correct for it. Or is it?…
Turns out there is a very simple and elegant way to handle this without descending into a morass of if-then-else statements: use subtraction without regard to sign or overflow. This lends itself very nicely to C since one of the “shortcomings” of integer arithmetic in C is that it ignores overflow! Simply subtract the count at time A from the count at time B using unsigned arithmetic of the same size as the counter. If the timer is an 8 bit counter, use unsigned char arithmetic. If it’s 16 bits, use unsigned short. For 32 bits, use unsigned long:
Elapsed Time = B – A
That’s all there is to it!
In the case of our example, while polling the timer after event A, the code should take the present timer value, subtract the value saved when event A occurred, then compare that result to 100. In other words, perform event B when:
(Now – A) >= 100
This works. The approach described in our example above doesn’t always work:
Now >= (A + 100)
Interestingly, even though these two expressions are algebraically equivalent in any infinite number set, they are not equivalent in the case of modulo arithmetic where the set of numbers is finite.
The key to avoiding wrap problems is to perform the unsigned, don’t-care-about-overflow subtraction first, then do any additional operations needed. By using subtraction like this as the first operation, any wrap-around of the timer register that may have occurred just drops out. No special effort is needed to get rid of it!
Of course, the total duration of the counter has to exceed the longest interval to be measured, but not by much. As long as the time to count from zero to maximum is greater than the longest measurement interval, this works. Typically, the hardware counter/timer can be extended in software by utilizing the interrupt on overflow they almost all provide. A very small interrupt service routine that simply increments a static memory variable accomplishes this.
Reading the total count now becomes a little trickier because you have synchronization issues and so forth, but the principle still applies. Extend the hardware counter as much as necessary to make the interval between roll-overs greater than the longest measurement interval, always perform the unsigned subtraction first, and you’re good to go.