5

Currently, im working on an embedded project, where most of the subsystems are based on timing.

i have searched for many solutions to avoid issues with timers rolling over, but one thing still puzzles me.

At present time, i am using the twos complement of unsigned long's like this.

ulong t1 = tick of last event;
ulong t2 = current tick;
if ( t2 - t1 >= limit ){
 do something
}

Others have suggested, that it is necessary to cast the result of t2-t1 to a signed entity, before this will work, but that i can't understand why. Any other insights or suggestions?

Barath Ravikumar
  • 5,658
  • 3
  • 23
  • 39
olekaiwalker
  • 51
  • 2
  • This question might shed light on the issue http://stackoverflow.com/questions/2084949/arithmetic-operations-on-unsigned-and-signed-integers – mathematician1975 Jul 25 '12 at 09:55
  • I'm sure I've been over this before a few times. I used signed ints, but had to be careful how I compared them. IIRC, I had to compute the elapsed count by adding the interval to the start count, then, on each check, subtract the current tick from the elapsed tick and compare the result to 0. Something like that anyway - does anyone else know more? – Martin James Jul 25 '12 at 12:17

3 Answers3

2

Sometimes I do it like this:

ulong t1 = tick of last event;
ulong t2 = current tick;

if ( t1 > t2 ){
    if ((ULONG_MAX-t1+t2+1)>=limit){
       do something
    }
} else {
if ( t2 - t1 >= limit ){
    do something
}
Jeff
  • 1,364
  • 1
  • 8
  • 17
  • The condition `if (t1 > t2) { ... }` is useless because `ULONG_MAX + 1 = 0`. The whole trick is based on the concept that the difference between two `unsigned int` numbers is always computed correctly, regardless the overflow. For example `5 - 10 = 11`, with 4-bit unsigned integers, because this is the result of `21 - 10 = (16 + 5) - 10` when using 5 bits. The extra bit is not virtual, rather it is quite real: it's the carry bit. – lorcap Oct 15 '12 at 13:00
0

If it is guaranteed that t2 is conceptually always larger than t1, casting to a signed entity would be wrong. Arithmetic of unsigned integers is guaranteed by the standard to be correct modulo UTYPE_MAX + 1, so the difference t2 - t1 will be correct modulo ULONG_MAX + 1 when calculated as unsigned longs. When casting to a signed entity, the behaviour is implementation defined if the value is not representable in the target type. Often that converts large positive values to negative values.

The test

if ( t2 - t1 >= limit ){

will break down if the difference between the current tick count and the previous without wrapping of the timer becomes larger than ULONG_MAX, but otherwise it works.

But if t2 could be earlier than t1, the true difference t2 - t1 would be negative, but as an unsigned long, it would be a potentially large positive number. Then casting to a signed type can work correctly in cases where using unsigned types doesn't.

Daniel Fischer
  • 181,706
  • 17
  • 308
  • 431
  • Even if `t2` is smaller than `t1`, `t2-t1` still shows the correct time difference (if the timer hasn't rolled over more than once). Image `ulong` is 4 bits, `t1=14` and `t2=3 (or 16+3)`. The actual time difference is 5, and the result of `t2-t1` is also 5. – Shahbaz Jul 25 '12 at 10:02
  • That's the situation I handle in the first paragraph. In the last, I talk about the situation where `t2 < t1` _without wrapping_. Then the true difference would be `-11`, but as an unsigned 4-bit integer, that's 5. – Daniel Fischer Jul 25 '12 at 10:07
  • i have implemented some of the code, and made a simple test, and on a simple windows machine nothing strange happened. But on my embedded 16-bit processor, the above code seemed to fail if the result was not cast to a signed long. – olekaiwalker Jul 25 '12 at 15:59
  • What type is `limit`? And is `ulong` really a typedef for `unsigned long`? And could it be that the timer wrapped more than once on the 16-bit processor? – Daniel Fischer Jul 25 '12 at 16:03
  • limit is actually a define but in code it is cast as a unsigned long. No, there is neither a wrap nor two wraps. Could it be some kind of limitation due to the 16-bit nature of the processor. It is like, that no matter if there is a wrap or not, the processor some times has trouble comparing – olekaiwalker Jul 25 '12 at 16:16
  • Could of course be a buggy compiler, but per the standard it ought to work. `t2 - t1` _must_ be the correct value modulo `ULONG_MAX + 1`. If there's no wrap, that must be the mathematically correct value (unless `t2 < t1`, but if `t2` is later than `t1`, that means the timer must have wrapped). Converting that to a `signed long` leaves the value unchanged if it is representable, has implementation-defined semantics otherwise. So casting to a signed type introduces possibilities of going wrong. Is there any possibility of getting some values for which it fails? – Daniel Fischer Jul 25 '12 at 17:35
  • i kinda believe that the compiler might be a bit buggy but it seems very consistent in doing it wrong – olekaiwalker Jul 26 '12 at 05:08
  • Which compiler are you using? – Jeff Aug 04 '12 at 20:00
0

You don't have to cast it to signed. If "do something" is alarm handling code and limit is time interval.

The best practice of the regular intervals is:

 ulong next_alarm_ticks = 0;

 void poll_alarm()
 {
     if (get_ticks() - next_alarm_ticks < ULONG_MAX/2) { 
         // current time is "greater" than next_alarm_ticks
         handle_alarm();
         next_alarm_ticks += alarm_interval;
     }
 }
Dmitry Poroh
  • 3,705
  • 20
  • 34