[U-Boot] [RFC] Review of U-Boot timer API

[J. William Campbell]

On 5/22/2011 1:15 AM, Reinhard Meyer wrote:
> Dear J. William Campbell,
>
> please demonstrate for me (and others), by a practical example,
> how _any_ arithmetic (even less with just shifts and multiplies)
> can convert a free running 3.576 MHz (wild example) free running
> 32 bit counter (maybe software extended to 64 bits) into a ms
> value that will properly wrap from 2**32-1 to 0 ?
Hi All
       I accept the challenge! I will present two ways to do this, one 
using a 32 bit by 16 bit divide, and one using only multiplies.
This first method is "exact", in that there is no difference in 
performance from a "hardware" counter ticking at the 1 ms rate. This is 
accomplished by operating the 1 ms counter based on the delta time in 
the hardware time base. It is necessary to call this routine often 
enough that the hardware counter does not wrap more than once between 
calls. This is not really a problem, as this time is 1201 seconds or so. 
If the routine is not called for a long time, or at the first call, it 
will return a timer_in_ms value that will work for all subsequent calls 
that are within a hardware rollover interval. Since the timer in ms is a 
32 bit number anyway. The same rollover issue will exist if you 
"software extend" the timer to 64 bits. You must assume 1 rollover. If 
it is more than 1, the timer is wrong.


The variables in the gd are
u32 prev_timer;
u32 timer_in_ms;
u16 timer_remainder;

/* gd->timer remainder must be initialized to 0 (actually, an number 
less than 3576, but 0 is nice). Other two variables don't matter but can 
be initialized if desired  */

u32 get_raw_ms()
{
         u32 delta;
        u32  t_save;

       read(t_save);   /* atomic read of the hardware 32 bit timer 
running at 3.576 MHz */
       delta_t = (t_save  - gd->prev_timer) ;

       gd->prev_timer =  t_save;
      /*
        Hopefully, the following two lines only results in one hardware 
divide when optimized. If your CPU has no hardware divide, or if it 
slow, see second method .
     */
      gd->timer_in_ms += delta_t  / 3576; /* convert elapsed time to ms */
      gd->timer_remainder += delta_t  % 3576; /* add in remaining part 
not included above */
      if (gd->timer_remainder >= 3576) /* a carry has been detected */
     {
        ++gd->timer_in_ms;
        gd->timer_remainder -= 3576; /* fix remainder for the carry above */
     }

      return(gd->timer_in_ms)
}

This approach works well when the number of ticks per ms is an exact 
number representable as a small integer, as it is in this case. It is 
exact with a clock rate of 600 MHz, but is not exact for a clock rate of 
666 MHz. 666667 is not an exact estimate of ticks per ms, It is off by 
0.00005 % That should be acceptable for use as a timeout delay. The 
accumulated error in a 10 second delay should be less than 0.5 ms.

There is a way that the divide above can be approximated by multiplying 
by an appropriate fraction, taking the resulting delta t in ms, 
multiplying it by 3576, and subtracting the product from the original 
delta to get the remainder.  This is the way to go if your CPU divides 
slowly or not at all. This approach is presented below.

the vaues in gd are as follows:

u32 prev_timer;
u32 timer_in_ms;

/*
     One tick of the 3.576 MHz timer corresponds to 1/3.576/1000 ms,
     or 0.000279642 ms. Scale the fraction by 65536 (16 bit shift),
     you get 37532.9217
*/
u32 get_raw_ms(void)
{
   u32  t_save;
   u32  temp;

   /* read the hardware 32 bit timer running at 3.576 MHz */
   read_timer_atomic(t_save);
   t_save         -= gd->prev_timer; /* get "delta time" since last call */
   gd->prev_timer += t_save; /* assume we will use all of the counts */

   /*
    * This first while loop is entered for any delta time > about 18.3 
ms. The
    * while loop will execute twice 2.734% of the time, otherwise once.
    */
   while (t_save > 65535)
   {
     temp = t_save >> 16;   /* extract msb */
     temp  = ((temp * 37532) + ((temp * 60404) >> 16)) >> 11;
     /* temp  = (temp * 37532) >> 11; */
     gd->timer_in_ms += temp;
     t_save          -= temp * 3576;
   }
   /*
    * This second while loop is entered for 94.837% of all possible 
delta times,
    * 0 through 0XFFFFFFFF. The second while loop will execute twice 
0.037% of
    * the time, otherwise once.
    */
   while (t_save >= 3576)
   {
     temp  = (t_save * 37532) >> (16 + 11);
     if (temp == 0)
       temp = 1;     /* we know that 1 works for sure */
     gd->timer_in_ms += temp;
     t_save          -= temp * 3576;
   }
   gd->prev_timer -= t_save; /* restore any counts we didn't use this 
time */
   return gd->timer_in_ms;
}

I have tested this code and it seems to work fine for me. I have 
attached a more readable copy as "example .c" for those who wish to play 
around with it. In my original post, I had a version of this code that 
could be used with different clock rates. I can provide the same 
functionality with this code, for CPUs/systems where the clock rate is 
unknown at compile time or is variable. I can also address the error 
encountered by non-integer ticks per millisecond, if people really think 
the error is enough to matter, but I won't post it unless people want to 
see it.

Best Regards,
Bill Campbell




>
> I fail to see how that will be possible...
>
> Best Regards,
> Reinhard
>
>

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: example.c
Url: http://lists.denx.de/pipermail/u-boot/attachments/20110522/8aee390d/attachment.txt