Detecting wrap in counter comparisons

I know there should be a fairly simple solution to this, but I can't figure
it out.  I have a situation where I store a store a timeout value, which is
calculated by adding an offset to the current counter.  I need to detect
when the current time has passed the timeout value, and be able to do this
reliably even in the presence of the counter wrapping.

An example:
Assume the counter is 8-bits (in reality it is 32-bits, but the math is
easier with 8), taking on values from 0-255.  Assume the timeout increment
is 10.  If the current counter is 100, then I store 110 as the timeout
value, and flag a timeout when counter > 110.  Fine, no problems.  Now
assume the current counter is 250.  For the timeout value, I store 260,
which aliases to 4.  Now it times out immediately since counter > 4.

I would like to fix the problem ideally by only changing the check for
timeout, not the counter incrementing, calculating of the timeout value,
etc. and also without introducing any new variables if possible.  I know
there are ways to fix it (e.g. adding an extra flag indicating wrap) but I
would like to make minimal changes to this already-released code.  I am
programming in C.

I think there should be some way to detect that the current count and
timeout value have wrapped--absolute value of the difference or something
similar--but haven't managed to figure it out for 32-bit numbers.  Any
ideas?


		
This message was sent using the Comp.DSP web interface on
www.DSPRelated.com

I've got a few ideas.  Maybe one of them will work for you.

* Many processors have this sort of functionality built into the hardware in 
the form of a compare register for the timer.  That way you just update the 
compare register to the desired value and once the timer hits that value you 
get an interrupt.  Sometimes it's in the form of a period register such that 
in your example below the counter would only ever count from 0 to 9 over and 
over again triggering an interrupt each time.

* I don't know your system and how fast the timer is counting, but would it 
be possible to replace your > comparison with an = comparison?  That way you 
wouldn't run into the wrap problem as you would only trigger an event on an 
exact match.

* You could change your software such that rather than looking for a 
specific timer value you could always compute the difference since the last 
event.  I believe that if you use an unsigned int type the wrapping won't 
make a difference.  Take your last example of the timer being 250 and you're 
looking for 4.  You would instead use unsigned ints to do a subtraction.  So 
you'd get:
254-250=4
255-250=5
0-250=6
:
:
4-250=10
You would always have to do a subtraction and then compare the result of the 
subtraction with the period you want.

I hope one of these suggestions help.  Good luck.

Brad

"jharris" <jon_harris7@hotmail.com> wrote in message 
news:T_ydnRAbU-iopHXfRVn-tw@giganews.com...
>I know there should be a fairly simple solution to this, but I can't figure
> it out.  I have a situation where I store a store a timeout value, which 
> is
> calculated by adding an offset to the current counter.  I need to detect
> when the current time has passed the timeout value, and be able to do this
> reliably even in the presence of the counter wrapping.
>
> An example:
> Assume the counter is 8-bits (in reality it is 32-bits, but the math is
> easier with 8), taking on values from 0-255.  Assume the timeout increment
> is 10.  If the current counter is 100, then I store 110 as the timeout
> value, and flag a timeout when counter > 110.  Fine, no problems.  Now
> assume the current counter is 250.  For the timeout value, I store 260,
> which aliases to 4.  Now it times out immediately since counter > 4.
>
> I would like to fix the problem ideally by only changing the check for
> timeout, not the counter incrementing, calculating of the timeout value,
> etc. and also without introducing any new variables if possible.  I know
> there are ways to fix it (e.g. adding an extra flag indicating wrap) but I
> would like to make minimal changes to this already-released code.  I am
> programming in C.
>
> I think there should be some way to detect that the current count and
> timeout value have wrapped--absolute value of the difference or something
> similar--but haven't managed to figure it out for 32-bit numbers.  Any
> ideas?
>
>
>
> This message was sent using the Comp.DSP web interface on
> www.DSPRelated.com 

On Wed, 27 Jul 2005 20:47:33 -0500, "jharris"
<jon_harris7@hotmail.com> wrote in comp.dsp:

> I know there should be a fairly simple solution to this, but I can't figure
> it out.  I have a situation where I store a store a timeout value, which is
> calculated by adding an offset to the current counter.  I need to detect
> when the current time has passed the timeout value, and be able to do this
> reliably even in the presence of the counter wrapping.
> 
> An example:
> Assume the counter is 8-bits (in reality it is 32-bits, but the math is
> easier with 8), taking on values from 0-255.  Assume the timeout increment
> is 10.  If the current counter is 100, then I store 110 as the timeout
> value, and flag a timeout when counter > 110.  Fine, no problems.  Now
> assume the current counter is 250.  For the timeout value, I store 260,
> which aliases to 4.  Now it times out immediately since counter > 4.
> 
> I would like to fix the problem ideally by only changing the check for
> timeout, not the counter incrementing, calculating of the timeout value,
> etc. and also without introducing any new variables if possible.  I know
> there are ways to fix it (e.g. adding an extra flag indicating wrap) but I
> would like to make minimal changes to this already-released code.  I am
> programming in C.
> 
> I think there should be some way to detect that the current count and
> timeout value have wrapped--absolute value of the difference or something
> similar--but haven't managed to figure it out for 32-bit numbers.  Any
> ideas?

The real problem here is that you're computing the time out value at
the beginning.

Even keeping to your 8-bit value, assume you need an interval of 50
clocks and the value at the start is 246.  You add 50 and get 296,
which, with modulo arithmetic in unsigned calculations, becomes 40.

You could detect this wrap around at the time you do the calculation,
by testing that the calculated value is less than either current value
or the interval.  It will be less than either of them.  But what do
you do if there's going to be a warp?

The way I've always done this, which never has a problem with wrap
around, is to NOT precompute the end point.  Keep the start time,
subtract it from the current time (for an up counter), or the current
time from it (for a down counter), and compare the result with the
desired time out interval.

That is, to start timing:

#define TIMEOUT_VALUE 100UL
static uint32_t start_time = hardware_counter;

Then when you want to check the time:

if ((hardware_counter - start_time) > TIMEOUT_VALUE)
{
   /* time is up, do your thing */
}

The rules of C's arithmetic operations on unsigned types guarantees
the subtraction will return the true number of counts between the two,
so long as it hasn't wrapped twice.  So long as the unsigned types you
use are at least as wide as unsigned int, which I assume is the case
here.  You just have to make sure that the counter value, whether you
read it directly from the hardware or have it returned by a function
call, is defined as uint32_t as well.

If your time out interval can't be a constant because it might have
different values under different circumstances, store it in a 32 bit
unsigned int/long, do you don't have problems mixing signed and
unsigned types in a calculation.

BTW, if your counter was a down counter (some hardware counter/timers
only count down), you just reverse the order of the subtraction in the
test:

if ((start_time - hardware_counter) > TIMEOUT_VALUE)
{
   /* time's up! */
}

-- 
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html

jharris wrote:
> I know there should be a fairly simple solution to this, but I can't figure
> it out.  I have a situation where I store a store a timeout value, which is
> calculated by adding an offset to the current counter.  I need to detect
> when the current time has passed the timeout value, and be able to do this
> reliably even in the presence of the counter wrapping.
> 
> An example:
> Assume the counter is 8-bits (in reality it is 32-bits, but the math is
> easier with 8), taking on values from 0-255.  Assume the timeout increment
> is 10.  If the current counter is 100, then I store 110 as the timeout
> value, and flag a timeout when counter > 110.  Fine, no problems.  Now
> assume the current counter is 250.  For the timeout value, I store 260,
> which aliases to 4.  Now it times out immediately since counter > 4.
> 
> I would like to fix the problem ideally by only changing the check for
> timeout, not the counter incrementing, calculating of the timeout value,
> etc. and also without introducing any new variables if possible.  I know
> there are ways to fix it (e.g. adding an extra flag indicating wrap) but I
> would like to make minimal changes to this already-released code.  I am
> programming in C.
> 
> I think there should be some way to detect that the current count and
> timeout value have wrapped--absolute value of the difference or something
> similar--but haven't managed to figure it out for 32-bit numbers.  Any
> ideas?

If at most one wraparound can happen in your longest interval, you know 
that a final count less than the initial count -- an apparently negative 
time according to a naive algorithm -- then a wraparound has happened. 
If more than one wraparound is possible, you need to count them.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

"Jack Klein" <jackklein@spamcop.net> wrote in message 
news:jbgge1poho1hi4jutk6r3923nmfltujrsu@4ax.com...
> On Wed, 27 Jul 2005 20:47:33 -0500, "jharris"
> <jon_harris7@hotmail.com> wrote in comp.dsp:
>
>> I know there should be a fairly simple solution to this, but I can't figure
>> it out.  I have a situation where I store a store a timeout value, which is
>> calculated by adding an offset to the current counter.  I need to detect
>> when the current time has passed the timeout value, and be able to do this
>> reliably even in the presence of the counter wrapping.
>>
>> An example:
>> Assume the counter is 8-bits (in reality it is 32-bits, but the math is
>> easier with 8), taking on values from 0-255.  Assume the timeout increment
>> is 10.  If the current counter is 100, then I store 110 as the timeout
>> value, and flag a timeout when counter > 110.  Fine, no problems.  Now
>> assume the current counter is 250.  For the timeout value, I store 260,
>> which aliases to 4.  Now it times out immediately since counter > 4.
>>
>> I would like to fix the problem ideally by only changing the check for
>> timeout, not the counter incrementing, calculating of the timeout value,
>> etc. and also without introducing any new variables if possible.  I know
>> there are ways to fix it (e.g. adding an extra flag indicating wrap) but I
>> would like to make minimal changes to this already-released code.  I am
>> programming in C.
>>
>> I think there should be some way to detect that the current count and
>> timeout value have wrapped--absolute value of the difference or something
>> similar--but haven't managed to figure it out for 32-bit numbers.  Any
>> ideas?
>
> The real problem here is that you're computing the time out value at
> the beginning.
>
> Even keeping to your 8-bit value, assume you need an interval of 50
> clocks and the value at the start is 246.  You add 50 and get 296,
> which, with modulo arithmetic in unsigned calculations, becomes 40.
>
> You could detect this wrap around at the time you do the calculation,
> by testing that the calculated value is less than either current value
> or the interval.  It will be less than either of them.  But what do
> you do if there's going to be a warp?
>
> The way I've always done this, which never has a problem with wrap
> around, is to NOT precompute the end point.  Keep the start time,
> subtract it from the current time (for an up counter), or the current
> time from it (for a down counter), and compare the result with the
> desired time out interval.

Yes, I had considered that, but hope to change only the comparison code rather 
than the set-up code and data structures.

> That is, to start timing:
>
> #define TIMEOUT_VALUE 100UL
> static uint32_t start_time = hardware_counter;
>
> Then when you want to check the time:
>
> if ((hardware_counter - start_time) > TIMEOUT_VALUE)
> {
>   /* time is up, do your thing */
> }
>
> The rules of C's arithmetic operations on unsigned types guarantees
> the subtraction will return the true number of counts between the two,
> so long as it hasn't wrapped twice.  So long as the unsigned types you
> use are at least as wide as unsigned int, which I assume is the case
> here.  You just have to make sure that the counter value, whether you
> read it directly from the hardware or have it returned by a function
> call, is defined as uint32_t as well.
>
> If your time out interval can't be a constant because it might have
> different values under different circumstances, store it in a 32 bit
> unsigned int/long, do you don't have problems mixing signed and
> unsigned types in a calculation.

Yes, the timeout is variable depending on what the operation is.

Thanks for your reply. 

"Brad Griffis" <bradgriffis@hotmail.com> wrote in message 
news:t6ydnddzJ_kG2XXfRVn-ug@comcast.com...
> I've got a few ideas.  Maybe one of them will work for you.
>
> * Many processors have this sort of functionality built into the hardware in 
> the form of a compare register for the timer.  That way you just update the 
> compare register to the desired value and once the timer hits that value you 
> get an interrupt.  Sometimes it's in the form of a period register such that 
> in your example below the counter would only ever count from 0 to 9 over and 
> over again triggering an interrupt each time.

Not an option here.  It is all software.  :-(

> * I don't know your system and how fast the timer is counting, but would it be 
> possible to replace your > comparison with an = comparison?  That way you 
> wouldn't run into the wrap problem as you would only trigger an event on an 
> exact match.

That is too risky.  The counter advances every millisecond and sometimes a task 
may not be serviced for tens of milliseconds.  If you miss the comparison, then 
you are stuck until a wrap-around occurs (some 49 days later in my system!).

> * You could change your software such that rather than looking for a specific 
> timer value you could always compute the difference since the last event.  I 
> believe that if you use an unsigned int type the wrapping won't make a 
> difference.  Take your last example of the timer being 250 and you're looking 
> for 4.  You would instead use unsigned ints to do a subtraction.  So you'd 
> get:
> 254-250=4
> 255-250=5
> 0-250=6
> :
> :
> 4-250=10
> You would always have to do a subtraction and then compare the result of the 
> subtraction with the period you want.

Unfortunately, the timeout period is not always the same.  In my example, it 
would be 10 sometimes, 3 other times, etc..  So that makes this method difficult 
without introducting extra variables, which I was hoping to avoid.

> I hope one of these suggestions help.  Good luck.
>
> Brad

Thanks for your reply.

> "jharris" <jon_harris7@hotmail.com> wrote in message 
> news:T_ydnRAbU-iopHXfRVn-tw@giganews.com...
>>I know there should be a fairly simple solution to this, but I can't figure
>> it out.  I have a situation where I store a store a timeout value, which is
>> calculated by adding an offset to the current counter.  I need to detect
>> when the current time has passed the timeout value, and be able to do this
>> reliably even in the presence of the counter wrapping.
>>
>> An example:
>> Assume the counter is 8-bits (in reality it is 32-bits, but the math is
>> easier with 8), taking on values from 0-255.  Assume the timeout increment
>> is 10.  If the current counter is 100, then I store 110 as the timeout
>> value, and flag a timeout when counter > 110.  Fine, no problems.  Now
>> assume the current counter is 250.  For the timeout value, I store 260,
>> which aliases to 4.  Now it times out immediately since counter > 4.
>>
>> I would like to fix the problem ideally by only changing the check for
>> timeout, not the counter incrementing, calculating of the timeout value,
>> etc. and also without introducing any new variables if possible.  I know
>> there are ways to fix it (e.g. adding an extra flag indicating wrap) but I
>> would like to make minimal changes to this already-released code.  I am
>> programming in C.
>>
>> I think there should be some way to detect that the current count and
>> timeout value have wrapped--absolute value of the difference or something
>> similar--but haven't managed to figure it out for 32-bit numbers.  Any
>> ideas? 

"Jerry Avins" <jya@ieee.org> wrote in message 
news:YPqdncmggKD0_XXfRVn-hA@rcn.net...
> jharris wrote:
>> I know there should be a fairly simple solution to this, but I can't figure
>> it out.  I have a situation where I store a store a timeout value, which is
>> calculated by adding an offset to the current counter.  I need to detect
>> when the current time has passed the timeout value, and be able to do this
>> reliably even in the presence of the counter wrapping.
>>
>> An example:
>> Assume the counter is 8-bits (in reality it is 32-bits, but the math is
>> easier with 8), taking on values from 0-255.  Assume the timeout increment
>> is 10.  If the current counter is 100, then I store 110 as the timeout
>> value, and flag a timeout when counter > 110.  Fine, no problems.  Now
>> assume the current counter is 250.  For the timeout value, I store 260,
>> which aliases to 4.  Now it times out immediately since counter > 4.
>>
>> I would like to fix the problem ideally by only changing the check for
>> timeout, not the counter incrementing, calculating of the timeout value,
>> etc. and also without introducing any new variables if possible.  I know
>> there are ways to fix it (e.g. adding an extra flag indicating wrap) but I
>> would like to make minimal changes to this already-released code.  I am
>> programming in C.
>>
>> I think there should be some way to detect that the current count and
>> timeout value have wrapped--absolute value of the difference or something
>> similar--but haven't managed to figure it out for 32-bit numbers.  Any
>> ideas?
>
> If at most one wraparound can happen in your longest interval, you know that a 
> final count less than the initial count -- an apparently negative time 
> according to a naive algorithm -- then a wraparound has happened. If more than 
> one wraparound is possible, you need to count them.

My wraparound period is ~50 days (2^32 milliseconds), so multiple wraparounds is 
not a problem.  But I still don't see how to solve the problem--can you 
elaborate? 

Jon Harris wrote:
> "Jerry Avins" <jya@ieee.org> wrote in message 
> news:YPqdncmggKD0_XXfRVn-hA@rcn.net...
> 
>>jharris wrote:
>>
>>>I know there should be a fairly simple solution to this, but I can't figure
>>>it out.  I have a situation where I store a store a timeout value, which is
>>>calculated by adding an offset to the current counter.  I need to detect
>>>when the current time has passed the timeout value, and be able to do this
>>>reliably even in the presence of the counter wrapping.
>>>
>>>An example:
>>>Assume the counter is 8-bits (in reality it is 32-bits, but the math is
>>>easier with 8), taking on values from 0-255.  Assume the timeout increment
>>>is 10.  If the current counter is 100, then I store 110 as the timeout
>>>value, and flag a timeout when counter > 110.  Fine, no problems.  Now
>>>assume the current counter is 250.  For the timeout value, I store 260,
>>>which aliases to 4.  Now it times out immediately since counter > 4.
>>>
>>>I would like to fix the problem ideally by only changing the check for
>>>timeout, not the counter incrementing, calculating of the timeout value,
>>>etc. and also without introducing any new variables if possible.  I know
>>>there are ways to fix it (e.g. adding an extra flag indicating wrap) but I
>>>would like to make minimal changes to this already-released code.  I am
>>>programming in C.
>>>
>>>I think there should be some way to detect that the current count and
>>>timeout value have wrapped--absolute value of the difference or something
>>>similar--but haven't managed to figure it out for 32-bit numbers.  Any
>>>ideas?
>>
>>If at most one wraparound can happen in your longest interval, you know that a 
>>final count less than the initial count -- an apparently negative time 
>>according to a naive algorithm -- then a wraparound has happened. If more than 
>>one wraparound is possible, you need to count them.
> 
> 
> My wraparound period is ~50 days (2^32 milliseconds), so multiple wraparounds is 
> not a problem.  But I still don't see how to solve the problem--can you 
> elaborate? 
> 
> 
So in your code somewhere you have:

int32 timeout = get_sys_time() + interval;

right?

Then if you compute

int32 difference = get_sys_time() - timeout;

difference will now either be negative (indicating that the timeout has 
not yet occurred), zero ('cause you've caught it) or positive ('cause 
it's happened less than 25 days ago).  If it's zero or positive you take 
it as occurred.

Note that this won't work for timeouts more than 12 days in the future...

So if you want to time out in 2 minutes 11 seconds (about 20000 hex) and 
your system timer is at 0xffff0000, your timeout will equal 0x00010000 
('cause it wraps).  For that same time your difference evaluates to 
0xfffe0000, which is negative in a 2's complement system (it is 2's 
complement?  You're not using a 30 year old mainframe?).  At a system 
time of 0x00000000 difference evaluates to 0xffff0000 -- still negative. 
  At a system time of 0x0000ffff your difference evaluates to 0xffffffff 
-- _still_ negative.  At a system time of 0x00010000 your difference is 
zero, and at a system time a good deal above 0x00010000 your difference 
stays positive.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Jon Harris wrote:

   ...

> That is too risky.  The counter advances every millisecond and sometimes a task 
> may not be serviced for tens of milliseconds.  If you miss the comparison, then 
> you are stuck until a wrap-around occurs (some 49 days later in my system!).

   ...

I take it from this that the counter's period is 49 days, and that no 
interval you need to measure lasts that long. So there can be at most 
one wraparound in any interval. You can do as I described in my previous 
message, or use unsigned arithmetic modulo(counter_size).

Do you sample the counter periodically?

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Hello John,

The others have answered for the case where only one so wraps occurs. A
related problem occurs when unwrapping phase. But in this case there
may be multiple wraps across a block of data. So I use to count the
number of increases and number of decreases in phase across the block
and use a voting scheme to determine  what the overall trend is. But
unlike some generic unwrapping algos, you know your counter is always
going in one direction.

Clay