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

J. William Campbell
2011-05-23T00:14:47Z

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