Timing Rollover

One of the requested items I found was handling 'rollover' from 'millis()' and also, 'micros()'. This is actually not a very difficult matter to deal with, and it's something I've needed to address a lot of times in various contexts, from kernel drivers to applications, and of course, micro-controllers.

First, I shall explain two's complement mathematics, and signed vs unsigned integers.

Two's complement is a way to represent negative numbers in binary. It requires that you sacrifice one bit of precision (the most significant bit), to handle negative values.

For a 16-bit integer, a two's complement value can represent any number between -32768 and 32767, inclusive. For now, this is what I will focus on.

By definition, if you subtract a binary 1 from a binary zero, you should end up with a binary -1. Conversely, if you add a binary 1 to a binary -1, you should get zero.

???????????????? + 0000000000000001 = 0000000000000000

Doing a little atmospheric extrapolation, it's pretty obvious that the following is true.

1111111111111111 + 0000000000000001 = 0000000000000000

If there were another bit shown (i.e. the 'carry' bit) you would see a 17-bit number with the high bit set. But this is the consequence of using a fixed-length binary value. You get 'rollover'.

Consequently to adding binary 1 to "all 1's" to get zero, the following will also be true:

0000000000000000 - 0000000000000001 = 1111111111111111

So the representation of a -1 must be 'all 1 bits' for any two's complement integer, given a fixed-length integer size in bits.

Now it is important to distinguish 'unsigned' from 'signed' integer math. If you want to subtract two unsigned values, and have a negative result if the second is larger, you have to cast the result to a signed integer. This will treat the unsigned result as if it were two's complement, like so:

unsigned int i,j;
...

if( (int)(i - j) < 0 ) { do something }

And, this is the heart of the solution to 'rollover'. In the case where the value of 'i' has not yet 'crossed' the value of 'j', the result of 'i - j' (cast to a signed integer) will be NEGATIVE. If 'i' crosses 'j', the result will be POSITIVE.

Example: Assuming that 'millis()' returned a 16-bit integer (for simplicity), if the current 'millis()' time is 65500 and you want to wait for 1000 milliseconds, you can use unsigned math to add 1000 to 65500 and get a result of 964 (rolling over to zero at what would be 65536). When the '16-bit' millis() 'rolls over' to zero, it will continue to increment until it, too, reaches the value 964. At that point, your timer code can recognize the 'crossing' by subtracting the wait time from millis(), converting it to a signed integer, and checking that it's greater than or equal to zero.

The following code checks to see if you have 'crossed' a 1000 millisecond 'delay point', and initiate's another timer delay of 1000 milliseconds after some kind of periodic processing.

The same kind of code can be applied to 'micros()' as well.

static unsigned long lWaitMillis;

void setup()\\
{
lWaitMillis = millis() + 1000;  // initial setup
}

void loop()\\
{
if( (long)( millis() - lWaitMillis ) >= 0)
{
// millis is now later than my 'next' time

{ do something }

lWaitMillis += 1000;  // do it again 1 second later
}
else
{
// millis is still 'before' my 'next' time
// so I continue waiting

delay(1);  // one possible thing you can do
}
}

Solving the rollover with register arithmetic

The sketch below shows how to use unsigned variables, using the register arithmatic to overcome the rollover problem. The result it send to the serial monitor.

If the calculation for millis() and micros() is done with unsigned long, the difference between the new time and the old time is always valid, even in case of a rollover.

Remember to always use unsigned long variables to make this work.

// -------------------------------------------------------
//
//  Rollover demonstration sketch
//  Solving the rollover with register arithmetic
//
//  Another test sketch for:
//    http://playground.arduino.cc/Code/TimingRollover
//
//  Using parts of:
//
//  public domain
//

// Variables for the demonstration in the setup() function.
// The variables are "volatile" to force the calculation
// in the Arduino microcontroller for this test only.
// You don't need "volatile" in your sketch.
//
volatile byte p, q, r;
volatile unsigned long ulNew, ulOld, ul;

// Variables for the blinking led.
// Created according to:
// But updated to solve the rollover problem.
//
const int ledPin = 13;
int ledState = LOW;
unsigned long ul_PreviousMillis = 0UL;
unsigned long ul_Interval = 500UL;

void setup()
{
Serial.begin( 9600);

// If the Leonardo or Micro is used,
// wait for the serial monitor to open.
while (!Serial);

Serial.println( F("Rollover demonstration sketch."));
Serial.print( F("Solving the rollover problem"));
Serial.println( F(" with register arithmetic."));
Serial.println( "");

Serial.println( F("Test with unsigned 8-bit."));

p = 150;
q = 140;
r = p - q;
Serial.print( F("150 - 140 = "));
Serial.println( r, DEC);

p = 4;         // rollover of value 260
q = 250;
r = p - q;     // valid for unsigned variables
Serial.print( F("260 (=4) - 250 = "));
Serial.println( r, DEC);
Serial.println( "");

Serial.println( F("Test with unsigned long."));
// http://arduino.cc/en/Reference/UnsignedLong

ulNew = 3000000000UL;
ulOld = 2000000000UL;
ul = ulNew - ulOld;
Serial.print( F("3,000,000,000 - 2,000,000,000 = "));
Serial.println( ul, DEC);

ulNew = 705032704UL;  // rollover of value 5,000,000,000
ulOld = 4000000000UL;
ul = ulNew - ulOld;   // valid for unsigned long
Serial.print( F("5,000,000,000 (=705,032,704) - 4,000,000,000 = "));
Serial.println( ul, DEC);
Serial.println( "");

// The loop() function contains an example with millis()
Serial.print( F("A led at pin 13 will blink"));
Serial.println( F(" without rollover error"));
pinMode( ledPin, OUTPUT);
ul_PreviousMillis = millis();
}

void loop()
{
// Here is where you put your code
// that needs to be running all the time.

unsigned long ul_CurrentMillis = millis();

// The next lines are very important
// Since the millis() is unsigned long, also the testing
// and updating the time must be done with unsigned long.
if( ul_CurrentMillis - ul_PreviousMillis > ul_Interval)
{
// Update the last time you blinked the LED
// This update with the interval
// must also be done with unsigned long.
// Option 1:
//     Set the previous time to the current time.
//     A delay by code will shift everyting further in time.
ul_PreviousMillis = ul_CurrentMillis;
//  Option 2:
//     Increment the previous time with the interval.
//     The timing stays in pace.
//     A delay by code, will shorten the next interval.
//     If two intervals are missed, the next interval
//     will be very short, since it is trying to catch up
//     with the time.
// ul_PreviousMillis += ul_Interval;

// if the LED is off, turn it on and vice-versa:
if( ledState == LOW)
ledState = HIGH;
else
ledState = LOW;

// set the LED with the ledState of the variable:
digitalWrite(ledPin, ledState);
}
}

The result of the sketch is:

```Rollover demonstration sketch.
Solving rollover with register arithmetic.

Test with unsigned 8-bit.
150 - 140 = 10
260 (=4) - 250 = 10

Test with unsigned long.
3,000,000,000 - 2,000,000,000 = 1000000000
5,000,000,000 (=705,032,704) - 4,000,000,000 = 1000000000

A led at pin 13 will blink without rollover error
```