1D and 2D table lookup

March 31, 2013 Coded in C

This is a lookup facility for 1-dimensional tables and 2-dimensional maps.  The routines interpolate the data linearly between data points, making it ideal for converting thermistor ADC readings to temperature or choosing control loop gains from a one- or two-dimensional gain scheduling table.

/**
 * @file
 * Table lookup with interpolation (1-D and 2-D).
 *
 * This is a 1/2-D table lookup facility.  Each routine looks up data in a table 
 * structure, interpolating as needed between data points.  The 2-D version
 * looks up along 2 axes and interpolates in two dimensions.
 *
 * <h2>Limitations</h2>
 * - The table axes (input values) must monotonically increase, or the lookup
 *   will fail.
 * - The index data type is nominally 8 bits, limiting the table length to
 *   256 elements.  Change <code>index_t</code> if larger tables are needed.
 */

#include <stdint.h>
#include <stdbool.h>
#include "lookup.h"

/** Index data type */
typedef uint8_t index_t;

/**
 * 1-D table lookup.
 *
 * This function performs a 1-D table lookup with interpolation.  The output
 * value is clamped to either of the table end values when the input value is
 * out of bounds.
 *
 * @param[in]   t      table data structure
 * @param[in]   ix     input (X-axis) value
 * @param[out]  o      output data
 *
 * @retval      true   if the lookup result is suspect due to clipping
 * @retval      false  on successful lookup
 */
bool lookup1d (Table1d *t, int ix, int *o)
{
  index_t i;
  
  /* ------------------------------------------------------------------------ */
  /* Off the end of the table */
  if (ix > t->columns[t->ncols - 1])
  {
    *o = t->table[t->ncols - 1];
    return true;
  }
  
  /* Off beginning of the table */
  else if (ix < t->columns[0])
  {
    *o = t->table[0];
    return true;
  }

  /* Within the bounds of the table */
  for (i = 0; i < t->ncols - 1; ++i)
  {
    if (   ix >= t->columns[i]
        && ix <= t->columns[i + 1])
    {
      /* Output (table) low value */
      int o_low   = t->table[i];
      /* Input (X-axis) low value */
      int i_low   = t->columns[i];
      /* Spead between the two adjacent input values */
      int i_delta = t->columns[i + 1] - t->columns[i];
      /* Spread between the two adjacent table output values */
      int o_delta = t->table[i + 1]   - t->table[i];
      
      /* Prevent division by zero.  We could get here if two consecutive
         input values in the table are the same. */
      if (o_delta == 0)
      {
        *o = o_low;
        return true;
      }
      
      *o = o_low + ((ix - i_low) * (long)o_delta) / i_delta;
      return false;
    }
  }

  /* Didn't find it (we shouldn't ever get here). */
  return true;
}

/**
 * 2-D table lookup.
 *
 * This function performs a 2-D table lookup with interpolation.  The output
 * value is clamped to either of the table end values when the input value is
 * out of bounds.
 *
 * @param[in]   t      table data structure
 * @param[in]   ix     input (X-axis) value
 * @param[in]   iy     input (Y-axis) value
 * @param[out]  o      output value
 *
 * @retval      true   if the lookup result is suspect due to clipping
 * @retval      false  on successful lookup
 */

bool lookup2d (Table2d *t, int ix, int iy, int *o)
{
  /* The lower X and Y coordinates of the interpolation box */
  index_t i, j;
  /* Set whenever one of the lookups goes off the end of the table */
  bool is_fault = false;
  
  /* ------------------------------------------------------------------------ */
  /* X axis coordinate lookup */

  /* Off the end of the table */
  if (ix > t->columns[t->ncols - 1])
  {
    /* Pretend the input value is right at the table edge so that interpolation
       works as expected */
    ix = t->columns[t->ncols - 1];
    i = t->ncols - 1;
    is_fault = true;
  }

  /* Off beginning of the table */
  else if (ix < t->columns[0])
  {
    ix = t->columns[0];
    i = 0;
    is_fault = true;
  }

  /* Within the bounds of the table */
  else
  {
    for (i = 0; i < t->ncols - 1; ++i)
    {
      if (   ix >= t->columns[i]
          && ix <= t->columns[i + 1])
      {
        break;
      }
    }
  }

  /* ------------------------------------------------------------------------ */
  /* Y axis coordinate lookup */

  /* Off the bottom of the table */
  if (iy > t->rows[t->nrows - 1])
  {
    iy = t->rows[t->nrows - 1];
    j = t->nrows - 1;
    is_fault = true;
  }

  /* Off the top of the table */
  else if (iy < t->rows[0])
  {
    iy = t->rows[0];
    j = 0;
    is_fault = true;
  }

  /* Within the bounds of the table */
  else
  {
    for (j = 0; j < t->nrows - 1; ++j)
    {
      if (   iy >= t->rows[j]
          && iy <= t->rows[j + 1])
      {
        break;
      }
    }
  }

  /* ------------------------------------------------------------------------ */
  /* 2-D interpolation */

  /* At this point we know that the input X value is between
     column[i] and column[i+1] and that the input Y value is between
     row[j] and row[j+1].  Therefore we have a rectangle in which we need
     to interpolate. 
     
     To do the interpolation, we first interpolate between column i and
     column i+1 on the upper row j.  Then, we interpolate between the same
     columns on row j+1.  Finally, we interpolate vertically between the two
     rows based on the input Y value.
     
     row0 is the upper row data and row1 is the lower (higher subscript) row
     data. */
  {
    const int *row0 = &t->table[j * t->ncols];
    const int *row1 = &row0[t->ncols];
    /* Difference between the two adjacent column values */
    int i_delta = t->columns[i + 1] - t->columns[i];
    /* Difference between the two adjacent row values */
    int j_delta = t->rows[j + 1] - t->rows[j];
    /* Low column value */
    int i_low = t->columns[i];
    /* Low row value */
    int j_low = t->rows[j];
    /* Interpolation results for the upper and lower rows */
    int o0, o1;
    
    /* Prevent division by zero if the input values aren't increasing.
       If no division by zero, interpolate between columns in the upper and
       lower row. */
    if (i_delta == 0)
    {
      o0 = row0[i];
      o1 = row1[i];
      is_fault = true;
    }
    else
    {    
      /* Interpolate the upper row */
      {
        int o_low   = row0[i];                 /* Row value at low column # */
        int o_delta = row0[i + 1] - row0[i];   /* Difference from next column */
  
        o0 = o_low + ((ix - i_low) * (long)o_delta) / i_delta;
      }

      /* Interpolate the lower (higher subscript) row */
      {
        int o_low   = row1[i];                 /* Row value at low column # */
        int o_delta = row1[i + 1] - row1[i];   /* Difference from next column */
  
        o1 = o_low + ((ix - i_low) * (long)o_delta) / i_delta;
      }
    }

    /* Guard against division by zero in the row axis.  If all is well,
       interpolate between the two row interpolation results from earlier. */
    if (j_delta == 0)
    {
      *o = o0;
      is_fault = true;
    }
    else
    {
      *o = o0 + ((iy - j_low) * (long)(o1 - o0)) / j_delta;
    }
  }
 
  return is_fault;
}

/* Header file */
#if !defined(_LOOKUP_H)
#define _LOOKUP_H

/**
 * @file
 * Table lookup with interpolation (1-D and 2-D) header file.
 */

#include <stdbool.h>

/** One dimensional lookup table. */
typedef const struct
{
  /** Number of elements in the table.  This must be at least 2. */
  unsigned char ncols;
  /** List of input values. */
  int *columns;
  /** Table data (output values).  The output values list must have the same
      length as the input list. */
  int *table;
} Table1d;

/** Two dimensional lookup table. */
typedef const struct
{
  /** Number of columns (X values) in the table.  Must be at least 2. */
  unsigned char ncols;
  /** Number of rows (Y values) in the table.  Must be at least 2. */
  unsigned char nrows;
  /** X-axis input values list. */
  int *columns;
  /** Y-axis input values list. */
  int *rows;
  /** Table data.  This is an array of <code>columns</code>X<code>rows</code>,
      arranged in rows.  For example, <code>table[1]</code> is the second 
      column in the first row. */
  int *table;
} Table2d;

/* Prototypes */
bool lookup1d (Table1d *t, int ix, int *o);
bool lookup2d (Table2d *t, int ix, int iy, int *o);

#endif

Comments:

There are no comments yet!


Sorry, you need javascript enabled to post any comments.