Go Down

Topic: Time Fine Correction Function (In seconds per day) (Read 3 times) previous topic - next topic

miclmr

Many projects include clocks or other time measuring functionality.
Unfortunately, after few days of running, we will reveal, that the clock is not so exact.
In most cases it deviates for few seconds per day.
But why the main timing library in wiring.c doesn't contain the Fine Correction function.

Please, if it is possible, add the time correction functionality to wiring.c
The code is below.
Just replace the SIGNAL(TIMER0_OVF_vect) function with the code below:


volatile long deviationInSecondsPerDay = 0;
volatile unsigned long stepMillisToPerformTimeCorrectionInteger = 0;
volatile unsigned int  stepMillisToPerformTimeCorrectionFract = 0;
volatile unsigned long nextMillisToPerformTimeCorrectionInteger = 0;
volatile unsigned int  nextMillisToPerformTimeCorrectionFract = 0;

// Add to Arduino.h:  void setDeviationInSecondsPerDay(long value);
void setDeviationInSecondsPerDay(long value)
{
   uint8_t oldSREG = SREG;
   cli();
   nextMillisToPerformTimeCorrectionInteger = timer0_millis;
   deviationInSecondsPerDay = constrain(value, (-21600), 21600); // +/- 6 Hours.
    if (deviationInSecondsPerDay != 0)
    {
        stepMillisToPerformTimeCorrectionInteger = ((86400000 / abs(deviationInSecondsPerDay)) / 1000);
        stepMillisToPerformTimeCorrectionFract   = ((86400000 / abs(deviationInSecondsPerDay)) % 1000);
   }
   SREG = oldSREG;
}
boolean updateNextMillisAndCorrectTime()
{
    boolean retVal = false;
    if (deviationInSecondsPerDay != 0)
    {
        nextMillisToPerformTimeCorrectionInteger += stepMillisToPerformTimeCorrectionInteger;
      nextMillisToPerformTimeCorrectionFract   += stepMillisToPerformTimeCorrectionFract;
      retVal = true;
      if (nextMillisToPerformTimeCorrectionFract >= 1000)
      {
            nextMillisToPerformTimeCorrectionFract -= 1000;
            retVal = false;
      }
    }
   return retVal;
}
void correctTimeIfNeeded()
{
    if (timer0_millis >= nextMillisToPerformTimeCorrectionInteger)
    {
      if (updateNextMillisAndCorrectTime())
      {
           timer0_millis += (deviationInSecondsPerDay > 0) ? (-1) : 1;
      }
    }
}

#if defined(__AVR_ATtiny24__) || defined(__AVR_ATtiny44__) || defined(__AVR_ATtiny84__)
SIGNAL(TIM0_OVF_vect)
#else
SIGNAL(TIMER0_OVF_vect)
#endif
{
   // copy these to local variables so they can be stored in registers
   // (volatile variables must be read from memory on every access)
   unsigned long m = timer0_millis;
   unsigned char f = timer0_fract;

   m += MILLIS_INC;
   f += FRACT_INC;
   if (f >= FRACT_MAX) {
      f -= FRACT_MAX;
      m += 1;
   }

   timer0_fract = f;
   timer0_millis = m;
   timer0_overflow_count++;
   correctTimeIfNeeded();
}



robtillaart

#1
May 19, 2012, 07:40 pm Last Edit: May 19, 2012, 11:34 pm by robtillaart Reason: 1
Sounds very usable!

Have you considered posting this as a new feature here - http://code.google.com/p/arduino/issues/list - ??


There is a point of attention, there are function calls that affect the time keeping (e.g. sei cli) , which makes the deviation of the clock in practice not predictable.
As the way a program runs (more less irq's) can affect the time more or less one should have testruns to make an educated guess.

Nevertheless this is far better than having no correction function at all.

Some remarks wrt the code:

For clearness sake I would compact the code

Code: [Select]

incorrect code removed => see post below.


Some open questions:   void setDeviationInSecondsPerDay(long seconds);  

why is the param a long? it is constrained to 21600  so an int should be enough.

better, why not making the param milliseconds as that allows (extreme) tuning possible ?  not realistic to have 1/1000 th of a second correction but 1/10 could be.


Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

miclmr

Hi!
1. The param is long for accomodation with other variables.
2. It is constrained to 21600 because 21600 sec = 6 hours. If the clock deviates for more than 6 hours per day, sand clock is preferable.
3. There is no possibility of tunning for 1/1000 sec per day. It is only integer seconds adjustment possible.

If we know that we have deviation of, lets say, 20237 seconds per day (86400 seconds).
Then we have to add one millisecond each (86400 / 20237 = 4.269) milliseconds.
But we are using integer values, so 86400 / 20237 = 4. So 0.269 will be lost.
In order to correct this issue we need 1/1000 fractional parts.

robtillaart

#3
May 19, 2012, 10:44 pm Last Edit: May 19, 2012, 11:38 pm by robtillaart Reason: 1
Quote
1. The param is long for accomodation with other variables.
2. It is constrained to 21600 because 21600 sec = 6 hours. If the clock deviates for more than 6 hours per day, sand clock is preferable.
3. There is no possibility of tunning for 1/1000 sec per day. It is only integer seconds adjustment possible.

add 1)  makes no sense, the compiler will take care of int to long conversion when needed. It are 2 unused bytes imho.

add 2) very true, even a deviation of 1 hour is "madness". If you use an int as param it would be automatically constrained to +-32767 seconds ~~9hours (also madness) and you don't need the constrain command making the footprint smaller.

add 3) I agree with the fractional part is important. But 1/10th should be possible, try to show you in another example when the deviation is relative small

Assume the deviation is 100 seconds, that could be 100.0 ..100.99
100.00 => 864.0000...
100.30 => 861.4157...
100.60 => 858.8469...
100.90 => 856.2933...
100.99 => 855.5302...

That means that the adjustment times are quite different. The root cause is that in your example of 20000 the deviation has the same number of significant digits as 86400, then one tenth or 1/100th is relative less than 0.01% of the value. However if the deviation is small (1..10 seconds) then 1/10th of a second can be as big as 10% of the deviation.
I'll dive into this to see how it affect the code..

BTW my code was also not correct at first, gonna fix it asap. (I'll be back :)
[fixed]
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

robtillaart

#4
May 19, 2012, 11:32 pm Last Edit: May 19, 2012, 11:40 pm by robtillaart Reason: 1
updated code
+ made param seconds an int as that should be enough.
+ made deviationInSecondsPerDay an int
- removed the constrain() as it now is automatically constrained by the range of the int
+ rewrote calculation of next adjustment time - contained a bug
? one possible optimization ?

Code: [Select]

volatile int deviationInSecondsPerDay = 0;
volatile uint8_t delta = 0;

volatile unsigned long stepMillisToPerformTimeCorrectionInteger = 0;
volatile unsigned int  stepMillisToPerformTimeCorrectionFract = 0;
volatile unsigned long nextMillisToPerformTimeCorrectionInteger = 0;
volatile unsigned int  nextMillisToPerformTimeCorrectionFract = 0;

// Add to Arduino.h:  void setDeviationInSecondsPerDay(int seconds);
void setDeviationInSecondsPerDay(int seconds)
{
 uint8_t oldSREG = SREG;
 cli();
 nextMillisToPerformTimeCorrectionInteger = timer0_millis;
 deviationInSecondsPerDay = seconds;                                       // max +/- 9 Hours.
 if (deviationInSecondsPerDay != 0)
 {
   // unsigned long temp = 86400000 / abs(deviationInSecondsPerDay);    // is this more efficient?
   stepMillisToPerformTimeCorrectionInteger = ((86400000 / abs(deviationInSecondsPerDay)) / 1000);
   stepMillisToPerformTimeCorrectionFract   = ((86400000 / abs(deviationInSecondsPerDay)) % 1000);
   delta = (deviationInSecondsPerDay > 0) ? (-1) : 1;
 }
 SREG = oldSREG;
}

void correctTimeIfNeeded()
{
 if (deviationInSecondsPerDay  != 0)
 {
   if (timer0_millis >= nextMillisToPerformTimeCorrectionInteger)  // time to adjust?
   {
     timer0_millis += delta;  // adjust

     // calc next adjusttime
     nextMillisToPerformTimeCorrectionInteger += stepMillisToPerformTimeCorrectionInteger;
     nextMillisToPerformTimeCorrectionFract   += stepMillisToPerformTimeCorrectionFract;
     if (nextMillisToPerformTimeCorrectionFract >= 1000)
     {
       nextMillisToPerformTimeCorrectionFract -= 1000;
       nextMillisToPerformTimeCorrectionInteger += 1;       // fractions add up to more than one mil.
     }
   }
 }
}
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

gerg

#5
May 20, 2012, 10:12 pm Last Edit: May 20, 2012, 10:14 pm by gerg Reason: 1
Wow, what awesome timing. I was just literally churning on how to go about doing this for my own project. Nice.

BTW, is there a reason why most, if not all, of the globals are not declared static? Looks like there are accessors for setting the ones users need to manipulate.

westfw

I'm not sure.
I mean, it would be nice for millis() to return counts that make accurate large-scale timing easier.
But won't this mess up short-term timing?  In short intervals between millis(), or use of delay(), we'll now have up to 1ms jitter depending on whether the interval includes a correction or not (I'm willing to assume that by the time you get 2ms of adjustment, that you might be more accurate with the new code compared to the old code.)  1ms error doesn't sound like a lot, but delay() was recently made more complicated specifically to cut down on such errors...

gerg

I had not looked at the implementation details until you posted. I've now peeked under the covers. I didn't spend a ton of time on it and its possible I didn't understand some things properly. Please correct me as needed.

It looks like it attempts to correct over a period of 24-hours. This in turn creates ms jitter over a full 24 hours.

What I would suggest is it be coded to allow for more reasonable limits (9 hours over 24??? really?). Accordingly the period of correction should be reduced to a number of hours; say, no more than two, and possibly much less. The smaller the correction, the smaller the window required to correct. This has the advantage of only creating jitter during a couple of hours per day (max). The rest of the day is jitter free.

Next, rather than correct at the ms level, which imposes ms jitter per interval, correct at the us level per ms intervals. This is far more friendly for things like delay.

The point is, try to minimize the duration and magnitude in which additional jitter is imposed on the system and therefore the user. I noticed fractional ms (assume us) is already tracked. If we break the correction further into us rather than ms, we would further reduce the magnitude of the jitter.

Many NTP implementations, when they find the clock requires large adjustments, simply refuses to adjust because the imposed jitter is far too insufferable. I recommend a like-minded approach here. Realistically, if people are losing more than roughly several minutes per day, and it affects their application, they need to specifically be taking that into account and adjust their own clock accordingly. Meaning, the hardware is insufficient for their requirements.

westfw

I don't know if larger jitter over a shorter time would be any better.  (The current implementation spreads the jitter as much as possible, adding or subtracting 1ms each 1/n interval for n seconds/day overall correction.)

My other worry is the size of the ISR.  The AVR is "not good" at 32 bit math.  And each time the ISR is touched, it gets added to instead of replaced (the fractional ms code was supposed to replace maintaining timer0_overflow_cnt.  Sigh.)

Maybe we should just add a separate "get_tod()" call that does all the corrections based on an unmodified millis(), to only be used for long-tem timing, and only if needed.  (and incidentally, compatible with adding RTC hardware.)

gerg


I don't know if larger jitter over a shorter time would be any better.  (The current implementation spreads the jitter as much as possible, adding or subtracting 1ms each 1/n interval for n seconds/day overall correction.)


It would be smaller jitter over a smaller period of time with more intervals. So rather than +-1ms over 24-hours, you get +-n us every y-ms, over one to two hours. Which means there would actually be smaller jitter, just more frequent. A subtle but important distinction. Which translates to us resolution jitter over a given ms. Much, much better for things like delay, regardless of the variant.

I would have to do some math and learn more about Arduino/AVR timing semantics to better understand exactly how it would shake out but it sounds like a stronger alternative.


My other worry is the size of the ISR.  The AVR is "not good" at 32 bit math.  And each time the ISR is touched, it gets added to instead of replaced (the fractional ms code was supposed to replace maintaining timer0_overflow_cnt.  Sigh.)

Maybe we should just add a separate "get_tod()" call that does all the corrections based on an unmodified millis(), to only be used for long-tem timing, and only if needed.  (and incidentally, compatible with adding RTC hardware.)



Compatibility with RTC hardware can be determined by measuring relative time passed versus wall clock on RTC for the same period and using that delta to set the correction factor. For RTCs which support it, you could then store the correction factor on the RTC itself, to allow for priming at start up.

robtillaart

@westfw
True words, think this code should only be considered if one really needs it.

That said, I would look into the effect of using millis as deviation to support 1/10 and 1/100th seconds correction. E.g a deviation of 4333 millis becomes possible.
Did just that and refactored the code to optimize memory usage and performance. The code became a bit simpler imho.

+ changed seconds deviation to milliseconds deviation to maximize tunability
+ rewrote the (expensive) modulo
+ shortend var names - just cosmetic
+ started fraction counter at -1000 as comparing against 0 is more efficient
+ removed deviationSeconds var completely
+ moved all code into the ISR to remove function call overhead

Optimizations still open
- abs(deviationMilliSec) ==> deviationMilliSec & 0x7FFFFFFF
  as it is only called during initialization there is less to win.
- the acces to nextMillisInt and nextMillisFrac can be optimized by
  using local variables, similar to m and f.

(code is not tested, merely posted as a concept).
Code: [Select]

volatile uint8_t delta = 0;
volatile unsigned long stepInt = 0;
volatile unsigned int  stepFract = 0;
volatile unsigned long nextMillisInt = 0;
volatile unsigned int  nextMillisFract = -1000;  // optimization trick see below

// Add to Arduino.h:  void setDeviation(long milliSeconds);
void setDeviation(long milliSeconds)
{
  uint8_t oldSREG = SREG;
  cli();
  delta = 0;
  if (milliSeconds != 0)
  {
    stepInt   = 86400000 / abs(milliSeconds);
    stepFract = 86400000 - stepInt * abs(milliSeconds);
    delta = (milliSeconds > 0) ? (-1) : 1;
  }
  nextMillisInt = timer0_millis;
  SREG = oldSREG;
}

#if defined(__AVR_ATtiny24__) || defined(__AVR_ATtiny44__) || defined(__AVR_ATtiny84__)
SIGNAL(TIM0_OVF_vect)
#else
SIGNAL(TIMER0_OVF_vect)
#endif
{
  // copy these to local variables so they can be stored in registers
  // (volatile variables must be read from memory on every access)
  unsigned long m = timer0_millis;
  unsigned char f = timer0_fract;

  m += MILLIS_INC;
  f += FRACT_INC;
  if (f >= FRACT_MAX) {
     f -= FRACT_MAX;
     m += 1;
  }
 
  if (delta != 0)   // force fast test first
  {
    if (m >= nextMillisInt)
    {
      m                += delta;           // adjust
      nextMillisInt   += stepInt;        // calc next time
      nextMillisFract += stepFract;
      if (nextMillisFract >= 0)          // compare with 0 is faster than with 1000
      {
        nextMillisFract -= 1000;
        nextMillisInt += 1;              // fractions add up to more than one millisec.
      }
    }
  }
 
  timer0_fract = f;
  timer0_millis = m;
  timer0_overflow_count++;
}
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

robtillaart

Quote
Maybe we should just add a separate "get_tod()" call that does all the corrections based on an unmodified millis(), to only be used for long-tem timing, and only if needed.  (and incidentally, compatible with adding RTC hardware.)


what would the signature of get_tod() be?   unsigned long get_tod();  representing the seconds since startup?

Maybe the Time library is a better place, then for these kind of adjustments.
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

miclmr

Here is the new code:
deviationInSecondsPerDay = constrain(value, (-21600), 21600); line is needed because otherwise the step between corrections will be less than 4.


//-----------------------------------------------------------------------------------------------------------------------------------
volatile int deviationInSecondsPerDay = 0;
volatile unsigned long stepMillisToPerformTimeCorrectionInteger = 0;
volatile unsigned int  stepMillisToPerformTimeCorrectionFract = 0;
volatile unsigned long nextMillisToPerformTimeCorrectionInteger = 0;
volatile unsigned int  nextMillisToPerformTimeCorrectionFract = 0;

// Add to Arduino.h:  void setDeviationInSecondsPerDay(int value);
void setDeviationInSecondsPerDay(int value)
{
   uint8_t oldSREG = SREG;
   cli();
   deviationInSecondsPerDay = constrain(value, (-21600), 21600); // +/- 6 Hours.
   nextMillisToPerformTimeCorrectionInteger = timer0_millis;
   nextMillisToPerformTimeCorrectionFract = 0;
   stepMillisToPerformTimeCorrectionInteger = (deviationInSecondsPerDay == 0) ? 0 : ((86400000 / abs(deviationInSecondsPerDay)) / 1000);
   stepMillisToPerformTimeCorrectionFract   = (deviationInSecondsPerDay == 0) ? 0 : ((86400000 / abs(deviationInSecondsPerDay)) % 1000);
   SREG = oldSREG;
}

#if defined(__AVR_ATtiny24__) || defined(__AVR_ATtiny44__) || defined(__AVR_ATtiny84__)
SIGNAL(TIM0_OVF_vect)
#else
SIGNAL(TIMER0_OVF_vect)
#endif
{
   // copy these to local variables so they can be stored in registers
   // (volatile variables must be read from memory on every access)
   unsigned long m = timer0_millis;
   unsigned char f = timer0_fract;
   unsigned long nm = nextMillisToPerformTimeCorrectionInteger;
   unsigned int  nf = nextMillisToPerformTimeCorrectionFract;
   char correction = (deviationInSecondsPerDay == 0) ? 0 : ((deviationInSecondsPerDay > 0) ? (-1) : 1);

   m += MILLIS_INC;
   f += FRACT_INC;
   if (f >= FRACT_MAX) {
      f -= FRACT_MAX;
      m += 1;
   }

   if (m >= nm)
   {
      nm += stepMillisToPerformTimeCorrectionInteger;
      nf += stepMillisToPerformTimeCorrectionFract;
      if (nf >= 1000)
      {
         nf -= 1000;
         nm += 1;
      }
      m += correction;
   }

   nextMillisToPerformTimeCorrectionFract = nf;
   nextMillisToPerformTimeCorrectionInteger = nm;
   timer0_fract = f;
   timer0_millis = m;
   timer0_overflow_count++;
}

robtillaart

#13
May 22, 2012, 07:25 pm Last Edit: May 22, 2012, 08:04 pm by robtillaart Reason: 1
Big improvements sice the first version!
Can you tell how much bytes it adds to the footprint?

Quote
line is needed because otherwise the step between corrections will be less than 4.

why is that a problem when it is less then 4?  
- millis() does not count in steps of 4 as micros() does -
- why not 5,10, or 42?
- Can you explain?

I think the constrain() line is not needed in practice as deviations that big are not occuring often. OK, many many interrupts that stall the clock?.
imho if the clock deviates more than 1 in 100  - 15 minutes ~ 1% of day - it is allready too much as 1% is about 1 correction every second.



The use of correction this way does not speed up the code as it is evaluated every call => slowing down.
Code: [Select]
char correction = (deviationInSecondsPerDay == 0) ? 0 : ((deviationInSecondsPerDay > 0) ? (-1) : 1);

You should calculate it in the setDeviationInSecondsPerDay() function to evaluate it only once, and make it a volatile char. The deviationInSecondsPerDay  is then not needed anymore - see my code example.

BTW please consider using [ code] [ /code] tags around your code, looks better (use the # button)
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

miclmr


Go Up