# Missing `const`

I see you sprinkled `const` almost everywhere. However, you actually missed the one spot where it actually matters most: `input` should be a `const` pointer:

```
_Bool fft(const complex_t* input, complex_t* output, const unsigned int size) {
    ...
}
```

# Use the `restrict` keyword if possible

Since `input` and `output` are of the same type, they can alias. This might prevent the compiler from generating optimal code, as it now must assume that any write to a value of `output` might change a value in `input`. Annotate these pointers with the [`restrict`][1] keyword if supported by your compiler.

Note that making `input` a `const` pointer [doesn't prevent aliasing][2].

# Avoid divisions

Divisions are one of the slowest operations on any CPU, but especially on low end CPUs they might take tens of times more cycles than a multiply. You can avoid the division when calculating `angle` by writing:

```
double angle = -M_PI;
for (unsigned int even_to_odd = 2; even_to_odd < size; even_to_odd *= 2) {
    angle *= 0.5;
    ...
}
```

But perhaps even better:

# Consider using sin/cos look-up tables

`cos()` and `sin()` are transcedental functions that can take a long time to evaluate, especially on weak microcontrollers. On the other hand, microcontrollers usually have very low memory access latencies. So it might make sense to pre-calculate all the possible values of `sin(angle)` and `cos(angle)` that you might encounter, and store them in a look-up table.

  [1]: https://en.cppreference.com/w/c/language/restrict
  [2]: https://stackoverflow.com/questions/32706977/c-modify-const-through-aliased-non-const-pointer