How do I convert from a 32-bit int representing time in usec to a 32-bit int representing time as a binary fraction in secs?

Question

POSIX uses struct timeval to represent time intervals.

struct timeval
{
    time_t   tv_sec;
    unsigned tv_usec;
};

GHS Integrity represents Time in the following manner,

struct Time
{
    time_t Seconds;
    unsigned Fraction;
};

For example, 0.5 sec is represented as 0x80000000 and 0.25sec is represented as 0x40000000.

What is the best way to convert from timeval to Time?

(p.s. The answer is not to link the POSIX library into Integrity and use POSIX calls.)

Answer 1

This is an unusual way to represent time.

Anyway, there are two easy ways to do it either way if you have 64-bit integers or floating points (the former are more likely on an embedded system):

/* assuming long is 64-bit and int is 32-bit
   or in general long twice the size of int: */
Fraction = (long) tv_usec * UINT_MAX / 1000000        /* usecs to fraction */
tv_usec = (long) Fraction * 1000000 / UINT_MAX        /* fraction to usecs */

/* assuming floating points are available: */
Fraction = tv_usec * ((double) UINT_MAX / 1000000)    /* usecs to fraction */
tv_usec = Fraction * ((double) 1000000 / UINT_MAX)    /* fraction to usecs */

Obviously both are only integer approximations, because most values in one scale cannot be represented as integers in the other scale. And in one direction you may be losing some precision because the Fraction form can represent much finer times - one increment of the Fraction form is less than 0.00024 microseconds. But that is only if your timer can actually measure those values which is not very likely - most timers cannot even measure at the scale of microseconds, and the value you see in tv_usec is often rounded.

If neither 64-bit integers nor floating points are available an option, you could do it iteratively with an extra variable. I was thinking if there is a simpler (and less expensive, considering that this is timing code) way to do such scaling than doing the equivalent of iterative 64-bit multiplication and division with two 32-bit integers. Of the two ideas that came to my mind, one would not do exact even scaling and may produce results that are by up to 9 bits off, and the one that compensates for that turns out not to be any cheaper. If something new comes up in my mind I will post it here, but this is an interesting challenge. Does anyone else have a good algorithm or snippet? Perhaps with the aid of a small precomputed table?

Answer 2

You might wanna read up on floating-point representation as Fraction seems to be the first bits of the significand.

Time t;
u64 s = 1000000 * t.Seconds + 
 u64(1000000 * reinterpret_cast<double>(0x3FF0000000000000|((u64)t.Fraction>>12)))
timeval tv;
tv.tv_sec = s / 1000000
tv.tv_usec = s % 1000000

This is foobar but it really works... you'll need 64-bit integers and double floating-point.

Answer 3

I've implemented @Tom Alsberg's suggestion (double variant). There are caveats (compare output for frac_t == uint32_t and frac_t == uint64_t).

#include <iomanip>  // setw()
#include <iostream>
#include <limits>

typedef unsigned frac_t;
const frac_t FRACTIONS_PER_SECOND = std::numeric_limits<frac_t>::max();

template <class Uint>
Uint fraction2usec(Uint fraction) {
  return static_cast<Uint>(fraction * 1e6 / FRACTIONS_PER_SECOND + 0.5);
}

template <class Uint>
Uint usec2fraction(Uint usec) {
  return static_cast<Uint>(usec / 1e6 * FRACTIONS_PER_SECOND + 0.5);
}

int main(void) {
  uintmax_t fractions[] = {
    0, 1, 0x10c6, 0x10c6f7a0b5edull,
    static_cast<uintmax_t>(FRACTIONS_PER_SECOND / 2. + 0.5),
    static_cast<uintmax_t>(FRACTIONS_PER_SECOND / 4. + 0.5), 
    FRACTIONS_PER_SECOND,
    FRACTIONS_PER_SECOND + 0x1ull,
  };
  const int w1 = 2*sizeof(uintmax_t) , w2 = 10;
  for (size_t i = 0; i < (sizeof(fractions) / sizeof(*fractions)); ++i)
    std::cout << std::hex << std::setw(w1) << fractions[i] << ": " 
          << std::dec << std::setw(w2) << fraction2usec(fractions[i]) 
          << ", "  << std::hex << std::setw(w1) 
          << usec2fraction(fraction2usec(fractions[i])) << "\n";
}

Output (frac_t == uint32_t):

           0:          0,                0
           1:          0,                0
        10c6:          1,             10c7
10c6f7a0b5ed: 4294967297,     10c6f7a0b5ee
    80000000:     500000,         80000000
    40000000:     250000,         40000000
    ffffffff:    1000000,         ffffffff
   100000000:    1000000,         ffffffff

Output (frac_t == uint64_t):

               0:          0,                0
               1:          0,                0
            10c6:          0,                0
    10c6f7a0b5ed:          1,     10c6f7a0b5ee
8000000000000000:     500000, 8000000000000000
4000000000000000:     250000, 4000000000000000
ffffffffffffffff:    1000000,                0
               0:          0,                0