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.

Answer 1

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.

Answer 2

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();
}

Answer 3

What if it overflows twice? Is that a scenario that can happen?

Answer 4

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)

Answer 5

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.

Answer 6

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);
}

Answer 7

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$