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

[Reinhard Meyer <u-boot@emk-elektronik.de>]

Dear 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)
> }

Thank you! Basically this is similar to a Bresenham Algorithm.

>
> 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.

I would think the non exact cases result in such a small error that can be
tolerated. We are using the ms tick for timeouts, not for providing a clock
or exact delays. We should just round up when calculating the divider.

Hence the hick-ups that result when this is not called frequent enough to
prevent a multiple rollover of the raw value between calls do not matter
either (they should be just documented).

>
> 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.
>
[...]

Optimizations would be up to the implementer of such a hardware and work
only if the divider is a compile time constant. Often the divider will be
run time determined (AT91 for example).

Reinhard