1

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:

  • build the whole thing and then have a post-processing step that sorts the array inside the binary - very un-portable though.
  • build once, look at the list file to figure out the real order of functions, re-write mySearchData and compile again - but there's no guarantee the compiler is deterministic

Neither of those sound great though.

Gordon Williams
  • 1,856
  • 1
  • 17
  • 31
  • ...or if I generated a big switch statement, would the compiler be smart enough to optimise it? – Gordon Williams Aug 14 '15 at 15:35
  • Your concern about post-processing is that things will be unportable -- but it seems that any build time solution you come up with is going to be unportable (and in some cases, could even break if you update to a newer gcc). Perhaps a better solution is to not make your table const and instead have an initialization step that sorts it at runtime. – mah Aug 14 '15 at 15:38
  • Yes, it will be smart enough. usually. – Behrooz Aug 14 '15 at 15:38
  • AFAICT you're doing this to keep the args in a table, right? – Behrooz Aug 14 '15 at 15:38
  • Another thing that you can do is partitioning your list and using a normal boring linear search. You could partition by the 1st byte of pointer.makes 256 arrays.Or 1st nibble, that makes 16 arrays. – Behrooz Aug 14 '15 at 15:40
  • I don't catch your problem! Your table with your data is sorted by hand and not related to any relocation and link time. And the pointers which are included into the function are relocated by the linker and must NOT be ordered because there is no need for that? Something I did not caught? – Klaus Aug 14 '15 at 15:41
  • @Klaus, I think he's using this to locate the arguments required for each function call. – Behrooz Aug 14 '15 at 15:43
  • The problem is I have 8kB of RAM in the micro. I don't want to waste it on something that is never going to change after it is calculated. Partition is a good idea, but I'm not sure I can do that in C? I just checked and it refuses to let me switch on function pointers. – Gordon Williams Aug 14 '15 at 15:46
  • 1
    how many functions are there? – Behrooz Aug 14 '15 at 15:48
  • if it's less than 50 you're wasting cycles with this, use linear search. – Behrooz Aug 14 '15 at 15:48
  • @Behrooz That's a good point. It's around 100 at the moment - I guess it's not likely to ever be more than 200 though. The file that references the functions is machine generated, but the functions themselves aren't. – Gordon Williams Aug 14 '15 at 15:51
  • changing my answer now. – Behrooz Aug 14 '15 at 15:55
  • Thanks for all the help so far - it's a language interpreter for JS (called Espruino) and I'm hoping to improve the symbol lookup on it. In RAM, I have a bunch of vars, but all the library functions and their names (around 700 of them) are in symbol tables in ROM. As it's JS, a function can have other fields inside it so I need a way to get from that function's pointer to the symbol table for that function. Very little apart from the fn's pointer is stored in RAM (and ideally I wouldn't change any of that side of things as it works well as-is) so I just need a way to look up via fn ptr – Gordon Williams Aug 14 '15 at 16:35
  • I actually auto-generate a series of 'if' statements right now, but I was looking for a way to improve on that. edit: I have to leave for the weekend now, but will check up on monday. – Gordon Williams Aug 14 '15 at 16:36

2 Answers2

2

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!

Klaus
  • 24,205
  • 7
  • 58
  • 113
1

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.

Community
  • 1
  • 1
Behrooz
  • 1,696
  • 2
  • 32
  • 54
  • Do you have an example of sorting things with a linker script? I do already use a custom one and I could tag all things I want sorted as needing to go in a specific section. – Gordon Williams Aug 14 '15 at 15:48
  • Thanks for adding Method 2 - you're suggesting allocating the lists up front? Still a lot of RAM - ignoring allocation overhead, for 100 functions that's 1400 bytes (out of my 8192) in that example. – Gordon Williams Aug 14 '15 at 16:17
  • You can erase the initial list after you initialize your partitions. – Behrooz Aug 14 '15 at 16:45