LUT

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.

Another fun use is in the GNU regular expression library. I'm sure there are others in there, but this is one that sticks out through the interface:

When you search a string for a regular expression, you can pass in a pointer to a "translation table", which is an array of 256 characters. If you do that, then for each character the library deals with, it'll pull the corresponding character out of the translation table and use that instead. This is nifty; it's obvious enough to do a case-blind or diacritical-blind translation table, but there are other, weirder applications. It probably takes up a bit more space than the machine code to do the same job with an algorithm, but as whizkid observes, if you'd written a function your best hope would be that the optimizer would turn it into a look-up table anyway. So you'd just be back where you started. Space for speed is a fair trade; optimizers do it all the time. That's what caching is all about, too. If you're working with embedded systems, that's a different matter of course.

Obviously, a lot of the fun and space-efficiency of this is lost with a 16-bit character set like Unicode. The table would have to be 65k instead of 1/4k.

The GNU regex library is tons of fun in any case. It's like getting a holodeck for your birthday, when all you were expecting was a giant panda and a bottle of cheap liquor.