Analysis of the Millis() Function

I recently started an art clock project which actually needed to be run for more than just a few hours, and ran head on into a known issue with the millis() function of the Arduino library. I finally got some time to look into the issue.

Concerns
I had used the millis() function in smaller projects before, but none of them were ever meant to be run for more than a short time. I knew that there was some nine hour rollover issue when the clock overflows, but had been content to leave it at that. However, to complete my current project, I needed to confront this.

I was concerned about two things: first, the accuracy of the millisecond count, and second, how overflows were handled. Rob Faduli proposed a method for detecting and handling rollovers in the code, but I was confused about the problem- if it was a straight rollover problem, my code should have worked properly, as modular arithmetic should ignore the momentary overflow. I was concerned about two things: First, the accuracy of the millis() count, and second, the peculiar rollover behavior of the function.

Millisecond accuracy
The first issue I had was with how accurate the millisecond clock count is on the Arduino. This count is generated from Timer 0. Timer 0 is an eight bit counter that is fed by the system clock divided by 64. The issue is that the 16 clock MHz cannot be factored by a power of two to equal 1ms, so a straight clock divider cannot produce a 1ms signal. It turns out there is an elegant software workaround- the counter actually ticks slightly slower than 1ms, so every once in a while, the clock is advanced by 1ms in order to synchronize the output to actual time. With the system cock set to 16 MHz, the counter overflows every:

So, for every 1000 timer counts, real time has advanced 1.024 ms. To fix this discrepancy, 24 extra counts have to be added to the output. The code that accomplishes this is as follows (from the Arduino library):

timer0_overflow_count * 64UL * 2UL / (F_CPU / 128000UL);

Using a simulator [Appendix A] to examine the output of the first 1000 counts, this appears to be happening at overflow counts:

42, 84, 125, 167, 209, 250,
292, 334, 375, 417, 459, 500,
542, 584, 625, 667, 709, 750,
792, 834, 875, 917, 959, 1000

This is exactly 24 times, as is expected, so my fears about the timing being off were misplaced. Over the course of 1 second, then millis() count is accurate. It may be off by almost 1ms at any time, however this is probably good enough for a C program.

Rollover Events with the millis() count
The next issue was with the rollover in the function. Initially, I thought this was due to the actual millis() count overflowing, but that would occur at 2^32*1.024ms- over 50 days! On closer inspection, our culprit is the same function that converted the timer count into milliseconds:

timer0_overflow_count * 64UL * 2UL / (F_CPU / 128000UL);

To understand the issue here, the first thing to note is that the computer has a limited number of bits which can be used to do math. In this case, the computation is done in a 32-bit variable space, which is equivalent to performing the operation in a mod(2^32) space. Simply, what this mean is that if the computation goes over 4294967296 at any time, it will wrap over and lose any higher data. Looking at the function, the first thing it does is multiply the number by 128. This means that as soon as the timer counter goes over (2^32/128), the result will overflow and wrap over to zero. Computing this, we see:

(33554431*128) mod (2**32) = 4294967168
(33554432*128) mod (2**32) = 0

So the function overflows much earlier than would be expected. Converting the count to time, we see that the overflow happens at 9.54 hours, which fits what has been reported about this. The division portion of the equation can safely be ignored, because it will only ever decrease the value of the function, posing no risk of overflow.

Rollover event with timer0_overflow_count
Similar to above, there is another possibility for a glitch when timer0_overflow_count overflows as well. Fortunately, this is coincident with the previous rollover, so it can be safely ignored.

Conclusion
As it stands, the function is fine for most uses, as long as care is taken to look for the overflow events. I am mostly content to use the solution posed by Rob Faludi. However, this has the feel of a workaround, which doesn’t sit well. It would be best to push the rollover out to the bounds of the 32-bit value returned by millis(), or reduce that value to a lower bit count. This way, addition and subtraction will give meaningful results without having to worry about the overflow condition.

Test source code

// Arduino millis() simulator
// By Matt Mets (matt.mets@cibomahto.com)
//
// Written to help understand the functionality of the millis() function on
// the Arduino platform.  Many thanks to the Arduino team for developing such
// a cool system!
 
#include <iostream>
using namespace std;
 
// CPU frequency
#define F_CPU 16000000L
 
// Simulation control variables: Set these to control the interval over which
// the timer is to be run.
#define START_VALUE     0       // Starting value of timer0_overflow_count
#define COUNT           100     // Number of overflows to simulate
#define PRINT_STEP      1       // How often to print the state
 
// Functional class to model the millis() interface
class millis_sim
{
    private:
        uint32_t timer0_overflow_count;
 
    public:
        millis_sim();
        void reset_counter();
        void set_counter(uint32_t value);
        uint32_t get_counter();
        void cause_overflow();
 
        uint32_t millis();
};
 
millis_sim::millis_sim()
{
    timer0_overflow_count = 0;
}
 
void millis_sim::reset_counter()
{
    timer0_overflow_count = 0;
}
 
void millis_sim::set_counter(uint32_t value)
{
    timer0_overflow_count = value;
}
 
uint32_t millis_sim::get_counter()
{
    return timer0_overflow_count;
}
 
void millis_sim::cause_overflow()
{
    timer0_overflow_count++;
}
 
uint32_t millis_sim::millis()
{
    return timer0_overflow_count * 64 * 2 / (F_CPU / 128000);
}
 
 
int main(void)
{
    millis_sim my_millis;
 
    my_millis.set_counter(START_VALUE);
    for (unsigned long i = 0; i < COUNT; i++)
    {
        if (i%PRINT_STEP == 0) {
            cout << my_millis.get_counter() << ","
                 << my_millis.millis() << endl;
        }
        my_millis.cause_overflow();
    }
 
}
This entry was posted in tech. Bookmark the permalink.

6 Responses to Analysis of the Millis() Function

  1. Alex says:

    Is this for your wonky clock?

  2. mahto says:

    Yeah, i wanted to figure this out before I went any further with it.

  3. JP says:

    Thanks. This helps me sort out the millis() rollover math problems that I’m having.

  4. mahto says:

    Cool, glad to hear it!

  5. Alex says:

    This is based on the old millis function, before it was improved in Arduino 1.0. The new millis function does indeed rollover at 2^32 milliseconds. Reference wiring.c in the current repository.

  6. Pingback: Arduino millis() jumps by 2 every 43 milliseconds | Dr. Lawlor's Code, Robots, & Things

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>