What happened first? Handling timer wraparound

Suppose you had to determine which of two timestamps occurred first. Clearly the “obvious“ approach is to use a simple numerical comparison, for example:

if (ts1 < ts2) {
    ts1_first = TRUE;
} else {
    ts1_first = FALSE;
}

In an embedded system, timestamps are often provided by counters linked to (for example) a system clock. In a typical configuration, these counters increment with every clock tick until they reach their maximum value then wraparound to zero. In many cases the range of the counters is very limited, for example a 16-bit counter is not uncommon. If this timer were linked to a 20MHz clock, a wraparound would occur approximately every 3.3ms.

In practice, this means that code which handles time comparisons must address the wraparound of timers.

When timer wraparound is a possibility, the “obvious” approach we've used above will not work – in fact it produces an intermittent fail (problems only arise when ts1 is read before the wrap and ts2 is read afterwards).

Finding a solution exposes some important constraints we need to impose on our application:

• This test relies upon the assumption that the maximum difference in time between ts1 and ts2 is less than half of the range of the counter (less than 32768 ticks in the case of a 16 bit counter).
• The variables used to record ts1 and ts2 are the same size as the counter (16-bits in the case our our example), and are unsigned.

The test is simply implemented as:

if ((ts2 – ts1) < COUNTER_RANGE/2) { ...

So in a straightforward case, we might have:

ts1 = 0x11 and ts2 = 0x37

This gives 0x37-0x11 = 0x26, which is less than half the counter range (0x8000). If the values were switched, 0x11-0x37, when evaluated with unsigned arithmetic gives 0xffd9. So what happens when the counter wraps? The unsigned integer arithmetic handles this very nicely. For example, if we have ts1 = 0xfff3 and ts2 = 0x0004, the difference between the two values comes out at 0x11.

Automating WCET Analysis for DO-178B & DO-178C

This white paper assesses the current state of practice for determining WCET when working to these guidelines and introduces the benefits that arise from being able to automate this process. With its DO-178B/DO-330 qualification pack, RapiTime (part of Rapita Verification Suite) is unique in allowing these benefits to be realised for DO-178B/C developments.

Download

A slight problem occurs if the counter width is different to the integer size, for example a 12-bit counter. This is simply handled by masking unused bits out after the subtraction:

if ((ts2 – ts1) & 0x0fff) < COUNTER_RANGE/2 { ...

The consequences of handling counter wraparound incorrectly are often intermittent and difficult to detect. Once the need for handling counter wraparound has been identified, it is a relatively simple thing to handle correctly, provided that you can be sure that you only ever compare timestamps that are within half the range of the counter.