Is there a way to create an array of combined functions compile-time in c++?

Question

I'm working on an NES emulator in c++ and figured that the most efficient way to run opcodes would be to call a function pointer in an array of functions that do exactly what the opcode does.

The problem is that each opcode has a specific operation and memory address. While searching for a solution, I stumbled upon lambda expressions. This is definitely good enough for a NES emulator on modern hardware. However, I can't find a solution such that each function in the array contains the machine code for both the operation and the addressing without defining 256 separate functions.

This is along what I had in mind for a similar function that combines f and g:

int addone(int x) {
  return x + 1;
}

int multtwo(int x) {
  return 2 * x;
}

something combine(function<int(int)> f, function <int(int)> g) {
  /* code here */
}

/*
combine(addone, multtwo) creates a function h that has the same machine code as
int h(x) {
  return 2 * x + 1;
}
*/

Any ideas? If I had to take a guess, it would have something to do with templates. Thanks!

Answer 1

I'd say that when you want to write generics for functions that it's kind of a "design pattern" to switch to functors: Compilers are desigined to handle types easily, but handling function pointers for stuff you want to mis-match and keep optimised at compile-time gets ugly!

So we either write our functions as functors, or we wrap them as functors:

struct A
{
    static constexpr int Func (int x)
    {
        return -3*x + 1;
    }
};

struct B
{
    static constexpr int Func (int x)
    {
        return -2*x - 5;
    }
};

// etc...

If we have nice symmetry in how we'll use them, then we can manage them systematically. Eg. if we always want to combine them like f(g(h(...y(z())...))), then we can solve as follows:

template <class T, class ... Ts>
struct Combine
{
    static constexpr int Get ()
    {
        int x = Combine<Ts...>::Get();
        return T::Func(x);
    }
};

template <class T>
struct Combine <T> // The base case: the last function in the list
{
    static constexpr int Get ()
    {
        return T::Func();
    }
};

demo

Or if we're in no such luck, we'll have to resort to more old-fashioned inputs like you suggested:

template <class Funcs, class Data>
constexpr int Combine (const Data & d) 
{
    Funcs F;
    // Some use without much symmetry:
    return F.f(F.g(d)) - F.h(d);
}

int main ()
{
    struct FuncArgs
    {
        A f;
        B g;
        C h;
    };

    return Combine<FuncArgs>(5);
}

demo

Note that in the second example I've changed from static methods to non-static. This doesn't really matter - the compiler should optimise these fully regardless, but I think in this case it makes the syntax slightly nicer (and shows an alternative style).

Answer 2

You can do something like this, using a lambda to capture the two functions and to assign a function to a variable:

#include <functional>
#include <iostream>


int addone(int x){
    return x + 1;
}

int multtwo(int x){
    return x * 2;
}

std::function<int(int)> combine(std::function<int(int)> f, std::function<int(int)> g){
    auto tmp = [&](int x){ return f(g(x)); };
    return std::function<int(int)>(tmp);
}

int main(){
    auto h = combine(std::function<int(int)>(addone), std::function<int(int)>(multtwo)); // (2 * x) + 1
    std::cout << h(10); // Prints 21
}

If you want it to generally combine the functions, you can use a template:

#include <functional>
#include <iostream>


int addone(int x){
    return x + 1;
}

int multtwo(int x){
    return x * 2;
}

template <typename Func>
std::function<Func> combine(std::function<Func> f, std::function<Func> g){
    auto tmp = [&](int x){ return f(g(x)); };
    return std::function<Func>(tmp);
}

int main(){
    auto h = combine<int(int)>(std::function<int(int)>(addone), std::function<int(int)>(multtwo));
    std::cout << h(10) << "\n"; // Prints 21
}

You also don't need to specify the type, since the compiler can figure it out:

#include <functional>
#include <iostream>


int addone(int x){
    return x + 1;
}

int multtwo(int x){
    return x * 2;
}

template <typename func>
std::function<Func> combine(std::function<Func> f, std::function<Func> g){
    auto tmp = [&](int x){ return f(g(x)); };
    return std::function<Func>(tmp);
}

int main(){
    auto h = combine(std::function<int(int)>(addone), std::function<int(int)>(multtwo));
    std::cout << h(10) << "\n"; // Still prints 21
}

Answer 3

If you want to create automatically the functions, use 2pichar's answer with a for loop, but for an emulator you'd probably want something like opcode->int(*)(int). This could be done by some tree-like structure:

std::map<char, naive_opcode> opcodes;
struct naive_opcode {
    std::map<char, naive_opcode> next;
    int(* opcode_func)(int);
};

You'd work through this in some fashion like:

char data;
buf >> data;
naive_opcode opcode = opcodes[data];
while(!opcode.opcode_func){
    buf >> data;
    opcode = opcode.next[data];
}
opcode.opcode_func(param);

This of course ignores errors and does not include things like the instruction pointer and the .text section memory, rather replacing it with the buf buffer for illustrative purposes (In a real life example I'd expect this to be replaced by data=memory[ip]; ++ip;). This could then be combined with an implementation like:

#include <iostream>


int addone(int x){
    return x + 1;
}

int multtwo(int x){
    return x * 2;
}

template<int(* F)(int), int(* G)(int)>
int combined(int x){
    return F(G(x));
}

int main(){
    std::cout << combined<addone,multtwo>(10);
}

for which you could essentially just define the end node of naive_opcode as {{}, combined<addone,multtwo>}.

Unfortunately as I mentioned in my comment, this probably cannot be done automatically. The best you could do I recon is that you define something like:

std::vector<std::pair<const char*, int(*)(int)>> raw_opcodes = {{"\x10\x13", addone}, ...};

and then parse that into the tree like structure. As a brief side note: this might not be needed if all the opcodes are 1 byte (which I am unsure about since I am not familiar with NES). Then a simple std::map<char,int(*)(int)> opcodes will suffice instead of the convoluted naive_opcode (or better tree) implementation.

Looked it up and it seems that you wouldn't need the tree implementation, but a modification like this can be useful:

template<int(* F)(int)>
int combined(int x){
    return F(x);
}

template<int(* F)(int), int(* A)(int), int(*... G)(int)>
int combined(int x){
    return F(combined<A, G...>(x));
}

This allows for combining many effects into each other, rather than 2.

Answer 4

We can use templates to create a generic compose function that "combines" two unary functions using a lambda that captures the functions passed in, and returns it.

#include <functional>
#include <iostream>

template <typename Input, typename Output1, typename Output2>
std::function<Output2(Input)> compose(
    std::function<Output2(Output1)> f, 
    std::function<Output1(Input)> g
) {
    return [&f, &g](Input x) { return f(g(x)); };
}

int foo(int x) {
    return x + 1;
}

int bar(int x) {
    return x * 2;
}

int main() {
    auto baz = compose<int, int, int>(foo, bar);

    std::cout << baz(5) << std::endl;

    auto wooble = compose<int, int, float>(
        [](int x) { return static_cast<float>(x) + 1.5; },
        [](int x) { return x * 3; }
    );

    std::cout << wooble(5) << std::endl;   

    return 0;
}

Answer 5

Do you want this?

int f1(int x) { return x + 1; }
int f2(int x) { return x * 2; }
int f3(int x) { return x * 3; }
int f4(int x) { return x - 5; }
int f5(int x) { return x + 9; }

int main() {
    auto cf = combine<int>(f1, f2, f3, f4, f5);
    std::cout << cf(5) << std::endl;
    return 0;
}

Output:
40

Full code:

#include <functional>
#include <concepts>
#include <iostream>

template<typename T, typename NUM = int>
concept num_processor = requires (T t, NUM x) {
    {t(x)} -> std::same_as<NUM>;
};

template<typename NUM, num_processor p>
NUM process(NUM v, p proc) {
    return proc(v);
}

template<typename NUM, num_processor p, num_processor... Funs>
NUM process(NUM v, p proc, Funs... funs) {
    return process(proc(v), funs...);
}

template<typename NUM, num_processor... Funs>
std::function<NUM (NUM)> combine(Funs... funs) {
    return [...funs = funs] (NUM v) { return process(v, funs...); };
}

int f1(int x) { return x + 1; }
int f2(int x) { return x * 2; }
int f3(int x) { return x * 3; }
int f4(int x) { return x - 5; }
int f5(int x) { return x + 9; }

int main() {
    auto cf = combine<int>(f1, f2, f3, f4, f5);
    std::cout << cf(5) << std::endl;
    return 0;
}

Compile with -std=c++20 for gcc and /std:c++latest for msvc

Answer 6

Most other answers suggest std::function, but I'm wary of the runtime overhead it requires.

Since you don't need to select which functions are composed at runtime, you can do it without it. I'm using the same idea as @Elliot, but generalized for arbitrary types, and with hopefully nicer syntax:

#include <iostream>
#include <utility>

template <auto F0, auto ...F>
struct FuncList
{
    static constexpr auto first = F0;
    static constexpr bool have_next = true;
    using next = FuncList<F...>;
};
template <auto F0>
struct FuncList<F0>
{
    static constexpr auto first = F0;
    static constexpr bool have_next = false;
};

template <typename F, typename ...P>
decltype(auto) Combine(P ...params) // Normally there would be `&&`, but I removed it allow casting to any function pointer type.
{
    if constexpr (F::have_next)
        return F::first(Combine<typename F::next, P &&...>(std::forward<P>(params)...));
    else
        return F::first(std::forward<P>(params)...);
}

int addone(int x)
{
    return x + 1;
}

int multtwo(int x)
{
    return 2 * x;
}

int main()
{
    int (*ptr)(int) = Combine<FuncList<addone, multtwo>>;
    std::cout << ptr(10) << '\n'; // 21
}