Favorite Tools - Look Up Tables

Matthew EshlemanOctober 22, 20162 comments

As we grow in our engineering careers, we must continually add new tools to our collective tool kits. One favorite tool in my toolkit will be obvious to many experienced embedded software engineers. I still remember learning this approach early in my career via code written by colleague David Starling. The tool in question: 

Look up tables 

Look up tables simplify code and improve firmware maintenance. What is a look up table? A look up table is often nothing more complex than a constant statically defined array of information. It could be a dynamic std::map data structure created during program initialization or other container as appropriate. The table elements often consist of data structures defining behavior, translating between types, or providing access to additional metadata. Let’s dive into an example.

A device consists of a keypad with buttons that must initiate actions in the firmware. Perhaps the product specification requires some keys to behave with a discrete one time action while other keys must exhibit a repeating behavior. Among the repeating keys some should repeat at different rates. Using a look up table, example code implementing these requirements might appear as:

This article is available in PDF format for easy printing
//abstracted key enum in public header
//for application/main loop consumption
enum class Key {
    KEY_VOLUME_UP,
    KEY_VOLUME_DOWN,
    KEY_SELECT,
    KEY_UP,
    KEY_DOWN,
    NUMBER_OF_KEYS
};

//////////////////////////////////////
//  Private, internal to module
typedef struct KeyBehavior
{
    Key          abstracted_key;
    uint16_t     repeat_rate_ms;
    const char * debug_key_name;
} KeyBehaviorT;

//Internal key behavior look up table
static constexpr KeyBehaviorT m_KeyBehaviors[] = {
    { Key::KEY_VOLUME_UP,   100, "VolumeUp"   },
    { Key::KEY_VOLUME_DOWN, 100, "VolumeDown" },
    { Key::KEY_SELECT,      0,   "SelectKey"  },
    { Key::KEY_UP,          250, "UpKey"      },
    { Key::KEY_DOWN,        250, "DownKey"    },
};
static constexpr uint16_t NUM_OF_KEY_VALUES = sizeof(m_KeyBehaviors)/sizeof(m_KeyBehaviors[0]);
static_assert(NUM_OF_KEY_VALUES == (int)Key::NUMBER_OF_KEYS, "look up table is missing a key!");

static constexpr uint16_t KEY_RELEASED_VALUE = 0xFFFF;
static uint16_t m_LastKey = KEY_RELEASED_VALUE;
static uint32_t m_LastSentTimeStamp_ms = 0;

void KeyHandler::ProcessDebouncedRawKey(uint16_t key)
{
    //for this example, 'key' is predefined to be a simple 0 based index
    //into our lookup table. 0xFFFF represents key released. 
    //'key' is already de-bounced.

    if((key != KEY_RELEASED_VALUE) && (key >= NUM_OF_KEY_VALUES))
    {
        DebugOutput("unknown key value received: %d\n", key);
        return;
    }

    bool sendThisKey = false;
    if((key != m_LastKey) && (key != KEY_RELEASED_VALUE))
    {
        //new key, send it.
        sendThisKey = true;
    }
    else if(key != KEY_RELEASED_VALUE)
    {
        //ongoing key press
        if(m_KeyBehaviors[key].repeat_rate_ms != 0)
        {
            uint32_t delta_ms = GetMilliSecondTimeStamp() - m_LastSentTimeStamp_ms;
            if(delta_ms >= m_KeyBehaviors[key].repeat_rate_ms)
            {
                sendThisKey = true;
            }
        }
    }

    if(sendThisKey)
    {
        m_LastSentTimeStamp_ms = GetMilliSecondTimeStamp();
        SendKey(m_KeyBehaviors[key].abstracted_key);
        DebugOutput("Sent key : %s at %d ms\n", m_KeyBehaviors[key].debug_key_name, m_LastSentTimeStamp_ms);
    }

    m_LastKey = key;
}

Key points to notice in the above example:

  • Business logic is now trivial to modify. Maybe the product decides that volume up and volume down should repeat at different rates. Just change the values in the table.
  • A new key is added to the hardware? Add a new row to the table.
  • The table provides a nice location for metadata, such as debug friendly strings for each key.

There are many other ways to use look up tables in our embedded software. If code consists of a long series of if()/else if() blocks or an extensive switch() statement, a look up table might be appropriate. Other examples include:

  • Mapping enumerated types to metadata. Examples:
    • Debug strings
    • Hardware register addresses or offsets
  • Extracting business logic/parameters into a single easy to read table/location
  • Simple state machines
    • e.g. Map a state enumerated value to various callback function handlers for the state.
  • Internationalization of user interface strings

Look up tables are a handy tool to add to our collective toolkit, simplifying code and improving maintenance. Where have you found a look up table useful in your embedded software?


Next post by Matthew Eshleman:
   Surprising Linux Real Time Scheduler Behavior


Comments:

[ - ]
Comment by nventuroOctober 24, 2016

Note that your KeyBehaviour type has the key stored inside the struct (abstracted_key), and is unnecessary (since you obviously already know the key value). Plus, for your table to work, the order in which the keys are declared in the enum and in the table MUST be the same. Starting from C90, you can specify the array indexes to achieve a less error-prone solution:

static const KeyBehaviorT m_KeyBehaviors[] = {
    [KEY_VOLUME_UP] = { 100, "VolumeUp"   },
    [KEY_VOLUME_UP] = { 100, "VolumeDown" }
};

Admittedly, I don't think C++ supports this feature, so I'm not sure what would be the best way to get this behaviour in a constexpr array.

[ - ]
Comment by MatthewEshlemanOctober 24, 2016

I love how we learn something new every day. I was not aware of that addition to C90. Slick, I like it, good to know! I also tried it in my sample code (C++11, clang) and it compiled fine and passed my tests too, even when I move the order around in the declaration. Nice.

I was purposefully abstracting the actual key value received via the "hardware" (details not shown) and translating to the "application level" Key enum, which could then be any value. Yes, in this example they are one in the same, I should have made them different to further show this use of the table!

Thank you for the feedback and C90 tidbit! Much appreciated!

To post reply to a comment, click on the 'reply' button attached to each comment. To post a new comment (not a reply to a comment) check out the 'Write a Comment' tab at the top of the comments.

Registering will allow you to participate to the forums on ALL the related sites and give you access to all pdf downloads.

Sign up
or Sign in