A (rather long) story about time

How is time managed in OpenViBE, I’ve been asked this question dozens of times… Time is crucial when talking about real time applications and indeed, I tried to have the best I could on this point… I decided to represent time on 64 bits integer in 32:32 fixed point arithmetic. But what is that strange beast ?

Well the idea behind fixed point arithmetic is to multiply the fractional value we want to represent by a fixed scale. For example, with a scale of 1000, we can represent the value 1.234 with the integer 1234. Or we can represent 0.001 with the integer 1. Each variation of 1 unit in the integer represents a variation of a thousands for the corresponding value.

That’s quite easy with decimal factors… But computer science generally prefers powers of two, binaries and hexadecimals :). Choosing a scale factor which is a power of two is equivalent to reserve a number of bits of the integer for the fractional part of the value it represents. For example, let’s say we want a scale of 256 (which is 2^8), the value 1 can be represented by the integer 256 and the value 0.5 can be represented by the integer 128. Looks a bit harder at first, but if you look at it with hexadecimal values, then 256 becomes 0x100 and 128 becomes 0x80. As you can notice, the last byte (8 bits) represents the fractional part. That looks more easy to read…

Now how did I have such idea ? Back in the late 90s, I used to be a demomaker… Not an outstanding one but anyway, I learned a couple of tricks back then. At that time, the processor Floating Point Unit (FPU) was not as powerfull as what can be found on todays processors. For that reason, realtime demos usually did not use floating point operations. They had far better performances with integers. It is not the case anymore today. However, learning the concept let me know the other differences between floating point and fixed point operations, and particularly about the computation error that is included in those computations. Just to remind you how it works, the 32 bits floating point values are represented in memory with 1 sign bit, 8 exponent bits and 23 significand bits (as described in this page). Roughly speaking, it looks like scientific notation : the significand parts gives an idea of the value and the exponent part gives an idea of the scale. A good point with floating point values is that they are able to represent a very wide range of numbers thanks to the exponent part. Another good point is that the user thinks he is using real numbers (as in real numbers). Wait, good point ? Well, the bad point actually is that the user thinks he is using real numbers ! Indeed, the user usually doesn’t realize that there are numbers he won’t ever be able to represent, and that the distance between two consecutive representable numbers varies a lot. And the good point with fixed point values is of course that the distance between two consecutive representable numbers is exactly the same : 1/scale !

Now why does that help for time management ? Because when manipulating your time values, you know exactly what error will be included in the computation and you will be able to correct this or to chose your computations in a way that has no derivation. As I said at the begining, we use 32:32 representation, meaning that we reserve 32 bits for the integer part, and 32 bits for the fractional part. We are talking about seconds here, so it allows us to have more than 4,000,000,000 seconds represented (2^32 = 4,294,967,296). This is a little bit more than 136 years… This should be enough for everyone (If I could make as much money as Bill Gates did…) More seriously, this is more than what we need for a single run of OpenViBE. And the error is never more than 1/(2^32) which is less than 3E-10. The error is never more than 0.0000000003 seconds. But in order to achieve this precision you have to take care about how you do the computations. For example, don’t include floating point values in the computation if doing iterative things. The error would become bigger and bigger over time. Good practice usually supposes to save a start time (its computation can eventually be done using floating point), and a current time and to compute the difference between them in order to get the elapsed time. This will be more precise than repeatedly adding the amount of elapsed time since last computation. In this case, there would be a small error each time which would grow up and become significant.

Basic operations such as sum and difference in fixed point arithmetic is as easy as this :

// suppose a and b are 32:32 fixed point integer and
// you want to compute sum_ab, diff_ab

sum_ab = a + b; // yes !
diff_ab = a – b; // yes again !

For the multiplication and division operations, it becomes more tricky. Basically, since each value is multiplied by a scale, multiplying two values together involves to divide by the scale… Dividing the two values involves multiplying by the scale. You will have to face a deal here to have maximum precision on the first hand, and avoid overflow on the other hand. For example, the following code :

// suppose a and b are 32:32 fixed point integer and
// you want to compute mult_ab and div_ab

// right shift of 32 bits is equivalent
// to dividing by scale = 2^32
mult_ab = (a * b) >> 32;

// left shit of 32 bits is equivalent
// to multiplying by scale = 2^32
div_ab = (a << 32) / b;

is only valid if a and b are lower than 1 (which is 0x100000000 in hexa, remember ?). Indeed, multiplying 0x100000000 something equal or bigger will result in a value bigger than 0x10000000000000000 which is too big to fit the 64 bits ! For this reason, you may consider lowering the fractional part precision to avoid the overflow such as in :

// suppose a and b are 32:32 fixed point integer and
// you want to compute mult_ab and div_ab

// two right shifts of 16 bits is equivalent
// to dividing by scale = 2^32
mult_ab = ((a>>16) * (b>>16));

// two left shits of 16 bits is equivalent
// to multiplying by scale = 2^32
div_ab = ((a<<16) / b) << 16;

This last example will allow a and b to be any value lower than 65536 (which is 0x1000000000000 in hexa, remember ?)

Right, now back to OpenViBE, here are two handy functions to let you compute the time of a given signal sample index, and the sample index back from the corresponding time… This can be useful when writing a driver and sending stimulations for example :

uint64 get_time_from_sample(
    uint64 ui64SamplingRate,
    uint64 ui64SampleIndex)
{
    return (ui64SampleIndex<<32)/ui64SamplingRate; } uint64 get_sample_from_time(
    uint64 ui64SamplingRate,
    uint64 ui64Time)
{
    return ((ui64Time+1)*ui64SamplingRate-1)>>32
}

Comments are closed.