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
_______________________________________________
U-Boot mailing list
U-Boot@lists.denx.de
http://lists.denx.de/mailman/listinfo/u-boot
