Fixed Point math to convert 100MHz counter to millisecond

Question

I am working on little endian 32bit micro-controller with no FPU. I need a way to convert a 100MHz counter to be proper milliseconds.

I want to create a function that will return me the current time in millisecond.

static uint32_t prev_time;
static uint32_t time;
uint32_t get_current_time()
{
   curr_time = get_100MHz_counter_value();
   uint32_t elapsed_time = curr_time - prev_time;

   prev_time = curr_time;   
   time = /* DONT KNOW HOW TO CONVERT THE TIME USING FIXED POINT MATH */
   return  time;
}

100MHz = 100000000 cycles per second. As immibis said, divide by 100000 for milliseconds. You don't need floating point math, integers will work just fine. — MateoConLechuga, Jan 06 '17 at 04:45
`x/100000` --> about `(x*168) >> 16` may be close enough. What is needed is the max value of `elapsed_time` and precisions needs and/or viability of `uint64_t` math. — chux - Reinstate Monica, Jan 06 '17 at 05:36
@chux - did you mean to say `>> 24` ? Anyway - I think `(x*21) >> 21` would be just as precise. — Support Ukraine, Jan 06 '17 at 05:45
@4386427 Yes `>> 24` was meant, not `>> 16`. IAC, range of `elapsed_time` is needed to be known unless one wants to venture into 64-bit math. — chux - Reinstate Monica, Jan 06 '17 at 05:55
Division by a constant is something entirely different than "a division" — harold, Jan 06 '17 at 05:59

rcgldr · Answer 1 · 2017-01-06T06:02:57.380

0

Assuming the processor can multiply two 32 bit unsigned integers resulting in a 64 bit product (there may be an intrinsic for the multiply), you can use this magic number formula to divide by 100000 (100000 == 32 * 3125).

n / 100000 =    ((n>>5)*175921861ull)>>(32+7)   // ull = unsigned long long

The sequence is multiply (n>>5) by 175921861, then take the upper 32 bits of the product and shift right 7 bits to get the quotient.

Some processors have an instruction to multiply two 32 bit numbers and produce the upper 32 bits of the 64 bit product, with an instruction name similar to umulh.

edited Jan 06 '17 at 06:02

answered Jan 06 '17 at 05:55

rcgldr

27,407
3
36
61

The initial (n>>5) seems like you're needlessly throwing precision away. Why not multiply by ((2^32)/10000)-1) and then shift down by 32? – Russ Schultz Jan 09 '17 at 17:27
@RussSchultz - The goal here is to emulate integer division n/100000, which truncates: quotient = floor(n / 100000). Since this is a truncating divide, n/100000 = n/(32*3125) = (n>>5)/3125. As another example of truncating integer division, consider 31/8 == (31>>1)/4 == ((31>>1)>>1)/2 == ((31>>1)>>1)>>1 = 3. With the truncation, it doesn't matter than 31/8 = 3.875 and ((31>>1)>>1)>>1 = 3.5, the fractional part is removed by truncation, and never results in rounding up. – rcgldr Jan 10 '17 at 00:00
@RussSchultz - Take a look at this prior thread about [magic numbers](http://stackoverflow.com/questions/41183935/why-does-gcc-use-multiplication-by-a-strange-number-in-implementing-integer-divi/41224096#41224096). For n/100000, the pre shift == 5. The pre shift is done first, so the modified divisor = 3125. The initial value of ℓ = ceil(log2(3215) = 12. The initial range for 33 bit multiplier m : (2^(32+12))/3125 <= m <= (2^(32+12) + 2^12)/3125, post shift = 12, and the multiplier is optimized to (2^(32+7)) / 3125) + 1 = 28 bit multiplier 175921861, post shift = 7 – rcgldr Jan 10 '17 at 00:02
"Some processors have an instruction to multiply two 32 bit numbers and produce the upper 32 bits of the 64 bit product, with an instruction name similar to umulh." Some do but it tends to be the higher-end ones. Many microcontroller-level cores will be lacking such an instruction. – plugwash Jan 10 '17 at 13:39
It looks like in the case of arm cortex M series (the dominant family of 32-bit microcontroller cores) the M3 has UMULL but the M0 doesn't. – plugwash Jan 10 '17 at 15:50
The M0 does have a 32 by 32 multiply but it only produces a 32 bit result. If the compiler uses it sensiblly your soloution may still turn out to be reasonablly efficient. It would be interesting to test what it comes up with for different approaches. – plugwash Jan 10 '17 at 16:10
I put your expression into godbolt for the m0 and it ended up making a library call for the multiply. https://godbolt.org/g/V07Xdj – plugwash Jan 10 '17 at 16:19
n/100000 seems to generate a call to a library divide routine. So I expect your soloution is still better than the nieve approach. – plugwash Jan 10 '17 at 23:28

Fixed Point math to convert 100MHz counter to millisecond

1 Answers1