Calling functions from an array?

Go To Last Post
27 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hi,

I'm working on some interpreter residing in my Atmega8.
This interpreter receives one-byte instructions through it's RS232 interface. There are about 16 different instructions.
In stead of using a switch statement in 'C' casing all 16 instructions I would like to have an array with 16 locations, pointing to 16 different functions to be executed. So if instruction 0x03 is received then the function pointed to by location 0x03 in my array, will be called.

Is this possible and if yes how?

Henk

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

They are called function pointers, lots of info if you google for those.

So you need to start from a typedef of FuncPtr for example, and then make an array of FuncPtrs, and initialize the array with addresses of the functions. The array can reside in code flash, if you do not wish to change the functions in code, but the array can reside in sram too, so you can change the functions on the fly.

All the functions need to be of the same type, for example void a(void) and void b(void), but if you wish, they all can be for example of type uint8_t c(uint8_t x).

I know it is nice to do this with function pointers, but is there a reason to do so? It would propably be faster to just do it with switch-case or if-then-else statements.

- Jani

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thanks,
I searched the Internet and found a lot of answers.

As I'm using the Atmega8L and I encounter problems while I need all 8K of Flash memory I thought that using a pointer array would cost less Flash memory.
(I will do some experiments to find out)

On the other hand I thought that execution is faster because for example when the last 'case' is excuted all previous 'cases' must be evaluated. When using an array of pointers the requested function is executed immediately.

Or do I see this wrong?

Henk

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Try both methods. I would expect little difference in code size for 16 function switch. For a 4 case switch I would expect an if else sequence. For a 16 case switch I would expect the compiler to binary chop the search. I would not expect a significant speed penalty.

However when you use function pointers, the compiler may not be able to do a full call-graph analysis. Using the switch statement it can.

Some compilers with some processors will not overlay the function auto variables properly. I have not looked to see what avr-gcc does, so it may not be an issue. If all auto variables are on a stack of sufficient depth you do not get the overlay problem.

Hint. do not use function pointers with Keil 8051 C.

David.

Last Edited: Sat. Sep 29, 2007 - 04:01 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Depends on the optimization the compiler does automatically.

If the functions are only called once from the switch-case statement block and nowhere else, your compiler might optimize away the actual function call and inline the code, at least if the function is told to be static or inline, but still the code must go through the switch-case table in order, which means that the last function takes the most overhead to execute and the first function takes the least overhead.

With function table, the function must always be called with full entry and exit code, but every function will have the exact same amount of overhead.

If these few nanoseconds are important to you, then you must experiment and measure yourself what is faster to you and what fits best to your memory needs.

Please report back here what you found out :)

- Jani

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Jepael wrote:
still the code must go through the switch-case table in order, which means that the last function takes the most overhead to execute and the first function takes the least overhead.

No, switch does not test each case! why would it do that?

If all your cases are in order the compiler automatically makes a jump table which is the same as your array of function pointers except it might be even more efficient.

If the cases aren't in order your array won't work anyway, and the compiler still doesn't have to test each case, it uses a binary search.

I would just use the switch and inline the functions if you care about execution speed.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

It has been my experience that sometimes avr-gcc fails to create jump tables automatically for switch-case blocks, even if that block does happen to contain all consecutive values.

I've seen cases where, for example, a chain of if-elseif clauses actually ended up more size efficient than switch-case for around 7 or so consecutive possibilities.

And I have seen a switch-case block with around 30 consecutive possibilities which actually ended up more space efficient when it was explicitly translated into a table of function pointers. (It also had the side effect of becoming a lot easier for me to keep track of all the different cases and maintain the code going forward.)

Mind you, this was all with a previous version of AVR-GCC. Things may have improved since GCC 4.x came along.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Embedded Systems Programming, May 1999 provides good background material in the article called "Arrays of Pointers to Functions".

Can anyone suggest other references?

Cheers

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

lfmorrison wrote:
It has been my experience that sometimes avr-gcc fails to create jump tables automatically for switch-case blocks, even if that block does happen to contain all consecutive values.

I've seen cases where, for example, a chain of if-elseif clauses actually ended up more size efficient than switch-case for around 7 or so consecutive possibilities.

Interesting, I made an assumption here. Wouldn't it be more worthwhile to fix gcc than to hack your program?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

geckosenator wrote:

Interesting, I made an assumption here. Wouldn't it be more worthwhile to fix gcc than to hack your program?

It appears that gcc does produce varying code for switch statements. There are several different algorithms and I do not see bad code from them.

From the OP's point of view. An interpreter driven from RS232 is not going to be too time-critical. Different switch algorithms will not make much difference in speed.

If he was implementing a RTOS then it is probably worth using function pointers and hand optimised assembly code.

ie his application is specific. the compiler has to be generic.

David.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

geckosenator wrote:
Interesting, I made an assumption here. Wouldn't it be more worthwhile to fix gcc than to hack your program?

I didn't consider it "hacking" at the time - I was simply choosing one completely syntactically equivalent construct instead of another when I saw that one had advantages over the other for the particular problem at hand.

Again, this was with a version of GCC in the 3.4.x series if I recall correctly. It's entirely possible that things have improved in GCC 4.x.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

A switch statement can be compiled into several different assembly "forms", and the choice on which form (according to the optimization level) is part of the compiler's heuristics. Which basically means that you, as the programmer, have very little control over it. A simple one line change can cause a whole different assembly output. This is why I always caution against using switch statements in C for embedded systems. If you want to have an array of pointers to functions, then code it as such in C. Don't expect the compiler to do it correctly for you.

And no, it is not easier to hack GCC then it is to hack your own code.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

davef wrote:
Embedded Systems Programming, May 1999 provides good background material in the article called "Arrays of Pointers to Functions".

Can anyone suggest other references?

Cheers

Hi,

Below is a quick example, with no range checking, etc, etc. Just what you need to get going.

/* Define a pointer to void ...(void) Function */
typedef void (*FuncPtr_t)(void);

/* Prototypes for Functions */
void Function01(void);
void Function02(void);
void Function03(void);

/* Handlers are addresses of functions */
FuncPtr_t Handler[] = {
  Function01,
  Function02,
  Function03
  };

/* The pointers are executed by () */
void ServiceRx(unsigned char rx)
{
  Handler[rx]();
}
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

EW wrote:
... This is why I always caution against using switch statements in C for embedded systems. ...

Hmmm--"always"? I guess since it is a "caution", and not a "never", those who use protothreads or other incarnations of Duff's Device cannot object too strongly.

Lee

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

:)
Show me a use of Duff's Device for an embedded system...

And at the risk of sounding trite, I never say never. :)

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

Show me a use of Duff's Device for an embedded system...

Adam Dunkel's protothreads.
http://www.sics.se/~adam/pt/
Quote:
Protothreads are extremely lightweight stackless threads designed for severely memory constrained systems, such as small embedded systems or wireless sensor network nodes. ...

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I'm familiar with the Protothreads overall project, but does it have Duff's deivce in its implementation? Where at?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

I'm familiar with the Protothreads overall project, but does it have Duff's deivce in its implementation? Where at?

http://www.sics.se/~adam/pt/expa...
Quote:
Did you notice anything slightly strange with the code above? The switch(pt->lc) statement jumped right into the while(1) loop. The case 12: statement was inside the while(1) loop! Does this really work? Yes, it does in fact work! This feature of the C programming language was probably first found by Tom Duff in his wonderful programming trick dubbed Duff's Device. The same trick has also been used by Simon Tatham to implement coroutines in C (a terrific piece of code).

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

If you are all that constrained, why would you use C in the first place?

Seems that one would use assembler in an embedded system so limited that couldn't handle a switch statement.

The only time I've seen an array of function pointers in a commercial application, I came to the conclusion that the programmer was looking for job security (he was also a snotty arrogant butthead, so that may have affected my judgment of the concept).

Are we talking about being fancy for the sake of being fancy, or is using an array of function pointers a good programming practice? If so, can you point to some tutorial or discussion that dumbs the topic down a bit so that I can maybe drop a bit of my prejudice to the concept?

Smiley

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

There are currently two threads on switch statements and calling indexed functions.

This thread appears to be about efficiently executing a function by number. Using an array of function pointers is the obvious solution.

However the functions should have similar signatures and you should be aware that recursion or nested calling could give stack problems. The compiler cannot really do a proper call-graph analysis.

Most code is not executed by function number and is thus more clearly written with if else or switch statements.

I cannot speak for Smiley's experience with function pointers. IMHO they have their place.

David.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Joe,

See the large piece of code I posted to page 6 the "smallest bootloader" thread:

https://www.avrfreaks.net/index.p...

which is actually an example of someone trying to use C but trying to out-manoeuvre the C compiler by implementing a dispatch table rather than coding a switch or a multiple if/"else if's" because tight code was the ultimate design goal here (in a (failed) aim to get the 109 bootloader into 512 bytes)

But I agree that it's kind of unusual to do this unless you are TIGHT up against a space constraint and cannot afford to let the C compiler "do it's own thing" - otherwise I'd just go with whatever it thinks is optimal until the code size hits the buffers and you need to start "hand optimising" - but things like -mshort-calls and -nostdlib buy you far more space than things like this - even with the 28 cases: that were being used here.

Cliff (operating incognito)

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

theusch wrote:
Quote:

I'm familiar with the Protothreads overall project, but does it have Duff's deivce in its implementation? Where at?

http://www.sics.se/~adam/pt/expa...
Quote:
Did you notice anything slightly strange with the code above? The switch(pt->lc) statement jumped right into the while(1) loop. The case 12: statement was inside the while(1) loop! Does this really work? Yes, it does in fact work! This feature of the C programming language was probably first found by Tom Duff in his wonderful programming trick dubbed Duff's Device. The same trick has also been used by Simon Tatham to implement coroutines in C (a terrific piece of code).

Hot damn! Thanks for the quote Lee! :)

Eric

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

smileymicros wrote:
If you are all that constrained, why would you use C in the first place?

Seems that one would use assembler in an embedded system so limited that couldn't handle a switch statement.

The only time I've seen an array of function pointers in a commercial application, I came to the conclusion that the programmer was looking for job security (he was also a snotty arrogant butthead, so that may have affected my judgment of the concept).

Are we talking about being fancy for the sake of being fancy, or is using an array of function pointers a good programming practice? If so, can you point to some tutorial or discussion that dumbs the topic down a bit so that I can maybe drop a bit of my prejudice to the concept?

Smiley

Hi Joe,

Also see this other thread:
https://www.avrfreaks.net/index.p...

This is not about being fancy for the sake of being fancy. It's like any real language. There may be big words and ways to use them that make for a terse, appropriate statement. It's better to increase your understanding of the language so you can express yourself in better ways.

There are two very common areas where a table of function pointers make a fairly efficient implementation, even in embedded systems:

1. Menus
2. Dispatch Tables (for communications)

And even, then both of those are just slightly different views of the same thing.

In a menu, a user selects a menu option, and something will happen, i.e. a function will execute. It is easier to implement this with a data structure, such that the menu option text, is associated with the function that gets executed. Which means that you need to take the address of the function and put it into the same data structure that the address of the menu option string is located in. Then, code that executes the menu becomes generic: it takes the data structure and displays the string. When the user moves a cursor to the selection, the string is then highlighted (with color, or inverted like on an LCD), and then when the user presses a selection button (like Enter), the code is already indexed to the specific menu option data structure and it will grab the function address, dereference it, which indirectly calls the function to execute the menu option.

Now, yes this can save a lot of space when writing a large menu. But, more importantly, once the menu code is written, it becomes simple to add menu options or remove menu options because all you have to do is to add or remove data structures. You don't have to add lines to this and that function, or remove lines from this and that function. When one has to add/remove lines from functions, the possibility for errors occurs. Granted, errors can happen when adding/removing data structures, but they are smaller errors and the data structures are located in a single area. So the real benefit here is faster coding and easier modifications down the road, in addition to the potential space savings.

A dispatch table is very similar to a menu. The idea here is that if you have a communications system, where one device (or person) is sending a command to another device. The device that is receiving the command can turn the command into an index into a table of function pointers, and then pull the address of the function, dereference it and indirectly call the function. This function can then take over the communications and get the number of parameters for itself. This way, each command can have a variable number of parameters. In a way this is just a different way implementing a "menu", just without a display, and adding a communications portion.

HTH
Eric Weddington

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Eric,

Some days I feel like an old cow that keeps stepping on it's own udders.

When you said 'menus' I said 'ouch' since I have a whole chapter in my book where I use function pointers as part of a menu structure containing the state, state text, and state function pointer that is used for the menu system on the Butterfly.

I guess it was the thought of an table of function pointers that threw me since that was what my former colleague used to such confusing effect IIRC his work used an index into a table of functions and I couldn't understand the logic of his indexing scheme. Then again, maybe my udders are getting too long.

Thanks,
Joe

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I can do like this...

typedef BYTE (*TFunction)(BYTE bAction);

TFunction rgpfnFunctions[] = {Function1, Function2};

b = rgpfnFunctions[0](0);  // Call function

But the array will be in SRAM also. To only have it in flash I add PROGMEM...

TFunction rgpfnFunctions[] PROGMEM = {Function1, Function2};

Now it does not work!
What is wrong?

//Michael

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Define "does not work" - you mean you can't now cal through a function pointer from the array?

TFunction p_fn;
p_fn=pgm_read_word(&rgpfnFunctions[0]);
p_fn(0);

Should do the same as before.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

"does not work" = reset (or simular), my program seems to start from beginning.

TFunction pfn;
pfn = (TFunction)pgm_read_word(&rgpfnFunctions[0]);
b = pfn(0);

Did the trick, now it works.

Thanks