embedded software boot camp

A tutorial on lookup tables in C

Monday, January 11th, 2010 by Nigel Jones

A while back I wrote a blog posting on using lookup tables as a means of writing efficient C. Since then, every day someone looking for basic information on lookup tables ends up on this blog – and I suspect goes away empty handed. To help make their visits a bit more fruitful I thought I’d offer some basic information on how best to implement look up tables in C. Given that this blog is about embedded systems design, my answers are of course embedded systems centric.

So what is a lookup table? Well a lookup table is simply an initialized array that contains precalculated information. They are typically used to avoid performing complex (and hence time consuming) calculations. For example, it is well known that the speed of CRC calculations may be significantly increased by use of a lookup table. A suitable lookup table for computing the CRC used in SMBUS calculations is shown below. (Note that the SMBUS consortium refers to their CRC as a PEC)

uint8_t pec_Update(uint8_t pec)
static const __flash uint8_t lookup[256] =
0x00U, 0x07U, 0x0EU, 0x09U, 0x1CU, 0x1BU, 0x12U, 0x15U,
0x38U, 0x3FU, 0x36U, 0x31U, 0x24U, 0x23U, 0x2AU, 0x2DU,
0x70U, 0x77U, 0x7EU, 0x79U, 0x6CU, 0x6BU, 0x62U, 0x65U,
0x48U, 0x4FU, 0x46U, 0x41U, 0x54U, 0x53U, 0x5AU, 0x5DU,
0xE0U, 0xE7U, 0xEEU, 0xE9U, 0xFCU, 0xFBU, 0xF2U, 0xF5U,
0xD8U, 0xDFU, 0xD6U, 0xD1U, 0xC4U, 0xC3U, 0xCAU, 0xCDU,
0x90U, 0x97U, 0x9EU, 0x99U, 0x8CU, 0x8BU, 0x82U, 0x85U,
0xA8U, 0xAFU, 0xA6U, 0xA1U, 0xB4U, 0xB3U, 0xBAU, 0xBDU,
0xC7U, 0xC0U, 0xC9U, 0xCEU, 0xDBU, 0xDCU, 0xD5U, 0xD2U,
0xFFU, 0xF8U, 0xF1U, 0xF6U, 0xE3U, 0xE4U, 0xEDU, 0xEAU,
0xB7U, 0xB0U, 0xB9U, 0xBEU, 0xABU, 0xACU, 0xA5U, 0xA2U,
0x8FU, 0x88U, 0x81U, 0x86U, 0x93U, 0x94U, 0x9DU, 0x9AU,
0x27U, 0x20U, 0x29U, 0x2EU, 0x3BU, 0x3CU, 0x35U, 0x32U,
0x1FU, 0x18U, 0x11U, 0x16U, 0x03U, 0x04U, 0x0DU, 0x0AU,
0x57U, 0x50U, 0x59U, 0x5EU, 0x4BU, 0x4CU, 0x45U, 0x42U,
0x6FU, 0x68U, 0x61U, 0x66U, 0x73U, 0x74U, 0x7DU, 0x7AU,
0x89U, 0x8EU, 0x87U, 0x80U, 0x95U, 0x92U, 0x9BU, 0x9CU,
0xB1U, 0xB6U, 0xBFU, 0xB8U, 0xADU, 0xAAU, 0xA3U, 0xA4U,
0xF9U, 0xFEU, 0xF7U, 0xF0U, 0xE5U, 0xE2U, 0xEBU, 0xECU,
0xC1U, 0xC6U, 0xCFU, 0xC8U, 0xDDU, 0xDAU, 0xD3U, 0xD4U,
0x69U, 0x6EU, 0x67U, 0x60U, 0x75U, 0x72U, 0x7BU, 0x7CU,
0x51U, 0x56U, 0x5FU, 0x58U, 0x4DU, 0x4AU, 0x43U, 0x44U,
0x19U, 0x1EU, 0x17U, 0x10U, 0x05U, 0x02U, 0x0BU, 0x0CU,
0x21U, 0x26U, 0x2FU, 0x28U, 0x3DU, 0x3AU, 0x33U, 0x34U,
0x4EU, 0x49U, 0x40U, 0x47U, 0x52U, 0x55U, 0x5CU, 0x5BU,
0x76U, 0x71U, 0x78U, 0x7FU, 0x6AU, 0x6DU, 0x64U, 0x63U,
0x3EU, 0x39U, 0x30U, 0x37U, 0x22U, 0x25U, 0x2CU, 0x2BU,
0x06U, 0x01U, 0x08U, 0x0FU, 0x1AU, 0x1DU, 0x14U, 0x13U,
0xAEU, 0xA9U, 0xA0U, 0xA7U, 0xB2U, 0xB5U, 0xBCU, 0xBBU,
0x96U, 0x91U, 0x98U, 0x9FU, 0x8AU, 0x8DU, 0x84U, 0x83U,
0xDEU, 0xD9U, 0xD0U, 0xD7U, 0xC2U, 0xC5U, 0xCCU, 0xCBU,
0xE6U, 0xE1U, 0xE8U, 0xEFU, 0xFAU, 0xFDU, 0xF4U, 0xF3U
pec = lookup[pec];
return pec;

There are several things to note about this declaration.

The use of static
If static was omitted, then this table would be allocated and initialized on the stack every time the function is called. This is very slow (and hence self defeating) and will most likely lead to a stack overflow on smaller systems. As a result, a lookup table that is not declared static is almost certainly a mistake. The only exception that I am aware of to this rule is when the lookup table must be used by multiple modules- and hence must be declared so as to have global scope.

The use of const
By definition a lookup table is used to read data. As a result, writing to a lookup table is almost always a mistake. (There are exceptions, but you really need to know what you are doing if you are dynamically altering lookup tables). Thus to help catch unintended writes to a lookup table, one should always declare the array as const.

Note that sometimes this is superfluous if the array is forced into Flash, as described below.

The use of __flash
If one provides no memory modifier (such as __flash) then many embedded systems compilers will copy the array into RAM (even though it is declared as const). Given that RAM is normally a much more precious resource than Flash, then this is a very bad thing. As a result, one should give a memory specifier such as __flash to force the array to be kept in Flash. Note that the syntax for doing so varies by compiler vendor. __flash is an IAR extension. I’ve also seen CODE (Keil) and ROM (Microchip) among others.

The use of a size specific data type such as uint8_t
Almost by definition lookup tables can consume a lot of space. As a result it is very important that you be aware of exactly how much space is being consumed. The best way to do this is to use the C99 data types so that you know for sure what the underlying storage unit is. As a result, if your data type is ‘int’ then I’d suggest that you are doing yourself a disservice.

Avoidance of incomplete array declarations
You should also note I have explicitly declared the array size as 256. I could of course have omitted this and had the declaration read as static const __flash uint8_t lookup[] = { …};
However, I strongly recommend that you do not do this with lookup tables, as this is your first line of defense against inadvertently declaring the table with the wrong number of initializers.

Range Checking
In this case, range checking of the array indexer is unnecessary as it is an 8-bit entity and the table is 256 bytes. Thus by definition it is not possible to index beyond the end of the array. However, in general one should always range check the indexer before performing the lookup. If you make your index variable unsigned then you can make the check one-sided which aids in keeping the computation speed high. For example:

#define TABLE_SIZE (27u)
uint8_t lookup(uint8_t index)
uint16_t value;
static const __flash uint16_t lookup[TABLE_SIZE] =
946u, 2786u, … 89u
if (index < TABLE_SIZE)
value = lookup[index];
//Handle error


So where do I use lookup tables? I’ve already mentioned CRC calculations as a common application. Probably my most common usage is for implementing jump tables. I wrote an extremely detailed article about this which I recommend you read if this is your interest. The third area where I often implement lookup tables is when I need to know the value of some complex function, where the independent variable has a limited set of values. To put this into plain English. If I have a typical 8 or 10 bit analog – digital – converter (ADC) and I need to compute say 6.5 * ln(X) where X is the ADC reading, then I’ll often just declare a lookup table that contains the values of 6.5 * ln(X) for all possible X (0 – 255 in the case of an 8 bit ADC). In this case all I need do is index the lookup table with the value of the ADC and I have my result. (The really observant reader will have noticed that 0 is an invalid input to the ln() function and so my previous statement is not entirely correct. Although this can be handled in several ways including range checking or the use of NaN (Not a Number),  I mention it so as to point out that lookup tables do not absolve you of taking care of corner conditions).

Once you get the hang of using lookup tables, particularly if you embrace the idea of very large lookup tables, then you’ll quickly begin to wonder how you ever got along without them.

I’m sure that visitors to this blog would also appreciate hearing about other real world examples of the use of lookup tables – so feel free to tell the world about your experiences in the comments section.


Tags: ,

50 Responses to “A tutorial on lookup tables in C”

  1. steve says:

    Lookup tables can be used for storing bitmaps, for use on embedded systems which have, say, LCD displays.Evidentally, this particular usage is unfamiliar to some non-embedded programmers, as shown by its inclusion here: http://thedailywtf.com/Articles/The-cbitmap.aspx

  2. Nigel Jones says:

    Good suggestion Steve.

  3. Anonymous says:

    NigelWhy would you declare the lookup table in flash when the reason for using a look up table approach is speed? Flash access times are generally higher than RAM. I guess the size of the lookupt table would be factor though

    • Neri says:

      The size will not be a factor in here, because in almost all the cases the compiler will use offsets to address the table. This is, take the address of the first element and then just add the offset to reach any of the elements you want, making this access quite faster. An example:

      pec = lookup[counter];

      lea _lookup,a0
      move.b (a0,d1.l),d0
      move.b d0,_pec

      This is code generated for a ColdFire v2 as you can see, to take the data from the lookup table just took one instruction, which is the second one.

      Carlos Neri

  4. Nigel Jones says:

    I'm showing my low end processor bias! On most of the systems I work on, the clock speed is low enough that the access time of Flash & RAM are the same. If you are working on a high performance system with lots of RAM, then I agree you shouldn't force the table into Flash.

  5. Nigel, you failed to mention applications for a look-up table in RAM when speed and performance are important in a real-time embedded system.
    Given that the access time of RAM is normally much faster than Flash, if the memory budget exists for the (256 bytes of) RAM, then using fast RAM to hold the table is a very good thing.

  6. Steven says:

    Hi Nigel

    I came across this article while trying to find a way to implement a small database. Could one use this or is there a better way of implementing a database.

    • Nigel Jones says:

      It depends what you mean by a database. If you are looking for a relational database then you will need a lot more than is presented here. However, if you are looking for a simple flat database then a look up table is a great foundation. You can add significant functionality by incorporating pointers into the table. You can add a huge amount of functionality by adding pointers to functions into the table. If pointers to functions scare you, then read this article.

      • Steven says:

        Thanks Nigel

        I’m only interested in a flat file structure. Also thanks for pointing out that one could use pointers to functions in the table.

        • bandit says:

          While I use pointers to functions when appropriate, there are cases when this is not permitted for safety reasons. The easy solution is to have a function number in the table, and use that number in a switch statement. (Of course, use an enum or define such as FCN_NUM_FOO.)

          Another general method for lookup tables is to create a file, ie cli_cmd.tbl, with macros for each CLI command:

          CLI_CMD( CLI_ARDU_STOP, “stop”, “stop the robot” )
          CLI_CMD( CLI_ARDU_FWD, “fwd”, “move the robot fwd” )
          CLI_CMD( CLI_ARDU_BACK, “back”, “move the robot back” )

          this gets included several times into a .h or .c file, each time creating a table or a string with a name from the first arg

          CLI_ARDU_STOP_cmd[] = “stop”;
          CLI_ARDU_STOP_help[] = “stop the robot”;

          The first arg goes into an enum

          #undef CLI_CMD
          #define CLI_CMD( a,b,c ) a, /* the enum string */

          typedef enum
          CLI_FIRST_CMD_ENUM = CLI_CMD_START, // placeholder

          #include “cli_cmd.tbl” // the first table entry is the command enum value

          CLI_LAST_CMD // size of the table (for free)

          } CLI_CMD_ENUM;

          Note you need to do the #undef because the macro is re-defined several times in a row, and the compiler will complain if you don’t do the #undef.

          The final is a lookup table with all of the pieces. You can search thru the table for the command, and use the enum in a switch() statement to actually execute the command. Help is dumping the table with the command and help strings.

          This may be expanded to include constants, number and types of args, etc.

          This is only one example of generating a lookup table on-the-fly. Most IDE’s and clever use of Makefiles allow you to generate a lookup table for most anything as part of the build sequence.

          • Akshay Immanuel D says:

            Hey exactly.
            While working on a SIL4 project i was asked not to implement state machines using function pointers by the V&V team.
            You said “While I use pointers to functions when appropriate, there are cases when this is not permitted for safety reasons. The easy solution is to have a function number in the table, and use that number in a switch statement. (Of course, use an enum or define such as FCN_NUM_FOO.)”.
            This method seems possible to implement a state machine without function pointers.
            Can you elaborate on this method a bit more please.


  7. Sherwin says:


    I am trying to implement a LUT so I can go from milliVolts to dBm. I was wondering if you could better explain what you mean by “Indexing the LUT” such that once a data piece is entered then a dBm result could be extracted from the table.

    • Nigel Jones says:

      I assume that the mV value is an integer and has some known bound. For example 0 – 1023 mV is the possible range. You then declare a lookup table that has 1024 entries with the nth entry corresponding to the dBm value for a mV reading of n. Then at run time your dBm value is simply given by dBm = lut[mV]; If this still isn’t clear then feel free to give me a ring at +1 301 551 5138.

      • Sherwin says:

        Hi Nigel,

        Thanks for your response, I understand what you’re saying and I have already begun to apply it. i have another question, lets say that I construct a LUT with 1024 members with each member representing a dBm value corresponding to a input of mV. What if I decided to decrease my indexed LUT range yet keeping my mV the same, can I make jumps within the LUT. What I’m trying to say is that instead of having a one to one correspondence between the members of the LUT and the input mV, can I have it such that each input mV corresponds to every other nth member of LUT.

        so…..: mV1 to LUT Member 1
        mV2 to LUT Member 3
        mV3 to LUT Member 5 and so on.



        • Nigel Jones says:

          Sure. You can index the LUT anyway you like. In fact I regularly index my LUTs in interesting ways. In the example you cited, I would just declare a variable ‘index’ and then make index the requisite function of the mV input. Then I would use index to access the LUT. Example. index = mv * 2; return LUT[index];
          Or am I missing something?
          BTW a common thing to do is to use a LUT together with interpolation. Say for example that a 1024 LUT consumes too much space. You could take say every 4th value and create a 256 entry LUT. Then to get to the values that you have discarded you perform interpolation between points in the table. Of course the interpolation is much slower than a simple table look-up. Incidentally while linear interpolation is by far the simplest form of interpolation, there are are other higher order forms of interpolation that can give better results in some circumstances.

  8. Frances says:

    Is it advisable/efficient to use a look up table with a char array as an argument? In all your examples, the arg is an int. Our project involves a scripting language with ~200 commands. My task is to simply take the encrypted file, extract the commands, and execute the relevant function. I thought a look up table would be a nice implementation of this rather than a long if/else chain. Any advice?
    Note: I must keep the program as small and efficient as possible as it will be running on a small hardware controller.


    • Nigel Jones says:

      Actually Frances, my first example is an array of uint8_t (which is effectively an unsigned char on most systems). Thus, is it advisable to use a char array – yes. Is it efficient? On all 8 & 16 bit processors I have worked on, a char array is very efficient. On 32 bit processors, it may not be depending upon the architecture.

      I am not a big fan of long if-else chains. I am a huge fan of arrays of pointers to functions (in other words a lookup table of function pointers). You will find this article I wrote very useful: http://www.rmbconsulting.us/Publications/jump-Tables.pdf

      • Frances says:

        Thank you. I’m very new to C/C++ programming, and I’ve had difficulty finding a truly professional opinion regarding efficiency and performance (Most people saying that lookup tables with function pointers are too awkward/difficult to use for a beginner.)
        In fact, in my quest to actually properly define and initialize a lookup table, I have learned many of the fundamental C/C++ concepts.
        Good to know that I haven’t been wasting my time.
        Great article too, exactly what I need.

        • bandit says:

          Just remember the 80/20 rule: 20 % of the code does 80 % of the work.

          A very common mistake is optimize. This sounds oxymoronic, but most of the time most code does not need to be optimized. Instead, concentrate on the algorithm – that is the best first means of optimizing.

          In this case, the use of a lookup table is an algorithm choice, and appropriate.

          Second – get the code to work *correctly*. Optimized bad code is still bad code.

          Last, *measure* before you optimize. If you do not measure, you are almost certain to “optimize” the wrong thing. Remember the 80/20 rule. Measure as you optimize, and look at the generated code.

          I do embedded real-time critical systems. In the last 20 years (been in the biz for 35), I have had to optimize 3 times, and each time I knew where I was needing to optimize before I wrote any code, because I designed the system. I measured after I got the code correct, to verify my design, and that I knew where the optimization needed to be.

          Of the three times, two were wiggling bits fast enough to stroke hardware many times in a very short time, and the last was a PID loop in a time-critical portion. The PID code optimization was mainly measuring how long each chunk took, and shuffling the code to not recalculate invariant values.

          C can be a hard language to learn all of the subtle aspects, but a critical part is to put the tricky part in the algorithm, and keep the code very simple. The example does a good job of explaining many of the possible issues embedded systems also add: flash, const, etc. The syntax is system-dependent, but the concepts are important.

  9. Frances says:

    Is it possible to declare a lookup table in a header file? Concerning performance and efficiency, where is the best place to declare one?

    • Nigel Jones says:

      You can declare a lookup table in a header file. However I suspect you meant to ask whether one should define a lookup table in a header file. (A definition reserves storage, a declaration is essentially informational). The short answer is that defining a lookup table in a header file is a bad idea. The best combination of security and speed is to define the lookup table in a regular C file and to access it via a function in the same file. That’s essentially what is done in the example.

      • Frances says:

        I see what you mean. I have an application which will very frequently require access to the lookup table, so I’d like to do the declaration and definition once. Do you have any recommendations as to how to achieve this? (Currently, I’m defining it in the same function that searches it, so it gets created and filled every time, leading to performance deterioration.)

        • Nigel Jones says:

          Go back and read the blog post. Define the LUT to be static and const and you should get what you need.

          • Frances says:

            Thank you. One last question; is it possible to create a lookup table of function pointers when those functions pointed to take variable numbers/types of arguments?

          • Nigel Jones says:

            In C, an array of ‘anything’ has to be of the same type. Thus you can’t have an array consisting of floats and ints for example. You can of course define a structure and have an array of structures – but still each array element has the same type. When it comes to pointers to functions, there is a difference between a function whose prototype is void fn(int) and another whose prototype is void fn(float). As a result arrays of pointers to functions are normally homogeneous. You can potentially get around this in a couple of ways:
            1. Define your functions as taking a pointer to void – and then casting within the function to get the appropriate type.
            2. You can use variable length argument lists.

            Personally I have never done either of the above and so there are no guarantees that it works!

  10. John says:

    The link to your previous article (“lookup tables” ; “very large lookup tables”) is dead. Does it still exist? Would like to read it. Thanks.

  11. Trevor Ruth says:

    Very useful. Thanks.


  12. Sherwin says:

    Hi Nigel,

    I have a LUT memory allocation question. I am building an RF power meter and I am using several LUT’s and an interpolation equation to detrmin watts and dB’s. As I enter the LUT’s and compile them, I get the fallowing error

    Error – section ‘.idata_87j90demo.o’ can not fit the section. Section ‘.idata_87j90demo.o’ length=0x00000134

    What I interpret this to mean is that the compiler is trying to fit all my uninitialized data into a single 256byte bank and so it sees an overflow and thus the error. Now I put static const in front of all my LUT’s because I think that way I can save RAM memory, but I still get the same error. Why is it doing this? Why is it still putting arrays into RAM even after I declare the LUT as static const? How can i enter my LUT’s into memory without this crazy linker problem?

    • Nigel Jones says:

      For some compilers, ‘static const’ is sufficient to have the LUT put (and kept) in Flash. For other compilers it is necessary to add a memory space qualifier. For example on the IAR AVR compiler it is necessary to use the keyword __flash. Thus one ends up with __flash static const uint16_t lut[] = {….}

  13. Louis says:

    Hi Nigel,

    I have a question that is not related to lookup table, I will like to ask you if you know how can i up my ADC sampling rate from 10 ksps to 44.1 ksps?

  14. Anonymous says:

    Looks like your calculations are wrong? You have data that is 12 bits long yet you have a declaration that it is 8 bits long?

    0xNNN = 12 bits

    You have declared:


    It really should be:

    0xNN = 8 bits

  15. Pablo Varela says:

    Good tip!!!

    I often use lokup-tables for trigonometric calcultaions. Then , I don’t need include library on my code, and I reduce code and time to calculation (I use one lookup-table of a cuadrant 0-90 degrees with 0.5º precision). Moreover, I don’t need to use floats, because you can have 2 decimal precision with one byte type. Example:

    cos(30º)=0.866–>0.87, then you set in lookuptable, position 60 (because you have 0.5º precision, for 90 deggrees you have 180 position in lookuptable), the value 87 (factorized)

    if you need cos(150º) you know that is the same -cos(30º), the -lookuptable[60]

    Good luck

  16. Raul says:

    Hi Mr. Jones,

    Great article like always.

    I read your tutorial on function pointer arrays (http://www.rmbconsulting.us/jump-tables-via-function-pointer-arrays-in-cc), and I had a great time reading it, very educational and very clarifying about the use of type and memory qualifiers, too.

    It appears to be a typing error in the article though; in the first paragraph of Example 12 says “and return a const pointer to a volatile CHAR (i.e. the pointer may be modified,…” I think instead of “the pointer may be modified” it has to be “the pointer may NOT be modified”?

    Thank again for sharing your knowledge.

  17. hanish says:

    sir, nice article!
    but i would rather go for an enum and then use a switch case for the members in enum which leads to good performance and very less memory consumtion.
    I am from automotive industry where i recently implemented a LUT but then changed to enum strategy coz of more potency
    (in my header file inlconfig.h)
    /* enum for all can messages for interior lighting*/
    typedef enum
    //all can messages

    (and then in my c file inlmain.c)

    void updatesignal( const Inl_message_enum_t Inl_can_addr_index)
    // and so on
    }//end of function
    i found out better than LUT

  18. Leonard says:

    Thank you for this tutorial. I have to implement a lookup table to convert the thermocouple voltage in degrees, because the polynomial is 9th grade…

    • Nigel Jones says:

      An alternative to a direct lookup table for thermocouples is to use a series of piece wise linear approximations. To put it in plainer English. If you plot the ninth order polynomial you will find that it is actually reasonably linear and can be approximated by a series of straight lines. Thus your lookup table actually becomes a lookup of linear equations. I have used this technique to very quickly convert mV to degrees while simultaneously keeping the lookup table small. If this isn’t clear then perhaps I’ll put together a blog posting showing the general idea.

  19. Pashgan says:

    In the array is larger than specified. This is a mistake?

  20. Mohamed Muslim says:

    Thank you very much, superb Article,
    you seem to have excellent skills of teaching and making people understand .
    Thanks again

  21. sheen says:

    i have a data and now i have to genrate and design LUT so how how i will start doing that . please sugest me

  22. Martina says:

    Thank you very much for this article, it helped me a lot. But I still have a question: does it make sense to use Lookup tables with restrict pointers? I found an artifact in foreign code and I’m not sure if there is any speedup to expect, I’m not even sure if this would do more damage than improvement. Thank you.

  23. David Brown says:

    It is better /not/ to specify the size of a table like this, precisely because you can get better checking of the size if it is calculated automatically:

    static const __flash uint8_t lookup[] =
    0x00U, 0x07U, 0x0EU, 0x09U, 0x1CU, 0x1BU, 0x12U, 0x15U,

    static_assert(sizeof(lookup) / sizeof(lookup[0]) == 256, “Incorrect number of initialisers for lookup”);

    If you give the number of elements explicitly (static const __flash uint8_t lookup[256] = …), you cannot check the initialiser. Many compilers will give a warning if the initialiser table is too big, but it is not required by the C standards. And the standards say explicitly that if there are too few initialisers, the remaining ones will have default (0) initialisation.

    (If you are using a C11 compiler, #include or use #define static_assert _Static_assert. C++11 provides static_assert directly. For compilers without a real static_assert, it’s easy enough to make an ugly but useful macro for it.)

Leave a Reply