# Notes on PFFFT
We strongly recommend to **read this file** before using PFFFT and to **always wrap** the original C library within a C++ wrapper.

[Example of PFFFT wrapper](https://cs.chromium.org/chromium/src/third_party/webrtc/modules/audio_processing/utility/pffft_wrapper.h).

## Scratch buffer
The caller can optionally provide a scratch buffer. When not provided, VLA is used to provide a thread-safe option.
However, it is recommended to write a C++ wrapper which allocates its own scratch buffer.
Note that the scratch buffer has the same memory alignment requirements of the input and output vectors.

## Output layout
PFFFT computes the forward transform with two possible output layouts:
1. ordered
2. unordered

### Ordered layout
Calling `pffft_transform_ordered` produces an array of **interleaved real and imaginary parts**.
The last Fourier coefficient is purely real and stored in the imaginary part of the DC component (which is also purely real).

### Unordered layout
Calling `pffft_transform` produces an array with a more complex structure, but in a more efficient way than `pffft_transform_ordered`.
Below, the output produced by Matlab and that produced by PFFFT are compared.
The comparison is made for a 32 point transform of a 16 sample buffer.
A 32 point transform has been chosen as this is the minimum supported by PFFFT.

Important notes:
- In Matlab the DC (Matlab index 1 [R1, I1]]) and Nyquist (Matlab index 17 [R17, I17]) values are not repeated as complex conjugates.
- In PFFFT the Nyquist real and imaginary parts ([R17, I17]) are omitted entirely.
- In PFFFT the final 8 values (4 real and 4 imaginary) are not in the same order as all of the others.
- In PFFFT all imaginary parts are stored as negatives (like second half in Matlab).

```
+-------+-----------+-------+-------+
| Index |  Matlab   | Index | PFFFT |
+-------+-----------+-------+-------+
|     1 | R1 + I1   |     0 | R1    |
|     2 | R2+ I2    |     1 | R2    |
|     3 | R3 + I3   |     2 | R3    |
|     4 | R4 + I4   |     3 | R4    |
|     5 | R5 + I5   |     4 | -I1   |
|     6 | R6 + I6   |     5 | -I2   |
|     7 | R7 + I7   |     6 | -I3   |
|     8 | R8 + I8   |     7 | -I4   |
|     9 | R9 + I9   |     8 | R5    |
|    10 | R10 + I10 |     9 | R6    |
|    11 | R11 + I11 |    10 | R7    |
|    12 | R12 + I12 |    11 | R8    |
|    13 | R13 + I13 |    12 | -I5   |
|    14 | R14 + I14 |    13 | -I6   |
|    15 | R15 + I15 |    14 | -I7   |
|    16 | R16 + I16 |    15 | -I8   |
|    17 | R17 + I17 |    16 | R9    |
|    18 | R16 - I16 |    17 | R10   |
|    19 | R15 - I15 |    18 | R11   |
|    20 | R14 - I14 |    19 | R12   |
|    21 | R13 - I13 |    20 | -I9   |
|    22 | R12 - I12 |    21 | -I10  |
|    23 | R11 - I11 |    22 | -I11  |
|    24 | R10 - I10 |    23 | -I12  |
|    25 | R9 - I9   |    24 | R13   |
|    26 | R8 - I8   |    25 | R16   |
|    27 | R7 - I7   |    26 | R15   |
|    28 | R6 - I6   |    27 | R14   |
|    29 | R5 - I5   |    28 | -I13  |
|    30 | R4 - I4   |    29 | -I16  |
|    31 | R3 - I3   |    30 | -I15  |
|    32 | R2 - I2   |    31 | -I14  |
+-------+-----------+-------+-------+
```