Non-linear Data Transformations


There is a simple algorithm for interpolating values in a non-linear data set. The function interpolates between adjacent values in the data set using the bits of the lower value to weight the bits in the higher value. This data transformation algorithm requires that you have a set of data points at evenly spaced intervals, scaled to intervals of 256.

In the example below, the constable array holds 6 Y values for entries between 0 and 1280 at even intervals of 256 on the X axis. The findY() function uses the most significant byte of its argument, Xvalue, to index into the constable array, and performs a linear interpolation between the adjacent constable entries which fall immediately below and above the Xvalue.

The bits of the least significant byte of Xvalue are used to weight the interpolation by successively adding fractions of the difference between two table entries.

long l;
/* Y values for X-axis values from 0 to 1279 */
long constable[] = { 1,234,566,786,1234,4455 };

long findY (long Xvalue) 
    unsigned long Yvalue, DeltaY;
    signed int lowbyte;    //signed 8-bit int
    /* Use MSB to index into the table. DeltaY is the
       difference between the adjacent table entries */
    Yvalue = constable[(short)Xvalue >> 8];
    DeltaY = constable[((short)(Xvalue >> 8))+1]-Yvalue;
    /* Use LSB of Xvalue to weight bits in DeltaY */
    lowbyte = Xvalue &0xff;
    do {
        /* Divide the delta value by 2 */
        DeltaY >>= 1;
        /* If the high bit of the Xvalue LSB is set,
           add remaining DeltaY to result */
        if (lowbyte < 0)
            Yvalue += DeltaY;
    } while (lowbyte <<= 1); /* Examine next bit */ 
void main (void) 
     l = findY(300);