Handling Counter Wrap Around

You need to delay a certain amount of time ticks. Easy, right? You can just say:

target=get_ticks()+100;
/* Do some things */
/* wait for target time to pass */
while (get_ticks()<target);

This works fine as long as adding 100 (the delay count) to the current tick counter doesn’t cause an overflow. Remember 100 is 64 hex and consider this 16-bit counter incident (assuming 16 bit math):

target=get_ticks();  // target=0xFFF0
target=target+100;   // target=0054
while (get_ticks()<target);  // get_ticks is FFFE which is not < 54! Immediate fall through

The same problem occurs with any wrap around, regardless of the word size. However, there is an old trick as long as you can do unsigned math. Let’s look at the following cases:

Case A: Current tick=0x0000; target=0x0100

Case B: Current tick=0xFFFE; target=0x00FE

Case C: Current tick=0xFF00; target=0x0000

When you do a subtraction, the top bit will be set if there was a borrow off the end of the word. That is, subtracting 0x0010 from 0x1234 is really the same as subtracting 0x0010 from 0x11234 and and the end you throw away the extra bit at the left. This helps solve our problem. What if you subtracted the target time from the current time?

Let’s consider the case where the tick is just one more than the original current tick:

Case A: 0x0001-0x0100 = 0xFF01

Case B: 0xFFFF-0x00FE= 0xFF01

Case C: 0xFF01-0x0000=0xFF01

And the case where the current tick has wrapped but isn’t up to the target yet (only applies to B):

Case B: 0x0000-0x00FE=0xFF02

Then consider the case when you are one away from matching:

Case A: 0x00FF-0x0100=0xFFFF

Case B: 0x00FD-0x00FE=0xFFFF

Case C: 0xFFFF-0x0000=0xFFFF

Of course, when you hit the target, you get zero. The key takeaway here is that every result will have bit 15 (in this case; the top bit, in general) set until the result matches. This can be fast to implement. For example, here’s a 32-bit timer from an NXP LCP111x delay loop:

// Set up timer 0 
SIM->SCGC6|=SIM_SCGC6_PIT_MASK; 
PIT->MCR=0; 
PIT->CHANNEL[0].LDVAL=0xFFFFFFFF; 
PIT->CHANNEL[0].TCTRL=PIT_TCTRL_TEN_MASK; 
// Ok here's our start time 
counts=PIT->CHANNEL[0].CVAL; 
// do some stuff here and when done 
// compute the target 
count counts=~counts; // convert to count up (this counter runs down) 
counts+=474; // how many ticks before we proceed (40nS per tick + a little overhead) 
do { clock=~PIT->CHANNEL[0].CVAL; // again, convert to up count 
 } while (clock-counts>=0x80000000UL); // could do a bit test here as well (e.g., while (clock_counts[31]);

 

Naturally, there are other ways to solve this. If the timer isn’t used for anything else, I could have preloaded it and waited for it to hit zero, but that’s not always an option.

Leave a Reply