CODEWITHSUNDEEP
cgccfunction-pointersmicrocontroller
Gordon Williams
Gordon Williams

Reputation: 1886

GCC + C: Keeping Functions in order in the binary file

I'm doing some code for microcontrollers where I need to look up data based on function pointers (this data and the functions will be in ROM).

I'd like to be able to do this relatively quickly, and without using RAM for a lookup table. The easiest way I can think to do this would be to do a binary search.

I just hacked this up as an example, so it might be broken but hopefully you get the idea:

void myFunction1() {}
void myFunction2() {}
void myFunction3() {}
void myFunction4() {}
// ...

typedef struct {
  void *functionPtr;
  int myData[10];
} SearchData;

const SearchData mySearchData[] = {
 { &myFunction1, ... },
 { &myFunction2, ... },
 { &myFunction3, ... },
 { &myFunction4, ... },
 // ...
};

void doBinarySearch(void *func, int min, int max) {
  if (max<min) return;
  int mid = (min+max)/2;
  if (func < mySearchData[mid].functionPtr)
    doBinarySearch(func, min, mid-1);
  else if (func > mySearchData[mid].functionPtr)
    doBinarySearch(func, mid+1, max);
  else {
    // we found it!
  }
}

void realBinarySearch(void *func) {
  doBinarySearch(func, 0, (sizeof(mySearchData)/sizeof(SearchData))-1);
}

However for this to work, myFunction1, myFunction2, etc need to be laid out one after the other in memory (although not necessarily right next to each other). I need to compile everything with -Os to fit it in available ROM, so how do I ensure that the functions actually stay in the correct order?

...or failing that, how could I re-order mySearchData such that it matches the order of the functions?

About the only things I can think of right now are:

Neither of those sound great though.

Upvotes: 1

Views: 1547

Answers (2)

Klaus
Klaus

Reputation: 25623

OK,. I did not really understand why you need a function pointer to SEARCH for a function... It is much simpler to put the data to the function which in that case will also be reordered. But you are asking for that.

OK, gcc in C code is given:

You can place every function in its own section by adding:

void f1() __attribute__((section(".text.1")));
void f1()
{
}

void f2() __attribute__((section(".text.2")));
void f2()
{
}

void f3() __attribute__((section(".text.3")));
void f3()
{
}

And you then use a modified linker script like this:

 .text   :
  {
   ....
   *(.text.1)
   *(.text.2)
   *(.text.3)
   ... continues here ...

Also there are a lot more possibilities in linker script to sort input sections. Look ld description for SORT!

From the ld manual: Normally, the linker will place files and sections matched by wildcards in the order in which they are seen during the link. You can change this by using the SORT keyword, which appears before a wildcard pattern in parentheses (e.g., SORT(.text*)). When the SORT keyword is used, the linker will sort the files or sections into ascending order by name before placing them in the output file.

But as a remark, I believe you have a XY-problem. I think you would do something and sorting functions and dealing with binary search is your solution for it. I believe that the origin problem can be solved without such hacks!

It would be nice to get your original problem!

Upvotes: 4

Behrooz
Behrooz

Reputation: 1734

Litteral answer to question:
How can I force the order of functions in a binary with the gcc toolchain?
this link http://sourceware.org/binutils/docs-2.21/ld/Scripts.html#Scripts
It's SCARY but works

EDIT:
Method 2 partition the lookup table:
partition by nibble, it's very efficient.You just need an initialization step. allocate 16 bytes.read all the elements in the array. "&" the 1st byte of function pointer with 0x0F, and increment the slot in the resulting offset. allocate 16 lists with the lengths that you just calculated. re-read all the elements in the array, this time insert them in the allocated lists and use the 16 bytes as counter for where you're putting the pointer.
btw do you have dynamic memory allocation? I just realized you said 8KiB.

Upvotes: 1

Related Questions