There are a couple different techniques used to optimize the code for speed. One is to minimize the number of divisions. Another is to unroll the for loop. Finally, I used only static variables, because their location in RAM is fixed and therefore the reference in code is also fixed.

The linear interpolation takes on the form:

Where the time variables are repesented by unsigned 16-bit numbers and the position variables are represented by unsigned 8-bit numbers.

In order to perform the division only once, a fractional representation of is required. Considering that the end result is a 8-bit number and the maximum number handled by the C18 complier is 32-bit, we can use a 24-bit fractional representation. If we consider 0x01000000 to be equal to one, then we can use the lower bytes as fractions and discard them after the operation.

Using this, we perform the operation:

static unsigned long divisor = 0x01000000 / (unsigned long)(time_final - time_initial);

Doing the casting after the subtraction to ensure proper wrapping. Since the static keyword is used, the location of divisor in memory is fixed, which can speed up the code. The registers are fixed so their values in memory can be hard coded by the complier/linker.

Unrolling the for loop means the code

for(i = 0; i < 5; i++)
   Value[i] = Numerator[i] * divisor;

is replaced by

Value[0] = Numerator[0] * divisor;
Value[1] = Numerator[1] * divisor;
Value[2] = Numerator[2] * divisor;
Value[3] = Numerator[3] * divisor;
Value[4] = Numerator[4] * divisor;

Which is trading program size for speed. Note: you must turn off function optimization or the complier will re-roll the loop.

The final bit of ompitization is the access of the most significant byte from the 32-bit number.

We can't use

MSByte = Value / 0x01000000;

as it will call the division subroutine

If we use

MSByte = Value >> 24;

it will perform a series of shifts.

The best way is to use pointers.

MSByte = *(((unsigned char *)(&Value)) + 3);

The &Value operation will find the address of Value in memory. The C18 compiler is little-endian which means that the location of Value corresponds to the least significant byte. To provide access to the 8-bit numbers, the pointer is cast to (unsigned char *). By adding 3 to the pointer, this shifts the address up by three 8-bit spots to get the most significant byte. The * operator accesses the byte and places it into MSByte. This operation disassembles into a single MOVFF operation.

-- SalomonTrujillo - 20 Jun 2006

• interpolate.c: Source code for linear interpolatation optimization