Rollover safe timer (tick) comparisons

Question

I have a counter in hardware that I can observe for timing considerations. It counts miliseconds and is stored in a 16 bit unsigned value. How do I safely check if a timer value has passed a certain time and safely handle the inevitable rollover:

//this is a bit contrived, but it illustrates what I'm trying to do
const uint16_t print_interval = 5000; // milliseconds
static uint16_t last_print_time;   

if(ms_timer() - last_print_time > print_interval)
{
    printf("Fault!\n");
    last_print_time = ms_timer();
}

This code will fail when ms_timer overflows to 0.

Cola

Answer 1

You don't actually need to do anything here. The original code listed in your question will work fine, assuming ms_timer() returns a value of type uint16_t.

(Also assuming that the timer doesn't overflow twice between checks...)

To convince yourself this is the case, try the following test:

uint16_t t1 = 0xFFF0;
uint16_t t2 = 0x0010;
uint16_t dt = t2 - t1;

dt will equal 0x20.

Koger

When I run the original code it works up to the over flow point and then prints for every count. – Cola

My final stab-in-the-dark, given the original behaviour and your replacement solution, is that your x variable / ms_timer() function is / returns an int larger than 16 bits, which causes an unintended type promotion when calculating the time difference. – Koger

Answer 2

I use this code to illustrate the bug and possible solution using a signed comparison.

/* ========================================================================== */
/*   timers.c                                                                 */
/*                                                                            */
/*   Description: Demonstrate unsigned vs signed timers                       */
/* ========================================================================== */

#include <stdio.h>
#include <limits.h>

int timer;

int HW_DIGCTL_MICROSECONDS_RD()
{
  printf ("timer %x\n", timer);
  return timer++;
}

// delay up to UINT_MAX
// this fails when start near UINT_MAX
void delay_us (unsigned int us)
{
    unsigned int start = HW_DIGCTL_MICROSECONDS_RD();

    while (start + us > HW_DIGCTL_MICROSECONDS_RD()) 
      ;
}

// works correctly for delay from 0 to INT_MAX
void sdelay_us (int us)
{
    int start = HW_DIGCTL_MICROSECONDS_RD();

    while (HW_DIGCTL_MICROSECONDS_RD() - start < us) 
      ;
}

int main()
{
  printf ("UINT_MAX = %x\n", UINT_MAX);
  printf ("INT_MAX  = %x\n\n", INT_MAX);

  printf ("unsigned, no wrap\n\n");
  timer = 0;
  delay_us (10);

  printf ("\nunsigned, wrap\n\n");
  timer = UINT_MAX - 8;
  delay_us (10);

  printf ("\nsigned, no wrap\n\n");
  timer = 0;
  sdelay_us (10);

  printf ("\nsigned, wrap\n\n");
  timer = INT_MAX - 8;
  sdelay_us (10);

}

Sample output:

bob@hedgehog:~/work2/test$ ./timers|more
UINT_MAX = ffffffff
INT_MAX  = 7fffffff

unsigned, no wrap

timer 0
timer 1
timer 2
timer 3
timer 4
timer 5
timer 6
timer 7
timer 8
timer 9
timer a

unsigned, wrap

timer fffffff7
timer fffffff8

signed, no wrap

timer 0
timer 1
timer 2
timer 3
timer 4
timer 5
timer 6
timer 7
timer 8
timer 9
timer a

signed, wrap

timer 7ffffff7
timer 7ffffff8
timer 7ffffff9
timer 7ffffffa
timer 7ffffffb
timer 7ffffffc
timer 7ffffffd
timer 7ffffffe
timer 7fffffff
timer 80000000
timer 80000001
bob@hedgehog:~/work2/test$ 

Hypo

The delay provided next to INT_MAX has an incorrect length, right? – Aspirin

Answer 3

I used to write code like following for the such case.
I tested with test case and assure that it works 100%.
In addition, change to uint32_t from uint16_t and 0xFFFFFFFF from 0xFFFF in below code with 32 bits timer tick.

uint16_t get_diff_tick(uint16_t test_tick, uint16_t prev_tick)
{
    if (test_tick < prev_tick)
    {
        // time rollover(overflow)
        return (0xFFFF - prev_tick) + 1 + test_tick;
    }
    else
    {
        return test_tick - prev_tick;
    }
}

/* your code will be.. */
uint16_t cur_tick = ms_timer();
if(get_diff_tick(cur_tick, last_print_time) > print_interval)
{
    printf("Fault!\n");
    last_print_time = cur_tick;
}

Recumbent

Answer 4

Just check if ms_timer < last_print_time and if so add 2^16 no?

Edit: You also need to up to an uint32 for this if you can.

Chalkboard

Answer 5

Probably the safest way to avoid the problem would be to use a signed 32-bit value. To use your example:

const int32 print_interval = 5000;
static int32 last_print_time; // I'm assuming this gets initialized elsewhere

int32 delta = ((int32)ms_timer()) - last_print_time; //allow a negative interval
while(delta < 0) delta += 65536; // move the difference back into range
if(delta < print_interval)
{
    printf("Fault!\n");
    last_print_time = ms_timer();
}

Priedieu

Answer 6

This seems to work for intervals up to 64k/2, which is suitable for me:

const uint16_t print_interval = 5000; // milliseconds
static uint16_t last_print_time;   

int next_print_time = (last_print_time + print_interval);

if((int16_t) (x - next_print_time) >= 0)
{
    printf("Fault!\n");
    last_print_time = x;
}

Makes use of nature of signed integers. (twos complement)

Cola

Answer 7

I found that using a different timer API works better for me. I created a timer module that has two API calls:

void timer_milliseconds_reset(unsigned index);
bool timer_milliseconds_elapsed(unsigned index, unsigned long value);

The timer indices are also defined in the timer header file:

#define TIMER_PRINT 0
#define TIMER_LED 1
#define MAX_MILLISECOND_TIMERS 2

I use unsigned long int for my timer counters (32-bit) since that is the native sized integer on my hardware platform, and that gives me elapsed times from 1 ms to about 49.7 days. You could have timer counters that are 16-bit which would give you elapsed times from 1 ms to about 65 seconds.

The timer counters are an array, and are incremented by the hardware timer (interrupt, task, or polling of counter value). They can be limited to the maximum value of the datatype in the function that handles the increment for a no-rollover timer.

/* variable counts interrupts */
static volatile unsigned long Millisecond_Counter[MAX_MILLISECOND_TIMERS];
bool timer_milliseconds_elapsed(
    unsigned index,
    unsigned long value)
{
    if (index < MAX_MILLISECOND_TIMERS) {
        return (Millisecond_Counter[index] >= value);
    }
    return false;
}

void timer_milliseconds_reset(
    unsigned index)
{
    if (index < MAX_MILLISECOND_TIMERS) {
        Millisecond_Counter[index] = 0;
    }
}

Then your code becomes:

//this is a bit contrived, but it illustrates what I'm trying to do
const uint16_t print_interval = 5000; // milliseconds

if (timer_milliseconds_elapsed(TIMER_PRINT, print_interval)) 
{
    printf("Fault!\n");
    timer_milliseconds_reset(TIMER_PRINT);
}

Girhiny

Answer 8

Sometimes I do it like this:

#define LIMIT 10   // Any value less then ULONG_MAX
ulong t1 = tick of last event;
ulong t2 = current tick;

// This code needs to execute every tick
if ( t1 > t2 ){
    if ((ULONG_MAX-t1+t2+1)>=LIMIT){
       do something
    }
} else {
if ( t2 - t1 >= LIMT ){
    do something
}

Impression