Getting a stateless time-based index out of overflowing timer

Question

I'm currently working on an Arduino project where I need to keep track of entries for a certain amount of time, in this case, 30 days. Our company will attempt to sell this product to cities and governments. Therefore it really has to just work, which makes me want to refrain from dynamically allocating memory.

The entries are really small, they (currently) consist out of a single char, but they might get bigger before the end of this project. An entry will be generated every specific interval, for now I am assuming this to be once every 5 minutes.

My idea was to allocate one array of entries, with as size the maximum amount of entries. To read or write an entry, I was thinking of grabbing the time in milliseconds since startup and dividing that by the amount of milliseconds in between every entry. Some pseudo-code: (The values in the defines do not match the described reality, I use simple values to make the example as clear as possible)

#define TOTAL_ENTRIES_TO_KEEP 5000
#define MILLISECONDS_PER_ENTRY 50

Entry[] entries = new Entry[TOTAL_ENTRIES_TO_KEEP];

Entry getCurrentEntry(){
    return entries[(millis()/MILLISECONDS_PER_ENTRY)%TOTAL_ENTRIES_TO_KEEP];
}

I've implemented this, tested it, and it works fine. My problem is brought to me by Arduino.cc: (emphasis mine)

Returns the number of milliseconds since the Arduino board began running the current program. This number will overflow (go back to zero), after approximately 50 days.

This product has to keep running for way more than 50 days in a row, it should be able to stand for a couple years with only the bare minimum on maintenance. So I'll have to deal with this overflow. If the timer would overflow at, say, exactly TOTAL_ENTRIES_TO_KEEP * MILLISECONDS_PER_ENTRY this would be no problem, as then it would overflow from entry 4999 to 0, which is what I do with %TOTAL_ENTRIES_TO_KEEP anyways. Point is, it doesn't, and messing with the internal libraries to make it do so would not seem like the best idea to me.

I do not care about a slight deviation in the interval between entries, nor in the total amount of entries to keep. This system needs to show an average of entries over a monthly period, which is already ambiguous, so whether a month to the system lasts 30, 31, 32 or 30.94836 days does not matter to the end result.

How could I protect this system against the effects of this overflow? Thanks in advance for your input.

Answer 1

If you insist on using millis() to index the array, then you either have to make the array size a factor of the max millis() value, or you have to reset the millis() value to zero when your array wraps. But these seem like bad ideas and I don't understand why you are using millis() to index the array.

Think of the array as a circular (ring) buffer. Create a variable that represents the current index value into the array. The current index gets incremented every time an entry is stored. When the array is full the index value wraps to zero. Use this index variable to index the array instead of millis(). You can still store entries at the same rate but now you've disassociated the millis() value from the array index.

Answer 2

The key to this is to extend the range of the counter that you are using to track time.

Just keep a "number of overflows" 32bit counter that you increment each time the millis() value wraps, and use your counter and the millis() value to form a 64-bit counter -- that will give you a wrap time of 50 * 2^32 (or about 200 billion) days -- probably longer than you can expect your device to keep functioning.

You can detect the overflow by keeping track of the last value of millis() you got, and if the current value is smaller, then you increment your "number of overflows" counter.

You'll have to be sure to call this routine at least once every wrap period.

Something like:

uint64_t long_term_millis() 
{
static uint32_t last_millis = 0;
static uint32_t wrap_count = 0;
uint32_t current_millis = millis();

    if (current_millis < last_millis) wrap_count++;

    last_millis = current_millis;

    return (((uint64_t)wrap_count)<<32) + current_millis;
}