|
Branch Tables via Function Pointer Arrays in C |
|
|
|
Page 1 of 6 Branch Tables via Function Pointer Arrays in C Examination of assembly language code that has been crafted by an expert will usually reveal extensive use of function "branch tables." Branch tables (a.k.a., jump tables) are used because they offer a unique blend of compactness and execution speed, particularly on microprocessors that support indexed addressing. When one examines typical C code, however, the branch table (i.e., an array of funtion pointers) is a much rarer beast. The purpose of this article is to examine why branch tables are not used by C programmers and to make the case for their extensive use. Real world examples of their use are included.
Function pointers
In talking to C programmers about this topic, three reasons are usually cited for not using function pointers. They are:
* They are dangerous
* A good optimizing compiler will generate a jump table from a switch statement, so let the compiler do the work
* They are too difficult to code and maintain
Are function pointers dangerous?
This school of thought comes about, because code that indexes into a table and then calls a function based on the index has the capability to end up just about anywhere. For instance, consider the following code fragment:
void (*pf[])(void) = {fna, fnb, fnc, …, fnz};
void test(const INT jump_index)
{
pf[jump_index](); /* Call the function specified by jump_index */
}
The above code declares pf[] to be an array of pointers to functions, each of which takes no arguments and returns void. The test() function simply calls the specified function via the array. As it stands, this code is dangerous for the following reasons.
* pf[] is accessible by anyone.
* In test(), there is no bounds checking, such that an erroneous jump_index would spell disaster.
A much better way to code this that avoids these problems is as follows
void test(const uint8_t jump_index)
{
static void (*pf[])(void) = {fna, fnb, fnc, …, fnz};
if (jump_index < sizeof(pf) / sizeof(*pf))
pf[jump_index](); /* Call the function specified by jump_index */
}
The changes are subtle, yet important.
* By declaring the array static within the function, no one else can access the jump table.
* Forcing jump_index to be an unsigned quantity means that we only need to perform a one sided test for our bounds checking.
* Setting jump_index to the smallest data type possible that will meet the requirements provides a little more protection (most jump tables are smaller than 256 entries).
* An explicit test is performed prior to making the call, thus ensuring that only valid function calls are made. (For performance critical applications, the if() statement could be replaced by an assert()).
This approach to the use of a jump table is just as secure as an explicit switch statement, thus the idea that jump tables are dangerous may be rejected.
Leave it to the optimizer?
It is well known that many C compilers will attempt to convert a switch statement into a jump table. Thus, rather than use a function pointer array, many programmers prefer to use a switch statement of the form:
void test(const uint8_t jump_index)
{
switch jump_index
{
case 0:
fna();
break;
case 1:
fnb();
break;
…
case 26:
fnz();
break;
default:
break;
}
}
|
C programming 