Acronym for look-up table.

LUTs are an important part of computer programming. They are generally used for one of several purposes.

  • A configuration LUT tells the software about the system it is using. For example, the PC BIOS uses LUTs to know about the type of hard disks installed (though modern BIOSs tend to figure it out without a table), or the time zone the computer is in, etc.

  • An optimization LUT is often used to completely replace a software routine (function) to speed up processing. Often used in computer graphics, real time programming, and other types of programming where speed is of essense.

    This type of LUT is based on the observation that in digital processing it is often the case that a function will return only a specific number of results.

    Take, for example, a pixel special effect routine changing the value of the red, green, and blue channels, each of which can be in the 0 - 255 range. In many cases, the routine can be of this type:

    new_value = function(old_value);

    The processing of this function can be fairly intense. But since the new value is a function of the old value and nothing else, calling the function with the same old value will always produce the same new value. Now, considering there are only 256 possible old values, but an image can easily contain a million pixels, it is more efficient to calculate the new values only once, and create a LUT which is only 256 bytes in size. The above function can then be replaced with a simple lookup, which is much faster, and hence more efficient.

  • A pointer LUT (i.e., jump table) - often replaces a complex if-else if-else-if, etc procedure with pointers to functions (indirect addressing). Compilers often optimize a case switch into a pointer LUT.

  • A compression LUT - often used to make data smaller to save storage space or transmission time (e.g. on the Internet to save bandwidth). An example would be the way GIF files (and others) store an image: They reduce all pixels to one of up to 256 24-bit colors. They place a small LUT at the start of the file. In the LUT they list the 24-bit values, e.g., color 0 means red = 0, green = 255, blue = 127, etc. Then, in the bitmap, they just list the 8-bit values with offsets to the LUT. The software that displays the image then looks up the 24-bit values for each pixel from the LUT.